Задачі оптимізації/ У яких випадках застосування інструментарію генетичного алгоритму є ефективнішим за традиційні методи оптимізації

Зада́ча оптиміза́ції — задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції.

Нехай задано деяку множину X із n -вимірного евклідового простору і функцію f(x), визначену на X. Необхідно знайти точки мінімуму значень функції f(x) на X. Або: f(x) → min, x є X., тут f(x) — цільова функція, X — допустима множина, кожна точка x цієї множини — допустима точка задачі.

Також, задачу оптимізації можна сформулювати як пошук максимуму (максимумів) цільової функції:

f(x) → max, x є X. - ця задача еквівалентна попередній задачі мінімізації цільової функції із знаком мінус, в тому сенсі, що множини їхніх розв'язків збігаються.

Розв'язки задачі можна розділити на дві множини:

глобальні (глобального мінімуму) - це такі допустимі точки x* в яких цільова функція має найменше значення на всій допустимій області: f(x*) ≤ f(x), ∀ x є X;

локальні (локального мінімуму) - це такі допустимі точки x* в яких цільова функція приймає найменше значення в деякому околі: f(x*) ≤ f(x), ∀ x є X ∩ Uε(x*),

де Uε(x*) = {x є Rn | ||x— x*|| ≤ ε} — куля радіусу ε в центрі x*.

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

Особливістю генетичного алгоритму є акцент на використання оператора "схрещення", який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі. Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується "генетичні оператори" (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:

1.знаходження глобального, або надоптимального вирішення;

2.вичерпання числа поколінь, що відпущені на еволюцію;

3.вичерпання часу, відпущеного на еволюцію.

Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих і тяжких просторах пошуку.