22183

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

Лекция

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

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

Русский

2013-08-04

248.5 KB

65 чел.

ЛЕКЦИЯ

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

         Вопросы:

        1  Основные понятия генетических алгоритмов

2  Классический генетический алгоритм

3 Выполнения классического генетического алгоритма

4   Кодирование параметров задачи в генетическом алгоритме

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

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

1  Основные понятия генетических алгоритмов

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

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

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

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

Ген (также называемый свойством, знаком или детектором) – это атомарный элемент генотипа, в частности, хромосомы.

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

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

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

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

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

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

Пример - 24.

Рассмотрим функцию

                                        

                                             F(x)=2x2+1                                                      (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}.

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

2  Классический генетический алгоритм

   

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

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

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

3) проверка условий остановки алгоритма;

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

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

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

7) выбор «наилучшей» хромосомы.

 Блок-схема основного генетического алгоритма изображена на рисунке 1. Рассмотрим конкретные этапы этого алгоритма более подробно.

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

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

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

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

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

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

                                                                                 (2)

где        

                                                                                     (3)

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

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

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

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

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

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

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

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

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

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

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

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

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

 Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности рс. Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью N, то рс=2/N. Аналогично, если из родительской популяции численностью N выбирается 2z хромосом (zN/2), которые образуют z пар родителей, то рс=2z/N. Если все хромосомы текущей популяции объединены в пары до скрещивания, то рс=1. После операции скрещивания родители в родительской популяции замещаются их потомками.

 Операция мутации изменяет значения генов в хромосомах с заданной вероятностью рm способом, представленным при описании соответствующего оператора. Это приводит к инвертированию значений отобранных генов с 0 на 1 и обратно. Значение рm, как правило, очень мало, поэтому мутации подвергается лишь небольшое количество генов. Скрещивание – это ключевой оператор генетических алгоритмов, определяющий их возможности и эффективность. Мутация играет наиболее ограниченную роль. Она вводит в популяцию некоторое разнообразие и предупреждает потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания.

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

3 Выполнения классического генетического алгоритма

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

Пример

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

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

ch1=[111001100101]

ch2=[001100111010]

ch3=[011101110011]

ch4=[001000101000]

ch5=[010001100100]

ch6=[010011000101]

ch7=[101011011011]

ch8=[000010111100]

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

F(ch1)=7

F(ch2)=6

F(ch3)=8

F(ch4)=3

F(ch5)=4

F(ch6)=5

F(ch7)=8

F(ch8)=5

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

Селекция хромосом. Селекция производится методом рулетки. На основании формул (2) и (3) для каждой из 8 хромосом текущей популяции (в нашем случае – исходной популяции, для которой N = 8) получаем секторы колеса рулетки, выраженные в процентах (рисунок 2)

v(ch1)=15.22

v(ch2)=13.04

v(ch3)=17.39

v(ch4)=6.52

v(ch5)=8.7

v(ch6)=10.87

v(ch7)=17.39

v(ch8)=10.87

Рисунок 2 - Колесо рулетки для селекции

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

79  4  9  74  44  86  48  23

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

ch7 ch3 ch1 ch7 ch3 ch7 ch4 ch2

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

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

ch2 и ch7  ch1 и ch7  ch3 и ch4  ch3 и ch7

Первая пара родителей:    Первая пара потомков:

 скрещивание  

lk=4

Вторая пара родителей:    Вторая пара потомков:

 скрещивание  

lk=3

Третья пара родителей:     Третья пара потомков:

 скрещивание  

lk=11

Четвертая пара родителей:    Четвертая пара потомков:

 скрещивание  

lk=5

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

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

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

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

Ch1 = [001111011011]   Ch5 = [011101110010]

Ch2 = [101000111010]   Ch6 = [001000101001]

Ch3 = [111011011011]   Ch7 = [011101011011]

Ch4 = [101001100101]   Ch8 = [101011110011]

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

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

F(Ch1)=8     F(Ch5)=7

F(Ch2)=6     F(Ch6)=4

F(Ch3)=9     F(Ch7)=8

F(Ch4)=6     F(Ch8)=8

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

4   Кодирование параметров задачи в генетическом алгоритме.

Выбор исходной популяции связан с представлением параметров задаче в форме хромосом, т.е. с так называемым хромосомным представлением. Это представление определяется способом кодирования. В классическом генетическом алгоритме применяется двоичное кодирование, т.е. аллеи всех генов в хромосоме равны 0 или 1. Длина хромосом зависит он условий задачи, точнее говоря – от количества точек в пространстве поиска.

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

