Top

Natural Computing

Published in:

23-03-2018

A novel context-free grammar for the generation of PSO algorithms

Authors: Péricles B. C. Miranda, Ricardo B. C. Prudêncio

Published in: Natural Computing | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Particle swarm optimization algorithm (PSO) has been widely studied over the years due to its competitive results in different applications. However, its performance is dependent on some design components (e.g., inertia factor, velocity equation, topology). Thus, to define which is the best algorithm design to solve a given optimization problem is difficult due to the large number of variations and parameters that can be considered. This work proposes a novel context-free grammar for Grammar-Guided Genetic Programming (GGGP) algorithms to guide the creation of Particle Swarm Optimizers. The proposed grammar considers four aspects of the PSO algorithm that may strongly impact on its performance: swarm initialization, neighborhood topology, velocity update equation and mutation operator. To assess the proposal, a GGGP algorithm was set with the proposed grammar and employed to optimize the PSO algorithm in 32 unconstrained continuous optimization problems. In the experiments, we compared the algorithms generated from the proposed grammar with those algorithms produced by two other grammars presented in the literature to automate PSO designs. The results achieved by the proposed grammar were better than the counterparts. Besides, we also compared the generated algorithms to 6 competition algorithms with different strategies. The experiments have shown that the algorithms generated from the grammar reached better results.

previous article A pattern-driven solution for designing multi-objective evolutionary algorithms

next article Population-based bio-inspired algorithms for cluster ensembles optimization

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Alkaya AF, Algin R, Sahin Y, Agaoglu M, Aksakalli V (2014) Performance of migrating birds optimization algorithm on continuous functions. In: International conference in swarm intelligence. Springer, pp 452–459

Back T (1998) An overview of parameter control methods by self-adaptation in evolutionary algorithms. Fundam Inf 35(1–4):51–66MATH

Bader-El-Den M, Poli R (2008) Generating sat local-search heuristics using a gp hyper-heuristic framework. In: Artificial evolution. Springer, pp 37–49

Bojarczuk CC, Lopes HS, Freitas AA (1999) Discovering comprehensible classification rules by using genetic programming: a case study in a medical domain. In: GECCO, Citeseer, pp 953–958

Bojarczuk CC, Lopes HS, Freitas A et al (2000) Genetic programming for knowledge discovery in chest-pain diagnosis. IEEE Eng Med Biol Mag 19(4):38–44

Bot MC, Langdon WB (2000) Application of genetic programming to induction of linear classification trees. In: Genetic programming. Springer, pp 247–258

Brits R, Engelbrecht AP, Van den Bergh F (2002) A niching particle swarm optimizer. In: 4th Asia-Pacific conference on simulated evolution and learning, vol 2. Orchid Country Club, Singapore, pp 692–696

Burke EK, Hyde MR, Kendall G, Ochoa G, Ozcan E, Woodward JR (2009) Exploring hyper-heuristic methodologies with genetic programming. In: Computational intelligence. Springer, pp 177–201

Burke EK, Hyde M, Kendall G, Woodward J (2010) A genetic programming hyper-heuristic approach for evolving 2-d strip packing heuristics. IEEE Trans Evol Comput 14(6):942–958

Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724

Elshamy W, Emara HM, Bahgat A (2007) Clubs-based particle swarm optimization. In: Swarm intelligence symposium, 2007. SIS 2007. IEEE, IEEE, pp 289–296

El-Sherbiny MM (2011) Particle swarm inspired optimization algorithm without velocity equation. Egypt Inf J 12(1):1–8

Engelbrecht AP (2010) Heterogeneous particle swarm optimization. In: International conference on swarm intelligence. Springer, pp 191–202

Ferreira de Carvalho D, José Albanez Bastos-Filho C (2009) Clan particle swarm optimization. Int J Intell Comput Cybern 2(2):197–227MathSciNetMATH

Folino G, Pizzuti C, Spezzano G (2000) Genetic programming and simulated annealing: A hybrid method to evolve decision trees. In: Genetic programming. Springer, pp 294–303

Fukunaga AS (2008) Automated discovery of local search heuristics for satisfiability testing. Evol Comput 16(1):31–61

