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

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

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

Впервые подобный алгоритм был предложен в 1975 году Дж. Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.

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

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

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

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

1. из популяции выбираются две особи, которые будут родителями;
2. определяется (обычно случайным образом) точка разрыва;
3. потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора :

Хромосома_1: 0000000000

Хромосома_2: 1111111111

Допустим, разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1: 0000000000 >> 000 1111111 Результирующая_хромосома_1

Хромосома_2: 1111111111 >> 111 0000000 Результирующая_хромосома_2

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 >> 1111111 000

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

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

Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B 0 = {A 1 ,A 2 ,…,A k)
2. Вычислить приспособленность (пригодность ) каждой особи F Ai = fit(A i) , i=1…k и популяции в целом F t = fit(B t) (также иногда называемую термином фиттнес ). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
3. Выбрать особь A c из популяции. A c = Get(B t)
4. С определенной вероятностью (вероятностью кроссовера P c) выбрать вторую особь из популяции А c1 = Get(B t) и произвести оператор кроссовера A c = Crossing(A c ,A c1).
5. С определенной вероятностью (вероятностью мутации P m) выполнить оператор мутации. A c = mutation(A c).
6. С определенной вероятностью (вероятностью инверсии P i) выполнить оператор инверсии A c = inversion(A c).
7. Поместить полученную хромосому в новую популяцию insert(B t+1 ,A c).
8. Выполнить операции, начиная с пункта 3, k раз.
9. Увеличить номер текущей эпохи t=t+1.
10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Рассмотрим подробнее отдельные этапы алгоритма.

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

P Get(Ai) ~ Fit(A i)/Fit(B t).

Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор . Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма , которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Другой важный момент – определение критериев останова.

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

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

Пример

Найти максимум функции f(x)=x2 в диапазоне 0

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

Установим размер популяции, равный четырем строкам.

Таблица 11.1 – Начальная популяция и оценка пригодности

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

Таблица 11.2– Родительский пул и скрещивание

Второе поколение без мутации приведено ниже.

Таблица 11.3 – Второе поколение

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

Применение генетических алгоритмов

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

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

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

Примеры программного обеспечения

На рынке программного обеспечения имеется несколько продуктов, использующих генетические алгоритмы: Evoler, GeneHunter, Genetic Training Option for BrainMaker, Auto2Fit, Omega, Genitor, Xpert Rule Gen Asy, PC/Beagle, EM, Escapate, GAGA, Gausd, Genesis, OOGA, EnGENer, Game, GA Workbench, Pegasus и др.

Введение

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

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

• Генетические алгоритмы (ГА).
• Эволюционные стратегии.
• Генетическое программирование.
• Эволюционное программирование.

Генетические алгоритмы применяются для решения таких задач, как:

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

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

Природный механизм

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

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

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

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

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

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

Классический генетический алгоритм

Родителем современной теории генетических алгоритмов (ГА) считается Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems» (1975), стала классикой в этой области. В ней Холланд впервые ввел термин «генетический алгоритм». Сейчас описанный там алгоритм называют «классический ГА» (иногда «канонический ГА», canonical GA), а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.

Ученики Холланда Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David E. Goldberg) внесли огромный вклад в развитие ГА. На книгу Голдберга «Genetic algorithms in search optimization and machine learning» (1989), ссылаются авторы практически каждой работы по этой теме.

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

Функция приспособленности и кодирование решений

Итак, пусть перед нами стоит задача оптимизации. Варьируя некоторые параметры, к примеру, если решать задачу размещения, координаты размещаемых элементов, нужно найти такую их комбинацию, чтобы минимизировать занимаемую площадь. Такую задачу можно переформулировать как задачу нахождения максимума некоторой функции f (x 1 , x 2 , …, x n). Эта функция называется функцией приспособленности (fitness function) и используется для вычисления приспособленности особей. Она должна принимать неотрицательные значения, а область определения параметров должна быть ограничена.

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

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

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

Например, пусть переменная x k принадлежит отрезку [ x min , x max ]. Закодируем ее бинарной строкой из l битов. Тогда строка s k обозначает следующее значение переменной x k:

X k = x min + s k (x max − x min) ⁄ 2 l

