77536

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ И ИХ ПРИМЕНЕНИЕ

Лекция

Информатика, кибернетика и программирование

В животной клетке каждая молекула ДНК окружена оболочкой – такое образование называется хромосомой. Основная часть хромосомы нить ДНК определяющая какие химические реакции будут происходить в данной клетке как она будет развиваться и как функции выполнять. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом на самом деле 23 пары причем в каждой паре одна из хромосом получена от отца а вторая от матери.

Русский

2015-02-02

299 KB

8 чел.

Лекция 11.

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

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

- выбор наилучшей стратегии в условиях неопределенности(выбор цели);

- определение наиболее простого варианта построения системы или модели при соблюдению заданных требований к качеству ее функционирования ( задача структурного синтеза);

- нахождение оптимальной настройки параметров многокомпонентной системы при заданной ее структуре (параметрический синтез); 

Примеры:

- нахождение оптимального пути мобильной транспортной системы с учетом появления препятствий на ее пути ( минимум пути, недопущение столкновений);

- выбор формы и взаимного расположения функций принадлежности нечеткого регулятора;

- выбор оптимальной структуры нейронной сети (число слоев, количество нейронов в слоях);

- выбор алгоритма обучения нейронной сети, подбор параметров весов.

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

- резкий рост вычислительных затрат и времени;

- локальный характер алгоритмов поиска;

- низкая помехозащищенность алгоритмов. Генетические алгоритмы представляют собой новое направлен6ие – эволюционные вычисления. К ним относятся:

- эволюционные стратегии;

- эволюционное программирование;

-генетическое программирование;

-системы классификации.

        Эволюционная теория утверждает, что каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. В процессе эволюции многие виды насекомых и рыб приобрели защитную окраску, еж стал неуязвимым благодаря иглам, человек стал обладателем сложнейшей нервной системы. Можно сказать, что эволюция - это процесс оптимизации всех живых организмов.
          Основной механизм эволюции - это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (
генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает.
         В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул
нуклеотидов.  Нуклеотид представляет собой  комбинацию сахара, фосфата и одного из четырех входящих в состава ДНК азотистых оснований: аденина (А), тимина (Т), гуанина (G) и цитозина (С).  Молекула ДНК образует длинную спираль, состоящую из двух цепей, объединенных водородными связями. При этом основание (А) одной цепи может соединяться только с основанием (Т) другой цепи, основание (G) – только с основанием (С). В животной клетке каждая молекула ДНК окружена оболочкой – такое образование называется хромосомой. Основная часть хромосомы - нить ДНК, определяющая, какие химические реакции будут происходить в данной клетке, как она будет развиваться и как  функции выполнять. При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка.

 Различают два вида клеток: половые (такие, как сперматозоид и яйцеклетка) и соматические. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом - на самом деле 23 пары, причем в каждой паре одна из хромосом получена от отца, а вторая - от матери. Парные хромосомы отвечают за одинаковые признаки - например, родительская хромосома может содержать ген черного цвета глаз, а парная ей материнская - ген голубого цвета. Существуют определенные законы, управляющие участием тех или иных генов в развитии особи.

В половых клетках хромосом только 23, и они непарные. При оплодотворении происходит слияние мужской и женской половых клеток и получается клетка зародыша, содержащая 46 хромосом. Какие свойства потомок получит от отца, а какие - от матери? Это зависит от того, какие именно половые клетки принимали участие в оплодотворении. Процесс выработки половых клеток (так называемый мейоз) в организме подвергается случайностям, благодаря которым потомки во многом отличаются от своих родителей. При мейозе, происходит следующее: парные хромосомы соматической клетки сближаются вплотную, потом их нити ДНК разрываются в нескольких случайных местах и хромосомы обмениваются своими частями (рис. 40). Этот процесс обеспечивает появление новых вариантов хромосом и называется "кроссинговер".

Рис.40. Условная схема кроссинговера

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

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

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

Ген - это отрезок цепи ДНК, ответственный за определенное свойство особи, например за цвет глаз, тип волос, цвет кожи и т.д. Вся совокупность генетических признаков человека кодируется с помощью приблизительно 60 тыс. генов, длина которых составляет более 90 млн. нуклеотидов.

Различные значения гена называются его аллелями.
         Основной способ взаимодействия -
кроссовер (скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.
           При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида.

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

Идею генетических алгоритмов высказал Дж. Холланд в конце 60-х – начале 70-х годов двадцатого века. Холланд был уверен, что возможно составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи так, как это делает природа – путем эволюции. Он начал трудиться над алгоритмами, оперировавшими последовательностями набора двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные процесс в поколениях таких хромосом. В них были реализованы механизмы селекции и репродукции, аналогичные применяемым при естественной эволюции. Как и в природе, генетические алгоритмы осуществляли поиск «хороших» хромосом без использования какой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособленность. Механизм селекции заключается в выборе хромосом с наивысшей оценкой (наиболее приспособленных), которые репродуцируют чаще, чем особи с более низкой оценкой (хуже приспособленные).

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

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

- обрабатывают не значения параметров самой задачи, а их закодированную форму;

- осуществляют поиск решения исходя не из единственной точки, а из их некоторой популяции;

- используют только целевую функцию, а не ее производные, либо иную дополнительную информацию;

- применяют вероятностные, а не детерминированные правила выбора.

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

Популяция – это конечное множество особей.

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

Хромосомы – это упорядоченные последовательности генов.

Ген – это атомарный элемент генотипа, в частности, хромосомы.

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

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

Аллель – это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус или позиция указывает место размещения  данного гена в хромосоме. Множество позиций генов -  это локи.

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

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

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

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

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

 Пример хромосомы, кодирующей четыре параметра (x1, x2, x3, x4) представлен на рис.41.

Рис.41. Пример хромосомы.

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

1) отбор (селекция). В общем случае, отбор производится на основе вероятностей Pi(si), вычисленных для каждого из индивидуумов si популяции (i = 1, 2,…,М). Наиболее часто применяются следующие схемы отбора:

- пропорциональный отбор

- линейное ранжирование

Где ηmin = 2 - ηmax  и   1 ≤ ηmax ≤ 2; М – количество хромосом в популяции.

 - равномерное ранжирование:

где μ – некоторое фиксированное число первых членов популяции.

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

2) кроссовер (кроссинговер). Одноточечный кроссовер (скрещивание) представляет оператор рекомбинации и применяется по отношению к паре хромосом из популяции si, прошедших отбор. Назначается вероятность выполнения кроссовера Ркр. Далее, для случайно выбранной пары хромосом определяется случайное число k   { 1, 2, …,n-1}, называемое местом (или позицией) кроссовера, и затем биты из двух выбранных хромосом меняются местами после k-го бита с вероятностью Ркр (см. рис.42). Этот процесс повторяется для других выбранных хромосом до тех пор, пока популяция si  не окажется пустой. Обычно,  Ркр  [0,6; 0,99].

