Колекти вний інтеле кт англ swarm intelligence термін що описує комплексну колективну поведінку децентралізованої систем

Колекти́вний інтеле́кт (англ. swarm intelligence) — термін, що описує комплексну колективну поведінку децентралізованої системи із самоорганізацією. Розглядається в теорії штучного інтелекту як метод оптимізації. Термін запровадили Херардо Бені й Ван Цзин у 1989 році у контексті системи клітинних роботів. Інколи колективний інтелект ще називають ройовим інтелектом.

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

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

Застосування

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

Використання

Дизайнери використовують технології рою як засіб створення складних інтерактивних систем і моделювання натовпу. «Розбиваючи лід» — був перший фільм, що використовував технології колективного інтелекту для візуалізації, реалістичного зображення руху груп риб і птахів із використанням Boids системи. Тім Бертон створив фільм «Бетмен повертається» також з використанням технології колективного інтелекту для демонстрації руху груп кажанів. У фільмі «Володар перснів» використовували подібну технологію, відому як технологія масивів, під час батальних сцен. Такі технології є особливо привабливими, тому що використання колективного інтелекту — це дешевий, надійний і простий спосіб.

Авіакомпанії використовують теорію колективного інтелекту під час моделювання пасажирів перед посадкою в літак. Дослідник Дуглас Лоусон використовував мурах на основі комп'ютерного моделювання та визначив існування лише шести правил взаємодії пасажирів та спромігся оцінити час посадки з використанням різних методів посадки. (Miller, 2010, XII–XVIII).

Програми

Колективний інтелект може бути використаний у цілому ряді програм. Збройні сили США використовують методи колективного інтелекту для управління безпілотними транспортними засобами. Європейське космічне агентство думає про «орбітальний рій» для самостійної збірки і інтерферометрії. NASA досліджує використання технології колективного інтелекту для створення планетарних карт. У 1992 році робота М. Anthony Lewis and George A. Bekey довела можливість використання розвідки роєм, за допомогою колективного інтелекту для контролю нанороботів у тілі з метою знищення ракових пухлин. Також колективний інтелект застосовується для інтелектуального аналізу даних.

Телекомунікації

Використання колективного інтелекту в телекомунікаційних мережах також досліджували, у вигляді основ мурашиної маршрутизації. Це було вперше відкрито Dorigo та Hewlett Packard в середині 1990-х років із низкою змін з тих пір. В основному це використання імовірнісних таблиць маршрутизації з використанням «нагородження» — зміцнення успішно пройденого маршруту кожної «мурашки» (невеликий пакет управління), який проходить у мережі. Посилення маршруту вперед, у зворотному напрямку, і обидва одночасно були досліджені. У зворотному напрямку зміцнення вимагає симетричної мережі і пар в обох напрямках разом. Мобільні засоби масової інформації і нові технології можуть змінити поріг для колективних дій у зв'язку з ростом інтелекту систем.

Авіація

Авіакомпанії використовували мурашину маршрутизацію в призначенні воріт для літака, що прибуває в аеропорт. В авіакомпанії Southwest програма використовує колективний інтелект, тобто теорію, що колонія мурашок працює краще, ніж поодинці. Кожен пілот працює як мураха в пошуках найкращих воріт в аеропорт. «Пілот вчиться на власному досвіді, що найкраще для нього, і виявляється, що це найкраще рішення для авіакомпанії» пояснює Дуглас Лоусон. У результаті роботи колонії, кожен пілот завжди прямує до вільних воріт.

Приклади алгоритмів, що використовують колективний інтелект

Алгоритм альтруїзму

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

Алгоритм колонії мурах

Докладніше: Мурашиний алгоритм

Мурашиний алгоритм (алгоритм оптимізації мурашиної колонії, англ. ant colony optimization, ACO) — один з ефективних поліноміальних алгоритмів для знаходження наближених рішень задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах. Підхід запропонований бельгійським дослідником Марко Доріго (англ. Marco Dorigo). Суть підходу полягає в аналізі та використанні моделі поведінки мурах, що шукають дороги від колонії до їжі. У основі алгоритму лежить поведінка — маркування вдалих доріг великою кількістю феромону. Робота починається з розміщення мурашок у вершинах графа (містах), потім починається рух мурашок — напрям визначається імовірнісним методом, на підставі формули:

