genetic-algorithm - 轮盘选择功能最小化

Question

这个问题回答了轮盘赌选择的伪代码。但这是为了最大化问题。但我的问题是最小化适应度函数的值。这意味着，适应度低的个体比适应度高的个体获得更高的被选中概率。我该如何实施？

提前致谢。

Answer 1

使用相同的算法，但使每个个体的比例 =maxfitness - fitness

Answer 2

将适应度更改为 Fitness_new = 1 / Fitness_old，您又遇到了最大化问题。如果 Fitness_old = 0 是可能的，则将分母加 1 以避免被零除。

Answer 3

import java.util.Random;
import java.util.Arrays;
import java.util.Comparator;

class MyComparator implements Comparator
{
    public int compare(Object o1, Object o2)
    {
        Number n1 = (Number) o1;
        Number n2 = (Number) o2;

        if(n1.jump > n2.jump)
        {
            return 1;
        }
        else if(n1.jump < n2.jump)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
}


class Number
{
    public double i;
    public int pos;
    public double jump = 0;


    public Random r = new Random();

    public Number(int pos)
    {
        this.pos = pos;

        i = r.nextInt();
    }
}


public class Temp
{
    public static  void main(String[] args)
    {
        Number[] n = new Number[50];

        double total = 0;

        for(int i=0; i<50; i++)
        {
            n[i] = new Number(i);

            total += n[i].i;
        }

        for(int i=0; i<50; i++)
        {
            n[i].jump = n[i].i/total;
        }


        Arrays.sort(n, new MyComparator());     

        for(int i=0; i<50; i++)
        {
            System.out.print(n[i].pos + ", ");
        }

        System.out.println();

        for(int i=0; i<50; i++)
        {
            n[i].jump = n[i].i / total;
            n[i].jump = 1-n[i].jump;
        }

        Arrays.sort(n, new MyComparator());     

        for(int i=0; i<50; i++)
        {
            System.out.print(n[i].pos + ", ");
        }

        System.out.println();   
    }
}

在上面的例子中，说Number类是你的个人类，i是适应度，jump是被选为父类的概率。首先，我们像以前一样计算被选为父母的概率。在这一步，适应度越高，概率越高。然后我们从 1 中减去概率。这使适应度较低的个体具有较高的适应度（为了选择而使用伪适应度）。现在重新计算概率。看，存在的顺序完全颠倒了。

Answer 4

由于缩放，轮盘不能用于最小化。此外，当适应度为负或为零时，也不能使用它，因为它们的概率为负或为零。

正如拉里建议的那样，您可以通过将每个个体的适应度减去人口的最大适应度来使用局部归一化，但是您必须再次确定最大适应度，使其不具有零概率。

我建议您使用已被证明比轮盘赌好数倍的锦标赛选择。

Answer 5

可能为时已晚，但我不推荐，max_fitness - fitness因为你会失去最糟糕的元素（它们可以帮助探索）。相反，您可以进行某种反转。

def roulette_selection(population):
    fs = [fitness(i) for i in population]
    sum_fs = sum(fs)
    max_fs = max(fs)
    min_fs = min(fs)
    p = random()*sum_fs
    t = max_fs + min_fs
    choosen = population[0]
    for i in population:
        if MAXIMIZATION:
            p -= fitness(i)
        elif MINIMIZATION:
            p -= (t - fitness(i))
        if p < 0:
            choosen = i
            break
    return choosen

Answer 6

反转概率顺序的简单方法：

假设原始概率列表[p1,p2,p3,...,pn]是针对人口中的个体的。

为了颠倒顺序，对于pi这个列表中的每个，我们得到new_pi = (1-pi) / (n-1).

解释：

由于0<=pi<=1， 的值(1-pi)使较小的概率得到较大的值。

由于(1-pi)for ifrom 1ton的总和n-1，除以(n-1)（归一化）后，我们确定0<=new_pi<=1.

代码示例：

def rouletteWheelSelect(population):
    fitnessSum = 0
    for individual in population:
        fitnessSum += individual.fitness
    for individual in population:
        individual.selectProb = individual.fitness / fitnessSum
    probSum = 0
    wheelProbList = []
    if MAXIMIZATION_PROBLEM:
        for individual in population:
            probSum += individual.selectProb
            wheelProbList.append(probSum)
    elif MINIMIZATION_PROBLEM:
        for individual in population:
            probSum += (1-individual.selectProb) / (POPULATION_SIZE-1)
            wheelProbList.append(probSum)
    r = random.random()  # 0<=r<1
    for i, p in enumerate(wheelProbList):
        if r < p:
            return population[i]
    return None