если в формуле s k обозначает значение бинарного числа, кодируемого этой строкой.

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

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

101100 11001011 01101100 1100 1 11101 | x 1 | x 2 | | | | x n |

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

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

Алгоритм работы

На рисунке изображена схема работы любого генетического алгоритма:

В классическом ГА начальная популяция формируется случайным образом. Фиксируется размер популяции (количество особей в ней будем обозначать символом N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L -битная строка, где L — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.

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

Шаг алгоритма состоит из трех стадий: генерация промежуточной популяции (intermediate generation ) путем отбора (selection ) текущего поколения (current generation ), скрещивание (recombination ) особей промежуточной популяции путем кроссовера (crossover ), что приводит к формированию нового поколения (next generation ), и мутация нового поколения. На рисунке изображены первые две стадии:

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

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection ). Можно его реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора каждой особи пропорционален ее приспособленности. Изначально промежуточная популяция пуста. N раз запуская рулетку, выберем требуемое количество особей для записи в промежуточную популяцию. Ни одна выбранная особь не удаляется с рулетки. Такой отбор называется stochastic sampling .

Другой способ отбора, который также является пропорциональным, это . Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная — это ее вероятность попасть туда еще раз. Пусть, к примеру, для некоторой особи i f i ⁄ < f > = 1.36 (< f > — средняя приспособленность текущей популяции). Тогда она будет выбрана один раз, а затем с вероятностью 0.36 еще раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N , причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:

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

В классическом генетическом алгоритме применяется одноточечный оператор кроссовера (1-point crossover ): для родительских хромосом (т. е. строк) случайным образом выбирается точка раздела, и они обмениваются отсеченными частями. Полученные две строки являются потомками:

К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью p m инвертируется. Эта вероятность обычно очень мала, менее 1%.

1011001100 101101 ⇒ 1011001101 101101

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

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

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

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

Шаблоны

Шаблоном (schema ) называется строка длины L (т. е. той же длины, что и любая строка популяции), состоящая из символов {0, 1, *} (где * — «don"t care» символ). Будем говорить, что строка является представителем данного шаблона, если в позициях, где знак шаблона равен 0 или 1, она имеет тот же символ. Например, у шаблона 01*0*110 следующие представители:

• 010 00 110
• 010 01 110
• 011 10 110
• 011 11 110

Порядком (order ) шаблона называется количество фиксированных битов в нем. Определяющей длиной (defining length ) шаблона называется расстояние между его крайними фиксированными битами. Например, для шаблона *1***01* порядок o = 3, а определяющая длина Δ = 5.

Очевидно, что количество представителей шаблона H равно 2 L − o (H) , а количество шаблонов равно 3 L (действительно, шаблоны — это строки, у которых на каждой позиции может находиться один из трех символов).

Если представить пространство поиска в виде гиперкуба, то строки это его вершины, а шаблон определяет в нем гиперплоскость. К примеру, шаблон **1 определяет правую грань этого трехмерного куба:

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

На нем видно, что некоторые шаблоны имеют с среднем по всему пространству поиска большую приспособленность, чем другие.

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

Внешне кажется, что генетический алгоритм при отборе выбирает строку, однако при этом неявным образом происходит выборка шаблонов, представителем которых она является. Это означает, что на каждом поколении количество представителей шаблона изменяется в соответствии с текущей приспособленностью этого шаблона. У «хороших» шаблонов представители в среднем более приспособленные, а значит, они чаще будут выбираться в промежуточную популяцию. «Плохие» шаблоны имеют много шансов вымереть. Одна строка является представителем сразу многих шаблонов (а именно 2 L: на каждой позиции мы либо оставляем бит строки, либо заменяем его на «*»). Поэтому при отборе одной строки отбирается сразу целое множество шаблонов. Это явление получило название неявный параллелизм (implicit parallelism ).

Теорема шаблонов

Теорема шаблонов (The Schema Theorem ) была приведена в упомянутой выше работе Холланда и является первой попыткой объяснить, почему генетические алгоритмы работают. Она показывает, как изменяется доля представителей шаблона в популяции.

Пусть M (H , t) — число представителей шаблона H в t -ом поколении. В силу того, что при построении промежуточной популяции используется пропорциональный отбор, в ней количество представителей данного шаблона будет

M (H , t + intermediate) = M (H , t) f (H , t) ⁄ < f (t)>

где f (H , t) — приспособленность шаблона H в t -ом поколении, а < f (t)> — средняя приспособленность t -го поколения.

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

Δ(H) (1 − P (H , t) f (H , t) ⁄ < f (t)>) ⁄ (L −1)

где P(H, t) — доля представителей шаблона H в t -ом поколении. Первый множитель произведения равен вероятности точки раздела попасть между фиксированными битами шаблона, а второй — вероятности выбрать в пару представителя другого шаблона.

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

Таким образом, после кроссовера, переходя от количества представителей к их доле, получаем следующее неравенство:

< f (t)>) ⁄ (L −1)] ⁄ < f (t)>

