Учебное пособие по курсу интеллектуальные системы (Часть 1) Москва 2003

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

Генетические алгоритмы это алгоритмы, использующие методы "эволюционного вычисления". Эволюционное вычисление занимается решением проблем, используя приложения эволюционных механизмов. Эта область развилась из трех более или менее независимых разработок: генетических алгоритмов, эволюционного программирования и эволюционных стратегий. Весь три дисциплины начали изучаться в 60-х годах и 70-х годах (первые две в США, третья в Германии), но только в конце 80-х годов они начали признаваться. В настоящее время генетические алгоритмы рассматриваются как одни из наиболее успешных методов машинного обучения. По существу, они являются процедурами оптимизации, имитирующими при проектировании модели данных такие процессы, как генетическая рекомбинация, мутация и отбор, аналогичные тем, что обусловливают естественную эволюцию. Первые генетические алгоритмы были предложены в начале 70-х годов Джоном Холландом (John Holland) с целью имитации эволюционных процессов в живой природе [6]. Схему конструирования генетического алгоритма для решениЯ задач можно представить следующим образом:

1). разработайте хорошее кодирование задачи в терминах строк ограниченного алфавита;
2). постройте искусственную среду в компьютере, где решения могут конкурировать друг с другом. Обеспечьте объективную оценку успеха или неудачи, что в профессиональных терминах называется функцией пригодности;
3). разработайте способы, которыми возможные решения могут быть объединены. Здесь очень популярна так называемая операция скрещивания (кроссинговер), в который строки отца и матери просто отрезаются и после выделения отрезанные части объединяются вместе. При репродукции могут быть применены другие операторы, такие как операторы мутации, инверсии и т.д.;
4). введите хорошо изменяемую начальную популяцию и заставьте компьютер играть в "эволюцию", удаляя плохие решения из каждого поколения и заменяя их потомством или мутациями хороших решений;
5). остановитесь, когда будет порождено семейство успешных решений.
Схема достаточна проста, но успех будет зависеть, прежде всего, от адекватного задаче кодирования (так называемая техника представления) и нахождения эффективных операторов мутации.
Удачи и недостатки генетических алгоритмов частично сходны с таковыми при естественном отборе вообще. Двумя недостатками являются большое перепроизводство объектов и случайный характер процесса поиска. В общем случае требуется масса вычислительной мощности, чтобы достигнуть чего-нибудь значительного. С другой стороны, методика устойчива; если решение существует, то генетический алгоритм с большой вероятностью найдет его. Однако, в специфической проблемной области исследования операций, генетические алгоритмы часто не согласовываются с общепринятыми алгоритмами, их работоспособность главным образом является следствием их широкой применимости и концептуальной ясности. Вместе со своими родственниками, нейронными сетями, они являются ядром самообучающихся систем.
Решения, найденные генетическими алгоритмами закодированы символами и поэтому часто легко читаемы, что является преимуществом над нейронными сетями, в которых последняя функция просто является черным ящиком.
Генетические алгоритмы могут рассматриваться как вид мета обучающей стратегии, что означает, что генетический подход может использоваться параллельно с использованием почти любого другого обучающего механизма. За прошедшие несколько лет было разработано много гибридных приложений, в которых нейронные сети использовались, чтобы создать вход для генетических алгоритмов, или альтернативно генетические алгоритмы использовались, чтобы оптимизировать выход нейронной сети.
Предположим, что мы хотим обнаружить хорошее разбиение на группы нашей БД журналов, используя генетические алгоритмы. Первый шаг состоит в том, чтобы найти соответствующее кодирование задачи в терминах строк ограниченного алфавита, и один из способов состоит в том, чтобы описать разбиение как набор направляющих точек в пространстве, которое исследуется. На рис. 3.11 показано хорошее разбиение на группы пространства выборки в терминах пяти направляющих точек. Заметим, что в этих терминах решение состоит в том, чтобы оптимальным образом выбрать искомые пять направляющих точек. Первое поколение -это случайный выбор пяти направляющих точек, затем - вычисление функции пригодности, операции кроссовингера и мутации порождают второе поколение, далее опять вычисление функции пригодности, но уже для второго поколения и т.д. до получения решения с минимальной в нашем случае оценкой функции пригодности, т.е. по сути это оптимизационный метод.
Направляющие точки описывают кластерные области нашего пространства поиска, граница между двумя направляющими точками определяется эквидистантой обеих точек. Разбиение на различные области, которое следует из определения этих границ, называется диаграммой Вороного. Используя технику диаграмм Вороного, можно разделить пространство выборки на различные области в соответствии с множеством найденных направляющих точек. В этом случае имеем пять таких областей, которые дают грубую классификацию пространства выборки. Если бы использовалось большее количество направляющих точек, то, вероятно, получили бы лучшее разбиение пространства на подобласти.
В случае нашего алгоритма кластеризации в качестве кодирования для потенциального решения задачи можно выбрать строку, состоящую из координат пяти направляющих точек, Тогда объект (элемент) в пространстве поиска должен состоять из десяти вещественных чисел, описывающих координаты пяти точек.



