28.07.2008

1-Введение, история, 2-Оргкомитет, 3-Приз, 4-Статьи, книги, 5-Цели

Ant colony optimization "Алгоритм оптимизации подражанием муравьиной колонии" Sixth International Conference on Ant Colony Optimization and Swarm Intelligence Фото покрупнее >>> (115 Kb) "The Best Paper Award". Специальный приз за Лучшую Статью на ACO - 2008 (работа итальянского скульптора Matteo Pugliese)

VI международная конференция.

Брюссель, Бельгия,
22-24 сентября, 2008 г.
Universite Libre de Bruxelles, Campus du Solbosch, Building S (Sociologie, 1st floor), Av. Jeanne 44, 1050 Brussels. 2008.  

       VI международная конференция "Алгоритм оптимизации подражанием муравьиной колонии", Ant colony optimization, ACO

ИСТОРИЯ

Ant Colony Optimization and Swarm Intelligence Springer, 2006

Ant Colony Optimization and Swarm Intelligence Springer, 2004

Ant Algorithms Springer, 2002

Swarm intelligence Oxford University Press, 1999

       Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, ant colony optimization, ACO, или как я здесь впервые предлагаю термин, вынесенный в заголовок "Оптимизация по-муравьиному" - В.К.) — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра (отыскание самого выгодного маршрута методами вычислительной математики и компьютерной инженерии), а также аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к пище. В основе алгоритма лежит поведение муравьиной колонии — маркировка более удачных путей большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв — направление определяется вероятностным методом.

       Главные алгоритмы в системе ACO.
В литературе было предложено несколько метаэвристических моделей ACO. Я здесь только кратко набросаю основные исторические вехи на этом пути. Среди них три наиболее успешные:
1) ant system (Dorigo 1992, Dorigo et al. 1991, 1996),
2) ant colony system (ACS) (Dorigo & Gambardella 1997),
3) MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000).

       Впервые понятие о системах ACO (Ant Colony Optimization) было введено бельгийским исследователем Марко Дориго (Marco Dorigo) в его диссертации (Ph.D. thesis, 1992), и тогда названо как алгоритм "Ant System" (AS). Алгоритм AS является результатом исследования on computational intelligence approaches to combinatorial optimization, которые Дориго развил работая в Politecnico di Milano в сотрудничестве с Alberto Colorni и Vittorio Maniezzo. AS was initially applied to the travelling salesman problem, and to the quadratic assignment problem.

       С 1995 года Дориго, Лука-Мария Гамбарделла (Luca Maria Gambardella) и Томас Стацл (Thomas Stutzle) работали над различными версиями парадигмы AS. В 1997 году Дориго и Гамбарделла предложили Ant Colony System (ACS), в то время как Stutzle и H.H.Hoos в 2000 году выдвинули понятие MAX-MIN Ant System (MMAS). Обе методики были успешно применены для решения прорблемы ассиметрично и симметрично "путешествующего коммивояжера" (symmetric and asymmetric travelling salesman problem). Далее, Дориго Гамбарделла и Стацл также предложили гибридные версии ant colony optimization с локальным поиском. Алгоритм оптимизации подражанием муравьиной колонии был успешно применен к большому количеству трудных дискретных проблем оптимизации, включая the traveling salesman problem, the quadratic assignment problem, scheduling, vehicle routing, и т.д., а также к маршрутизации в телекоммуникационных сетях.

       Swarm intelligence - относительно новая дисциплина, которая имеет дело с изучением самоорганизации процессов и в природе и в искусственных системах. Исследователи в этологии и поведении животных предложили множество моделей, чтобы объяснить интересные аспекты поведения социальных насекомых таких как самоорганизация и shape-formation. Недавно были предложены алгоритмы, вдохновленные этими моделями, чтобы решить трудные вычислительные проблемы.

       Другим интересным подходом является particle swarm optimization, that focuses on continuous optimization problems. Here too, a number of successful applications can be found in the recent literature.

       Swarm robotics - другое важное поле из этой сферы. Here, the focus is on applying swarm intelligence techniques to the control of large groups of cooperating autonomous robots.



       Для ввода Вас в эти проблемы рекомендуем две прекрасные статьи по теме: в марте 2000 в журнале "Scientific American" и в публикации "Inspiration for Optimization from Social Insect Behavior" 6 июля 2000 в журнале Nature.

       Недавняя книга "Ant Colony Optimization" (Dorigo and Stutzle, 2004) дает полный обзор многих успешных областей применения Ant Colony Optimization.

       Профессор Марко Дориго (Marco Dorigo) является директором Belgian Funds for Scientific Research (FNRS) и содиректором лаборатории IRIDIA Брюссельского университета (artificial intelligence lab of the Universite Libre de Bruxelles). Он является разработчиком метаэвристики "Ant Colony Optimization" (см.список его публикаций ниже) и лидером этого поля исследований. За этот вклад он был в 2003 году награжден "Marie Curie Research Excellence Award" от имени European Commission, а 22 ноября 2005 года Король Бельгии Альберт II презентовал его как "FNRS - Dr A. De Leeuw-Damry-Bourlart award in Applied Sciences".

       Его коллега и соавтор Thomas Stutzle (IRIDIA, ULB, Brussels, Belgium) также работает профессором в Дармштадском технологическом университете в Германии (Assistant Professor in the Computer Science Department at Darmstadt University of Technology).