Теперь учтем влияние мутации. Для каждого фиксированного бита вероятность того, что он не будет инвертирован, равна (1 − p m). Поскольку всего в шаблоне фиксированных битов o (H), то верна следующая итоговая формула теоремы шаблонов:

P (H , t + 1) ≥ P (H , t) f (H , t) (1 − p m) o (H) ⁄ < f (t)>

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

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

Строительные блоки

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

Холланд (1992) показал, что в то время, как ГА обрабатывает N строк на каждом поколении, в то же время неявно обрабатываются порядка N 3 гиперплоскостей. Это доказывается с рассчетом на реально применимые размеры популяции и длины строки. Практически это означает, что большая популяция имеет возможность локализовать решение быстрее, чем маленькая. Для оценки рекомендуемого размера популяции в зависимости от длины строки можно вспомнить, что всего гиперплоскостей 3 L .

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

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

Все локальные максимумы приведенной функции приходятся на блок **0*, а минимумы — на **1*, поэтому очевидно, что после отбора основная часть особей будут представителями первого блока. Левая половина графика в среднем ниже правой, поэтому доля блока 1*** будет преобладать над долей 0***. Получается, что основная масса особей окажутся представителями блока 1*** и в то же время **0*, значит, большое их количество будут представителями блока 1*0*. Теперь, выбирая между блоками 100* и 110*, получаем, что второй блок будет преобладать над первым. Таким образом, можно сказать, что хорошие строительные блоки малого порядка сложились в приспособленные блоки большего порядка, и в результате мы оказались в области глобального максимума, чем приблизились к решению задачи.

Настройка ГА

Генетический алгоритм производит поиск решений двумя методами одновременно: отбором гиперплоскостей (hyperplane sampling ) и методом hill-climbing . Кроссовер осуществляет первый из них, поскольку комбинирует и совмещает шаблоны родителей в их детях. Мутация обеспечивает второй метод: особь случайным образом изменяется, неудачные варианты вымирают, а если полученное изменение оказалось полезным, то, скорее всего, эта особь останется в популяции.

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

С точки зрения теоремы шаблонов, мутация только вредит росту количества представителей хороших шаблонов, поскольку лишний раз их разрушает. Однако мутация просто необходима для ГА с малым размером популяции. Дело в том, что для малочисленных популяций свойственна преждевременная сходимость (premature convergence ). Это ситуация, когда в некоторых позициях все особи имеют один и тот же бит, но такой набор битов не соответствует глобальному экстремуму. При этом кроссовер практически не изменяет популяции, т. к. все особи почти одинаковы. В этом случае мутация способна инвертировать «застрявший» бит у одной из особей и вновь расширить пространство поиска.

Введем понятие давления отбора (selection pressure ) — это мера того, насколько различаются шансы лучшей и худшей особей популяции попасть в промежуточную популяцию. Для пропорционального отбора эта величина имеет свойство уменьшаться с увеличением средней приспособленности популяции. Действительно, при этом для каждой особи отношение f ⁄ < f > стремится 1, а значит шансы плохой и хорошей особей создать потомство уравниваются.

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

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

Другие модели ГА

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

Кодирование

