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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

  • Панміксія
  • Інбридинг
  • Аутбридинг
  • Селекція
    • Турнірний відбір
    • Рулеточний відбір

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

Панміксія[ред.ред. код]

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

Інбридинг[ред.ред. код]

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

Посилання[ред.ред. код]