17.10. Стандартний генетичний алгоритм

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

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

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

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

Методи нормалізації розглянуто у праці Л. Девіса (Davis., 1991 р.). Іншим методом, що підтримує генетичну різноманітність популяції, є паралельний ГА (Miihlenbein et al., 1991). У деяких ГА застосовуються витонченіші стратегії селекції. Наприклад, нащадкам дозволяється входити в нову популяцію тільки в тому разі, якщо вони значно відрізняються від решти членів популяції. З метою підтримки достатньої генетичної різноманітності частина створених (відібраних) хромосом може бути впроваджена в наступне покоління до досягнення популяцією наперед заданого бажаного розміру. Проте методи, які знижують вірогідність звироднілості популяції та сприяють отриманню глобального рішення, пов’язані з необхідністю обчислення ступеня подібності між індивідуумами. Для складних завдань такі розрахунки виконувати, як правило, небажано. Тому розроблено більш довершені стратегії. Одна з них припускає залучення додаткового, конкуруючого з основним, ГА, який виводить так званих «паразитів».

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

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

З біології відомо, що генетичний код організму називається його генотипом, а його фізична реалізація — фенотипом. Ці

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

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

17.10. Стандартний генетичний алгоритм

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

Під стандартним ГА розуміється метод стохастичної оптимізації для вирішення завдань дискретної оптимізації вигляду:

Максимізувати f(s) за умови, що s ? ? = {0, 1} L , де f : ? ? R називається функцією придатності (або фітнес-функцією), s ? ? — хромосома довжини L, ? — популяція, R — множина дійсних чисел (??, +?).

та інші визначення є базовими в термінології ГА, що не означає точного спадкоємства біологічних процесів, а лише в деякому наближенні, ГА можна вважати моделлю біологічних процесів. У біологічній хромосомі інформація закодована в ланцюжку ДНК, що складається з довгої послідовності чотирьох складових: аденіну, цитозину, гуаніну і тиміну. Початковий генетичний код організму записують, використовуючи чотири букви (А, С, G, Т) алфавіту. У ГА хромосома представлена рядком, записаним у двоелементному алфавіті, що складається з нуля і одиниці.

Фітнес-функція найчастіше є цільовою функцією. Цільова функція — це функція, оптимум якої треба знайти. Але на практиці іноді виникає потреба трансформувати цільову функцію у фітнесфункцію, тобто у функцію придатності. Але оскільки поняття цільової і фінтнес-функції часто збігаються, то далі вони використовуються як синоніми.

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

Подальша робота ГА є ітераційним процесом, який триває доти, поки не буде виконано задане число поколінь або який-небудь інший критерій зупинки.

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

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

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

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

17.11. Перехресне схрещування

Оператор схрещування у генетичному програмуванні виконується так.

Крок 1. Вибрати випадковим чином на кожному з батьківських дерев одну або декілька точок (вузлів дерева подань рішень).

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

— при виборі точок перетину необхідно враховувати, що одержані в результаті схрещування нащадки мають зберегти синтаксичну структуру. Тому під час реалізації складних мов можуть виникати проблеми з вибором сумісних точок перетину;

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

Крок 2. Виконати генерацію нащадків. Для цього необхідно змінити у початкових програмах фрагменти дерев відповідно до вибраних на попередньому кроці точок розриву. Існує величезна кількість генетичних операторів (Genetic operator), проте тільки деякі використовуються для розв’язання загальних задач. Перехресне схрещування і мутація, про які йтиметься нижче, є прямими аналогами природних процесів.

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

Одноточкове схрещування. Це класичний варіант. Випадковим чином вибирається число, що належить інтервалу(1, L-1), де L — розмір хромосоми, так зване точкою схрещування або точкою розриву, і всі гени, починаючи з наступного після точки розриву до останнього включно, переставляються у вибраних хромосомах. Наприклад, з точкою розриву:

1001010? 100~1010 ? 00~1101? 1001101

0101101? 010~1101 ? 10~1010 ?0101010 n-точкове схрещування.

За такого способу випадково вибираються n точок розриву, що приводить до розбиття початкових векторів на n + 1 частин різної довжини. Далі пропонується змінити у початкових хромо-

