Эволюционные Алгоритмы: Оптимальные Распределения Населения

Question

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

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

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

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

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

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

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

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

Мне не безразлично, что это именно та проблема, которую может решить советник. Вы знаете, что кто-нибудь пробовал это?

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

@ Кайл Бертон: частота кроссоверов и мутаций также постоянно обсуждается в каждом классе проблем, переданных в GA и GP.

Answer 4

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

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

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

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

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

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

Answer 5

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

Answer 6

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

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

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

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

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

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

Answer 7

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

Answer 8

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

Но, как правило, я держу верхние 12% и 28% скрещиваний; с 30% каждый для остальных.