stify"> Назвемо уявлення кожного індивіда геномом. Для кожного виду і кожного подання для даного цільового умови задається цільова функція. Значення цільової функції назвемо цільовим значенням. Вектор, що складається з цільових значень всіх індивідів в популяції, назвемо вектором цільових значень. Тоді якщо обчислений вектор цільових значень, то можна визначити пристосованість (fitness) індивіда в популяції, для чого задається спеціальна функція пристосованості від даного цільового значення і від вектора цільових значень. Аналогічно вектору цільових значень введемо вектор пристосованості. Часто цільове значення називають пристосованістю, а значення пристосованості, в сенсі ймовірність участі в розмноженні, неявно обчислюється під час відбору. Процес еволюції зупиняється, коли популяція відповідає певним критерієм - критерієм завершення.
Принципова схема роботи ГА складається з наступних основних фаз:
. Створення початкової популяції. Завдання генома кожному з індивідів. Розрахунок вектора цільових значень.
. Крок еволюції - побудова нового покоління.
. Перевірка критерію завершення, якщо не виконано - перехід на 2.
Крок еволюції можна розділити на наступні етапи:
. Обчислення вектора пристосованості.
. Відбір кандидатів на схрещування (Відбір - Selection).
. Схрещування, тобто породження кожною парою відібраних кандидатів нових індивідів, шляхом геномів.
. Мутація геномів.
. Обчислення вектора цільових значень і побудова нової популяції (нового покоління).
Серед компонентів, що утворюють генетичний алгоритм, в більшості випадків тільки два безпосередньо визначаються конкретним завданням - це кодування завдання (відображення простору пошуку на простір бітових рядків) і цільова функція. Розглянемо задачу параметричної оптимізації, яка полягає у визначенні набору змінних, що мінімізують деяку величину (мета). У більш традиційних термінах, завдання полягає в пошуку мінімуму деякої функції F (X1, X2, ..., XM).
На першому етапі зазвичай робиться припущення, що змінні, що представляють параметри, можуть бути представлені бітовими рядками. Це означає, що змінні попередньо дискретизируются деяким чином і що область дискретних значень відповідає деякій мірі 2. Наприклад, з 10 бітами на параметр ми отримуємо область з 2 10=1024 дискретних значень. Якщо параметри неперервні, то проблема дискретизації не заслуговує особливої ??уваги. Зрозуміло, передбачається, що дискретизація забезпечує достатнє дозвіл, щоб зробити можливим регулювання отримання результату з бажаним рівнем точності. Передбачається також, що дискретизація в деякому розумінні представляє основну функцію.
бітовим рядком довжини N можна розглядати як ціле двійкове число I, якому відповідає деякий дійсне значення r із заданого діапазону. Це відповідність встановлюється формулою
.
За винятком проблеми кодування, цільова функція зазвичай дається як частина постановки завдання. З іншого боку, розробка цільової функції іноді може безпосередньо входити в розробку алгоритму оптимізації або пошуку рішення. В інших випадках значення цільової функції може залежати від реалізації і давати тільки наближений або приватний результат.
Генетичні оператори
У відповідності з технічним завданням рішення задачі проводиться генетичним алгоритмом.
Генетичний алгоритм - це евристичний алгоритм пошуку, використовуваний для вирішення задач оптимізації та моделювання шляхом випадкового підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Є різновидом еволюційних обчислень. Відмінною особливістю генетичного алгоритму є акцент на використання оператора «схрещування», який виробляє операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещування в живій природі.
Завдання формалізується таким чином, щоб її рішення могло бути закодовано у вигляді вектора («хромосоми»). Випадковим чином створюється деяка кількість початкових векторів («початкове покоління»). Вони оцінюються з використанням «функції пристосованості», в результаті чого кожному вектору присвоюється певне значення («пристосованість»), яке визначає ймовірність виживання організму, представленого даними вектором, а також може впливати на ймовірність застосування до нього «генетичних операторів».
З отриманого безлічі рішень («покоління») з урахуванням значення «пристосованості» обираються рішення (зазвичай кращі особини мають велику ймовірність бути вибраними), до яких ...
