• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Для застосування ГА необхідно:

1) виділити сукупність властивостей об'єкту, що характеризуються внутрішніми параметрами і що впливають на його корисність, тобто виділити множина керованих параметрів X= (x1,x2...xn); серед xi можуть бути величини різних типів (real, integer, Boolean, enumeration). Наявність нечислових величин (enumeration) обумовлює можливість вирішення завдань не тільки параметричної, але і структурної оптимізації;

2) сформулювати кількісну оцінку корисності варіантів об'єкту - функцію корисності F. Якщо в початковому вигляді завдання многокрітеріальна, то таке формулювання означає вибір скалярного (узагальненого) критерію;

3) Розробити математичну модель об'єкту, що є алгоритмом обчислення F для заданого вектора N;

4) Представити вектор Nу формі хромосоми - запису наступного вигляду.

У ГА використовується наступна термінологія: ген - керований параметр xi;

аллель - значення гена;

локус (позиція) - позиція, займана геном в хромосомі;

генотип - екземпляр хромосоми, генотип представляє сукупність внутрішніх параметрів проектованого за допомогою ГА об'єкту;

генофонд - множина всіх можливих генотипів;

функція корисності (пристосованості) F - цільова функція;

фенотіп - сукупність генотипу і відповідного значення F, під фенотіпом часто розуміють сукупність вихідних параметрів об'єкту, що синтезується за допомогою ГА.

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

Далі організовується циклічний процес зміни поколінь:

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

Розглянемо алгоритми виконання операторів в простому генетичному алгоритмі.

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

де Fmax - якнайгірше значення цільової функції F серед екземплярів (членів) поточного покоління, Fi - значення цільової функції i-го екземпляра.

Правило (4.31) називають правилом колеса рулетки. Якщо в колесі рулетки виділити сектори, пропорційні значенням Fmax-fi, то вірогідність попадання в них суть Pi, визначувані відповідно до (4.31).

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

Мутації'. Оператор мутації виконується з деякою вірогідністю Sм, тобто з вірогідністю Sм відбувається заміна аллеля випадковим значенням, вибираним з рівною імовірністю в області визначення гена. Саме завдяки мутаціям розширюється область генетичного пошуку.

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

Внутрішній цикл закінчується, коли число екземплярів нового покоління стане рівним N.

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

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

Кросовер.

1) допустимі схеми багатоточкового кросовера.

2) відзначимо ситуації, коли на склад аллелей накладені деякі додаткові умови. Наприклад, хай в завданні розбиття графа число вершин в підграфах C1і C2повинне бути N1 і N2 і хай к-й аллель, рівний 1, означає, що вершина до потрапляє в C1, якщо ж к-й аллель рівний 0, то в C2.

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

Один із способів - метод PMX (Partially Matched Crossover). Для ілюстрації PMX розглянемо приклад двоточкового кросовера в завданні, коли в хромосомі повинні бути присутніми, причому тільки по одному разу, всі значення генів із заданого набору. Хай в прикладі цей набір включає числа від 1 до 9.

У табл. 4.4 перші два рядки представляють батьківські хромосоми. Третій рядок містить хромосому одного з нащадків, застосування двоточкового кросовера, що згенерувало в результаті (після другого і п'ятого локусов). Отримана хромосома не належить до допустимих, оскільки в ній значення генів 1, 2 і 9 зустрічаються двічі, а значення 3, 4 і 5 відсутні. Четвертий рядок показує результат застосування РМХ. У цьому методі виділяються зв'язані пари аллелей в однойменних локусах одній з частин, що рекомбінуються. У нашому прикладі це пари (3 і 1) (4 і 9) (5 і 2). Хромосома нащадка є видимою зліва направо; якщо повторно зустрічається деяке значення, воно замінюється на зв'язане значення. Так, в прикладі в локусах 3, 5 і 9 аллелі, що повторно зустрічаються, 1, 2 і 9 послідовно замінюються на значення 3, 5 і 4.

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

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

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

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

Наступний варіант селекції - відбір N екземплярів серед членів репродукційної групи, яка складається з батьків, нащадків і мутантів, що задовольняють умові Fi < t, де t - порогове значення функції корисності. Поріг може бути рівний або середньому значенню F в поточному поколінні, або значенню F особині, що займає певне порядкове місце. При цьому м'яка схема відбору - в нове покоління включаються N кращих представників репродукційної групи. Жорстка схема відбору - в нове покоління екземпляри включаються з вірогідністю qi:

де Nr - розмір репродукційної групи.

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

Призначення переупорядковування пов'язане з властивістю, що носить назву епістасис. Епістасис має місце, якщо функція корисності залежить не тільки від значень генів (аллелей), але і від їх позиціонування. Наявність епістасиса говорить про нелінійність цільової функції і істотно ускладнює вирішення завдань. Дійсно, якщо деякі аллелі двох генів роблять певний позитивний вплив на цільову функцію, утворюючи деяку зв'язку (схему), але унаслідок епістасиса при розриві зв'язки ці аллелі роблять вже протилежний вплив на функцію корисності, то розривати такі схеми не слід. А це означає, що зв'язані епістасисом гени бажано розташовувати близько один до одного, тобто при невеликих довжинах схем. Оператор переупорядковування допомагає автоматично “намацати” такі сукупності генів (вони називаються хромосомними блоками або building blocks) і розмістити їх в близьких локусах.

Генетичний метод комбінування евристик.Можливі два підходи до формування хромосом.

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

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

Другий підхід отримав назву - метод комбінування евристик. Цей метод виявляється переважним у багатьох випадках. Наприклад, в завданнях синтезу розкладів розподіляється задана множина робіт в часі і між обслуговуючими пристроями - серверами, тобто проектними параметрами для кожної роботи будуть номер сервера і порядковий номер в черзі на обслуговування. Хай N - число робіт, M - число серверів. Якщо гени відповідають номерам робіт, то в першому підході в хромосомі потрібно мати 2n генів і загальне число хромосом W, що відрізняються один від одного, помітно перевищує найбільше з чисел N!іMN.

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

.

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

Читайте також:

1. IV. Прийняття рішень у полі четвертої інформаційної ситуації
2. V. Завдання.
3. V. Прийняття рішень у полі п’ятої інформаційної ситуації
4. VI. Прийняття рішень у полі шостої інформаційної ситуації
5. VІ. Підсумки уроку і повідомлення домашнього завдання.
6. Адаптація персоналу: цілі та завдання. Введення у посаду
7. Адвокатура в Україні: основні завдання і функції
8. АКТУАЛЬНI ПРОБЛЕМИ І ЗАВДАННЯ КУРСУ РОЗМIЩЕННЯ ПРОДУКТИВНИХ СИЛ УКРАЇНИ
9. Актуальність і завдання курсу безпека життєдіяльності. 1.1. Проблема безпеки людини в сучасних умовах.
10. Аналіз альтернативних рішень
11. Аналіз для прийняття рішень стосовно залучення інвестицій
12. Аналіз економічноїї політики за допомогою моделі Мандела-Флемінга. Випадки вільного та фіксованого валютного курсів.

Переглядів: 930