Лекция: Генетический алгоритм.
В основе генетических алгоритмов лежат генетика и хромосомная теория эволюции организмов. Хромосомы — это нитевидные структуры, находящиеся в клеточном ядре, которые являются носителями наследственности. Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает). Каждый биологический вид имеет определенное, постоянное количество хромосом. Каждая клетка содержит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится 23 пары хромосом, в клетках комара — 3.
Классическая генетика обосновала наследственность и изменчивость благодаря созданию фундаментальной теории гена, основные положения которой формулируются следующим образом:
. все признаки организма определяются наборами генов;
. гены — это элементарные единицы наследственной информации, которые находятся в хромосомах;
. гены могут изменяться — мутировать;
. мутации отдельных генов приводят к изменению отдельных элементарных признаков организма, или фенов.
Ген определяется как структурная единица наследственной информации, далее неделимая в функциональном отношении. Он представляет собой участок молекулы ДНК, на котором сохраняется постоянный порядок следования пар нуклеотидов. Комплекс генов, содержащихся в наборе хромосом одного организма, образует геном. Роль молекул ДНК, обладающих уникальной способностью к самовоспроизведению, заключается в хранении и передаче генетической информации последующим поколениям.
В задачах поиска оптимальных решений каждое решение из множества возможных можно представить набором информации, который может быть изменен путем введения в него элементов другого решения. Другими словами, возможные решения соответствуют хромосомам, состоящим из генов, причем в ходе оптимизации происходит обмен генами между хромосомами (рекомбинация). При построении генетических алгоритмов важен выбор принципа генетической рекомбинации. Существует несколько типов перераспределения наследственных факторов:
1) рекомбинация хромосомных и нехромосомных генов;
2) рекомбинация целевых неroмологических хромосом;
3) рекомбинация участков хромосом, представленных непрерывными молекулами ДНК
Для построения генетических алгоритмов наибольший интерес представляет третий тип рекомбинации, который используется для накопления в конечном решении лучших функциональных признаков, какие имелись в наборе исходных решений. Существует несколько типов рекомбинации участков хромосом: кроссинговер, сайт, иллегальная рекомбинация.
Кроссинговер соответствует регулярной рекомбинации, при которой происходит обмен определенными участками между гомологичными
хромосомами. Он приводит к появлению нового сочетания сцепленных генов.
Caйт — это вид рекомбинации, при которой на коротких специализироанных участках хромосом происходит обмен генофоров (генных носителей), часто различных по объему и составу генетической информации.
Иллегальная рекомбинация допускает негомологичные обмены, к которым относятся транслокации, инверсии и случаи неравного кроссинговера. Такие способы могут оказаться полезными при генерации новых решений.
В генетических алгоритмах наибольшее распространение получила операция кроссинговера, заключающаяся в разрыве гомологичных хроматид с последующим соединением их в новом сочетании. Схема кроссинговера, демонстрирующая образование двух новых хромосом после обмена генетическим материалом, приведена на рис. 10.33.
Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков в одном решении.
А х
В х
а
А1
В1
б
Рис. 10.33. Схема кроссинговера:
а — родительские хромосомы А, Вдо кроссинroвера; б — хромосомы-потомки А1, В1 после кроссинговера
Кроссинговер может происходить в нескольких точках. Пример двойного кроссинговера между хромосомами f и w приведен рис. 10.34.
Рис. 10.34. Схема двойного кроссинговера: а — до кроссинговера; б — во время кроссинговера; в — после кроссинговера
Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как мутация, инверсия, транслокация, селекция (инбридинг и гибридизация), генная инженерия.
Под мутациейпонимается генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или линейности. Свойство дискретности позволяет выделить в исходном генетическом материале отдельные фрагменты, контролирующие те или иные функции. Непрерывность означает, что определенные комбинации генов совместно контролируют некоторую функцию. Линейность проявляется в определенной последовательности генов в пределах группы сцепления.
Процессы мутации ведут к получению более разнообразного генетического материала. В связи с этим применение операции мутации в генетических алгоритмах направлено на получение решений, которые не могут быть улучшены качественно посредством кроссинговера.
Инверсия, транслокация, транспозиция, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсииучасток хромосомы поворачивается на 1800. Транслокациейназывают перенос части одной хромосомы в дрyгyю. При перемещении небольших участков генетического материала в пределах хромосомы используют термин транспозиция. Делеция – это выпадение отдельных участков хромосом, дупликация - повторение участков генетического материала.
Селекцияпредставляет собой форму искусственного отбора, который может быть массовым или индивидуальным. Установлено, что массовый отбор по фенотипу (совокупности всех внешних и внутренних признаков) менее эффективен, чем индивидуальный, когда популяцию делят на отдельные линии, а для размножения выбирают носителей желаемых свойств. Применение процедуры селекции в генетических алгоритмах оптимизации способствует ускорению процесса синтеза искомого решения.
Генная инженерияпредставляет собой совокупность методов для получения рекомбинантной ДНК и операции над нею. Рекомбинантная ДНК получается путем объединения фрагментов ДНК различных организмов. Использование подходов генной инженерии позволяет в ряде задач значительно быстрее находить желаемое решение.
Механизм эволюции основан на трех повторяющихся процессах: отборе, амплификации (процесс производства потомков) и мутации. Он используется в качестве механизма случайно направленного комбинаторного перебора при решении задач оптимизации и слабоструктурированных проблем принятия решений.
Генетический алгоритм — это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы, обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции.
В генетических алгоритмах используются специфические термины, взятые из генетики, которые трактуются следующим образом (Табл. 10.5).
Понятие генетики. | Понятие генетического алгоритма. |
Хромосома | Решение, стринг, строка, последовательность, родитель, потомок |
Популяция | Набор решений (хромосом) |
Локус | Местоположение гена в хромосоме |
Поколение | Цикл работы генетического алгоритма, в процессе которого сгенерировано множество решений |
Ген | Элемент, характеристика, особенная черта, свойство, детектор |
Аллель | Значение элемента, характеристики |
Фенотип | Структура |
Эпистасис | Множество параметров, альтернативные решения |
Скрещивание, рекомбинация, кроссинговер | Оператор рекомбинации |
Мутация | Оператор модификации |
Таблица 10.5. Соответствие понятий генетики генетическим алгоритмам.
При разработке генетических алгоритмов преследуются две главные цели:
. абстрактное и формальное объяснение процессов адаптации в естественных системах;
. проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.
Основные отличия ГА от других алгоритмов оптимизации:
. используются не параметры, а закодированные множества параметров;
. поиск осуществляется не из единственной точки, а из популяции точек;
. в процессе поиска используются значения целевой функции, а не ее приращения;
. применяются вероятностные, а не детерминированные правила поиска и генерации решений;
. выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.
Согласно репродуктивному плану Холланда [14, 26] генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции рис. 10.35:
Рис. 10.35. Простой генетический алгоритм.
1, Конструируется начальная популяция. Вводится начальная точка отсчета поколений t=0. Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособJI«IIIIOC'I'!> всей популяции.
2. Устанавливается значение t = t + 1. Выбираются два родителя (хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.
3. Формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков A(t), который сохраняется как член новой популяции. Далее к потомку A(t)последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как A'(t).
4. Обновление текущей популяции путем замены случайно выбранной хромосомы на A'(t).
5. Определение приспособленности A'(t) и пересчет средней приспособленности популяции.
6. Если t= tк, где tк– конечное число шагов, то переход к этапу 7, в противном случае — переход к этапу 2.
7. Конец работы.
Основная идея эволюции, заложенная в различные конструкции генетических алгоритмов, проявляется в способности «лучших» хромосом оказывать большее влияние на состав новой популяции за счет длительного выживания и более многочисленного потомства.
Простой генетический алгоритм включает операцию случайной генерации начальной популяции хромосом и ряд операторов, обеспечивающих генерацию новых популяций на основе начальной. Этими операторами являются репродукция, кроссинговер и мутация.
Репродукциейназывается процесс копирования хромосом с учетом значений целевой функции, т.е. хромосомы с «лучшими» значениями целевой функции имеют большую вероятность попадания в следующую популяцию. Этот процесс является аналогией митозного деления клеток. Выбор клеток (хромосом) для репродукции проводится в соответствии принципом «выживания сильнейшего». Простейшим способом представления операции репродукции в алгоритмической форме является колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное значению целевой функции.
Рассмотрим пример применения простого генетического алгоритма для максимизации функции f(x)=x2на целочисленном интервале [0,31] .(Пример взят из монографии В.М. Курейчика «Генетические алгоритмы».)
Значения аргумента функции f(x)=x2, изменяющегося в интервале от 0 до 31, можно представить пятиразрядными двоичными числами. Первоначальная популяция, состоящая из четырех строк пятиразрядных чисел, полученная с помощью процедуры генерации случайных чисел, приведена во втором столбце табл. 10.6. Значение целевой функции для каждой хромосомы
Таблица 10.6.