Тогда последовательность

сходится к d(х-х*) при k® ¥, где d (х-х*) - функция Дирака.

3. Кроссинговер и мутация

После завершения отбора, выполняются генетические операции: кроссинговер и мутация [38]. Обе операции имеют случайный характер (вероятность применения, выбор локуса внутри хромосомы). Соответственно элементу a^t_i Î Р^t_i выбирается партнер из Р^t для рекомбинации, если это необходимо (например, для кроссинговера) и строится новая хромосома. Операторы, приводящие непосредственно после своего завершения к более чем одному потомку, случайно или, используя какую-либо иную стратегию, отбирают одного или более элементов-потомков, которые будут окончательным результатом операции, остальные элементы отбрасываются.

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

Традиционный и наиболее важный оператор рекомбинации, используемый генетическими алгоритмами, одноточечный кроссинговер, который осуществляется с вероятностью P_c (часто P_c=0.6). Кроссинговер выполняется следующим образом [38]:

1) Случайный выбор партнера для скрещивания

a2=(a_2,1...a_2,l) из P^t;

2) Случайный выбор точки кроссинговера

x Î {1, ..., l-1};

3) Формирование двух новых индивидуумов

a₁’={ a_1,1...a_1,x a_2,x+1...a_2,l } и

a₂’={ a_2,1...a_2,x a_1,x+1...a_1,l };

4) Случайный выбор a Î { a₁’, a₂’ }.

Отсюда может быть подсчитан вклад, вносимый кроссинговером, в теорему Холланда. Доступно l-1 точек для кроссинговера внутри строки, следовательно, вероятность того, что шаблон H будет разрушен кроссинговером, равна d(Н)/(l-1). Так как кроссинговер носит вероятностный характер, данное выражение необходимо умножить на P_c.

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

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

1) Случайный выбор (с некоторой фиксированной вероятностью P_m) позиций {x₁... x_k) Í {1, ..., l} внутри битовой строки, подверженных мутации;

2) a=(a_1,1...a_1,x1-1a’_x1a_1,x1+1...a_1,xh-1a’_xha_1,xh+1...a_1,l)

где a’_xi Î {0,1} "i = 1,...,h выбираются случайным образом.

При использовании мутации вероятность того, что шаблон порядка s(Н) будет разрушен, равна 1-(1-P_m)^s(Н). Для малых P_m это приблизительно равно s(Н)P_m , что объясняет наличие последнего члена в выражении, используемом в теореме о шаблоне.

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

Теорема. Пусть функция g(x)³0,"xÎF имеет глобальный максимум g* (возможно, во многих точках); существует непрерывная и пространтсвенно-односвязная окресность вокруг каждой точки глобального оптимума; исходная плотность распределения ненулевая по крайней мере в одной из таких окресностей. Тогда существует последовательность условных плотностей распределения оператора мутации с матрицами ковариации такая, что последовательность плотностей распределения внутри популяции, определенная как

приводит к увеличению средней оптимальности и сходится к глобальному максимуму, то есть E[g_k+1] ³ E[g_k] и lim_k®¥ E[g_k]=g*.

Таким образом, переход от поколения t к поколению t+l формально можно записать следующим образом (рис. 5):

(15)

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

Рис. 5. Структура генетического алгоритма.

4. Поиск оптимума

При выполнении специальных условий генетический алгоритм способен отыскивать глобальный оптимум.

Теорема [34]. Пусть выполняются следующие условия:

1) Последовательность популяций Р⁰, Р¹, ... , генерируемая алгоритмом - монотонна, то есть:

"iÎN:min{f(a)|aÎP^t+1}£min{f(a)|aÎP^t}.

2) "a,a’ элемент a’ достижим из a посредством мутации и кроссинговера, то есть через последовательность переходов в ряде структур.

Тогда глобальный оптимум функции f отыскивается с вероятностью 1:

lim_t®¥p{a*ÎP^t}=1. (16)

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

Для n-мерной с непрерывными параметрами оптимизационной задачи предполагается, что индивидуум популяции а состоит из l=nl_x, битов, где l_x - количество бит, используемое для кодирования одной непрерывной переменной x_iÎ[a_i,b_i]. Для бинарной кодировки переменных декодирующая функция, Г_a,b,l:{0,1}^l, принимает форму [14]:

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

где Å - суммирование по модулю 2. Пример кода Грея показан в таблице1. Отличительной характеристикой кода Грея является то, что соседние целые числа отличаются друг от друга только на один бит.

Учет дополнительных ограничений, возможен, если использовать один из следующих методов:

