Global Optimization by Particle Swarm Method:A Fortran Program

Mishra, SK (2006): Global Optimization by Particle Swarm Method:A Fortran Program.

Abstract

Programs that work very well in optimizing convex functions very often perform poorly when the problem has multiple local minima or maxima. They are often caught or trapped in the local minima/maxima. Several methods have been developed to escape from being caught in such local optima. The Particle Swarm Method of global optimization is one of such methods.

A swarm of birds or insects or a school of fish searches for food, protection, etc. in a very typical manner. If one of the members of the swarm sees a desirable path to go, the rest of the swarm will follow quickly. Every member of the swarm searches for the best in its locality - learns from its own experience. Additionally, each member learns from the others, typically from the best performer among them. Even human beings show a tendency to learn from their own experience, their immediate neighbours and the ideal performers. The Particle Swarm method of optimization mimics this behaviour. Every individual of the swarm is considered as a particle in a multidimensional space that has a position and a velocity. These particles fly through hyperspace and remember the best position that they have seen. Members of a swarm communicate good positions to each other and adjust their own position and velocity based on these good positions.

The Particle Swarm method of optimization testifies the success of bounded rationality and decentralized decisionmaking in reaching at the global optima. It has been used successfully to optimize extremely difficult multimodal functions. Here we give a FORTRAN program to find the global optimum by the Repulsive Particle Swarm method. The program has been tested on over 90 benchmark functions of varied dimensions, complexities and difficulty levels.

• Item Type: MPRA Paper
• Institution: North-Eastern Hill University, Shillong (India)
• Language: English
• Keywords: Bounded rationality; Decentralized decision making; Jacobian; Elliptic functions; Gielis super-formula; supershapes; Repulsive Particle Swarm method of Global optimization; nonlinear programming; multiple sub-optimum; global; local optima; fit; data; empirical; estimation; parameters; curve fitting
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C60 - General; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling

References

· Abramowitz, M. and Stegun, I.A.: Handbook of Mathematical Functions, Dover Publications, New York, 1964.

· Bauer, J.M.: “Harnessing the Swarm: Communication Policy in an Era of Ubiquitous Networks and Disruptive Technologies”, Communications and Strategies, 45, 2002.

· Bhabhrawala, T. and Krovi, V.: “Shape Recovery from Medical Image Data using Extended Superquadrics”, ASME 2005 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Long Beach, California USA, September 24-28, 2005.

· Box, M.J.: “A new method of constrained optimization and a comparison with other methods”. Comp. J. 8, pp. 42-52, 1965.

· Bukin, A. D.: New Minimization Strategy For Non-Smooth Functions, Budker Institute of Nuclear Physics preprint BUDKER-INP-1997-79, Novosibirsk 1997.

· Cerny, V.: "Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm", J. Opt. Theory Appl., 45, 1, 41-51, 1985.

· Chacón, R.: “A Mathematical Description of Natural Shapes in our Nonlinear World”, Working paper, arXive:nlin. AO/0405057 v1 25 May, 2004.

· Eberhart R.C. and Kennedy J.: “A New Optimizer using Particle Swarm Theory”, Proceedings Sixth Symposium on Micro Machine and Human Science, pp. 39–43. IEEE Service Center, Piscataway, NJ, 1995.

· Fleischer, M.: “Foundations of Swarm Intelligence: From Principles to Practice”, Swarming Network Enabled C4ISR, arXiv:nlin.AO/0502003 v1 2 Feb 2005.

· G.E.P. Box, “Evolutionary operation: A method for increasing industrial productivity”, Applied Statistics, 6 , pp. 81-101, 1957.

· Gielis, J.: “A Generic Geometric Transformation that unifies a Wide Range of Natural and Abstract Shapes”, American Journal of Botany, 90(3): pp. 333–338, 2003.

· Glover F.," Future paths for Integer Programming and Links to Artificial Intelligence", Computers and Operations Research, 5:533-549, 1986.

· Holland, J.: Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, 1975.

· Jung, B.S. and Karney, B.W.: “Benchmark Tests of Evolutionary Computational Algorithms”, Environmental Informatics Archives (International Society for Environmental Information Sciences), 2, pp. 731-742, 2004.

· Karush, W. Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois, 1939.

· Kirkpatrick, S., Gelatt, C.D. Jr., and Vecchi, M.P.: "Optimization by Simulated Annealing", Science, 220, 4598, 671-680, 1983.

· Kuester, J.L. and Mize, J.H.: Optimization Techniques with Fortran, McGraw-Hill Book Co. New York, 1973.

· Kuhn, H.W. and Tucker, A.W.: “Nonlinear Programming”, in Neymann, J. (ed) Proceedings of Second Berkeley Symposium on Mathematical Statistics and Probability, Univ. of California Press, Berkrley, Calif. pp. 481-492, 1951.

