A hybrid swarm intelligence algorithm for the travelling salesman problem |
| |
| Authors: | I‐Hong Kuo Shi‐Jinn Horng Tzong‐Wann Kao Tsung‐Lieh Lin Cheng‐Ling Lee Yuan‐Hsin Chen YI Pan Takao Terano |
| |
| Affiliation: | 1. Department of Electrical Engineering, National Taiwan University of Science and Technology, 106 Taipei, Taiwan;2. Department of Electronic Engineering, National United University, 36003 Miao‐Li, Taiwan Email: horngsj@yahoo.com.tw;3. Department of Computer Science and Information Engineering, National Taiwan University of Science and Technology, 106 Taipei, Taiwan;4. Department of Computer Science, Georgia State University, Atlanta, Georgia, USA;5. Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Japan;6. Department of Electronic Engineering, Technology and Science Institute of Northern Taiwan, Taipei, Taiwan;7. Department of Electro‐Optical Engineering, National United University, 36003 Miao‐Li, Taiwan |
| |
| Abstract: | Abstract: We present a hybrid model named HRKPG that combines the random‐key search method and an individual enhancement scheme to thoroughly exploit the global search ability of particle swarm optimization. With a genetic algorithm, we can expand the area of exploration of individuals in the solution space. With the individual enhancement scheme, we can enhance the particle swarm optimization and the genetic algorithm for the travelling salesman problem. The objective of the travelling salesman problem is to find the shortest route that starts from a city, visits every city once, and finally comes back to the start city. With the random‐key search method, we can search the ability of the particle and chromosome. On the basis of the proposed hybrid scheme of HRKPG, we can improve solution quality quite a lot. Our experimental results show that the HRKPG model outperforms the particle swarm optimization and genetic algorithm in solution quality. |
| |
| Keywords: | travelling salesman problem particle swarm optimization genetic algorithm random‐key search method individual enhancement scheme |
|
|