1) Разработка специализированных генетических операторов таким образом, чтобы производимые с их помощью новые индивидуумы популяции подчинялись налагаемым ограничениям [28].

2) Использование штрафных функций для наказания некорректных индивидуумов в соответствии с их степенью нарушения ограничений [56] .

Таблица 1.

Сравнение двоичного кода и кода Грея.

Масштабирование предназначено для предотвращения доминирования какого-либо элемента популяции над остальными на ранних стадиях эволюции и для расширения диапазона значений оптимальности на финальных стадиях эволюции, когда разнообразие в популяции существенно снижается. Среди данного класса методов выделяется динамическое параметрическое перекодирование [63], которое реализуется следующим овразом: когда наблюдается сходимость популяции, максимальные и минимальные значения диапазона пересчитываются для меньшего интервала (окна), и процесс итерируется далее. Этим достигается динамическое изменение диапазона решений при приближении к оптимуму. Таким образом масштабирование контролирует селективный отбор внутри популяции.

Возможны также другие методы масштабирования, такие как, например, линейное динамическое масштабирование, логарифмическое масштабирование, экспоненциальное масштабирование [38, 33] и др.

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

5. Строительные блоки

Возвращаясь к теореме о шаблоне:

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

Согласно данной теореме гарантируется рост числа шаблонов в последовательности поколений при соблюдении трех условий: (1) оптимальность шаблона выше средней по популяции; (2) его длина относительно мала; (3) он низкого порядка. Когда все три условия выполняются, то данный шаблон называется строительным блоком. Таким образом, значение фактора роста (большее или меньшее 1) является указанием на то, является ли данный шаблон строительным блоком. Когда g>1, последующие поколения будут содержать увеличивающееся количество строк, содержащих данный шаблон. Новые строки будут создаваться посредством рекомбинации данного строительного блока и других строительных блоков.

Однако существуют ситуации, нарушающие сходимость алгоритма к оптимальным точкам. Предположим, что оптимальность каких-либо двух коротких, низкого порядка шаблонов выше средней, а оптимальность их объединения - ниже средней. Например, оптимальность 00***** и *****00 выше средней, в то время как оптимальность 00***00 значительно. меньше оптимальности дополнения, 11***11, являющегося строительным блоком точки оптимума, 1111111. В этом случае генетический алгоритм сходится к точкам, имеющим меньшую оптимальность (например, 0011100), потому, что с высокой степенью вероятности кроссинговер будет разрушать необходимые в данном случае комбинации (11***11). Данная ситуация показывает проявление так называемой проблемы ложного оптимума (deception) [22]. Способ кодирования и упорядочивания битов внутри строки может направить алгоритм по ложному пути, вызывая сходимость к локальным оптимумам. Для преодоления данной проблемы были предложены два варианта: (1) использование предварительной информации для правильного упорядочивания битовых комбинаций внутри строки (сцепление битов); (2) использование инверсии.

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

Если упорядочивание битов внутри строки при решении определенной задачи является случайным, то было бы полезным знать вероятность случайного кодирования группы битов порядка k с определяющей длиной s=d в строке длины l. Для такого варианта Frantz [21] подсчитал, что соответствующая плотность вероятности равна:

а кумулятивное распределение :

Математическое ожидание длины строительного блока:

Рассматрмвая левую часть этого выражения как нормализованную длину, можно увидеть как быстро она растет с увеличением k. Даже для блока третьего порядка математическое ожидание нормализованной определяющей длины составляет 2/4=0.5. Таким образом, даже для битовых комбинаций низкого порядка шансы быть закодированными с необходимым упорядочиванием (быть сцепленными) являются низкими. По этой причине (а также потому, что априорная информация не всегда доступна) была предложена инверсия и другие операторы, переупорядочивающие биты внутри строки во время работы алгоритма.

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

((1 1) (2 1) (3 0) (4 0) (5 0) (6 1) (7 1)).

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

Стандартный оператор инверсии выбирает две позиции внутри строки и перебрасывает полученную подстроку между этими позициями. Пусть инверсия происходит между 2-м и 3-м битами и после 7-ого бита. Тогда получаем

((1 1) (2 1) (71) (6 1) (5 0) (4 0) (3 0))

Видно, что в данном случае инверсия получила необходимое сцепление битов для формирования строительного блока 1111***. Этот пример показывает, что инверсия может быть применена для осуществления нужного сцепления битов. Однако, вопрос о степени ее эффективности является спорным. Исследования [26] показали невысокую эффективность инверсии. Инверсия играет по отношению к упорядочиванию битов ту же роль, что мутация по отношению к аллелям. Оба оператора предотвращают преждевременное уменьшение разнообразия внутри популяции. Было найдено, что для того, чтобы инверсия обеспечивала сходимость к оптимуму, вероятность ее применения должна быть очень низкой. Но тогда возникает вопрос о ее практической ценности при одновременном поиске хороших аллелей и необходимого сцепления битов, так как время эволюции при ее применении значительно возрастает.

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

