Posibniki.com.ua Інформатика Прикладні системи штучного інтелекту Тема 18. ПРИКЛАДНІ СИСТЕМИ КОЛЕКТИВНОГО ІНТЕЛЕКТУ SWARM INTELLIGENCE


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

Тема 18. ПРИКЛАДНІ СИСТЕМИ КОЛЕКТИВНОГО ІНТЕЛЕКТУ SWARM INTELLIGENCE


ОСНОВНІ ПРИНЦИПИ КОЛЕКТИВНОГО ІНТЕЛЕКТУ

ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК

Після опанування теми студент має знати:

• мультиагентні методи інтелектуальної оптимізації, що моделюють колективний інтелект;

• принципи колективного інтелекту;

• відмінності між різновидами методу мурашиних колоній;

• переваги й недоліки методу мурашиних колоній;

• біонічні основи методу бджолиної колонії;

• особливості модифікацій методів бджолиної колонії;

• напрями використання PSO-методу;

• відмінності й особливості модифікацій методу бджолиної колонії.

Має вміти:

• представити прикладну мультиагентну систему в загальному вигляді;

• застосовувати метод мурашиних колоній;

• використовувати метод бджолиних колоній;

• застосовувати метод оптимізації на основі моделювання переміщення бактерій для розв’язання задач.

Розділ 7

ЗМІСТ ПИТАНЬ З ТЕМИ

18.1. Біологічні основи мурашиних колоній

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

Новим напрямом розвитку методів ПСШІ є мультиагентні методи інтелектуальної оптимізації, що моделюють колективний інтелект (КІ) суспільних тварин, комах та інших живих істот, — методи Swarm Intelligence. Цей напрям ШІ є молодим і мало дослідженим, проте мультиагентні методи надають хороші результати у розв’язанні різних задач оптимізації, що свідчить про перспективність його розвитку.

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

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

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

Для реалізації указаних методів використовується парадигма агентно-орієнтованого програмування, заснована на моделюванні суспільного інтелекту. До них належать: метод мурашиних колоній (Ant Colony Optimization, ACO), метод бджолиної колонії (Bee Colony Optimization, BCO), оптимізація за допомогою рою часток (Particle Swarm Optimization, PSO) та інші методи. Дані методи вже ефективно застосовуються для розв’язання різних задач; ACO застосовується для вирішення завдань комівояжера, календарного планування, відбору інформативних ознак, кластеризації тощо; BCO — для вирішення задач календарного планування, задач комівояжера, вирішення транспортного завдання та ін.

Прикладну мультиагентну систему (ПМАС) у загальному випадку можна подати у вигляді множини з трьох елементів: Агенти, Середовище, Зв’язки між Середовищем та Агентами:

МАС=<Агенти, Середовище, Зв’язки>.

Кожен і-ий Агент i описується за допомогою множини чотирьох елементів: Стан i , Вхід i , Вихід i , Процес i :

Агент i = <Стан i , Вхід i , Вихід i , Процес i >, де Стан i — це множина змінних, що повністю визначають агента; Вхід i та Вихід i — підмножина Стану i , елементи яких пов’язані із середовищем.

Процес i — автономний метод, що виконує відповідні зміни над Станом. «Автономний метод» означає, що даний метод викликається без будь-якого зовнішнього впливу.

Середовищем являється множина з двох елементів:

Середовище = <Стан с , Процес с >, де індекс с інформує про те, що дані елементи належать до середовища, а не до будь-якого іншого агента.

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

Вхід i та Вихід i різноманітних агентів пов’язані з елементами Стану с , але середовище не відрізняє, які з елементів Стану с перебувають у залежності з ними. Відсутність Входу та Виходу у Середовища означає, що воно, на відміну від агентів, є необмеженим. Якби в Середовище були додані Вхід та Вихід, то це означало б, що середовище обмежене та є фактично агентом високого

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

Рис. 7.1. Класифікація мультиагентних систем

Рис. 7.1. Класифікація мультиагентних систем

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

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

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

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

рівня. Отже, може моделюватися взаємодія агентів високого та низького рівнів.

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

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

Кооперація спостерігається в процесі добування їжі, коли окремого індивіда недостатньо, щоб доставити їжу. Відомо багато прикладів спільного транспортування їжі різними видами мурах. Таке транспортування їжі може бути дуже ефективним для доставки їжі в гніздо. Наприклад, мурахи Pheidologeton diversus спільно можуть транспортувати в десять разів більшу вагу, ніж якби вони робили це поодинці.

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

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

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

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

Кожна зі складових виявляється на колективному рівні за рахунок непрямої взаємодії між особинами. Така взаємодія забез-

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

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

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

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

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

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

