Оператори вибору батьків

Опера́тори ви́бору батькі́в — це елемент генетичного алгоритму, який відповідає за спосіб вибору батьків із популяції. Існує кілька підходів до вибору батьківської пари. Найпоширенішими операторами вибору батьків та пар для схрещування є наступні:

• Вибір пар для схрещування:

1. Панміксія;
2. Інбридинг;
3. Аутбридинг;
4. Селекція.

• Оператори вибору батьків:

1. Турнірний відбір;
2. Пропорційний відбір (рулеточний);
3. Ранжування;
4. Локальний відбір (часткова заміна);
5. Метод усічення;
6. Метод Больцмана;
7. Елітарний метод.

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

Панміксія

Панміксія — найпростіший оператор відбору. Відповідно до нього, популяцію нумерують числом з відрізку $[1;n]$ (де $n$ — кількість особин в популяції), потім кожному номеру ставиться у відповідність інший, випадково обраний з того ж відрізку, номер. Будемо розглядати ці пари чисел як номери особин, які візьмуть участь у схрещуванні. При такому виборі пари із однаковими номерами не схрещуються. Якісь члени популяції візьмуть участь у процесі відтворення неодноразово з різними особинами популяції. Незважаючи на простоту, такий підхід універсальний для вирішення різних класів задач. Але він досить критичний до чисельності популяції, оскільки ефективність алгоритму, що реалізує такий підхід, знижується зі зростанням чисельності популяції.

Приклад (пари відсортовано для зручності):

Номери популяції	[1, 2, 3, 4, 5]
Відповідна множина	[3, 2, 2, 2, 1]
Утворені пари	(1, 3), (3, 2), (4, 2), (5, 1)
Відсортовані пари	(1, 3), (1, 5), (2, 3), (2, 4)

Інбридинг

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

Хромосоми популяції	Кількість різних локусів
1000000	2
1010101	1
1111111	4
1100001	2
0000000	3

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

Аутбридинг

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

Селекція

Селекція полягає в тому, що батьками можуть стати тільки ті особини, значення пристосованості яких не менше порогової величини, наприклад середнього значення пристосованості по популяції. Такий підхід забезпечує швидшу збіжність алгоритму. Проте, через швидку збіжність селективний вибір батьківської пари не підходить тоді, коли ставиться завдання визначення декількох екстремумів, оскільки для таких завдань алгоритм, як правило, швидко сходиться до одного з рішень. Крім того, для деяких багатовимірних завдань зі складним ландшафтом цільової функції швидка збіжність може мати невірний розв'язок. Цей недолік може бути частково компенсований використанням відповідного механізму відбору, який би «гальмував» занадто швидку збіжність алгоритму. Порогова величина в селекції може бути обчислена різними способами. Тому в літературі для генетичного алгоритму виділяють різні варіації селекції. Найбільш відомі з них — це турнірний і рулеточний (пропорційний) відбори.

Турнірний відбір

При турнірному відборі (tournament selection) з популяції, яка складається із $N$ особин, вибираються випадковим чином $t$ особин, і найкраща особина записується в проміжний масив. Ця операція повторюється $N$ раз. Особини в отриманому проміжному масиві потім використовуються для схрещування (також випадковим чином). Розмір групи рядків, що відбираються для турніру, часто дорівнює 2. У цьому випадку говорять про двійковий (парний) турнір. Взагалі ж $t$ називають чисельністю турніру. Перевагою даного способу є те, що він не вимагає додаткових обчислень. Файл:Tournire.jpg

Рулеточний відбір

У методі рулетки (roulette-wheel selection) особини відбираються за допомогою $N$ «запусків» рулетки, де $N$ — розмір популяції. Колесо рулетки містить по одному сектору для кожного члена популяції. Розмір $i$ -го сектору пропорційний ймовірності попадання в нову популяцію $P(i)$. При такому відборі члени популяції з більш високою пристосованістю з більшою ймовірністю будуть частіше вибиратись, ніж особини з низькою пристосованістю.

Популяція із 5 особин	Придатність	Ймовірність вибору
$C_{1}$	52	$52/200=0,26$
$C_{2}$	85	$85/200=0,425$
$C_{3}$	37	$37/200=0,185$
$C_{4}$	3	$3/200=0,015$
$C_{5}$	23	$23/200=0,115$

Елітарний

Основне правило методу: особи з найкращими фітнес функціями стають "елітою", вони гарантовано проходять на наступне коло алгоритму.

Часткова заміна

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

Ранжування

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

Метод Больцмана

Вводиться "температурна" константа.

Метод усічення

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

Посилання

• Генетичні алгоритми. Т. В. Панченко