Posibniki.com.ua Інформатика Прикладні системи штучного інтелекту 17.13. Узагальнена схема роботи генетичних методів


< Попередня  Змiст  Наступна >

17.13. Узагальнена схема роботи генетичних методів


 

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

0 , P

1 , P

2 , ..., P T .

t + 1жать поколінню P t .

Покоління P

0 є початковою популяцією. Процес формування покоління P

0 називається ініціалізацією. Кожне покоління є результатом циклу роботи генетичного методу.

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

Покоління P t + 1 — це сукупність особин, батьки яких належать поколінню P t .

Покоління P

0 є початковою популяцією. Процес формування покоління P

0 називається ініціалізацією. Кожне покоління є результатом циклу роботи генетичного методу.

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

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

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

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

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

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

Схему роботи узагальненого генетичного методу наведено на рис. 6.7.

Рис. 6.7. Схема роботи узагальненого генетичного методу

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

Рис. 6.7. Схема роботи узагальненого генетичного методу

17.14. Етапи генетичного програмування

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

Узагальнений метод генетичного пошуку можна записати так.

Крок 1. Установити лічильник ітерацій (часу): t = 0. Виконати ініціалізацію (initialization) початкової популяції особин: P t = {H

1 , H

2 , …, H N }.

Крок 2. Оцінити особини поточної популяції (evaluating) способом обчислення їх fitness-function f(H j ), j = 1, 2, …, N.

Крок 3. Перевірити умови закінчення пошуку (termination criteria). Як такі умови можна використати: досягнення максима-P t = {H

1 , H

2 , …, H N }.

Крок 2. Оцінити особини поточної популяції (evaluating) способом обчислення їх fitness-function f(H j ), j = 1, 2, …, N.

Крок 3. Перевірити умови закінчення пошуку (termination criteria). Як такі умови можна використати: досягнення максима-собом обчислення їх fitness-function f(H j ), j = 1, 2, …, N.

Крок 3. Перевірити умови закінчення пошуку (termination criteria). Як такі умови можна використати: досягнення максима-

Крок 1. Установити лічильник ітерацій (часу): t = 0. Виконати ініціалізацію (initialization) початкової популяції особин: P t = {H

1 , H

2 , …, H N }.

Крок 2. Оцінити особини поточної популяції (evaluating) способом обчислення їх fitness-function f(H j ), j = 1, 2, …, N.

Крок 3. Перевірити умови закінчення пошуку (termination criteria). Як такі умови можна використати: досягнення максима-

Крок 4. Збільшити лічильник ітерацій (часу): t = t + 1.

Крок 5. Вибрати частину популяції (батьківські особини) для схрещування (selection of parents) P’.

Крок 6. Сформувати батьківські пари (mating) з особин, що відібрані на попередньому кроці.

Крок 7. Схрестити (crossover) вибрані батьківські особини.

Крок 8. Застосувати оператор мутації (mutation) до особин P’.

Крок 9. Обчислити нову функцію пристосованості f(H j ) особин, отриманих у результаті схрещування та мутації.

Крок 10. Сформувати нове покоління шляхом вибору особин, що вижили, виходячи з рівня їх пристосованості (replacing, selection of survivors).

Крок 11. Перейти до кроку 3.

Крок 12. Зупинення.

Отже, для реалізації генетичних методів необхідно:

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

— задати цільову функцію;

— визначити правила ініціалізації початкової популяції;

— вибрати оператори відбору, схрещування і мутації, а також задати їх параметри;

— визначити критерії зупинення.

17.15. Ініціалізація

Стандартні генетичні методи починають свою роботу з ініціалізації, тобто формування початкової популяції P

0 — скінченного набору допустимих рішень задачі: P

0 = {H

1 , H

2 , ..., H N }; де N — чисельність популяції; H j = {h

1j , h

2j , ..., h Lj } — j-та хромосома, що складається з L генів; h ij — значення i-го гену j-ої хромосоми, w min, i ? h ij ? w max, i ; w min, i та w max, i — мінімальне й максимальне значення i-го параметра у розв’язуваній за допомогою генетичного методу задачі.

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

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