В общем случае, ГаА с рекомбинацией ( использует оператор кроссовера по схеме m:k ( m родителей, k потомков).

Рис.42. Схема кроссовера.

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

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

мут [0,001; 0,01]) (см. рис.43 ).

Рис.43  Операция мутации.

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

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

Например, предположим, один родитель состоит из 10 нулей, а другой - с 10 единиц. Пусть из 9 возможных точек разрыва избрана точка 3. Родители и их потомки показаны ниже.

Кроссинговер

Родитель 1 0000000000 000~0000000--> 111~0000000 1110000000 Потомок 1

Родитель 2 1111111111 111~1111111 --> 000~1111111 0001111111 Потомок 2

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

В настоящее время исследователи генов предлагают другие операторы отбора, кроссинговера и мутации. Ниже приведены наиболее распространенные.

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

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

Блок-схема генетического алгоритма изображена на рис. 2. Сначала генерируется начальная популяция особей (индивидуумов), то есть некоторый набор решений задачи. Как правило, это делается случайным образом. Потом моделируется размножение внутри популяции. Для этого, случайно отбирается несколько паров индивидуумов, происходит скрещивание между хромосомами в каждой паре, а полученные новые хромосомы переходят в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора - чем приспособленней индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет брать участие в скрещивании. Теперь моделируются мутации - в нескольких случайно избранных особях нового поколения изменяются некоторые гены. Старая популяция частично или целиком уничтожается и переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т.д.

Рис. 44. Блок-схема генетического алгоритма

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

Пример 1.

Рассмотрим функцию f(x) = 2x2  + 1, и допустим, что x принимает целые значения из интервала от 0 до 15. Задача оптимизации этой функции заключается в перемещении по пространству, состоящему из 16 точек со значениями 0, 1, …, 15 для обнаружения той точки, в которой функция принимает максимальное (или минимальное) значение.

