Метод колоній в задачах оптимізації
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Львівський національний університет імені Івана Франка
Економічний
факультет
Індивідуальна робота
з курсу ”Економічний аналіз”
Тема:
Метод колоній в задачах
оптимізації
Львів 2010
ПЛАН
Вступ
1.
Оптимізація методом
1.1. Опис алгоритму.
1.2. Етапи генетичного алгоритму.
1.3. Застосування генетичних алгоритмів.
2. Мурашині алгоритми оптимізації.
3. Метод бджолиних колоній.
3.1. Біологічні основи методу бджолиної колонії.
3.2. Формалізація поведінки бджіл в процесі фуражування.
3.3. Метод бджолиної колонії в задачах дискретної оптимізації.
Висновки.
Список використаної літератури.
Вступ
Оптимізація — процес надання будь-чому найвигідніших характеристик чи співвідношень.
Мета даної роботи – аналіз методів колоній, призначених для розв’язання задач оптимізації, зокрема методу еволюційної оптимізації (в тому числі генетичні алгоритми), методів мурашиних та бджолиних колоній.
Метод
еволюційної оптимізації –
Генетичний метод – еволюційний метод структурного синтезу та параметричної оптимізації, заснований на моделюванні деяких властивостей механізму спадковості, що має місце в живій природі.
Метод
мурашиних колоній –
При розв’язанні задач комбінаторної оптимізації досить перспективними є використання методів, заснованих на моделюванні інтелектуальної поведінки колоній агентів.
Один з найновіших методів даного напрямку – метод бджолиних колоній. Він являє собою евристичний ітеративний метод випадкового пошуку і застосовується для розв’язку різних задач оптимізації, які відносяться як до дискретної, так і до неперервної оптимізації.
1. Оптимізація методом еволюційного розвитку. Генетичний алгоритм.
Еволюція — термін, який позначає сукупність усіх змін у популяції організмів протягом поколінь.
Методи еволюційного розвитку – це скоріше не методи обробки даних, а загальний підхід до побудови моделей, який може використовуватися в різних методах. Ідея еволюційних методів (ЕМ) запозичена у природи. Процес еволюції в природі базується на трьох головних принципах: спадковості, мінливості та відборі.
Спадковість — здатність передавати з покоління в покоління спадкові ознаки, збереження й відтворення у нащадків основних ознак зовнішньої та внутрішньої будови, фізико-хімічних особливостей і життєвих функцій батьків [8].
Мінливість – це можливість змін невеликої частини ознак (мутацій), що забезпечує гнучкість і можливість розвитку [8].
Відбір
– це перевірка результатів, той механізм,
який дозволяє розділити хороші і погані
властивості. Тобто відбір – це процес,
завдяки якому сприятливі спадкові характеристики
стають більш загальними в наступних поколіннях
популяції організмів, що розмножуються,
а несприятливі спадкові характеристики
стають менш загальними.
Рис.1. Загальна схема процесу еволюції
Ці принципи можна використовувати для вирішення найрізноманітніших завдань. Підхід з використанням вищенаведених принципів називається еволюційним.
У загальному випадку схема процесу еволюції [6] виглядає так (Рис.1): дано об'єкт або декілька об'єктів, стан яких потрібно покращити. Об'єктом може бути майже все що завгодно: набір чисел, математична формула, технічний пристрій, хімічний склад, комп'ютерна програма і т.д. Далі створюється кілька копій вихідних об'єктів, які не є абсолютно точними, кожна має невеликі відмінності. Необхідно перевірити, які з отриманих об'єктів найкраще відповідають поставленим вимогам. Вибравши найкращі, знову копіюємо їх з невеликими змінами і знову вибираємо найкращі. Повторивши таку операцію багато разів, ми можемо значно покращити вихідний об'єкт. Ідея ця дуже проста і давно використовується, наприклад, при виведенні сортів рослин та порід тварин. Але досить часто використовувати еволюційні методів може бути надто складно. Процес еволюції може вимагати тисяч поколінь, виготовляти і перевіряти такі кількості реальних фізичних об'єктів, що часто є просто неможливим і майже завжди нерентабельним через величезний обсяг роботи. Але розвиток комп'ютерів відкрило перед еволюційними методами зовсім нові можливості. Замість того, щоб працювати з реальними об'єктами, можна працювати з їх математичними моделями.
Хоча еволюційні моделі підходять практично для будь-якої задачі, їх застосування не завжди є виправданим. Якщо ми хоча б приблизно можемо оцінити, як впливають зміни окремих ознак на якість об'єкта, то зазвичай можна зробити висновок, що є більш ефективні методи пошуку, ніж еволюційний. Чим складнішою є система і чим менше відомо про вплив окремих параметрів на поведінку системи в цілому, тим більш корисними можуть бути еволюційні методи. Їх цінність саме в тому, що зовсім не обов'язково знати, якими повинні бути зміни ознак для покращення стану об'єкта, ці зміни можуть вибиратися випадково.
До трьох основних принципів еволюційного процесу іноді додають четвертий – схрещування. Хоча схрещування і не є обов'язковим для еволюційних методів, воно дозволяє значно збільшити їх ефективність. Ідея полягає в тому, що різні об'єкти одного покоління можуть незалежно накопичувати різні корисні ознаки. Якщо для створення об'єкта нащадка береться лише один об'єкт батько, то для накопичення всіх корисних ознак може знадобитися дуже багато поколінь, адже зміни невеликі і випадкові. Схрещування – це спосіб створення об'єкта нащадка, за якого половина властивостей береться від одного об'єкта – батька, а друга половина від іншого. Це дозволяє відразу об'єднати корисні властивості, незалежно накопичені обома об'єктами-батьками в одному об'єкті-нащадку.
Методи, що реалізують еволюційний пошук з використанням схрещування, часто називають генетичними алгоритмами.
Генетичний алгоритм — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію [7].
Особливістю
генетичного алгоритму є акцент
на використання оператора "схрещення",
який виконує операцію рекомбінацію
рішень-кандидатів, роль якої аналогічна
ролі схрещення в живій природі.
1.1. Опис алгоритму
Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так: «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується "генетичні оператори" (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація [7].
Так
моделюється еволюційний
- знаходження глобального, або надоптимального вирішення;
- вичерпання числа поколінь, що відпущені на еволюцію;
- вичерпання часу, відпущеного на еволюцію.
Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих і складних просторах пошуку.
1.2. Етапи генетичного алгоритму.
Можна виділити наступні етапи генетичного алгоритму [7]:
- Створення початкової популяції:
- Обчислення функції пристосованості для осіб популяції (оцінювання)
- Повторювання до виконання критерію зупинки алгоритму:
- Вибір індивідів із поточної популяції (селекція)
- Схрещення або/та мутація
- Обчислення функції пристосовуваності для всіх осіб
- Формування нового покоління
Також виділяють такі етапи генетичного алгоритму [1, с. 359]:
1. Створити початкову
популяцію
2. Цикл за поколіннями,
поки не виконана умова зупинки
/ / Цикл життя одного
покоління
3. Оцінити пристосованість
кожної особини.
4. Виконати відбір за
пристосованістю.
5. Випадковим чином
розбити популяцію на дві групи пар.
6. Виконати фазу ймовірнісної
рекомбінації для пар популяції і
замінити батьків
7. Виконати фазу ймовірнісної
мутації.
8. Оцінити пристосованість
нової популяції і обчислити умови зупинки.
9. Оголосити нащадків
новим поколінням
10. Кінець циклу
за поколіннями.
У завданнях структурного синтезу (задача структурного синтезу полягає у відшуканні оптимальної або раціональної структури (схеми) технічного об'єкта для реалізації заданих функцій у рамках обраного принципу дії. Результати структурного синтезу можуть бути подані у вигляді переліку елементів разом з таблицею з'єднань; схеми алгоритмів; схеми розташування елементів із указівкою їхніх типів і т.п. [5]) будь-яка структура (альтернатива) представляється значеннями структурних параметрів – множини [4]. У генетичних методах множині відповідає запис, який називається хромосомою, елементи хромосоми відповідають параметрам , їх називають генами, а значення генів – алелями. Кожен ген розміщується в хромосомі в деякій позиції – локусі. У разі геометричної інтерпретації кожному гену відповідає одна з осей координатного простору, а хромосомі – деяка точка пошукового простору.
Очевидно, що в більшості практично значущих завдань структурного синтезу число можливих альтернатив настільки велике, що явне подання безлічі альтернатив є неможливо. Тому в кожний момент пошуку генетичний алгоритм оперує підмножиною альтернатив потужності N, що становлять деякі N точок простору структурних параметрів. Цю підмножину називають популяцією, а N – розміром популяції. Хромосома, представлена конкретними значеннями своїх генів, є проектною альтернативою або примірником хромосоми.
Основна ідея генетичного алгоритму полягає в еволюції популяції, що повторює деякі риси еволюції організмів в живій природі [4]. Якщо мета еволюції в живій природі – забезпечення найбільшої життєздатності популяції в умовах навколишнього середовища, то мета еволюції в генетичних алгоритмах – отримання зразків з найкращими значеннями певних критеріїв, що характеризують якість зразка.
Будь-який конкретний екземпляр хромосоми називають генотипом (комплекс усіх генів організму, які зумовлюють спадкові властивості), а сукупність характеристик, властивих індивіду на певній стадії розвитку – фенотипом.
Таким чином, мета генетичного пошуку – знайти примірник хромосоми, що має значення функції корисності, максимально близьку до її екстремального значення. Спрямований пошук малої околиці екстремуму здійснюється в генетичних алгоритмах за допомогою генетичних операторів вибору батьків, кросовера, мутації, селекції, що пояснюємо нижче.
Генетичні алгоритми імітують еволюційний процес наближення до оптимального результату, починаючи з деякого вихідного покоління структур, представлених примірниками хромосом. Цей процес у базовому генетичному алгоритмі є вкладеним циклічним обчислювальним процесом. Зовнішній цикл імітує зміну поколінь. У внутрішньому циклі формуються члени чергового покоління.
Члени вихідного покоління генеруються випадковим чином [4]. При цьому для кожного гена задана область визначення, наприклад, у вигляді інтервалу , та значення генів вибираються з рівною імовірністю в його межах. Результатом кожного чергового витка зовнішнього циклу є нове покоління, про якість якого судять по примірнику хромосоми з кращим значенням функції корисності F. Характер наближення до екстремуму зазвичай такий, що на початкових витках швидкість поліпшення цільової функції досить значна, але в міру наближення до екстремуму вона сповільнюється і може наступити припинення поліпшення F на деякому віддаленні від екстремальної точки. Це явище називають стагнацією. Зазвичай воно відбувається через виродження популяції – втрати різноманітності генного матеріалу. Пошук припиняють найчастіше при появі ознак стагнації, про що свідчить відсутність покращення стану цільової функції протягом кількох останніх поколінь, або після закінчення відведеного часу на вирішення завдання.
У внутрішньому циклі базового ГА виконується наступна послідовність генетичних операторів: вибір батьків, кросовер (схрещування), мутації, формування нового покоління.
Породження нових екземплярів хромосом відбувається в процесі схрещування (кросовера) батьківських пар. Вибір пари членів популяції як батьків виробляється випадковим чином серед членів даного покоління. При цьому ймовірність вибору примірників як батьків у базовому генетичному алгоритмі залежить від значень їх функції корисності, тобто чим краще значення F, тим вищою повинна бути ймовірність вибору.
Частіше
за все для вибору батьків застосовують
правило, зване правилом рулетки. У ньому
ймовірність Pk вибору k-го члена
популяції як батька визначається як відношення
корисності даного члена до сумарної корисності
всіх членів популяції. Якщо цільова функція
мінімізується, то
=(
-
)/
(
-
)
де - функція корисності k-го примірника, - максимальне значення функції корисності серед членів даного покоління, - розмір популяції.
Схрещення (кросове) полягає в розриві двох обраних батьківських хромосом і рекомбінуванні створених хромосомних відрізків, що дає пару хромосом-нащадків.
Мутації, тобто випадкові зміни деяких алелей, призначені для реалізації пошуку в просторі всіх можливих примірників хромосом. Без мутацій пошук не може вийти за межі тієї підмножини примірників хромосом, в якій алелі співпадають із згенерованими значеннями генів в початковій популяції.
Формування
нового покоління (селекція) – це відбір
членів нового покоління серед нащадків,
отриманих в результаті схрещення і мутацій
в даному поколінні. У базовому генетичному
алгоритмі в нове покоління включається
кращий з двох нащадків, породжених після
схрещення. Внутрішній цикл закінчується,
коли виявиться сформованим нове покоління,
тобто в ньому виявиться N членів.
1.3. Застосування генетичних алгоритмів [1, с. 360-361]
Основна проблема, пов'язана з використанням генетичних алгоритмів - це їх евристичний характер. Говорячи більш строго, яка ймовірність досягнення популяцією глобального оптимуму в заданій області? В даний час не існує відповіді і теоретично обґрунтованих оцінок. Є припущення, що генетичний алгоритм може стати ефективною процедурою пошуку оптимального рішення, якщо:
- простір пошуку досить великий;
- завдання не вимагає знаходження глобального оптимуму, необхідно досить швидко знайти прийнятне «хороше» рішення, що досить часто зустрічається в реальних завданнях.
Генетичний алгоритм є в певному сенсі універсальним методом, тобто він явно не враховує специфіку задачі або повинен бути для неї налаштований.
Наявність
у генетичних алгоритмів цілої «популяції»
розв’язків, спільно з імовірнісним механізмом
мутації, дозволяють припускати
меншу ймовірність знаходження локального
оптимуму й більшу ефективність роботи
на багатоекстремальному ландшафті. Сьогодні
генетичні алгоритми успішно застосовуються
для вирішення задач оптимізації в просторах
з великою кількістю вимірювань, низки
економічних завдань оптимального характеру,
наприклад, завдань розподілу інвестицій.
2. Мурашині алгоритми оптимізації [2].
Мурахи належать до так званих «соціальних комах», тобто комах, що живуть в межах певного колективу — сім'ї або колонії. На Землі біля двох відсотків комах є «соціальними», половина з яких припадає на мурах. Поведінка мурах під час транспортування їжі, обминання перешкод, побудови мурашника тощо наближається до теоретично оптимальної. Основу «соціальної» поведінки мурах складає самоорганізація — сукупність динамічних механізмів, за допомогою яких система досягає глобальної мети в результаті взаємодії елементів на низькому рівні. Принциповою особливістю такої низькорівневої взаємодії є використання елементами системи лише локальної інформації, без будь-якого централізованого управління та звернення до глобального образу, який репрезентує систему у зовнішньому світі. Самоорганізація є результатом взаємодії таких чотирьох компонентів:
1) випадковість;
2) додатний зворотний зв'язок;
3) від'ємний зворотний зв'язок;
4) багатократність взаємодій.
Мурахи використовують два способи передачі інформації: прямий — обмін харчами, мандибулярний, візуальний та хімічний контакти тощо, та непрямий — стигмержі. Стигмержі — це рознесений у часовому просторі тип взаємодії між елементами системи, коли один суб'єкт взаємодії змінює деяку частину оточуючого середовища, а решта використовує інформацію про її стан пізніше, коли знаходяться в її околі. Біологічно, стигмержі здійснюється через феромон — спеціальний секрет, який відкладається як слід під час руху мурахи. Чим вища концентрація феромону на стежці, тим більше мурах буде рухатись по ній. Феромон з часом випаровується, що дозволяє мурахам адаптувати свою поведінку до зміни оточуючого середовища. Розподіл феромону по простору пересування мурах є своєрідною глобальною пам'яттю, яка динамічно змінюється. Кожна мураха може сприймати та змінювати лише локальну чарунку цієї глобальної пам'яті мурашника.
Рис.2. Асиметричний
міст
Розглянемо, як колективна поведінка біологічних мурах забезпечує знаходження найкоротшого шляху до їжі на прикладі експериментів на асиметричному мості [2, с. 63]. Асиметричний міст (рис.2) з'єднує гніздо мурах з джерелом їжі двома гілками різної довжини. Експерименти проводилися за такою схемою:
1) будувався міст А-В-С-D;
2) відчинялися дверцята в точці А;
3)
фіксувалась кількість мурах, які обрали
довгий (А-С-D) та короткий (А-В-D) На початку
експериментів мурахи обирали обидві
гілки з однаковою ймовірністю тому, що
на мості не було феромонів. Через деякий
час майже усі мурахи пересувались найкоротшим
маршрутом А-В-D, що пояснюється таким чином.
Мурахи, які обрали короткий маршрут А-В-D-В-А,
скоріше поверталися з їжею в гніздо, залишаючи
феромонні сліди на короткій гілці мосту.
При наступному виборі маршруту мурахи
віддавали перевагу короткій гілці мосту,
тому що на ній вища концентрація феромонів.
Таким чином, феромон швидше накопичується
на гілці А-В-D, що підштовхує мурах до вибору
найкоротшого маршруту.
3. Метод бджолиних колоній.
При
розв’язанні задач
Один
з найновіших методів даного напрямку
– метод бджолиних колоній. Він являє
собою евристичний ітеративний метод
випадкового пошуку і застосовується
для розв’язку різних задач оптимізації,
які відносяться як до дискретної, так
і до неперервної оптимізації.
3.1. Біологічні основи методу бджолиної колонії [3, с. 15]
Для описання поведінки бджіл в природі використовуються три основні поняття: джерело нектару (квітка), зайняті робочі бджоли (фуражири), незайняті робочі бджоли.
Джерело нектару характеризується значенням, що визначається різними факторами: відстанню від вулика, концентрація нектару, зручністю його добування.
Зайняті робочі бджоли закріплені за віддаленим джерелом, в якому вони добувають нектар, тобто «зайняті» ним. Зайняті робочі бджоли володіють такою інформацією про дане джерело нектару, як: відстань і напрямок від вулика, корисність джерела.
Незайняті робочі бджоли продовжують шукати джерела нектару для їх використання. Існує два типи незайнятих робочих бджіл: розвідники, які шукають нові джерела нектару, і спостерігачі, які чекають у вулику і можуть там виконувати інші дії.
Кожна незайнята бджола може полетіти до джерела нектару за бджолою-розвідником, яка знайшла дорогу до квітки. Це досягається за рахунок того, що кожний вулик має так звану закриту площину для танцю, на якій бджоли, знайшовши джерело нектару, виконують «зигзагоподібний танець», тим самим намагаються привабити інших незайнятих бджіл іти за ними. Якщо бджола вирішує залишити вулик, щоб дістати нектар, вона летить за однією із бджіл-розвідників до місця з нектаром. Таким чином, незайнята бджола стає занятою. Механізми, у відношенні з якими вона вирішує іти за іншою бджолою, дослідженні недостатньо добре, але припускається, що вербування серед бджіл з математичної точки зору завжди являється функцією якості джерела нектару.
Після досягнення місця з нектаром зайняті робочі бджоли добувають нектар і повертаються у вулик, залишаючи нектар там. Після того як бджола залишає нектар, вона може виконувати одне із наступних трьох дій: покинути джерело нектару і знову стати незайнятою робочою бджолою; продовжувати літати до того джерела з нектаром, не вербуючи інших особин свого вулика; виконати танець і таким чином завербувати інших. Бджола вибирає одну із альтернатив з деякою ймовірністю.
Таким чином, виконується поділ функцій між занятими бджолами і бджолами-розвідниками на покращене вивчення знайдених з нектаром і знаходження нових місць з нектаром відповідно. За рахунок такого розподілу обов’язків досягається ефективна робота всього рою бджіл.
3.2. Формалізація поведінки бджіл в процесі фуражування [3, с. 16]
Існує модель поведінки самоорганізації колонії бджіл. В ній робочі бджоли переміщаються до квіток (джерел нектару), повертаються у вулик, а також володіють інформацією про користь відповідного джерела нектару. Зібраний нектар забезпечує зворотній зв'язок з теперішнім становищем потоку нектару у вулику. Корисність – функція якості нектару, кількість нектару і відстань від вулика. Зворотній зв'язок встановлює відповідний поріг для сигналу вербування,також відомого як зигзагоподібний танець, довжина якого залежить і від порогу, і від корисності. Зигзагоподібний танець виконується на спеціальній площадці для танців. Робочі бджоли можуть випадковим чином вибирати танець для спостереження і у відповідності з цим танцем вибирати місцезнаходження ділянки квітки і покинути вулик для фуражирування.