Если сравнивать кодирование бинарным алфавитом и небинарным, то первый вариант обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество. Действительно, если требуется закодировать 2 L значений, то для бинарного алфавита количество гиперплоскостей будет 3 L , тогда как при использовании, к примеру, четырехзначного алфавита длина слов будет в 2 раза меньше, и гиперплоскостей будет 5 L ⁄ 2 , т. е. меньше.

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

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

Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея , а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs , когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f (x) = x 2 . Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.

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

Кроссовер

Одноточечный кроссовер мы рассмотрели выше.

При двухточечном кроссовере для родительской пары случайным образом выбираются 2 точки раздела, и родители обмениваются промежутками между ними. В результате получаются два ребенка. Удобно в этом случае представить строки в виде колец:

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

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

Однородный кроссовер осуществляется следующим образом: один из детей наследует каждый бит с вероятностью p 0 у первого родителя, а иначе у второго. Второй ребенок получает все остальные не унаследованные биты. Обычно p 0 = 0.5. Для однородного кроссовера не важна определяющая длина шаблона, и вообще в большинстве случаев шаблон разрушается. Такой агрессивный оператор плохо предназначен для отбора гиперплоскостей, однако его применение оправдано при малом размере популяции, т. к. он препятствует преждевременному схождению, свойственному таким популяциям.

Стратегии отбора

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

Ранковый отбор (rank selection ) отличается от пропорционального тем, что для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.

Турнирный отбор (tournament selection ) осуществляется следующим образом: из популяции случайным образом выбирается t особей, и лучшая из них помещается в промежуточную популяцию. Этот процесс повторяется N раз, пока промежуточная популяция не будет заполнена. Наиболее распространен вариант при t = 2. Турнирный отбор является более агрессивным, чем пропорциональный.

Отбор усечением (truncation selection ): популяция сортируется по приспособленности, затем берется заданная доля лучших, и из них случайным образом N раз выбирается особь для дальнейшего развития.

Стратегии формирования нового поколения

Выделяют два типа формирования нового поколения после получения множества детей в результате кроссовера и мутации:

1. дети замещают родителей;
2. новое поколение составляется из совокупности и детей, и их родителей, например, выбором N лучших.

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

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

Некоторые модели генетических алгоритмов

Классический ГА был рассмотрен выше. Напомним, что его создал Holland (1975).

Genitor

Этот алгоритм был создан Уитли (D. Whitley). Genitor -подобные алгоритмы отличаются от классического ГА следующими тремя свойствами:

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

Утверждается (Syswerda, 1991), что в Genitor поиск гиперплоскостей происходит лучше, а сходимость быстрее, чем у классического ГА.

CHC

CHC расшифровывается как Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation . Этот алгоритм был создан Eshelman (1991) и характеризуется следующими параметрами:

• Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.
• Для скрещивания выбирается случайная пара, но не допускается, чтобы между родителями было мало Хэммингово расстояние или мало расстояние между крайними различающимися битами.
• Для скрещивания используется разновидность однородного кроссовера HUX (Half Uniform Crossover ): ребенку переходит ровно половина битов каждого родителя.
• Размер популяции небольшой, около 50 особей. Этим оправдано использование однородного кроссовера.
• CHC противопоставляет агрессивный отбор агрессивному кроссоверу, однако все равно малый размер популяции быстро приводит ее к состоянию, когда создаются только более или менее одинаковые строки. В таком случае CHC применяет cataclysmic mutation : все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.

Hybrid Algorithms

Идея гибридных алгоритмов (hybrid algorithms ) заключается в сочетании генетического алгоритма с некоторым другим методом поиска, подходящим в данной задаче (зачастую это бывает hill-climbing ). На каждом поколении каждый полученный потомок оптимизируется этим методом, после чего производятся обычные для ГА действия. При использовании hill-climbing получается, что каждая особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации.

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

Генетический алгоритм способен быстро найти во всей области поиска хорошие решения, но он может испытывать трудности в получении из них наилучших. Такой метод, как hill-climbing быстро достигает локального максимума, однако не может искать глобальный. Сочетание этих двух алгоритмов способно использовать преимущества обоих.

Параллельные ГА

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

