0

我正在寻找关于组合优化中搜索算法参数（在线学习）的自适应参数控制的想法/经验/参考/关键字。

更详细一点：

我有一个框架，负责优化硬组合优化问题。这是在一些以迭代方式使用的“小型启发式”的帮助下完成的（大型邻域搜索；破坏和重建方法）。这些“小启发式”的每个算法都采用一些外部参数，这些参数在某种程度上控制着启发式逻辑（目前：只是随机值；某种噪声；使搜索多样化）。

现在我希望有一个控制框架，用于以改进收敛的方式选择这些参数，尽可能通用，以便以后在不更改参数控制的情况下添加新的启发式方法。

至少有两个一般性的决定需要做出：

  • A：选择在下一次迭代中使用的算法对（一个销毁算法和一个重建算法）。
  • B：选择算法的随机参数。

唯一的反馈是新发现的解决方案的评估功能。这让我想到了强化学习这个话题。这是正确的方向吗？

不是真正的学习行为，但目前的简单想法是：

  • A：根据迭代期间收集的一些性能值进行轮盘赌选择（接近过去的比旧的更有价值）。因此，如果启发式 1 确实找到了所有新的全局最佳解决方案 -> 选择这个的可能性很高。
  • B：还不知道。也许可以在 (0,1) 范围内使用一些不均匀的随机值，我正在收集一些变化的动量。因此，如果启发式 1 上次使用 alpha = 0.3 并且没有找到新的最佳解决方案，则使用 0.6 并找到新的最佳解决方案 -> 有朝向 1 的动量 -> 下一个随机值可能大于 0.3。可能的问题：振荡！

需要注意的事项： - 一种特定算法的良好收敛所需的参数可能会发生巨大变化 -> 开始时可能需要更多的多样化操作，最后需要更多的强化操作。- 在一对特定的破坏/重建算法（有时称为：耦合邻域）中可能会产生良好的协同效应。怎么会认出这样的东西？那还在强化学习领域吗？- 不同的算法由不同数量的参数控制（有些取 1，有些取 3）。

有什么想法、经验、参考资料（论文）、关键字（ml-topics）吗？
如果有关于以离线学习方式决定（b）的想法。毫不犹豫地提到这一点。

感谢您的输入。

萨沙

4

2 回答 2

1

您有一组参数变量，用于控制您的算法集。算法的选择只是另一个变量。

您可能要考虑的一种方法是使用遗传算法来发展您的“参数空间”。简而言之，遗传算法使用自然选择过程的类似物来不断培育出更好的解决方案。

您将需要开发一种编码方案来将您的参数空间表示为字符串，然后创建大量候选解决方案作为您的起始代。遗传算法本身在您的集合中采用最合适的解决方案，然后将各种遗传算子应用于它们（突变、繁殖等）以培育出更好的集合，然后成为下一代。

这个过程中最困难的部分是开发一个适当的适应度函数：定量测量给定参数空间的质量。您的搜索问题可能过于复杂，无法衡量总体中的每个候选人，因此您需要一个代理模型函数，该函数可能与理想解决方案本身一样难以开发。

如果不了解您所写的更多内容，就很难看出这种方法是否可行。GA 通常非常适合像这样的多变量优化问题，但它不是灵丹妙药。如需参考，请从 Wikipedia 开始。

于 2010-11-23T15:08:26.897 回答
1

这听起来像是您正在尝试做的超启发式方法。尝试寻找该关键字。

在Drools Planner（开源，java）中，我支持禁忌搜索和模拟退火。我还没有实现破坏和重建方法（还），但这应该很容易，尽管我并不期待更好的结果。挑战：证明我错了，分叉并添加它，并在示例中击败我。超启发式在我的 TODO 列表中。

于 2010-12-24T11:08:58.947 回答