如何比我的轮盘赌选择方法更好地评估更好的后代？

Question

我正在研究遗传编程算法，我想知道如何通过替代或改进我选择的繁殖方式来确定并确保我最好的范例繁殖得更多。目前我使用的方法是这样的：

function roulette(population)
    local slice = sum_of_fitnesses(population) * math.random()
    local sum = 0
    for iter = 1, #population do
        sum = sum + population[iter].fitness
        if sum >= slice then
            return population[iter]
        end
    end
end

但我无法让我的种群达到高于某个值的平均适应度，我担心这是因为适应度较低的成员与适应度较高的成员一起繁殖，从而继续传播它们的弱基因。

那么如何改进我的轮盘选择方法呢？或者我应该使用完全不同的适合度比例选择器？

Answer 1

这里有几个问题。

您正在根据个体的适应度选择个体复制的概率，因此您使用的适应度函数需要夸大微小的差异，否则适应度略有下降并不是那么糟糕。例如，如果适应度从 81 下降到 80，这种变化可能在系统的噪音范围内，不会对进化产生太大影响。如果需要进行一系列小的改变，肯定几乎不可能攀升到非常高的适应度，因为 select 压力根本不够大。

解决这个问题的方法是使用锦标赛 selection 之类的东西。在最简单的形式中，每次你想选择另一个人出生时，你会随机选择 K 个人（K 是已知的并且 "tournament size"）。您计算每个人的适应度，并复制具有最高适应度的人。适应度差异是 81 对 80 还是 10000 对 2 并不重要，因为它只需要最高的适应度。

现在的问题是：你应该把K设置成什么？ K可以被认为是select离子的强度。如果你将它设置得较低（例如，K=2），那么许多低适应度的人会幸运地溜走，与其他低适应度的人竞争。你会得到很多多样性，但部分很少。另一方面，如果您将 K 设置得较高（例如，K=100），您总是会选择种群中适应度最高的一个，确保种群平均值接近最大值，但同时降低人口多样性。

这里的特定权衡取决于具体问题。我建议尝试不同的选项（包括您的原始算法）和几个不同的问题，看看会发生什么。例如，尝试全一问题：潜在的解决方案是位串，而适应度只是 1 的个数。如果您的 selection 较弱（如在您的原始示例中，或 K=2），您会发现它永远不会完全达到完美的全一解决方案。

那么，为什么不总是使用高 K 呢？考虑一个问题，除非它们出现在连续四个（或八个，或更多）的块中，否则它们突然变得非常积极。这样的问题是"deceptive"，这意味着你需要探索看起来很糟糕的解决方案才能找到好的解决方案。如果你将 selection 的强度设置得太高，你将永远不会为最后的突变收集三个，给你第四个。

存在许多使用锦标赛 selection 的更高级技术，您可能想看看。例如，随着时间的推移，甚至在人口中改变 K，select 一些人使用低 K 而其他人使用高 K。如果您打算构建更好的算法，那么值得多读一些。

如何比我的轮盘赌选择方法更好地评估更好的后代？

How to valorize better offsprings better than with my roulette selection method?

genetic-algorithm

evolutionary-algorithm