Алгоритм из 1992 года на 0,10% не дотягивает до идеала — и снова в моде

Аргентинский муравей располагает примерно 250 тысячами нейронов и скромным зрением, но колония без единого координатора безошибочно прокладывает кратчайший маршрут к цели. Как сообщает Хабр, биологи описали это поведение в 1989 году, а через три года оно стало алгоритмом Ant Colony Optimization (ACO).

На классической задаче коммивояжёра метод до сих пор отстаёт от оптимума всего на 0,10%. Для эвристики тридцатилетней давности это неплохо: современные архитектуры не всегда выглядят убедительнее.

На конференции NeurIPS алгоритм вернулся в новой роли — бэкбона для графовых нейросетей. Старые идеи, судя по всему, умеют ждать.