ння, а деяка підмножина квазіоптимальних рішень, називаються хромосомами і складаються з генів. Це підмножина носить назву "популяція". Оптимальність рішення, закодованого в кожній хромосомі, оцінюється за допомогою обчислення цільової функції. p align="justify"> На початку роботи алгоритму випадковим чином формується початкова популяція, що складається із заданого числа хромосом.
Після формування початкової популяції, здійснюється процес синтезу нових рішень (поколінь) завдання за допомогою кросинговеру (схрещування) і мутації. Вихідними даними для нього є хромосоми поточної популяції. Досліджувана в деякий момент часу популяція називається поточною. На початку роботи алгоритму поточна популяція збігається з початковою. br/>В
Розгорнута схема роботи ГА
Операція кросинговеру відбувається наступним чином. Випадковим чином серед хромосом ті покоління вибираються пари батьків, причому ймовірність вибору хромосом з кращими значеннями цільової функції повинна бути вище. Далі відбувається розрив двох батьківських хромосом і рекомбінірованіе утворилися хромосомних відрізків. Мутації, тобто випадкові зміни деяких хромосом, відбуваються по деякому правилу (наприклад, із заданою вірогідністю) і служать для виключення застрявання пошуку в обмеженому підпросторі. br/>В
Кросовер
Очевидно, що не будь-який результат кросинговеру виявляється припустимою хромосомою. Тому після кросинговеру необхідно проводити перевірку хромосоми на допустимість шляхом перевірки на обмеження. br/>В
Мутація
Після схрещування і мутації розмір популяції збільшується. Однак для наступних перетворень необхідно скоротити число хромосом поточної популяції. Така процедура носить назву селекції. У поточній популяції, що складається з батьків і нащадків, проводиться відбір кращих рішень, тобто хромосом з найкращим значенням цільової функції. Ця функція показує, наскільки досліджувана хромосома близька до оптимального рішення. Для поточної популяції повторюються всі описані процедури. Процес продовжується до тих пір, поки не буде оброблено задане число поколінь. При цьому кожна наступна популяція повинна бути краще, ніж попередня. Вирішенню завдання відповідає хромосома з найкращим значенням цільової функції. p align="justify"> Генетичні алгоритми мають такими справді унікальними перевагами:
Гј Дозволяють вирішувати задачу з будь-якою кількістю точок.
Гј Дозволяють распараллеліть задачу.
Гј Припускають обмеження вирішення задачі, як за часом, так і по заданому значенню критерію.
Гј Мають високою швидкодією і можуть використовувати рішення, отримані іншими методами, як початкові наближення з ї...
