Ant Colony Optimization (ACO) är en sorts metaheuristic som har blivit mycket populär för att lösa problem från combinatorial optimering. Lösningar för ett givet problem är konstruerade av en slumpmässig gång på en så kallad byggkurva. Denna slumpmässiga gång kan påverkas av heuristisk information om problemet. I motsats till många framgångsrika tillämpningar är den teoretiska grunden för denna typ av metaheuristisk ganska svag. Teoretiska undersökningar med avseende på ACO-algoritmers runtime-beteende har inletts först nyligen för optimering av pseudo-Booleska funktioner. Vi presenterar den första omfattande rigorösa analysen av en enkel ACO-algoritm för ett kombinatoriskt optimeringsproblem. I våra undersökningar, vi anser den minsta spännvidd träd (MST) problem och undersöka effekten av två konstruktion grafer med avseende på runtime beteende. Valet av konstruktionsgrafen i en ACO-algoritm verkar vara avgörande för att en sådan algoritm ska lyckas. Först tar vi indatagrafen själv som konstruktionsgrafen och analyserar användningen av en konstruktionsprocess som liknar Broders algoritm för att välja ett spännträd jämnt på måfå. Därefter analyseras en mer inkrementell konstruktionsprocess. Det visar sig att denna procedur är överlägsen den Broder-baserade algoritmen och producerar dessutom i ett konstant antal iterationer en MST, om inflytandet av den heuristiska informationen är tillräckligt stor.
Neumann och Witt REF föreslog en ACO för att lösa problemet med minsta spännvidd.
Ant Colony Optimization and the minimum spanning tree problem
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}