遗传算法-子集和问题

Question

我要做一个用遗传算法解决子集和问题的项目。不幸的是，在对算法进行编码时我发现了一个大问题.

我的算法：

只要没有找到解，步骤的次数比步骤做的要小: chromosome

• perform选择(roulette)

• select n染色体的概率和分布函数由

• 计算为crossed

• perform，交叉点是选择randomly)

• select m染色体到mutation

• perform突变

• ，如果找到解决方案，则停止

。

(算法取自“遗传算法+数据结构=进化程序，第2章")变量，如人口规模、数据量、数据收集范围、步骤数、突变次数(步骤)、交叉次数(一步)在程序选项中严格设置。

问题是，在种群中经过一定(相对较小的)步数之后，所有的染色体都是相同的。这个问题说明了这个图：http://imageshack.us/m/96/7693/wykresb.png

我做错什么了？怎么修呢？提前谢谢。

编辑：

在这里您可以从我的应用程序：http://paste.pocoo.org/show/391318/找到日志

我认为轮盘赌不是最好的解决办法(正如迪翁所说)。突变也需要改善。

Answer 1

我以前也有过类似的问题，我希望它和你的一样

首先，你需要检查A染色体是否比B染色体好(使用任何测量指标)，这样你就可以对种群的染色体进行严格的排序，并且能够对种群进行排序。

然后，当你产生一个新的染色体(无论是变异还是交叉)，你可能会产生一个已经存在于你的群体中的染色体。请确保不要将此包括在人口列表中。

换句话说，确保您的列表总是包含不同的染色体，并且总是从最好到最坏的排序！

注意:我使用的遗传算法通常如下(这是最通用的算法，也是最常用的)：

worst-fit)

• select
• 创建P不同的染色体，并将它们添加到Pop列表中；
  1. (未找到最优解&& all；LIM)
  2. 使用交叉、变异或任何其他方法创建新的染色体；
  3. 将所创建的染色体添加到列表Pop
  4. 排序列表Pop(从最适合于Pop的第一P不同染色体进行排序，并丢弃所有来自Pop的其他染色体)。while

• end

​

Answer 2

这是(潜在的)问题。免责声明当然是你可能只是一个错误的程序。

轮盘赌轮的选择太糟糕了。问题是，在运行初期，适应度值的分布是随机的。您有一些糟糕的解决方案和一些合理的，可以比较。你不会期望他们中的任何一个人非常优秀，但你会希望他们中的一些人比其他人好得多。

轮盘赌轮的选择利用这些可能性的相对差异，并放大它们。如果你的人口规模是100人，而一个人的健康水平是其他人的5倍，那么它就会被选中5倍。在典型的轻微突变率下，你很快就会选择同一个个体进行两次重组，产生一些新的完全相同的后代，做出非常小的改变(也许)，然后将它们重新放入种群中。因为你还处于早期阶段，大多数解决方案仍然是糟糕的，所以当你有一个高于平均水平的解决方案时，你选择它为五个高于平均水平的解决方案，培育它们得到10个高于平均水平的解决方案，然后重新开始这个过程。如果你不仔细地设计你的一组操作符，这些解决方案可以很快地占据整个群体，尽管算法只知道它们比它所看到的糟糕的解决方案更好。

解决方案是使用更好的选择运算符。二进制锦标赛的选择更快，更容易编码，并施加了一个更可容忍的选择压力。也有排名偏倚的选择，按比例选择适合度排名，而不是绝对差异。

编辑：这并不是说你不能使用比例选择。仅仅因为它非常容易过早收敛并有效地使用它，您通常必须考虑到这一点构建一组完整的操作符。

Answer 3

在应用遗传算法时，可能会出现算法陷入局部最优的情况。然而，人们对全局最优(或者更确切地说是对这种最优的近似)感兴趣。

可以通过以下方式避免局部最佳情况：

• A较高的突变率
• 不同的交叉功能

此外，它可能是有用的杀死克隆。这意味着您在每次迭代之后“快速”查看您的种群，并且不允许克隆。我的意思是，你只需要寻找近似的克隆，因为检查精确的克隆需要O(m*n^2)，其中n是你的种群大小，m是染色体的大小。这种方法帮助我解决了另一个问题，我也面临着克隆人。

希望这能帮上忙，克里斯蒂安

编辑

如果您能够发布您的交叉功能，也将是很好的。最好不是作为代码，而是用纯英语文本。交叉函数是遗传算法的关键部分.