Выбор рулетки в генетических алгоритмах

Ответ 1

Прошло несколько лет с тех пор, как я сделал это сам, однако следующий псевдокод был легко найден в google.

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
    do this twice
        number = Random between 0 and 1
        for all members of population
            if number > probability but less than next probability 
                then you have been selected
        end for
    end
    create offspring
end loop

Сайт, на котором это произошло, можно найти здесь, если вам нужна дополнительная информация.

Ответ 2

Множество правильных решений уже, но я думаю, что этот код более ясный.

def select(fs):
    p = random.uniform(0, sum(fs))
    for i, f in enumerate(fs):
        if p <= 0:
            break
        p -= f
    return i

Кроме того, если вы накапливаете fs, вы можете создать более эффективное решение.

cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]

def select(cfs):
    return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))

Это быстрее и чрезвычайно сжатый код. STL в С++ имеет аналогичный алгоритм бисекции, доступный, если этот язык используется.

Ответ 3

В опубликованном псевдокоде содержатся некоторые нечеткие элементы, и это добавляет сложность генерации потомства вместо выполнения чистого отбора. Вот простая реализация python этого псевдокода:

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <http://stackoverflow.com/questions/177271/roulette
        -selection-in-genetic-algorithms/177278#177278>
    """
    total_fitness = float(sum(fitnesses))
    rel_fitness = [f/total_fitness for f in fitnesses]
    # Generate probability intervals for each individual
    probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
    # Draw new population
    new_population = []
    for n in xrange(num):
        r = rand()
        for (i, individual) in enumerate(population):
            if r <= probs[i]:
                new_population.append(individual)
                break
    return new_population

Ответ 4

Это называется выбором колеса рулетки с помощью стохастического приема:

/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.

unsigned rw_selection(double f_max)
{
  for (;;)
  {
    // Select randomly one of the individuals
    unsigned i(random_individual());

    // The selection is accepted with probability fitness(i) / f_max
    if (uniform_random_01() < fitness(i) / f_max)
      return i;
  }   
}

Среднее количество попыток, необходимых для одного выбора:

& тау; = f _max/avg (f)

• f _max - максимальная пригодность населения
• avg (f) - средняя пригодность

& тау; не зависит явно от числа индивидуумов в популяции (N), но отношение может изменяться с N.

Однако во многих приложениях (где фитнес остается ограниченным, а средняя пригодность не уменьшается до 0 при увеличении N) & tau; не увеличивается неограниченно с N и, следовательно, типичная сложность этого алгоритма - O (1) (выбор колесика рулетки с использованием алгоритмов поиска имеет сложность O (N) или O (log N)).

Распределение вероятности этой процедуры действительно такое же, как в классическом выборе колеса рулетки.

Подробнее см.:

• Выбор рулетки с помощью стохастического приема (Adam Liposki, Dorota Lipowska - 2011)

Ответ 5

Вот код в C:

// Find the sum of fitnesses. The function fitness(i) should 
//return the fitness value   for member i**

float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
    sumFitness += fitness(i);

// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;

// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;

while (randomNumber > partialSum)
{
   partialSum += fitness(memberID);
   memberID++;
} 

**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**

Ответ 6

Из приведенного выше ответа я получил следующее, что было яснее для меня, чем сам ответ.

Чтобы привести пример:

Случайный (сумма):: Случайный (12) Итерируя через популяцию, мы проверяем следующее: random < сумма

Выберем 7 как случайное число.

Index   |   Fitness |   Sum |   7 < Sum
0       |   2   |   2       |   false
1       |   3   |   5       |   false
2       |   1   |   6       |   false
3       |   4   |   10      |   true
4       |   2   |   12      |   ...

В этом примере наиболее подходящий (индекс 3) имеет самый высокий процент выбора (33%); так как случайное число должно располагаться в пределах 6- > 10, и оно будет выбрано.

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }

Ответ 7

Prof. Thrun из лаборатории Stanford AI также представил быстрый (er?) Код повторной выборки на python во время его CS373 Udacity. Результат поиска Google привел к следующей ссылке:

http://www.udacity-forums.com/cs373/questions/20194/fast-resampling-algorithm

Надеюсь, что это поможет

Ответ 8

Здесь компактная реализация java, которую я недавно написал для выбора рулетки, надеюсь, что она будет использоваться.

public static gene rouletteSelection()
{
    float totalScore = 0;
    float runningScore = 0;
    for (gene g : genes)
    {
        totalScore += g.score;
    }

    float rnd = (float) (Math.random() * totalScore);

    for (gene g : genes)
    {   
        if (    rnd>=runningScore &&
                rnd<=runningScore+g.score)
        {
            return g;
        }
        runningScore+=g.score;
    }

    return null;
}

Ответ 9

Выбор колеса рулетки в MatLab:

TotalFitness=sum(Fitness);
    ProbSelection=zeros(PopLength,1);
    CumProb=zeros(PopLength,1);

    for i=1:PopLength
        ProbSelection(i)=Fitness(i)/TotalFitness;
        if i==1
            CumProb(i)=ProbSelection(i);
        else
            CumProb(i)=CumProb(i-1)+ProbSelection(i);
        end
    end

    SelectInd=rand(PopLength,1);

    for i=1:PopLength
        flag=0;
        for j=1:PopLength
            if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
                SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
                flag=1;
                break;
            end
        end
        if(flag==0)
            SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
        end
    end

Ответ 10

Based on my research ,Here is another implementation in C# if there is a need for it:


//those with higher fitness get selected wit a large probability 
//return-->individuals with highest fitness
        private int RouletteSelection()
        {
            double randomFitness = m_random.NextDouble() * m_totalFitness;
            int idx = -1;
            int mid;
            int first = 0;
            int last = m_populationSize -1;
            mid = (last - first)/2;

            //  ArrayList BinarySearch is for exact values only
            //  so do this by hand.
            while (idx == -1 && first <= last)
            {
                if (randomFitness < (double)m_fitnessTable[mid])
                {
                    last = mid;
                }
                else if (randomFitness > (double)m_fitnessTable[mid])
                {
                    first = mid;
                }
                mid = (first + last)/2;
                //  lies between i and i+1
                if ((last - first) == 1)
                    idx = last;
            }
            return idx;
        }

Ответ 11

Хорошо, поэтому есть 2 метода для выбора выбора рулетки > : Обычная и Стохастическая приемка.

Обычный алгоритм:

# there will be some amount of repeating organisms here.
mating_pool = []

all_organisms_in_population.each do |organism|
  organism.fitness.times { mating_pool.push(organism) }
end

# [very_fit_organism, very_fit_organism, very_fit_organism, not_so_fit_organism]
return mating_pool.sample #=> random, likely fit, parent!

Метод стохастической приемки:

max_fitness_in_population = all_organisms_in_population.sort_by(:fitness)[0]
loop do
  random_parent = all_organisms_in_population.sample
  probability = random_parent.fitness/max_fitness_in_population * 100
  # if random_parent fitness is 90%,
  # it very likely that rand(100) is smaller than it.
  if rand(100) < probability
    return random_parent #=> random, likely fit, parent!
  else
    next #=> or let keep on searching for one.
  end
end

Вы можете выбрать либо, они будут возвращать одинаковые результаты.

Полезные ресурсы:

http://natureofcode.com/book/chapter-9-the-evolution-of-code - удобная для начинающих и четкая глава по генетическим алгоритмам. объясняет выбор колесика рулетки как ведро с деревянными буквами (чем больше вы вставляете - великий шанс выбрать алгоритм A, Обычный).

https://en.wikipedia.org/wiki/Fitness_proportionate_selection - описывает алгоритм Стохастический прием.

Ответ 12

Это расширение массива Swift 4 реализует взвешенный случайный выбор, a.k.a выбор рулетки из его элементов:

public extension Array where Element == Double {

    /// Consider the elements as weight values and return a weighted random selection by index.
    /// a.k.a Roulette wheel selection.
    func weightedRandomIndex() -> Int {
        var selected: Int = 0
        var total: Double = self[0]

        for i in 1..<self.count { // start at 1
            total += self[i]
            if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
        }

        return selected
    }
}

Например, учитывая массив из двух элементов:

[0.9, 0.1]

weightedRandomIndex() вернет ноль 90% времени и один 10% времени.

Вот более полный тест:

let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
    let index = weights.weightedRandomIndex()
    results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
    print(weights[key], Double(val)/Double(n))
}

выход:

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

Этот ответ в основном совпадает с ответом Эндрю Мао:fooobar.com/questions/113325/...

Ответ 13

Я написал версию на С# и действительно ищу подтверждение, что она действительно правильная:

(roulette_selector - это случайное число, которое будет находиться в диапазоне от 0.0 до 1.0)

private Individual Select_Roulette(double sum_fitness)
    {
        Individual ret = new Individual();
        bool loop = true;

        while (loop)
        {
            //this will give us a double within the range 0.0 to total fitness
            double slice = roulette_selector.NextDouble() * sum_fitness;

            double curFitness = 0.0;

            foreach (Individual ind in _generation)
            {
                curFitness += ind.Fitness;
                if (curFitness >= slice)
                {
                    loop = false;
                    ret = ind;
                    break;
                }
            }
        }
        return ret;

    }