Генетический алгоритм экстремумы функции реализация. Введение.Основы генетических алгоритмов

Идея генетических алгоритмов (ГА) появилась достаточно давно (1950-1975 гг.), но по-настоящему объектом изучения они стали только в последние десятилетия. Первооткрывателем в этой области признано считать Д. Холланда, который позаимствовал многое из генетики и адаптировал под вычислительные машины. ГА широко используются в системах искусственного интеллекта, нейронных сетях и задачах оптимизации.

Эволюционный поиск

Модели генетических алгоритмов были созданы на базе эволюции в живой природе и методах рандомного поиска. При этом случайный поиск является реализацией наиболее простой функции эволюции – случайных мутаций и последующего отбора.

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

Зачем нужны генетические алгоритмы

ГА преследуют следующие цели:

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

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

Особенности ГА

Перечислим главные отличия ГА от большинства других методов поиска оптимального решения.

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

Критерии работы

Генетические алгоритмы производят расчеты исходя из двух условий:

1. Выполнение заданного числа итераций.
2. Качество найденного решения соответствует требованиям.

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

Базовая терминология

Ввиду того, что ГА основаны на генетике, то и большая часть терминологии соответствует ей. Любой генетический алгоритм работает исходя из начальной информации. Множество начальных значений есть популяция Пt = {п1, п2, ..., пn}, где пi = {г1, ..., гv}. Разберем подробнее:

• t - это номер итерации. t1, ..., tk - означает итерации алгоритма с номера 1 по k, и на каждой итерации создается новая популяция решений.
• n - размер популяции Пt.
• п1, ..., пi - хромосома, особь, или организм. Хромосома или цепочка - это закодированная последовательность генов, каждый из которых имеет порядковый номер. При этом следует иметь в виду, что хромосома может быть частным случаем особи (организма).
• гv - это гены, являющиеся частью закодированного решения.
• Локус - это порядковый номер гена в хромосоме. Аллель - значение гена, которое может быть как числовым, так и функциональным.

Что значит "закодированный" в контексте ГА? Обычно любое значение кодируется на основе какого-либо алфавита. Простейшим примером является перевод чисел из десятеричной системы счисления в двоичное представление. Таким образом алфавит представляется как множество {0, 1}, а число 15710 будет кодироваться хромосомой 100111012 , состоящей из восьми генов.

Родители и потомки

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

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

Функция приспособленности

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

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

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

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

Базовый генетический алгоритм

Разложим по шагам наиболее простой (классический) ГА.

1. Инициализация начальных значений, то есть определение первичной популяции, того множества особей, с которыми будет происходить эволюция.
2. Установление первичной приспособленности каждой особи в популяции.
3. Проверка условий прекращения итераций алгоритма.
4. Использование функции селекции.
5. Применение генетических операторов.
6. Создание новой популяции.
7. Шаги 2-6 повторяются в цикле до выполнения необходимого условия, после чего происходит выбор наиболее приспособленной особи.

Пройдемся вкратце по мало очевидным частям алгоритма. Условий прекращения работы может быть два:

1. Количество итераций.
2. Качество решения.

Генетическими операторами является оператор мутаций и оператор скрещивания. Мутация изменяет случайные гены с определенной вероятностью. Как правило, вероятность мутации имеет низкое числовое значение. Поговорим подробнее о процедуре генетического алгоритма "скрещивание". Он происходит по следующему принципу:

1. Для каждой пары родителей, содержащих L генов, случайным образом выбирается точка скрещивания Тскi.
2. Первый потомок составляется путем присоединения к генам первого родителя [Тскi+1; L] генов второго родителя.
3. Второй потомок составляется обратным путем. Теперь к генам второго родителя добавляется гены первого родителя на позициях [Тскi+1; L].

Тривиальный пример

Решим задачу генетическим алгоритмом на примере поиска особи с максимальным числом единиц. Пусть особь состоит из 10 генов. Зададим первичную популяцию в количестве восьми особей. Очевидно, наилучшей особью должна быть 1111111111. Составим для решения ГА.