1001010 ?1~00~10~10 ? 1~10~10~01 ?1101001

0101101? 0~10~11~01 ? 0~00~11~10 ?0001110

Окремим випадком є двоточкове схрещування.

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

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

Наприклад, маска схрещування = (1001011), тоді

1100110? 1100110 ? 1110010

0110001? 0110001 ? 0100101

Після розгляду всіх операторів схрещування слід зазначити, що різні типи схрещування володіють загальною позитивною властивістю: вони контролюють баланс між подальшим використанням уже знайдених хороших підобластей простору пошуку і дослідженням нових підобластей. Це досягається за рахунок неруйнування загальних блоків усередині хромосом-батьків і одночасного дослідження нових областей у результаті обміну частинами рядків (хромосом).

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

Виходячи з їх емпіричних міркувань, було встановлено, що найбільш прийнятними значеннями вірогідності схрещування є: 0,6 ? Р к?

0,99.

сомах ділянки з парними номерами, а ділянки з непарними залишити без змін:

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

17.12. Мутація

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

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

В еволюційному програмуванні у разі використання як особин скінченних автоматів застосовуються такі способи реалізації оператора мутації:

— зміна завершального стану;

— зміна умови переходу з одного стану в інший;

— додавання нового стану;

— видалення стану;

— зміна початкового стану.

У процесі мутації з ненульовою вірогідністю чергове рішення може перейти в будь-яке інше рішення. Зауважимо, що модифікація рішення може полягати не тільки у випадковій мутації, але й у частковій перебудові рішення алгоритмами локального пошуку. Застосування локального спуску дозволяє ГА зосередитися тільки на локальному оптимумі. Безліч локального оптимуму може виявитися експоненціально великою і на перший погляд здається, що такий варіант алгоритму не матиме великих переваг. Проте експериментальні дослідження розподілу локального оптимуму свідчать про високу концентрацію їх у безпосередній близькості від глобального оптимуму. Це спостереження відоме як гіпотеза про існування «ве-

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

Мутація інвертуванням

Алгоритм мутації такий. Спочатку нумеруються довільним чином усі представники початкової популяції. Потім, починаючи з першого гена першої хромосоми, є видимою вся популяція, при цьому вибираються випадкові числа з інтервалу [0, 1]. Якщо на деякому кроці вибране число виявляється меншим P m , то поточний ген піддається мутації.

У деяких реалізаціях алгоритму оператор мутації є інверсією тільки одного випадково вибраного біта хромосоми.

Мутація відстанню

Програмно операцію мутації реалізують за допомогою генератора випадкових чисел. За великих розмірів популяції І/АБО бітових рядків ця операція істотно підвищує обчислювальну складність алгоритму. Тому замість того, щоб обчислювати мутацію для кожного біта, розраховуємо відстань від поточного біта за формулою:

ликої долини» для завдань на мінімум або «центрального гірського масиву» для завдань на максимум.

Біт, віддалений на обчислену відстань, інвертується. Поріг вірогідності мутації у такому разі вибирається в інтервалі 0.0075?0.0085.

Мутація шляхом обміну

Випадковим чином обираються дві позиції в хромосомі, і елементи, що стоять на них, міняються місцями:

0101001 ?0~1~01~0~01 ? 0~0~01~1~01 ?0001101

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

— 132, вибрана позиція — 6):

00011111? 000~11111 ? 11111~ 000 ?11111000

Мутація із збільшенням (grow mutation)

Крок 1. Випадковим чином вибрати вузол дерева подань програм для виконання мутації.

Крок 2. У вибраному вузлі побудувати нову гілку програми відповідно до семантики використовуваної мови.

Мутація із стисненням (shrink mutation)

Крок 1. Випадковим чином вибрати вузол дерева подань програм для виконання мутації.

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

Мутація із заміною (switch mutation)

Крок 1. Вибрати випадковим чином дві гілки дерева подань програм для виконання мутації.

Крок 2. Поміняти вибрані гілки місцями. При цьому необхідно забезпечити синтаксичну правильність одержуваної програми.

Циклічна мутація (cycle mutation)

Крок 1. Вибрати випадковим чином вузол дерева подань програм для виконання мутації.