Здесь в качестве параметров задачи выступает переменная x. Множество (0, 1, …, 15) составляет пространство поиска и одновременно – множество потенциальных решений задачи. Каждое из 16 чисел, принадлежащих этому множеству, называется точкой пространства поиска, решением, значением параметра, фенотипом. Решение, оптимизирующее функцию, называется наилучшим или оптимальным решением. Значения параметра x  от 0 до 15 можно закодировать следующим образом:

0000    0001    0010    0011    0100    0101    0110    0111

1000    1001    1010    1011    1100    1101    1110    1111

Это известный способ двоичного кодирования. Представленные кодовые последовательности называются цепями или хромосомами. Здесь они выступают в роли генотипов. Каждая из хромосом состоит из 4 генов (4 битов). Значение гена в конкретной позиции называется аллелью, принимающей значения 0 или 1. Популяция состоит из особей, выбираемых из этих 16 хромосом. Примером популяции с численностью, равной 6, может быть, например, множество хромосом (0010, 0101, 0111, 1001, 1100, 1110), представляющих собой закодированную форму следующих фенотипов (2,5,7, 9,12, 14). Функция приспособленности задается вышеприведенным уравнением. Приспособленность отдельных хромосом в популяции определяется значением этой функции для значений x, соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным значениям.

Классический генетический алгоритм состоит из следующих шагов:

- инициализация, или выбор исходной популяции хромосомы

- оценка приспособленности хромосом в популяции;

- проверка условия остановки алгоритма;

- селекция хромосом;

- применение генетических операторов;

- формирование новой популяции;

- выбор «наилучшей» хромосомы. Блок схема алгоритма показана на рис. 45

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

 

Где Хmax и Хmin – максимальное и минимальное значение параметров, Δ - значение погрешности определения оптимального параметра. Если Δ≠0,001(Хmax – Xmin), то n-= 9.

Размер селекции, то есть количество хромосом М обычно задается эмпирически.

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

n

Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение этой функции, тем выше «качество» хромосомы, Форма функции зависит от характера решаемой задачи. Предполагается, что функция приспособленности всегда принимает неотрицательные значения и, кроме того, для решения оптимизационной задачи требуется максимизировать эту функцию.

Рис. 45 Блок-схема генетического алгоритма.

 Проверка условия остановки алгоритма. Определение условия остановка ГА зависит от его конкретного применения. В оптимизационных задачах, если известно максимальное (или минимальное) значение функции приспособленности, то остановка алгоритма может произойти после достижения ожидаемого оптимального значения, возможно – с заданной точностью. Сходимость достигнута, если 60% хромосом в популяции имеют один и тот же вид. Остановка ГА может произойти также в случае, если его выполнение не приводит к улучшению уже достигнутого значения. Алгоритм может быть остановлен по истечении определенного времени выполнения либо после выполнения заданного количества итераций. Если условие остановки ГА выполнено, то производится переход к завершающему этапу выбора «наилучшей» хромосомы. В противном случае на следующем шаге выполняется селекция.

 Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е для очередного поколения. Такой выбор производится согласно  принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки, который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорционально значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений функции приспособленности для всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой chi для I = 1, 2, …,N(где N обозначает численность популяции) соответствует сектор колеса v(chi), выраженный в процентах согласно формуле

v(chi) = ps(chi) 100%

где

Причем F(chi) – значение функции приспособленности хромосомы  chi, а ps(chi) - вероятность селекции хромосомы chi. Селекция хромосомы может быть представлена как  результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Если всю окружность колеса рулетки представить в виде цифрового интервала [0,100], то выбор хромосомы можно отождествить с выбором числа из интервала [a,b], где а и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что 0≤a≤b≤100. В этом случае  выбор с помощью колеса рулетки сводится к выбору числа из интервала [0,100], которое соответствует конкретной точке на окружности колеса.

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

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

В классическом ГА применяются два основных генетических оператора: оператор скрещивания и оператор мутации. Однако оператор мутации играет второстепенную роль по сравнению с оператором скрещивания, т.е. скрещивание в классическом ГА производится практически всегда, а мутация – достаточно редко. Вероятность скрещивания, как правило, достаточно велика (обычно 0,5≤рс≤1), тогда как вероятность мутации устанавливается весьма малой (чаще  всего 0≤рм≤0,1).  Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко.

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

 Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции. Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным образом в соответствии с вероятностью скрещивания. Далее для каждой пары отобранных таким образом хромосом родителей разыгрывается позиция гена в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из  генов, то очевидно¸ что точка скрещивания lk представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L-1]. В результате скрещивания пары родительских хромосом получается следующая пара потомков:

