🐜 Мурашиний алгоритм оптимізації

Мурашиний алгоритм оптимізації (ant colony optimization, ACO) — це ймовірнісна метаевристика, натхненна пошуковою поведінкою справжніх мурах, які залишають феромонні сліди під час руху й надають перевагу слідам, залишеним іншими, тож коротші шляхи накопичують феромон швидше і посилюються з кожним наступним проходом. Запропонований Марко Доріго на початку 1990-х, алгоритми ACO симулюють популяцію віртуальних мурах, які покроково будують кандидатні розв'язки, керуючись поєднанням сили феромону та евристичної привабливості, а потім відкладають віртуальний феромон пропорційно якості розв'язку, тоді як старий феромон з часом випаровується. Цей простий контур зворотного зв'язку дозволяє колонії колективно знаходити близькі до оптимальних розв'язки складних комбінаторних задач, як-от задача комівояжера чи маршрутизація в мережах, без жодного центрального координатора. Випаровування феромону критично важливе для успіху алгоритму: без нього феромон на ранніх, можливо, неоптимальних шляхах постійно зростав би й тримав би всю колонію в локальному оптимумі, тоді як стала швидкість розпаду дозволяє слабшим слідам згасати, щоб кращі маршрути, знайдені пізніше, могли все ж перемогти. Оскільки рішення кожної мурахи залежить лише від локальних концентрацій феромону та простих імовірнісних правил, ACO добре масштабується на великі задачі й легко розпаралелюється, тому лишається стандартним інструментом для маршрутизації транспорту, календарного планування виробництва та інших NP-складних задач оптимізації.