• Инициализация. Выберем 8 случайных особей:

Из таблицы видно, что особи 3 и 7 имеют наибольшее число единиц, а значит являются наиболее подходящими членами популяции для решения задачи. Так как на данный момент решения требуемого качества нет, алгоритм продолжает работу. Необходимо провести селекцию особей. Для простоты объяснения пусть селекция происходит случайным образом, и мы получаем выборку особей {п7, п3, п1, п7, п3, п7, п4, п2} - это родители для новой популяции.

• Использование генетических операторов. Снова для простоты положим, что вероятность мутаций равна 0. Иными словами все 8 особей передают свои гены такими, какие есть. Для проведения скрещивания, составим пары особей случайным образом: (п2, п7), (п1, п7), (п3, п4) и (п3, п7). Так же случайным способом выбираются точки скрещивания для каждой пары:

• Составление новой популяции, состоящей из потомков:

Дальнейшие действия очевидны. Самое интересное в ГА открывается в случае, если оценить среднее количество единиц в каждой популяции. В первой популяции в среднем на каждую особь приходилось 5,375 единиц, в популяции потомков – 6,25 единиц на особь. И такая особенность будет наблюдаться даже в случае, если в ходе мутаций и скрещивания особь с наибольшим числом единиц в первой популяции потеряется.

План реализации

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

1. Определение представления (алфавита).
2. Определение операторов случайных изменений.
3. Определение выживания особей.
4. Генерация первичной популяции.

Первый этап гласит о том, что алфавит, в который будут кодироваться все элементы множества решений или популяции, должен быть достаточно гибким, чтобы одновременно позволял производить нужные операции случайных перестановок и оценивать приспособленность элементов, как первичных, так и прошедших через изменения. Математически установлено, что создать идеальный алфавит для этих целей невозможно, поэтому его составление – это один из самых сложных и ответственных этапов, чтобы обеспечить стабильную работу ГА.

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

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

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

Эффективность

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

1. Создание полной популяции, что будет включать всевозможные варианты особей в некоторой заданной области.
2. Случайное создание особей на основе всех допустимых значений.
3. Точечное случайное создание особей, когда среди допустимых значений выбирается диапазон для генерации.
4. Комбинирование первых трех способов создания популяции.

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

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

1) инициализация, или выбор исходной популяции хромосом;

2) оценка приспособленности хромосом в популяции;

3) проверка условия остановки алгоритма;

4) селекция хромосом;

5) применение генетических операторов;

6) формирование новой популяции;

7) выбор «наилучшей» хромосомы.

Блок-схема основного генетического алгоритма изображена на рис. 4.3. Рассмотрим конкретные этапы этого алгоритма более подробно с использованием дополнительных подробностей, представленных на рис. 4.4.

Рис. 4.3. Блок-схема генетического алгоритма.

Рис. 4.4. Схема выполнения генетического алгоритма.

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

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

Проверка условия остановки алгоритма. Определение условия остановки генетического алгоритма зависит от его конкретного применения. В оптимизационных задачах, если известно максимальное (или минимальное) значение функции приспособленности, то остановка алгоритма может произойти после достижения ожидаемого оптимального значения, возможно - с заданной точностью. Остановка алгоритма также может произойти в случае, когда его выполнение не приводит к улучшению уже достигнутого значения. Алгоритм может быть остановлен по истечении определенного времени выполнения либо после выполнения заданного количества итераций. Если условие остановки выполнено, то производится переход к завершающему этапу выбора «наилучшей» хромосомы. В противном случае на следующем шаге выполняется селекция.

Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки (roulette wheel selection), который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой для (где обозначает численность популяции) соответствует сектор колеса , выраженный в процентах согласно формуле

, (4.2)

, (4.3)

причем - значение функции приспособленности хромосомы , a - вероятность селекции хромосомы . Селекция хромосомы может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала , то выбор хромосомы можно отождествить с выбором числа из интервала , где и обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что . В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала , которое соответствует конкретной точке на окружности колеса. Другие методы селекции будут рассматриваться в п. 4.8.1.

