17.7. Генетичний та еволюційний пошук

0 } — j-та хромосома популяції P

0 — набір значень незалежних змінних, поданих у вигляді генів; h ij

0 — i-ий ген j-ої хромосоми популяції, P

0 — значення i-го оптимізованого параметра задачі, що входить в j-те рішення; N

— кількість хромосом у популяції; L — довжина хромосом (кількість генів); f — цільова функція (fitness-function, функція пристосованості, функція здоров’я, функція придатності); ? — оператор відбору; ? — оператор схрещування; ? — оператор мутації; T — критерії зупинення.

Породження нових екземплярів хромосом відбувається в процесі схрещування (кросовера) батьківських пар. Вибір пари членів популяції як батьків виробляється випадковим чином серед членів даного покоління. При цьому імовірність вибору примірників як батьків у базовому ГА залежить від значень їх функції корисності, тобто чим краще значення F, тим вищою має бути імовірність вибору.H j

0 = {h

1j

0 , h

2j

0 , …, h Lj

0 } — j-та хромосома популяції P

0 — набір значень незалежних змінних, поданих у вигляді генів; h ij

0 — i-ий ген j-ої хромосоми популяції, P

0 — значення i-го оптимізованого параметра задачі, що входить в j-те рішення; N

— кількість хромосом у популяції; L — довжина хромосом (кількість генів); f — цільова функція (fitness-function, функція пристосованості, функція здоров’я, функція придатності); ? — оператор відбору; ? — оператор схрещування; ? — оператор мутації; T — критерії зупинення.

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

ГМ = ГМ(P

0 , N, L, f, ?, ?, ?, T), де P

0 = {H

1

0 , H

2

0 , …, H N

0 } — початкова популяція — множина розв’язків задачі, поданих у вигляді хромосом; H j

0 = {h

1j

0 , h

2j

0 , …, h Lj

0 } — j-та хромосома популяції P

0 — набір значень незалежних змінних, поданих у вигляді генів; h ij

0 — i-ий ген j-ої хромосоми популяції, P

0 — значення i-го оптимізованого параметра задачі, що входить в j-те рішення; N

— кількість хромосом у популяції; L — довжина хромосом (кількість генів); f — цільова функція (fitness-function, функція пристосованості, функція здоров’я, функція придатності); ? — оператор відбору; ? — оператор схрещування; ? — оператор мутації; T — критерії зупинення.

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

Найчастіше для вибору батьків застосовують правило, зване правилом рулетки. У ньому ймовірність P k вибору k-го члена популяції як батька визначається як відношення корисності даного члена до сумарної корисності всіх членів популяції. Якщо цільова функція мінімізується, то: ()() ? = ??= N i ikk FFFFP

1 maxmax /, де F k — функція корисності k-го примірника, F max — максимальне значення функції корисності серед членів даного покоління, N

— розмір популяції.

Схрещення (кросовер) полягає в розриві двох обраних батьківських хромосом і рекомбінуванні створених хромосомних відрізків, що дає пару хромосом-нащадків.

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

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

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

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

17.7. Генетичний та еволюційний пошук

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

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

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

Мінливість — це можливість змін невеликої частини ознак (мутацій), що забезпечує гнучкість і можливість розвитку.

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

Ці принципи можна використовувати для вирішення найрізноманітніших завдань. Підхід з використанням вищенаведених принципів називається еволюційним.

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

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

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

Розмноження: спадковість

Розмноження: спадковість

Розмноження: спадковість

Рис. 6.3. Загальна схема процесу еволюції

Хоч ЕМ підходять практично для будь-якої задачі, їх застосування не завжди є виправданим. Якщо ми хоча би приблизно можемо оцінити, як впливають зміни окремих ознак на якість об’єкта, то зазвичай можна зробити висновок, що є більш ефективні методи пошуку, ніж еволюційний. Чим складнішою є система і чим менше відомо про вплив окремих параметрів на поведінку системи в цілому, тим більш корисними можуть бути ЕМ. Їх цінність саме в тому, що зовсім не обов’язково знати, якими мають бути зміни ознак для покращання стану об’єкта, ці зміни можуть вибиратися випадково.

До 3-х основних принципів еволюційного процесу іноді додають четвертий — схрещування. Хоча схрещування і не є обов’язковим для ЕМ, воно дозволяє значно збільшити їх ефективність. Ідея полягає в тому, що різні об’єкти одного покоління можуть незалежно нагромаджувати різні корисні ознаки. Якщо для створення об’єкта нащадка береться лише один об’єкт — батько, то для нагромадження всіх корисних ознак може

жди нерентабельним через величезний обсяг роботи. Але розвиток комп’ютерів відкрив перед ЕМ зовсім нові можливості. Замість того, щоб працювати з реальними об’єктами, можна працювати з їх математичними моделями.

