Генетичні алгоритми і задачі оптимізації

Еволюційна теорія

Генетичні алгоритми ГА (Genetic Algorithms) є складовою еволюційних методів, оскільки виникли у результаті спроб копіювання еволюції живих організмів. Ідея генетичних алгоритмів вперше висловив Дж.Холланд в кінці 60-х років ХХ століття. Суть методу полягала у створенні комп’ютерної програми, яка б вирішувала складні задачі так, як це робить природа - шляхом еволюції. Відповідно у ГА використовують поняття, запозичені з генетики.

Розглянемо принципи генетичних алгоритмів на прикладі класичної задачі комівояжера (TSP - travelling salesman problem). Задача формулюється так: комівояжеру вимагається об'їхати декілька міст, побувавши в кожному один раз, і повернутися в початкову точку. Цільовою функцією є довжина шляху S, яка повинна мінімізуватися. Виявляється, що вже для M=30 міст пошук оптимального шляху традиційними методами (наприклад, перебору) є складною задачею, що спонукало розвиток нових методів (зокрема нейромереж і генетичних алгоритмів).

За допомогою ГА задача вирішується наступним чином. Уявімо собі штучний світ, населений кількістю N істот (особин), причому генетичний код кожної істоти - це деякий розв’язок нашої задачі. Разом всі особини утворюють популяцію Р. Для простоти вважається, що генетичний код кожної особини (генотип) записується у вигляді однієї хромосоми Х (для людини 46 хромосом). Тоді популяція Р={X₁, X_N}

У випадку задачі комівояжера кожний розв’язок або маршрут є рядком з М десяткових чисел, тобто хромосома особини є впорядкованою послідовністю з М генів, де на j-му місці стоїть номерj-го по порядку обходу міста. X={g₁,… g_M}}. Хромосома – числовий вектор, який описує рішення задачі.

В ГА кожний ген записується у вигляді набору R бітів, тому вся хромосома записується набором двійкових чисел (алелів) довжиною L=M*R (подібно до молекули ДНК). Кожен ген кодує певну властивість організму (в людини більше 60 тис. генів)

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

Якщо на початку рішення задачі ми маємо випадковий набір маршрутів (особин), то в процесі еволюції виживуть тільки маршрути з мінімальною довжиною (кращим набором генів X={g₁,… g_M}).

Рис.1. ГА та Задача комівояжера

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

Генетичні алгоритми і задачі оптимізації

За сучасними уявленнями еволюція - це процес постійної оптимізації біологічних видів. В класичних задачах оптимізації можна керувати декількома параметрами (позначимо їх значення через g₁,… g_M), а метою є максимізація (або мінімізація) деякої функції, f(g₁,… g_M). Функція f називається цільовою функцією.

У випадку, якщо цільова функція достатньо гладка і має тільки один локальний максимум (унімодальна), те оптимальне рішення можна одержати методом градієнтного спуску. Ідея цього методу полягає у тому, що оптимальне рішення знаходиться методом ітерацій. Недоліком градієнтного алгоритму є дуже високі вимоги до функції - на практиці унімодальність зустрічається украй рідко, а для інших функцій градієнтний метод – неоптимальний.

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

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

2) виконують пошук рішення виходячи не з однієї точки, а з деякої популяції.

3) використовують тільки цільову функцію, а не її похідні або іншу додаткову інформацію.

4) використовують ймовірнісні, а не детерміновані правила відбору.

Дуже важливим поняттям в ГА є функція пристосованості (fitness function) або функція оцінки, яка дозволяє серед популяції особин виділити найкращих.