<<
>>

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

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

Существуют различные методы, позволяющие повысить эф­фективность эволюционного поиска. Основным способом повы­шения скорости работы стационарных генетических алгоритмов является распараллеливание [13.1]. Другое направление — раз­работка адаптивных генетических алгоритмов [13.2], суть ко­торого состоит в переходе от алгоритмов с жестко заданными связями к модели с динамически меняющейся структурой в за­висимости от решаемой задачи. Выбор параметров генетических алгоритмов — произвольный, во многих задачах он определяется только интуицией пользователя. Различные методы выбора па­раметров генетических алгоритмов предложены в работах [13.3, 13.4]. Недостатком этих подходов является то, что параметры генетического алгоритма задаются перед запуском программы и неизменны в течение всего процесса эволюции. В поколенческих

генетических алгоритмах [13.2, 13.5] размер популяции может меняться в определенных пределах. Такой подход позволяет расширить пространство поиска при незначительном снижении скорости. Развитием этих идей являются многоуровневые гене­тические алгоритмы, которые в процессе работы могут менять многие параметры генетического поиска.

13.1.1. Принципы построения виртуальных популяций. Разработка генетического алгоритма включает три основных компоненты: разработка структуры, принципов кодирования и декодирования хромосом; разработка основных генетических операторов; разработка общей структуры генетического поиска [13.3, 13.6].

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

В ряде случаев решение задачи представляется в виде век­тора P = {pi| i = 1,2,...,n}, где piв пределах P имеет уни­кальное значение, т. е. (Vi, j) [pi= pj∙]. Такое представление ис­пользуется при решении задач размещения, разбиения, раскрас­ки, установления изоморфизма и др. [13.6, 13.7, 13.8]. Каждой перестановке элементов вектора P соответствует свое решение задачи. Известно, что непосредственное представление вектора в виде хромосомы делает хромосому негомологичной, что приводит в дальнейшем к проблемам, связанным в основном с получением нелегальных решений [13.1, 13.6].

В работе предлагается два подхода к построению структур и принципов кодирования хромосом, обеспечивающих их гомо­логичность [13.4, 13.8].

Решение P получается путем применения рекурсивной про­цедуры декодирования.

Хромосома H = {gt11 = 1,2,..., n — 1} состоит из генов, чис­ло которых на единицу меньше числа элементов решения P.

Рассмотрим первый подход. Ген gtможет принимать значе­ния, лежащие в интервале 1 ≤ gt≤ n — t + 1, т. е. чем больше порядковый номер t, тем меньшее значение он может принять. Процесс декодирования осуществляется последовательно, начи­ная с первого гена gι. На шаге t декодируется ген gt. В ре­зультате декодирования гена gtопределяется элемент вектора P,

который помещается в позицию t. Для декодирования хромосомы используется опорный вектор элементов Bi = {bi1| i = 1,2,..., n}. После декодирования очередного гена gtвектор Btуменьшается путем удаления из него элемента, определенного при декодиро­вании gt.

Пусть на шаге t (t = 1,2,..., n — 1) декодируется ген gt. К мо­менту декодирования gtполучен вектор Bt= {pt | i = 1,2,..., n — — t + 1} путем удаления t — 1 элемента из Bi на предыдущих шагах. Определяется значение i гена gt, т. е. i = gt. В векторе Bt определяется очередной элемент &t, который помещается в пози­цию t, т. е. ptприсваивается значение (pt= bt). После этого формируется вектор Bt+ι, для этого из Btудаляется элемент bt. Связь между элементами bt+1и определяется с помощью следующих выражений:

На шаге n вектор Bnсостоит из одного элемента b", поэтому pn = b".

Рассмотрим первый метод декодирования на примере. Пусть имеется хромосома H = (5,2,3,2) и опорный вектор Bi = = (2,3,1,5,4)

На первом шаге рассматриваем ген gι; i = gι = 5. Отсюда pi = bi1= F = 4. Элемент &5 удаляется из Bi и получается B2 = = (2,3, 1,5). На втором шаге рассматривается ген g2; i = g2 = 2. Тогда p2 = &2 = 3. Элемент b∣удаляется из B2 и получается B3 = = (2, 1,5). На третьем шаге рассматриваем ген g3; i = g3 = 3. Тогда p3 = &3 = 5. Элемент b3удаляется из B3 и получается B4 = = (2, 1). На четвертом шаге рассматривается ген g4. i = g4 = 2. Отсюда p4 = &2 = 1. Удаляем из B4 и получаем B5 = (2). Так как &5 является единственным, то p5 = &5 = 2. Таким образом, построенный вектор P имеет вид P = (4,3,5, 1,2).

