nach oben

Natural Computing

Erschienen in:

01.03.2008

A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications

verfasst von: Alec Banks, Jonathan Vincent, Chukwudi Anyakoha

Erschienen in: Natural Computing | Ausgabe 1/2008

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Particle Swarm Optimization (PSO), in its present form, has been in existence for roughly a decade, with formative research in related domains (such as social modelling, computer graphics, simulation and animation of natural swarms or flocks) for some years before that; a relatively short time compared with some of the other natural computing paradigms such as artificial neural networks and evolutionary computation. However, in that short period, PSO has gained widespread appeal amongst researchers and has been shown to offer good performance in a variety of application domains, with potential for hybridisation and specialisation, and demonstration of some interesting emergent behaviour. This paper aims to offer a compendious and timely review of the field and the challenges and opportunities offered by this welcome addition to the optimization toolbox. Part I discusses the location of PSO within the broader domain of natural computing, considers the development of the algorithm, and refinements introduced to prevent swarm stagnation and tackle dynamic environments. Part II considers current research in hybridisation, combinatorial problems, multicriteria and constrained optimization, and a range of indicative application areas.

Vorheriger Artikel Lower bounds on the computational power of an optical model of computation

Nächster Artikel Doubler and linearizer: an approach toward a unified theory for molecular computing based on DNA complementarity

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abido MA (2002) Optimal power flow using particle swarm optimization. Int J Elect Power Energy Syst 24(7):563–571CrossRef

Angeline PJ (1998) Using selection to improve particle swarm optimization. In: Proceedings of the IEEE congress on evolutionary computation, Anchorage, Alaska

Balci HH, Valenzuela JF (2004) Scheduling electric power generators using particle swarm optimization combined with the Lagrangian relaxation method. Int J Appl Math Comput Sci 14(3):411–421MATHMathSciNet

Baltar AM, Fontane DG (2006) A generalized multiobjective particle swarm optimization solver for spreadsheet models: application to water quality. In: Proceedings of the twenty sixth annual American geophysical union hydrology days, 20–22 March 2006

Baumgartner U, Magele C, Renhart W (2004) Pareto optimality and particle swarm optimization. IEEE Trans Magn 40(2):1172–1175

Brabazon A, Silva A, de Sousa TF, O’Neill M, Matthews R, Costa E (2005) Investigating strategic inertia using orgswarm. Informatica 29:125–141

Brits R, Engelbrecht AP, van den Bergh F (2002) A niching particle swarm optimizer. In: Proceedings of the fourth Asia-Pacific conference on simulated evolution and learning

Chang BCH, Ratnaweera A, Halgamuge SK, Watson HC (2004) Particle swarm optimization for protein motif discovery. Genet Program Evolvable Mach 5:203–214CrossRef

Chen Y, Dong J, Yang B, Zhang Y (2004) A local linear wavelet neural network. In: Proceedings of the fifth world congress on intelligent control and automation, Hangzhou, P.R. China, pp 1954–1957, 15–19 June 2004

Chen A, Yang G, Wu Z (2006) Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J Zhejiang Univ Sci A 7(4):607–614MATHCrossRef

Clerc M, Kennedy J (2002) The particle swarm: explosion, stability and convergence in a multi-dimensional complex space. IEEE Trans Evol Comput 6:58–73

Coello Coello CA, Lechuga MS (2002) MOPSO: a proposal for multiple objective particle swarm optimization, in congress on evolutionary computation (CEC’2002), vol 2, IEEE Service Center, Piscataway, New Jersey, pp 1051–1056, May 2002

Conradie AVE, Miikkulainen R, Aldrich C (2002) Adaptive control utilising neural swarming. In: Proceedings of the genetic and evolutionary computation conference, New York, USA

Das S, Konar A, Chakraborty UK (2005a) An efficient evolutionary algorithm applied to the design of two-dimensional IIR filters. In: GECCO 2005: proceedings of the 2005 conference on genetic and evolutionary computation, pp 2157–2163

Das S, Konar A, Chakraborty UK (2005b) Improving particle swarm optimization with differentially perturbed velocity. In: GECCO 2005: proceedings of the 2005 conference on genetic and evolutionary computation, pp 177–184

