A discrete particle swarm optimization algorithm with fully communicated information

ABSTRACT

In this paper, a novel discrete particle swarm optimization (DPSO) algorithm is presented for solving the combinational optimization problems such as knapsack and clustering. The proposed algorithm mainly employs the idea of the information stored and exchanged among particles through Information-Shared Matrix (ISM). There are two reasons for using the idea. To begin with, the mechanism, storing and exchanging information, makes it possible to construct a discrete algorithm to solve combinational problems. Furthermore, the positions of particles in the space are adjusted according to not only historical information and global information current particles left, but also the information the other particles left. Therefore, information can be more sufficiently shared by each particle. The performance of DPSO algorithm is evaluated in comparison with well-known ACO algorithm, TS algorithm and other discrete PSO algorithms. Our computational simulations reveal very encouraging results in terms of the quality of solution found.

REFERENCES

• 1: Kennedy J, Eberthart R. Particle Swarm Optimization. IEEE International Conference on Neural Networks, Perth, Australia, pp. 1942--1948, 1995
• 2: AL-SULTAN K S. A Tabu Search Approach to the Clustering Problem. Pattern Recognition, vol. 28, pp. 1443--1451, 1995
• 3: Elbeltagi E, Hegazy T, Grierson D. Comparison among five evolutionary-based optimization algorithms. Advanced Engineering Informatics, vol. 19, pp. 43--53, 2005
• 4: Kennedy J, Eberhart R C. A Discrete Binary Version of Particle Swarm Algorithm. Proceedings of the 1997 Conference on System, Man, and Cybernetics. Piscataway: IEEE Press, pp. 4104--4108, 1997
• 5: Shen Q, Jiang J H, Jiao C X, et al. Modified Particle Swarm Optimization Algorithm for Variable Selection in MLR and PLS Modeling: QSAR Studies of Antagonism of Angiotensin II Antagonists. European Journal of Pharmaceutical Sciences, vol. 22, pp. 145--152, 2004
• 6: Wang Y, Feng X Y, Huang Y X, et al. A Novel Quantum Swarm Evolutionary Algorithm for Solving 0-1 Knapsack Problem. International Conference on Natural Computation, Lecture Notes in Computer Sciences. Berlin Heideberg Spring-Verlag, vol. 3611, pp. 698--704, 2005
• 7: Huang L, Wang K P. Particle Swarm Optimization for Traveling Salesman Problems. Journal of JILIN Univeristy, vol. 41, pp. 477--480, 2003
• 8: Gao S, Han B, Wu X J, et al. Solving Traveling Salesman Problem by Hybrid Particle Swarm Optimization Algorithm. Control and Decision, vol. 19, pp. 1286--1289, 2004
• 9: Shelokar P S, Jayaraman V K, Kulkarni B D. An ant colony approach for clustering. Analutica Chimica Acta, vol. 509, pp. 187--195, 2004
• 10: Ng M K, Wong J C. Clustering categorical data sets using tabu search techniques. Pattern Recognition, vol. 35, pp. 2783--2790, 2002
• 11: Diansheng Guo , Donna J. Peuquet , Mark Gahegan, ICEAGE: Interactive Clustering and Exploration of Large and High-Dimensional Geodata, Geoinformatica, v.7 n.3, p.229-253, September 2003 [doi>10.1023/A:1025101015202]
• 12: H. Ressom , D. Wang , P. Natarajan, Adaptive double self-organizing maps for clustering gene expression profiles, Neural Networks, v.16 n.5-6, p.633-640, June 2003 [doi>10.1016/S0893-6080(03)00102-3]
• 13: Lee S C, Suh Y H, Kim J K, et al. A cross-national market segmentation of online game industry using SOM. Expert Systems with Applications, vol. 27, pp. 559--570, 2004
• 14: Cique L, Foresti G, Lombardi L. A clustering fuzzy approach for image segmentation. Pattern Recognition, vol. 37, pp. 1797--1807, 2004
• 15: Kim K J, Cho S B. Fuzzy integration of structure adaptive SOMs for web content mining. Fuzzy Sets and Systems, vol. 148, pp. 43--60, 2004
• 16: Garcia H L, Gonzalez I M. Self-organizing map and clustering for wastewater treatment monitoring. Engineering Applications of Artificial Intelligence, vol. 17, pp. 215--225, 2004
• 17: Shelokar P S, Jayaraman V K, Kulkarni B D. An ant colony approach for clustering. Analutica Chimica Acta, vol. 509, pp. 187--195, 2004
• 18: Sanghamitra Bandyopadhyay , Ujjwal Maulik, An evolutionary technique based on K-means algorithm for optimal clustering in R^N, Information Sciences—Applications: An International Journal, v.146 n.1-4, p.221-237, October 2002 [doi>10.1016/S0020-0255(02)00208-6]
• 19: Ng M K, Wong J C. Clustering categorical data sets using tabu search techniques. Pattern Recognition, vol. 35, pp. 2783--2790, 2002
• 20: Paterlini S, Krink T. Differential evolution and particle swarm optimization in partitional clustering. Computational Statistics and Data Analysis, vol. 50, pp.1220--1247, 2006

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

General Terms:
Algorithms

Keywords:
clustering, discrete particle swarm optimization, information shared matrix