- потомок, хромосома которого на позициях от 1 до lk состоит из генов первого родителя, а на позициях от lk + 1 до L – из генов второго родителя;

- потомок, хромосома которого на позициях от 1 до lk состоит из генов второго родителя, а на позициях от lk + 1 до L – из генов первого родителя.

 Оператор мутации с вероятностью pm изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или обратно). Вероятность pm обычно очень мала и может эмулироваться, например, случайным выбором числа из интервала [0,1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению pm.

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

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

Пример 1. Найти хромосому с максимальным количеством единиц. Допустим, что хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц.

Выбор исходной популяции хромосом. Необходимо случайным образом сгенерировать 8 двоичных последовательностей длиной12 битов. Это можно достигнуть, например, подбрасыванием монеты (96 раз, при выпадании «орла» приписывается значение 1, а в случае «решки» - 0). Таким образом можно сформировать исходную популяцию:

сh1 = [111001100101]                            сh5 = [010001100100]  

сh2 = [001100111010]                            сh6 = [010011000101]                            

сh3 = [011101110011]                            сh7 = [101011011011]                            

сh4 = [001000101000]                             сh8 = [000010111100]  

Оценка приспособленности хромосом к популяции. Функция приспособленности определяет количество единиц в хромосоме. Ее значения для каждой хромосомы из исходной популяции:

F(ch1) = 7                          F(ch5) = 4

F(ch2) = 6                        F(ch6) = 5

F(ch3) = 8                        F(ch7) = 8

F(ch4) = 3                        F(ch8) = 5   

Хромосомы ch3 и ch7 характеризуются наибольшими значениями функции принадлежности. Они считаются наилучшими кандидатами на решение задачи. Если условие остановки алгоритма не выполняется, то на следующем шаге производится селекция хромосом из ткущей популяции.

 Cелекция хромосом. Селекция производится по методу рулетки. Для каждой из 8 хромосом текущей популяции получаем сектора рулетки, выраженные в процентах (рис. 46):  

Рис. 46. Принцип работы рулетки.

V(ch1) = 15,22                           V(ch5)= 8,7

V(ch2) = 13,04                           V(ch6)= 10,87

V(ch3) = 17,39                           V(ch7)= 17,39

V(ch4) = 6,52                            V(ch5)= 10,87

Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому. Допустим, что разыграны следующие 8 чисел:

 70    44    9    74    44    86    48    23

Это означает выбор хромосом

 ch7    ch3    ch1    ch7    ch3    ch7    ch4    ch2

Как видно, хромосома ch7 была выбрана трижды, а хромосома ch3 – дважды. Именно эти хромосомы имеют наибольшее значение функции приспособленности. Однако выбрана хромосома ch4 с наименьшим значением функции приспособленности. Все выбранные таким образом хромосомы включаются в так называемый родительский пул.

Применение генетических операторов. Допустим, что ни одна из отобранных в процессе селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Это означает, что вероятность скрещивания рс =1, а вероятность мутации рм = 0. Допустим, что из этих хромосом случайным образом сформированы пары родителей:

 сh2 и ch7    ch1 и ch7    ch3 и ch4    ch3 и ch7

Для первой пары случайным образом выбрана точка скрещивания lk = 4, для второй

lk = 3, для третьей lk = 11, для четвертой lk = 5. При этом процесс скрещивания протекает так, как показано на рис.  . В результате выполнения оператора скрещивания получается 4 пары потомков.

Если бы при случайном подборе хромосом для скрещивания были объединены, например, ch3 с ch3 и ch4 с ch7 вместо ch3 с ch4 и ch3 с ch7, а другие пары остались без изменения, то скрещивание ch3 с ch3 дало бы две такие же хромосомы независимо от разыгранной точки скрещивания.. Это означало бы получение двух потомков, идентичных своим родителям. Заметим, что такая ситуация вероятна для хромосом с наибольшим значением функции приспособленности, т.е. именно такие хромосомы получают наибольшие шансы на переход в новую популяцию.

Рис.47. Работа ГА.

Формирование новой популяции. После выполнения операции скрещивания мы получаем (согласно рис.  ) следующую популяцию потомков:

Ch1 = [001111011011]                             Ch5 = [011101110010]  

           Ch2 = [101000111010]                             Ch6 = [001000101001]                            

            Ch3 = [111011011011]                            Ch7 = [011101011011]                            

            Ch4 = [101001101101]                             Ch8 = [101011110011]

Для отличия от хромосом предыдущей популяции обозначения вновь сформированных хромосом начинаются с большой буквы С.

Согласно блок-схеме генетического алгоритма производится возврат ко второму этапу, т.е. к оценке приспособленности хромосом из вновь сформированной популяции, которая становится текущей. Значения функций приспособленности этой популяции составляют

 F(Сh1) = 8                          F(Сh5) = 7

                       F(Сh2) = 6                          F(Сh6) = 4

                       F(Сh3) = 9                         F(Сh7) = 8

                       F(Сh4) = 6                         F(Сh8) = 8  

Заметно, что популяция характеризуется более высоким средним значением функции приспособленности, чем популяция родителей. В результате скрещивания получена хромосома Сh3 с наибольшим значением функции приспособленности, которым не обладала ни одна хромосома из родительской популяции. Однако могло произойти и обратное, поскольку после скрещивания на первой итерации хромосома, которая в родительской популяции характеризовалась наибольшим значением функции приспособленности, могла просто «потеряться». Помимо этого «средняя»  приспособленность новой популяции все равно оказалась бы выше предыдущей, а хромосомы с большими значениями функции приспособленности имели бы шансы появиться в следующих поколениях.

Пример 2. Найти максимум функции f(x) = 2x2+1 для х = 0…31.

Для применения ГА необходимо прежде всего закодировать в виде двоичных последовательностей значения х. Очевидно, что числа 0…31 можно представить в двоичной системе счисления. При этом ) кодируется как 00000, а 31 – 11111, т.е. это цепочка из 5 битов.. Выберем случайным образом популяцию, состоящую из 6 кодовых последовательностей N=6 (30 раз подбрасываем монету). Допустим, что выбраны хромосомы:

