Эволюционных алгоритмы: Оптимальная Репопуляция Поломка

Question

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

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

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

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

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

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

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

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

Это не потеряно для меня, что это именно тот тип проблемы, который может решить EA. Знаете ли вы, что кто-то пытается это сделать?

Заранее благодарен!

Answer 1

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

@ Kyle Burton: коэффициент кроссовера и мутации также равен constantly debated в каждом классе проблем, переданных GA и GP.

Answer 5

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

Answer 6

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

Answer 7

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

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

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

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

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

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

Answer 8

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

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

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

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

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

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