Binary-Coding-Based Ant Colony Optimization and Its Convergence  

作　　者：Tian-MingBu Song-NianYu Hui-WeiGuan 

机构地区：[1]SchoolofComputerEngineeringandScience,ShanghaiUniversity,Shanhai200072,P.R.China [2]DepartmentofComputerScience,NorthShoreCommunityCollege,MA01923,USA

出　　处：《Journal of Computer Science & Technology》2004年第4期472-478,共7页计算机科学技术学报（英文版）

基　　金：上海市科委资助项目

摘　　要：Ant colony optimization (ACO for short) is a meta-heuristics for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. In this paper, genetic algorithm's (GA for short) ideas are introduced into ACO to present a new binary-coding based ant colony optimization. Compared with the typical ACO, the algorithm is intended to replace the problem's parameter-space with coding-space, which links ACO with GA so that the fruits of GA can be applied to ACO directly. Furthermore, it can not only solve general combinatorial optimization problems, but also other problems such as function optimization. Based on the algorithm, it is proved that if the pheromone remainder factor rho is under the condition of rho greater than or equal to 1, the algorithm can promise to converge at the optimal, whereas if 0 < rho < 1, it does not.Ant colony optimization (ACO for short) is a meta-heuristics for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. In this paper, genetic algorithm's (GA for short) ideas are introduced into ACO to present a new binary-coding based ant colony optimization. Compared with the typical ACO, the algorithm is intended to replace the problem's parameter-space with coding-space, which links ACO with GA so that the fruits of GA can be applied to ACO directly. Furthermore, it can not only solve general combinatorial optimization problems, but also other problems such as function optimization. Based on the algorithm, it is proved that if the pheromone remainder factor rho is under the condition of rho greater than or equal to 1, the algorithm can promise to converge at the optimal, whereas if 0 < rho < 1, it does not.

关 键 词：ant colony optimization genetic algorithm binary-coding CONVERGENCE HEURISTIC function optimization 

分 类 号：TN911.22[电子电信—通信与信息系统]