遗传算法:命名驱动突变位置的片段
要提出我的问题，请允许我从一个示例开始：
假设有1000个长度相同的数组(也称为行向量)。每个向量都填充了-1到1之间的随机数。然后，我随机抽取500个行向量，并将它们相加。我现在从总和开始，并希望对原始1000中的选择进行反向工程。
我决定用遗传算法来解决这个问题。我开始了一个1000位长的位串系列，并运行了变异(也就是翻转随机位)和交叉过程。然后，十分之一秒后，我就对了75%。然后，再过一个小时，我是76%正确的。从本质上讲，我一直在等待几十个比特被正确设置。这可能是我的随机数生成器从来没有以一种可以将它们合并到解决方案中的方式引入它们。
该算法在开始时做得很好，但后来未能进一步改进解决方案。我试着确保我的基因家族拥有每一个可能的比特位置。这并没有帮助；您无法判断项目从池中消失的速度有多快。
看来，算法中必须有一个额外的组成部分。一定有什么东西推动了翻转比特(也就是突变)位置的选择。这首曲子的专业术语是什么？梯度？它是从哪里来的？
回答 4
Stack Overflow用户
发布于 2013-06-26 17:12:33
所以本质上你有一个数字s，你想找到一个加起来为s的数字的子集，这被描述为subset sum problem，它是knapsack problem的一个特例。
我认为你关于遗传算法应用的解释是错误的。为了可视化必须考虑的可能解决方案的数量，从1000个项目的集合中选择500个项目，请阅读下面的数字"1000 / 500“的二项式系数
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320 (source)。
让我先澄清一下:遗传算法和相关方法是metaheuristics，的，这意味着它们不适合找到最优解，而是在非常短的时间内找到一个“好”的解。为了在NP困难的问题中找到最优解，你必须在最坏的情况下尝试每一种可能的组合。有一些精确优化的方法，可以智能地划分搜索空间，只评估较少的解决方案，但仍然需要数周时间才能得出最佳答案。
如果你需要找到这个确切的最优方法，我建议你寻找确切的方法，比如branch and bound。例如，您可以使用著名的CPLEX优化器将您的问题描述为一个整数程序。例如，看看ILP formulation of the TSP，看看如何实现这一点，并将其转化为您的问题。
如果你不需要找到精确的最优解，你可以在你的遗传算法中监控几件事来改善它的输出：
- 使用足够大的种群大小和相应的选择压力。你想要避免多样性的影响，仍然要实现多样性( convergence.
- Monitor genetic drift )在你的种群中。它是不是在迅速减少？如果你的种群中的所有解本质上都是相同的，那么算法已经收敛了。一旦它收敛了，你就需要重新启动它，或者引入新的遗传信息来恢复进化中的process.
- Vary突变的力量。在搜索开始时翻转多个比特，在搜索结束时只翻转几个比特。
- 使用多个交叉点(我假设您使用单点交叉)。对于这么长的字符串，你可能想使用10个交叉点。
Stack Overflow用户
发布于 2013-06-25 20:41:02
我想你指的是“收敛速度”或“收敛速度”。你的问题在文献中有很多解决方案。我建议减少每次迭代的突变率，直到你陷入局部最优(收敛速度变得太低，绝对或相对)，然后重置或增加突变率以避免局部最优。
另外，你会做什么样的选择？如果父母比孩子好，你会留住他们吗？你是选择最好的个体，还是做轮盘赌选择(这会保持次优解，并有机会获得更多熵)？
Stack Overflow用户
发布于 2013-06-25 21:02:23
这是一个相当透彻的教程，应该可以帮助你理解训练过程和所涉及的收敛。你说得对，它是一种梯度下降的形式。
http://informatics.indiana.edu/larryy/al4ai/lectures/03.IntroToGAs.pdf
该文档已移动，现在可以在以下位置找到：
http://shinyverse.org/al4ai/lectures/03.IntroToGAs.pdf
https://stackoverflow.com/questions/17297313
复制相似问题
腾讯云开发者
