кр. Ю. Ю. Громов, О. Г. Иванова, В. В. Алексеев, М. П. Беляев, Д. П. Швец, аи. Елисеев интеллектуальные информационные системы и технологии
 Скачать 2.03 Mb.
|
|
3. ЭВОЛЮЦИОННЫЕ АНАЛОГИИ В ИСКУССТВЕННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ Эволюционное моделирование можно определить как воспроизведение процесса естественной эволюции с помощью специальных компьютерных программ. Термин эволюция в ограниченном смысле, касающемся только смены поколений организмов, начал широко использоваться в XVII в. С появлением в 1859 г. учения Дарвина этот термин приобрёл современное толкование Биологическая эволюция – историческое развитие организмов. Необходимые и достаточные условия, определяющие главные факторы эволюции, были сформулированы в XX в. на основе созданной популяционно-генетической теории. К факторам, определяющим неизбежность эволюции, относятся наследственная изменчивость как предпосылка эволюции, её материал борьба за существование как контролирующий и направляющий фактор естественный отбор как преобразующий фактор. На рисунке 3.1 приведена конкретизация факторов эволюции, учитывающая многообразие форм их проявления, взаимосвязей и взаимовлияния [11]. Главные факторы выделены пунктиром. Современная теория эволюции базируется на теории общей и популяционной генетики. Элементарным объектом эволюции является 57 популяция – сообщество свободно скрещивающихся особей. В популяциях происходят микроэволюционные процессы, приводящие к изменению их генофонда. Преобразования генетического состава популяции происходят под действием элементарных эволюционных факторов. Случайные структурные или функциональные изменения в генах, хромосомах и других воспроизводимых единицах называют мутациями, если они приводят к наследственному изменению какого-либо фе- нотипического признака особи. Хромосомы – это специфические структуры клеточного ядра, которые играют важнейшую роль в процессах деления клеток. Хромосомы состоят из генов. Геном называется реально существующая, независимая, комбинирующаяся и расщепляющаяся при скрещиваниях единица наследственности. Преобразования генофонда популяции происходят под управлением естественного отбора. Эволюция – это многоэтапный процесс возникновения органических форм с более высокой степенью организации, который характеризуется изменчивостью самих эволюционных механизмов. История эволюционных вычислений началась с разработки ряда независимых моделей, среди которых были генетические алгоритмы и классификационные системы, созданные американским исследователем Дж. Холландом. Он предложил использовать методы и модели развития органического мира на Земле в качестве механизма комбинаторного пе- Рис. 3.1. Схема взаимодействия факторов эволюции 58 ребора вариантов при решении оптимизационных задач [14, 26]. Компьютерные реализации этого механизма получили название генетические алгоритмы. В х гг. в рамках теории случайного поиска Л.А. Растригиным был предложен ряд алгоритмов, использующих идеи бионического поведения особей [10]. Развитие этих идей нашло отражение в цикле работ ИЛ. Букатовой по эволюционному моделированию. Идеи МЛ. Цетлина, развитые в исследованиях поведения сообществ конечных автоматов, легли в основу алгоритмов поиска глобального экстремума, основанных на моделировании процессов развития и элиминации особей [15]. Большой вклад в развитие эволюционного программирования внесли работы Л. Фогеля, А. Оуэнса и М. Уолша [12, 20, 21]. К основным направлениям развития эволюционного моделирования на современном этапе относятся следующие генетические алгоритмы (ГА, предназначенные для оптимизации функций дискретных переменных и использующие аналогии естественных процессов рекомбинации и селекции классифицирующие системы (КС), созданные на основе генетических алгоритмов, которые используются как обучаемые системы управления генетическое программирование (ГП), основанное на использовании эволюционных методов для оптимизации создаваемых компьютерных программ эволюционное программирование (ЭП), ориентированное на оптимизацию непрерывных функций без использования рекомбинаций; эволюционные стратегии (ЭвС), ориентированные на оптимизацию непрерывных функций с использованием рекомбинаций. Эволюционные методы целесообразно использовать в тех случаях, когда прикладную задачу сложно сформулировать в виде, позволяющем найти аналитическое решение, или тогда, когда требуется быстро найти приближенный результат, например, при управлении системами в реальном времени. В России развитием эволюционных методов занимаются научные школы профессоров ИЛ. Букатовой [2, 3], Д.И. Батищева [1], В.М. Ку- рейчика [7 – 9] и И.П. Норенкова [6] . 3.1. Генетические алгоритмы В основе генетических алгоритмов лежат генетика и хромосомная теория эволюции организмов. Хромосомы – это нитевидные структуры, находящиеся в клеточном ядре, которые являются носителями наследственности. Каждая хромосома уникальна морфологически иге нетически и не может быть заменена другой либо восстановлена при утере (при потере хромосомы клетка, как правило, погибает. Каждый биологический вид имеет определённое, постоянное количество хромосом. Каждая клетка содержит удвоенный набор морфологически и генетически сходных хромосом. Например, в клетках человека содержится пары хромосом, в клетках комара – 3. На процесс наследования признаков существенно влияет поведение хромосом при делении клеток. Существует митозное и мейозное деление клеток. Митозное деление обеспечивает распределение исходных хромосом между двумя образующимися дочерними клетками, которые будут иметь равноценные наборы хромосом и будут очень похожи друг на друга. При этом происходит редупликация исходных хромосом, вследствие чего к моменту деления клетки каждая хромосома состоит из двух копий исходной материнской хромосомы – сестринских хроматид (рис. 3.2). Вовремя мейоза происходит два последовательных деления редукционное и эквационное. Мейоз приводит к образованию клеток, у которых число хромосом вдвое меньше по сравнению с исходной клеткой. В фазе редукции хроматиды обмениваются генами, те. участками дезоксирибонуклеиновой кислоты (ДНК. После этого клетка разделяется на две новые, причём каждая из них содержит удвоенный набор хромосом, структуры которых отличаются от исходных. Механизм обмена генами называется кроссинговером. В результате эквационного деления из двух получившихся клеток образуются четыре клетки, каждая из которых содержит одиночный набор хромосом (рис. 3.2). Таким образом, митоз обеспечивает возобновление клеток, а мейоз отвечает за передачу наследственной информации и способствует генетическому разнообразию организмов данного вида. Классическая генетика обосновала наследственность и изменчивость благодаря созданию фундаментальной теории гена, основные положения которой формулируются следующим образом все признаки организма определяются наборами генов гены – это элементарные единицы наследственной информации, которые находятся в хромосомах гены могут изменяться – мутировать мутации отдельных генов приводят к изменению отдельных элементарных признаков организма, или фенов. Ген определяется как структурная единица наследственной информации, далее неделимая в функциональном отношении. Он представляет собой участок молекулы ДНК, на котором сохраняется постоянный порядок следования пар нуклеотидов. Комплекс генов, содержащихся в наборе хромосом одного организма, образует геном. Роль молекул ДНК, обладающих уникальной способностью к самовоспроизведению, заключается в хранении и передаче генетической информации последующим поколениям. Рис. 3.2. Механизмы деления клеток 61 В задачах поиска оптимальных решений каждое решение из множества возможных можно представить набором информации, который может быть изменён путём введения в него элементов другого решения. Другими словами, возможные решения соответствуют хромосомам, состоящим из генов, причём входе оптимизации происходит обмен генами между хромосомами (рекомбинация. При построении генетических алгоритмов важен выбор принципа генетической рекомбинации. Существует несколько типов перераспределения наследственных факторов 1) рекомбинация хромосомных и нехромосомных генов 2) рекомбинация целевых негомологических хромосом 3) рекомбинация участков хромосом, представленных непрерывными молекулами ДНК. Для построения генетических алгоритмов наибольший интерес представляет третий тип рекомбинации, который используется для накопления в конечном решении лучших функциональных признаков, какие имелись в наборе исходных решений. Существует несколько типов рекомбинации участков хромосом кроссинговер, сайт, иллегаль- ная рекомбинация. Кроссинговер соответствует регулярной рекомбинации, при которой происходит обмен определёнными участками между гомологичными хромосомами. Он приводит к появлению нового сочетания сцепленных генов. Сайт – это вид рекомбинации, при которой на коротких специализированных участках хромосом происходит обмен генофоров (генных носителей, часто различных по объёму и составу генетической информации. Иллегальная рекомбинация допускает негомологичные обмены, к которым относятся транслокации, инверсии и случаи неравного кроссинговера. Такие способы могут оказаться полезными при генерации новых решений. В генетических алгоритмах наибольшее распространение получила операция кроссинговера, заключающаяся в разрыве гомологичных хроматид с последующим соединением их в новом сочетании. Схема кроссинговера, демонстрирующая образование двух новых хромосом после обмена генетическим материалом, приведена на рис. 3.3. Основная цель кроссинговера заключается в создании из имеющегося генетического материала желаемой комбинации признаков водном решении. Кроссинговер может происходить в нескольких точках. Пример двойного кроссинговера между хромосомами приведён на рис. 3.4. 62 Рис. 3.3. Схема кроссинговера а – родительские хромосомы А, В до кроссинговера б – хромосомы-потомки А, В после кроссинговера Рис. 3.4. Схема двойного кроссинговера а – до кроссинговера б – вовремя кроссинговера в – после кроссинговера Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как мутация, инверсия, транслокация, селекция (инбридинг и гибридизация, генная инженерия. Под мутацией понимается генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала дискретности, непрерывности или линейности. Свойство дис- а) баб) в) x x B А А W f f 63 кретности позволяет выделить в исходном генетическом материале отдельные фрагменты, контролирующие те или иные функции. Непрерывность означает, что определённые комбинации генов совместно контролируют некоторую функцию. Линейность проявляется в опре- делённой последовательности генов в пределах группы сцепления. Процессы мутации ведут к получению более разнообразного генетического материала. В связи с этим применение операции мутации в генетических алгоритмах направлено на получение решений, которые не могут быть улучшены качественно посредством кроссинговера. Инверсия, транслокация, транспозиция, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокацией называют перенос части одной хромосомы в другую. При перемещении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция – это выпадение отдельных участков хромосом, дупликация – повторение участка генетического материала. Кроме перечисленных, существуют другие разновидности хромосомных мутаций [7]. Селекция представляет собой форму искусственного отбора, который может быть массовым или индивидуальным. Установлено, что массовый отбор по фенотипу (совокупности всех внешних и внутренних признаков) менее эффективен, чем индивидуальный, когда популяцию делят на отдельные линии, а для размножения выбирают носителей желаемых свойств. Применение процедуры селекции в генетических алгоритмах оптимизации способствует ускорению процесса синтеза искомого решения. Генная инженерия представляет собой совокупность методов для получения рекомбинантной ДНК и операции над нею. Рекомбинантная ДНК получается путём объединения фрагментов ДНК различных организмов. Использование подходов генной инженерии позволяет в ряде задач значительно быстрее находить желаемое решение. Механизм эволюции основан натр х повторяющихся процессах отборе, амплификации (процесс производства потомков) и мутации. Он используется в качестве механизма случайно направленного комбинаторного перебора при решении задач оптимизации и слабострук- турированных проблем принятия решений. Генетический алгоритм – это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенериро- ванных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы, обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции [2, 3, 7, 8, 16, 22 – 26]. В генетических алгоритмах используются специфические термины, взятые из генетики, которые трактуются следующим образом Генетика Генетические алгоритмы Хромосома Решение, стринг, строка, последовательность, родитель, потомок Популяция Набор решений (хромосом) Локус Местоположение гена в хромосоме Поколение Цикл работы генетического алгоритма, в процессе которого сгенерировано множество решений Ген Элемент, характеристика, особенная черта, свойство, детектор Аллель Значение элемента, характеристики Фенотип Структура Эпистасис Множество параметров, альтернативные решения Скрещивание, рекомбинация, кроссинговер Оператор рекомбинации Мутация Оператор модификации При разработке генетических алгоритмов преследуются две главные цели абстрактное и формальное объяснение процессов адаптации в естественных системах проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем. Основные отличия ГА от других алгоритмов оптимизации используются не параметры, а закодированные множества параметров поиск осуществляется не из единственной точки, а из популяции точек 65 в процессе поиска используются значения целевой функции, а нее приращения применяются вероятностные, а не детерминированные правила поиска и генерации решений выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счёт объединения ква- зиоптимальных решений из разных популяций. Согласно репродуктивному плану Холланда [14, 26] генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции 1. Конструируется начальная популяция. Вводится начальная точка отсчёта поколений t = 0. Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции. 2. Устанавливается значение t = t + 1. Выбираются два родителя хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции. 3. Формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков A(t), который сохраняется как член новой популяции. Далее к потомку A(t) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как A'(t). 4. Обновление текущей популяции путём замены случайно выбранной хромосомы A'(t). 5. Определение приспособленности A'(t) и пересчёт средней приспособленности популяции. 6. Если t = t*, где t* – заданное число шагов, то переход к этапу, в противном случае – переход к этапу 2. 7. Конец работы. Основная идея эволюции, заложенная в различные конструкции генетических алгоритмов, проявляется в способности лучших хромосом оказывать большее влияние на состав новой популяции за счёт длительного выживания и более многочисленного потомства. Простой генетический алгоритм [23, 26] включает операцию случайной генерации начальной популяции хромосом и ряд операторов, обеспечивающих генерацию новых популяций на основе начальной. Этими операторами являются репродукция, кроссинговер и мутация. 66 Репродукцией называется процесс копирования хромосом с уч- том значений целевой функции, те. хромосомы с лучшими значениями целевой функции имеют большую вероятность попадания в следующую популяцию. Этот процесс является аналогией митозного деления клеток. Выбор клеток (хромосом) для репродукции проводится в соответствии принципом выживания сильнейшего. Простейшим способом представления операции репродукции в алгоритмической форме является колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное значению целевой функции. Рассмотрим пример применения простого генетического алгоритма для максимизации функции ( ) 2 x x f = на целочисленном интервале (пример взят из монографии В.М. Курейчика Генетические алгоритмы [7]). Значения аргумента функции ( ) 2 x x f = , изменяющегося винтер- вале от 0 до 31, можно представить пятиразрядными двоичными числами. Первоначальная популяция, состоящая из четырёх строк пяти- разрядных чисел, полученная с помощью процедуры генерации случайных чисел, приведена во втором столбце табл. 3.1. Значение целе- 3.1. Анализ начальной популяции на первом шаге простого генетического алгоритма Номер хромосомы Дв о и ч н ы й код хромосомы Значение десятичный код) Значение целевой функции Нормированное значение) Ожидаемое количество копий хромосомы вслед у ю щ ем поколении Реальное количеств окоп и й хромосомы вслед у ю щ ем поколении 1,96 0,24 1,24 1 2 0 1 Суммарная целевая функция 1170 1,00 3,00 4 Среднее значение целевой функции 293 0,25 1,00 1 Максимальное значение целевой функции 576 0,49 1,97 2 |