Основі кроки класичного генетичного алгоритму. Опишіть їх

Генетичний алгоритм — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується "генетичні оператори", створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути: 1) знаходження глобального, або надоптимального вирішення; 2) вичерпання числа поколінь, що відпущені на еволюцію; 3) вичерпання часу, відпущеного на еволюцію. Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих і тяжких просторах пошуку. Можна виділити наступні етапи генетичного алгоритму: 1) створення початкової популяції; 2) обчислення функції пристосованості для осіб популяції (оцінювання); 3) повторювання до виконання критерію зупинки алгоритму (Вибір індивідів із поточної популяції (селекція), Схрещення або/та мутація, Обчислення функції пристосовуваності для всіх осіб, Формування нового покоління).

Суть теореми про схеми.

Теорема схем (англ. Schema Theorem) (інші назви: теорема шаблонів (схеми, шим), фундаментальна теорема генетичних алгоритмів) — перша теорема, яка обгрунтовувала ефективність генетичних алгоритмів. Запропонована Джоном Г. Голландом. Ця теорема пояснює, чому для певних задач певний клас генетичних алгоритмів є ефективним. У даний момент відомо декілька теорем схем, які обгрунтовують ефективність інших класів алгоритмів, зокрема теореми схем для генетичного програмування.

Під схемою ξ розумітемимо підмножину простору генотипів G. Якщо елементами G є бінарні рядки x, тоді дозволивши приймати деяким компонентам рядка довільні значення, а решті тільки 0 або 1, отримуємо схему або шаблон. Наприклад: 1 * * 0. Елементами підмножини, яку представляє цей шаблон тоді будуть 1000, 1010, 1100 та 1110. Довільну схема може бути описана за допомогою трьох показників: визначальної довжини l(ξ), порядку та значення функції пристосованості. Припустімо, що li(ξ) (відповідно hi(ξ)) - функція, що повертає номер позиції у схемі першого (відповідно останнього) фіксованого елемента ξ. Тоді визначальна довжина дорівнює l(ξ) = hi(ξ) − li(ξ). Порядком називається кількість фіксованих елементів у схемі.

Теорема

Зв'язок між часткою P(ξ,t) популяції, що представляє схему ξ у поточному поколінні t та часткою P(ξ,t + 1) у наступному поколінні t + 1 подається у такому вигляді:

,

де Pc — частка популяції, що піддається кросоверу, l(ξ) — визначальна довжина схеми ξ, — середнє значення функції пристосованості для бінарних рядків зі схемою вигляду ξ, — середнє значення функції пристосованості для всієї популяції бінарних рядків.