algorithm - 关于遗传算法

Question

目前，我正在研究遗传算法(个人的，不是必需的)，我遇到了一些我不熟悉或基本熟悉的主题，它们是:

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

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

我知道我可能应该了解这些是什么，但到目前为止我只学习了代数 2 和几何，但我自己尝试了物理、矩阵/向量数学和数据结构，所以如果我看起来很幼稚请原谅.

Answer 1

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

此类最著名的问题之一是 travelling salesman problem ，其中寻找一种算法，该算法将在给定城市列表及其距离的情况下找到仅访问每个城市一次的最短路线。对于这个问题，只有检查所有可能的路径(整个搜索空间)，找到最短的路径(具有的路径)才能找到精确解>最小距离，即搜索空间中的极值)。这种算法(称为穷举搜索)的最佳时间复杂度是指数级的(尽管仍有可能存在 better solution )，这意味着最坏情况下的运行时间呈指数级增长，如下所示城市数量增加。

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

这种迭代方法的问题是算法很容易“卡在”局部极值(同时试图改进解决方案)，而不知道在更远的地方可能有更好的解决方案:

该图显示，为了获得实际的最优解(全局 最小值)，当前检查局部 最小值附近的解的算法需要“跳过”搜索空间中的最大最大值。遗传算法会快速找到此类局部最优解，但它通常不会“牺牲”这种短期 yield 来获得可能更好的解决方案。

因此，总结如下:

• 穷举搜索

  • 检查整个搜索空间(长时间)

  • 找到全局极值

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

  • 检查搜索空间的一部分(短时间)

  • 找到局部极值