Найчастіше розмір початкової популяції вибирається в інтервалі 20—100 особин.

Використовуються такі стратегії ініціалізації початкової популяції (рис. 6.8):

• випадкове формування початкової популяції;

• рівномірне формування початкової популяції (сіткова ініціалізація). За такої стратегії генерується множина рішень, рівно віддалених одне від одного;

Рис. 6.8. Стратегії формування початкової популяції: а) випадкова ініціалізація; б) сіткова ініціалізація; в) випадкова ініціалізація, заснована на знаннях; г) сіткова ініціалізація, заснована на знаннях

Рис. 6.8. Стратегії формування початкової популяції: а) випадкова ініціалізація; б) сіткова ініціалізація; в) випадкова ініціалізація, заснована на знаннях; г) сіткова ініціалізація, заснована на знаннях

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

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

• сіткова ініціалізація, заснована на знаннях, об’єднує основні положення попередніх двох стратегій.

17.16. Еволюційні (µ + ?) та (µ, ?) еволюційні стратегії та алгоритми

Тоді як ГА моделює еволюцію на рівні геномів, еволюційні стратегії (ЕС) та інші ЕМ спрямовані на еволюцію фенотипів. Оскільки ПСШІ розвивалися спеціально для числової оптимізації, фенотипи в них представлені дійсними векторами.

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

Оригінальна (у первинному варіанті) ЕС була двоелементною схемою, що складалася з батька і нащадка. У базовому методі батько, мутуючи, створює нащадка, і одна з двох особин з кращим значенням fitness-function переходить у популяцію наступного покоління. Цей метод був узагальнений пізніше на так звані (µ + ?) і (µ, ?) ЕС. Параметри µ і ? означають число батьків і нащадків відповідно.

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

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

Коефіцієнт ? = ? / µ зазвичай більший або дорівнює семи. Що більший він, то більше шансів, що кожен батько згенерує щонайменше одного нащадка, кращого, ніж він сам. Проте відмінності між (µ + ?) та (µ, ?) ЕС стають меншими, якщо ? є достатньо великим.

Канонічна ЕС може бути подана такою послідовністю кроків.

Крок 1. t = 0.

Крок 2. Ініціалізувати популяцію P t µ випадковими індивідами з R n .

Крок 3. Якщо немає умови зупинки алгоритму, то виконати:

Крок 3.1. Одержати особини з P t з рівними імовірностями для виробництва ? нащадків.

Крок 3.2. Виконати мутації над нащадками.

Крок 3.3. Обчислити fitness-function нащадків.

Крок 3.4. Вибрати кращі µ нащадків, базуючись на значеннях fitness-function, і створити P t + 1 .

Крок 3.5. t = t + l.

Крок 4. Виконати перевірку критеріїв зупинення пошуку. У разі невиконання їх, перейти до кроку 3.

Крок 5. Зупинення.

Порівняльний аналіз ЕС і ГА свідчить, що головна відмінність полягає в тому, що тоді як у ГА вибираються особини для рекомбінації пропорційно до їх fitness-function і замінюються особини з попередньої популяції, в ЕС діють навпаки. У цьому випадку особини для репродукції вибираються з рівними імовірностями, а формування наступної популяції базується на значеннях fitness-function. Існують відмінності в базових процесах ЕМ. У ГА і ГП вибираються особини для репродукції пропорційно до значення fitness-function і замінюються елементи попередньої популяції однаково (рівноймовірно). ЕМ і ЕП припускають протилежну стратегію, яка полягає в тому, що з рівними імовірностями вибираються особини для репродукції і виживання базується на значенні fitness-function. Як уже зазначалося, варіації порядку вказаних операцій мають малий вплив на процес еволюції.

Мутація, яка часто є єдиним еволюційним оператором, полягає у зміні кожного елементу вектора вагів-зв’язків на величину, що має нормальний розподіл, ?(t) дисперсія якого адаптується в часі. У стратегії правило «20 % успіху» використовується для адаптації дисперсії.

