|
|
|
| Modified Discrete Particle Swarm Optimization Algorithm Based on Inver-Over Operator |
| ZHENG Dong-Liang,XUE Yun-Can,YANG Qi-Wen,LI Fei |
| College of Computer and Information,Hohai University,Changzhou 213022 |
|
|
|
|
Abstract Though the discrete particle swarm optimization (DPSO) can make the best of the local and global optima of particles, it converges slowly with low precision. The Guo Tao algorithm converges with fast high precision, but it is blindfold to learn from the other particles. A modified discrete particle swarm optimization algorithm is presented based on the inver-over operator (IDPSO). To prevent premature convergence, the local sub-optimum particle swarm is introduced into IDPSO. Particles learn from the particles in the local sub-optimum particle swarm instead of their local optima. Three new parameters are introduced into IDPSO. Learning selection probability is introduced to select the particle to be learned. A generation threshold is introduced to define when to learn from the global particle. Local sub-optimum particle swarm ratio is introduced to define the size of the sub-optimum particle swarm. Selecting principles of these parameters is detailed discussed and the general reference scopes are given. Experiments are carried out on the traveling salesman problem and the results show that the modified IDPSO achieves good results compared with the Guo Tao algorithm and the general DPSO. The proposed algorithm improves both the convergence speed and solution precision.
|
|
Received: 15 April 2009
|
|
|
|
|
|
[1] Kennedy J, Eberhart R C. Particle Swarm Optimization // Proc of the IEEE International Conference on Neural Networks. Perth, Australia, 1995: 1942-1948
[2] Eberhart R C, Kennedy J. A New Optimizer Using Particle Swarm Theory // Proc of the 6th International Symposium on Micro Machine and Human Science. Nagoya, Japan, 1995: 39-43
[3] Poli R. An Analysis of Publications on Particle Swarm Optimization Applications. Technical Report, CSM-469, Essex, UK: University of Essex. Department of Computer Science, 2007
[4] Kennedy J, Eberhart R. A Discrete Binary Version of the Particle Swarm Algorithm // Proc of the World Multi-Conference on Systemics, Cybernetics and Informatics. Piscataway, USA, 1997: 4104-4109
[5] Jarboui B, Damak N, Siarry P, et al. A Combinatorial Particle Swarm
Optimization for Solving Multi-Mode Resource-Constrained Project Scheduling Problems. Applied Mathematics and Computation, 2008, 195(1): 299-308
[6] Lian Zhigang, Gu Xingsheng, Jiao Bin. A Novel Particle Swarm Optimization Algorithm for Permutation Flow-Shop Scheduling to Minimize Makespan. Chaos, Solitons Fractals, 2008, 35(5): 851-861
[7] Tseng C T, Liao C J. A Discrete Particle Swarm Optimization for Lot-Streaming Flowshop Scheduling Problem. European Journal of Operational Research, 2008, 191(2): 360-373
[8] Tan Hao, Wang Jinyan, He Yizheng, et al. Sub Swarm and Crossbreed Strategy PSO for TSP. Systems Engineering, 2005, 23(4): 83-87 (in Chinese)
(谭 皓,王金岩,何亦征,等.一种基于子群杂交机制的粒子群算法求解旅行商问题.系统工程, 2005, 23(4): 83-87)
[9] Gao Shang, Han Bin, Wu Xiaojun, et al. Solving Traveling Salesman Problem by Hybrid Particle Swarm Optimization Algorithm. Control and Decision, 2004, 19(11): 1286-1289 (in Chinese)
(高 尚,韩 斌,吴小俊,等.求解旅行商问题的混合粒子群优化算法.控制与决策, 2004, 19(11): 1286-1289)
[10] Guo Wenzhong, Chen Guolong. Fuzzy Self-Adapted Particle Swarm Optimization Algorithm for Traveling Salesman Problems. Computer Science, 2006, 33(6): 161-162 (in Chinese)
(郭文忠,陈国龙.求解TSP问题的模糊自适应粒子群算法.计算机科学, 2006, 33(6): 161-162)
[11] Zhong Yiwen, Yang Jiangang, Ning Zhengyuan. Discrete Particle Swarm Optimization Algorithm for TSP Problem. Systems Engineering-Theory Practice, 2006, 26(6): 88-94 (in Chinese)
(钟一文,杨建刚,宁正元.求解TSP问题的离散粒子群优化算法.系统工程理论与实践, 2006, 26(6): 88-94)
[12] Wang Wenfeng, Liu Guangyuan, Wen Wanhui. Study of a Self-Escape Hybrid Discrete Particle Swarm Optimization for TSP. Computer Science, 2007, 34(8): 143-145 (in Chinese)
(王文峰,刘光远,温万惠.求解TSP问题的自逃逸混合离散粒子群算法研究.计算机科学, 2007, 34(8): 143-145)
[13] Tao Guo, Michalewicz Z. Inver-Over Operator for the TSP // Proc of the 5th International Conference on Parallel Problem Solving from Nature. Amsterdam, Netherlands, 1998: 803-812 |
|
|
|
2010, Vol. 23 
