轮盘赌选择具有正负适应度值以实现最小化

Question

我正在做一个遗传算法，每个个体都会产生 3 个新的后代。使用适应度函数对新个体进行评估，该函数可能返回负值和正值。如果我想最小化，使用轮盘赌选择在后代之间进行选择的正确方法是什么？

适应度函数的一些可能值是：

fitness_offspring_1 = -98.74; fitness_offspring_2 = -10.1; fitness_offspring_3 = 100.31

我正在研究Python，但我只需要这个想法，这样我就可以自己实现它。

Answer 1

轮盘赌选择只是分配与个人适应度成正比的概率值。然后从该分布中随机选择。适合的人被选中的机会更大，而不太适合的人被选中的机会则较低。

您可以通过使用后代列表而不是个体来轻松地将其适应您的代码。

让我们从Python中简单的伪代码实现开始，您可以根据需要修改它：

fitness_sum = sum([ind.fitness for ind in individuals])
probability_offset = 0

for ind in individuals:
    ind.probability = probability_offset + (ind.fitness / fitness_sum)
    probability_offset += ind.probability

r = get_random_float()

selected_ind = individuals[0] # initialize
for ind in individuals:
    if ind.probability > r:
        break; 
    selected_ind = ind

现在，上面的代码（根据轮盘赌的性质）假设所有适应度值为正。因此，对于您的情况，我们需要将其标准化。您可以简单地将所有值除以最小后代的绝对值。但这会使其概率为 0，因此您可以简单地为所有人添加一个偏差，也给它一个微小的机会。

让我们看看它如何处理简单的值，比如 [1, 5, 14]

fitness_sum = 20
previous_probability = 0

# iterating first for loop:
individual[0].fitness => 0 + 1 / 20 = 0.05
individual[1].fitness => 0.05 + 5 / 20 = 0.3 
individual[2].fitness => 0.3 + 14 / 20 = 1

# We created the wheel of probability distributions, 
# 0 - 0.05 means we select individual 0
# 0.05 - 0.3 means we select individual 1 etc...

# say our random number r = 0.4

r = 0.4
selected_ind = individual_0

# iterating second for loop:
# 0.05 > 0.4 = false
selected_ind = individual_0
# 0.3 > 0.4 = false
selected_ind = individual_1
# 1.0 > 0.4 = true
break

我确信您可以在 python 中搜索更好的伪代码或实现。只是想给你一个想法。

Answer 2

这就是我在 JavaScript 中实现它的方式，为您提供一个总体思路：

    var totalFitness = 0;
    var minimalFitness = 0;

    for(var genome in this.population){
      var score = this.population[genome].score;
      minimalFitness = score < minimalFitness ? score : minimalFitness;
      totalFitness += score
    }

    minimalFitness = Math.abs(minimalFitness);
    totalFitness += minimalFitness * this.popsize;

    var random = Math.random() * totalFitness
    var value = 0;

    for(var genome in this.population){
      genome = this.population[genome];
      value += genome.score + minimalFitness;
      if(random < value) return genome;
    }

    // if all scores equal, return random genome
    return this.population[Math.floor(Math.random() * this.population.length)];

然而，正如 @umutto 所提到的，这使得具有“最低”分数的基因组“没有机会”被选择。所以你可以人为地为每个基因组添加一点适应性，这样即使是最低的个体也有机会。注意：我没有在上面的代码中实现 @umutto 提到的那个小偏差。 要使用轮盘选择进行最小化，您必须执行两个预处理步骤：

Answer 3

你必须去掉负的适应度值，因为适应度值将代表选择概率，它不能为负。最简单的方法是从所有适应度值中减去最低（负）值。最低适应度值现在为零。

为了最小化，您必须

恢复
1. 适应度值。这是通过将适应度值设置为
max Fitness
2. - fitness 来完成的。适应度最好的个体现在具有最高的适应度值。 转换后的适应度值现在被输入到正常
轮盘选择器中，该选择器选择具有最高适应度的个体。但本质上你正在做一个最小化。

Java GA，Jenetics，就是通过这种方式进行最小化的。

这是我用的。我认为“简单”的解决方案是将所有适应度调整到一个共同范围，例如[1.0 .. 10.0]。它管理多个独特的选择（请参阅

Cohort_Size

Answer 4

auto Selector::select_roulette(const Pool& pool, Set& indices) const -> void
{
    const auto& fitness = pool.fitness().scale(1, 10);
    const auto sum = fitness.sum();
    const auto num = fitness.enumerate();
    while (indices.size() <= Cohort_Size)
        for (auto p = uniform_real(sum); const auto && [i, pi] : num)
            if (p -= pi; p <= 0.0)
            {
                indices.insert(i);
                break;
            }
}