Мірмекологи (зоологи, котрі спеціалізуються на вивченні мурах) підрозділяють мурах на 12 сучасних і вимерлих підвидів, які об’єднують 197 родів. А всього відомо близько 15 тис. різновидів мурах. Довжина робочих мурах — 0,8—30 мм, самки крупніші.

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

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

печує можливість оцінювання зовнішньої інформації за двома основними напрямами.

Мурахи належать до так званих соціальних комах, тобто комах, які живуть у межах певного колективу — сім’ї або колонії. На Землі близько двох відсотків комах є «соціальними», половина з яких припадає на мурах. Поведінка мурах під час транспортування їжі, долання перешкод, побудови мурашника тощо наближається до теоретично оптимальної. Основою «соціальної» поведінки мурах є самоорганізація сукупність динамічних механізмів, за допомогою яких система досягає глобальної мети в результаті взаємодії елементів на низькому рівні. Принциповою особливістю такої низькорівневої взаємодії є використання елементами системи лише локальної інформації, без будь-якого централізованого управління та звернення до глобального образу, який репрезентує систему в зовнішньому світі. Самоорганізація є результатом взаємодії таких чотирьох компонентів:

1) випадковість;

2) додатний зворотний зв’язок;

3) від’ємний зворотний зв’язок;

4) багатократність взаємодій.

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

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

Мурахи використовують два способи передавання інформації: прямий

— обмін харчами, мандибулярний, візуальний та хімічний контакти тощо, та непрямий

стигмержі.

складається головно із самок. Життєвий цикл усіх мурах триває від 8 до 10 тижнів і включає 4 стадії: яйце ? личинка ? лялечка ? зріла особа.

Стигмержі — це рознесений у часовому просторі тип взаємодії між елементами системи, коли один суб’єкт взаємодії змінює деяку частину навколишнього середовища, а решта використовує інформацію про її стан пізніше, коли перебувають в її околі. Біологічно стигмержі здійснюється за допомогою феромону — спеціального секрету, що відкладається як слід під час руху мурахи. Чим вища концентрація феромону на стежці, тим більше мурах буде рухатись по ній. Феромон з часом випаровується, що дозволяє мурахам адаптувати свою поведінку до зміни навколишнього середовища. Розподіл феромону по простору пересування мурах є своєрідною глобальною пам’яттю, яка динамічно змінюється. Кожна мураха може сприймати та змінювати лише локальну чарунку цієї глобальної пам’яті мурашника.

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

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

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

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

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

Крім основних складових, самоорганізація характеризується певними властивостями.

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

2. Емерджентність: властивості систем, що самоорганізуються, є більш складними, ніж властивості окремих агентів, що входять у неї. Такі властивості системи є результатом нелінійної комбінації взаємодій між агентами.

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

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

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

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

привести за собою інших робочих особин для розроблення цього джерела їжі.

Приклад непрямого зв’язку — накладання слідів феромону, виконуване деякими різновидами мурах.

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

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

Під час проведення експериментів колонії мурах Аргентини Linep-ithema humile було надано два шляхи ідентичної довжини, і після того, як минув певний час, було відзначено, що мурахи сходилися до однієї з доріжок, після чого фактично була виключена альтернатива. Щоб перевірити, чи сходився б цей вид мурах до найбільш короткого з множини шляхів, було проведено подвійний експеримент мосту, де мурахи повинні були вибирати двічі між коротким і довгим шляхами (рис. 7.2).

Рис. 7.2. Подвійний експеримент асиметричного мосту

Рис. 7.2. Подвійний експеримент асиметричного мосту

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

Колективна поведінка біологічних мурах забезпечує знаходження найкоротшого шляху до їжі на прикладі експериментів на асиметричному мості. Асиметричний міст (рис. 7.2) з’єднує гніздо мурах із джерелом їжі двома гілками різної довжини. Експерименти проводилися за такою схемою:

1) будувався міст А-В-С-D;

2) відчинялися дверцята в точці А;

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

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

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

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

18.2. Метод мурашиних колоній

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

Узагальнену схему роботи методу мурашиних колоній подано на рис. 7.3.

Рис. 7.3. Узагальнена схема роботи методу мурашиних колоній

Рис. 7.3. Узагальнена схема роботи методу мурашиних колоній

