Мрављи алгоритам

У информатици и операционим истраживањима је мрављи алгориам (енгл. Ant colony optimization algorithms, АЦО) пробабилистичка техника за решавање рачунарских проблема који се могу редуковати на налажење путања кроз графове.^[1]

Истраживања колективног понашања мрава и пчела омогућила су научницима из рачунарских наука да развију разне методе за оптимизацију. Ови алгоритми су се показали као флексибилни и робусни у динамичким окружењима каква се срећу код свих врста саобраћаја: транспорта возила, компјутерских мрежа или телефоније.

Основна карактеристика колективног понашања мрава је да сви чланови колоније индиректно или директно размењују информације о свом окружењу, тј. присутан је феномен колективне интелигенције.^[2]^[3] У природи је откривено да сваки мрав за собом оставља траг, испуштајући одређену количину хемијске супстанце која се зове феромон. Што више мрава иде једном путањом, више је и феромона, а то је за сваког следећег мрава „позитивна информација“ о исправности те путање. На овај начин мрави посредно, преко феромона, међусобно комуницирају. Применом овог принципа колонија мрава проналази најкраћи пут до хране.

У природи је такође примећено:

Не бирају сви мрави путању са највише феромона, већ поједини мрави бирају алтернативне путеве. Утврђено је да сваки мрав бира путању са највише феромона са одређеном вероватноћом.
Битна карактеристика феромона, као хемијске супстанце, је да током времена испарава. Тако рута коју мрави не користе након неког времена остаје без феромона, и самим тим постаје мање „интересантна“ за остале чланове колоније.

Једну од примена мрављи алгоритми су нашли у решавању проблема рутирања возила.

Референце[уреди | уреди извор]

^ M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.
^ A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.
^ M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.

Литература[уреди | уреди извор]

Марцо Дориго, 1992. Оптимизатион, Леарнинг анд Натурал Алгоритхмс, ПхД тхесис, Политецницо ди Милано, Италy.
Дориго, M.; Маниеззо, V.; Цолорни, А. (1996). „Ант сyстем: Оптимизатион бy а цолонy оф цооператинг агентс”. ИЕЕЕ Трансацтионс он Сyстемс, Ман, анд Цyбернетицс, Парт Б (Цyбернетицс). 26 (1): 29—41. ПМИД 18263004. дои:10.1109/3477.484436. .
Дориго, M.; Гамбарделла, L.M. (1997). „Ант цолонy сyстем: А цооперативе леарнинг аппроацх то тхе травелинг салесман проблем”. ИЕЕЕ Трансацтионс он Еволутионарy Цомпутатион. 1 (1): 53—66. дои:10.1109/4235.585892. .
Дориго, M.; Ди Царо, Г.; Гамбарделла, L. M. (1999). „Ант алгоритхмс фор дисцрете оптимизатион”. Артифициал Лифе. 5 (2): 137—172. ПМИД 10633574. С2ЦИД 990370. дои:10.1162/106454699568728. .
Е. Бонабеау, M. Дориго ет Г. Тхераулаз, 1999. Сwарм Интеллигенце: Фром Натурал то Артифициал Сyстемс, Оxфорд Университy Пресс. ISBN 0-19-513159-2
M. Дориго & Т. Стüтзле, 2004. Ант Цолонy Оптимизатион, МИТ Пресс. ISBN 0-262-04219-3
M. Дориго, 2007. "Ант Цолонy Оптимизатион". Сцхоларпедиа.
C. Блум, 2005 "Ант цолонy оптимизатион: Интродуцтион анд рецент трендс". Пхyсицс оф Лифе Ревиеwс, 2: 353-373
M. Дориго, M. Бираттари & Т. Стüтзле, 2006 Ант Цолонy Оптимизатион: Артифициал Антс ас а Цомпутатионал Интеллигенце Тецхниqуе. ТР/ИРИДИА/2006-023
Мохд Муртадха Мохамад,"Артицулатед Роботс Мотион Планнинг Усинг Форагинг Ант Стратегy",Јоурнал оф Информатион Тецхнологy - Специал Иссуес ин Артиﬁциал Интеллигенце, Вол.20, Но. 4 пп. 163–181, Децембер 2008, ИССН0128-3790.
Н. Монмарцхé, Ф. Гуинанд & П. Сиаррy (едс), "Артифициал Антс", Аугуст 2010 Хардбацк 576 пп. ISBN 978-1-84821-194-0.
Зборник год. 27, Број 18, страна 3815-3818 - Фацултy оф Тецхницал Сциенцес - РУТИРАЊЕ ВОЗИЛА ПРИМЕНОМ МРАВЉЕГ АЛГОРИТМА ИССН0350-428X

Спољашње везе[уреди | уреди извор]

[M._Dorigo_et_L.M._Gambardella-1] M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.

[2] A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.

[M._Dorigo,_Optimization,_Learning_and_Natural_Algorithms-3] M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.

[1]

[2]

[3]