Eberhart RC, Shi Y (2000) Comparing inertia weights and constriction factors in particle swarm optimization. In: Proceedings of the IEEE congress evolutionary computation, San Diego, CA, pp 84–88

Eberhart RC, Simpson P, Dobbins R (1996) Computational intelligence PC tools, chap. 6. AP Professional, San Diego, CA, pp 212–226

Foo YC, Chien SF, Low ALY, Teo CF (2005) New strategy for optimizing wavelength converter placement. Opt Express 13(2):545–551

Gaing Z-L (2003) Particle swarm optimization to solving the economic dispatch considering the generator constraints. IEEE Trans Power Syst 18(3):1187–1195

Georgiou VL, Pavlidis NG, Parsopoulos KE, Alevizos PhD, Vrahatis MN (2004) Optimizing the performance of probabilistic neural networks in a bioinformatics task. In: Proceedings of the EUNITE 2004 conference, pp 34–40

Goudos SK, Sahalos JN (2006) Microwave absorber optimal design using multi-objective particle swarm optimization. Microwave Opt Technol Lett 48:1553–1558. Published online in Wiley InterScience (http://www.interscience.wiley.com)

Habibi J, Zonouz SA, Saneei M (2006) A hybrid PS-based optimization algorithm for solving traveling salesman problem. In: IEEE symposium on frontiers in networking with applications (FINA 2006), Vienna, Austria, 18–20 April 2006

Higashi N, Iba H (2003) Particle swarm optimization with Gaussian mutation. In: Proceedings of the IEEE swarm intelligence symposium 2003 (SIS 2003), Indianapolis, Indiana, USA, pp 72–79

Hsiao YT, Chuang CL, Jiang JA (2005) Particle swarm optimization approach for multiple biosequence alignment. In: Proceedings of the IEEE international workshop on genomic signal processing and statistics 2005, Rhode Island, USA, 22–24 May 2005

Hu X, Eberhart RC (2002a) Multiobjective optimization using dynamic neighbourhood particle swarm optimization. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2002), Honolulu, Hawaii, USA

Hu X, Eberhart RC (2002b) Solving constrained nonlinear optimization problems with particle swarm optimization. In: Proceedings of the sixth world multiconference on systemics, cybernetics and informatics 2002 (SCI 2002), Orlando, USA

Hu X, Eberhart RC, Shi Y (2003a) Particle swarm with extended memory for multiobjective optimization. In: IEEE swarm intelligence symposium 2003, Indianapolis, IN, USA

Hu X, Eberhart RC, Shi Y (2003b) Engineering optimization with particle swarm. In: IEEE swarm intelligence symposium 2003, Indianapolis, IN, USA

Ismail A, Engelbrecht AP (1999) Training product units in feedforward neural networks using particle swarm optimization. In: Proceedings of the international conference on artificial intelligence, Durban, South Africa, pp 36–40

Jian M, Chen Y (2006) Introducing recombination with dynamic linkage discovery to particle swarm optimization. In: Proceedings of the genetic and evolutionary computation conference (GECCO2006), pp 85–86

Jiménez JJ, Cedeño JR (2003) Application of particle swarm optimization for electric power system restoration. PowerCON 2003, Special Theme: BLACKOUT

Juang C-F (2004) A hybrid of genetic algorithm and particle swarm optimization for recurrent network design. IEEE Trans Syst Man Cybern – Part B: Cybern 34(2):997–1006CrossRef

Kannan S, Slochanal SMR, Subbaraj P, Padhy NP (2004) Application of particle swarm optimization technique and its variants to generation expansion planning problem. Elect Power Syst Res 70(3):203–210CrossRef

Karpat Y, Özel T (2006) Swarm-intelligent neural network system (SINNS) based multi-objective optimization of hard turning. Trans NAMRI/SME 34:179–186

Kassabalidis IN, El-Sharkawi MA, Marks RJI, Moulin LS, Alves da Silva AP (2002) Dynamic security border identification using enhanced particle swarm optimization. IEEE Trans Power Syst 17(3):723–729CrossRef

Kauffman S, Levin S (1987) Towards a general theory of adaptive walks on rugged landscapes. J Theor Biol 128:11–45MathSciNet