· Liang, J.J. and Suganthan, P.N. “Dynamic Multi-Swarm Particle Swarm Optimizer”, International Swarm Intelligence Symposium, IEEE # 0-7803-8916-6/05/$20.00. pp. 124-129, 2005.

· Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E.: "Equation of State Calculations by Fast Computing Machines", J. Chem. Phys.,21, 6, 1087-1092, 1953.

· Mishra, S.K.: “Some Experiments on Fitting of Gielis Curves by Simulated Annealing and Particle Swarm Methods of Global Optimization”, Social Science Research Network (SSRN): http://ssrn.com/abstract=913667, Working Papers Series, 2006 (a).

· Mishra, S.K.: “Least Squares Fitting of Chacón-Gielis Curves by the Particle Swarm Method of Optimization”, Social Science Research Network (SSRN), Working Papers Series, http://ssrn.com/abstract=917762 , 2006 (b).

· Mishra, S.K.: “Performance of Repulsive Particle Swarm Method in Global Optimization of Some Important Test Functions: A Fortran Program” , Social Science Research Network (SSRN), Working Papers Series, http://ssrn.com/abstract=924339 , 2006 (c).

· Mishra, S.K.: “Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method”, Social Science Research Network (SSRN) Working Papers Series, http://ssrn.com/abstract=927134, 2006 (d).

· Mishra, S.K.: “Repulsive Particle Swarm Method on Some Difficult Test Problems of Global Optimization” ,SSRN: http://ssrn.com/abstract=928538 , 2006 (e).

· Mishra, S.K.: “Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions”. SSRN: http://ssrn.com/abstract=933827 , 2006 (f).

· Mundim, K.C.: “Generalized Simulated Annealing”, (provides GSA Fortran Program to download) available at www.unb.br/iq/kleber/GSA/artigo2/node2.html , 1996.

· Mundim, K.C. and Tsallis, C.: “Geometry Optimization and Conformational Analysis through Generalized Simulated Annealing”,Int. Journal of Quantum Chemistry, 58, pp. 373-381, 1996.

· Nelder, J.A. and Mead, R.: “A Simplex method for function minimization” Computer Journal, 7: pp. 308-313, 1964.

· Parsopoulos, K.E. and Vrahatis, M.N., “Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization”, Natural Computing, 1 (2-3), pp. 235- 306, 2002.

· Prigogine, I. and Strengers, I.: Order Out of Chaos: Man’s New Dialogue with Nature, Bantam Books, Inc. NY, 1984.

· Silagadge, Z.K.: “Finding Two-Dimensional Peaks”, Working Paper, Budkar Insttute of Nuclear Physics, Novosibirsk, Russia, arXive:physics/0402085 V3 11 Mar 2004.

· Simon, H.A.: Models of Bounded Rationality, Cambridge Univ. Press, Cambridge, MA, 1982.

· Smith, A.: The Theory of the Moral Sentiments, The Adam Smith Institute (2001 e-version), 1759.

· Storn, R. and Price, K: "Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces" : Technical Report, International Computer Science Institute, Berkley, 1995.

· Törn, A.A and Viitanen, S.: “Topographical Global Optimization using Presampled Points”, J. of Global Optimization, 5, pp. 267-276, 1994.

· Törn, A.A.: “A search Clustering Approach to Global Optimization” , in Dixon, LCW and Szegö, G.P. (Eds) Towards Global Optimization – 2, North Holland, Amsterdam, 1978.

· Tsallis, C. and Stariolo, D.A.: “Generalized Simulated Annealing”, ArXive condmat/9501047 v1 12 Jan, 1995.

· Veblen, T.B.: "Why is Economics Not an Evolutionary Science" The Quarterly Journal of Economics, 12, 1898.

· Veblen, T.B.: The Theory of the Leisure Class, The New American library, NY. (Reprint, 1953), 1899.

· Vesterstrøm, J. and Thomsen, R.: “A comparative Study of Differential Evolution, Particle Swarm Optimization, and Evolutionary Algorithms on Numerical Benchmark Problems”, Congress on Evolutionary Computation, 2004. CEC2004, 2, pp. 1980-1987, 2004.

· Whitley, D., Mathias, K., Rana, S. and Dzubera, J.: “Evaluating Evolutionary Algorithms”, Artificial Intelligence, 85, pp. 245-276, 1996.

· Whittaker, E.T. and Watson, G.N.: A Course of Modern Analysis, Cambridge Univ. Press, 1996.

· Yao, X. and Liu, Y.: “Fast Evolutionary Programming”, in Fogel, LJ, Angeline, PJ and Bäck, T (eds) Proc. 5th Annual Conf. on Evolutionary programming, pp. 451-460, MIT Press, Mass, 1996.