Крок 2. Випадковим чином замінити вибраний вузол на вузол того самого типу.

Мутація із зміщенням

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

513264789 5~132~64789 ? 789561324

Мутація із зміщенням і мутація інвертуванням також називаються операторами інвертування, оскільки змінюють порядок проходження символів у ділянках хромосом. Коли використовуються ці методи, гени мають містити деяку «мітку», так, щоб їх можна було правильно ідентифікувати незалежно від їхньої позиції в хромосомі. Мета переупорядковування полягає в тому, аби спробувати знайти порядок генів, який має кращий еволюційний потенціал. Багато дослідників використовували інверсію у своїй роботі, хоча здається, що небагато з них спробували її обґрунтувати або визначити її внесок. Гольдберг і Бріджес аналізують оператора переупорядковування на дуже маленькому завданні, показуючи, що вона може дати певну перевагу, хоча вони вважають, що їхні методи не принесли б такої самої переваги на великих завданнях. Переупорядковування також значно розширює область пошуку. Мало того, що ГА намагається знаходити безліч значень генів, він також одночасно пробує знаходити хороше впорядкування генів. Це набагато важче завдання для вирішення.

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

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

Зазвичай спочатку задається вірогідність мутації Р m . Конкретне значення Р m залежить від розв’язуваної задачі та в загальному випадку знаходиться в інтервалі [0.001, 0.01]. Слід зазначити, що, скоріше за все, вірогідність мутації не повинна бути константою. Роль оператора мутації різко зростає, наприклад, якщо популяція збиткова у «генетичному» сенсі. У такому разі схрещування не дає поліпшення, і тоді мутація може допомогти змінити ситуацію. Інверсія, транслокація, транспозиція, делеція і дуплікація належать до різновидів хромосомної мутації. Під час інверсії ділянка хромосоми повертається на 180 ° . Клітини при інверсіях зберігають нормальну життєздатність, окрім тих випадків, коли виявляється ефект положення гена, тобто деякі гени у разі зміни положення в хромосомі можуть надавати несприятливу дію на життєздатність. Транслокацією називають перенесення частини однієї хромосоми в іншу. При переміщенні невеликих ділянок генетичного матеріалу в межах однієї хромосоми використовують термін транспозиція. Транспозиції — також переміщення генетичного матеріалу між хромосомами або в межах однієї хромосоми, проте цей термін зазвичай застосовують до переміщень невеликих ділянок генетичного матеріалу, зіставних за протяжністю з геном. Делеція — це випадання окремих ділянок хромосом, дуплікація — повторення ділянки генетичного матеріалу. Дефішенси, або кінцеві шлюби (також втрата інформації). Вони зазвичай викликають зниження життєздатності особини.

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

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

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

Наприкінці 1940-х — на початку 1950-х років А. Новік і Л. Сциллард виявили, що частота мутацій пропорційна тривалос-

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

Відбір

Пропорційна репродукція (у деяких джерелах носить назву пропорційно-імовірнісної репродукції).

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

Пропорційна репродукція призначає кожній структурі вірогідність P s (i), дорівнює відношенню її пристосованості f(i) до сумарної пристосованості популяції: ? = = n i s if if iP