Kendall G, Su Y (2005) A particle swarm optimization approach in the construction of optimal risky portfolios. In: Proceedings of the 23rd IASTED international multi-conference artificial intelligence and applications, Innsbruck, Austria, pp 140–145, 14–16 Feb. 2005

Kennedy J (1997) The particle swarm: social adaptation of knowledge. In: Proceedings of the international conference on evolutionary computation, IEEE, Piscataway, NJ, pp 303–308

Kennedy J (2003) Bare bones particle swarms. In: Proceedings of the IEEE swarm intelligence symposium 2003 (SIS 2003), Indianapolis, Indiana, USA, pp 80–87

Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks, Piscataway, NJ, pp 1942–1948

Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. In: Proceedings of the conference on systems, man and cybernetics, Piscataway, New Jersey, pp 4104–4109

Khemka N, Jacob C, Cole G (2005) Making soccer kicks better: a study in particle swarm optimization. In: Proceedings genetic and evolutionary computation conference (GECCO2005), pp 382–385

Ko PC, Lin PC (2004) A hybrid swarm intelligence based mechanism for earning forecast. In: Proceedings of the second international conference information technology for application

Krink T, Løvbjerg M (2002) The lifecycle model: combining particle swarm optimization, genetic algorithms and hillclimbers. In: Proceedings of parallel problem solving from nature VII (PPSN 2002). Lecture notes in computer science (LNCS) no 2439, pp 621–630

Li Y, Yao D, Yao J, Chen W (2005) A particle swarm optimization algorithm for beam angle selection in intensity-modulated radiotherapy planning. Phys Med Biol 50:3491–3514CrossRef

Lin C-J, Hong S-J, Lee C-Y (2006) The design of neuro-fuzzy networks using particle swarm optimization and recursive singular value decomposition. In: 2006 International joint conference on neural networks, Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, 16–21 July 2006

Liu H, Abraham A (2005) Fuzzy adaptive turbulent particle swarm optimization. In: Proceedings of fifth international conference on hybrid intelligent systems (HIS’05), Rio de Janeiro, Brazil, 6–9 November 2005

Lopes HS, Coelho LS (2005) Particle swarm optimization with fast local search for the blind travelling salesman problem. In: Proceedings of fifth international conference on hybrid intelligent systems (HIS’05), Rio de Janeiro, Brazil, 6–9 November 2005

Løvbjerg M, Rasmussen TK, Krink T (2001) Hybrid particle swarm optimizer with breeding and subpopulations. In: Proceedings of the genetic and evolutionary computation conference (GECCO-2001)

Lu H (2003) Dynamic population strategy assisted particle swarm optimization in multiobjective evolutionary algorithm design, 2003. IEEE Neural Network Society, IEEE NNS Student Research Grants 2002 – Final Reports

Luna EH, Coello Coello CA, Aguirre AH (2004) On the use of a population-based particle swarm optimizer to design combinational logic circuits. In: Zebulum RS, Gwaltney D, Hornby G, Keymeulen D, Lohn J, Stoica A (eds) Proceedings of the 2004 NASA/DoD conference on evolvable hardware. IEEE Computer Society, Los Alamitos, California, pp 183–190, June 2004

Mehran R, Fatehi A, Lucas C, Araabi BN (2006) Particle swarm extension to LOLIMOT. In: Proceedings of the sixth international conference on intelligent systems design and applications (ISDA’06)

Mendes R, Cortez P, Rocha M, Neves J (2002) Particle swarms for feedforward neural network training. In: Proceedings of the 2002 international joint conference on neural networks (IJCNN 2002), pp 1895–1899

Minsky M (1986) The society of mind. Simon and Schuster, New York

Mostaghim S, Teich J (2003a) Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO). In: 2003 IEEE swarm intelligence symposium proceedings, IEEE Service Center, Indianapolis, Indiana, USA, pp 26–33, April 2003

Mostaghim S, Teich J (2003b) The role of ε-dominance in multi objective particle swarm optimization methods. In: Proceedings of the 2003 congress on evolutionary computation (CEC’2003), vol 3. IEEE Press, Canberra, Australia, pp 1764–1771, December 2003

Naka S, Genji T, Yura T, Fukuyama Y (2003) A hybrid particle swarm optimization for distribution state estimation. IEEE Trans Power Syst 18(1):60–68CrossRef