Hendtlass T (2001) A combined swarm differential evolution algorithm for optimization problems. In: Engineering of intelligent systems. Springer, pp 11–18

Hugosson J, Hemberg E, Brabazon A, O’Neill M (2010) Genotype representations in grammatical evolution. Appl Soft Comput 10(1):36–43

Jabeen H, Jalil Z, Baig AR (2009) Opposition based initialization in particle swarm optimization (o-pso). In: 11th Annual conference companion on genetic and evolutionary computation conference: late breaking papers. ACM, pp 2047–2052

Kramer O (2010) Evolutionary self-adaptation: a survey of operators and strategy parameters. Evol Intell 3(2):51–65MATH

Kruse R, Borgelt C, Braune C, Mostaghim S, Steinbrecher M (2016) Computational intelligence: a methodological introduction. Springer, New YorkMATH

Liu JL et al (2008) Evolving particle swarm optimization implemented by a genetic algorithm. J Adv Comput Intell Intell Inf 12:284–289

Li C, Yang S, Korejo I (2008) An adaptive mutation operator for particle swarm optimization. In: UK workshop on computational intelligence, 2008. IEEE, pp 165–170

Mckay RI, Hoai NX, Whigham PA, Shan Y, O’Neill M (2010) Grammar-based genetic programming: a survey. Genet Program Evol Mach 11(3–4):365–396

Miranda PB, Prudêncio RB (2015) Gefpso: A framework for pso optimization based on grammatical evolution. In: Proceedings of the 2015 on genetic and evolutionary computation conference. ACM, pp 1087–1094

Miranda PB, Prudêncio RB (2016b) Tree-based grammar genetic programming to evolve particle swarm algorithms. In: 2016 5th Brazilian conference on intelligent systems (BRACIS). IEEE, pp 25–30

Miranda P, Prudêncio R (2016a) A novel context-free grammar to guide the construction of particle swarm optimization algorithms. In: Proceedings of the 2016 5th Brazilian conference on intelligent systems. IEEE, pp 295–300

Montana DJ (1995) Strongly typed genetic programming. Evol Comput 3(2):199–230

Nasir M, Das S, Maity D, Sengupta S, Halder U, Suganthan PN (2012) A dynamic neighborhood learning based particle swarm optimizer for global numerical optimization. Inf Sci 209:16–36MathSciNet

O’Neill M, Brabazon A (2006a) Grammatical differential evolution. In: IC-AI, pp 231–236

O’Neill M, Brabazon A (2006b) Grammatical swarm: the generation of programs by social programming. Nat Comput 5(4):443–462MathSciNetMATH

O’Neil M, Ryan C (2003) Grammatical evolution. In: Grammatical evolution. Springer, pp 33–47

Pappa GL, Freitas A (2009) Automating the design of data mining algorithms: an evolutionary computation approach. Springer, New YorkMATH

Pappa GL, Ochoa G, Hyde MR, Freitas AA, Woodward J, Swan J (2014) Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms. Genet Program Evol Mach 15(1):3–35

Parsopoulos KE (2010) Particle swarm optimization and intelligence: advances and applications: advances and applications. IGI Global, Hershey

Parsopoulos KE, Vrahatis MN (2002) Recent approaches to global optimization problems through particle swarm optimization. Nat Comput 1(2–3):235–306MathSciNetMATH

Passaro A, Starita A (2008) Particle swarm optimization for multimodal functions: a clustering approach. J Artif Evol Appl 2008:8

Poli R, Di Chio C, Langdon WB (2005) Exploring extended particle swarms: a genetic programming approach. In: Proceedings of the 7th annual conference on genetic and evolutionary computation. ACM, pp 169–176

Poli R, Woodward J, Burke EK (2007) A histogram-matching approach to the evolution of bin-packing strategies. In: IEEE Congress on evolutionary computation, 2007. CEC 2007. IEEE, pp 3500–3507

Rashid M (2010) Combining pso algorithm and honey bee food foraging behavior for solving multimodal and dynamic optimization problems. PhD thesis, National University of Computer & Emerging Sciences