Сделаем из классического ГА параллельный. Для этого будем использовать турнирный отбор. Заведем N ⁄ 2 процессов (здесь и далее процесс подразумевается как некоторая машина, процессор, который может работать независимо). Каждый из них будет выбирать случайно из популяции 4 особи, проводить 2 турнира, и победителей скрещивать. Полученные дети будут записываться в новое поколение. Таким образом, за один цикл работы одного процесса будет сменяться целое поколение.

Island Models

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

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

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

Cellular Genetic Algorithms

Cellular Genetic Algorithms — модель параллельных ГА. Пусть дано 2500 процессов, расположенных на сетке размером 50×50 ячеек, замкнутой, как показано на рисунке (левая сторона замыкается с правой, верхняя с нижней, получается тор).

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

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

Другие модели

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

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

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

Наблюдения

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

Факторы, создающие сложность для ГА

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

Размер популяции

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

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

Выводы

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

Примеры применения ГА

• Демонстрация работы классического ГА на многоэкстремальной функции (http://ai.bpa.arizona.edu/~mramsey/ga.html).
• Решение задачи коммивояжера (TSP) при помощи ГА (http://lib.training.ru/Lib/ArticleDetail.aspx?ar=803&l=&mi=93&mic=112).
• Обучение модели человека ходьбе при помощи ГА (http://www.naturalmotion.com/pages/technology.htm).
• Еще одна демонстрация работы ГА (http://www.rennard.org/alife/english/gavgb.html).

Литература

1. Darrel Whitley, A Genetic Algorithm Tutorial, Statistics and Computing (4): 65-85, 1994.
2. Darrel Whitley, An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls, Journal of Information and Software Technology 43: 817-831, 2001.
3. K. Deb, S. Agrawal, Understanding Interactions Among Genetic Algorithm Parameters, 1998.
4. Авторский сайт Ю. Цоя (http://www.qai.narod.ru/).
5. Исаев С.А. Популярно о генетических алгоритмах (http://algolist.manual.ru/ai/ga/ga1.php).

Булат Яминов

Спасибо, полезная статья.

Хочу обратить ваше внимание на несколько моментов.

В разделе?Шаблоны? в столбик перечислены представители шаблона. В третьем и четвертом представителях следует на четвертой позиции писать цифру 0, вместо 1. В абзаце перед изображением куба говорится, что?шаблон определяет в нем гиперплоскость?, что верно лишь для некоторых шаблонов. Например, *11 уже не гиперплоскость (коразмерность не равна 1).

Надеемся, посетители этой страницы обратят внимание на ваши замечания.

И некоторые языковые опечатки. <... ...="">

Спасибо, указанные вами опечатки устранены.

В разделе?Примеры применения ГА?, к сожалению, 3 битых ссылки.

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

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

2. Устанавливается t= t+1. Производится выбор двух родителей (хромосом) для реализации оператора кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

3. Формируется генотип потомков. Для этого с заданной вероятностью производится оператор кроссинговера над генотипами выбранных хромосом. Далее с вероятностью 0,5 выбирается один из потомков P i (t) и сохраняется как член новой популяции. После этого к P i (t) последовательно применяется оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняется как P k (t).

4. Определяется количество хромосом для исключения их из популяции, чтобы ее размер оставался постоянным. Текущая популяция обновляется заменой отобранных хромосом на потомков P k (t).

5. Производится определение приспособленности (целевой функции) и пересчет средней приспособленности всей полученной популяции.

6. Если t = t заданному, то переход к 7, если нет, то переход к 2.

7. Конец работы.

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

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

ПГА состоит из трех операторов:

репродукция;

кроссинговер;

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

Рассмотрим пример Д. Гольдберга: необходимо найти значение максимума функции f(x)=x 2 на целочисленном интервале . Традиционными методами можно изменять значения переменной x, пока не получим максимальное значение f(x).

Для объяснения и реализации ПГА построим следующую таблицу:

В столбце 2 табл. расположены 4 хромосомы (представленные в двоичном коде), сгенерированные случайным образом. Значение ЦФ для каждой хромосомы (столбец 4) определяется как квадрат значения десятичного кода двоичного числа, которое приведено для хромосом во втором столбце таблицы. Тогда суммарное значение ЦФ всех хромосом равно 890. Для селекции хромосом используется оператор репродукции на основе колеса рулетки. На рисунке поля колеса рулетки соответствуют значению ЦФ каждой хромосомы в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для реализации следующего оператора. Очевидно, не всегда хромосома с большим значением ЦФ в результате ОР будет выбрана для дальнейших преобразований.

Колесо рулетки для примера

На основе реализации ОР выбираются хромосомы для применения ОК. Оператор кроссинговера, как правило, выполниться в 3 шага, одним из ОК описанным выше. Точка разрыва kвыбирается случайно между 1 и числом равным длине хромосомы минус единица, то есть в интервале (1, L-1). Длина хромосомы L – это число значащих цифр в ее коде. В рассматриваемом примере таблицы длина каждой хромосомы равна пяти (L=5). На основе ОК создаются две новые хромосомы, путем обмена их частей между позициями (k+1) и L соответственно.

Например, рассмотрим хромосомы 1 и 2 из начальной популяции. Пусть k=1. Тогда получим:

P 1 0 | 1 1 0 0 До применения оператора кроссинговера

P 2 1 | 0 0 0 0,

-----------------

P 1 0 0 0 0 0 После применения оператора кроссинговера

P 2 1 1 1 0 0.

Работа ПГА начинается с репродукции. Хромосомы для следующей генерации выбираются путем вращения колеса рулетки. В примере колесо рулетки вращается 4 раза. Это число соответствуют мощности начальной популяции.

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

где f i (x)значение ЦФ i-й хромосомы в популяции, sum f(x)суммарное значение ЦФ всех хромосом в популяции. Величину
также называют нормализованной вероятностью выбора. Ожидаемое число копий

i-й хромосомы после реализации ОР определяются по формуле:

где
число анализируемых хромосом, причемN G включается вN.

Ожидаемое число копий хромосомы P i , переходящее в следующее поколение, также иногда определяют на основе выражения:

.

где
среднее значение ЦФ по всей популяции.

Тогда для рассматриваемого примера, ожидаемое число копий для первой хромосомы из таблицы равно 0,164=0,64 копий, для второй0,294=1,16 копий, для третьей0,054 = 0,2 и наконец для четвертой0,54=2. Используя модель «бросание монеты» можно определить число полученных копий. Например, (см. столбец 7 таблицы) хромосомы P 1 и P 2 получают 1 копию, хромосома P 4 – 2 копии, и хромосома 3 не получает копий. Сравнивая этот результат с ожидаемым числом копий, получаем то, что «лучшие» хромосомы дают большее число копий, «средние» остаются и «плохие» удаляются после реализации оператора репродукции.

Для рассматриваемого примера построим таблицу. В столбце 2 приведен вид 4 хромосом после выполнения оператора репродукции. В столбце 3 приведены списки пар хромосом, которые выбраны случайным образом для реализации оператора кроссинговера. В столбце 4 указан номер позиции для точки разреза хромосом. В столбце 5 приведен вид 4 хромосом после выполнения оператора кроссинговера. В столбце 6 приведены значения десятичного кода двоичного числа каждой хромосомы столбца 5. В столбце 7 приведено значение f(x) для каждой из 4 хромосом новой популяции. В строке 5 приведено суммарное значение ЦФ хромосом новой популяции, в строке 6 –среднее значение их ЦФ, а в строке 7- максимальное значение ЦФ хромосомы из новой популяции.

Применяя к популяции полученной после реализации оператора репродукции (столбец 2 табл.) оператор кроссинговера, получим новую популяцию хромосом (5 столбец таблицы). В принципе оператор кроссинговера можно применять любое число раз. После проведения одной генерации ПГА улучшились все показатели: среднее и максимальное значение ЦФ.

Далее, согласно схеме выполнения ПГА, реализуется оператор мутации. Существует большое количество видов операторов мутации. Заметим, что эти операторы соответствуют перестановкам элементов внутри заданного множества. Очевидно, что при небольшой длине хромосомы L (порядка 1020) можно выполнить полный перебор за приемлемое время и найти наилучшие решения. При увеличении L до 50200 и выше, полный перебор произвести затруднительно, и необходимы другие механизмы поиска. Здесь как раз и приходит на помощь направленно-случайный поиск, который реализуется на основе ПГА.

Отметим, что глобальный максимум можно было найти еще на этапе реализации кроссинговера. Для этого необходимо было увеличить пространство поиска. Например, если в столбце 5 табл. выбрать хромосомы P 2 и P 4 и между ними выполнить оператор кроссинговера (точка ОК выбрана случайно и равна 3), то получим:

P 2: 1 0 1 | 1 1 (ЦФ-23)

P 4: 1 1 1 | 0 0 (ЦФ-28)

P 2 : 1 0 1 0 0 (ЦФ-20)

P 4 : 1 1 1 1 1 (ЦФ-31).

Решение P 4 , полученное в результате применения ОК случайным образом, является наилучшим результатом (глобальным оптимумом).

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

потомки являются точными копиями родителей (неполовое воспроизводство без мутации);

потомки имеют «большие» отличия от родителей.

В генетических алгоритмах в основном используют комбинации этих механизмов. Отметим, что в инженерных задачах начальная популяция может выбираться любым образом, например, моделированием «бросания монеты» (орел = 1, решка = 0). Тогда оператор репродукции выполняется через моделирование движения колеса рулетки. Оператор кроссинговера в задачах вычислительного характера обычно выполняется через двоичное декодирование двух положений монеты. Часто применяют другие типы ОК и другие технологии его выполнения. Вероятность ОК допускается равной Рr(ОК) = 1.0 и меньше, вероятность ОМ допускается равной Рr(ОМ) = 0.01 и больше. В общем случае вероятность применения оператора мутации зависит от знаний о решаемой задаче.

Приведем другой стандартный тип генетического алгоритма, описанный Л.Девисом:

Инициализация популяции хромосом.

Оценка значения каждой хромосомы в популяции.

Создание новых хромосом посредством скрещивания текущих хромосом; применение операторов мутации и рекомбинации.

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

Оценка значений новых хромосом и вставка их в популяцию.

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

Конец работы алгоритма.

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

Приведем пример модифицированного ПГА:

1. Создание начальной популяции решений.

2. Моделирование популяции (определение ЦФ для каждой хромосомы).

3. Пока не проведено необходимое число генераций или не закончилось время, заданное на реализацию алгоритма или не найдено оптимальное значение ЦФ (если оно известно):

а) выбор элементов для репродукции;

Применение:

б) оператора кроссинговера для создания потомков;

в) оператора мутации;

г) оператора инверсии;

д) оператора транспозиции;

е) оператора транслокации;