P_{i}={\frac {{l_{i}}^{q}\cdot {f_{i}}^{p}}{\sum _{k=0}^{N}{{l_{k}}^{q}\cdot {f_{k}}^{p}}}}

,

де:

P_{i}

— імовірність переходу дорогою

i

,

l_{i}

— довжина

i

-ого переходу,

f_{i}

— кількість феромонів на

i

-ому переході,

q

— величина, яка визначає «жадібність» алгоритму,

p

— величина, яка визначає «стадність» алгоритму і

q+p=1

.

Бджолиний алгоритм

Докладніше: Бджолиний алгоритм

Штучний алгоритм бджолиної сім'ї (ABC) — алгоритм рою на основі мета-евристичного алгоритму було введено Карабогом у 2005 році. Він імітує поведінку кормових медоносних бджіл. Алгоритм ABC складається з трьох етапів: робочої бджоли, бджоли-наглядача, та бджоли-розвідника. Бджоли використовують алгоритм локального пошуку в околі рішення, що вибрані на основі детермінованого відбору робочими бджолами і імовірнісного відбору бджолами-наглядачами. Бждола-розвідник виконує відмову від виснажених джерел живлення в кормовому процесі. За цією аналогією рішення, які не корисні більше для пошуку розв'язку відкидаються, і додаються нові рішення (за аналогією з дослідженням нових регіонів у пошуку джерел).

Метод рою часток

Докладніше: Метод рою часток

Метод рою часток, МРЧ (англ. Particle Swarm Optimization, PSO) — метод чисельної оптимізації, для використання якого не потрібно знати точного градієнта оптимізованої функції. МРЧ був доведений , і Шіі, спочатку призначався для імітації . Алгоритм був спрощений, і було зауважено, що він придатний для виконання оптимізації. Книга Кеннеді й Еберхарта описує багато філософських аспектів МРЧ і так званого ройового інтелекту. Велике дослідження застосувань МРЧ зроблене Полі.

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

Алгоритм гравітаційного пошуку

Докладніше: Алгоритм гравітаційного пошуку

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

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

Штучна імунна система

Докладніше: Штучна імунна система

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

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

Алгоритм зозулі

Докладніше: Алгоритм зозулі

Алгоритм зозулі (англ. Cuckoo search) являє собою оптимізований алгоритм, розроблений англ. Xin-She Yang та англ. Suash Deb у 2009 році. Натхненням для його створення послужив гніздовий паразитизм деяких видів зозуль, що підкладають свої яйця до гнізд інших птахів (інших видів птахів). Деякі з власників гнізд можуть вступити у прямий конфлікт із зозулями, що вдираються до них. Наприклад, якщо власник гнізда виявить, що яйця не його, то він або викине ці чужі яйця або просто покине гніздо і збудує нове десь в іншому місці.

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

Алгоритм інтелектуальних крапель води

Докладніше: Алгоритм інтелектуальних крапель

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

Інші алгоритми

(англ. Bacterial foraging optimization).
(англ. Stochastic diffusion search).

Відомі вчені

Колективний інтелект в популярній культурі

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

Популярний радянський письменник С. Ф. Гансовський, в оповіданні «Господар затоки» (1962), описав морське чудовисько, що складається з мікроскопічних частинок, які можуть самоорганізовуватися в єдине ціле.
Зерги в Starcraft демонструють поняття рою, коли в групах посилюється психічний контроль. Понадлюдський розум не контролює кожну особу, вказуючи їй, а використовує її власні думки.
Письменник Олаф Степлдон, описав у своїх книгах колективний інтелект рівний або вищий людського. В Останні і перші люди (1931), рій з розвідки Марса складається з крихітних окремих клітин, що взаємодіють одна з одною за допомогою радіохвиль, в Зірка Maker (1937) на колективному інтелекті засновані численні цивілізації, що складаються зі зграй птахів.
Decipher по Стел Павлу розповідає про колективний інтелект нанороботів, що мешкають в Атлантиді.
«Рій», розповідь Брюса Стерлінга про місію, здійсненою групою людей, щоб зрозуміти і використовувати космічні розумні рої.
«Хакер і мурашки», книга Руді Рукер про кібер мурах у віртуальному середовищі.
«Непереможний» — фантастичний роман Станіслава Лема, де людина знаходить космічний корабель, який має розумну поведінку та керується зграєю розумних дрібних часток, що здатні до самозахисту.
У романі «Штам Андромеда», автором якого є Майкл Крайтон, вірус із космосу спілкується між окремими клітинами і відображає здатність думати і реагувати окремо і в цілому.
У грі Mass Effect, галактична раса, відома як Quarians, створила живі машини відомі як гети. Гети, володіють обмеженим штучним інтелектом і навичками вирішення проблем, поодинці, але автоматично створюють мережі один з одним, коли знаходься в групах. Це означає, що можливості машини для вирішення проблем збільшується відповідно до розміру групи.
Науково-фантастичний роман «Рій» німецького автора Френка Шетцінга (2005) описує одноклітинних істот, які діють в унісон, щоб знищити людство.

Література

Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с.
Swarm Intelligence: From Natural to Artificial Systems by Eric Bonabeau, Marco Dorigo and Guy Theraulaz. (1999) ,
Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds by Mitchel Resnick.
Swarm Intelligence by James Kennedy and Russell C. Eberhart.
Fundamentals of Computational Swarm Intelligence [ 14 березня 2022 у Wayback Machine.] by Andries Engelbrecht. Wiley & Sons.
Nanocomputers and Swarm Intelligence [ 16 травня 2010 у Wayback Machine.] by Jean-Baptiste Waldner, ISTE, , 2007.
Miller, Peter (July 2007), , National Geographic Magazine, архів оригіналу за 10 листопада 2007, процитовано 22 серпня 2010
Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff,
— «From Ants to People: an Instinct to Swarm» — NY Times, 11-13-07 [ 9 травня 2012 у Wayback Machine.]
Swarm Intelligence (Journal) Chief Editor: Marco Dorigo. Springer New York. ISSN 1935-3812 (Print) 1935-3820 (Online) [1] [ 30 червня 2009 у Wayback Machine.]
Eva Horn, Lucas Marco Gisi (Ed.): Schwarme — Kollektive ohne Zentrum. Eine Wissensgeschichte zwischen Leben und Information, Bielefeld: transcript 2009.
Search methodologies edited by Edmund K. Burke, Graham Kendall. Springer. (2005) , (e-book)
Swarm Intelligence: From Natural to Artificial Systems by Eric Bonabeau, Marco Dorigo and Guy Theraulaz. (1999) ,
Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds by Mitchel Resnick.
Swarm Intelligence by James Kennedy and Russell C. Eberhart.
Fundamentals of Computational Swarm Intelligence [ 14 березня 2022 у Wayback Machine.] by Andries Engelbrecht. Wiley & Sons.
Nanocomputers and Swarm Intelligence [ 16 травня 2010 у Wayback Machine.] by Jean-Baptiste Waldner, ISTE, , 2007.
Miller, Peter (July 2007), , National Geographic Magazine, архів оригіналу за 10 листопада 2007, процитовано 22 серпня 2010
E. Ridge, D. Kudenko, D. Kazakov, and E. Curry, «Moving Nature-Inspired Algorithms to Parallel, Asynchronous and Decentralised Environments», [ 19 жовтня 2012 у Wayback Machine.] in Self-Organization and Autonomic Informatics (I), 2005, vol. 135, pp. 35-49.
Metaheuristic Optimization by Xin-She Yang, Scholarpedia article, cholarpedia, 6(8):11472 (2011 [2] [ 3 квітня 2012 у Wayback Machine.]
Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff,
- «From Ants to People: an Instinct to Swarm» — NY Times, 11-13-07 [ 9 травня 2012 у Wayback Machine.]
Swarm Intelligence (Journal) Chief Editor: Marco Dorigo. Springer New York. ISSN 1935-3812 (Print) 1935-3820 (Online) [3] [ 30 червня 2009 у Wayback Machine.]
Eva Horn, Lucas Marco Gisi (Ed.): Schwärme — Kollektive ohne Zentrum. Eine Wissensgeschichte zwischen Leben und Information, Bielefeld: transcript 2009.
L. Fisher, The Perfect Swarm : The Science of Complexity in Everyday Life, Basic Books, 2009.
E. Ridge and E. Curry, «A roadmap of nature-inspired systems research and development», [ 19 жовтня 2012 у Wayback Machine.] Multiagent and Grid Systems, vol. 3, no. 1, pp. 3-8, 2007.
«» by Carolin Kaiser, Johannes Kröckel, Freimut Bodendorf (2010) Proceedings of the 43rd Hawaii International Conference on System Sciences, pp. 1-9.

Примітки

Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26-30 (1989)
Miller, Peter (2010). The Smart Swarm: How understanding flocks, schools, and colonies can make us better at communicating, decision making, and getting things done. New York: Avery. ISBN .
Lewis M. Anthony. The Behavioral Self-Organization of Nanorobots Using Local Rules.
Martens, D.; Baesens, B.; Fawcett, T. (2011). Editorial Survey: Swarm Intelligence for Data Mining. Machine Learning. 82 (1): 1—42. doi:10.1007/s10994-010-5216-5.
. Science Daily. 1 квітня 2008. Архів оригіналу за листопад 24, 2010. Процитовано 1 грудня 2010.
Altruism helps swarming robots fly better [ 15 вересня 2012 у Wayback Machine.] genevalunch.com, 4 May 2011.
Waibel M, Floreano1 D and Keller L (2011) «A quantitative test of Hamilton's rule for the evolution of altruism»^{[недоступне посилання]}PLoS Biology, 9(5): e1000615. DOI:10.1371/journal.pbio.1000615
Karaboga, Dervis (2010) Artificial bee colony algorithm [ 3 квітня 2014 у Wayback Machine.] Scholarpedia, 5(3): 6915.
Parsopoulos, KE; Vrahatis, MN (2002). Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization. Natural Computing. 1 (2-3): 235—306. doi:10.1023/A:1016568309421.
Particle Swarm Optimization [ 22 лютого 2014 у Wayback Machine.] by Maurice Clerc, ISTE, , 2006.
de Castro, Leandro N.; Timmis, Jonathan (2002). . . с. 57—58. ISBN . {{}}: Перевірте значення |isbn=: недійсний символ ()
R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).
Shah-Hosseini, Hamed (2009). The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. International Journal of Bio-Inspired Computation. 1 (1/2): 71—79.
Гансовский С. Ф. Хозяин бухты (рассказ) // Мир приключений-7, 1962.

[1] Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26-30 (1989)

[2] Miller, Peter (2010). The Smart Swarm: How understanding flocks, schools, and colonies can make us better at communicating, decision making, and getting things done. New York: Avery. ISBN .

[3] Lewis M. Anthony. The Behavioral Self-Organization of Nanorobots Using Local Rules.

[4] Martens, D.; Baesens, B.; Fawcett, T. (2011). Editorial Survey: Swarm Intelligence for Data Mining. Machine Learning. 82 (1): 1—42. doi:10.1007/s10994-010-5216-5.

[5] . Science Daily. 1 квітня 2008. Архів оригіналу за листопад 24, 2010. Процитовано 1 грудня 2010.

[6] Altruism helps swarming robots fly better [ 15 вересня 2012 у Wayback Machine.] genevalunch.com, 4 May 2011.

[7] Waibel M, Floreano1 D and Keller L (2011) «A quantitative test of Hamilton's rule for the evolution of altruism»^{[недоступне посилання]}PLoS Biology, 9(5): e1000615. DOI:10.1371/journal.pbio.1000615

[8] Karaboga, Dervis (2010) Artificial bee colony algorithm [ 3 квітня 2014 у Wayback Machine.] Scholarpedia, 5(3): 6915.

[9] Parsopoulos, KE; Vrahatis, MN (2002). Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization. Natural Computing. 1 (2-3): 235—306. doi:10.1023/A:1016568309421.

[10] Particle Swarm Optimization [ 22 лютого 2014 у Wayback Machine.] by Maurice Clerc, ISTE, , 2006.

[11] Castro, Leandro N.; Timmis, Jonathan (2002). . . с. 57—58. ISBN . {{}}: Перевірте значення |isbn=: недійсний символ ()

[12] R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).

[13] Shah-Hosseini, Hamed (2009). The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. International Journal of Bio-Inspired Computation. 1 (1/2): 71—79.

[14] Гансовский С. Ф. Хозяин бухты (рассказ) // Мир приключений-7, 1962.