0

要设置我的问题,请允许我从一个示例开始:

假设一组 1000 个长度相同的数组(又名行向量)。每个都填充了 -1 和 1 之间的随机数。然后我随机抽取 500 个这些行向量并将它们相加。我现在从总和开始,想从最初的 1000 中对选择进行逆向工程。

我决定用遗传算法解决这个问题。我开始了一系列 1000 位长的位串,并运行了变异(又名,翻转随机位)和交叉过程。然后,十分之一秒后,我是 75% 正确的。然后,再过一个小时,我是对的 76%。本质上,我一直在等待正确设置几十位。可能是我的随机数生成器从未以可以合并到解决方案中的方式引入它们。

该算法在开始时做得很好,但后来未能进一步改进解决方案。我试着确保我的基因家族拥有每一个可能的位置之一。那没有帮助;您无法判断物品会以多快的速度从池中消失。

似乎该算法必须有一个额外的组件。一定有什么东西在驱动翻转位(又名突变)位置的选择。这件作品的技术术语是什么?坡度?它从何而来?

4

4 回答 4

0

这是一个非常全面的教程,应该可以帮助您了解训练过程和所涉及的收敛。你说得对,它是一种梯度下降的形式。

http://informatics.indiana.edu/larryy/al4ai/lectures/03.IntroToGAs.pdf

该文档已移动,现在可以在此处找到:

http://shinyverse.org/al4ai/lectures/03.IntroToGAs.pdf

于 2013-06-25T13:02:23.460 回答
0

遗传算法不是精确算法,而是启发式算法。这意味着无论你多么努力,只有在极少数情况下,你实际上会得到最佳解决方案。因此,您正在用精度换取一些速度。这并不意味着该算法是失败者,只是它是为不需要精确解决方案但需要很好近似的问题而设计的。这也意味着除了找到最优值之外,您还必须有算法的结束条件。这意味着必须存在一个评估解决方案并告诉您它有多好的功能。

如果您想尝试提高一点精度,那么您将不得不使用特定于问题的知识来调整您的启发式方法。这意味着,使用您对问题的了解来设计更好的突变(而不是使用预定义的突变),并改进您对总体的细化,即选择算法。我再重复一遍,这不能保证你会找到最佳的。

在您的特定情况下,我相信几分钟后您会陷入局部最大值。这意味着离这里越远你就不会变得更好。这有时可以通过向总体中注入一些随机元素来解决,以使算法摆脱最大值。这有时也可以通过故意选择不好的解决方案来解决。

于 2013-06-25T13:03:20.233 回答
0

我认为您的意思是“收敛速度”或“收敛速度”。文献中有很多解决您的问题的方法。我建议每次迭代都降低突变率,直到你“陷入”局部最优(收敛率变得太低,绝对或相对),然后你重置或增加突变率以逃避局部最优。

另外,你做什么样的选择?如果父母比孩子好,你会留住他们吗?你选择最好的个人还是轮盘赌选择(保持次优解决方案有更多熵的机会)?

于 2013-06-25T12:41:01.887 回答
0

所以本质上你有一个数字 s 并且你想找到一个数字的子集加起来 s。这被描述为子集和问题,它是背包问题的一个特例。

我认为您对遗传算法应用的解释是错误的。为了可视化从 1000 个项目中选择 500 个项目必须考虑的可能解决方案的数量,请阅读以下数字 [“1000 超过 500”的二项式系数]:

270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320来源)。

我先澄清一下:遗传算法和相关方法是元启发式的,这意味着它们不适合在很短的时间内找到最佳解决方案,而是一个“好”的解决方案。要在 NP 难题中找到最佳解决方案,您必须在最坏的情况下尝试所有可能的组合。有一些精确优化的方法可以智能地划分搜索空间并仅评估较少数量的解决方案,但仍可能需要数周时间才能得出最佳答案。

如果您需要找到这个精确的最佳值,我建议您寻找精确的方法,例如branch 和 bound。例如,您可以使用著名的CPLEX优化器将您的问题描述为整数程序。例如,查看TSP 的 ILP 公式,了解如何实现这一点并将其转化为您的问题。

如果您不需要找到确切的最优值,您可以在遗传算法中监控几件事以改进其输出:

  • 使用足够大的人口规模并根据选择压力。你想避免遗传漂移的影响,仍然实现收敛。
  • 监控总体中的方差(多样性)。是不是下降的很快?如果您的总体中的所有解决方案基本相同,则该算法已经收敛。一旦它收敛,你就需要重新启动它,或者引入新的遗传信息来恢复进化过程。
  • 改变突变的强度。在搜索开始时翻转多个位,并在搜索结束时减少到仅翻转几个位。
  • 使用多个交叉点(我假设您使用的是单点交叉)。对于这么长的字符串,您可能想要使用 10 个交叉点。
于 2013-06-26T09:12:32.637 回答