В результате процесса селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью , равной численности текущей популяции.

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

В классическом генетическом алгоритме применяются два основных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation). Однако следует отметить, что оператор мутации играет явно второстепенную роль по сравнению с оператором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация - достаточно редко. Вероятность скрещивания, как правило, достаточно велика (обычно ), тогда как вероятность мутации устанавливается весьма малой (чаще всего ). Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко.

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

Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания . Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из генов, то очевидно, что точка скрещивания представляет собой натуральное число, меньшее . Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала . В результате скрещивания пары родительских хромосом получается следующая пара потомков:

1) потомок, хромосома которого на позициях от 1 до состоит из генов первого родителя, а на позициях от до - из генов второго родителя;

2) потомок, хромосома которого на позициях от 1 до состоит из генов второго родителя, а на позициях от до - из генов первого родителя.

Действие оператора скрещивания будет проиллюстрировано примерами 4.4 и 4.5 (п.п. 4.5 и 4.6).

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

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

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

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

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

Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности . Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью способом, представленным при описании соответствующего оператора. Это приводит к инвертированию значений отобранных генов с 0 на 1 и обратно. Значение , как правило, очень мало, поэтому мутации подвергается лишь небольшое количество генов. Скрещивание - это ключевой оператор генетических алгоритмов, определяющий их возможности и эффективность. Мутация играет более ограниченную роль. Она вводит в популяцию некоторое разнообразие и предупреждает потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания.

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

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

Другой пример: вы едете по скользкой дороге, и вдруг ваш автомобиль начинает заносить, справа в нескольких метрах от вас столб, а по встречной полосе едет грузовик. Внимание вопрос: как выйти из ситуации с наименьшими потерями, а лучше вообще без них. Факторов, которые нужно учитывать много: ваша скорость и скорость встречного автомобиля, расстояние до столба, «крутость» заноса и т.д. Что нужно делать? Давать газу, пытаясь выйти из заноса, или тормозить, или, может, попытаться аккуратно съехать в кювет, так чтобы не попасть в столб. Вариантов много, и для того чтобы определить оптимальный — нужно попробовать их все. Будь это компьютерной игрой – вы могли бы сохраниться и переигрывать до тех пор, пака результат вас не удовлетворит. Это и есть поиск оптимального решения.

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

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

Скажем проще: по сути, генетический алгоритм — это метод перебора решений для тех задач, в которых невозможно найти решение с помощью математических формул. Однако простой перебор решений в сложной многомерной задаче – это бесконечно долго. Поэтому генетический алгоритм перебирает не все решения, а только лучшие. Алгоритм берёт группу решений и ищет среди них наиболее подходящие. Затем немного изменяет их – получает новые решения, среди которых снова отбирает лучшие, а худшие отбрасывает. Таким образом, на каждом шаге работы алгоритм отбирает наиболее подходящие решения (проводит селекцию), считая, что они на следующем шаге дадут ещё более лучшие решения (эволюционируют).

Причём тут биология?

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

Особь – одно решение задачи.

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

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

Это вариация задачи о коммивояжёре (путешественнике) – относится к классу NP-полных, проще говоря, не может быть решена с помощью математических формул.

Решение задачи – это последовательность прохождения контрольных точек. Возьмём несколько возможных решений (особей)– это и есть .

Определения качества решений

Функция пригодности – функция определяющая качество особей популяции. В нашем примере это будет сумма расстояний от точки до точки в выбранном маршруте.

ФП = Р(1)+Р(2)+Р(3)+Р(4)+Р(5)+Р(6),

где Р(1) … Р(6) – расстояние между точками в соответствующем переходе из матрицы расстояний

Нам необходимо найти минимальное расстояние, поэтому, чем меньше значение ФП для особи, тем лучше.

Давайте посчитаем функции пригодности. Для первой особи:

Для остальных особей таким же образом получаем.

Выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить к следующему экспонату ко второй части, где описывается создание на основе ГА бота для программистской игры Robocode. Это, по последним сведениям разведки, еще не встречалось на хабре.

Часть первая. Жизнь и творчество генетического алгоритма.

Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, нас наебали, все расходимся. Например, при решении квадратного уравнения ответ (значения x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель - написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!

Хм, как же мы будем добиваться такой цели? Принесем у костра жертву богам рекурсии: напишем программу, которая напишет программу, которая бы находила функцию (программу)... Нет, во второй раз такое не прокатит. Лучше мы возьмем пример у природы, кинув наш взор на такие явления, как механизм эволюции, естественный отбор. Всё как в жизни: наши программы будут жить, спариваться, давать потомство и погибать под гнетом более приспособившихся особей, передавая свои лучшие качества потомкам. Звучит безумно, но стоит приглядеться.

Бог нашего мира программ - это наша задача. Программы должны верить в нее, спариваться ради нее, ставить в нее честь свечки в церкви и жить с единственной целью - найти смысл жизни решение этой задачи. Наиболее приспособившийся к среде (приблизившийся к решению задачи) становится альфа-самцом, выживает и дает крепкое потомство. Лузер, который просидел всю жизнь за онлайн играми не познал успеха в решении задачи, имеет совсем маленькие шансы дать потомство. Генофонд будет очищаться от вклада этих прыщавых товарищей, а всё общество программ будет идти к светлому будущему решенной задачи. Что же, в общих чертах уже понятно, теперь нужно разобраться с нюансами: во-первых, как вы себе представление спаривание программ? во-вторых, откуда мы возьмем первое поколение программ? в-третьих, по какому признаку мы будем определять приспособленность особей и как она будет влиять на скрещивание? в-четвертых, стоит определиться с условиями окончания работы алгоритма, когда всю эту оргию останавливать.

Искусство спаривания программ

Вопрос скрещивания программ не так уж прост. Случайный обмен функциями, строками или переменными приведет к жирному потоку страшных слов в ваш адрес от компилятора/интерпретатора, а никак не новую программу. То есть необходимо найти способ скрестить программы корректно . Умные дяди нашли выход. А умные мальчики и девочки, изучавшие строения компиляторов, тоже уже догадались. Да-да, это синтаксическое дерево .

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

Например: некоторая особь-программа square из двух выражений, пытающаяся (не особо удачно) решить квадратное уравнение:
function square(a, b, c){ x1 = min(sin(b)*(a+1), 0); x2 = 3 + exp(log(b*a)); return {x1, x2}; }
С представлением определились, теперь надо разобраться с хранением. Так как вокруг этих самых программ еще предстоит множество плясок, в том числе передача их из одной часть системы в другую (которые, вообще говоря, в моем случае вообще были написаны на разных языках), то хранение нашей особи в виде дерева не очень-то удобное. Для представления более удобным способом (идеально - набор строк над некоторым конечным алфавитом) нашу особь-программу-набор_деревьев придется научиться кодировать/раскодировать.

Вроде как дерево, а вроде и нет

Здесь n, +, *, if - функции; 2 - константа; a и b - переменные. В реальных задачах таблица поувесистей, с таким набором и квадратное уравнение не решить. Также надо иметь ввиду тот факт, что во избежании деления на нуль и других сценариев апокалипсиса все функции должны быть определены на всём множестве вещественных чисел (ну, или какое вы там множество используете в задаче). А то придется сидеть на карауле, отлавливать логарифмы от нуля и потом разбираться, что с этим делать. Мы люди не гордые, мы пойдем легким путем, исключая подобные варианты.

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

По таблице идентифицируем каждый элемент, вспоминаем также и про арность:

Теперь при помощи арности расставляем ссылки на аргументы функций:

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

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

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

У меня глаза от папы такие

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

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

Эй, эта девушка со мной!

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

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

Функция приспособленности выдает каждой особи поколения некоторое число, показывающее ее полезность, приспособленность. Это значение будет влиять на процедуру отбора (селекции): чем больше у особи это значение, тем больше у нее вероятность найти пару для скрещивания (и даже не одну). На практике, после вычисления приспособленности для всех особей поколения мы нормируем эти значения (чтобы сумма приспособленностей особей равнялась 1) и для каждого из мест для поцелуев бросается жребий (случайное число от 0 до 1), определяющий счастливчика. Альфа-самец может получить себе несколько мест, неудачник ничего не получит и так и останется в одиночестве с потертым календариком 1994 года с Памеллой. Такой способ селекции называется «отбором методом рулетки», и схематично это выглядит как-то так:

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

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

Сотворения мира и Апокалипсис

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

Эй, ты! Харошш парить мозг! Что в итоге-то?

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

Часть вторая. Роль генетического алгоритма в образе бота Robocode.

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

Как представить решение задачи в виде особи

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

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

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

Функции:
+(x, y) = x + y
++(x, y, z) = x + y + z
n(x) = -x
*(x, y) = x * y
**(x, y) = x * y * z
min(x, y) = x > y? y: x
s(x) = 1/(1+exp(-x))
if(x, y, z, w) = x > y? z: w

Переменные:
x, y - координаты танка соперника относительно нашего танка;
dr - расстояние, которое осталось «доехать» нашему танку;
tr - угол, на который осталось повернуться нашему танку;
w - расстояние от нашего танка до края поля;
dh - угол между направлением на танк соперника и пушкой нашего танка;
GH - угол поворота пушки нашего танка;
h - направление движения танка соперника;
d - расстояние между нашим танком и танком соперника;
e - энергия танка соперника;
E - энергия нашего танка.

Ну и константы: 0.5, 0, 1, 2, 10

Функция приспособленности

Вообще говоря, вычисление приспособленности особи включает в себя проведение серии боев! Т.е. такой, казалось бы, незначительный пункт, как просчет приспособленности, состоит из таких плясок с бубном:
1) Наша система сохраняет закодированные хромосомы особи в файл chromosome.dat;
2) Для каждой особи запускается среда «Robocode», которая организовывает поединок. На вход ей мы подаем файл формата.battle, описывающий условия боя - список сражающихся танков, размеры поля, количество раундов и прочее;
3) Для битвы Robocode загружает танки, наш робот-оболочка считывает файл chromosome.dat с закодированным поведением, интерпретирует его в набор действий и ведет согласно им бой;
4) Среда Robocode по окончании поединка записывает результат битвы в файл results.txt и на этом завершает свою работу;
5) Наша система подбирает этот файл, парсит и выделяет из него значения total score нашего танка и соперника. Путем нехитрой арифметики получаем значение приспособленности.

