Research of ant colony algorithm and the application of 0–1 knapsack

Author

Ling He ; Yanyan Huang

Author_Institution

Software Coll., Xiamen Univ., Xiamen, China

fYear

2011

fDate

3-5 Aug. 2011

Firstpage

464

Lastpage

467

Abstract

Among the different works inspired by ant colonies, the ant colony algorithm (ACA) is probably the most successful and popular one. ACA is a novel bio-inspired optimization algorithm, which simulates the foraging behavior of ants for solving various complex combinatorial optimization problems. In this paper, a well-structured definition of basic ACA, detailed implementation process and complexity analyses of basic ACA are presented. It is also devoted to the explanation of improvement strategies of ACA in discrete space optimization and in continuous space optimization. In order to handle the 0/1 knapsack problem, it revises the model of ant algorithm and use the computer to test the modified algorithm. Finally, outlines some ongoing and most promising research trends in ACA.

Keywords

combinatorial mathematics; knapsack problems; optimisation; 0/1 knapsack problem; ACA; ant colony algorithm; bio-inspired optimization algorithm; combinatorial optimisation; continuous space optimization; discrete space optimization; Cities and towns; Computers; Educational institutions; Mathematical model; Optimization; Partitioning algorithms; Traveling salesman problems; ant colony algorithms; knapsack problem; pheromone; problem of TSP;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science & Education (ICCSE), 2011 6th International Conference on

Conference_Location

Singapore

Print_ISBN

978-1-4244-9717-1

Type

conf

DOI

10.1109/ICCSE.2011.6028680

Filename

6028680