ж) оператора сегрегации;

з) оператора удаления вершин;

и) оператора вставки вершин;

к) рекомбинация родителей и потомков для создания новой генерации;

л) оператора редукции.

4. Реализация новой генерации.

Новые модификации ГА могут строиться путем объединения, например, пунктов «б – л» или их частичного устранения, или их перестановок, а также на основе применения адаптационных принципов управления эволюционным поиском.

Введение в аксиоматическую теорию генетических алгоритмов

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

Пусть каждому исходному понятию и отношению аксиоматической теории ГА поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации . Всякому утверждению U теории ГА ставится в соответствие некоторое высказывание U* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории ГА соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории ПГА, которая в частности может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория ГА непротиворечива, то непротиворечива и теория ПГА.

Пусть теория ГА проинтерпретирована в теории ПГА таким образом, что все аксиомы A i теории ГА интерпретируются истинными суждениями A i * теории ПГА. Тогда всякая теорема теории ГА, то есть всякое утверждение А, логически выведенное из аксиом A i в ГА, интерпретируется в ПГА некоторым утверждением A * , выводимым в ПГА из интерпретаций A i * аксиом A i и, следовательно, истинным.

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

Язык системы ГА: аппарат алгебры логики; теория множеств; теория графов, теория алгоритмов, основные положения биологии и теории систем.

1. Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.

   Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории ГА:

построение моделей эволюций;

конструирования популяций;

построения ЦФ;

разработки генетических операторов;

репродукции популяций;

рекомбинации популяций;

редукции;

адаптации.

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

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

Популяция конструируется случайным образом.

Выполнение оператора репродукции производится на основе «колеса рулетки».

Обязательное использование операторов кроссинговера и мутации.

Размер популяции после каждой генерации остается постоянным.

Размер популяции меняется.

Число копий (решений), переходящих в следующую генерацию меняется.

Целевая функция определяется на основе принципа «Выживание сильнейших».

Правила вывода ГА. Фиксируется конечная совокупность предикатов П 1 , П 2 ,…, П k на множестве всех формул системы. Пусть П (x 1 ,…,x ni +1) – какой-либо из этих предикатов (n i 0) если, для данных формулF 1 ,…,F ni +1 утверждение П (F 1 ,…,F ni +1) истинно, то говорят, что формулаF ni +1 непосредственно следует из формулF 1 ,…,F ni +1 по правилу П i .

Заданием 1,2,3 исчерпывается задание формальной системы ГА как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ГА называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ГА, либо непосредственно следует из каких-либо предшествующих ей (этой последовательности) формул по одному из правил вывода П i системы.

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

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

«поиск – эволюция»;