1 )( )( )(.

Як особливі процедури репродукції можна розглядати так звану стратегію і ГА з частковою заміною популяції.

Елітарна стратегія (elitist strategy) полягає в захисті якнайкращих хромосом на подальших ітераціях. У класичному ГА самі пристосовані особини не завжди переходять у наступні покоління. Це означає, що нова популяція Р(k + 1) не завжди містить хромосому з найбільшим значенням функції пристосованості з популяції Р(k). Елітарна стратегія застосовується для запобігання втрати такої особини. Ця особина гарантовано включається в нову популяцію.

ті клітинної генерації, а не числу ділень; тобто мутації можуть відбуватися не тільки при подвоєнні генів. Ще в кінці 1920-х років запропоновано розглядати мутабельність як адаптивну ознаку виду. Очевидно тільки, що мутабельність, як і всі інші ознаки організму, є об’єктом природного відбору.

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

Батьківські пари можна вибирати у такий спосіб:

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

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

Аутбридинг — пари формуються аналогічно, але із максимально далеких членів популяції.

Розрізняють фенотипний і генотипний інбридинг та аутбридинг. Існує два механізми відбору членів нової популяції: елітний та відбір з витисненням. За елітного відбору нова популяція складатиметься лише із найкращих членів репродукційної групи, до якої входять батьки, потомки і мутанти. При відборі з витісненням те, чи буде член репродукційної групи заноситись у нову популяцію, визначається не тільки ступенем її пристосованості, але й тим, чи є у новій популяції член з аналогічним набором хромосом.

Потім відбувається відбір (із заміщенням) усіх n особин для подальшої генетичної обробки, згідно з величиною P s (i). Простий пропорційний відбір — рулетка — відбирає особини за допомогою n «запусків» рулетки.

Колесо рулетки містить по одному сектору для кожного члена популяції. Розмір i-го сектору пропорційний відповідній величині P s (i). Особина одержує нащадків, якщо число, що випадково згенерувало, у межах від 0 до 2 потрапляє в сектор, відповідний цій особині. За такого відбору члени популяції з вищою пристосованістю з більшою вірогідністю частіше вибиратимуться, ніж особини з низькою пристосованістю. Імовірнісний вибір особини в турнірній репродукції деякою мірою дозволяє виключити передчасну втрату популяцією різноманітності. Схема рулетки може давати дуже великі похибки в

Турнірна репродукція

Вище розглядався метод імовірнісного вибору: чим краще здоров’я хромосоми, тим більша вірогідність, що її буде обрано для формування наступного покоління. Проте трудність імовірнісного вибору полягає в тому, що може відсіватися навіть здорова хромосома. Щоб гарантувати рекомбінування найздоровіших хромосом, можна використовувати метод еліти, котрий полягає в автоматичному переносі певної кількості (наприклад, 10 %) найздоровіших хромосом у наступне покоління.

За методом турніру з популяції обирають дві або кілька хромосом, які потім змагаються за право потрапити в наступне покоління. Перемагає та хромосома, здоров’я якої міцніше. Турнір повторюється два рази, у результаті обираються два батьки, які переходять у наступне покоління.

Турнірний відбір реалізує k турнірів, щоб вибрати k особин. Кожен турнір побудований на вибірці m елементів з популяції, і вибору кращої особини серед них. Найбільш поширений турнірний відбір з m = 2.

Турнірна селекція має певні переваги перед пропорційною, оскільки не втрачає своєї вибірковості, коли в прцесі еволюції всі елементи популяції стають приблизно рівними за значенням цільової функції. Чисельність популяції є досить важливим елементом ГА. Якщо популяція занадто мала, генетичного матеріалу може не вистачити для розв’язання даної проблеми.

Репродукція ранжируванням

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

1 )([ )( minmaxmax ? ? ?????= n i n iP s , де ? min = 2 – ? maх і 1 ? ? maх ? 2.

1

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

в) рівномірне ранжирування ? ? ? ??µ µ??µ = ,0

11 ni, , i, / (i) P s де µ — деяке фіксоване число перших членів популяції.

Як бачимо, схема пропорційного відбору збігається за своєю ідеєю з методом колеса рулетки. Ця та інші вказані вище схеми відбору мають такі недоліки: якнайкраща хромосома в популяції може бути втрачена в будь-якому поколінні й немає якої-небудь гарантії, що результати еволюції, досягнуті у ряді поколінь, не будуть втрачені. Одним із способів подолання цього є використання елітного відбору, який завжди зберігає якнайкращу хромосому популяції. Даний вид відбору гарантує асимптотичну збіжність рішення до глобального оптимуму. У деяких реалізаціях алгоритму застосовується так звана стратегія елетизму, яка полягає в тому, що особини з найбільшою пристосованістю гарантовано переходять у нову популяцію. Використання елетизму зазвичай дозволяє прискорити збіжність ГА. Недолік використання стратегії елетизму в тому, що підвищується вірогідність потрапляння алгоритму в локальний мінімум. в) рівномірне ранжирування ? ? ? ??µ µ??µ = ,0

11 ni, , i, / (i) P s де µ — деяке фіксоване число перших членів популяції.

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