Схрещування — це спосіб створення об’єкта нащадка, за якого частина властивостей береться від одного об’єкта — батька, а друга частина від іншого. Це дозволяє відразу об’єднати корисні властивості, незалежно нагромаджені обома об’єктами-батьками в одному об’єкті-нащадку.

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

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

Оптимізаційні методи використовують для знаходження екстремальних значень функцій і відповідних їм значень незалежних змінних.

Вибір методу оптимізації пов’язаний з типом розв’язуваної оптимізаційної задачі. Задачі оптимізації можна класифікувати за такими критеріями:

— тип змінних, що оптимізуються (безперервні та дискретні);

— кількість змінних, що оптимізуються;

— вид цільової функції (лінійна, квадратична, нелінійна);

— властивості функцій (унімодальність, неперервність, гладкість, монотонність, диференційованість);

— спосіб задавання цільової функції (явне або неявне задавання);

— наявність, кількість і вид обмежень;

— вид оптимізації (глобальна або локальна);

— кількість цільових функцій, що оптимізуються (однокритеріальна або багатокритеріальна оптимізація).

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

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

знадобитися дуже багато поколінь, адже зміни невеликі й випадкові.

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

Так моделюється еволюційний процес, який триває кілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:

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

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

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

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

Методи еволюційного пошуку можуть бути класифіковані за різними критеріями.

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

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

2. За способом організації відтворення виокремлюють популяційні та стаціонарні еволюційні методи.

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

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

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

3. За використання паралельного підходу методи еволюційного пошуку можуть бути класифіковані на послідовні й паралельні.

Послідовні еволюційні методи використовують єдину популяцію хромосом на кожній ітерації.

У разі застосування паралельних методів на кожній ітерації використовується кілька підпопуляцій. До паралельних методів належать:

— однопопуляційні методи;

— острівна модель еволюційного пошуку;

— дрібноструктурні;

— ієрархічні гібриди.

4. За способом кодування хромосом виділяють еволюційні методи, що використовують бінарні хромосоми, числові хромосоми й векторні хромосоми. У бінарних хромосомах гени можуть набувати два значення. Числові хромосоми містять гени, що приймають будь-які значення в заданому інтервалі. При цьому в гомологічних числових хромосомах допускається наявність генів з однаковими значеннями, а в негомологічних хромосомах усі гени набувають різні значення. Векторні хромосоми складаються з генів, які являють собою вектор цілих чисел.

5. За методом керування параметрами еволюційного пошуку виокремлюють неадаптивні методи та адаптивні.

До неадаптивних методів керування параметрами відносять:

— використання параметрів-констант;

— детерміноване керування параметрами.

Адаптивні методи керування можуть бути класифіковані в такий спосіб:

— оцінювальні методи;

— пристосовувальні методи;

— структурно-орієнтовані методи (розбиття популяції й метод просторової популяційної структури).

Рис. 6.4. Класифікація методів

еволюційного пошуку

6. За використання полімодального пошуку виокремлюють класичні методи та методи полімодального пошуку.

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

— методи ухилення від передчасної збіжності (методи уповільнення генетичної збіжності й методи запобігання появи збіжних рішень);

— методи відновлення (методи множинного заміщення, методи перезапуску і фазові методи).

7. За кількістю критеріїв пошуку виокремлюють однокритеріальні та багатокритеріальні методи еволюційної оптимізації.

Методи багатокритеріальної еволюційної оптимізації дозволяють виявити оптимум сукупності цільових функцій і розподіляються на:

— апріорні методи (метод агрегувальних функцій, лексикографічне впорядковування, мінімаксний метод, метод досягнення заданого значення);

— прогресивні методи;

— апостеріорні методи (популяційний підхід і пошук, заснований на підході Парето).

8. За можливістю підтримки обмежень виокремлюють методи, що не підтримують обмеження, та методи, що підтримують обмеження. До методів, що підтримують обмеження, відносять методи:

— методи, що використовують штрафні функції;

— методи перетворення простору пошуку;

— методи, що використовують спеціальні еволюційні оператори;

— методи відновлення неприпустимих рішень;

— методи, що застосовують багатокритеріальний підхід.

17.8. Оператори генетичного програмування

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

Методи генетичного програмування використовують генетичні оператори відбору, схрещування і мутації.

Оператори відбору, які розроблені для генетичних методів, можуть бути також застосовні і в методах генетичного програмування.

Основними генетичними операторами (рис. 6.5) є:

1. Схрещування (crossover) — два рішення кандидата ділять на кілька частин і обмінюються цими частинами, результатом стають два нові кандидати.

2. Мутація, що полягає у випадковому виборі кандидата і випадковій зміні деяких його властивостей, наприклад: мутація може полягати у випадковому виборі біта в шаблоні та зміні його значення з 1 на 0 або на #, значення мутації полягає в можливому заповненні важливих компонентів рішення, відсутніх у початковій популяції.

