Journal
INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS
Volume 19, Issue 3, Pages 305-334Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0218213010000200
Keywords
Bee colony optimization; traveling salesman problem; local search; combinatorial optimization; metaheuristic
Categories
Funding
- Universiti Sains Malaysia
- Ministry of Higher Education of Malaysia
Ask authors/readers for more resources
Many real world industrial applications involve the Traveling Salesman Problem (TSP), which is a problem that finds a Hamiltonian path with minimum cost. Examples of problems that belong to this category are transportation routing problem, scan chain optimization and drilling problem in integrated circuit testing and production. This pap er presents a Bee Colony Optimization (BCO) algorithm for symmetrical TSP. The BCO model is constructed algorithmically based on the collective intelligence shown in bee foraging behaviour. The algorithm is integrated with a fixed-radius near neighbour 2-opt (FRNN 2-opt) heuristic to further improve prior solutions generated by the BCO model. To limit the overhead incurred by the FRNN 2-opt, a frequency-based pruning strategy is proposed. The pruning strategy allows only a subset of the promising solutions to undergo local optimization. Experimental results comparing the proposed BCO algorithm with existing approaches on a set of benchmark problems are presented. For 84 benchmark problems, the BCO algorithm is able to obtain an over all average solution quality of 0.31% from known optimum. The results also show that it is comparable to other algorithms such as Ant Colony Optimization and Particle Swarm Optimization.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available