Вплив параметрів генетичного алгоритму на ефективність пошуку

Оператори кросовера та мутації. Найбільш традиційним підходом є відхід від традиційної схеми “розмноження”, що використовується у більшості ГА-маx і що повторює класичну схему. Класична схема передбачає обмеження потомків шляхом використання так званої вірогідності кросовера. Така модель надає величині, що відповідає чисельності потомків, узагалі кажучи, недетермінований храктер. Є метод, що пропонує відійти від вірогідності кросовера і використовувати фіксоване число шлюбних пар на кожному поколінні, при цьому кожна шлюбна пара дає двох потомків. Такий підхід добрий тим, що дає процес пошуку більш передбачених обчислювальних затрат.

Як генетичні оператори отримуємо нові генотипи “потомків”, використовуючи генетичну інформацію хромосомних наборів батьків, ми використовуємо два типи кросоверів одно-та двоточкових. Обчислювальні експерименти показали, що навіть для простих функцій не можна говорити про переваги того або іншого оператора. Більше того показано, що використання механізму випадкового вибору одно- або двоточкового кросовера для кожної конкретної шлюбної пари іноді є більш ефективним, ніж детермінований підхід до вибору кросоверів, оскільки достатньо важко визначити, який з двох операторів більше підходить для конкретного ланшафту пристосування. Використання ж випадкового вибору мало за мету перш за все згладити відмінності цих двох підходів і поліпшити показники середнього очікуваного результату. Для всіх представлених функцій так і вийшло, – випадковий вибір є ефективніший від гіршого.

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

Другий спосіб вибору особин у батьківську пару – так званий селективний. Його суть полягає у тому, що батьками можуть стати тільки і особини, значення пристосованості яких не менше від середнього значення пристосованості до популяції, при рівних вирогідностях таких кандидатів утворити шлюбну пару. Такий підхід забезпечує більш швидку збіжність алгоритму. Однак через швидку збіжність селективний вибір батьківської пари не підходить тоді, коли ставиться задача визначення декількох екстремумів, оскільки для таких задач алгоритм, як правило, швидко збігається до одного з розв’язків. Крім того, для деякого класу задач із укладеним лагшафтом пристосованості швидка збіжність може перетворитися у передчасну збіжність до квазіоптимального розв’язку. Цей недолік може бути частково може бути компенсований використанням такого механізму відбору, який би гальмував надто швидку збіжність алгоритму. Інші два способи формування батьківської пари, на які хотілося б звернути увагу – це інбридинг й аутбридинг. Ці обидва методи побудовані на формуванні пари на основі близького та далекі спорідненості відповідно. Під спорідненістю тут розуміють відстань між членами популяції у розумінні геометричної відстані особин у просторі параметрів. У зв’язку з цим розрізняють генотипний і фенотипний (або географічний) інбридинг та аутбридинг. Під інбридингом розуміють такий метод, коли перший член пари вибирається випадково, а другий з більшою вірогідністю буде максимально близькою до нього особиною. Аутбридинг – навпаки, формує шлюбні пари з максимально далеких собин. Використання генетичних інбридингу та аутбридинга є більш ефективним порівняно з географічним для всіх тестових функцій за наявності різних параметрів алгоритмів. Найбільш корисне застосування обох представлених методів для багатоекстремальних задач. Однак два ці способи по-різному впливають на поведінку генетичного алгоритму. Так, інбридинг характеризується своєю концентрацією пошуку в локальних вузлах, що фактично призводить до розбиття популяції на окремі локальні групи навколо підозрілих на екстремуми ділянки ланшафту. Навпаки, аутбридинг якраз направлений на попередження збіжності алгоритму до вже знайдених розв’язків, примушуючи алгоритм переглядати нові, недосліджені області.

Механізм відбору. Найбільш ефективні два механізми відбору – елітний та відбір з витісненням.

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

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

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

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

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

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

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

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

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

Контрольні запитання

1. Який алгоритм називається детермінованим?

2. Що називається алгоритмом у програмуванні?

3. Наведіть приклади алгоритмів, які використовуються у повсякденному житті.

4. Що називається розміром задачі?

5. Що називається часовою і місткісною складністю алгоритму?

6. Чим відрізняється складність алгоритму від складності опису алгоритму?

7. Що є більш важливим: ефективність алгоритму чи швидкість роботи комп¢ютера? Обґрунтуйте відповідь.

8. У чому полягає зміст генетичного алгоритму?

Лекція 7

Задачі оптимального керування. Методи розв’язання задач лінійного керування. Задачі на умовний екстремум

1. Поняття про математичне моделювання економічних задач.

2. Різні форми задач лінійного програмування.

3. Геометричний зміст задач лінійного програмування при n=2, 3.