Классический генетический алгоритм. Основоположником современной теории генетических алгоритмов (ГА) считается Холланд (J

Основоположником современной теории генетических алгоритмов (ГА) считается Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems» (1975) стала классикой в этой области. В ней Холланд впервые ввел термин «генетический алгоритм». Сейчас описанный там алгоритм называют «классический», иногда «канонический» ГА, а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА. Ученики Холланда Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David E. Goldberg) внесли огромный вклад в развитие ГА. На книгу Голдберга «Genetic algorithms in search optimization and machine learning» (1989), ссылаются авторы практически каждой работы по этой теме.

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

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

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

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

y(x) = 5 − 24x + 17x²− 11x³/3+ x⁴/4 на отрезке [0; 7] (рис. 1).

На этом отрезке функция принимает минимальное значение в точке x = 1. В точке x = 6 функция попадает в локальный минимум. Если для нахождения глобального минимума использовать градиентные методы, то в зависимости от начального приближения можно попасть в данный локальный минимум.

Для простоты положим, что x принимает лишь целые значения, т.е. x ∈ {0, 1, 2, 3, 4, 5, 6, 7}. Это предположение существенно упростит изложение, сохранив все основные особенности работы генетического алгоритма. Выберем случайным образом несколько чисел на отрезке [0; 7]: Числа {2, 3, 5, 4} будем рассматривать в качестве пробных решений нашей задачи. (В эволюции это называется выбор популяции)

Основной идеей генетических алгоритмов является организация «борьбы за существование» и «естественного отбора» среди пробных решений. Запишем выбранные пробные решения в двоичной форме: {010, 011, 101, 100} (кодировка).

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

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

Для этого сформируем из исходной популяции брачные пары для скрещивания, поставив в соответствие каждой особи исходной популяции случайное целое число из диапазона от 1 до 4, которое будем рассматривать как номера членов популяции (табл.2). Процесс размножения (рекомбинация) заключается в обмене участками хромосом между родителями. Например, пусть скрещиваются две хромосомы 111111 и 000000. Определяем случайным образом точку разрыва хромосомы, пусть, это будет 3: 111|111, 000|000. Теперь хромосомы обмениваются частями, стоящими после точки разрыва, и образуют двух новых потомков: 111000 и 000111. Определение места разрыва хромосом называется кроссинговером.

Для нашей популяции процесс создания первого поколения потомков показан в таблице 2 (скрещиваются 1-4, 3-1, остальные варианты не рассматриваем).

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

Случайность будем моделировать колесом рулетки. Пусть вероятность мутации равна 0,3. Для каждого потомка возьмем случайное число на отрезке [0; 1], и если это число меньше 0,3, то инвертируем случайно выбранный ген (заменим 0 на 1 или наоборот) (табл. 3). Как видно, мутации способны улучшить (первый потомок) или ухудшить (четвертый потомок) приспособленность особи-потомка. Если в результате скрещивания хромосомы обмениваются «хвостами», т.е. младшими разрядами в двоичном представлении числа, то в результате мутаций изменению может подвергнуться любой разряд, в том числе, старший. Таким образом, если скрещивание приводит к относительно небольшим изменениям пробных решений, то мутации могут привести к существенным изменениям значений пробных решений (табл. 3).

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

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

Значение приспособленности наиболее «хорошей» особи (или средняя приспособленность по популяции) и будет являться решением нашей задачи. Следуя этому, в данном случае, взяв наиболее приспособленную особь 001 во втором поколении, можно сказать, что минимумом целевой функции является значение −5,42, соответствующее аргументу x = 1. Тем самым попадания в локальный минимум удалось избежать!

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

Итак, основные принципы работы ГА заключены в следующей схеме:

1. Производится инициализация начального поколения. Генерируем начальную популяцию из n хромосом.

2. Вычисляем для каждой хромосомы ее пригодность.

3. Выбираем пару хромосом-родителей с помощью одного из способов

отбора.

4. Проводим кроссинговер двух родителей с вероятностью p с, производя двух потомков.

5. Проводим мутацию потомков с вероятностью p m.

6. Повторяем шаги 3–5, пока не будет сгенерировано новое поколение популяции, содержащее n хромосом

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

8. Повторяем шаги 2–6, пока не будет достигнут критерий окончания процесса.

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

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

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

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

2-x битный код Грея: 00, 01, 11,10 3-x битный код Грея: 000, 001, 011, 010, 110, 111, 101, 100.

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

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

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

· нахождение глобального, либо субоптимального решения;

· исчерпание числа поколений, отпущенных на эволюцию;

· исчерпание времени, отпущенного на эволюцию.

Кроссинговер. Операция рекомбинации хромосом на основе кроссинговера (хромосомы скрещиваются, обмениваясь частями строк), осуществляемого с вероятностью Р_КР, относится к схеме одноточечного кроссинговера. Обычно на практике применяется Ркр= 0,6.

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

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

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

Островная модель ГА

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