Вибір батьківської пари

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

Існує кілька способів вибору батьківської пари.

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

Крок 1. Для вибору пари батьків задається ймовірність схрещування Р_с.

Крок 2. Довільним чином нумеруються всі представники вихідної популяції.

Крок 3. Вибір першого батька: починаючи з першого рішення, проглядається популяція доти, поки випадково обране число з інтервалу [0, 1] не буде меншим, ніж Р_с. Елемент, для якого виконується така умова, стає першим батьком.

Крок 4. Відбувається перегляд популяції, починаючи з наступному після першого батька рішення, поки знову випадково обране число не буде меншим, ніж Р_с. Елемент, для якого виконується така умова, стає другим батьком.

Описаним способом складаються пари доти, поки не вибереться потрібна кількість пар батьків.

Конкретне значення Р_с залежить від розв'язуваної задачі, і в загальному випадку лежить в інтервалі [0,6; 0,99].

Незважаючи на простоту, такий підхід універсальний для розв’язування різних класів задач. Однак він досить критичний до чисельності популяції, оскільки ефективність методу, що реалізує такий підхід, знижується з ростом чисельності популяції.

Інший метод випадкового вибору батьківської пари може бути представлений у вигляді наступної послідовності кроків.

Крок 1. Розбити популяцію випадковим чином на два масиви (підпопуляції) одного розміру.

Крок 2. Відсортувати кожну підпопуляцію.

Крок 3. Сформувати пари для схрещування з особин, що мають однаковий ранг (номер) у підпопуляціях.

Крок 4. Допустити до схрещування пари, для яких випадково згенероване в інтервалі [0;1] число буде перевищувати задану ймовірність схрещування.

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

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

Крім того, для деякого класу задач зі складним ландшафтом фітнесс-функції швидка збіжність може перетворитися в передчасну збіжність до квазіоптимального розв’язку. Цей недолік може бути частково компенсований використанням відповідного механізму відбору, який би “гальмував” занадто швидку збіжність методу.

Інші два способи формування батьківської пари – це інбридингтааутбридинг. Обоє ці методи побудовані на формуванні пари на основі близького й далекого “споріднення”, відповідно. Під “спорідненням” тут розуміється відстань між членами популяції як у сенсі евклідової (геометричної) відстані особин у просторі параметрів (для фенотипів), так і у сенсі відстані Хеммінгу між хромосомними наборами особин (для генотипів).

Евклідова відстань R^(jk) між j-ою та k-ою особинами популяції визначається за формулою:

де p – кількість параметрів (генів) особини;

x_i⁽^j⁾ – i-ий параметр у незакодованому вигляді j-ої особини.

Відстань Хеммінгу H^(jk) між j-ою та k-ою особинами популяції визначається як кількість різних бітів в однакових позиціях j-ої та k-ої хромосом.

Інбридинг складається з двох етапів:

1. Перший член пари вибирається випадково.

2. Другим батьком з більшою ймовірністю буде максимально близька до першого особина.

Один з варіантів процедури інбридингу може бути реалізований у такий спосіб.

Крок 1. Вибрати випадковим чином першого батька.

Крок 2. Вибрати з поточної популяції випадковим чином групу з С хромосом (С = 1%–15% від розміру популяції).

Крок 3. Розрахувати Евклідову відстань від хромосоми, отриманої на першому кроці, до кожної із С відібраних на другому кроці хромосом.

Крок 4. В якості другого батька вибрати найближчу до першого батька хромосому.

Аутбридинг формує батьківські пари з максимально далеких особин.

Використання генетичних інбридингу й аутбридингу є ефективним для багато екстремальних задач. Однак два цих способи по-різному впливають на поводження генетичного методу. Інбридинг можна охарактеризувати властивістю концентрації пошуку в локальних вузлах, що фактично призводить до розбиття популяції на окремі локальні групи навколо підозрілих на екстремум ділянок ландшафту. Аутбридинг, навпаки, спрямований на попередження збіжності методу до вже знайдених рішень, змушуючи метод переглядати нові, недосліджені області.

<== попередня сторінка	\|	наступна сторінка ==>
Турнірний відбір	\|	Оператори схрещування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.002 сек.