ch1 = 10011           ch4= 10101

ch2= 00011            ch5= 01000

ch3= 00111            ch6 = 11101

Соответствующие  им фенотипы – это числа из интервала 0…31.

ch1 = 19           ch4= 21

ch2= 3              ch5= 8

ch3= 7              ch6 = 29

По вышеприведенной формуле рассчитываем значения функции приспособленности

Fch1 = 723          Fch4= 883

Fch2=  19          F ch5= 129

Fch3= 99           Fch6 = 1683  Среднее значение F =589, сумма – 3536

Рассчитываем

Pch1 = 20,45          Pch4= 24,97

Pch2=  0,54         P ch5= 3,65

Pch3= 2,8           Pch6 = 47,6  

Методом рулетки выбираем 6 хромосом длz репродукции (вращаем рулетку 6 раз) . Допустим, что выбраны числа

97   26   54   13   31   88

Это означает выбор хромосом  ch6   ch4   ch6   ch1   ch4   ch6.

Пусть скрещивание выполняется с вероятностью 1. Для скрещивания случайным образом  формируем пары ch1 и   ch4   ch4 и   ch6   ch6 и  ch6.

Допустим, что случайным образом выбрана точка скрещивания, рваная 3 для первой пары, а также точка скрещивания , равная 2 для второй пары. Операция скрещивания для третьей пары бесполезна, т.к. дает тот же результат. При условии, что вероятность мутации равна 0, в новую популяцию включаются хромосомы:

Ch1 = 10001           Ch4= 11101

Ch2= 10111            Ch5= 11101

Ch3= 10101            Ch6 = 11101

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

Ch1 = 17           Ch4= 29

Ch2= 23            Ch5= 29

Ch3= 21            Ch6 = 29

Функции приспособленности

Fch1 = 579          Fch4= 1683

Fch2= 1059          F ch5= 1683

Fch3= 883              Fch6 = 1683  Среднее значение F =1262, что значительно больше предыдущего значения.

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

Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера. Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).
Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.

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

Рис. 48 Метод перебора.

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

Рис. 49. Градиентный метод.

Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является.

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

Рис. 50. Мультимодальная функция.

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


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

