Roulette wheel selection for function minimization

Question

This question answers pseudocode for roulette wheel selection. But it's for maximization problem. But my problem is to minimize the value of fitness function. That means, individuals with low fitness get higher probability for being selected than individual with high fitness. How can I implement that?

Thanks in advance.

Duramen

Answer 1

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();   
    }
}

In above example, say Number class is your individual class, i is fitness, jump is the probability of being selected as parent. At first we compute the probability of being selected as parent like before. At this step, higher fitness will get higher probability. Then we subtract probability from 1. This gives lower fitness individual higher fitness (pseudo fitness for selection's sake). Now recalculate the probability. See, the order of being is totally reversed.

Levis

Answer 2

Use the same algorithm but make the proportion of each individual = maxfitness - fitness

Bort

For real life problem, it's quite unlikely to know MAX_FITNESS as like as MIN_FITNESS. – Levis

I shouldn't have used constant-indicating caps. maxFitness for your roulette wheel is the maximum fitness of the current generation, since the size of the roulette wheel / lottery is the sum of current generation fitnesses. – Bort

Answer 3

Change the fitness to fitness_new = 1 / fitness_old and you have maximization problem again. If fitness_old = 0 is possible, add 1 to the denominator to avoid division by zero.

Ezraezri

Answer 4

Roulette wheel cannot be used for minimization because of the scaling. Furthermore, it also cannot be used when there are negative or null fitnesses because their probability would be negative or null.

As suggested by Larry you can use local normalization by subtracting, to the maximal fitness of your population, the fitness of each individual, but again you will have to fix the maximal fitness so that it has not a null probability.

I suggest you to use a tournament selection that has been proved multiple times better than roulette.

Pedestrian

Answer 5

Simple Way to Reverse the Probability Order:

Say a original probability list [p1,p2,p3,...,pn] is for individuals in population.

To reverse the order, for each pi in this list, we get new_pi = (1-pi) / (n-1).

Explanation:

Since 0<=pi<=1, the value of (1-pi) makes a smaller probability get a larger value.

Since the sum of (1-pi) for i from 1 to n become n-1, after dividing by (n-1) (normalization), we make sure 0<=new_pi<=1.

Code Sample:

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

Lungfish

Answer 6

May be its too late but, I don't recommend the max_fitness - fitness since you will loose the worst elements (they can help for exploration). Instead you can do a sort of an inversion.

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

Cataclinal