При цьому таке правило може застосовуватися на кожній ітерації або через кожні А ітерацій. Періодично під час пошуку одержують частоту успіху, тобто відношення кількості успіхів до всього числа спроб (мутацій). Під успішністю виконання еволюційного оператора над певною хромосомою мають на увазі появу нової хромосоми, fitness-function якої краща порівняно з fitness-function батьківської хромосоми. Якщо відношення більше 1/5, то середньоквадратичне відхилення зростає, інакше — спадає: ? ? ? ? ? ? ? > ?? =?? k c At kAt kAtc t

1

1 t Atl l j B j l Hu B k l , де B l — кількість виконаних мутацій на l-ій ітерації; u(H j l ) — функція, що характеризує успішність виконання мутації на l-ій ітерації для j-ої хромосоми. При мінімізації фітнес-функії f значення u(H j l ) обчислюється за формулою: () ()() ()() ? ? ? ? ? ? < = ? ? .якщо,0 ;якщо,1

11

1 l j l j l j l j l j HfHf HfHf Hu

При використанні (µ + ?) або (µ, ?) ЕС, в яких µ хромосомбатьків породжують ? нащадків, функцію успішності u t виконання мутації на t-ій ітерації обчислюють за формулою: ()() ()() ? ? ? ? ? ? ? ? ? ? ? µ ? < µ = ?? ?? ? = ? µ = ? = ? µ = .якщо,0 ;якщо,1

1

1 j l j j l j j l j j l j l HfHf HfHf u

1

1

Коефіцієнт успішності виконання мутації від (tА – 1)-ої до (t1)-ої ітерації при використанні (µ + ?) або (µ, ?) ЕС обчислюється за формулою: ? ? ??= =

1

1 t Atl l uk.

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

Більш прийнятною за правило «20 % успіху» при виконанні мутації в багатоелементних стратегіях є зміна середньоквадратичних відхилень з використанням логнормального розподілу:

Збіжність ЕС чутлива до вибору коефіцієнта ? та початкових значень вектора середньоквадратичних відхилень. Універсального методу їх отримання незалежно від цільової функції наразі не

де А — кількість ітерацій, упродовж яких не відбувається зміна середньоквадратичного відхилення; ?(t) та ?(tА) — середньоквадратичне відхилення нормального розподілу на t-ій та (tА)-ій ітераціях відповідно; c — параметр швидкості зміни кроку середньоквадратичного відхилення, значення якого вибирають в інтервалі 0,817 ? c ? 1; k — коефіцієнт успішності виконання мутації від (tА – 1)-ої до (t1)-ої ітерації: () ?? ? ??== ? ? ? ? ? ? ? ? =

Збіжність ЕС чутлива до вибору коефіцієнта ? та початкових значень вектора середньоквадратичних відхилень. Універсального методу їх отримання незалежно від цільової функції наразі не

= j

1 де C залежить від µ та ?. Приймають C = 1 для еволюційної стратегії (10,100).

Для ініціалізації вектора середньоквадратичних відхилень поде C залежить від µ та ?. Приймають C = 1 для еволюційної стратегії (10,100).

Для ініціалізації вектора середньоквадратичних відхилень по=? N C

2

2 , чатковими значеннями використовується рівність: =? N j j R

2 , = j

1 де константа R j — максимальний ранг невизначеності відповідної змінної.

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

Ключовим чинником є те, що всі ЕМ базуються на фундаментальних Дарвіновських принципах природної селекції. Переваги одного ЕМ над іншим є предметом дискусії. існує. Рекомендується приймати: ? = ? =? N j j C

1

2

2 , де C залежить від µ та ?. Приймають C = 1 для еволюційної стратегії (10,100).

Для ініціалізації вектора середньоквадратичних відхилень початковими значеннями використовується рівність: ? = ? =? N j j j j R

1

2 , де константа R j — максимальний ранг невизначеності відповідної змінної.

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

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

17.17. Приклад реалізації генетичного алгоритму