Пока же отметим, что согласно [39] генетические алгоритмы относятся к классу методов оптимизации, обладающих наилучшими нелокальными свойствами. Благодаря своей гибкости генетические алгоритмы охватывают широкий диапазон запросов (рис. 6). Поскольку популяция каким-то образом рассеяна в пространстве объектных параметров Rⁿ, у нее мало шансов сосредоточиться вокруг первого попавшегося локального минимума. Тем не менее, в силу рекурсивного характера алгоритма, это не может гарантировать глобальную сходимость. Возможность отыскания глобального оптимума среди множества локальных зависит от отношения размера популяции к числу объектных параметров, от природы множества оптимизации, адекватного выбора способа кодирования и упорядочивания переменных в виде элементов популяции, формы представления управляющих параметров генетического алгоритма, контролирующих отбор, кроссинговер, мутацию и возможные другие генетические операторы, например, инверсию. Всегда остается выбор между максимальной скоростью сходимости с одной стороны, и глобальной сходимостью с другой. Современные исследования концентрируются вокруг следующих направлений:

1) развитие более строгого математического фундамента генетических алгоритмов как метода оптимизации, включая анализ проблем, которые являются трудными для данных алгоритмов [58,63,13,46] и анализ зависимости эффективности алгоритма от различных генетических операторов и их параметров [52,70,62,29];

2) сравнение генетических алгоритмов с другими методами оптимизации и анализ возможных схем интеграции генетических алгоритмов .с другими методами оптимизации, например такими, как имитация отжига [50,42];

3) использование генетических алгоритмов для решения инженерных задач [45,44};

4) применение в адаптивных системах классификации [20,47];

5) использование в качестве базового для моделирования систем искусственой жизни [38,43];

6) реализация на параллельных архитектурах[66,53].

Рис. 6. Сравнительная эффективность алгоритмов оптимизации

б. Динамичность генома

Большинство типов генетических алгоритмов в настоящее время используют заранее определенные схемы кодирования строк и структуры генетических операторов. Независимо от характера решаемой проблемы, как правило, используются строки фиксированной длины, состоящие из наборов генов также фиксированной длины, и одно- или дву- точечная схема рекомбинации. Имеющиеся исключения в большинстве случаев также ограничены специальными условиями, накладываемыми на операции обработки строк. В противоположность этому в природе эволюция от простого к сложному использует значительно больше разнообразных механизмов регуляции на уровне генотипа. У эукариот, например, большинство генов состоит из нртранскрибируемых участков ДНК (интронов), разделенных участками, которые транскрибируются и транслируются (экзоны). Число интронов может достигать 16, как, например, у куриного гена, кодирующего белок овотрансферрин [8]. мРНК образуется путем сплайсинга РНК из экзонов. Процесс соединения участков РНК, происходящих из обособленных экзонов, отличается упорядоченностью. При сборке они соединяются соответствующими концами и в нужной последовательности [25,57].

На уровне хромосомы существуют также такие механизмы как 1) репарация ДНК, состоящая в замене тех оснований, которые неправильно включились или модифицировались [9,24]; 2) коррекция, осуществляемая ДНК-полимеразой, которая вырезает участки ДНК, непригодные для репликации [10]; 3) элиминация целых хромосомных участков, целых хромосом и целых хромосомных наборов [11]. Введение новшеств, или создание новых генных последовательностей установлено уже на молекулярном уровне. Ген иммуноглобулина создан хромосомой с использованием. тривиальных молекулярных механизмов. Две последовательности ДНК, которые в клетках зародышевой линии мышей непосредственно не функционировали, то есть не транскрибировали РНК, а поэтому не могли рассматриваться как структурные гены, объединяются при помощи перестроек в соматических тканях, в результате чего они становятся активными и образуют ген иммуноглобулина [67]. Избыточность и амплификация также представляют собой процессы, ведущие к новшествам. Они не только увеличивают число копий генов, но и порождают новые взаимодействия между существующими генами, модифицируя их активность [3,51]. Кроме того, возможно расщепление и воссоединение ДНК, что лежит в основе хромосомных перестроек, которые выражаются в форме транслокации, инверсии, дупликации и делеции. Благодаря этому возможно апробирование новых путей развития. Новые функции, которые приобретают гены в результате некоторых из этих перестроек, приводят к образованию новых функциональных направлений [49,48].

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

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