Как наши их, да?

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

В качестве результата продемонстрируем итоги создания соперника роботам Walls и Crazy:




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

После созерцания промыть глаза спиртом

Глава 1. Генетические алгоритмы

1.1 Естественный отбор в природе

1.2 Представление объектов. Кодирование признаков

1.3 Основные генетические операторы

1.4 Схема функционирования генетического алгоритма

Глава 2. Задачи оптимизации

2.1 Задачи, решаемые с помощью генетических алгоритмов

2.2 Математическая постановка задачи оптимизации

2.3 Решение Диофантова уравнения

2.4 Пути решения задач оптимизации

2.5 Задача коммивояжера

Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам

3.1 Обоснование выбора программного обеспечения

3.2 Описание программной реализации

Заключение

1.1. Естественный отбор в природе

“XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?..”

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

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

Почти в каждой клетке любой особи есть набор хромосом, несущих информацию об этой особи. Основная часть хромосомы - нить ДНК, определяющая, какие химические реакции будут происходить в данной клетке, как она будет развиваться и какие функции выполнять. Ген - это отрезок цепи ДНК, ответственный за определенное свойство особи, например за цвет глаз, тип волос, цвет кожи и т.д. При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.

При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов . Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

1.2. Представление объектов. Кодирование признаков

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

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма . Значения кодов Грея рассмотрены в таблице ниже:

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит