Колективний інтелект

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Застосування[ред.ред. код]

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

Використання[ред.ред. код]

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

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

Програми[ред.ред. код]

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

Телекомунікації[ред.ред. код]

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

Авіація[ред.ред. код]

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

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

Алгоритм альтруїзму[ред.ред. код]

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

Алгоритм колонії мурах[ред.ред. код]

Мурашиний алгоритм (алгоритм оптимізації мурашиної колонії, англ. 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 році.[8] Він імітує поведінку кормових медоносних бджіл. Алгоритм ABC складається з трьох етапів: робочої бджоли, бджоли-наглядача, та бджоли-розвідника. Бджоли використовують алгоритм локального пошуку в околі рішення, що вибрані на основі детермінованого відбору робочими бджолами і імовірнісного відбору бджолами-наглядачами. Бждола-розвідник виконує відмову від виснажених джерел живлення в кормовому процесі. За цією аналогією рішення, які не корисні більше для пошуку розв'язку відкидаються, і додаються нові рішення (за аналогією з дослідженням нових регіонів у пошуку джерел).

Метод рою часток[ред.ред. код]

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

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

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

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

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

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

Штучна імунна система[ред.ред. код]

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

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

Алгоритм зозулі[ред.ред. код]

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

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

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

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

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

Інші алгоритми[ред.ред. код]

Відомі вчені[ред.ред. код]

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

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

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

Література[ред.ред. код]

Примітки[ред.ред. код]

  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 9781583333907. 
  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. «"Planes, Trains and Ant Hills: Computer scientists simulate activity of ants to reduce airline delays». Science Daily. April 1, 2008. Процитовано December 1, 2010. 
  6. Altruism helps swarming robots fly better 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 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 by Maurice Clerc, ISTE, ISBN 1-905209-04-5, 2006.
  11. de Castro, Leandro N.; Timmis, Jonathan (2002). Artificial Immune Systems: A New Computational Intelligence Approach. Springer. с. 57–58. ISBN 1852335947, 9781852335946 Перевірте значення |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.