7. Немного истории

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

Другой отправной точкой развития исследований по генетическим алгоритмам была публикация в 1975 году книги Холланда "Adaptation in Natural and Artificial Systems". Эта книга заложила теоретический фундамент для работы де Джонга и всех последующих работ, математически обосновав идею близких подмножеств внутри генотипа, процессов гибели и селективного воспроизведения. Цели этой книги были достаточно широкими. Хотя доказательства основных утверждений были представлены для генов фиксированной длины и соответствующих простых операторов, это не ограничивало развитие представленного подхода на случаи более богатые по своим возможностям. Например, Холланд обсуждал возможность применения операторов внутрихромосомной дупликации, удаления и сегрегации участков хромосомы.

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

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

Исследование Кавичио [7], нацеленное на разработку детектора распознавания образов было одним из первых, использующих гены переменной длины. Расположенные на плоскости двоичные пикселы, способные различать свет и темноту, нумеровались и объединялись в подмножества, образующие разные детекторы, которые затем использобались некоторым априорно заданным алгоритмом для распознавания образов. При этом не возникало использование одного и того же пиксела дважды или не использования пиксела.

Смит [65] использовал правила, оперирующие строками переменной длины, создавая модель машинного игрока в покер. Его LS-1 система использовала модифицированный кроссинговер, который располагал точки кроссинговера как на границах строк, кодирующих правила, так и внутри них. Он также включил в алгоритм оператор инверсии, надеясь, что это поможет более эффективно распределять правила внутри строки.

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

Другие исследователи [12,26,54] предложили различные модификации схем генетического переупорядочивания внутри строки, когда используется кроссинговер. Одновременно был проведен ряд исследований, развивавших теорию Холланда [26,28] и продемонстрированы новые генетические операторы. Однако врпрос об их преимуществах и тщательном сравнении со стандартным генетическим алгоритмом продолжает оставаться открытым.

8. Особенности мобильного алгоритма.

Мобильный генетический алгоритм имееют следующие основные отличия от стандартного генетического алгоритма:

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

(2) Введение правил чтения или экспрессии генов.

(3) Использование операторов CUT (разрезание) и SPLICE (сплайсинг - сцепление) вместо традиционной схемы кроссинговера, оперирующего над генами фиксированной длины.

(4) Конкуренция между строительными блоками генотипа для отбора наиболее оптимальных.

(5) Деление эволюции на две фазы: предварительная фаза и фаза процессинга.

8.1 Представление хромосомы

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

Например, рассмотрим случай с длиной l = 3 и соответствующую ему строку из трех битов 011 стандартного генетического алгоритма. Данная строка будет представлена в новом алгоритме (используя LISP-подобный синтаксис) как ( (1 0) (2 1) (3 1) ), где каждый бит идентифицируется его именем и значением. В этой строке первым объектом является ген "1" со значением 0, вторым - ген "2" со значением 1 и третьим - ген "3" со значением 1. Так как и имя и значение гена определены, то может быть достигнута любая необходимая перестройка внутри хромосомы для сцепления определенных генов.

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

8.2 Пере- и недо- определение строки

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

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

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

8.3 Цикл работы алгоритма

Цикл работы мобильного генетического алгоритма имеет три этапа:

(1) инициализация;

(2) предварительная фаза;

(3) фаза процессинга.

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

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

8.4 Инициализация

Инициализация выполняется посредством создания популяции, содержащей по одной копии всех подстрок длиной k [53]. Этим гарантируется наличие в популяции всех необходимых строительных блоков генотипа. Когда выполняется обработка исходной популяции, то за счет применения новых генетических операторов формируются оптимальные структуры хромосом. Для выбора наиболее подходящего блока необходимо оценить каждый член популяции. Размер популяции при такой схеме инициализации определяется как:

(24)

(так как размерность равна l, то существует k^l комбинаций генов размера k, и для каждой комбинации существует 2^k различных бинарных комбинаций аллелей).

8.5 Предварительная фаза

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

8. б Фаза процессинга

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

Для рекомбинации строк переменной длины применяются два новых оператора CUT и SPLICE вместо обычного кроссинговера с фиксированным положением одной или двух точек рекомбинации (рис.7). CUT применяется к строке с вероятностью

p_c=(l-1)p_k, (25)

где l - длина строки,

p_k - некоторая константа, например, 0.1.

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

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

Рис. 7. Функционирование операторов CUT и SPLICE.

Вероятность выживания шаблона Н после операции CUT, P_surv можно охарактеризовать следующим неравенством:

где s - определяющая длина шаблона;

