Генетический алгоритм выбора колеса рулетки - PullRequest
Новая
       52

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

3 голосов
/ 26 ноября 2011

У меня проблемы с пониманием алгоритма.Вот самая популярная из увиденных в Интернете 

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


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

^^^ эта часть, в частности, меня смущает.Что такое «сумма вероятностей» и даже «вероятность» в контексте индивида в популяции?Это одинаковые ценности, которые люди имеют в начале?

Ответы [ 2 ]

1 голос
/ 16 декабря 2011

Это очень запутанный кусок кода.

Во втором блоке кода probability - это переменная, прикрепленная к каждому члену совокупности, а sum of probabilities - глобальная переменная для всей совокупности.

Теперь, что говорит метафора колеса рулетки, так это то, что все население может быть представлено как колесо рулетки, и у каждого члена населения есть срез в этом колесе рулетки, пропорциональный его относительной пригодности. Этот код выполняет грязную работу за этой метафорой - вместо клиньев на колесе элементы теперь представлены пропорциональными интервалами на отрезке [0,1], что является обычным способом представления вероятностей.

Чтобы сделать это, вам технически нужны два числа, начало и конец, для каждого участника. Но старт первого участника будет 0; начало второго члена будет концом первого члена; и т. д., до последнего члена, который имеет конец 1.

Вот что делает этот код. Sum of probabilities начинается с 0, и в первый раз в цикле probability - это то, что вы интуитивно думали, что это будет. Это маркировка конечной точки первого члена. Затем «сумма вероятностей» обновляется. Во второй раз в цикле «вероятность» - это то, что вы интуитивно думали, что она будет… сдвинута «суммой вероятностей». И так далее.

Итак, первый цикл суммирует пригодные значения как прелюдию к нормализации вещей. Второй цикл, о котором вы спрашиваете, - это нормализация и упорядочение этих нормализованных вероятностей в единичном интервале. И третий (самый сложный) цикл - это выбор двух случайных чисел, сопоставление их с двумя членами населения и их спаривание. (Обратите внимание, что предполагается, что эти члены имеют некоторый массивоподобный формат, так что вы можете последовательно проверять их конечные точки по случайному числу, которое вы свернули.)

1 голос
/ 26 ноября 2011

Ключ в 

probability = sum of probabilities + (fitness / sum)

и 

if number > probability but less than next probability 
         then you have been selected

Probability - это измерение возможности индивидуума создать потомство; размер его среза на колесе рулетки. sum of probabilities - это общий размер колеса рулетки. probability каждого человека является функцией его пригодности.

Я нашел эту ссылку полезной при попытке понять алгоритм.

...