进化算法退化为模拟退火的问题：突变太小？
我在理解进化算法时遇到问题。我多次尝试使用这种技术，但总是遇到同样的问题：退化为模拟退火。
假设我的初始种群（括号中的适应度）为：
A (7)、B (9)、C (14)、D (19)，
在交配和突变后我有以下孩子：
AB (8.3)、AC (12.2) ，AD（14.1），BC（11），BD（14.7），CD（17）
淘汰最弱后，下一回合得到
A，AB，B，AC
，AB再次交配，结果在8左右，推动AC出去。下一回合，再次AB，将B推出（假设突变改变的适应度主要在>1范围内）。
现在，仅经过几个回合，池中就填充了最初最适合的候选者（A，B）和这两个候选者的突变（AB）。无论初始池的大小如何，都会发生这种情况，只是需要更长的时间。比如说，初始群体为 50，需要 50 轮，然后所有其他人都被淘汰，将整个设置转变为更复杂的模拟退火。一开始我也让候选人与自己交配，这使问题变得更加严重。
那么，我想念什么？我的突变率是否太小了？如果我增加突变率，它会消失吗？
这是我使用它的项目： http://stefan.schallerl.com/simuan-grid-grad/ 是的，代码有问题，界面也很糟糕，但我现在懒得修复它 - 并且要小心，它可能会锁定你的浏览器。最好使用 chrome，即使 firefox 一次也不比 chrome 慢（可能图像比较的跟踪得到了回报，耶！）。如果有人感兴趣，可以在这里找到代码。
在这里我只是放弃了 ev-alg 的想法并进行了模拟退火。
PS：我什至不确定模拟退火 - 它就像进化算法，只是人口规模为一，对吧？
i have a problem understanding evolutionary algorithms. i tried using this technique several times, but i always ran into the same problem: degeneration into simulated annealing.
lets say my initial population, with fitness in brackets, is:
A (7), B (9), C (14), D (19)
after mating and mutation i have following children:
AB (8.3), AC (12.2), AD (14.1), BC(11), BD (14.7), CD (17)
after elimination of the weakest, we get
A, AB, B, AC
next turn, AB will mate again with a result around 8, pushing AC out. next turn, AB again, pushing B out (assuming mutation changes fitness mostly in the >1 range).
now, after only a few turns the pool is populated with the originally fittest candidates (A, B) and mutations of those two (AB). this happens regardless of the size of the initial pool, it just takes a bit longer. say, with an initial population of 50 it takes 50 turns, then all others are eliminated, turning the whole setup in a more complicated simulated annealing. in the beginning i also mated canditates with themselves, worsening the problem.
so, what do i miss? are my mutation rates simply too small and will it go away if i increase them?
here's the project i'm using it for:
http://stefan.schallerl.com/simuan-grid-grad/
yeah, the code is buggy and the interface sucks, but i'm too lazy to fix it right now - and be careful, it may lock up your browser. better use chrome, even thought firefox is not slower than chrome for once (probably the tracing for the image comparison pays off, yay!). if anyone is interested, the code can be found here.
here i just dropped the ev-alg idea and went for simulated annealing.
ps: i'm not even sure about simulated annealing - it is like evolutionary algorithms, just with a population size of one, right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你所做的似乎是产生所有可能的后代，然后选择最适合的。这不仅效率低下（因为您生成的候选数超出了您的需要），而且会导致过早收敛。
相反，你应该产生足够的后代来替代下一代的人口。选择适当数量的候选者作为父母（偏向更适合的个体），然后如果您保留后代并丢弃父母，您应该拥有与开始时相同数量的个体（掩盖精英主义 暂时） - 这是你的下一代。重复直到满足终止条件。
上一段中“偏向更适合的个人”的限定是故意含糊的。您可以通过多种不同的方式进行选择。看来你正在选择最适合的个体。这就是截断选择。它只对某些类型的问题真正有效。因为你无情地剔除较弱的个体，所以常常会导致过早的收敛。
理想情况下，您希望给较弱的个体一些生存机会，因为如果与正确的伴侣配对或以正确的方式突变，它可能会产生健康的后代。这就是为什么大多数选择策略都是概率性的。例如，轮盘赌选择为每个个体分配与其健身得分成比例的概率。因此，身体健康的个体会更容易生存，但体弱的个体仍然有一些很小的机会。
选择通常伴随着更替，因此同一代人可能会多次被选为父代。
另一种常用的选择策略是锦标赛选择。您可能对我编写的描述不同选择策略和精英主义的文档感兴趣。
What you appear to be doing is generating all possible offspring and then selecting the fittest. That is both inefficient (because you are generating more candidates than you need) and will lead to premature convergence.
Instead you should generate just enough offspring to replace the population for the next generation. Select the appropriate number of candidates to use as parents (favouring fitter individuals) and then if you keep the offspring and discard the parents you should have the same number of individuals that you started with (glossing over elitism for the moment) - this is your next generation. Repeat until your termination condition is met.
The "favouring fitter individuals" qualification in the previous paragraph is intentionally vague. There are many different ways that you can do selection. It seems that you are choosing the strictly fittest individuals. This is truncation selection. It's only really effective for certain types of problem. Because you are ruthlessly culling the weaker individuals it often leads to premature convergence.
Ideally you want to give a weaker individual some chance of surviving because it might potentially produce fit offspring if paired with the right partner or mutated in the right way. That's why most selection strategies are probabilistic. For example, roulette wheel selection assigns a probability to each individual that is proportionate to its fitness score. So fitter individuals will survive more often but weak individuals still have some small chance.
Selection is usually with replacement, so the same individual might get selected to be a parent more than once for a given generation.
Another commonly used selection strategy is tournament selection. You may be interested in this documentation I wrote describing different selection strategies and elitism.
在进化算法中，你不必将种群中的每个人与其他人杂交来产生更多的后代。确定繁殖阶段结果的方法有很多，但最基本的是采用所有元素的适应度，并将它们用作权重，为种群中的每个成员随机选择伴侣。这通常最终导致下一代拥有与前一代相同数量的成员，尽管某些交配方案最终会产生更多成员（基于对当前问题的某种推理）并砍掉最低值（同样是针对某种类型）领域特定推理）。你还因为大多数问题而抛弃了上一代产品。
此外，您的适应性需要根据繁殖目标来确定，并且针对每种情况充分推导可能非常具有挑战性。
In evolutionary algorithms, you don't necessarily cross everyone in your population with everyone else to produce a much larger set of offspring. There are many methods for determining the outcome of the breeding stage, but the most basic is to take the fitness of all elements, and use them as weights to randomly select partners for each member of the population. This usually ends up with the next generation having the same number of members as the previous population though some mating schemes end up with more (based on some kind of reasoning about the problem at hand) and chop off the lowest values (again for some kind of domain specific reasoning). You also throw out the previous generation for most problems.
Also, your fitness needs to be determined by the goal of reproduction, and can be very challenging to adequately derive for each scenario.