l - длина строки, содержащей шаблон;

p_c - вероятность операции CUT, определенная выше. Подставляя выражение для вероятности CUT, получаем

P_surv ³ 1-p_ks(H) (27)

Вероятность выживания шаблона после операции SPLICE равна единице, так как она не вызывает эффектов разрушения.

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

Рассмотрим вероятность Р_x продолжения экспрессии шаблона, активного в данный момент. Пусть N - событие, состоящее в том, что шаблон, экспрессированный на предыдущем шаге, не экспрессируется после последнего выполнения CUT и SPLICE. Тогда

Р_x =1-p_sP(N) (28)

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

P(N)=P(N|F)P(F)+P(N|B)P(B) (29)

Если подстрока в настоящий момент экспрессируется и она помещается в начало сцепленной пары, тогда шансы, что она не будет экспрессирована, нулевые, P(N|F)=0. С другой стороны, если эта же подстрока помещается в конец сцепленной пары, то вероятность ее экспрессии, P(N|B), будет зависеть от количества и типа генов, расположенных перед ней. Оценка этой вероятности для общего случая очень трудна. Поэтому, накладывая некоторые разумные предположения, можно получить приближенную оценку этой величины. Если гены распределены равномерно случайно по популяции и появление любого, отличного от анализируемого, гена в начале сцепленной пары блокирует экспрессию этого гена. При этих условиях

где l* - максимальная длина строки в популяции.

Применяя теорему о биномиальном распределении и отбрасывая члены высоких порядков, получаем:

Учитывая, что оператор SPLICE помещает подстроку в начало или конец новой строки с равной вероятностью, имеем:

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

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

Это уравнение можно свести к более простой форме после отбрасывания членов высоких порядков

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

9. Требования к ресурсам времени

Исследования [31] показали, что одной из важных характеристик мобильного алгоритма является количество времени, затрачиваемого на вычисления. Данные результаты представлены в табл. 2. Как видно из таблицы, большая часть времени затрачивается на этапе инициализации, когда необходимо оценить каждый элемент исходной популяции. При реализации алгоритма на последовательной машине количество требуемых оцениваний функции растёт полиномиально. При этом разница для инициализации и других этапов столь значительна, что возникает вопрос о необходимости оптимизации данного этапа. Поэтому наличие какой-либо предварительной информации о решаемой задаче может значительно снизить запросы алгоритма во время инициализации. На параллельной машине с достаточным числом процессоров вычислительное время алгоритма в течение инициализации может быть практически сведено к константе. На последующих этапах требуемое время растет как логарифмическая функция от числа переменных, что очень важно с точки зрения эффективности и последующих применений алгоритма при решении задач комбинаторной оптимизации.

Таблица 2. Оценки затрат для месси генетического алгоритма.

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

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

Библиография

[1] Лима-ле-Фариа А. Эволюция без отбора: Автоэволюция формы и функции. Москва, "Мир", 1991.

[2] Baker, J.E., "Adaptive selection methods for genetic algorithms," Proc. of the 1st. Intern. Conference on Genetic Algorithm and Their Applications, Hilisdale, NJ, pp. 101-111, 1985.

[3] Becak, W., Becak, M.L., Ruiz, I.R.G., "Gene regulation in polyploid amphibians," Proc. of the 14th Intern. Congress of Genetics, Moscow, Nauka, p.147, 1978.-

[4] Booker, L.B., "Intelligent behavior as an adaptation to the task environment". Technical Report No. 243, Ann Arbor; University of Michigan, Logic of Computer Group, 1982.

[5] Bremermann, H.J., Rogson, M. and Salaff, S., "Search by Evolution," in Biophysics and Cybernetic Systems. M. Maxfield, A. Callahan, and L. J. Fogel, Eds. Washington DC: Spartan Books, pp. 157-167, 1965.

[6] Bremermann, H.J., Rogson, M. and Salaff, S., "Global Properties of Evolution Processes," in Natural Automata and Useful Simulations. H. Pattee, E. A. Edisack, L. Feiri, and A. B. Callahan, Eds. Washington DC: Spartan Book^, pp. 3-41, 1966.

(7] Cavicchio, D.J., Adaptive search using simulated evolution,

PhD thesis, Univ. of Michigan, Ann Arbor, 1970.

[8) Chambon, P., "Split genes," Sci. Am., Vol. 244, No. 5, pp.

48-59, 1981.

[9] Cooper, P.К., Hanawalt, P.С., "Heterogeneity of patch size in repair replicated DNA in Escherichia coli," J. Mol. Bio!., 67, pp. 1-10, 1972.

