Метод колоній в задачах оптимізації

МІНІСТЕРСТВО  ОСВІТИ І НАУКИ  УКРАЇНИ

Львівський  національний університет імені  Івана Франка

 Економічний факультет 
 
 

                                                                                          Кафедра

                                                                                          економічної кібернетики

                        

                                                                    

             
 
 
 

Індивідуальна робота

з курсу ”Економічний аналіз”

Тема: Метод колоній в задачах оптимізації 
 
 
 
 
 
 

                                                         Виконали

                                                                                      студенти групи ЕккМ – 51

                                                          Кіт Марія

                                                                     Лешко Світлана

                                                          Викладач 

                                                                                        Дацко М.В.             
 
 
 
 

Львів 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. Створення початкової популяції:
2. Обчислення функції пристосованості для осіб популяції (оцінювання)
3. Повторювання до виконання критерію зупинки алгоритму:

1. Вибір індивідів із поточної популяції (селекція)
2. Схрещення або/та мутація
3. Обчислення функції пристосовуваності для всіх осіб
4. Формування нового покоління

Також виділяють  такі етапи генетичного алгоритму  [1, с. 359]:

1. Створити початкову популяцію 
2. Цикл за поколіннями, поки не виконана умова зупинки 
           / / Цикл життя одного покоління 
            3. Оцінити пристосованість кожної особини. 
            4. Виконати відбір за пристосованістю. 
             5. Випадковим чином розбити популяцію на дві групи пар. 
             6. Виконати фазу ймовірнісної рекомбінації для пар популяції і замінити батьків 
             7. Виконати фазу ймовірнісної мутації. 
             8. Оцінити пристосованість нової популяції і обчислити умови зупинки. 
              9. Оголосити нащадків новим поколінням 
10. Кінець циклу за поколіннями. 

      У завданнях структурного синтезу (задача структурного синтезу полягає у відшуканні оптимальної або раціональної структури (схеми) технічного об'єкта для реалізації заданих функцій у рамках обраного принципу дії. Результати структурного синтезу можуть бути подані у вигляді переліку елементів разом з таблицею з'єднань; схеми алгоритмів; схеми розташування елементів із указівкою їхніх типів і т.п. [5]) будь-яка структура (альтернатива) представляється значеннями структурних параметрів – множини [4]. У генетичних методах множині відповідає запис, який називається хромосомою, елементи хромосоми відповідають параметрам , їх називають генами, а значення генів – алелями. Кожен ген розміщується в хромосомі в деякій позиції – локусі. У разі геометричної інтерпретації кожному гену відповідає одна з осей координатного простору, а хромосомі – деяка точка пошукового простору.