1.1. Поняття генетичного алгоритму

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

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

Друга причина популярності ГА базується на стрімкому зростанні продуктивності сучасних комп’ютерів.

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

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

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

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

• генетичний алгоритм використовує як імовірнісні правила для породження нових точок пошуку, так і детерміновані правила для переходу від одних точок до інших;

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

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

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

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

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

Батьківська пара, як правило, породжує пару нащадків. Безпосередня генерація нових рядків відбувається за рахунок роботи оператора схрещування двох обраних рядків (випадково-детермінованого обміну), який в процесі роботи алгоритму може застосовуватися не до всіх пар батьків. Частина цих пар може переходити до популяції наступного покоління. Частота виникнення такої ситуації залежить від імовірності застосування оператора схрещування, яка є одним із параметрів ГА.