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

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

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 ответа

Решение

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

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

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

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

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

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

Источник

Ключ находится в

probability = sum of probabilities + (fitness / sum)

а также

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

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

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

Источник
Другие вопросы по тегам