ЖУРНАЛ

       С 2007 года в Нью-Йорке издательством "Springer US" выпускается мультидисциплинарный журнал "Swarm Intelligence". Swarm Intelligence is the principal peer reviewed publication dedicated to reporting research and new developments in this multidisciplinary field. The journal publishes original research articles and occasional reviews on theoretical, experimental, and practical aspects of swarm intelligence. It offers readers reports on advances in the understanding and utilization of systems that are based on the principles of swarm intelligence.

       Причем на журнальной обложке воспроизводится название основополагающей в данной области книги "Swarm Intelligence. From Natural to Artificial Systems". - Eric Bonabeau, Marco Dorigo and Guy Theraulaz (1999, 320p.).

       Акцент дается таким темам как моделирование и анализ коллективных биологических систем; применение биологических моделей swarm intelligence к реально-мировым проблемам; теоретическое и эмпирическое исследование ant colony optimization, particle swarm optimization, swarm robotics, и других алгоритмов swarm intelligence. Статьи часто комбинируют экспериментальную и теоретическую работу.

ВСЕ КОНФЕРЕНЦИИ И СИМПОЗИУМЫ ПО ТЕМЕ

1. ANTS 2008: Sixth International Conference on Ant Colony Optimization and Swarm Intelligence, -- Brussels, Belgium, 22.-24. September 2008.



2. IEEE Swarm Intelligence Symposium 2007, -- Hilton Hawaiian Village, Honolulu, Hawaii, April 1-5, 2007. (IEEE = Institute of Electrical and Electronics Engineers, Inc.)



3. ANTS 2006: Fifth International Workshop on Ant Colony Optimization and Swarm Intelligence, -- Brussels, Belgium, 4.-7. September 2006.



4. IEEE Swarm Intelligence Symposium 2006, -- Indianapolis, Indiana, USA, 12.-14. May 2006.



5. ACO/Swarm Intelligence Track at GECCO 2005 -- Washington D.C., USA, June 25-29, 2005



6. IEEE 2005: Swarm Intelligence Symposium, -- The Westin Pasadena, Pasadena, California, USA, June 8-10, 2005.



7. ANTS 2004: Fourth International Workshop on Ant Colony Optimization and Swarm Intelligence, -- Brussels, Belgium, 5.-8. September 2004.



8. ANTS 2002 - From Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms, -- Brussels, Belgium, 11.-14. September 2002.



9. Special ACO session at MIC-2001 -- Porto, Portugal, July 16-20, 2001.



10. ACO special track at GECCO-2001 -- San Francisco, USA, July 7-11, 2001.



11. ANTS'2000 - From Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms, -- Brussels, Belgium, September 8-9, 2000.



12. Ant Colony Methods Session at 1999 Congress on Evolutionary Computation, -- Washington DC, USA, July 6-9, 1999



13. ANTS'98 - From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization, -- Brussels, Belgium, October 15-16, 1998.



14. Ant Colony Optimization Session at INFORMS Tel Aviv 1998 -- Tel Aviv, Israel, June 28 - July 1, 1998

Другие наши обзоры по теме: Теоретическая мирмекология и Ant colony optimization >>> Математики расчитали смертность во время муравьиных войн >>> Геометрия следа и полярность фуражировочных сетей Математика и траектории следов муравьев Моделирование движения муравьев Моделирование процессов ограничения и конкуренции в муравьиных скоплениях Временная организация bi-направленного движения у Lasius niger Lasius: плотность движения и столкновения >>> Постоянство следовых меток фуражиров Lasius niger >>> Lasius niger: все бегом по синусоиде на сбор сахара! Formica japonica: навигация и выбор визуальных ориентиров >>>       Другие сайты по теме: ANSI C implementation of Ant Colony Optimization Thomas Stutzle C# implementation of Ant Colony Optimization Lawrence Botley Java implementation of Ant Colony Optimization Andrew Carson Список диссертаций по теме Ant Colony Optimization VisualBots - бесплатный симулятор в Microsoft Excel AntSim v1.0 A visual simulation of Ant Colony Optimization with artificial ants (Windows Application) Ant Farm Simulator A simulation of ants food-gathering behaviour (Windows Application and source code available)

