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

Question

Может ли кто-нибудь предоставить псевдокод для функции выбора рулетки? Как бы это реализовать:

Я не очень понимаю, как читать эту математическую запись. Я никогда не принимал никакой вероятности или статистики.

Answer 1

Хорошо, есть 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's fitness is 90%,
  # it's very likely that rand(100) is smaller than it.
  if rand(100) < probability
    return random_parent #=> random, likely fit, parent!
  else
    next #=> or let's 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 - описывает алгоритм стохастического принятия .

Answer 2

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's 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;
        }

Answer 3

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

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

    }