Nenortaite J (2005) Computation improvement of stockmarket decision making model through the application of grid. Inf Technol Control 34(3):269–275

Nenortaite J, Simutis R (2004) Stocks’ trading system based on the particle swarm optimization algorithm. In: Bubak M, van Albada GD, Sloot PMA, Dongarra JJ (eds) Workshop on computational methods in finance and insurance. Computational science – ICCS 2004: 4th international conference. Proceedings, Part IV, Kraków, Poland, 6–9 June 2004

Omran MG, Engelbrecht AP, Salman A (2005) A color image quantization algorithm based on particle swarm optimization. Informatica 29:261–269MATH

Pang W, Wang K, Zhou C, Dong L (2004) Fuzzy discrete particle swarm optimization for traveling salesman problem. In: Proceedings of the fourth international conference on computer and information technology (CIT’04)

Parsopoulos KE, Vrahatis MN (2002b) Particle swarm optimization method in multiobjective problems. In: Proceedings of the ACM symposium on applied computing (SAC 2002), pp 603–607

Parsopoulos KE, Vrahatis MN (2002c) Particle swarm method for constrained optimization problems. In: Proceedings of the Euro-international symposium on computational intelligence 2002

Parsopoulos KE, Vrahatis MN (2004) UPSO: a unified particle swarm optimization scheme. In: Proceedings of the international conference on computational method in science and engineering (ICCMSE 2004). Lecture series on computer and computational sciences. VSP International Science Publishers, Zeist, The Netherlands, pp 868–873

Parsopoulos KE, Vrahatis MN (2006). Studying the performance of unified particle swarm optimization on the single machine total weighted tardiness problem. In: Sattar A, Kang BH (eds) AI 2006, LNAI 4304, Springer-Verlag, pp 1027–1031

Parsopoulos KE, Tasoulis DK, Vrahatis MN (2004) Multiobjective optimization using parallel vector evaluated particle swarm optimization. In: Proceedings of the IASTED international conference on artificial intelligence and applications (AIA 2004), vol 2. ACTA Press, Innsbruck, Austria, pp 823–828, February 2004

Poli R, Langdon WB, Holland O (2005) Extending particle swarm optimization via genetic programming. In: Keijzer M, Tettamanzi A, Collet P, van Hemert J, Tomassini M (eds) Proceedings of eighth European conference, EuroGP 2005. Lausanne, Switzerland, March 30–April 1 2005

Potter MA, de Jong KA (1994) A cooperative coevolutionary approach to function optimization. In: Proceedings of the third conference on parallel problem solving from nature. Springer, Berlin, Germany, pp 249–257

Robinson, Rahmat-Samii (2004) Particle swarm optimization in electromagnetics. IEEE Trans Anten Propagat 52(2):397–407

Schaffer JD (1985) Multiple objective optimization with vector evaluated genetic algorithms. In: Genetic algorithms and their applications: proceedings of the first international conference on genetic algorithms, pp 93–100

Shi Y, Eberhart RC (1998) A modified particle swarm optimizer. In: Proceedings of the IEEE international conference on evolutionary computation. IEEE Press, Piscataway, NJ, pp 69–73

Sierra MR, Coello Coello CA (2005) Improving PSO-based multi-objective optimization using crowding, mutation and e-dominance. In: Coello Coello CA, Aguirre HA, Zitzler E (eds) Evolutionary multi-criterion optimization. Third International conference, EMO 2005. Lecture notes in computer science, vol 3410. Springer, Guanajuato, México, pp 505–519, March 2005

Sugisaka M, Fan X (2005) An effective search method for neural network based face detection using particle swarm optimization. IEICE Trans Inf Syst E88-D(2):214

Tasgetiren F, Sevkli M, Lian YC, Gencyilmaz G (2004) Particle swarm optimization algorithm for single machine weighted tardiness problem. In: Proceedings IEEE congress on evolutionary computation, pp 1412–1419

Ting TO, Tao MVC, Loo CK, Ngu SS (2003) Solving unit commitment problem using hybrid particle swarm optimization. J Heurist 9(6):507–520MATHCrossRef

Ujjin S, Bentley PJ (2003) Particle swarm optimization recommender system. In: Proceedings of the IEEE swarm intelligence symposium 2003 (SIS 2003), Indianapolis, Indiana, USA, pp 124–131