Першим завданням, до якого було застосовано метод мурашиних колоній, було завдання комівояжера (Traveling Salesman

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

Першим методом був метод мурашиних систем (Ant System — AS). Надалі цей метод послужив основою для багатьох інших методів, що працюють на принципі мурашиних колоній.

У методі мурашиних систем агент формує своє рішення в процесі переміщення від одного вузла до іншого на графі рішень. Метод працює до виконання t max ітерацій. На кожній ітерації агенти формують свої рішення за n кроків, на кожному з яких застосовується правило вибору наступного вузла — правило вибору агентом, що перебуває у вузлі r, наступного вузла для переміщення в нього.

Запропоновано три методи мурашиних систем, відмінних між собою способом оновлення шляхів — ребер. Ці методи називалися: щільнісний (ant-density), кількісний (ant-quantity) і циклічний (ant-cycle) методи мурашиних систем. У щільнісному й кількісному методах агенти залишали феромони в процесі формування рішення, у той час, як у циклічному методі агенти залишали феромони після закінчення переміщення, тобто після формування рішення.

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

Кількість феромонів ? ru (t), що їх залишає агент, відповідає дузі (r, u) — це кількість, що характеризує перевагу вибору даного ребра порівняно з іншими при переміщенні. Інформація про феромони на ребрах змінюється в процесі складання рішень. При цьому кількість феромонів, що залишається агентами, пропорційна якості рішення, сформованого відповідним агентом: чим коротший шлях, тим більше буде залишено феромону, і навпаки, чим довший шлях, тим менше буде залишено феромону на відповідних ребрах. Такий підхід дозволяє забезпечити безпосередній пошук у напрямку знаходження кращого рішення.

Пам’ять про вузли, які були відвідані агентом, забезпечується шляхом уведення так званого списку табу tList — у ньому збері-

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

Метод мурашиних колоній включає такі основні кроки:

Крок 1. Задати параметри методу: ? — коефіцієнт, що визначає відносну значущість шляху; ? — параметр, що показує значимість відстані; ? — коефіцієнт кількості феромону, що його залишає агент на шляху, де (1 – ?) показує коефіцієнт випаровування феромону на шляху після його завершення; Q — константа, що стосується кількості феромону, залишеного на шляху; startPheromone — початкове значення феромону, що знаходиться на шляхах до початку моделювання.

Крок 2. Ініціалізація методу. Створення популяції агентів. Після створення популяції агенти рівномірно розподіляються у вузлах мережі. Необхідно розподіляти агентів рівномірно між вузлами, щоб усі вузли мали однакові шанси стати відправною точкою. Якщо всі агенти розпочнуть рух з однієї точки, це означало б, що дана точка вважається оптимальною для старту, а насправді вона такою може й не бути. Водночас, якщо кількість агентів не кратна кількості вузлів, то кількість агентів у вузлах буде різною, але ця різниця не повинна перевершувати 1.

Крок 3. Рух агентів. Якщо агент іще не закінчив шлях, тобто не відвідав усі вузли мережі, для визначення наступного ребра шляху розраховується ймовірність переходу в u-ий вузол, коли агент перебуває в r-му вузлі, за такою формулою: )1( )()( )()( rand tt tt P Jk rkrk ruru ru > ??? ??? = ? ? ?? ?? , де P ru — імовірність того, що агент переміститься в u-ий вузол з r-го вузла; rand(1) — випадкове число в інтервалі (0; 1); J — множина вузлів, ще не відвіданих агентом; ? ru (t) — інтенсивність феромону на ребрі між вузлами r та u у момент часу t; ? ru (t) — функція, що репрезентує вимір зворотної відстані для ребра.

Агент переміщується тільки по тих вузлах, які ще не були відвідані (відзначені списком табу tList). Тому ймовірність розраховується тільки для ребер, які ведуть до ще не відвіданих вузлів.

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

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

Крок 4. Після завершення переміщень агентів може бути підрахована довжина шляху. Вона дорівнює сумі всіх ребер, по яких подорожував агент. Кількість феромону, що була залишена на кожному ребрі шляху i-го агента, визначається за формулою: де ?? i (t) — кількість феромону, що його залишив i-ий агент; L i (t)

— довжина шляху i-го агента. Змінна Q є постійною.

довжина шляху i-го агента. Змінна Q є постійною.

Результат є засобом виміру шляху: короткий шлях характеризується високою концентрацією феромону, а більш довгий шлях

— більш низькою. Потім отриманий результат використовується для збільшення кількості феромону вздовж кожного ребра, пройденого i-им агентом шляху за формулою: N де r, u — вузли, що утворюють ребра, які відвідав i-ий агент; N ru — загальна кількість агентів, що відвідали ребро ru.

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


< Попередня  Змiст  Наступна >
Iншi роздiли:
18.7. Особливості модифікацій методів бджолиної колонії
18.11. ПСШІ на основі переміщення бактерій
18.16. Людино-машинні інтерфейси (human-computer interface, HCI)
17.13. Узагальнена схема роботи генетичних методів
17.10. Стандартний генетичний алгоритм
17.7. Генетичний та еволюційний пошук
Тема 17. ЕВОЛЮЦІЙНІ ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ ТА МОДЕЛІ
Нейро-нечітка модель діяльності компанії
Дисциплiни

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

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