І) схрещування

.

На практиці часто приймають е =0.

Найчастіше використовують комбінований критерій, який сполучає всі три або будь-які два з наведених вище критеріїв.

ж) вибір (відсівання)

На даному етапі з популяції відбираються більш пристосо­вані особини, інші (менш пристосовані) відсіваються й у пода­льших перетвореннях не використовуються. Критерієм відбору є значення функції пристосованості кожної окремо взятої особини (хромосоми).

Операція вибору (відсівання) може здійснюватися з різною періодичністю й при різних умовах.

Регулярне відсівання – проводиться в кожній епосі.

Періодичне відсівання – проводиться через фіксовану або ви­падкову кількість епох.

Розмір популяції може бути фіксованим або змінним. У ви­падку змінного розміру популяції, варто погодити параметри ГА, які визначають параметри відсівання особин з популяції, з параметрами які визначають розмір нової популяції після репро­дукції для виключення неконтрольованого зменшення або збі­льшення популяції. Сам механізм відбору може бути одним з наступних видів:

1. Випадковий. Менш ефективний чим інші, тому що не вра­ховує значення ФП особин при їхньому відборі. Відбір прово­диться абсолютно випадково (за рівномірним законом). Даний механізм відбору доцільно використовувати при дослідженні самого ГА, але не при рішенні конкретних прикладних задач.

Риунок 9.5 – Оператор селекції типу колеса рулетки з

пропорційними функції пристосованості секторами

2. Випадковий відбір пропорційно значенню ФП («рулетка»). Реалізується відбір N особин, причому ймовірність відбору кожної конкретної особини пропорційна її пристосованості. Краща метафора цієї стратегії – рулетка. Нехай кожній особині популяції відповідає свій сектор рулетки. Розмір сектора про­порційний пристосованості особини (для визначення розміру сектора на відрізку 0–1 можна скористатися нормалізацією при­стосованостей особин популяції). Тепер, необхідно лише N раз «розкрутити» рулетку й подивитися де зупиниться кулька (рисунок 9.5).

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

3. Елітний відбір. Даний підхід може бути реалізований по різному, однак загальна його ідеї полягає у виборі певної час­тини найбільш ефективних особин, випадковий фактор виклю­чається. Можливі наступні варіанти: після ранжирування осо­бин за значенням ФП здійснюється відбір фіксованої кількості (або певної частки) найкращих особин; здійснюється відбір осо­бин значення ФП яких перевищує деякий поріг (наприклад сере­днє значення ФП у популяції) і деякі інші. За умови незмінної чисельності популяції застосування принципу переважного розмноження більш пристосованих призводить до трохи несподіваного результату – у популяції розмножу­ються не самі особини, а гени. Власне кажучи, це еквівалентно зниженню рівня розгляду системи: ми оперуємо не особинами, а генами. Гени борються один з одним за виживання, сильні витісняють із генофонду популяції слабких.

4. Турнірний відбір. Реалізує n турнірів, щоб вибрати n осо­бин. Кожний турнір побудований на вибірці k елементів з попу­ляції, і вибору кращої особини серед них. Найпоширеніший тур­нірний відбір з k=2.

5. Відбір з витисненням (з урахуванням схожості генотипів). Даний механізм – спроба вдосконалення елітного відбору. Для пояснення механізму відбору з витисненням введемо поняття «близькі родичі» і «далекі родичі», ці поняття будуть використо­вуватись нами й надалі. Під «близькими родичами» будемо ро­зуміти особин популяції які мають відносно близьке розташу­вання (євклідову відстань) у просторі генотипів. Відповідно «да­лекими родичами» будемо називати особин які мають відносно велике значення євклідової відстані в просторі генотипів (роз­гляд близькості особин у просторі фенотипів припустиме, однак за результатами практичних досліджень менш ефективне).

Відбір з витисненням припускає включення до складу попу­ляції найбільш ефективних особин, але при цьому з популяції виключаються «близькі родичі». Таким чином, у новій популяції залишаються найбільш ефективні хромосоми й при цьому ви­ключається виродження популяції (що полягає в сильній або аб­солютній схожості всіх генотипів). Виродження популяції хара­ктерне для елітного відбору й призводить до передчасного схо­дження ГА до локального екстремуму.

6. У деяких роботах [4-9] пропонується виключення операції відбору як такого. Замість цього вводиться спеціальне поняття – «тривалість життя хромосоми» або «вік хромосоми» – параметр LT. Значення параметра LT дорівнює кількості епох протягом яких буде існувати хромосома, після чого вона виключається з популяції. Розглянемо кілька можливих стратегій обчислення LT. Параметр LT для i–ої особини можна визначити на основі:

1) пропорційного випадкового впорядкування;

2) лінійного впорядкування;

3) нелінійного впорядкування.

У випадку 1–ої стратегії використовується підхід при якому LT для окремої особини (хромосоми) визначається випадково, але пропорційно значенню відповідної ФП, на зразок методу «рулетки».

У випадку 2–ої стратегії LT обчислюється відповідно до зна­чень ФП відносно найкращого значення ФП: чим більше ФП – тим довше життя хромосоми (у відмінності від 1–ої стратегії ви­ключається випадковий фактор).

3–я стратегія припускає обчислення значення параметра LT на підставі деякої функції подібної тим, що використовується при масштабуванні ФП.