Рис. 3.10. Диаграмма Вороного для базы данных о журналах.

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

На рис. 3.11 это множество начальных решений представляется как первое поколение. Следующее, что необходимо разработать - это хорошую функцию пригодности для объектов. В представленном случае это достаточно просто: берётся среднее расстояние от точек в пространстве выборки до ближайшей направляющей точки. Множество направляющих точек дадут лучшее разбиение, если среднее расстояние от всех точек до ближайшей направляющей точки минимально. На рис. 3.11 решения уже упорядочены согласно среднему расстоянию. Последнее, о чём необходимо позаботится, это определить хорошее скрещивание и хорошие мутационные связи. В нашем случае определить оператор кроссинговера также просто: берем три точки из одного объекта, две точки от другого объекта, переставляем их, и таким образом создаём два новых потомства от двух родителей. Мутация ещё проще: перемещаем случайным образом некоторые точки объекта в пространстве поиска. Используя операторы кроссинговера и мутации, можем создавать новые поколения решений нашей задачи. После определённого числа поколений, найдем устойчивое разбиение для пространства выборки, которое будет выглядеть примерно так, как показано на рис. 3.11. Этот пример показывает, как генетические алгоритмы могут использоваться для решения проблемы кластеризации (разбиения совокупности на группы).
В заключение раздела рассмотрим работу простого генетического алгоритма, впервые описанного Гольдбергом на основе работ Холланда [7,8]. Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ПГА случайно генерирует популяцию последовательностей – стрингов (хромосом). Затем ПГА применяет множество простых операций к начальной популяции и генерирует новые популяции.
ПГА состоит из трех операторов: репродукция, кроссинговер и мутация.
Под репродукцией понимается процесс, в котором хромосомы копируются согласно их целевыми функциями (в генетике – fitness- пригодность). Копирование хромосом с «лучшим» значением целевой функции имеет большую вероятность их попадания в следующую генерацию.

Рис. 3.11. Эволюция генетического алгоритма.
Таким образом, оператор репродукции (ОР) реализует стратегию натуральной селекции «выживание сильнейшего». ОР представляется в алгоритмической форме различными способами. Самый простой – создать колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное его целевой функцией.
Пусть необходимо максимизировать функцию f(x)=x² на целочисленном интервале [0, 31]. Для иллюстрации работы ПГА построим таблицу 3.1.

Таблица 3.1

Номер хромосом	Хромосома (двоичный код)	Десятич-ный код	ЦФ (fitness)	Значение ЦФ, в процентах
1	0 1 1 0 1	13	169	14.4
2	1 1 0 0 0	24	576	49.2
3	0 1 0 0 0	8	64	5.5
4	1 0 0 1 1	19	361	30.9

Хромосомы столбца 2 табл.3.1 сгенерированы случайным образом. Соответственно в табл. 3.1 суммарное значение целевой функции равно 1170.

Значение ЦФ для каждой хромосомы определим как возведенное в квадрат значение двоичного числа, которое кодирует хромосому в столбце 2 табл. 3.1. Для селекции хромосом используется механизм случайного поиска на основе колеса рулетки.
На рис. 3.12 поля колеса рулетки соответствуют значению целевой функции в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для следующего оператора. Очевидно, не всегда хромосома с большой ЦФ в результате действия оператора регенерации ОР будет выбрана для следующего оператора. Будем считать для упрощения, что 14,4=14; 49,2 = 49; 5,5 = 6; 30,9 = 31.

Рис.3.12. Колесо рулетки.

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

1  0 1 1 0 | 1 До применения оператора кроссинговера
2  1 1 0 0 | 0.
-----------------
1  0 1 1 0 | 0 После применения оператора кроссинговера
2  1 1 0 0 | 1.

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

Итак, согласно Холланду [8,9], одноточечный или простой ОК в технических системах выполняется в три этапа:

0. 
   Две структуры (хромосомы) А=а₁, а₂,.., а_L и B=a₁, a₂,.., a_L выбираются случайно из текущей популяции после ОР. Заметим, что этап 1 в некоторых случаях может выполняться и без ОР, т.е. непосредственно из начальной популяции.
   

1. 
   Число k выбирается из {1,2,...,L-1} также случайно. Здесь L- длина хромосомы, k- точка ОК.
   
2. 
   Две новые хромосомы формируется из А и В, заменяя множество элементов. В результате получим:
   

,
.
После применения ОК имеем две старые хромосомы и всегда получаем две новые хромосомы. Схематически простой ОК показывает преобразование двух хромосом и частичный обмен информации, используя точку пересечения, выбранную случайно. Например:
Перед ОК  После ОК
хромосома 1  1 1 1| 1 1 1 1 1 0 0 новая хромосома 1
хромосома 2  0 0 0| 0 0 0 0 0 1 1 новая хромосома 2.
Механизм ОР и ОК удивительно прост. Он включает случайную генерацию чисел, копирование хромосом и частичный обмен частей хромосом. Гольдберг отмечает: «Сначала это кажется удивительным: как два простых оператора могут образовывать мощный поисковый механизм?»