strategies)
ГА представляє з себе ітераційний процес, в якому особини спочатку відбираються для схрещування, потім схрещуються, потім з їхніх нащадків формується нове покоління і все починається спочатку. Стратегії відбору є складовою частиною ГА і визначають «гідних» для схрещування особин. Нижче розглядаються декілька найбільш поширених стратегій.
Пропорційний відбір (Proportional selection)
При даному виді відбору спочатку підраховується прісособленность кожної особини fi. Після цього знаходять середню пристосованість в популяції fср як середнє арифметичне значень пристосованості всіх особин. Потім для кожної особини обчислюється відношення fi / fср. Якщо це відношення більше 1, то особина вважається добре пристосованої і допускається до схрещування, в іншому випадку особина, швидше за все, залишиться «за бортом». Наприклад, якщо дріб дорівнює 2.36, то дана особина має подвійний шанс на схрещування і матиме ймовірність рівну 0.36 третього схрещування. Якщо ж пристосованість дорівнює 0.54, то особина візьме участь в єдиному схрещуванні з імовірністю 0.54.
Реалізувати це можна, наприклад, так.
Нехай є масив довічних рядків (популяція) і додатковий масив для особин допущених до схрещування. Визначимо для кожної особини популяції значення описаного вище відносини. Далі, будемо записувати рядки в проміжний масив згідно з наступним правилом: візьмемо цілу частину зрозуміло-якого-відносини і рівно стільки разів запишемо цю рядок у допоміжний масив, після цього за допомогою випадкової величини (СВ) визначимо, чи будемо ми записувати цю рядок ще раз : якщо СВ більше дробової частини відносини, то «так», якщо ні, то «ні». Надалі, особини для схрещування вибираються тільки з проміжного масиву випадковим чином, так що, якщо рядок присутній в ньому в кількох примірниках, то у неї більше шансів «наслідити» в історії ;). Для вже розглянутих прикладів з числами 2.36 і 0.51 ситуація виглядатиме наступним чином: перший рядок запишеться в проміжний масив два рази і з імовірністю 0.36 запишеться втретє. Друга ж рядок має ймовірність рівну 0.51 того, що вона взагалі буде присутній у допоміжному масиві.
Дана стратегія відбору знаменита тим, що саме для неї створена класична теорема шим (ось звідки там дріб).
Турнірний відбір (Tournament selection)
Турнірний відбір може бути описаний таким чином: з популяції, яка містить N рядків, вибирається випадковим чином t рядків і краща рядок записується в проміжний масив (між обраними рядками проводиться турнір). Ця операція повторюється N разів. Рядки в отриманому проміжному масиві потім використовуються для схрещування (також випадковим чином). Розмір групи рядків, що відбираються для турніру часто дорівнює 2. У цьому випадку говорять про довічним / парному турнірі (binary tournament). Взагалі ж t називається чисельністю турніру (tournament size). Чим більше турнір, тим жорсткіший варіант селекції, тобто тим менше шансів у особин, «кому за, або хто просто погано».
Перевагою даної стратегії є те, що вона не вимагає додаткових обчислень та впорядкування рядків у популяції по зростанню пристосованості. Також, на мій погляд, такий варіант селекції ближче до реальності, тому що успішність тієї чи іншої особини в чому визначається її оточенням, наскільки воно краще а...