Вік хромосом впливає на чисельність популяції на кожному етапі еволюційного процесу. Певні автори вважають, що такий підхід є більш «природним», чим використання механізмів від­бору.

з) генетичні перетворення (репродукція)

Після етапу відбору необхідне відновлення чисельного складу популяції, етап відновлення популяції одержав назву репродукції. Репродукція здійснюється з використанням генетичної операції схрещування (9.5.9). З огляду на те, що операція мутації (9.5.10) дозволяє змінювати хромосоми, тобто одержувати по суті нові хро­мосоми, її так само можна віднести до етапу репродукції.

Параметри репродукції (коефіцієнти схрещування й мутації) по­винні бути погоджені з параметрами які характеризують етап від­бору для виключення неконтрольованого неприпустимого змен­шення або збільшення популяції.

Нові особини отримують шляхом комбінації властивостей бать­ків. Як і в природньому процесі еволюції, ступінь участі в репродук­тивному процесі для кожної особини визначається значенням кри­терію якості: кандидати з більше високим значенням критерію яко­сті беруть участь у процесі відтворення з більш високою ймовірні­стю. Як ми вже відзначали, вибір здійснюється на основі імовірніс­них законів, коли слабкі члени популяції мають меншу ймовірність відтворення, однак така можливість не виключається. Виживання деяких слабких особин має важливе значення для розвитку популяції, оскільки вони можуть містити деякі важливі компоненти рішення.

Оператор схрещування (crossover) здійснює обмін частинами хромосом між двома (трьома й більше) хромосомами в популя­ції. Може бути одноточковим або багатоточечним.

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

Розглянемо види відбору батьків для схрещування.

Без відбору. Випадковий вибір. Граничний вибір. Пропорційно значенню функції пристосованості. Турнірний відбір. За принципом «споріднення».

Сама операція схрещування може бути здійснена з викорис­танням одного з наступних підходів:

– одноточкове;

– багатоточкове;

Рисунок 9.6 – Одноточковий оператор схрещування (точка розриву дорівнює чотирьом)

Рисунок 9.7 – Багатоточковий оператор схрещування (використову­ються дві крапки схрещування: на 2–ій і 5–ій позиції)

– рівномірне (імовірнісне);

– однорідне (по «масці»);

– полігамне.

Одноточкове схрещування працює в такий спосіб. Спочатку, випадковим чином обирається одна з точок розриву. Точка розриву – проміжок між сусідніми бітами в рядку. Обидві бать­ківські хромосоми розриваються на два сегменти відносно точки розриву. Після чого сегменти різних батьків «склеюються» між собою, в результаті отримаємо два генотипи нащадків (Рисунок 9.6).

Хромосома-батьки можуть розбиватися в будь-якій крапці, яку можна вибирати й змінювати випадковим образом у ході рішення завдання.

Багатоточкове схрещування здійснюється як одноточкове, але припускає багаторазове перехрещування ділянок хромосом між собою. Кожна точка схрещування обирається випадково. Так само випадково може обиратися й кількість крапок схрещу­вання (або визначатись певна послідовність виконання схрещу­вань з різною кількістю точок скрещування). Кожна хромосома-нащадок являє собою послідовність ділянок батьківських хромо­сом, що чергується між собою (рисунок 9.7).

Рисунок 9.8 – Імовірнісний оператор схрещування (обмін окремими бітами відбувся в 3–їй і 5–ої позиції)

Імовірнісне (рівномірне) схрещування припускає, що хромо­соми-батьки здійснюють побітний обмін з деякою ймовірністю. Так, наприклад, при ймовірності 0,8 (яка так само може визнача­тись випадковим чином для кожного схрещування, або за пев­ним алгоритмом) у першій хромосомі-нащадку в кожній позиції з імовірністю 0.8 будуть залишені біти 1-ої хромосоми-батька, і з імовірністю 0.2 біти 2-ої хромосоми-батька. А в другий хромо­сомі-нащадку навпаки (рисунок 9.8).

Рисунок 9.9 – Однорідний оператор схрещування («по масці»)

Однорідне схрещування («по масці»). Кожний біт у потом­стві створюється за допомогою копіювання відповідного біта від першого або другого батька, обраного згідно випадково (або за певним алгоритмом) згенерованої маски кроссинговера. Якщо в масці кроссинговера розташована 1, то біт копіюється від першого батька, якщо в масці розташований 0, то біт ко­піюється від другого батька. Нова маска кроссинговера ви­падково генерується для кожної пари батьків (рисунок 9.9).

Так само окремо слід зазначити можливість полігамного схрещування, тобто використання при схрещуванні більше 2-х хромосом. При цьому завжди кількість хромосом–нащадків дорі­внює кількості хромосом-батьків (рисунок 9.10).

Рисунок 9.10 – Операція полігамного схрещування (кількість хромо­сом, що схрещуються, дорівнює 3, схрещування проведене в 3-їй і 5-ої позиції)

При використанні специфічних видів кодування необхідно використати спеціально адаптовані операції схрещу­вання.

Операція схрещування забезпечує три види комбінативної мінливості хромосом:

– за рахунок випадкового вибору батьків;

– за рахунок схрещування у випадковій точці (точках);

– за рахунок випадкового накладення домінантно–рецесивних ознак (у випадку диплоідного кодування).

Дата добавления: 2014-01-04