ЛИТЕРАТУРА

Мои дополнения по теме и полный список см.отдельно:

1. Бахем И., Лампрехт И. Гнездо лесных муравьев Formica polyctena как модель биологической системы // ЖОБ. 1983. Т. 44, № 1. С. 114 – 123.
   
   
2. Васильева Л. Л., Васильев В. В. Моделирование процесса обучения в Т-образном лабиринте по электро-оборонительной методике // «Муравьи и защита леса»: Матер. VIII Всес. мирмекол. симп. Новосибирск, 1987. С. 216 – 219.
   
   
3. Захаров А. А. Муравьи как модельный объект изучения динамики биоразнообразия // Динамика разнообразия животног мира: Тез. докл. Всерос. сов. М., 1997. С. 139 – 143.
   
   
4. Красильников В. А. Оптимизация начального периода развития семей дернового муравья Tetramorium caespitum путем первичного плеометроза // «Муравьи и защита леса»: Матер. X Всерос. мирмекол. симп. М., 1998. С. 17 – 19.
   
   
5. Пилецкис С. А. Опыт применения математико-статистического метода для учета муравейников в лесах Литовской ССР // «Муравьи и защита леса»: Матер. IV Всес. мирмекол. симп. М., 1971. С. 95 – 98.
   
   
6. Сулханов А. В. Возможный алгоритм перемещения относительно точечного источника света по незнакомой территории // Проблемы управления в технике, экономике, биологии. М., 1981. С. 184 – 190.
   
   
7. Удалова Г. П., Карась А. Я. Асимметрия направления движения у муравьев Myrmica rubra при обучении в лабиринте // Журн. высш. нерв. днят. 1985. Т. 35, № 2. С. 377 – 379.
   
   
   
   
8. Angus, Daniel (2007). "Crowding population-based ant colony optimisation for the multi-objective travelling salesman problem." [Proceedings] 2007 IEEE Symposium on Computational Intelligence in Multicriteria Decision Making (MCDM 2007), Honolulu, Hawaii, United States, 01-05 April 2007, p. 333-340.
   Ant inspired algorithms have recently gained popularity for use in multi-objective problem domains. One specific algorithm, Population-based ACO, which uses a population as well as the traditional pheromone matrix ... ... ...
   
   
9. Montgomery, James (2007). "Alternative solution representations for the job shop scheduling problem in ant colony optimisation." Lecture Notes in Computer Science : Progress in Artificial Life : [Proceedings] Third Australian Conference on Artificial Life (ACAL07), Gold Coast, Queensland, Australia, 04-06 December 2007, Vol. 4828, p. 1-12
   Ant colony optimisation (ACO), a constructive metaheuristic inspired by the foraging behaviour of ants, has frequently been applied to shop scheduling problems such as the job shop, in which a collection of operations (grouped into jobs) must be scheduled for processing on different machines ... ... ...
   
   
10. Montgomery, James; ... (2008). "Solution bias in ant colony optimisation : lessons for selecting pheromone models." Source Computers & Operations Research, Vol. 35, no. 9 (Sep 2008), pp. 2728-2749.
    Ant colony optimisation is a constructive metaheuristic in which solutions are built probabilistically influenced by the parameters of a pheromone model—an analogue of the trail pheromones used by real ants when foraging for food ... ... ...
    
    
    
    ПОЛНЫЙ СПИСОК ЛИТЕРАТУРЫ >>>
    
    
    
    ***
    
    
    

©2008, Vladislav Krasilnikov  

… [Муравьиные новости]. [История сайта]. [ФОТОГАЛЕРЕЯ]. [Библиография]. [Неотропика]. [ Австралия]. [Афротропика].[Голарктика]. [ Муравьи Северной Америки]. [Обзор родов]. [Мирмекологи].[Рабовладельцы].[Муравьи – паразиты]. [Грибководы и листорезы]. [Кочевые муравьи]. [Крылатые муравьи].[Медовые муравьи]. [Пустынные муравьи – бегунки и «фаэтончики»]. [Муравьиные «коровы»].[Мирмекофилы]. [Содержание муравьев].[Простые опыты с муравьями]. [ТЕРМИНОЛОГИЯ]. [Ссылки].[Разное]… [ МУРАВЬИ в Анекдотах, ...Афоризмах, Высказываниях, ...Поэзии и Прозе]. [Муравьиная БИБЛИОТЕКА]. [Журналы]. [Муравьиная ГАЛЕРЕЯ].[СМЕХОгалерея]. [Муравьиная Галактика].