关于遗传算法

Question

目前，我正在学习遗传算法(个人的，不是必需的)，我遇到了一些我不熟悉或者只是基本熟悉的话题，它们是：

• 搜索空间
• 函数的“极端”

我知道一个人的搜索空间是所有可能的解决方案的集合，但我也想知道如何决定他们搜索空间的范围。此外，我想知道与函数有关的极限是什么，以及如何计算。

我知道我应该理解这些是什么，但到目前为止，我只学了代数2和几何学，但是我尝试了物理、矩阵/向量数学和数据结构，所以如果我看起来很天真的话，请原谅我。

Answer 1

通常，在一组项中寻找特定项的所有算法都称为搜索算法。当由数学函数(与数据库中的存在相反)定义项集合时，它被称为搜索空间。

这类最著名的问题之一是旅行商问题，在该问题中，需要搜索一个算法，该算法将给出一个城市及其距离的列表，该算法只为每个城市寻找一次访问的最短路径。对于这个问题，只有研究所有可能的路由(整个搜索空间)，并找到最短的路由(具有最小距离的路由，即搜索空间中的极值值)，才能找到确切的解决方案。这种算法的最佳时间复杂度(称为穷尽搜索)是指数(尽管仍然有可能存在更好的解决方案)，这意味着最坏情况下的运行时间随着城市数量的增加呈指数增长。

这就是遗传算法发挥作用的地方。与其他启发式算法算法类似，遗传算法试图通过迭代地改进候选解来接近最优解，但不能保证实际找到最优解。

这种迭代方法存在这样一个问题，即算法很容易陷入局部极值(同时试图改进解决方案)，而不知道在更远的地方有一个可能更好的解决方案：

​

​

图中显示，为了得到实际的最优解(全局最小值)，目前研究局部最小值的算法需要在搜索空间中“跳过”一个较大的最大值。一种遗传算法将快速定位这样的局部最优，但它通常不会“牺牲”这一短期收益，以获得一个潜在的更好的解决方案。

因此，总结如下：

• 穷举搜索

- examines the entire search space (long time)
- finds global extremes

​

• 启发式(例如遗传算法)

- examines a part of the search space (short time)
- finds local extremes

​

Answer 2

遗传算法不能很好地调整到局部最优。如果您想要找到一个全局最优，至少您应该能够接近或找到一个策略来接近局部最优。为了更好地找到局部最优解，最近进行了一些改进。

基于小波包分解的信息基函数选择遗传算法及其在声发射腐蚀识别中的应用

pdf/化学计量学

Answer 3

一般来说，“搜索空间”的意思是，你在寻找什么样的答案。例如，如果您正在编写一种建立桥梁、测试它们然后构建更多的遗传算法，那么您正在寻找的答案就是桥模型(以某种形式)。作为另一个例子，如果您试图找到一个函数，它与一些点上的一组样本输入一致，您可以尝试找到一个具有此属性的多项式。在这种情况下，搜索空间可能是多项式。您可以通过对项的数目、多项式的最大度等设置一个界来简化这一点。所以你可以指定你要在- 4，4的范围内搜索整数指数的多项式。在遗传算法中，搜索空间是你可以生成的一组可能的解。在遗传算法中，你需要仔细限制你的搜索空间，这样你才能避免那些完全愚蠢的答案。在我以前的大学里，一个物理学生写了一个程序，它是一个遗传算法，用来计算分子中具有低能性质的原子的最佳构型:他们找到了一个很好的解决方案，几乎没有能量。不幸的是，他们的溶液把所有的原子都放在了分子的中心，这在物理上是不可能的:-)。GAs确实能很好地解决你的健身功能，所以重要的是选择你的搜索空间，这样它就不会产生出健康的解决方案，而实际上是“不可能的答案”。

至于功能的“极端”。这只是函数取其最大值的点。关于遗传算法，你想要对你想要解决的问题找到最好的解决方案。如果你在建造一座桥，你就是在寻找最好的桥。在这个场景中，您有一个健身函数，它可以告诉您“此桥可以承受80磅的重量”和“该桥可以承受120磅的重量”，然后您将寻找比其他的更高的健身值的解决方案。有些函数有简单的极值:你可以用简单的高中微积分找到多项式的极值。其他函数没有一个简单的方法来计算它们的极值。值得注意的是，高度非线性函数具有极值，这可能很难找到。遗传算法擅长于使用一种巧妙的搜索技术来寻找这些解决方案，这种技术可以四处寻找高分，然后再找到其他的。值得注意的是，还有其他算法也能做到这一点，尤其是登山者。气体的不同之处在于，如果你找到一个局部极大值，其他类型的算法可能会被一个局部好的解蒙蔽，这样他们就永远不会在更远的搜索空间看到更好的解。还有其他方法使登山者适应这种情况，比如模拟退火。