«эволюция – поиск»;

«поиск – эволюция - поиск»;

«эволюция – поиск - эволюция».

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

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

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

Выводы

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

Существует четыре основных отличия ГА от оптимизационных методов:

прямое преобразование кодов;

поиск из популяции, а не из единственной точки;

поиск через элементы (слепой поиск);

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

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

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

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

Генетические алгоритмы (ГА) — это стохастические, эвристические оптимизационные методы, впервые предложенные Джоном Холландом в 1975 году. Они основываются на идее эволюции с помощью естественного отбора. Кроме более быстрого нахождения экстремума, к положительным свойствам генетических алгоритмов можно отнести и нахождение «глобального» экстремума. В задачах, где целевая функция имеет значительное количество локальных экстремумов, в отличие от градиентного метода, генетические алгоритмы не «застревают» в точках локального экстремума, а позволяют найти «глобальный» минимум.

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

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

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

ГА производит над особями следующие действия

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

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

Целевая функция будет иметь вид

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

Мутацией будет являться операция генерации нового случайного числа рассматриваемой популяции.

Инверсия будет изменять значение хромосомы на некоторую небольшую величину, таким образом осуществляя поиск в окрестностях точки с наилучшим решением.
Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#define _USE_MATH_DEFINES
#include
#include
#include
using namespace std;
double func(double x)
{
return sin(M_PI * x / 180) - 1 / x;
}
double mutation(double x0, double x1) // мутация: генерация случайной величины
{
const int NUM = 100000000;
return fabs((double )((rand() * NUM) % (int )((x1 - x0)*NUM) + 1) / NUM) + x0;
}
double inversion(double x, double eps) // инверсия: поиск в окрестностях точки
{
static int sign = 0;
sign++;
sign %= 2;
if (sign == 0) return x - eps;
else return x + eps;
}
void crossover(double *x, double eps, double x0, double x1) // кроссовер: среднее арифметическое
{
int k = 99;
for (int i = 0; i < 8; i++)
for (int j = i + 1; j < 8; j++)
{
x[k] = (x[i] + x[j]) / 2;
k--;
}
for (int i = 0; i < 8; i++)
{
x[k] = inversion(x[i], eps); k--;
}
for (int i = 8; i < k; i++)
x[i] = mutation(x0, x1);
}
void sort(double *x, double *y) // сортировка
{
for (int i = 0; i < 100; i++)
for (int j = i + 1; j < 100; j++)
if (fabs(y[j]) < fabs(y[i])) {
double temp = y[i];
y[i] = y[j];
y[j] = temp;
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
double genetic(double x0, double x1, double eps) // поиск решения с использованием ГА
{
double population;
double f;
int iter = 0;
for (int i = 0; i < 100; i++) // Формирование начальной популяции
{
population[i] = mutation(x0, x1);
f[i] = func(population[i]);
}
sort(population, f);
do {
iter++;
crossover(population, eps, x0, x1);
for (int i = 0; i < 100; i++)
f[i] = func(population[i]);
sort(population, f);
} while (fabs(f) > eps && iter<20000);
cout << iter << " iterations" << endl;
return population;
}
int main()
{
srand(time(NULL ));
cout << genetic(1.0, 10.0, 0.000001);
cin.get();
return 0;
}

Результат выполнения

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