ть.
Метою селекції є здійснення вибірки індивідуумів в поточній популяції (тобто з деякого набору) пропорційно їх придатності. Зазвичай використовують чотири різних механізму селекції - колесо рулетки, залишкова стохастична вибірка, стохастична рівномірна вибірка і турнірна селекція. Перші три алгоритму є варіантами пропорційної селекції, а останній - непропорційною.
Заснований на принципі колеса рулетки метод селекції вважається для генетичних алгоритмів основним методом відбору особин для батьківської популяції з метою подальшого їх перетворення генетичними операторами, такими як схрещування і мутація. Незважаючи на випадковий характер процедури селекції, батьківські особини вибираються пропорційно значеннями їх функцій пристосованості: кожній хромосомі зіставлений сектор колеса рулетки, величина якого встановлюється пропорційною значенню функції пристосованості даної хромосоми, тому, чим більше значення функції пристосованості, тим більше сектор на колесі рулетки. Звідси випливає, що чим більше сектор на колесі рулетки, тим вище шанс, що буде обрана саме ця хромосома. Слабка сторона цього методу полягає в тому, що особини з дуже малим значенням функції пристосованості занадто швидко виключаються з популяції, що може призвести до передчасної збіжності генетичного алгоритму. У зв'язку з вищесказаним, створені і використовуються альтернативні алгоритми селекції.
При турнірній селекції всі особини популяції розбиваються на підгрупи з подальшим вибором в кожній з них особини з найкращого пристосованістю. Розрізняються два способи такого вибору: детермінований вибір і випадковий вибір. Детермінований вибір здійснюється з імовірністю, рівної 1, а випадковий вибір - з імовірністю, меншою 1. Підгрупи можуть мати довільний розмір, але найчастіше популяція поділяється на підгрупи по 2-3 особиниу кожній.
Турнірний метод придатний для вирішення завдань як максимізації, так і мінімізації функції. Крім того, він може бути легко поширений на завдання, пов'язані з багатокритеріальної оптимізацією, тобто на випадок одночасної оптимізації декількох функцій. У турнірному методі допускається зміна розміру підгруп, на які поділяється популяція. Дослідження підтверджують, що турнірний метод діє ефективніше, ніж метод рулетки.
При рангової селекції особи популяції ранжуються за значеннями їх функції пристосованості. Це можна уявити собі як відсортований список особин, упорядкованих у напрямку від найбільш пристосованих до найменш пристосованим (або навпаки), в якому кожної особини приписується число, що визначає її місце в списку і зване рангом. Кількість копій кожної особини, введених в батьківську популяцію, розраховується за апріорно заданої функції залежно від рангу особини. Гідність рангового методу полягає в можливості його застосування як для максимізації так і для мінімізації функції.
Існують різні варіанти алгоритмів селекції. Представлені вище методи (рулетки, турнірний і ранговий) застосовуються найчастіше, але існують так звані особливі процедури селекції: елітарна стратегія і генетичний алгоритм з частковою заміною популяції.
Елітарна стратегія полягає в захисті найкращих хромосом на наступних ітераціях. У класичному генетичному алгоритмі самі пристосовані особини не завжди переходять у наступне покоління. Це означає, що нова популяція не завжди містить хромосому з найбільшим значенням функції пристосованості з попередньої популяції. Елітарна стратегія застосовується для запобігання втрати такої особини. Ця особина гарантовано включається в нову популяцію.
Генетичний алгоритм з частковою заміною популяції, інакше званий генетичним алгоритмом з зафіксованим станом, характеризується тим, що частина популяції переходить в наступне покоління без будь-яких змін. Це означає, що входять в цю частину хромосоми не піддавалося операціями схрещування і мутації. Часто в конкретних реалізаціях алгоритму даного типу на кожній ітерації замінюються тільки одна або дві особини замість схрещування і мутації в масштабі всієї популяції.
У даній роботі використовується так звана турнірна селекцію, що не вимагає попереднього ранжирування функції придатності. При цьому послідовно беруться два сусідні елементи поточної популяції (перший і другий, третій і четвертий і т.д.) і кращий з них (тобто елемент, що володіє меншим значенням цільової функції або функції придатності) поміщається в проміжну популяцію P '. Після першого проходу (поки сформована тільки половина проміжної популяції) вихідна популяція випадковим чином перемішується і описаний процес повторюється ще один раз. Тут кращі чи гірші індивідууми розглядаються в сенсі їх упорядкування згідно відповідним значенням цільової функції.
Селекція граємо важливу роль, так як ГА працюють з сукупністю особин...
