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

Question

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

适应度函数的一些可能值是：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 提到的，这使得具有最低分数的基因组 没有机会 被选中。所以你可以人为地为每个基因组增加一点适应性，这样即使是最低级的 invidivudla 也有机会。注意：我没有在@umutto 提到的上述代码中实现那个小偏差。

Answer 3

为了使用轮盘选择进行最小化，你必须做两个预处理步骤：

你必须去掉负的适应度值，因为适应度值将代表选择概率，不能为负。最简单的方法是从所有适应度值中减去最低（负）值。最低适应度值现在为零。
为了最小化，您必须还原适应度值。这是通过将适应度值设置为 max fitness - fitness 来完成的。具有最佳适应度的个体现在具有最高的适应度值。

转换后的适应度值现在被输入正常轮盘选择器，选择具有最高适应度的个体。但本质上你是在做一个最小化。

Java GA，Jenetics，正在以这种方式进行最小化。

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

Roulette wheel selection with positive and negative fitness values for minimization

python

genetic-algorithm

roulette-wheel-selection