Эволюционные Алгоритмы:Разбивки по оптимальному повторному заселению

Question

На самом деле все это есть в названии, но вот краткое изложение для всех, кто интересуется эволюционными алгоритмами:

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

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

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

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

Итак, мой вопрос заключается в следующем:каков оптимальный процент повторного заселения?

Я сохранил 10% лучших исполнителей и повторно заселил 30% скрещиваниями и 30% мутациями.Остальные 30% предназначены для новых организмов.

Я также опробовал теорию множественных островов, и мне также интересны ваши результаты по этому вопросу.

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

Заранее спасибо!

Answer 1

Сначала я попытался смоделировать, на что, по моему мнению, похожи органические системы.В конце концов решили, что это никуда не годится, и стали более агрессивными: 10% сохраненных, 20% мутировавших, 60% скрещенных и 10% случайных.

Затем я заметил, что все мои лучшие 10% были примерно одинаковы.Поэтому я увеличил коэффициент случайности до 30%.Это немного помогло, но не сильно.

Я пробовал использовать несколько островов, пропускать поколения и пересевать, что дало лучшие результаты, но все равно крайне неудовлетворительно, очень мало вариаций в топ-10%, безумно большое количество поколений для получения каких-либо результатов.В основном код научился взламывать мою оценку физической подготовки.

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

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

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

Answer 2

Лучшими источниками, с которыми я столкнулся по GA и EA, были книги Джона Козы по Генетическое программирование.Он подробно освещает тему - методы кодирования генома, случайные мутации, селекция, настройка функции приспособленности.

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

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

Зависит от того, какую "мету" вы хотите получить.

Answer 3

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

Итак, как предложил TraumaPony, настройте его самостоятельно для каждой решаемой вами проблемы или напишите что-нибудь, чтобы оптимизировать его для вас.Лучшее, что вы можете сделать, это отслеживать все ваши эксперименты с "поворотом ручки" и точной настройкой, чтобы вы могли наметить область решения и получить представление о том, как быстро оптимизировать работу в этом пространстве.Также попробуйте альтернативные техники, такие как восхождение на холм, чтобы у вас был базовый уровень для преодоления.

@Кайл Бертон:кроссовер противчастота мутаций также постоянно обсуждаемый в каждом классе задачи сдавались газу и GPs.

Answer 4

Предполагая, что у вас есть метод количественной оценки лучших исполнителей X%, я бы предложил вместо использования жестко заданного порога проанализировать распределение производительности и установить ограничение где-то в диапазоне первого значительного снижения производительности, а затем настроить ваши гибриды, мутации и новые организмы, чтобы заполнить пробелы.Таким образом, если у вас очень "продуктивная" серия, в которой множество вариаций были успешными, вы не задействуете значительное количество высококлассных исполнителей.Кроме того, если у вас "непродуктивный" запуск, вы можете отказаться от большего количества существующих организмов в пользу более новых организмов, которые должны занять их место.

Answer 5

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

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

На практике я остановил свой выбор на мультихромосомном генотипе.Одна хромосома кодирует репродуктивную функцию другой.Меньшая по размеру "репродуктивная хромосома" имела разумно фиксированную частоту мутаций и скрещивания.

Я обнаружил, что это остановило бы классическое плато и конвергенцию населения.

Кроме того, я склонен проводить как скрещивание, так и мутацию для каждого ребенка.

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

Answer 6

По-видимому, есть несколько ответов, предлагающих использовать 2-й GA для определения оптимальных параметров для 1-го GA, без упоминания о том, как определить оптимальные параметры для 2-го.Я не могу не задаться вопросом о религиозных верованиях тех, кто предлагает такой подход...

Answer 7

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

Прежде чем мы обсудим эволюционную разбивку от одного поколения к следующему, важно рассмотреть численность каждого поколения.Как правило, мой подход заключается в том, чтобы начать с довольно большой популяции (~ 100-500 тыс. особей) довольно разнообразных особей, что и предлагает Коза в некоторых своих работах.Чтобы добиться такого разнообразия с самого начала, вы могли бы разделить пространство вашего решения на группы, а затем убедиться, что в каждую группу попадает по крайней мере определенное количество пользователей.(Например,Дж.если у вас есть древовидное представление для каждого отдельного пользователя, убедитесь, что созданы равные количества глубиной 2, 3, ..., max_depth)

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

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

Тем не менее, мой текущий подход заключается в том, чтобы сохранить верхний 1%, скрестить верхние 20% с новыми 20%, скрестить верхние 40% со следующими 20%, скрестить верхние 90%, чтобы сгенерировать следующие 20%, и случайным образом сгенерировать остальные (39%).Если есть дубликаты, я удаляю их и заменяю новыми случайными пользователями.

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

Answer 8

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

Но обычно я оставляю 12% лучших и 28% помесей;по 30% каждому для остальных.