У 2002 році в британському центрі Magna відкрився павільйон Live Robots, де боролися за виживання 12 роботів двох видів: «геліофаги», здатні здобувати електроенергію з використанням сонячних батарей; «хижаки», які могли одержувати електроенер-

де ? j (t) та ? j (tА) середньоквадратичні відхилення j-ої хромосоми на t-ій та (tА)-ій ітераціях відповідно; ? коефіцієнт, що характеризує ступінь зміни значень вектора середньоквадратичних відхилень.

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

У Brandeis University була створена програма Golem, яка сама конструювала роботів. У програму була база деталей, а також механізм мутацій і функція придатності для «відсіювання» невдах — тих, хто не навчився рухатися. Після 600 поколінь за кілька днів програма одержала моделі трьох повзаючих роботів. Показово, що роботи виявилися симетричними, хоча симетрія ніяк не була явно прописана в правилах еволюції і початкових даних. Це означає, що вона з’явилася в процесі моделювання машинної еволюції як корисна межа, що дозволяє рухатися прямолінійно.

Алгоритм, який використовує відбір, вірогідність якого ґрунтується на значенні здоров’я, наведено у додатку А. У даному лістингу рекомбінування окремо не показано, оскільки воно виконується одночасно з процесом відбору.

Функція main працює так (додаток А). Спочатку за допомогою функції srand ініціалізувався генератор випадкових чисел. Відкривається файл, в який виводитиметься інформація про здоров’я хромосом. Потім популяція ініціалізувалася за допомогою довільно вибраних останніх (функція initPopulation), і виконується перевірка здоров’я хромосом (функція performFitnessCheck), оскільки здоров’я кожної хромосоми важливе для процесу відбору (функція performSelection).

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

Популяція складається з групи хромосом (задається як MAX_CHROMS), при цьому кожна хромосома є самою програмою (поле program), розміром програми (поле progSize) і здоров’ям програми (поле fitness). Змінна populations зберігає дві популяції (стару і нову). Змінна curPop указує, яка популяція розглядається у нинішній момент; у неї вносяться всі зміни. При рекомбінуванні батьків вибирають з поточної популяції (указується змінній curPop), а нові хромосоми поміщають в іншу популяцію (визначається виразом !curPop).

Головний цикл функції main (цикл поколінь) виконує відбір, перевірку здоров’я і переміщує популяції за кожної ітерації. Реш-

гію тільки від геліофагів. Роботи, що вижили, завантажували свої «гени» в загиблих і, таким чином, утворювали нові покоління.

Оцінка здоров’я виконується за допомогою функції perform Fitness Check.

Функція performFitnessCheck вивчає всі хромосоми в поточній популяції і розраховує їх здоров’я. Потім здоров’я зберігається як інформація про хромосому в структурі populations.

Алгоритм починає роботу з видалення всієї інформації про здоров’я та підготовки до оцінки поточної популяції. Після видалення інформації про здоров’я у циклі виконується тест для всіх хромосом. Щоб уникнути варіанта, за якого хромосома видасть правильну відповідь, яка працюватиме тільки в одному випадку, хромосоми перевіряються кілька разів (у даному випадку 10 разів). Масив args містить аргументи завдання. Він завантажується у стек віртуальної машини викликом функції evaluation. У кожному випадку масив args заповнюється випадковими — значеннями. Це дозволяє впевнитися, що програма дійсно вирішує поставлену задачу.

Після того, як для завдання були задані аргументи, розраховується і поміщається в змінну answer значення, яке має вийти в результат. Потім викликається функція interpretSTM, щоб оцінити здоров’я. На підставі результату, виданого функцією оцінки, визначається здоров’я хромосоми. Здоров’я ґрунтується на трьох значеннях: якщо вихід з програми пройшов успішно (не було математичної, або програмної помилки), повертається значення TIER1; якщо в стеку залишилося тільки одне значення, додається значення TIER2; нарешті, якщо у верхній комірці сте-

