Binary-coding-based ant colony optimization and its convergence |
| |
Authors: | Email author" target="_blank">Tian-Ming?BuEmail author Song-Nian?Yu Hui-Wei?Guan |
| |
Affiliation: | (1) School of Computer Engineering and Science, Shanghai University, 200072 Shanhai, P.R. China;(2) Department of Computer Science, North Shore Community College, 01923, MA, USA |
| |
Abstract: | 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 ρ is under the condition of ρ≥1, the algorithm can promise to converge at the optimal, whereas if 0<ρ<1, it does not.
This work is supported by the Science Foundation of Shanghai Municipal Commission of Science and Technology under Grant No.00JC14052.
Tian-Ming Bu received the M.S. degree in computer software and theory from Shanghai University, China, in 2003. And now he is a Ph.D.
candidate of Fudan University in the same area of theory computer science. His research interests include algorithms, especially,
heuristic algorithms and heuristic algorithms and parallel algorithms, quantum computing and computational complexity.
Song-Nian Yu received the B.S. degree in mathematics from Xi'an University of Science and Technology, Xi'an, China, in 1981, the Ph.D.
degree under Prof. L. Lovasz's guidance and from Lorand University, Budapest, Hungary, in 1990. Dr. Yu is a professor in the
School of Computer Engineering and Science at Shanghai University. He was a visiting professor as a faculty member in Department
of Computer Science at Nelson College of Engineering, West Virginia University, from 1998 to 1999. His current research interests
include parallel algorithms' design and analyses, graph theory, combinatorial optimization, wavelet analyses, and grid computing.
Hui-Wei Guan received the B.S. degree in electronic engineering from Shanghai University, China, in 1982, the M.S. degree in computer
engineering from China Textile University, China, in 1989, and the Ph.D. degree in computer science and engineering from Shanghai
Jiaotong University, China, in 1993. He is an associate professor in the Department of Computer Science at North Shore Community
College, USA. He is a member of IEEE. His current research interests are parallel and distributed computing, high performance
computing, distributed database, massively parallel processing system, and intelligent control. |
| |
Keywords: | ant colony optimization genetic algorithm binary-coding convergence heuristic function optimization |
本文献已被 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
|