遗传算法选择和交叉
我一直在为我的 ai 课程中的一个项目进行遗传算法的一些研究，但我对传统算法似乎有点困惑。
基本上，我想知道为什么他们使用不同的选择（如轮盘赌轮）来选择父母进行繁殖。为什么不选择健康得分最好的父母并结束呢？
交叉也让我感到困惑。每次随机选择点来拼接父信息。但根据之前的信息来改变交叉似乎更有意义。如果已知染色体串在一定程度上是良好的，则交叉仍然可以是随机的，但不在串中良好部分的范围内。
有什么想法吗？
I have been doing some research on genetic algorithms for a project in my ai class but I am a little confused as to what seems to be the traditional algorithm.
Basically, I wonder why they use different selections like roulette wheel to choose parents to reproduce. Why not choose the parents with the best fitness score and call it a day?
Also crossover confuses me as well. It randomly choose points every time to splice parent information. But it would seem to make more sense for crossovers to change based on previous info. If a chromosome string is known to good up to a point, the crossover could still be random but not in the range of the good part in the string.
Any thoughts?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
选择
如果你只选择最好的父母，你得到的就是爬山。爬山效果很好，但问题越困难，一般来说，你就越有可能陷入无法取得进一步进展的境地。
一般来说，问题越难，这样的局部最优就越多。除了最好的个体之外，选择其他个体可以保持群体的多样性：解决方案在搜索空间中进一步分散，如果群体的一部分陷入局部最优，则不同的个体会产生不同的结果。部分人口仍然可以取得进步。
现代遗传算法通常会投入大量精力来维持群体的多样性，以防止过早收敛。一种技术是健身共享。另一种简单的方法是将种群划分为不同的物种，这样不同物种的个体就不能（或很少能）彼此繁殖。
交叉
交叉试图将基因组的良好部分分配给因突变而产生的个体。如果人们能够交换基因组中好的部分，那就太好了，而且这已经被尝试过了；例如，您可以查看每个基因并测量拥有该基因的个体的平均适应性。
但这有两个主要问题：
计算成本很高。
基因组中可能存在相互依赖性。也许根据你的指标，基因 A 看起来确实很好，但基因 B 却不然，所以你把它排除在外。但实际上，如果没有基因 B 存在，基因 A 可能实际上不起作用。
Selection
If you only ever choose the best parent, what you get is Hill climbing. Hill climbing works nicely, but the more difficult the problem, generally, the more likely you are going to get stuck in a position you can make no further progress from.
Generally, the harder the problem, the more such local optima there are. Selecting other individuals in addition to the best ones maintains the diversity of the population: the solutions are spread further out in the search space, and if a part of the population is stuck in a local optimum, a different part of the population can still make progress.
Modern genetic algorithms usually devote a lot of effort to maintaining the diversity of the population to prevent premature convergence. One technique for that is fitness sharing. Another simple way to do this, is to divide the population into different species, so that individuals of different species can't (or only rarely can) reproduce with each other.
Crossover
Crossover tries to distribute good parts of the genome among individuals that have arisen due to mutation. It would indeed be nice if one could just swap the good parts of the genome, and this has been attempted; for example, you can look at each gene and measure the average fitness of individuals possessing that gene.
There are a two main problems with this though:
It is computationally expensive.
There might be interdependencies in the genome. Maybe gene A looks really good according to your metric, but gene B doesn't, so you leave it out. In reality though, it might be that gene A doesn't actually work without gene B being present.
只选择两个父母就到此为止，太快就能找到解决方案。您希望同时调整许多不同的变量。想象一个双变量场景，您使用遗传算法找到房间中的最低点。您的方法可能会很快找到一个局部波谷的最低点，但如果飞机有很多起伏，您可能会找不到最低点的波谷。
Picking only two parents and calling it a day converges to a solution too quickly. You are looking to adjust many different variables simultaneously. Imagine a two-variable scenario in which you use a genetic algorithm to find the lowest point in a room. Your approach might quickly find the lowest spot in one local trough, but if the plane has many undulations you risk not finding the trough with the lowest point.
没有选择最好的=>因为否则你很可能会陷入局部最优。出于类似的原因，轮盘赌选择已经成为过去，酷孩子使用基于排名的选择（根据适应性对后代进行排序并保留，比如最好的 1/10，检查“进化策略”）。如果健身规模不是很规则，则轮盘赌选择（又名健身比例选择）效果不佳，并且在实践中它从来都不是规则的。
交叉=>进化策略只使用变异，没有交叉就完全没问题。交叉假设你的目标函数可以被整齐地分解为几个位，交叉会发现。在大多数基因型中，基因型的各个部分以高度非线性的方式相关。仅在玩具问题上这是非常天真的和真实的。如果你没有充分的理由使用交叉算子，那就不用它，奥卡姆剃刀等等。
Not selecting the best => because else you very likely to get stuck on a local optima. For similar reason, roulette selection is a thing from the past and cool kids use rank based selection (sorting the offsprings per fitness and keeping, say 1/10 of the best, check "evolution strategies"). Roulette selection, aka fitness proportional selection, does not work well if the fitness scale is not very regular, and in practice it's never regular.
Crossover => Evolution strategies just use mutation and are totally fine without crossover. Crossover assume that your objective function can be neatly decomposed in several bits, that the crossover will find. In most genotype, various parts of the genotype are related in a highly non-linear way. It's very naive and true only on toy problems. If you have no serious justification to use a crossover operator, just do without it, Occam razor and all.
我认为 DataWraith 很好地回答了这个问题。关于交叉，我只想补充一点，John Holland 认为 GA 的工作原理是使用随机交叉和选择隐式计算每个染色体子串（“模式”）的适应度，而不是显式计算它，这将非常耗时（正如 DataWraith 所说）。 Holland 将这个过程称为“隐式并行性”。
-特德
I think DataWraith answered the question quite well. Concerning crossover, I'll just add that John Holland argues that the GA works by implicitly calculating the fitness of each chromosome substring ("schema") using randomized crossover and selection, instead of calculating it explicitly, which would be extremely time-consuming (as DataWraith said). Holland calls this process "implicit parallelism".
-Ted
交叉后更换物种怎么样？
我用轮盘赌选择法来选择繁殖物种。我的交叉率为 0.7 (70%)，但我实际上不知道这意味着什么。这是否意味着我选择 70 对父母，将它们交叉并用新的两对替换池中最差的两对？或者这意味着我选择 70/2 = 35 对父母，将它们交叉并用最差的父母代替？
真不知道你用什么物种来代替新孩子？如果孩子们的体能比泳池中最差的两个人的体能更差怎么办？请解释一下轮盘赌比例选择法的替换过程。
What about replacing species after crossover?
I choose species for reproduction with roulette wheel selection method. My crossover rate is 0.7 (70%), but I actually don't know what that means. Does it means that i choose 70 pairs of parents, crossover them and replace the worst two in pool with new twos? Or it means I choose 70/2 = 35 pairs of parents, crossover them and replace them with the worst ones?
I really don't know with what species you replace new children? What if fitness of children is worst than fitness of worst two in pool? Please explain replacing process in proportional selection method with roulette wheel.