та команд циклу видає інформацію про роботу програми і виконує перевірку на умови виходу. Якщо середнє здоров’я становить 98 % від максимального, то популяція вважається однорідною (тобто такою, що містить однакові хромосоми), і програма завершує роботу. Якщо максимальне здоров’я дорівнює максимально допустимому здоров’ю для функції, робота також закінчується, оскільки знайдено розв’язок задачі. Після того, як розв’язок знайдено, виводиться додаткова інформація для користувача, а також відображається програма (хромосома), яка має максимальне здоров’я. Ініціалізація популяції є досить простим процесом. Програма проходить по всіх хромосомах популяції і привласнює кожному гену довільну інструкцію. Здоров’я всіх хромосом обнуляється, а їх розмір задається максимально допустимим значенням. Із функції main викликається функція initPopulation, яка, у свою чергу, викликає функцію initMember, щоб ініціалізувати кожну хромосому популяції.

Після завершення перевірки здоров’я поточної хромосоми програма визначає, чи є це значення найбільшим або найменшим. Дана iнформація зберігається в змінних maxFitness і minFitness відповідно. Потім розраховується значення totFitness, а після завершення роботи циклу — перевірки всіх хромосом — визначається середнє здоров’я популяції — змінна avgFitness.

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

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

— вибір хромосом-батьків для схрещування;

— формування пар хромосом для схрещування;

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

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

Найбільш поширеними є такі оператори відбору:

— пропорційний відбір (пропорційно-імовірнісний);

— відбір ранжируванням;

— турнірний відбір;

— відбір з використанням порога.

Функція performReproduction працює з індексами в таблицях двох популяцій. Змінні par1 і раr2 є індексами в поточній популяції, а змінні child1 і child2 — індексами в новій популяції. Алгоритм вибирає індекси child, починаючи з нуля та збільшує їх на два при кожному розрахунку. Індекси батьків визначаються за допомогою функції selectParent. Після отримання значень для

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

Вибір батьків ґрунтується на принципі, згідно з яким шанси хромосоми бути вибраною пропорційні її здоров’ю порівняно із загальним здоров’ям популяції. Ця вірогідність (зберігається в змінній retFitness) розраховується на початку циклу do.

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

Спочатку виконується перевірка на необхідність використання оператора перехресного схрещування. Якщо випадкове число більше, ніж поріг XPROB, розраховується точка перетину (crossPoint) на підставі максимальної довжини хромосоми (розглядається та із хромосом-батьків, довжина якої більше). Розміри хромосом можуть бути різними (хоча в даному прикладі вони завжди максимальні). Точка перетину не може бути першим або останнім геном хромосоми.

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

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

До бінарних хромосом можуть бути застосовані такі оператори схрещування:

— точкове;

— однорідне;

— рівномірне;

— порівняльне;

— діагональне.

чотирьох індексів викликається функція performReproduction, яка виконує рекомбінування.

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

До гомологічних числових хромосом крім вище розглянутих можуть бути застосовані такі оператори схрещування:

— плоске;

— арифметичне;

— геометричне;

— змішане;

— евристичне;

— нечітке;

— SBX-схрещування.

Також існують оператори простого (simple crossover) і дискретного (discrete crossover) схрещування, аналогічні операторам одноточкового і однорідного схрещування, що використовуються для схрещування бінарних хромосом.


< Попередня  Змiст  Наступна >
Iншi роздiли:
Тема 18. ПРИКЛАДНІ СИСТЕМИ КОЛЕКТИВНОГО ІНТЕЛЕКТУ SWARM INTELLIGENCE
18.3. Різновиди методу мурашиних колоній
18.7. Особливості модифікацій методів бджолиної колонії
18.11. ПСШІ на основі переміщення бактерій
18.16. Людино-машинні інтерфейси (human-computer interface, HCI)
Дисциплiни

Медичний довідник новиниКулінарний довідникАнглійська моваБанківська справаБухгалтерський облікЕкономікаМікроекономікаМакроекономікаЕтика та естетикаІнформатикаІсторіяМаркетингМенеджментПолітологіяПравоСтатистикаФілософіяФінанси

Бібліотека підручників та статтей Posibniki (2022)