代码之家 › 专栏 › 技术社区 › stefs

进化算法退化为模拟退火的问题:变异太小?

simulated-annealing evolutionary-algorithm

1

stefs · 技术社区 · 16 年前

假设我的初始人口(括号内为适合度)为:

A(7)、B(9)、C(14)、D(19)

AB(8.3)、AC(12.2)、AD(14.1)、BC(11)、BD(14.7)、CD(17)

在淘汰最弱者后,我们得到

下一回合,AB将在8点左右再次配对,将AC推出。下一轮,AB再次,将B推出(假设变异主要改变了>1个范围)。

现在,在仅仅几轮之后,人才库中就充满了最初最合适的候选人(a,B)和这两个候选人(AB)的突变。无论初始池的大小如何,都会发生这种情况,只是需要更长的时间。比如说,当初始种群为50时,它需要50圈,然后所有其他的都被消除,在更复杂的模拟退火中改变整个设置。一开始,我还让坎迪塔特人与自己交配,使问题恶化。

那么,我错过了什么?我的突变率是不是太小了?如果我增加它们,它会消失吗?

以下是我使用它的项目: http://stefan.schallerl.com/simuan-grid-grad/ 是的,代码有缺陷,界面很糟糕,但我现在懒得去修复它——小心,它可能会锁定你的浏览器。更好地使用chrome,即使firefox不会比chrome慢一次(也许图像比较的跟踪会有回报,耶!)。如果有人感兴趣, the code can be found here .

在这里,我放弃了ev alg的想法,转而使用模拟退火。

ps:我甚至不确定模拟退火——它就像进化算法一样,只是种群规模只有一个,对吗?

2 回复 | 直到 15 年前

1

3

Dan Dyer 16 年前

你所做的似乎是产生所有可能的后代,然后选择最合适的。这不仅效率低下(因为您生成的候选对象比您需要的多),而且会导致过早收敛。

相反,你应该产生足够的后代来代替下一代的人口。选择适当数量的候选者作为父母(偏爱更健康的个体),然后如果你保留后代并抛弃父母,你应该拥有与开始时相同数量的个体(美化) elitism 现在),这是你的下一代。重复此操作,直到满足终止条件。

上一段中的“偏好装配工个人”资格故意含糊不清。有许多不同的方法可以进行选择。看来你是在挑选最适合的人。这是截断选择。它只对某些类型的问题有效。因为你无情地挑选较弱的个体,这常常导致过早收敛。

roulette wheel selection

另一种常用的选择策略是 tournament selection . 你可能会对我写的这个文档感兴趣 different selection strategies and elitism .

2

1

Nick Larsen 16 年前

在进化算法中,你不一定要让你的种群中的每一个人与其他人杂交来产生更大的后代。有许多方法可以确定繁殖阶段的结果,但最基本的方法是将所有元素的适合度作为权重,为每个种群成员随机选择伴侣。这通常会导致下一代的成员数量与前一代相同,尽管某些交配方案最终会有更多成员(基于对当前问题的某种推理)并切掉最低值(同样适用于某种特定领域的推理)。对于大多数问题,您也会抛弃上一代。

此外,你的健康状况需要由繁殖的目标来决定,并且对于每一种情况来说,充分推导出合适的结果是非常具有挑战性的。