3. Інверсія — зміна порядку проходження бітів у бітовому рядку. Досить успішно виявив себе оператор інверсії (inversion), який переставляє групу генів у хромосомі.

4. Обмін — зміна місць двох довільних бітів.

5. Відбір (Selection) є, імовірно, найбільш важливим і найважчим для розуміння етапом ГА. Оператор відбору також називається оператором репродукції, вибору або селекції. Він будується так, щоб з ненульовою вірогідністю будь-який елемент популяції міг би бути вибраний як один з батьків. Більше того, допускається ситуація, коли обидва батьки представлені одним і тим самим елементом популяції.

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

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

17.9. Основні поняття, принципи і передумови генетичних алгоритмів

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

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

Генетичні алгоритми (ГА) — це адаптивні методи функціональної оптимізації, засновані на комп’ютерному імітаційному моделюванні біологічної еволюції. Основні принципи ГА були сформульовані Голландом (Holland, 1975).

На сьогодні існує низка теорій біологічної еволюції (Ж.-Б. Ламарка, П. Тейяра де Шардена, К. Е. Бера, Л. С. Берга, А. А. Любіщева, С. В. Мейена та ін.), проте жодна з них не вважається загальновизнаною. Найбільш відомою і популярною, звичайно, є теорія Чарльза Дарвіна, яку він представив у праці «Походження Видів» 1859 року. Як це не парадоксально, але не зважаючи на те, що сам Чарльз Дарвін назвав свою роботу «Походження Видів», однак саме походження видів вона не пояснює.

Річ у тому, що виникнення нового виду «за алгоритмом Дарвіна» є вкрай маловірогідною подією, оскільки для цього потрібне випадкове виникнення в одній точці простору й часу відразу не менше 100 особин нового виду, тобто особин, які могли б мати плодовите потомство. За меншої кількості особин вид приречений на вимирання.

Тому процес видоутворення на основі випадкових мутацій мав би зайняти неймовірно багато часу (за деякими оцінками, у набагато разів більше, ніж час існування Всесвіту). Крім того, «алгоритм Дарвіна» не пояснює явної системності в різноманітті виникаючих форм, на зразок закону гомологічних рядів Н. І. Вавілова. Тому Л. С. Берг запропонував дуже цікаву концепцію номогенезу — закономірної або направленої еволюції живого. У цій концепції передбачається, що філогенез має певний напрям і зміна форми є не випадковою, а задається деяким вектором, природа якого не зрозуміла. Ідеї номогенезу глибоко розробив і розвинув А. А. Любіщев, який висловив гіпотезу про математичні закономірності, що визначають різноманіття живих форм.

Крім того, Дарвін не зміг показати механізм спадкоємства, за якого підтримується і закріплюється мінливість. Це було на п’ятдесят років до того, як генетична теорія спадковості почала поширюватися по світу, і за тридцять років до того, як «еволюційний синтез» укріпив зв’язок між теорією еволюції і молодою генетикою.

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

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

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

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

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

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

на Землі і відіграє позитивну роль у подальшому розробленні найбільш адекватної теорії біологічної еволюції.

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

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

У результаті описаних операцій на кожному етапі еволюції одержують популяції з досконалішими індивідуами.

Функціонування ГА (рис. 6.6) можна пояснити так. Спочатку ми випадковим чином оберемо кілька підмножин з повного набору незалежних змінних, назвемо кожну таку підмножину хромосомою, а вхідні в нього окремі змінні — генами. Якщо є яка-небудь апріорна інформація, її, звичайно, бажано використовувати під час початкового розбиття на хромосоми, це може відсікти тупикові шляхи еволюції і тим самим прискорити вирішення завдання. Для кожної хромосоми (тобто набору незалежних змінних) ми можемо яким-небудь чином (наприклад за допомогою дерева рішень, регресійного аналізу або якогось іншого методу) побудувати залежності цільової змінної від незалежних змінних, що входять у дану хромосому. Так ми робимо для всієї первинної популяції хромосом. Природно, що деяким хромосомам відповідають точніші моделі, іншим — менш точні. Відповідно до цієї точності кожній хромосомі приписується деяке оцінююче її значення, критерій її цінності. Це може бути, наприклад, кількість випадків, що

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

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

Рис. 6.6. Модель схрещування і мутації

Рис. 6.6 ілюструє одну з реалізовуваних у ГА моделей схрещування і мутації. Обидві генетичні операції виконуються з певною вірогідністю. Вірогідність схрещування, що визначається з розрахунку на одну хромосому, як правило, змінюється в межах від 0,8 до 1,0. Вірогідність мутації, віднесена до одного гена, вибирається найчастіше з інтервалу 0,001 — 0,01.

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