проблема эволюционных алгоритмов, переходящих в искусственный отжиг: слишком мала мутация?

Question

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

Допустим, мое начальное население с пригодностью в скобках:

A (7), B (9), C (14), D (19)

после спаривания и мутации у меня есть следующие дети:

AB (8,3), AC (12,2), AD (14,1), BC (11), BD (14,7), CD (17)

после устранения самого слабого мы получаем

A, AB, B, AC

в следующем ходу, AB снова спаривается с результатом около 8, выталкивая AC. В следующем повороте AB снова выталкивает B (при условии, что мутация меняет приспособленность в основном в диапазоне> 1).

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

Итак, что я скучаю? мои мутации просто слишком малы и они исчезнут, если я увеличу их?

вот проект, который я использую для: http://stefan.schallerl.com/simuan-grid-grad/ да, код содержит ошибки и интерфейс отстой, но я слишком ленив, чтобы исправить это прямо сейчас - и будьте осторожны, это может заблокировать ваш браузер. Лучше использовать Chrome, даже если подумать, что Firefox на этот раз не медленнее, чем Chrome (вероятно, трассировка для сравнения изображений окупается, ура!). если кому-то интересно, код можно найти здесь .

здесь я просто отбросил идею ev-alg и пошел на имитацию отжига.

пс: я даже не уверен насчет имитации отжига - это похоже на эволюционные алгоритмы, просто с численностью населения один, верно?

Answer 1

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

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

Квалификация «одобряющих сборщиков» в предыдущем абзаце преднамеренно расплывчата. Есть много разных способов сделать выбор. Похоже, вы выбираете строго приспособленных людей. Это выбор усечения. Это действительно эффективно только для определенных типов проблем. Поскольку вы безжалостно отбираете слабых людей, это часто приводит к преждевременной конвергенции.

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

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

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

Answer 2

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

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