110) Cornberg, A., DNA Replication, W. H. Freeman, San Francisco,

1980.

[II) Crouse, H.V., "X heterochromatin subdivision and cytogeiietic analysis in Sciara coprophila," Chromosoma, 74, pp. 219-239, 1979.

[12] Davis, L., Smith, D., "Adaptive design for layout synthesis,"

Dallas: Texas Instruments, 1985.

[13] Davis, Т.Е. and Principe, J.C., "A simulated annealing like convergence theory for the а1тр1" genetic algorithm," Proc. of the 4th Intern. Conf. on Genetic Algorithms, R. K. Belew and L. B. Booker, Eds. San Mateo, CA: Morgan Kaufmsnn, pp. 174-181, 1991.

[14] De Jong, К.А., Ал analysis of the.behaviour of a class of genetic adaptive systems, PhD thesis, Untv. of Michigan, 1975.

(15] Elben, A.E., Aarts, B;H., and Van Нее, К.M., "Global convergence of genetic algorithms: An Infinite Markov chain analysis," Parallel Problem Solving from Nature, H.-P. Schwefel and R. Manner, Eds. Heidelberg, Berlin: Springer-Verlag, pp. 4-12, 1991.

[16] Fahiman, S.E., "An eiTipirical study of learning speed in backpcopa.qat.i.ot\ i\etvork.s". Technical. Report, СМи-СЗ-вв-^та^, Carnegie Mellon University, Pittsburgh, PA, 1988.

[17) Fahiman, S.E., Leblere, C., "The Castfade Correlation Learning Architecture", Technical Report, CMU-CS-90-100, Carnegie Mellon University, Pittsburgh, PA, 1990.

[18] Fogarty, Т.С., "Varying the probability of mutation in genetic algorithm", Troc. of the Third Intern. Conf. on Genetic Algorithms and Their Applications, 104-109, San Mateo, California. Morgan Kauffmann Publishers, 1989.

[19] Fogel, D.B., "Asymptotic convergence properties of genetic algorithms and evolutionary programming: Analysis and experiments," Cybernetics and Systems, 1994.

[20] Forrest, S. and Miller, J.H., "Emergent behavior In classifier systems," Physica D, Vol. 42, pp. 213-227, 1990.

[21] Frantz, D.R., Non-linearities in genetic adaptive search, PhD

thesis, Univ. of Michigan, 1972.

[22] Fraser, A.S.,"Simulation o.f genetic systems," J. of Theor.

Biol., vol. 2, pp. 329-346, 1962.

[23] Fraser, A.S., "The evolution of purposive behavior," in Purposive Systems, H. von Foerster, J.D. White, L.J. Peterson, and J.K. Russel, Eds. Washington, DC: Spartan Books, pp. 15-23, 1968.

(24] Friedberg, E.G., DNA Repair, W. H. Freeman, New York, 1985.

[25] Gilbert, W., "Genes-in-pieces revisited," Science, No. 288,

pp. 823-824, 1985.

(26] Goldberg, D.E., Lingle, R., "Alleles, loci, and the traveling salesman problem,/' Proc. of an Intern. Conf. on Genetic Algorithms and Their Applications, pp.154-159, 1985.

[27] Goldberg, D.E., "Sizing populations for serial and parallel genetic algorithros," Proc. of the 3rd Intern, conference on Genetic Algorithms and Their Applications, San Mateo, CA, pp. 70-79, June 1989.

[28] Goldberg, D.E., Genetic algorithms in search, optimization

and machine learning. Addison Wesley, 1989.

[29] Goldberg, D.E., Deb, К., and dark, J.H., "Genetic algorithms: noise, and the sizing of populations," Complex Systems, Vol. 6, pp. 333-362, 1992.

(30) Goldberg, D.E., Korb, B., Deb, K., "Messy genetic algorithms: Motivation, analysis, and first results," Complex Systems, 3, pp. 493-530, 1989.

[31] Goldberg, D.E., Deb, K., Korb, B., "Messy genetic algorithms revisited; Studies in mixed size and scale," Complex Systems, 4, 415- 444, 1990.

132] Grefenstette, J.J., "Optimization of control parameters for genetic algorithm"," IEEE Trans. Sys., Man and Cybern., Vol. 16, N. I, pp. 122-128, 1986.

(33] Grefenstette, J.J. & Baker, J.E., "How genetic algorithms work: A critical look at Implicit parallelism," in Proc. of the 3rd Intern. Conference on Genetic Algorithms and Their Applications, San Mateo, CA, pp. 20-27, June 1969.

[34] Harti, R.E., "A global convergence proof for class of genetic

algorithms," Technische Universitat Wien, 1990.

(35] Hesser, J., and Manner, R., "Towards an optimal mutation probability in genetic algorithms". In Parallel Problem Solving from Nature, 23-32, Vol. 496 of Lecture Notes in Computer Science, Springer, Berlin, 1991.

[36] Hilliard, M.R., Liepins, G.E., Palmer, M., Morrow, M., ". Richardson, J., "A classifier based system for discovering scheduling heuristics", Proc. of the Second Intern. Co/if, on Genetic Algorithms and Their Applications, 231-235, 1987.

[37] Holland, J.H., "Adaptive plans optimal for payoff-only environments," Proc. of the 2nd Hawaii Int. Conf. on System Sciences, pp. 917-920, 1969.

(38] Holland, J.H., Adaptation in Natural and Artificial Systems.

Ann Arbor: Univ. of Michigan Press, 1975.

139] Holland, J.H., "Genetic algorithms," Scientific American, pp.

66-72, July, 1992.

(40) Holland, J.H., and Reltman, J.S., "Cognitive systei^s based on adaptive algorithms". In D.A. Waterman, i F. ^ayes-Roth (Eds.), Pattern directed Inference systems (313-329). New York: Academic Preas, 1978.

(41) Hollstlen, R.B., Artificial genetic adaptation in computer

control systems. PhD thesis, Univ. of Michigan, 1971.

[42] Inber, L. and Roacn, B., "Genetic algorithms and very fast simulated annealing - a comparison," Math. and Сотр. Model., Vol. 16, No. II, pp. 87-100, 1992.

[43] Jefferson, D., Collins, R., Cooper, C., Dyer, M., Flowers, M., Korf, R., Taylor, C., and Wang, A., "Evolution as a theme in artificial life: The Genesys/Tracker system," in Artificial Life II, C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, Eds. Reading, MA: 'Addison-Wesleу, pp. 549-' 578. 1991.

[44] Krishnakumar, К., and Goldberg, D.E., "Control system optimization using genetic algorithms," Journ. of Guidance, Control and Dynamics, Vol. 15, No. 3, pp. 735-740, 1992.

[45) Krietinsson, K., and Dumont, G.A., "System identification and control using genetic algorithms," IEEE Trans. Sys., Man and Cybern., Vol. 22, No. 5, pp. 1033-1046, 1992.

[46] Liepins, G.E., and Vose, M.D., "Deceptivieness and genetic algorithm dynamics," In foundationa of Genetic Algorithms, G. J. E. Rawl'lns, Ed. San Kl^teo, CA: Morgan Kaufmann, pp. 36-52, 1991.

[47] Liepins, G.E., Hilliard, M.R., Palmer, M. and Rangarajan, G., "Credit assignment and discovery In classifier systems," Intern. Journ. of Intelligent Sys., Vol. 6, No. I, pp. 55-69, 1991.

[48] LIma-de-Faria, A., Molecular Evolution and Organization 'of the Chromosome, Elsevier, Amsterdam, New York, Oxford, 1993.

[49) Lima-de-Faria, A., Arnason, U., Widegren, B., Isaksson, M., Essen-Moller, J., Jaworska, H., "DNA cloning and hybridization in deer species supporting the chromosome field theory," Biosystems, 19, pp. 185-212, 1986.

[50] Mahfoud, S.W. and Goldberg, D.E., "Parallel recombinative simulated annealing: A genetic algorithm," llliGAL Report No. 92001, Univ. of Illinois, Urbana-Champaign, 1992.

[51] Malva, C., Grazlani, F., Boncinelli, E., Polito, L., Ritossa, F., "Check o'f gene number during the process of rDNA magnification, "Nature New Biol., 239, pp. 135-137, 1972.

[52] Michalewicz, Z., Genetic Algorithms + Data Structures -Evolutionary Programs. Springer-Verlag, Al Series, New York, 1992.

[53] Muhlenbein, H., Schomisch, M. and Born, J., "The parallel genetic algorithm as function optimizer," Parallel Computing, Vol. 17, pp. 619-632, 1991.

[54] Oliver, 1.M., Smith, D.J., Holland, J.R.C., "A study of permutation crossover operators on the traveling salesman problem," Proc. of the 2nd Intern. Conf. on Genetic Algorithms, pp. 224-230, 1987.

(55] Reed J., Toombs R., and Barricelli, N.A., "Simulation of biological evolution and machine learning," Journal of Theoretical Biology, vol. 17, pp. 319-342, 1967.

[56] Richardson, J.T., Palmer, M.R., Liepins, G. and Hilliard, M., "Some guidelines for genetic algorithms with penalty functions," Proc. of the 3rd Intern. Conference on Genetic Algorithms and Their Applications, San Mateo, CA, pp. 191-197, June 1989.

[57] Rogers, J., "Exon shuffling and intron Insertion in serine

proteagenes," Nature, No. 315, pp. 458-459, 1985.'

[58] Rudolph, G., "Convergence properties of canonical genetic algorithms," IEEE Trans. on Neural Networks, Vol. 5, N. I, 1994.

(59] Rumelhait, D.E. and McClelland, J.L., Parallel Distributed Processing: Explorations in the Microstructures of Cognitior.. vol. I, Cambridge, MA: MIT Press, 1986.

[60) Sastry, P.S., Sar.thararo, G., and Unnikrishnan, K.P., "Memory neuron networks for Identification and control of dynamical systems", R4D Publication, GMR-7916, GM Technical Center, MI, 1993.

(6Ц Schaffer, J.D., Garuna, R.A., Eshelman, L.J., and Das, R., "A study of control parameters affecting online performance of genetic algorithms for function optimiz-ation", Proc. of the Third Intern. Conf. on Genetic Algorithms and Their Applications, 51-60, San Mateo, California. Morgan Kaufmann Pub-lishers, 1989.

[62] Schaffer, J.D. and Eshelman, L.J., "On crossover as an evolutionary viable strategy," in Proc. of the 4th Intern. Conf. on Genetic Algorithms, R. K. Belew and L. B.. Booker, Eds. San Mateo, CA: Morgan Kaufmann, pp. 61-68, 1991.

(63] Schraudolph, N.N. and Belew, R.K., " Dynamic parameter encoding for genetic algorithms," Machine Learning, Vol. 9, N. 1. pp. 9-21, 1992.

(64) Schwefel, H.P., Numerical Optimization of Computer Models,

Wiley, Chichester, 1981.

[йЬ] Smith, S.F., Л learning system based on genetic adaptive

algorithm, PhD thesis, Univ. of Pittsburgh, 1980.

[66] Spiessens, P. and Manderick, B., "A massively parallel genetic algorithm: iroplernentation and first analysis," Proc. of the fth Intern. Conf. on Genetic Algorithms, R. K. Belew and L. B. Booker, Eds. San Mateo, CA: Morgan Kaufmann, pp. 279-286, 1991.

(6'7] Tonegawa, S., Hozumi,, N., Matthyssens, G., Schuller, R., "Somatic changes In the content and context of immunoglobulin genes," Gold Spring Harbor Symp. Quant. Biol., 41, pp. Q^^-8Я9, 1977.

[68] Torn, A., and Zilinskas, Global Optimization, .Vol.350. of

Lecture Notes in Computer Scince. Springer, Berlifa. 1989.

[69] Unnilcrishnan, K.P. and Venugopal, K.P., "ALOPEX; a correlatl.on-baaed learning algorithm for feedfoi-ward and recurrent neural networks", R".D Publication GMR-7919, GM Technical Center, MI, 1993.

[70] Vignaux.. G.A., and Michalewicz, Z., "A gshetic algorithm for the Ilnear transportation problem," IEEE l'rans. on Systems, Man and Cybernetics, Vol. 21, N. 2, pp. 445-452, 1991.

[71] Werbos, P. "Beyond regression: new tools for prediction and analysis In the behavioral sciences," Doctoral dissertation, Harvard University, 1974.

[72] Wilson, S.W., "Knowledge growth in an artificial animal", Proc. of an Intern. Conf. on Genetic Algorithms and Their Applications, 16-23,1985.

[73] Wilson, S.W., "ClassJ.fier system learning of a boolean function". Research Memo, RIS-27r, Cambridge, MA: Rowland Institute for Science, 1986.

[74] Wilson, S.W., "Classifier systems and the Aniroat problem", Research Memo, RIS-36r, Cambridge, MA: Rowland Institute for Science, 1966.

[75] Xiaofeng Q., and Palmiet-i, F., "Theoretical analysis of evolutionary algorithms ij^lth an infinite population size in continuous space. Parts 1,11", IEEE Trans. on Neural Networks, Vol.5, No.1, 102-130, 1994.

[76] Narendra, K.S., "Recent developments in learning automata.", In K.S. Narendra (Ed.), Adaptive and learning systems: Theory and applications, pp. 197-212, New York: Plenum Press, 1986.

[77] Holland, J.H., Holyoak, K.J., Nisbett, R.E., and Thagard, P.R., Induction: Processes of inferencee, learning, ynd discovery. Cambridge: MIT Preess, 1986.

Поиск по сайту: