2006 | OriginalPaper | Buchkapitel
A Time Complexity Analysis of ACO for Linear Functions
verfasst von : Zhifeng Hao, Han Huang, Xili Zhang, Kun Tu
Erschienen in: Simulated Evolution and Learning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The time complexity analysis of ant colony optimization (ACO) is one of the open problems in ACO research. There has been little proposed work on this topic recently. In the present paper, two ACO algorithms (ACO I and ACO II) for linear functions with Boolean input are indicated, and their time complexity is estimated based on drift analysis which is a mathematical tool for analyzing evolutionary algorithms. It is proved that the algorithm ACO II can find the optimal solution with a polynomial time complexity. It is a preliminary work about estimating the time complexity of ACO, which should be improved in the future study.