用轮盘赌选择法进行函数最小化

Question

这个问题回答了轮盘赌选择的伪代码。但是它是针对最大化问题的。我的问题是最小化适应度函数的值。也就是说，适应度较低的个体被选中的概率比适应度较高的个体更高。我该如何实现这一点？

提前感谢。

- Masud Hasan

Answer 1

使用相同的算法，但是让每个个体的比例等于 maxfitness - fitness。

- Larry OBrien

---

对于现实生活中的问题，很难像MIN_FITNESS一样知道MAX_FITNESS。 - user

我不该使用常量表示的大写字母。对于你的轮盘赌选择，maxFitness 是当前一代中最大适应度，因为轮盘赌/抽奖的大小是当前一代适应度的总和。 - Larry OBrien

Answer 2

将适应度改为适应度_new = 1 / 适应度_old，您再次拥有了最大化问题。如果可能的话，若适应度_old = 0，则在分母中加1以避免除以零。

- CGFoX

Answer 3

轮盘赌不能用于最小化，因为它的比例尺度。此外，当存在负值或空白适应度时，它也无法使用，因为它们的概率会变成负数或零。

正如Larry所建议的那样，您可以通过减去每个个体的适应度与种群最大适应度之间的差来使用本地归一化，但是您还必须修正最大适应度，以使其没有零概率。

我建议您使用锦标赛选择，这已经被证明比轮盘赌更好了多次。

- mitch

Answer 4

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中减去概率。这给较低适应度的个体提供了更高的适应度（为了选择而伪造的适应度）。现在重新计算概率。注意，排名完全颠倒了。

- user

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

- Josue Ttito

Answer 6

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

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

为了逆转顺序，对于列表中的每个pi，我们得到new_pi = (1-pi) / (n-1)。

解释：

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

由于i从1到n的(1-pi)之和变为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

- Instein