van den Bergh F (1999) Particle swarm weight initialization in multi-layer perceptron artificial neural networks. In: Bajic VB, Sha D (eds) Development and practice of artificial intelligence techniques. IAAMSAD, Durban, South Africa, pp 41–45

van den Bergh F, Engelbrecht AP (2000)Cooperative learning in neural networks using particle swarm optimizers. South Afr Comput J (26):84–90

van den Bergh F, Engelbrecht AP (2002) A new locally convergent particle swarm optimizer. In: Proceedings of the IEEE conference systems, man and cybernetics, Hammamet, Tunisia

van den Bergh F, Engelbrecht AP (2004) A cooperative approach to particle swarm optimization. IEEE Trans Evol Comput 3:225–239CrossRef

Voss MS (2003) Social programming using functional swarm optimization. In: Proceedings of the 2003 IEEE swarm intelligence symposium (SIS03). Purdue University, Indianapolis, Indiana, USA, 24–26 April 2003

Voss MS, Feng X (2001) Emergent system identification using particle swarm optimization. In: Complex adaptive structures conference, Hutchinson Island, FL

Voss MS, Feng X (2002) A new methodology for emergent system identification using particle swarm optimization (PSO) and the group method of data handling (GMDH). In: Proceedings 2002 genetic and evolutionary computation conference, New York, NY, 9–13 July

Wachowiak MP, Smolikova R, Zheng Y, Zurada JM, Elmaghraby AS (2004) An approach to medical biomedical image registration utilizing particle swarm optimization. IEEE Trans Evol Comput 8(3):289–301CrossRef

Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82CrossRef

Xiao X, Dow ER, Eberhart RC, Ben Miled Z, Oppelt RJ (2003) Gene clustering using self-organizing maps and particle swarm optimization. In: Proceedings of second IEEE international workshop on high performance computational biology, Nice, France

Xiao-hua Z, Hong-yun M, Li-cheng J (2005) Intelligent particle swarm optimization in multiobjective optimization. In: 2005 IEEE congress on evolutionary computation (CEC’2005), vol 1. IEEE Service Center, Edinburgh, Scotland, pp 714–719, September 2005

Yang SY, Wang M, Jiao LC (2004) A quantum particle swarm optimization. In: Proceedings of the 2004 IEEE congress on evolutionary computation

Yen GG, Lu H (2002) Dynamic population size in multiobjective evolutionary algorithm. In: Proceedings 9th IEEE congress on evolutionary computation, pp 1648–1653

Yoshida H, Kawata K, Fukuyama Y, Takayama S, Nakanishi Y (2001) A particle swarm optimization for reactive power and voltage control considering voltage security assessment. In: Proceedings of power engineering society winter meeting, p 498

Zavala AEM, Diharce ERV, Aguirre AH (2005) Particle evolutionary swarm for design reliability optimization. In: Coello Coello CA, Aguirre AH, Zitzler E (eds) Evolutionary multi-criterion optimization. Third international conference, EMO 2005. Lecture notes in computer science, vol 3410. Springer, Guanajuato, México, pp 856–869, March 2005

Zhang WJ, Xie XF (2003) DEPSO: hybrid particle swarm with differential evolution operator. In: IEEE interenational conference on systems, man and cybernetics (SMCC), Washington DC, USA, pp 3816–3821

Zhang LB, Zhou CG, Liu XH, Ma ZQ, Liang YC (2003) Solving multi objective optimization problems using particle swarm optimization. In: Proceedings of the 2003 congress on evolutionary computation (CEC’2003), vol 4. IEEE Press, Canberra, Australia, pp 2400–2405, December 2003

Titel: A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications
verfasst von: Alec Banks
Jonathan Vincent
Chukwudi Anyakoha
Publikationsdatum: 01.03.2008
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2008
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-007-9050-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2008

Solving the Hamiltonian path problem with a light-based computer

Doubler and linearizer: an approach toward a unified theory for molecular computing based on DNA complementarity

On spiking neural P systems and partially blind counter machines

On the universality of peptide computing

Lower bounds on the computational power of an optical model of computation

Mapping non-conventional extensions of genetic programming

Premium Partner