2) Метод рою часток (англ. Particle swarm optimization).
) Бджолиний алгоритм (англ. Bees algorithm).
) Оптимізація пересуванням бактерій (англ. Bacterial foraging optimization).
) Стохастический дифузійний пошук (англ. Stochastic diffusion search).
) Алгоритм гравітаційного пошуку (англ. Gravitational search algorithm).
) Алгоритм крапель води (англ. Intelligent Water Drops algorithm).
) Свєтлякова алгоритм (англ. Firefly algorithm).
Мурашиний алгоритм (алгоритм оптимізації наслідуванням мурашиної колонії, англ. ant colony optimization, ACO) - один з ефективних поліноміальних алгоритмів для знаходження наближених рішень задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах. Суть підходу полягає в аналізі та використанні моделі поведінки мурах, що шукають шляхи від колонії до джерела живлення і являє собою метаеврістіческую (англ. metaheuristic, meta - «за межами» і heuristic - «знайти») оптимізацію. Перша версія алгоритму, запропонована доктором наук Марко Дориго в 1992 році, була спрямована на пошук оптимального шляху в графі.
В основі алгоритму лежить поведінка мурашиної колонії - маркування більш вдалих шляхів великою кількістю феромона. Робота починається з розміщення мурашок у вершинах графа (містах), затем починається рух мурашок - напрям визначається імовірнісним методом, на підставі формули виду:
,
де: вірогідність переходу по шляху, величина, зворотна вазі (довжині)-ого ??переходу, кількість феромону на-ом переході, величина, що визначає «жадібність» алгоритму, величина, що визначає «стадність» алгоритму і
Рішення не є точним і навіть може бути одним з найгірших, проте, в силу імовірнісний рішення, повторення алгоритму може видавати (достатньо) точний результат.
У літературі було запропоновано декілька метаеврістіческіх моделей 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)
У реальному світі, мурахи (спочатку) ходять у випадковому порядку і по знаходженню продовольства повертаються на свою колонію, прокладаючи феромонами стежки. Якщо інші мурахи знаходять такі стежки, вони, найімовірніше, підуть по них. Замість того, щоб відстежувати ланцюжок, вони зміцнюють її при поверненні, якщо зрештою знаходять джерело живлення. З часом феромонна стежка починає випаровуватися, тим самим зменшуючи свою привабливу силу. Чим більше часу потрібно для проходження шляху до цілі і назад, тим сильніше випарується феромонна стежка. На короткому шляху, для порівняння, проходження буде більш швидким і як наслідок, щільність феромонів залишається високою. Випаровування феромонів також має властивість уникнення прагнення до локально-оптимального рішення. Якби феромони не випаровується, то шлях, обраний першим, був би найпривабливішим. У цьому випадку, дослідження просторових рішень були б обмеженими. Таким чином, коли один мураха знаходить (наприклад, короткий) шлях від колонії до джерела їжі, інші мурахи, швидше за вс...