При втором подходе хромосома декодируется следующим об­разом. Хромосома имеет вид H = {gt1t = 1,2,..., n — 1}. Воз­можные значения гена зависят от локуса и меняются в интервале 1 ≤ gt ≤ t + 1.

Построение вектора P производится последовательно с ис­пользованием опорного вектора B = {bi| i = 1,2,..., n}. Обозна­чим через Ptчастично построенный вектор на шаге t. На каждом шаге t строится вектор Pt+ι путем включения в Ptэлемента

bt∈B. Место включения btв Ptопределяется в результате декодирования гена gt∈H.

Окончательно вектор P будет построен на шаге n, т. е. P = = Pn. Вначале принимается, что Pi = {bι}, т. е. Pi включает первый элемент bi ∈B.

Пусть Pt= {pt| i = 1,2,..., t}. Тогда Pi = {pi}, P2 = {p2,⅛ P3 = {Pι,P2,р3} и т. д.

На каждом шаге t декодирования хромосомы строится Pt+ι. Для этого выбирается ген gtи определяется место i = gtвклю­чения элемента bt+ι в вектор P2.

Pt+1 получается путем вставки в Ptэлемента bt+ι после pt_ 1 и сдвига на одну позицию элементов pt-i+j, j = 1,2,..., t — i. Связь между элементами pt и pt+1определяется с помощью следующих выражений:

Рассмотрим второй метод декодирования на примере. Пусть имеется хромосома H = (1,2,2, 1) и опорный вектор B = = (2,3,1,5,4).

В начале принимаем, что Pi = {bι} = {pl} = {2}. На первом шаге строится P2 путем включения &2 = 3 в Pi. Для этого рассматривается ген gi. i = g = 1; Отсюда p2= p2 = ½ = 3; p2 = P1= 2. Итак, P2 = {3,2}.

На втором шаге строится P3 путем включения b3 = 1 в P2. Рассматривается ген g2, i = g2 = 2; Отсюда p3= p2= 3; p3= p3= = b3 = 1; p3 = P2= 2. Итак, P3 = {3, 1,2}.

На третьем шаге строится P4 путем включения b4 = 5 в P3. Рассматривается ген g3. i = g3 = 2. Следовательно, p4= p3= 3; P4= p4= 5; p4= p2 = 1; p4 = p3= 2.Отсюда P4 = {3,5, 1,2}.

На четвертом шаге строится P5 путем включения ⅛ = 4 в P4. Рассматривается ген g4. i = g4 = 1. Следовательно, p5= p3= 4, P25= P41= 3; P53= P42= 5; P45= P34= 1; P55= P44= 2. Окончательно P2= P5 = {4,3,5,1,2}.

Трудоемкость декодирования хромосом имеет оценку O(n). Достоинствами предложенной структуры хромосомы и принци­пов ее декодирования являются:

— отсутствие сложных элементов;

— линейная оценка временной сложности — O(n);

— хромосомы и гены, расположенные в одних и тех же локу­сах, — гомологичные.

Фенотип, т. е. решение задачи, получается после декодирова­ния хромосом и построения вектора P. Отметим, что процесс де­кодирования хромосомы опирается на вектор B. Таким образом, одному и тому же генотипу H в зависимости от вида вектора B соответствуют различные фенотипы.

С учетом этого обстоятельства, в работе используется вирту­альное множество популяций V = {(Bι | Π), l = 1,2,...,nv}, где Π = {Hj∙ | j = 1,2,..., M} — популяция генотипов. Формирование исходной популяции осуществляется случайным образом. При формировании отдельной хромосоме присваиваются случайные значения в допустимых диапазонах, определенных выше.

Виртуальный набор популяций V = {vl11 = 1,2,..., nv} опре­деляется набором векторов B = {Bl11 = 1,2,...,nv} при задан­ном общей популяции генотипов П. Пара (Bι1П) определяет одну популяцию vι∈V.

Задается базовый вектор B*. Между B* и каждым из век­торов B/ ∈B установлено взаимно однозначное соответствие Γ(B*, Cl, Bl). Декодирование генотипа Hj∙ ∈П осуществляется с использованием вектора B* и строится базовый фенотип Pj*.

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

Использование виртуального множества популяций на одном наборе генотипов позволяет произвести распараллеливание гене­тического поиска, практически не изменяя пространственной и временной сложности алгоритма

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

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

Итак, достоинством предложенной структуры хромосомы и принципов ее декодирования является:

— отсутствие сложных элементов;

— линейность оценок пространственных сложностей и времен­ных сложностей алгоритма декодирования — O(n);

— расположенность в одних и тех же локусах хромосом и ге­нов — гомологичность;

— возможность формирования виртуального множества попу­ляций для распараллеливания генетического поиска без уве­личения пространственной сложности алгоритма.

13.1.2. Генетические операторы для виртуального мно­жества популяций. Основными генетическими операторами являются: кроссинговер, мутация, а также миграция хромосом между популяциями при распараллеливании процесса генетиче­ского поиска.

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

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

При использовании виртуального множества популяций для каждого l-го фенотипа Φji, соответствующего генотипу Hj, рас­считывается оценка Fji.Таким образом, одному генотипу Hj∙ ∈Π соответствует множество оценок Fj∙ = {Fjl11 = 1,2,...,nv}. Сре­ди оценок Fjiмножества Fj выбирается оценка с максимальным значением, равным Oj, т. е. (Vl)[Oj ≥ Fji]. Эта оценка и будет оценкой генотипа Hj.

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

Поставим в соответствие популяции хромосом Πuпопуляцию лучших генотипов Ru. В состав Ruвходят пары (Bi | Hj) по од­ной для каждой Hj ∈Πu, для которых Fji = Oj. Таким образом, популяции хромосом Πu, на базе которой реализованы процессы генетического поиска, соответствует популяция лучших решений P = {pj}. Эта популяция строятся фактически на базе популяции Ru, которая формируется в свою очередь на наборе виртуальных популяций.

13.1.3. Адаптация виртуального набора популяций. Для увеличения скорости генетического поиска осуществляется адап­тация виртуального набора популяций — адаптация набора B = {Bi 11 = 1,2,...,n}.

Суть заключается в смене опорного вектора Bi, если в те­чение некоторого числа генераций в виртуальной популяции (Bi | П) не появляются индивидуальности с лучшим значением функция качества.

Для реализации механизма адаптации каждому вектору Bi сопоставляется автомат адаптации aiс двумя группами состо­яний. На рис.13.1 приведена граф-схема переходов автомата адаптации.

Рис. 13.1. Граф-схема переходов автомата адаптации

Две группы состояний, S1и S2, соответствуют двум аль­тернативам: A1 = Γ(S1) — вектор Bi остается без измене­ний; A = Γ(⅞) — вектор Bi меняется. Входной алфавит Q = {+, —, R} включает возможные отклики среды: «поощрение» (+) и «наказание» (—), а также сигнал R — возврата.

Выработка управляющих сигналов (+) или (—) осуществля­ется следующим образом.

Обозначим через γι лучшее значение функции качества для виртуальной популяции Vl, т. е. (Vj) [γl≥ Fjl], l = const.

Пусть V∣* — виртуальная популяция, для которой оценка γι худшая (имеет наименьшее значение), которое обозначим как min.

Если в популяции Viпосле выполнения очередной генерации произошло улучшение показателя γi, то вырабатывается сигнал «поощрение» — (+), в противном случае вырабатывается сигнал «наказание» — (—).

Процесс адаптации на каждой генерации реализуется за че­тыре такта:

• на первом такте для всех выбранных популяций рассчиты­вается показатель γi;

• на втором такте вырабатываются отклики среды — сигна­лы (+) или (—);

• на третьем такте под действием откликов осуществляют­ся переходы в автоматах адаптации в соответствии с граф схемой переходов.

Отметим, что в состояние S2 автомат адаптации aiпопадает, если в течение q генераций подряд не было улучшения показателя γi;

• на четвертом такте реализуются альтернативы в соответ­ствии с состояниями автоматов адаптации.

Возможны три варианта реализации альтернатив:

• при первом варианте у всех виртуальных популяций Vi, для которых соответствующие им автоматы адаптации находятся в состоянии S2, осуществляется смена векторов Bi. Сме­на Bl заключается в генерации случайным образом нового вектора Bi. Во всех вариантах после смены вектора Bi на вход автомата адаптации подается сигнал R (возврата), по которому осуществляется переход в группу Si;

• при втором варианте смена Bi осуществляется только в том случае, если γi имеет худшую оценку среди всех остальных;

• при третьем варианте смена вектора Biосуществляется только в том случае, если оценка дляVi имеет худшее значение среди оценок тех виртуальных популяций, для ко­торых автоматы адаптации выдавали команду «сменить». Пусть Bi обозначение вектора до замены, a Bi — после замены.

Смена Bi на Bi осуществляется случайным образом. Между Bi и Bi устанавливается соответствие Γ(Bi, Ci, Bi).

При смене Biанализируется популяция лучших геноти­пов Ru. Если существует пара (Bi, Hj) ∈Ru, то на основе Bi строится генотип Hj такой, чтобы решения piна базе (Bi, Hj) и на базе (Bi, H-) были идентичны. После этого f

в популяции Πuосуществляется смена Hj на Hj-. Таким образом, при смене Bi лучшие решения pi, входящие в по­пуляцию решений P, не изменяются.

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

На каждой генерации последовательно выполняются опера­торы кроссинговера, мутации и редукции (селективный отбор).

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

Ниже представлен псевдокод генетического алгоритма с адап­тацией виртуального набора популяций.

Algorithm ГЕНЕТИЧЕСКИЙ ПОИСК C АДАПТАЦИЕЙ

Begin задача=ИСХ0ДНЫЕ_ДАННЫЕ;

генетика=НАСТРОЙКА;

база=ФОРМ(задача); нач_попул=ГЕНЕРАЦИЯ(задача, генетика); фитнесс=РАСЧЕТ(нач_попул, база, задача);

Т=число_поколений;

While T>0 do

{

крос_попул=0; мут_попул=0;

М=число_крос;

While N>0 do

{

род_пара=ВЫБОР(нач_попул, фитнесс, генетика); доч_пара=КРОССИНГ(род_пара, генетика); крос_попул=ВКЛЮЧИТЬ(крос_попул, доч_пара); N=N-1;

};

фитнесс=РАСЧЕТ(крос_попул, база, задача); тек_попул=ОБЪЕДИНИТЬ(нач_попул, крос_попул); мут_попул=МУТАЦИЯ(тек_попул, генетика); фитнесс=РАСЧЕТ(мут_попул, база, задача); тек_попул=ОБЪЕДИНИТЬ(тек_попул, мут_попул); лучш_реш=ВЫДЕЛИТЬ(тек_попул, фитнесс); база=АДАПТАЦИЯ(база, генетика, фитнесс); T=T-1;

нач_попул=СЕЛЕКЦИЯ(тек_попул, фитнесс);

};

end

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

T — число генераций;

M— объем начальной популяции генотипов;

W— число виртуальных популяций (локусов вектора V);

Pk, Pm— вероятности кроссинговера и мутации;

N— число пар для кроссинговера;

t1— тип селекции при выборе родительской пары;

t2— тип селекции при отборе популяции (редукции).

С помощью процедуры ФОРМ(задача) формируется базовый вектор B*. Затем опять же случайным образом, формируется набор векторов V = {Bi| i = 1,2,...,nv}, определяющий вирту­альное множество популяций. Далее для каждой пары векторов

B* и Biстроятся графики соответствия Ci.Сформированная информация заносится в массив база.

Процедурой ГЕНЕРАЦИЯ(задача, генетика) осуществ­ляется генерация начальной популяции генотипов Π объемом M, включаемой в массив нач_попул. С этой целью в каждой формируемой хромосоме, каждому гену лежащему в локусе t, случайным образом присваивается допустимое значение.

Процедурой РАСЧЕТ(нач_попул, база, задача) рас­считывается функция качества Fji для каждого фенотипа, определяемого парой (Hj,Bi). Затем среди Fjiдля одного Hj выбирается максимальная оценка, которая и будет функцией качества генотипа Hj.

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

Операторы кроссинговера выполняются N раз.

Каждый раз процедурой ВЫБОР(нач_попул, фитнесс, генетика) выбирается родительская пара — род_пара. Выбор род_пара осуществляется одним из способов, задаваемых при постройке механизмов генетического поиска. Это может быть «принцип рулетки», выбор на основе рейтинга и т. д.

С помощью процедуры КРОССИНГ(род_пара, гене­тика) реализуется оператор кроссинговера и образуется пара дочерних хромосом доч_пара, которая процедурой ВКЛЮЧИТЬ(крос_попул, доч_пара) включается в массив крос_попул.

Процедурой РАСЧЕТ(крос_попул, база, задача) рас­считывается значение фитнесса сначала для всех фенотипов, а затем для всех генотипов массива крос_попул. После этого процедурой ОБЪЕДИНИТЬ(нач_попул, крос_попул) массив крос_попул и нач_попул объединяются в тек_попул.

Хромосомы популяции тек_попул подвергаются мутации с помощью процедуры МУТАЦИЯ(тек_попул, генетика), при этом образуется новая популяция мут_попул.

Для каждой индивидуальности массива мут_попул проце­дурой РАСЧЕТ(мут_попул, база, задача), рассчитывается значение фитнесса. Процедура ОБЪЕДИНИТЬ(тек_попул, мут_попул) включает массив мут_попул в массив тек_попул.

Процедурой ВЫДЕЛИТЬ(тек_попул, фитнесс) выбирает­ся лучшее решение лучш_реш, которое запоминается.

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

С помощью процедуры АДАПТАЦИЯ(база, генетика, фитнесс) производится модификация отдельных опорных векторов Bi∈B, что приводит к смене виртуальной популяции Vi ∈V, определяемой парой (Bi| П).

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

Селекция осуществляется процедурой СЕЛЕКЦИЯ(тек_по- пул, фитнесс).

Временные затраты в предела одного поколения складывают­ся из затрат на декодирование хромосом, затрат на операторы кроссинговера, мутации, селекции, расчета фитнесса. Все эти затраты имеют линейную зависимость от числа размещаемых элементов. Отсюда временные затраты в пределах одного поко­ления для популяции объемом M имеют оценку трудоемкости O(n ∙ M).

13.2.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Организация процесса генетического поиска на базе адаптируемого виртуального набора популяций:

  1. 2. Принципы административного процесса
  2. 1.Сущность административного процесса
  3. Тема 13. Административный процесс
  4. 3.3 Исследование процесса спекания алюмокомпозитов системы А1- 3масс.%М-1масс.%Си с наномодификаторами
  5. 3.4 Исследование процесса спарк-плазменного спекания порошковых алюмокомпозитов системы Л1-3масс.%М-1масс.%Си с наномодификаторами
  6. Глава II МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ВЗАИМОДЕЙСТВИЯ СВЕТОВЫХ ПОТОКОВ C ВНУТРЕННИМИ ОБЪЕМАМИ И ПОВЕРХНОСТЯМИ КРИСТАЛЛОВ.
  7. 3. Структура административного процесса. Виды административных производств
  8. Глава 2 ОПЫТ РАЗРАБОТКИ И ИСПОЛЬЗОВАНИЯ УЧЕБНЫХ ЗАДАНИЙ, ОРИЕНТИРОВАННЫХ НА ДОСТИЖЕНИЕ ЛИЧНОСТНЫХ РЕЗУЛЬТАТОВ ШКОЛЬНИКОВ В ПРОЦЕССЕ ОБУЧЕНИЯ
  9. Разработка фондов учебных заданий, обеспечивающих достижение личностных результатов обучения в процессе опытно-экспериментальной работы
  10. 2.Административно-правовой статус организаций
  11. 3.1 Исследование процесса смешивания порошковых смесей системы Al- 3масс.%М-1масс.%Си, А1-4масс.%Си, А1-4масс.%Мд с наномодификаторами
  12. Структурно-функциональная организация оптико­электронного устройства трехмерного технического зрения с множественными источниками изображений
  13. 3. Организация милиции
  14. §1.1 Профессиографический подход к анализу деятельности менеджера коммерческой организации