Habr 25+Муравьи против трансформеров: старый алгоритм 1992 года, который вернулся
Начну с признания: истории формата «природа оптимизирует лучше людей» меня обычно раздражают, слишком уж часто это все притянуто за уши. Но с муравьями история действительно странная, и мне ее захотелось проверить. Короткая справка по нашему герою. Аргентинский муравей Linepithema humile в миллиметр длиной, с глазами у него все плохо, а в мозге около 250 000 нейронов (у нас, напомню, 86 млрд). Карты местности он не помнит. В 1989 году четверо бельгийских биологов поставили этим муравьям простой эксперимент — гнездо, еда, два мостика, где один длиннее другого в два раза. Через несколько минут вся колония сошлась на короткой ветке в 100% прогонов. И все это без координатора, без плана и без голосования. Через три года этот эксперимент превратится в Ant Colony Optimization — алгоритм, который я сегодня натравлю на классический TSP-бенч и получу 0,10% отставания от оптимума. А в 2023, через 34 года после наблюдений в Брюсселе, тот же алгоритм вернулся на NeurIPS в качестве бэкбона для графовых нейросетей. Что же, приступим.
#ACO #задача_коммивояжера #DeepACO #комбинаторная_оптимизация #NeurIPS #графовые_нейросети #стигмергия #selectel #ai #ml
Habr