Эволюционные алгоритмы: анализ оптимальной репопуляции

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

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

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

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

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

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

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

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

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

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

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

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

@Kyle Burton: коэффициенты кроссовера и мутации также постоянно обсуждаются в каждом классе переданных задач. к ГА и ВОП.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но обычно я держу 12% лучших, а 28% помесей; с 30% каждый для других.