关于遗传算法

Question

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

• 搜索空间
• 功能的"极端"

我知道一个人的搜索空间是所有可能解决方案的集合,但我也想知道如何决定他们的搜索空间范围.此外,我想知道与功能及其计算方式的极端情况.

我知道我应该明白这些是什么,但到目前为止我只采用了代数2和几何,但我已经冒险进入物理,矩阵/矢量数学和数据结构,所以请原谅我,如果我看起来很天真.

Answer 1

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

这种最着名的问题之一是旅行商问题,其中寻找一种算法,该算法将给出城市及其距离的列表,找到仅访问每个城市一次的最短路线.对于这个问题,只能通过检查所有可能的路径(整个搜索空间),找到最短的路径(具有最小距离的路线,即搜索空间中的极值)来找到确切的解决方案.这种算法(称为穷举搜索)的最佳时间复杂度是指数级的(尽管仍有可能存在更好的解决方案),这意味着最坏情况的运行时间随着城市数量的增加呈指数增长.

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

这种迭代方法存在的问题是,算法很容易陷入局部极端(同时试图改进解决方案),而不知道在更远的地方有更好的解决方案:

该图显示,为了获得实际的最优解(全局最小值),当前检查围绕局部最小值的解的算法需要在搜索空间中"跳过"一个大的最大值.遗传算法将快速定位这样的局部优化,但它通常不会"牺牲"这种短期增益来获得可能更好的解决方案.

所以,总结如下:

• 详尽的搜索

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

  • 发现全球极端

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

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

  • 发现当地的极端情况