Si T (2012) Grammatical differential evolution adaptable particle swarm optimization algorithm. Int J Electron Commun Comput Eng 3(6):1526–1531

Si T, De A, Bhattacharjee AK (2014) Grammatical swarm based-adaptable velocity update equations in particle swarm optimizer. In: International conference on frontiers of intelligent computing: theory and applications (FICTA) 2013. Springer, pp 197–206

Smart W, Zhang M (2005) Using genetic programming for multiclass classification by simultaneously solving component binary classification problems. In: Genetic programming. Springer, pp 227–239

Surjanovic S, Bingham D (2014) Virtual library of simulation experiments: test functions and datasets. Retrieved December 4:2014

Tan Y, Li J, Zheng Z (2015) Introduction and ranking results of the icsi 2014 competition on single objective optimization. arXiv preprint arXiv:150102128

Tavares J, Pereira FB (2012) Automatic design of ant algorithms with grammatical evolution. In: European conference on genetic programming. Springer, pp 206–217

Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54(3):453–473

Vella A, Corne D, Murphy C (2009) Hyper-heuristic decision tree induction. In: World congress on nature & biologically inspired computing, 2009. NaBIC 2009. IEEE, pp 409–414

Wang YX, Xiang QL (2008) Particle swarms with dynamic ring topology. In: IEEE congress on evolutionary computation, 2008., IEEE, pp 419–423

Whigham PA et al (1995) Grammatically-based genetic programming. In: Workshop on genetic programming: from theory to real-world applications, Citeseer, vol 16, pp 33–41

Whigham PA, Dick G, Maclaurin J, Owen CA (2015) Examining the best of both worlds of grammatical evolution. In: Proceedings of the 2015 on genetic and evolutionary computation conference. ACM, pp 1111–1118

Woodward JR, Swan J (2014) Template method hyper-heuristics. In: Proceedings of the 2014 conference companion on genetic and evolutionary computation companion. ACM, pp 1437–1438

Xiao X, Zhang Q (2014) The multiple population co-evolution pso algorithm. In: International conference in swarm intelligence. Springer, pp 434–441

Xinchao Z (2010) A perturbed particle swarm algorithm for numerical optimization. Appl Soft Comput 10(1):119–124

Xin J, Chen G, Hai Y (2009) A particle swarm optimizer with multi-stage linearly-decreasing inertia weight. In: International joint conference on computational sciences and optimization, 2009. CSO 2009. IEEE, vol 1, pp 505–508

Yao X (1999) Evolving artificial neural networks. Proc IEEE 87(9):1423–1447

Zhang WJ, Xie XF et al (2003) Depso: hybrid particle swarm with differential evolution operator. IEEE Int Conf Syst Man Cybern 4:3816–3821

Zhang B, Zhang M, Zheng YJ (2014) Improving enhanced fireworks algorithm with new Gaussian explosion and population selection strategies. In: International conference in swarm intelligence. Springer, pp 53–63

Zheng YJ, Wu XB (2014) Evaluating a hybrid de and bbo with self adaptation on icsi 2014 benchmark problems. In: International conference in swarm intelligence. Springer, pp 422–433

Zheng S, Janecek A, Tan Y (2013) Enhanced fireworks algorithm. In: 2013 IEEE congress on evolutionary computation, pp 2069–2077. https://doi.org/10.1109/CEC.2013.6557813

Zheng S, Liu L, Yu C, Li J, Tan Y (2014) Fireworks algorithm and its variants for solving icsi2014 competition problems. In: International conference in swarm intelligence. Springer, pp 442–451

Title: A novel context-free grammar for the generation of PSO algorithms
Authors: Péricles B. C. Miranda
Ricardo B. C. Prudêncio
Publication date: 23-03-2018
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2020
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-018-9679-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2020

Population-based bio-inspired algorithms for cluster ensembles optimization

A proposal of quantum data representation to improve the discrimination power

A class of discrete dynamical systems with properties of both cellular automata and L-systems

A pattern-driven solution for designing multi-objective evolutionary algorithms

Molecular computing for Markov chains

Swarm optimization clustering methods for opinion mining

Premium Partner