mathematical-optimization - 对于哪些类型的问题，遗传算法是合适的选择？

Question

（我已经思考了一段时间对于问答网站来说这是否是一个好问题。我认为它是 - 答案可能部分是主观的，但我希望在答案中寻找客观标准。尽管如此不是网络中最好的站点，但让我们在这里试试。）

我问这个问题是因为最近我尝试使用遗传算法来解决具有大参数空间的优化问题，但它失败了，即它没有随着时间的推移而改善。我切换到模拟退火并获得了更好的收敛性。因此，要么我的 GA 实施是错误的，要么是该工作的错误工具。

应用遗传算法的一个典型例子是旅行商问题，基因组是城市被访问的顺序。这是有道理的：“繁殖”或“交叉”混合并重新排列可能已经在本地优化的子路由，但通过更改访问这些子路由的顺序，整体效率可能会提高。类似的例子是背包问题。

我遇到的另一个例子是使用 GA 来找到二维函数的最大值，基因组是坐标。这可能被选为一个简单的教学示例，专注于如何实现 GA，但是首先，在这里，GA 是否是正确的选择似乎不太清楚：只是“任意”交换坐标或 - 在这个实现——取单个基因组的平均值，丢失所有的优化历史。因此，对我来说，这是一个本质上不适合 GA 的问题的示例，因为混合基因组（坐标），这是 GA 的核心思想，在这里似乎没有好处。没有它，即当简化为只有突变时，GA 只是在相空间中随机游走并重新启动。

一般来说，GAs 似乎更适合于具有高组合复杂度的离散解空间的问题，而不是探索连续相空间。还有哪些方面需要考虑？

标签： mathematical-optimizationgenetic-algorithm

Answer 1

很难预测 SA 和 GA 的结果（就像生活本身一样？）。

遗传算法的变异在某种程度上类似于 SA 的邻居提议，所以一个关键的区别是遗传算法的繁殖部分。

假设 x,y 都是针对您的问题的建议解决方案。

如果取 x 的 1 部分和 y 的 1 部分来做出更好的解决方案是有意义的，那么 GA 就有潜力。

您必须结合直觉和实验来检查上述是否属实。

为了搜索确实有意义的参数空间，如果参数 alpha 和 beta 在 1 种情况下运行良好，您可能希望从其他运行良好的提案解决方案中获取 gamma。

为了最小化 2D 中的函数（比如 0 是最小值），这通常没有多大意义，如果 (a,b) 接近 0，并且 (c,d) 接近 0，(a,d) 和(c,b) 与任何其他随机猜测一样好（在许多情况下）。

基于爬山的搜索在后者中更有意义。GA的育种部分与爬山不同。