он следующим образом:
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. Инициировать начальный момент времени 0x01 graphic
. Случайным образом сформировать начальную популяцию, состоящую из k
особей.
0x01 graphic
2. Вычислить приспособленность каждой особи 0x01 graphic
и популяции в целом 0x01 graphic
(также иногда называемую термином фиттнес). Значение этой функции
определяет насколько хорошо подходит особь, описанная данной
хромосомой, для решения задачи.
3. Выбрать особь 0x01 graphic
из популяции. 0x01 graphic
4. С определенной вероятностью (вероятностью кроссовера 0x01 graphic
) выбрать вторую особь из популяции 0x01 graphic
и произвести оператор кроссовера 0x01 graphic
.
5. С определенной вероятностью (вероятностью мутации 0x01 graphic
) выполнить оператор мутации. 0x01 graphic
.
6. С определенной вероятностью (вероятностью инверсии 0x01 graphic
) выполнить оператор инверсии 0x01 graphic
.
7. Поместить полученную хромосому в новую популяцию 0x01 graphic
.
8. Выполнить операции, начиная с пункта 3, k раз.
9. Увеличить номер текущей эпохи 0x01 graphic
.
10. Если выполнилось условие останова, то завершить работу, иначе переход
на шаг 2.
Теперь рассмотрим подробнее отдельные этапы алгоритма.
Наибольшую роль в успешном функционировании алгоритма играет этап отбора
родительских хромосом на шагах 3 и 4. При этом возможны различные
варианты. Наиболее часто используется метод отбора, называемый рулеткой.
При использовании такого метода вероятность выбора хромосомы определяется
ее приспособленностью, то есть 0x01 graphic
. Использование этого метода приводит к тому, что вероятность передачи
признаков более приспособленными особями потомкам возрастает. Другой часто
используемый метод - турнирный отбор. Он заключается в том, что случайно
выбирается несколько особей из популяции (обычно 2) и победителем
выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых
реализациях алгоритма применяется так называемая стратегия элитизма,
которая заключается в том, что особи с наибольшей приспособленностью
гарантировано переходят в новую популяцию. Использование элитизма обычно
позволяет ускорить сходимость генетического алгоритма. Недостаток
использования стратегии элитизма в том, что повышается вероятность
попадания алгоритма в локальный минимум.
Другой важный момент - определение критериев останова. Обычно в качестве
них применяются или ограничение на максимальное число эпох
функционирования алгоритма, или определение его сходимости, обычно путем
сравнивания приспособленности популяции на нескольких эпохах и остановки
при стабилизации этого параметра.
3. Непрерывные генетические алгоритмы.
Фиксированная длина хромосомы и кодирование строк двоичным алфавитом
преобладали в теории генетических алгоритмов с момента начала ее развития,
когда были получены теоретические результаты о целесообразности
использования именно двоичного алфавита. К тому же, реализация такого
генетического алгоритма на ЭВМ была сравнительно легкой. Все же, небольшая
группа исследователей шла по пути применения в генетических алгоритмах
отличных от двоичных алфавитов для решения частных прикладных задач. Одной
из таких задач является нахождение решений, представленных в форме
вещественных чисел, что называется не иначе как «поисковая оптимизация в
непрерывных пространствах». Возникла следующая идея: решение в хромосоме
представлять напрямую в виде набора вещественных чисел. Естественно, что
потребовались специальные реализации биологических операторов. Такой тип
генетического алгоритма получил название непрерывного генетического
алгоритма (RGA, или real-coded genetic algorithm), или генетического
алгоритма с вещественным кодированием.
Первоначально непрерывные гены стали использоваться в специфических
приложениях (например, хемометрика, оптимальный подбор параметров
операторов стандартных генетических алгоритмов и др.). Позднее они
начинают применяться для решения других задач оптимизации в непрерывных
пространствах (работы исследователей Wright, Davis, Michalewicz, Eshelman,
Herrera в 1991-1995 гг). Поскольку до 1991 теоретических обоснований
работы непрерывных генетических алгоритмов не существовало, использование
этого нового подвида было спорным; ученые, знакомые с фундаментальной
теорией эволюционных вычислений, в которой было доказано превосходство
двоичного алфавита перед другими, критически воспринимали успехи
алгоритмов с вещественным кодированием. После того, как спустя некоторое
время теоретическое обоснование появилось, непрерывные генетические
алгоритмы полностью вытеснили двоичные хромосомы при поиске в непрерывных
пространствах.
Преимущества и недостатки двоичного кодирования
Прежде чем излагать особенности математического аппарата непрерывных
генетических алгоритмов, остановимся на анализе достоинств и недостатков
двоичной схем кодирования.
Как известно, высокая эффективность отыскания глобального минимума или
максимума генетическим алгоритмом с двоичным кодированием теоретически
обоснована в фундаментальной теореме генетических алгоритмов («теореме о
шаблоне»), доказанной Холландом. Ее суть в том, что двоичный алфавит
позволяет обрабатывать максимальное количество информации по сравнению с
другими схемами кодирования.
Однако двоичное представление хромосом влечет за собой определенные
трудности при поиске в непрерывных пространствах большой размерности, и
когда требуется высокая точность найденного решения. В генетических
алгоритмах с двоичным кодированием для преобразования генотипа в фенотип
используется специальный прием, основанный на том, что весь интервал
допустимых значений признака объекта 0x01 graphic
разбивается на участки с требуемой точностью. Заданная точность p
определяется выражением
0x01 graphic
где N - количество разрядов для кодирования битовой строки.
Эта формула показывает, что p сильно зависит от N, т.е. точность
представления определяется количеством разрядов, используемых для
кодирования одной хромосомы. Поэтому при увеличении N пространство поиска
расширяется и становится огромным.
Известный книжный пример: пусть для 100 переменных, изменяющихся в
интервале 0x01 graphic
, требуется найти экстремум с точностью до шестого знака после запятой. В
этом случае при использовании генетических алгоритмов с двоичным
кодированием длина строки составит 3000 элементов, а пространство поиска -
около 0x01 graphic
хромосом.
Эффективность генетических алгоритмов с двоичным кодированием в этом
случае будет невысокой. На первых итерациях алгоритм потратит много усилий
на оценку младших разрядов числа, закодированных во фрагменте двоичной
хромосомы. Но оптимальное значение на первых итерациях будет зависеть от
старших разрядов числа. Следовательно, пока в процессе эволюции алгоритм
не выйдет на значение старшего разряда в окрестности оптимума, операции с
младшими разрядами окажутся бесполезными. С другой стороны, когда это
произойдет, станут не нужны операции со старшими разрядами - необходимо
улучшать точность решения поиском в младших разрядах. Такое «идеальное»
