I detta papper, vi bevisa polynomiska körtider gränser för två Ant Colony Optimization (ACO) algoritmer för två problem, One-Max och den enda-destination kortaste vägar problem på riktade acykliska grafer. Mer specifikt, vi utökar det senaste resultatet av Neumann och Witt på One-Max, till fallet med flera myror genom att visa att vår multipel-ant algoritm körs i ) logg (noder och m kanter. Vi anser att detta är den första tidsanalysen av en ACO-baserad algoritm på ett praktiskt problem. Vi föreslår också ett nytt begrepp om konvergens, som kallas girig konvergens.
Den första utredningen av ACO för kortaste väg problem har gjorts av REF.
A Running Time Analysis for an Ant Colony Optimization Algorithm for Shortest Paths on Directed Acyclic Graphs
{'venue': 'Inf. Process. Lett.', 'journal': 'Inf. Process. Lett.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}