Кодирование в генетических алгоритмах. Генетические операторы

Подчеркнем еще раз различие между фенотипом и генотипом. Из

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

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

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

Для многих задач, встречающихся в современных проблемах,

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

– бинарное кодирование;

– кодирование действительными числами;

– целочисленное кодирование;

– кодирование общей структуры данных.

Более подробно рассмотрим бинарное кодирование, которое используется в классическом подходе Д. Холланда. Пусть вектор допустимого решения х_ _D, где D – область поиска решений. Каждый компонент вектора x_ _ (x1,x2,...,xn) можно закодировать с помощью целого неотрицательного числа _i __0,Ki _, i _ 1,n; (Ki – число возможных дискретных значений i"й переменной).

Введем бинарный алфавит B2 = {0;1}. Для представления целочисленного вектора _!= (_1,…,_n) в алфавите B2 необходимо определить максимальное число двоичных символов _, которое достаточно для отображения в двоичном коде любого значения _i из области его допустимых значений [0,Ki].

В соответствии с кодированием общей структуры данных методы

кодирования могут быть разделены на два вида:

– одномерный;

– многомерный.

В большинстве случаев используется одномерное кодирование,

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

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

кодирования и решения, другими словами, пространствах генотипа

и фенотипа. Генетические операторы работают в пространстве генотипов, а оценка и отбор происходят в фенотипическом пространстве.

Естественный отбор – это связь между хромосомами и поведением

декодированных решений.

Отображение из генотипического пространства в фенотипическое

оказывает значительное влияние на поведение ГА. Одна из главных

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

– недопустимость;

– незаконность.

Генетические операторы.

Определены три основных вида генетических операторов:

– селекция;

– скрещивание;

– мутация.

Перед тем как непосредственно перейти к изучению этих операторов, остановимся подробнее на концепции поиска и его применении в ГА.

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

– случайный;

– локальный.

Случайный поиск исследует решение целиком и способен избежать

попадания в локальный оптимум. Локальный поиск использует лучшее решение и способен подняться вверх к локальному оптимуму.

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

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

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

Есть две гипотезы объяснения того, как ГА используют распределенную информацию для формирования хороших решений:

– гипотеза строительных блоков;

– гипотеза изменения управляемой сходимости.

Согласно первой гипотезе скрещивание комбинирует признаки от

двух родителей для производства потомства. Иногда скрещивание

использует лучшие признаки от обоих родителей, формируя очень

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

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

Основной принцип генетических алгоритмов, по существу, представляет собой дарвиновский естественный отбор. Селекция обеспечивает движущую силу в ГА. Чем больше эта сила, тем быстрее может завершиться генетический поиск; при меньшей величине этой силы эволюционный процесс будет медленнее, чем необходимо. Селекция направляет генетический поиск в «обещающие» районы поискового пространства. Основной компонент ГА – это метод, используемый для перехода от одной генерации к следующей. Существует много возможных вариаций относительно выбора потенциальных родителей и способа их комбинирования для воспроизводства потомства. Селекция может меняться от очень трудоемких подходов, требующих значительных усилий, до очень легких схем. В течение последних 20 лет были предложены многие методы, среди которых наибольшее распространение получили следующие:

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

В качестве очень упрощенного примера рассмотрим популяцию из 10 индивидуумов. Пусть эта популяция содержит шесть идентичных хромосом, которые обозначим как тип A и четыре идентичных хромосомы типа B. Допустим, что тип A имеет величину пригодности, равную 12, а тип B – 7. Общая пригодность составит величину:

6·12 + 4·7 = 100.

Тип A занимает 72% общей пригодности, а тип B – 28%. При таких входных данных «конструируем» рулетку, 72% площади которой обозначим меткой A, а 28% – меткой B. Для выбора следующей популяции даем рулетке только 10 оборотов (таков размер популяции) и создаем новую комбинацию из типов A и B. В созданной новой генерации будет содержаться, в среднем, около семи (основанном на 72%) членов типа A и трех (основанном на 28%) членов типа B. Поскольку вращение колеса рулетки и момент его остановки случайны (в компьютерной реализации используется случайный цифровой генератор), то действительное разделение между A и B может быть и 0 / 10, и 10 / 0, однако в среднем этот метод дает высокие значения пригодности.

Стохастическая остаточная селекция. Рассмотрим, как и выше, десятичленную популяцию типов A и B. Ожидаемое число копий типа

A есть 7,2, а для типа B – это число составит 2,8. В этом методе селекции вначале концентрируемся на целых частях ожидаемых величин: 7 и 2. Семь копий типа A размещаются в следующей генерации так же, как и две копии типа B. Для определения идентичности 10"го члена остатки используются для «взвешивания» колеса рулетки. Здесь B получает 80% всего веса, а тип A – только 20%. Этот метод будет давать вклад в новую генерацию в соотношении 7/3 или 8/2 между типами A и B.

Стохастическая универсальная селекция. Этот метод – еще одна вариация предыдущих двух, но требует немного большего воображения для его реализации. Представим то же самое колесо рулетки, 72% площади которой отмечено как A, а 28% – как B. Дополним это колесо внешним кольцом из 10 равных интервалов (маркеров). Колесо рулетки делает один оборот. Для определения состава следующей генерации рассматриваются 10 маркеров: те, которые находятся напротив площади A, помечаются как тип A; то же самое относится и к B. Этот метод будет давать результаты, похожие на предыдущий случай: разделение в этом случае составит или 7/3, или 8/2.

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

Ранжированная селекция. Эта процедура начинается с ранжирования популяции по величине пригодности. Далее вводится функция присваивания, которая дает каждой хромосоме вероятность включения в следующую генерацию. Хромосомы с более высоким рангом имеют большую вероятность включения. Функция присваивания может быть линейной или нелинейной (чаще – последняя). Колесо рулетки строится со слотами, определяемыми функцией присваивания. Последующая генерация n"размерной популяции определяется после n вращений колеса. Эта процедура продвигает селекцию к членам популяции, обладающими лучшими характеристиками.

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

Кроме указанных способов селекции, существуют так называемые

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

Наиболее часто используется процедура сохранения одной лучшей

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

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

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

– ген из отцовской хромосомы переходит в материнскую хромосому;

– ген из материнской хромосомы переходит в отцовскую хромосому;

– происходит взаимный обмен генами между материнской и отцовской хромосомами;

– отцовская и материнская хромосомы остаются без изменения.

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

Заключительным этапом размножения особей является акт мейоза,

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

зиготы путем независимого расхождения гомологичных хромосом по

дочерним гаметам, воспроизводящим потомство. Процесс размножения

двух особей должен удовлетворять первому и второму законам наследственности Менделя, которые формулируются следующим образом:

– два гена, определяющие тот или иной признак, не сливаются и

не растворяются один в другом, но остаются независимыми друг от

друга, расщепляясь при формировании гамет;

– родительские гены, определяющие различные признаки, наследуются независимо друг от друга.

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

В соответствии со вторым законом рекомбинация (обмен) генов в

акте сигнамии может происходить либо в каком"то одном аллельном

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

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

1. Из популяции случайно выбираются два потенциальных родителя.

2. Выполняется жеребьевка (компьютерная) для определения –

проводить или не проводить скрещивание.

3. При положительном варианте ответа на предыдущем шаге случайно выбирается точка расщепления.

4. Каждая исходная родительская строка перерезается в точке

расщепления.

5. Производится обмен генетическим материалом слева и справа

от точки расщепления и соединение полученных строк для формирования потомства.

Подводя итог рассмотрению оператора скрещивания, отметим, что

скрещиванию подвергается не вся популяция строк, а только ее часть,

определяемая вероятностью скрещивания (например, рскр = 0,6 означает, что лишь 60% строк из популяции будут образовывать родительские пары.

Мутация. При скрещивании генотипы потомков содержат новые

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

Процесс изменения содержания генов в хромосоме путем мутации

называется мутагенезом. Самое главное заключается в том, что этот

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

Мутации происходят независимо от того, приносят ли они особи

вред или пользу. Они не направлены на повышение или понижение

степени приспособленности особи, а только производят структурные

изменения в аллельных формах генов, что приводит к изменению

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