Сегодня на базе ГА формируется большой класс методов в рамках нового направления в области теории вычислительного интеллекта – класс эволюционных вычислений. К этому классу относятся:

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

- эволюционное программирование – оптимизация непрерывных функций без использования системы рекомбинации;

- генетическое программирование оптимизация создаваемых компьютерных программ;

- системы классификации – создание правил логического вывода с помощью ГА;

- когнитивные эволюционные компьютеры – нейроподобные элементы в сочетании с ГА для приобретения знаний;

- эволюционная информатика;

- создание биокомпьютеров.

 Некоторые модели генетических алгоритмов

 Genitor (Whitley)

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

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

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

7.2 CHC (Eshelman) 

CHC – это Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation.

Для нового поколения выбираются N лучших различных особей среди родителей и детей. Дублирование строк не допускается.

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

При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover), разновидность однородного кроссовера – каждому потомку переходит ровно половина битов каждого родителя.

Размер популяции небольшой. Этим оправдано использование однородного кроссовера.

Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций. В этом случае CHC применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссовер.

 Hybrid algorithm (Davis)

Использование гибридного алгоритма позволяет объединить преимущества ГА с преимуществами классических методов.

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

Однако можно использовать "классические" методы (hill-climbing, например) и внутри самих ГА. На каждом поколении каждый полученный потомок оптимизируется этим методом, таким образом, каждая особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации. Такой метод ухудшает способность алгоритма искать решение с помощью отбора гиперплоскостей, но зато возрастает вероятность того, что одна из особей попадет в область глобального максимума и после оптимизации окажется решением задачи.

 Island Models

Островная модель (island model) — модель параллельного генетического алгоритма. Разобьем популяцию на несколько подпопуляций. Каждая их них будет развиваться отдельно с помощью некого генетического алгоритма. Таким образом, можно сказать, что мы расселили особи по нескольким изолированным островам.

Изредка (например, каждые 5 поколений) происходит миграция – острова обмениваются несколькими хорошими особями.

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

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

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

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

Факторы, создающие сложность для ГА

Свойства функций приспособленности, создающие сложность для ГА.

Многоэкстремальность: создается множество ложных аттракторов. Пример — функция Растригина:


На картинке изображен график функции Растригина с одним аргументом.

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

Пример: пусть строка состоит из 10-ти четырехбитных подстрок. Пусть  равно количеству единиц в i-той подстроке. Зададим функцию g(u) следующей таблицей:

u

0

1

2

3

4

g(u)

3

2

1

0

4

и пусть функция приспособленности равна сумме g() по всем i = 1..10:

Изолированность («поиск иголки в стоге сена»): функция не предоставляет никакой информации, подсказывающей, в какой области искать максимум. Лишь случайное попадание особи в глобальный экстремум может решить задачу.

Дополнительный шум (noise): значения приспособленности шаблонов сильно разбросаны, поэтому часто даже хорошие гиперплоскости малого порядка не проходят отбор, что замедляет поиск решения.



 

А также другие работы, которые могут Вас заинтересовать

26571. ОПРЕДЕЛЕНИЕ КИСЛОТНОСТИ МОЛОКА 4.16 KB
  ОПРЕДЕЛЕНИЕ КИСЛОТНОСТИ МОЛОКА. Определение кислотности молока и молочных продуктов проводится по ГОСТ 362492.Сущность метода состоит в титровании кислых солей: белков углекислого газа и других компонентов молока раствором щелочи в присутствии фенолфталеина. Кислотность молока является важнейшим биохимическим показателем который учитывается при продаже молоха государству.
26572. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА ЖИРА В МОЛОКЕ 3.66 KB
  ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА ЖИРА В МОЛОКЕ.Определение состояния жира в молоке.Определение содержания жира в молоке. Уровень воды в водяной бане должен быть выше уровня столбика жира в жиромере.
26573. ОПРЕДЕЛЕНИЕ МЕХАНИЧЕСКОЙ ЗАГРЯЗНЕННОСТИ МОЛОКА 1.49 KB
  Молоко тщательно перемешивают и быстро чтобы механические частицы не осели отбирают 250 мл и выливают в прибор. Для ускорения фильтрации холодное молоко предварительно подогревают до 2030С когда все молоко профильтруется снимают фильтр с сетки и накладывают на эталон степень чистоты молока определяют сравнивая со стандартным эталоном. К первой группе относится молоко при фильтрации которого на фильтре отсутствуют частицы механических примесей ко 2ой группе если на фильтре имеются отдельные частицы к 3ей если на фильтре имеется...
