A Convergence Proof for the Particle Swarm Optimiser

• Autorzy: Bergh F. van den , Engelbrecht A.P.
• Języki publikacji: EN

Abstrakty

EN

The Particle Swarm Optimiser (PSO) is a population based stochastic optimisation algorithm, empirically shown to be efficient and robust. This paper provides a proof to show that the original PSO does not have guaranteed convergence to a local optimum. A flaw in the original PSO is identified which causes stagnation of the swarm. Correction of this flaw results in a PSO algorithm with guaranteed convergence to a local minimum. Further extensions with provable global convergence are also described. Experimental results are provided to elucidate the behavior of the modified PSO as well as PSO variations with global convergence.

Słowa kluczowe

EN

Particle Swarm Optimisation (PSO); convergence proofs; stochastic optimisation; local convergence; global convergence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 4
• Strony: 341--374
• Opis fizyczny: Bibliogr. 30 poz., wykr.

Twórcy

autor

Bergh F. van den

autor

Engelbrecht A.P.

• Department of Computer Science University of Pretoria, Pretoria, South Africa,

Bibliografia

• [1] van den Bergh, F.: An Analysis of Particle Swarm Optimizers, Ph.D. Thesis, Department of Computer Science, University of Pretoria, Pretoria, South Africa, 2002.
• [2] van den Bergh, F., Engelbrecht, A.: A Cooperative approach to particle swarm optimization, Evolutionary Computation, IEEE Transactions on, 8(3), June 2004, 225-239.
• [3] van den Bergh, F., Engelbrecht, A. P.: A New Locally Convergent Particle Swarm Optimizer, Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Hammamet, Tunisia, 2002.
• [4] van den Bergh, F., Engelbrecht, A. P.: A Study of Particle Swarm Optimization Particle Trajectories, Information Sciences, 176(8), 2006, 937-971.
• [5] Clerc, M.: The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization, Proceedings of the IEEE Congress on Evolutionary Computation, 1999.
• [6] Clerc, M.: Think Locally, Act Locally: The Way of Life of Cheap-PSO, an Adaptive PSO, 2001.
• [7] Clerc, M., Kennedy, J.: The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space, IEEE Transactions on Evolutionary Computation, 6(1), 2002, 58-73.
• [8] Eberhart, R. C., Kennedy, J.: A New Optimizer using Particle Swarm Theory, Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan, 1995.
• [9] Eberhart, R. C., Shi, Y.: Comparing InertiaWeights and Constriction Factors in Particle Swarm Optimization, Proceedings of the IEEE Congress on Evolutionary Computation, San Diego, USA, 2000.
• [10] Eberhart, R. C., Shi, Y.: Particle Swarm Optimization: Developments, Applications and Resources, Proceedings of the IEEE Congress on Evolutionary Computation, IEEE Press, Seoul, Korea, 2001.
• [11] Eberhart, R. C., Simpson, P. K., Dobbins, R. W.: Computational Intelligence PC Tools, First edition, Academic Press Professional, 1996.
• [12] Kennedy, J.: Small Worlds and Mega-Minds: Effects of Neighborhood Topology on Particle Swarm Performance, Proceedings of the IEEE Congress on Evolutionary Computation, 1999.
• [13] Kennedy, J., Eberhart, R. C.: Particle Swarm Optimization, Proceedings of the IEEE International Joint Conference on Neural Networks, IEEE Press, 1995.
• [14] Kennedy, J., Mendes, R.: Population Structure and Particle Performance, Proceedings of the IEEE Congress on Evolutionary Computation, IEEE Press, Honolulu, Hawaii, 2002.
• [15] Mendes, R., Cortez, P., Rocha, M., Neves, J.: Particle Swarms for Feedforward Neural Network Training, Proceedings of the International Joint Conference on Neural Networks, 2002.
• [16] Ozcan, E.,Mohan, C. K.: Analysis of a Simple Particle Swarm Optimization System, Intelligent Engineering Systems through Artificial Neural Networks, 1998.
• [17] Ozcan, E., Mohan, C. K.: Particle Swarm Optimization: Surfing the Waves, Proceedings of the IEEE Congress on Evolutionary Computation,Washington D.C., USA, 1999.
• [18] Parsopoulos, K. E., Plagianakos, V. P., Magoulas, G. D., Vrahitis, M. N.: Stretching Technique for Obtaining Global Minimizers Through Particle Swarm Optimization, Proceedings of the Particle Swarm Optimization Workshop, 2001, Indianapolis, USA.
• [19] Poli, R.: The Sampling Distribution of Particle Swarm Optimisers and their Stability, Technical Report CSM-465, Department of Computer Science, University of Essex, March 2007.
• [20] Potter, M. A., de Jong, K. A.: A Cooperative Coevolutionary Approach to Function Optimization, The Third Parallel Problem Solving from Nature, Springer-Verlag, Jerusalem, Israel, 1994.
• [21] Shi, Y., Eberhart, R. C.: A Modified Particle Swarm Optimizer, Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway, USA, 1998.
• [22] Shi, Y., Eberhart, R. C.: Parameter Selection in Particle Swarm Optimization, Proceedings of the Seventh Annual Conference on Evolutionary Programming, New York, USA, 1998.
• [23] Shi, Y., Eberhart, R. C.: Fuzzy Adaptive Particle Swarm Optimization, Proceedings of the IEEE Congress on Evolutionary Computation, IEEE Press, Seoul, Korea, 2001.
• [24] Solis, F., Wets, R.: Minimization by Random Search Techniques, Mathematics of Operations Research, 6, 1981, 19-30.
• [25] Suganthan, P. N.: Particle Swarm Optimiser with NeighborhoodOperator, Proceedings of the IEEE Congress on Evolutionary Computation, IEEE Press, Piscataway, USA, 1999.
• [26] Trelea, I. C.: The Particle Swarm Optimization Algorithm: Convergence Analysis and Parameter Selection, Information Processing Letters, 85(6), 2003, 317-325.
• [27] Venter, G., Sobieszczanski-Sobieski, J.: Multidisciplinary Optimization of a Transport Aircraft Wing using Particle Swarm Optimization, Ninth AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Atlanta, USA, 2002.
• [28] Xie, X., Zhang, W., Yang, Z.: Adaptive Particle Swarm Optimization on Individual Level, Proceedings of the Sixth International Conference on Signal Processing, Beijing, China, 2002.
• [29] Yasuda, K., Ide, A., Iwasaki, N.: Adaptive Particle Swarm Optimization, Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, 2003.
• [30] Yoshida, H., Fukuyama, Y., Takayama, S., Nakanishi, Y.: A Particle Swarm Optimization for Reactive Power and Voltage Control in Electric Power Systems Considering Voltage Security Assessment, Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, 1999.