Разведение родителей для нескольких детей в генетическом алгоритме

Question

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

Я строю несколько более простую структуру для этого урока планирования http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx#Chromosome8,, но у меня возникла проблема с разведением.

Я получил популяцию из 60 особей, и теперь я выбираю двух верхних особей для размножения, а затем выбираю несколько случайных других особей для размножения с первыми двумя, разве я не собираюсь в конечном итогедовольно небольшое количество родителей довольно быстро?

Я полагаю, что я не собираюсь добиваться значительных успехов в решении, если получу два лучших результата с каждым из следующих 20.

Это верно?Есть ли общепринятый метод для этого?

Answer 1

У меня есть образец генетических алгоритмов в Javascript здесь .

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

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

// save best guys as elite population and shove into temp array for the new generation
for(var e = 0; e < ELITE; e++) {
   tempGenerationHolder.push(fitnessScores[e].chromosome); 
}

// randomly select a mate (including elite) for all of the remaining ones
// using double-point crossover should suffice for this silly problem
// note: this should create INITIAL_POP_SIZE - ELITE new individualz
for(var s = 0; s < INITIAL_POP_SIZE - ELITE; s++) {
   // generate random number between 0 and INITIAL_POP_SIZE - ELITE - 1
   var randInd = Math.floor(Math.random()*(INITIAL_POP_SIZE - ELITE));

   // mate the individual at index s with indivudal at random index
   var child = mate(fitnessScores[s].chromosome, fitnessScores[randInd].chromosome);

   // push the result in the new generation holder
   tempGenerationHolder.push(child);
}

Этодовольно хорошо прокомментировано, но если вам нужны какие-либо дополнительные указатели, просто спросите (и здесь это репозиторий github, или вы можете просто сделать исходный вид по URL выше).Я использовал этот подход (элитарность) несколько раз, и для базовых сценариев он обычно работает хорошо.

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

Answer 2

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

Выбор других родителей полностью случайным образомбудет работать очень хорошо.Вам нужен механизм, с помощью которого более подходящие кандидаты выбираются чаще, чем более слабые.Есть несколько разных стратегий выбора, которые вы можете использовать, каждая из которых имеет свои плюсы и минусы.Некоторые из основных описаны здесь .Как правило, вы будете использовать выбор колеса рулетки или турнир.

Что касается объединения элитных персонажей с каждым из других родителей, то есть рецепт для уничтожения вариаций в популяции (а также для устранения ранее сохраненныхлучшие кандидаты).

Если вы используете элитарность, оставьте элитных индивидуумов без изменений (в этом смысл элитарности), а затем спаривайте пары других родителей (которые могут включать или не включать некоторые или все элитные индивидуумы,в зависимости от того, были ли они выбраны в качестве родителей стратегией отбора).Каждый родитель будет спариваться только один раз, если он не был выбран несколько раз стратегией выбора.

Answer 3

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

Я не могу вспомнить название статьи, чтобы подтвердить это, но есть математическое доказательство того, что выбор "ранжирования" сходится быстрее, чем "пропорциональный выборЕсли вы попытаетесь найти «стратегию выбора генетического алгоритма», вы можете кое-что найти в этом.один основанный на пропорции пригодности.Рассмотрим совокупность с 6 решениями и следующими значениями пригодности:

Solution   Fitness Value
A          5
B          4
C          3
D          2
E          1
F          1

При выборе рейтинга вы должны взять верхний k (скажем, 2 или 4) и использовать их в качестве родителей для следующего поколения.В пропорциональном ранжировании, чтобы сформировать каждого «ребенка», вы случайным образом выбираете родителя с вероятностью, основанной на значении пригодности:

Solution   Probability
A          5/16
B          4/16
C          3/16
D          2/16
E          1/16
F          1/16

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

Answer 4

Ваш подход может пострадать от преждевременной конвергенции . Хотя есть много других методов выбора. Выбор турнира .

Один из самых популярных, которые вы можете рассмотреть

Различные стратегии выбора обеспечивают различные уровни «давления выбора». Давление выбора - это то, насколько сильно стратегия настаивает на выборе лучших программ. Если абсолютные лучшие программы выбираются каждый раз, тогда ваш алгоритм фактически становится альпинистом холма ; он будет пойман в ловушку локального оптимума без возможности навигации к другим вершинам фитнес-ландшафта. На другом конце шкалы отсутствие физической нагрузки означает, что алгоритм будет слепо случайно наткнуться на ландшафт физической подготовки. Поэтому задача состоит в том, чтобы попытаться выбрать оператора с достаточным (но не чрезмерным) давлением выбора для решения проблемы, которую вы решаете.

Одним из преимуществ оператора выбора турнира является то, что, просто изменив размер турнира, вы можете легко настроить уровень давления выбора. Больший турнир даст больше давления, меньший - меньше.