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

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

要使用轮盘选择进行最小化，您必须执行两个预处理步骤：

1. 您必须摆脱负适应值，因为适应值将代表选择概率，不能为负。最简单的方法是从所有适应度值中减去最低（负）值。最低适应度值现在为零。
2. 为了最小化，您必须恢复适应度值。这是通过将适应度值设置为最大适应度来完成的。具有最佳适应度的个体现在具有最高的适应度值。

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

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

Answer 3

这就是我在 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 代码中实现那个小偏差。