[Генетические алгоритмы] для фана

Всем привет.

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

Но сначала давайте сделаем совсем краткий экскурс в эти самые алгоритмы.

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

ГА в общем случае подразумевает 4 шага, 3 из которых повторяются:

1. Создание начальной популяции. Этот шаг выполняется как понятно, единожды.

2. Размножение. На этом шаге создаётся потомство предыдущего поколения, как правило за счёт скрещивания особей старшего поколения.

3. Мутация. На этом шаге потомство подвергается случайным изменениям.

4. Селекция. Она же — отбор. На этом шаге выбираются самые сильные особи из потомства.

5. Результирующий шаг, на котором мы получаем новое, более приспособленное поколение.

Как же это можно использовать?

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

Всю систему в целом можно описать следующим образом:

1.  Создаётся остров, на котором случайным образом формируется ландшафт, определяющийся просто площадью участков земли разного рода — вода, горы, лес и равнина.

2. И тут сразу же первое отступление от правил ГА — я не создаю начальную популяцию: она формируется сама, автоматически, случайным образом.

3. Каждая особь представляется набором приобретённых свойств и атрибутов.

3.1. Атрибуты — параметры особи, которые можно измерить (например, скорость, сила и т.п.)

3.2. Свойства — качественные параметры особи (например, пол, предпочитаемая среда обитания и т.п.)

4. Каждая стадия развития мира проходит следующие шаги:

4.1. Особи пытаются размножиться (Размножение)

4.2. Происходят случайные мутации (Мутации)

4.3. Проходит селекция самых «сильных» (Селекция).

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

А пока давайте разберём, какой шаг самый важный и почему.

Размножение

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

Тут я сделаю небольшое отступление:

Возможность мутации в моей системе зависит от прогресса развития особи. Т.е., утрируя, например, существо не может атаковать, пока у него не появится сила.

Поэтому изначально, особи в моей системе имеют только 1 вариант размножения — деление. Со временем, благодаря мутациям, особь может приобрести пол и начать спариваться.

На этом шаге я столкнулся со следующими явлениями:

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

2. Если просто «суммировать» при скрещивании все параметры родителей, существа очень быстро развиваются, что по факту не так интересно, т.к. становится практически невозможно отследить плавный рост свойств и атрибутов.

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

Мутации

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

На этом шаге мне удалось выявить следующее:

1. Если не подвергать мутациям старшее поколение, то эволюция сильно замедляется, что в конце-концов приводит к вымиранию.

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

3. Если в мутациях слишком сильно влиять на рост прогресса, то ситуация аналогична предыдущему пункту.

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

Селекция

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

Что особенного на этом шаге:

1. Если оставлять в живых только самых прогрессивных, то это может привести или к полному вымиранию (в достаточно краткие сроки), или, наоборот, к экспоненциальному росту популяции. Поведение зависит от мутаций — если они примерно равномерно возникают и изменяются, то будет рост; если же мутации сильно различаются от особи к особи, то в живых будет оставаться всего 1 особь, которая впоследствии, скорее всего, умрёт.

2. Если рассматривать особи в рамках потомства одной «семьи», то эволюция будет слишком медленной, как и рост популяции. Это ещё одно отступление от норм ГА.

Выводы

Итак, какой шаг самый важный?

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

Зачем вообще всё это нужно?

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

Действующую систему, описанную в статье, можно посмотреть здесь: http://world.funcraft.ru

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

Реклама

Есть что сказать?

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s