26574. ОПРЕДЕЛЕНИЕ НАТУРАЛЬНОСТИ МОЛОКА 2.63 KB
  ОПРЕДЕЛЕНИЕ НАТУРАЛЬНОСТИ МОЛОКА. При добавлении в молоко несвойственных ему веществ или изъятий составных частей например жира оно считается фальсифицированным. где хэто колво воды Доплотность цельного мол30АД1плот. при добав соды в мол реакция щелоч.
26575. ОПРЕДЕЛЕНИЕ СОДЕРЖАНИЯ БЕЛКОВ В МОЛОКЕ 5.58 KB
  В настоящее время широкое распространение получил рефрактометрический метод определения белка в сыром молоке. Метод основан на измерении показателей преломления молока и безбелковой молочной сыворотки полученной из того же образца молока разность между которыми прямо пропорциональна массовой доле белка в молоке. Комплект для измерения массовой доли белка рефрактометр со шкалой массовой доли белка в диапазоне 0 15 и ценой деления 01 ИРФ464 и водяная баня закрытого типа для флаконов центрифуга для определения массовой доли жира в...
26576. ОПРЕДЕЛЕНИЕ СУХОВОГО ОСТАТКА МОЛОКА ЦЕЛЬНОГО И ОБЕЗЖИРЕННОГО 6.52 KB
  ОПРЕДЕЛЕНИЕ СУХОВОГО ОСТАТКА МОЛОКА ЦЕЛЬНОГО И ОБЕЗЖИРЕННОГО. Количество сухих веществ молока является показателем качества молока и его питательной ценности. В состав сухих веществ молока входят жир белок сахар минеральные вещества. Более постоянной величиной является сухой обезжиренный молочный остаток СОМО в состав которого входит белок сахар и соли молока.
26577. ОПРЕДЕЛЕНИЯ ПЛОТНОСТИ МОЛОКА 5.19 KB
  ОПРЕДЕЛЕНИЯ ПЛОТНОСТИ МОЛОКА Определение плотности молока производят в соответствии с требованиями ГОСТ 362584. Плотностью молока называют отношение массы молока при температуре 20 к массе равного объема воды при температуре 4С температура воды с наибольшей плотностью. Плотность цельного коровьего молока колеблется в пределах 1027 1033 кг мЗ. Плотность молока часто для краткости выражают не полным числом а только цифрами следующими за десятыми долями в градусах плотности отбрасывая две первые цифры 10 так как они всегда постоянны...
26578. ОСМОТР ТУШ И ОРГАНОВ УБИТЫХ ЖИВОТНЫХ В УБОЙНОМ ЦЕХЕ МЯСОКОМБИНАТА 4.74 KB
  ЛИВЕР подвешивают за кольца трахеи поворачивают средостением вскрывают бронхиальные и средостенные лимфоузлы прощупывают легкие разрезают легкие параллельно средостению отступя от него 1 см. Осматривают ПЕЧЕНЬ цвет размеры вскрывают портальные лимфоузлы разрезают печень вдоль 2 разрезами вскрывают желчные ходы. ПОЧКИ осматривают с поверхности прощупывают при необходимости вскрывают вскрывают почечные лимфоузлы. На мясокомбинатах скотобойнях и убойных пунктах лимфатические узлы туши вскрывают в том случае если к этому имеются...
26579. ОСОБЕННОСТИ СТРОЕНИЯ И ТОПОГРАФИИ ЛИМФОУЗЛОВ КРС, ОВЕЦ, СВИНЕЙ. ОСОБЕННОСТИ ТОПОГРАФИИ ЛИМФАТИЧЕСКИХ УЗЛОВ У РАЗНЫХ ВИДОВ ЖИВОТНЫХ 40.12 KB
  У КРУППОГО РОГАТОГО СКОТА И ОВЕЦ лимфатические узлы овальной формы окружены жировой тканью и имеют на разрезе серый или интенсивносерый цвет. По сравнению с крупным рогатым скотом некоторые лимфатические узлы у свиней отсутствуют. ЛИМФАТИЧЕСКИЕ УЗЛЫ КРУПНОГО РОГАТОГО СКОТА. Передние средостенные лимфатические узлы расположены в средостении впереди от аорты слева от пищевода и трахеи некоторые у входа в грудную полость.