Пример

Рассмотрим очень простой пример – задачу нахождения максимума функции, заданной выражением (1) для целочисленной переменной x, принимающей значения от 0 до 31.

Для применения генетического алгоритма необходимо, прежде всего, закодировать значения переменной x в виде двоичных последовательностей. Очевидно, что целые числа из интервала [0, 31] можно представить последовательностями нулей и единиц, используя их представление в двоичной системе счисления. Число 0 при этом записывается как 00000, а число 31 – как 11111. В данном случае хромосомы приобретают вид двоичных последовательностей, состоящих из 5 битов, т.е. цепочками длиной 5.

Также очевидно, что в роли функции приспособленности будет выступать целевая функция f(x), заданная выражением (1). Тогда приспособленность хромосомы chi, i=1, 2, … N будет определятся значением функции f(x) для x, равного фенотипу, соответствующему генотипу chi. Обозначим эти фенотипы chi*. В таком случае значение функции приспособленности хромосомы chi (т.е. F(chi)) будет равно f(chi*).

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

Допустим ,что выбраны хромосомы

Ch1=[10011]                           ch4=[10101]

Ch2=[00011]   ch5=[01000]

Ch3=[00111]                           ch6=[11100]

Соответствующие им фенотипы - это представленные ниже числа из интервала 0 до 31:

  Ch1*=19   ch4*=21

Ch2*=3 ch5*=8

  Ch3*=7   ch6*=29

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

F(ch1)=723    F(ch4)=883

F(ch2)=19 F(ch5)=129

 F(ch3)=99   F(ch6)=1683

Селекция хромосом. Методом рулетки выбираем 6 хромосом для репродукции. Колесо рулетки представлено на рисунке 3

Рисунок 3 - Колесо рулетки для селекции

Допустим что выбраны числа

97 26 54 13 31 88.

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

              Сh6 ch4 ch6 ch1 ch4 ch6

Пусть скрещивание выполняется с вероятностью pс=1  допустим, что для скрещивания  сформированы пары

сh1 и ch4  ch4 и ch6  ch6 и ch6

Кроме того допустим, что случайным образом выбрана точка скрещивания , равная 3 для хромосом сh1 и ch4, а также точка скрещивания равная 2 для хромосом сh4 и ch6.

сh1=[10011}  [10001]

сh4=[10101}     [10111]

     

сh4=[10101} [10101]

сh6=[11101}                     [11101]

     

При условии что вероятность мутации pm= 0, в новую популяцию включается хромосомы

 ch1=[10001]      ch4=[11101]

ch2=[10111] ch5=[11101]

ch3=[10101]                                      ch6=[11101]

Для расчета значений функции приспособленности этих хромосом необходимо декодировать представляющие их двоичные последовательности  и получить соответствующие им фенотипы. Обозначим их Chj*. В результате декодирования получаем числа ( из интервала от 0 до 31)

 ch1=17 ch4=29

ch2=23 ch5=29

ch3=21 ch=29

Соответственно значения функции приспособленности хромосом новой популяции рассчитанные по формуле (1) составят

 F(Ch1)=579  F(Ch4)=1683

F(Ch2)=1059 F(Ch5)=1683

F(Ch3)=883          F(Ch6)=1683

Легко заметить, что в этом случае среднее значение приспособленности возросло с 589 до 1262.

Если на следующей итерации будут сформированы для скрещивания пары хромосом, например, Ch4 и Ch2, Ch5  и Ch2  или Ch6 и Ch2 с точкой скрещивания 2 или 3, то среди прочих будет получена хромосома [11111] с фенотипом, равным числу 31, при котором оптимизируемая функция достигает своего максимума. Значение функции приспособленности для этой хромосомы оказывается наибольшим и составляет 1923. Если такое сочетание пар в данной итерации не произойдет, то можно будет ожидать образования хромосомы с наибольшим значением функции приспособленности на следующих итерациях. Хромосома [11111] могла быть получена и на текущей итерации в случае формирования для скрещивания пары Ch1 и Ch6 с точкой скрещивания 3.

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

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

Рассмотренное кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма. Значения кодов Грея рассмотрены в таблице ниже:

Таблица 1 - Соответствие десятичных кодов и кодов Грея

Двоичное кодирование

Кодирование по коду Грея

Десятичный код

Двоичное значение

Шестнадцатеричное значение

Десятичный код

Двоичное значение

Шестнадцатеричное значение

0

0000

0h

0

0000

0h

1

0001

1h

1

0001

1h

2

0010

2h

3

0011

3h

3

0011

3h

2

0010

2h

4

0100

4h

6

0110

6h

5

0101

5h

7

0111

7h

6

0110

6h

5

0101

5h

7

0111

7h

4

0100

4h

8

1000

8h

12

1100

Ch

9

1001

9h

13

1101

Dh

10

1010

Ah

15

1111

Fh

11

1011

Bh

14

1110

Eh

12

1100

Ch

10

1010

Ah

13

1101

Dh

11

1011

Bh

14

1110

Eh

9

1001

9h

15

1111

Fh

8

1000

8h

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

Логарифмическое кодирование - применяется в ГА для уменьшения длинны хромосом.

При кодировании нечисловых данных необходимо предварительно преобразовать их в числа.

В данной лекции описание способов кодирования не рассматривается. Для самостоятельного изучения рекомендуются статьи на сайте http://www.basegroup.ru/genetic/math.htm.


 

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

50322. Изучение явления дифракции света с помощью лазера 276 KB
  Рассмотрим дифракцию Фраунгофера от одной узкой прямоугольной щели рис. на щель падает плоская монохроматическая световая волна с длинной перпендикулярно к плоскости щели. Поместим за щелью на расстоянии во много раз большим по сравнению с шириной щели L а экран. В точке о лежащей на перпендикуляре к плоскости щели восстановленном из середины щели будут встречаться световые пучки длина пути которых от всех условных точечных источников щели до данной точки почти одинакова т.
50323. Изучение поляризации отраженного от диэлектриков света 682.5 KB
  Изучение поляризации отраженного от диэлектриков света. Цель работы: Изучение свойств света поляризованного при отражении от диэлектриков; изучение законов поляризации света при отражении от прозрачной среды; изучение методов определения показателя преломления диэлектрика по степени поляризации отраженного света. Приборы и принадлежности: Источник света; коллиматор; исследуемые образцы; анализатор; фотоэлемент; собирающая линза; миллиамперметр; транспортир. Подробно явление...
50324. Элементарный перцептрон Розенблатта 70.5 KB
  Подадим на вход перцептрона изображение буквы Т. Это изображение возбуждает все S-нейроны, кроме пятого и восьмого. Единичные сигналы с выходов возбужденных бинарных S-нейронов через связи, весовые коэффициенты которых заданы табл.1, поступают на входы A-нейронов. Суммарный входной сигнал на входе i-го A-элемента определяется соотношением
50325. Методы и системы искусственного интеллекта 170 KB
  Коэффициенты веса связей между Sи элементами постоянны. Необходимых комбинаций выходных сигналов на каждый класс изображений добиваются на этапе обучения или адаптации перцептрона за счет изменения переменных весов связей между и Rэлементами.
50326. Формирование земельного участка под строительство автомобильной дороги. Методические указания 359 KB
  Формирование земельного участка под строительство автомобильной дороги Направление подготовки 120700 Землеустройство и кадастры Профиль подготовки Земельный кадастр Квалификация степень выпускника Бакалавр Уфа 2012 УДК 332 ББК 65. Формирование земельного участка под строительство автомобильной дороги Цель лабораторных занятий – закрепление теоретических знаний и приобретение практических навыков по составлению и обоснованию проекта формирования...
50327. Определение кинематических характеристик по стробоскопическим фотографиям 246.5 KB
  Ошибкой измерения называется разность: Погрешность ∆Xэто количественная мера неизвестной экспериментатору ошибки ∂x.Отсчета и округления Относительная погрешность измерения: или б Погрешность прямых измерений nго количества наблюдений случайное отклонение результата iго измерения от среднего. средняя квадратичная погрешность отдельного наблюдения. Если то это наблюдение – промах средняя квадратная погрешность всей серии n ...
50328. Повышение технического и организационного уровня производительности 190 KB
  Чтобы их реализовать, каждое предприятие должно иметь чёткую систему внутрифирменного планирования, которая формирует не только рациональную производственную структуру предприятия и его организационно
50329. Процесс выявления ошибок в практике учёта и контроля расчетов с дебиторами и кредиторами в коммерческой организации 104.31 KB
  Проанализировать нормативную и теоретическую базу по теме исследования; Рассмотреть особенности учёта с дебиторами и кредиторами в коммерческих организациях; Выявить ошибки, которые могут возникать при ведении учёта расчётов с дебиторами и кредиторами; Разработать рекомендации способствующие совершенствованию учёта и контроля расчётов с дебиторами и кредиторами.