Recent approaches to global optimization problems through Particle Swarm Optimization
Tóm tắt
This paper presents an overview of our most recent results concerning the Particle Swarm Optimization (PSO) method. Techniques for the alleviation of local minima, and for detecting multiple minimizers are described. Moreover, results on the ability of the PSO in tackling Multiobjective, Minimax, Integer Programming and ℓ1 errors-in-variables problems, as well as problems in noisy and continuously changing environments, are reported. Finally, a Composite PSO, in which the heuristic parameters of PSO are controlled by a Differential Evolution algorithm during the optimization, is described, and results for many well-known and widely used test functions are given.
Tài liệu tham khảo
Ahonen H, Desouza PA and Garg VK (1997) A Genetic Algorithm for Fitting Lorentzian Line-Shapes in Mossbauer-Spectra 124(4): 633–638
Angeline PJ (1997) Tracking Extrema in Dynamic Environments. Proceedings of International Conference on Evolutionary Programming
Angeline PJ (1998) Evolutionary optimization versus Particle Swarm Optimization: Philosophy and performance differences. In: Porto VW, Saravanan N,Waagen D and Eiben AE (eds) Evolutionary Programming VII, pp. 601–610. Springer
Arnold DV (2001) Local Performance of Evolution Strategies in the Presence of Noise. Ph.D. thesis, Department of Computer Science, University of Dortmund, Germany
Bäck T (1996) Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York
Bäck T, Fogel D and Michalewicz Z (1997) Handbook of Evolutionary Computation. IOP Publishing and Oxford University Press, New York
Bandler JW and Charalambous C (1974) Nonlinear programming using minimax techniques. J. Optim. Th. Appl. 13: 607–619
Banzhaf W, Nordin P, Keller RE and Francone FD (1998) Genetic Programming-An Introduction. Morgan Kaufman, San Francisco
Bertsekas DP (1976) Minimax Methods Based on Approximations. Proceedings 1976 John Hopkins Conf. Inform. Sciences and Systems
Bertsekas DP (1976) A new algorithm for solution of nonlinear resistive networks involving diodes. IEEE Trans. Circ. Th. 23: 599–608
Bertsekas DP (1977) Approximation procedures based on the method of multipliers. J. Optim. Th. Appl. 23: 487–510
Beyer H-G (2000) Evolutionary algorithms in noisy environments: Theoretical issues and guidelines for practice. Comput. Methods Appl. Mech. Engrg. 186: 239–269
Beyer H-G (2001) The Theory of Evolution Strategies. Springer, Berlin
Beyer H-G and Schwefel H-P (2002) Evolution Strategies: A Comprehensive Introduction. Natural Computing, to appear
Blum EK (1989) Approximation of boolean functions by sigmoidal networks, Part I: XOR and other two-variable functions. Neural Computation 1: 532–540
Bohren CF and Huffman DR (1983) Absorption and Scattering of Light by Small Particles. Wiley, New York
Boutsinas B and Vrahatis MN (2001) Artificial nonmonotonic neural networks. Artificial Intelligence 132: 1–38
Box GEP and Muller ME (1958) A note on the generation of random normal deviates. Ann. Math. Statistics 29: 610–611
Britt HI and Luecke RH (1973) The estimation of parameters in nonlinear, implicit models. Technometrics 15: 233–247
Burke J and Xu S (2000) An non-interior predictor-corrector path-following algorithm for the monotone linear complementarity problem. Math. Progr. 87: 113–130
Bush TS, Catlow CRA and Battle PD (1995) Evolutionary programming techniques for predicting inorganic crystal-structures. J. Materials Chemistry 5(8): 1269–1272
Carlisle A and Dozier G (2001) An Off-The-Shelf PSO. Proceedings of the Particle Swarm Optimization Workshop, pp. 1–6
Charalambous C and Conn AR (1978) An efficient method to solve the minimax problem directly. SIAM J. Numerical Analysis 15: 162–187
Corana A, Marchesi M, Martini C and Ridella S (1987) Minimizing multimodal functions of continuous variables with the 'simulated annealing algorithm'. ACM Transactions on Mathematical Software 13(3): 262–280
Demyanov VF and Molozemov VN (1974) Introduction to Minimax. Wiley, New York
Drossos L, Ragos O, Vrahatis MN and Bountis TC (1974) Method for computing long periodic orbits of dynamical systems. Physical Review E 53: 1206–1211
Du DZ and Pardalos PM (1995) Minimax and Applications. Kluwer, Dordrecht
Eberhart RC and Kennedy J (1995) A New Optimizer Using Particle Swarm Theory, Proceedings Sixth Symposium on Micro Machine and Human Science, pp. 39–43. IEEE Service Center, Piscataway, NJ
Eberhart RC and Shi Y (1998) Comparison between genetic algorithms and Particle Swarm Optimization. In: Porto VW, Saravanan N, Waagen D and Eiben AE (eds) Evolutionary Programming VII, pp. 611–616. Springer
Eberhart RC and Shi Y (2000) Comparing inertia weights and constriction factors in Particle Swarm Optimization. Proceedings of the Congress on Evolutionary Computating, pp. 84–88
Eberhart RC, Simpson P and Dobbins R (1996) Computational Intelligence PC Tools. Academic Press
Elster C and Neumaier A (1995) A grid algorithm for bound constrained optimization of noisy functions. IMA Journal of Numerical Analysis 15: 585–608
Elster C and Neumaier A (1997) A method of trust region type for minimizing noisy functions. Computing 58: 31–46
Facchinei F, Jiang H and Qi L (1999) A smoothing method for mathematical programs with equilibrium constraints. Math. Progr. 85: 107–134
Fletcher R (1987) Practical Methods of Optimization. Wiley, New York
Fogel D (1996) Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, NJ
Forgó F (1988) Nonconvex Programming. Akadémiai Kiadó, Budapest
Gall DA (1966) A practical multifactor optimization criterion. In: Levi A and Vogl TP (eds) Recent Advances in Optimization Techniques, pp. 369–386
Gilmore T and Keeley CT (1995) An implicit filtering algorithm for optimization of functions with many local minima. SIAM J. Optim. 5: 269–285
Glankwahmdee A, Liebman JS and Hogg GL (1979) Unconstrained discrete nonlinear programming. Engineering Optimization 4: 95–107
Goldberg D (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, Reading, MA
Hansen ER (1992) Global Optimization Using Interval Analysis. Marcel Dekker, New York
Hansen N (1998) Verallgemeinerte individuelle Schrittweitenregelung in der Evolutionsstrategie. Mensch & Buch, Berlin
Hansen N and Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 9: 159–195
Heppner F and Grenander U (1990) A stochastic nonlinear model for coordinate bird flocks. In: Krasner S (ed) The Ubiquity of Chaos. AAAS Publications, Washington, DC
Hirriart JB (1978) On optimality conditions in non-differentiable programming. Mathematical Programming 14: 73–86
Hodgson RJW (2000) Genetic algorithm approach to particle identification by light scattering. J. Colloid and Interface Science 229: 399–406
Hooke R and Jeeves TA (1961) Direct search solution of numerical and statistical problems. J. ACM 8: 212–229
Horst R and Pardalos PM (1995) Handbook of Global Optimization. Kluwer Academic Publishers, London
Horst R and Tuy H (1996) Global Optimization-Deterministic Approaches. Springer, New York
Jaynes E (1979) Where do we stand on maximum entropy? In: Levine R and Tribus M (eds) The Maximum Entropy Formalism, pp. 15–118. MIT Press, Cambridge
Jin Y, Olhofer M and Sendhoff B (2001) Dynamic Weighted Aggregation for Evolutionary Multi-Objective Optimization: Why Does ItWork and How? Proceedings GECCO 20001 Conference, to appear
Kalantonis VS, Perdios EA, Perdiou AE and Vrahatis MN (2001) Computing with certainty individual members of families of periodic orbits of a given period. Celestial Mechanics and Dynamical Astronomy 80: 81–96
Kelahan RC and Gaddy JL (1978) Application of the adaptive random search to discrete and mixed integer optimization. Int. J. Num. Meth. Engin. 12: 289–298
Kelley R (1999) Iterative Methods for Optimization. SIAM, Philadelphia
Kennedy J 1998, The behavior of particles. In: Porto VW, Saravanan N, Waagen D and Eiben AE (eds) Evolutionary Programming VII, pp. 581–590. Springer
Kennedy J and Eberhart RC (1995) Particle Swarm Optimization. Proceedings IEEE International Conference on Neural Networks, IV: pp. 1942–1948. IEEE Service Center, Piscataway, NJ
Kennedy J and Eberhart RC (2001) Swarm Intelligence. Morgan Kaufmann Publishers
Knowles JD and Corne DW (2000) Approximating the nondominated front using the pareto archived evolution strategies. Evolutionary Computation 8(2): 149–172
Kort BW and Bertsekas DP (1972) A new penalty function algorithm for constrained minimization. Proceedings 1972 IEEE Conf. Decision and Control
Koza JR (1992) Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA
Laskari EC, Parsopoulos KE and Vrahatis MN (2001) Determination of the heuristic parameters of the Particle Swarm Optimization method. Proceedings Numerical Algorithms Conference submitted
Laskari EC, Parsopoulos KE and Vrahatis MN (2002a) Particle Swarm Optimization for Minimax Problems. IEEE Congress on Evolutionary Computation, pp. 1576–1581
Laskari EC, Parsopoulos KE and Vrahatis MN (2002b) Particle Swarm Optimization for Integer Programming. IEEE Congress on Evolutionary Computation, pp. 1582–1587
Levy A, Montalvo A, Gomez S and Galderon A (1981) Topics in Global Optimization. Springer-Verlag, New York
Li XS (1991) An aggregate function method for nonlinear programming. Science in China (A) 34: 1467–1473
Lukšan L and Vlček J (2000) Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical Report No. 798, Institut of Computer Science, Academy of Sciences of the Czech Republic
Michalewicz Z (1994) Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin
Millonas MM (1994) Swarms, phase transitions, and collective intelligence. In: Palaniswami M, Attikiouzel Y, Marks R, Fogel D and Fukuda T (eds) Computational Intelligence: A Dynamic System Perspective, pp. 137–151. IEEE Press, Piscataway, NJ
More JJ, Garbow BS and Hillstrom KE (1981) Testing unconstrained optimization software. ACM Transactions on Mathematical Software 7(1): 17–41
Murray W and Overton ML (1980) A projected lagrangian algorithm for nonlinear minimax optimization. SIAM J. Scient. Stat. Comp. 1: 345–370
Nelder JA and Mead R (1965) A simplex method for function minimization. Computer Journal 7: 308–313
Nemhauser GL, Rinooy Kan AHG and Todd MJ (eds) (1989) Handbooks in OR & MS, Vol. 1: Optimization. Elsevier
Nocedal J (1991) Theory of algorithms for unconstrained optimization. In: Iserles A (ed) Acta Numerica, pp. 199–242. Cambridge University Press, Cambridge
Osborne MR and Watson GA (1969) An algorithm for minimax approximation in the nonlinear case. Comput. J. 12: 63–68
Parsopoulos KE, Plagianakos VP, Magoulas GD and Vrahatis MN (2001a) Improving the Particle Swarm Optimizer by Function “Stretching”. In: Hadjisavvas N and Pardalos PM (eds) Advances in Convex Analysis and Global Optimization, pp. 445–457. Kluwer Academic Publishers
Parsopoulos KE, Plagianakos VP, Magoulas GD and Vrahatis MN (2001b) Objective Function “Stretching” to alleviate convergence to local minima. Nonlinear Analysis, TMA 47(5): 3419–3424
Parsopoulos KE, Plagianakos VP, Magoulas GD and Vrahatis MN (2001c) Stretching technique for obtaining global minimizers through Particle Swarm Optimization. Proceedings of the Particle Swarm Optimization workshop, pp. 22–29
Parsopoulos KE, Laskari EC and Vrahatis MN (2001d) Solving ℓ1 norm errors-in-variables problems using Particle Swarm Optimization. In: Hamza MH (ed) Artificial Intelligence and Applications, pp. 185–190. IASTED/ACTA Press
Parsopoulos KE and Vrahatis MN (2001a) Modification of the Particle Swarm Optimizer for locating all the global minima. In: Kurkova V, Steele NC, Neruda R and Karny M (eds) Artificial Neural Networks and Genetic Algorithms, pp. 324–327. Springer, Wien
Parsopoulos KE and Vrahatis MN (2001b) Particle Swarm Optimizer in noisy and continuously changing environments. In: Hamza MH (ed) Artificial Intelligence and Soft Computing, pp. 289–294. IASTED/ACTA Press
Parsopoulos KE and Vrahatis MN (2001c) Particle Swarm Optimization for imprecise problems. Proceedings of the 5th International Workshop on Mathematical Methods In Scattering Theory and Biomedical Technology, in press
Parsopoulos KE and Vrahatis MN (2002) Particle Swarm Optimization method in multiobjective problems. Proceedings ACM Symposium on Applied Computing (SAC 2002), pp. 603–607
Paszkowicz W (1996) Application of the smooth genetic algorithm for indexing powder patterns: Test for the orthorhombic system. Materials Science Forum 228(1 & 2): 19–24
Plagianakos VP and Vrahatis MN (1999) Training neural networks with 3–bit integer weights. In: Bahnzaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M and Smith RE (eds) Proceedings of Genetic and Evolutionary Computation Conference (GECCO 1999), pp. 910–915. Morgan Kaufmann
Plagianakos VP and Vrahatis MN (2000) Training neural networks with threshold activation functions and constrained integer weights. Proceedings of the IEEE International Joint Conference on Neural Networks (IJCNN 2000)
Peng J-M and Lin Z (1999) A non-interior continuation method for generalized linear complementarity problems. Math. Progr. 86: 533–563
Pierre DA (1986) Optimization Theory and Applications. Dover Publications
Pintér JD (1996) Global Optimization in Action. Academic Publishers
Polak E (1987) On the mathematical foundations of nondifferentiable optimization. SIAM Review 29: 21–89
Polak E (1997) Optimization: Algorithms and Consistent Approximations. Springer-Verlag, New York
Powell MJD (1988) A review of algorithms for nonlinear equations and unconstrained optimization. Proceedings ICIAM, pp. 220–232
Powell MJD (1992) A direct search optimization method that models the objective and constraint functions by linear interpolation. DAMTP 1992/NA5, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England
Rao SS (1996) Engineering optimization-theory and practice. Wiley
Rechenberg I (1994) Evolution Strategy. In: Zurada JM, Marks RJ II and Robinson C (eds) Computational Intelligence: Imitating Life. IEEE Press, Piscataway, NJ
ReevesWT (1983) Particle systems-a technique for modelling a class of fuzzy objects. ACM Transactions on Graphics 2(2): 91–108
Reynolds CW (1987) Flocks, herds, and schools: a distributed behavioral model. Computer Graphics 21(4): 25–34
Rudolph G (1994) An evolutionary algorithm for integer programming. In: Davidor Y, Schwefel H-P, Männer R (eds), pp. 139–148. Parallel Problem Solving from Nature 3 Rudolph G (1997) Convergence properties of evolutionary algorithms. Verlag Dr. Kovač, Hamburg Salomon R (1998) Evolutionary search and gradient search: Similarities and differences. IEEE Trans. Evolutionary Computation 2: 45–55
Schaffer JD (1985) Genetic Algorithms and their Applications: Proceedings of the first Int. Conf. on Genetic Algorithms, pp. 93–100
Schwefel H-P (1975) Evolutionsstrategie und numerische Optimierung. Technical University of Berlin, Department of Process Engineering, Dr.-Ing. Thesis
Schwefel H-P (1981) Numerical Optimization of Computer Models. Wiley, Chichester
Schwefel H-P (1995) Evolution and Optimum Seeking. Wiley, New York
Schwefel H-P and Rudolph G (1995) Contemporary evolution strategies. In: Morana F, Moreno A, Merelo J and Chacon P (eds), pp. 893–907. Advances in Artificial Life, Proceedings 3rd ECAL
Shi Y and Eberhart RC (1998) Parameter selection in Particle Swarm Optimization. In: Porto VW, Saravanan N, Waagen D and Eiben AE (eds) Evolutionary Programming VII, pp. 611–616. Springer
Shi Y and Eberhart RC (1998) A modified Particle Swarm Optimizer. Proceedings of the 1998 IEEE Conference on Evolutionary Computation. AK, Anchorage
Skinner AJ and Broughton JQ (1995) Neural networks in computational materials science: Training algorithms. Modelling and Simulation in Material Science and Engineering 3(3): 371–390
Snyman JA and Fatti LP (1987) A multi-start global minimization algorithm with dynamic search trajectories. J. of Optimization Theory and Applications 54(1): 121–141
Spall JC (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation'. IEEE Trans. Automatic Control 37: 332–341
Spall JC (1998a) Implementation of the simultaneous perturbation algorithm for stochastic optimization. IEEE Trans. Aerospace and Electronic Systems 34: 817–823
Spall JC (1998b) An overview of the simultaneous perturbation method for efficient optimization. Johns Hopkins APL Technical Digest 19: 482–492
Storn R and Price K (1997) Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optimization 11: 341–359
Swinehart K, Yasin M and Guimaraes E (1996) Applying an analytical approach to shop-floor scheduling: A case-study. Int. J. of Materials & Product Technology 11(1–2): 98–107
Torczon V (1989) A direct search algorithm for parallel machines. Ph.D. thesis, Department of Mathematical Sciences, Rice University, Houston, USA
Torczon V (1991) On the convergence of the multidimensional search algorithm. SIAM J. Optimization 1: 123–145
Törn A and Žilinskas A (1989) Global Optimization. Springer-Verlag, Berlin
Vrahatis MN, Androulakis GS, Lambrinos JN and Magoulas GD (2000) A class of gradient unconstrained minimization algorithms with adaptive stepsize. Journal of Computational and Applied Mathematics 114: 367–386
Vrahatis MN, Androulakis GS and Manoussakis ME (1996) A new unconstrained optimization method for imprecise function and gradient values. Journal of Mathematical Analysis and Applications 197: 586–607
Vrahatis MN, Perdiou AE, Kalantonis VS, Perdios AE, Papadakis K, Prosmiti R and Farantos SC (2001) Application of the characteristic bisection method for locating and computing periodic orbits in molecular systems. Computer Physics Communications 138: 53–68
Waren AD, Lasdon LS and Suchman DF (1967) Optimization in engineering design. Proceedings IEEE 55: 1885–1897
Xu S (2001) Smoothing method for minimax problems. Comp. Optim. Appl. 20: 267–279
Watson GA (1997) The use of the ℓ1 norm in nonlinear errors-in-variables problems. In: Van Huffel (ed) Proceedings of Recent Advances on Total Least Squares Techniques & Errorsin-Variables Modeling
Watson GA (1998) Choice of norms for data fitting and function approximation. Acta Numerica, pp. 337–377
Watson GA and Yiu KFC (1991) On the solution of the errors in variables problem using the ℓ1 norm. BIT 31: 697–710
Wilson EO (1975) Sociobiology: The New Synthesis. Belknap Press, Cambridge, MA
Zitzler E (1999) Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. Thesis, Swiss Federal Institute of Technology Zurich
Zitzler E, Deb K and Thiele L (2000) Comparison of multiobjective evolution algorithms: empirical results. Evolutionary Computation 8(2): 173–195
Zuhe S, Neumaier A and Eiermann MC (1990) Solving minimax problems by interval methods. BIT 30: 742–751