nach oben

Natural Computing

Erschienen in:

11.01.2021

The influence of fitness landscape characteristics on particle swarm optimisers

verfasst von: A P Engelbrecht, P Bosman, K M Malan

Erschienen in: Natural Computing | Ausgabe 2/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In the growing field of swarm-based metaheuristics, it is widely agreed that the behaviour of an algorithm, in terms of a good balance of exploration and exploitation, plays an important part in its success. Despite this, the influence that the characteristics of an optimisation problem may have on the behaviour of an algorithm is largely ignored. The characteristics of an optimisation problem can be intuitively understood and quantified in terms of fitness landscapes characteristics (FLCs). Similarly, the behaviour of a swarm-based algorithm can be quantified in terms of its diversity rate-of-change (DRoC). This study investigates correlations between the FLCs of optimisation problems and the DRoCs of particle swarm optimisers. The result is a collection of findings about links between particular problem characteristics and algorithm behaviour. The approach followed in this study may also be used as a template for further studies that broaden the scope of this study.

Vorheriger Artikel The fractal geometry of fitness landscapes at the local optima level

Nächster Artikel Gamesourcing: an unconventional tool to assist the solution of the traveling salesman problem

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

Arani BO, Mirzabeygi P, Panahi MS (2013) An improved PSO algorithm with a territorial diversity-preserving scheme and enhanced exploration-exploitation balance. Swarm Evolut Comput 11:1–15CrossRef

Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. (CSUR) 35(3):268–308CrossRef

Bosman P, Engelbrecht AP (2014) Diversity rate of change measurement for particle swarm optimisers. In: Solnon C, Stützle T, Dorigo M, Birttari M, Garnier S, Hamann H, Montes de Oca M (eds) Swarm intelligence. Springer International Publishing, Cham, pp 86–97CrossRef

Chen X, Li Y (2007) A modified PSO structure resulting in high exploration ability with convergence guaranteed. IEEE Trans Syst Man Cybern Part B (Cybernetics) 37(5):1271–1289CrossRef

Dan Den Bergh F, Engelbrecht AP (2002) A new locally convergent particle swarm optimizer. Proc IEEE Int Conf Syst Man Cybern 3:94–99

De Jong KA (1975) Analysis of the behavior of a class of genetic adaptive systems. PhD thesis, Computer and Communication Sciences, University of Michigan, Ann Arbor

Dorigo M, Di Caro G (1999) Ant colony optimization: a new meta-heuristic. Proc IEEE Congr Evolut Comput 2:1470–1477

Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on micro machine and human science. pp 39–43, https://doi.org/10.1109/MHS.1995.494215

Engelbrecht AP (2013) Particle swarm optimization: global best or local best? In: Proceedings of the BRICS congress on computational intelligence, pp 124–135

Gandomi AH, Alavi AH (2012) Krill herd: a new bio-inspired optimization algorithm. Commun Nonlinear Sci Numer Simul 17(12):4831–4845MathSciNetCrossRef

García-Gonzalo E, Fernández-Martínez J (2012) A brief historical review of particle swarm optimization PSO. J Bioinf Intell Control 1(1):3–16. https://doi.org/10.1166/jbic.2012.1002CrossRef

Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549MathSciNetCrossRef

Hansen N, Kern S (2004) Evaluating the CMA evolution strategy on multimodal test functions. In: Proceedings of the international conference on parallel problem solving from nature, Springer, pp 282–291

Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, CambridgeCrossRef

Jones T, Forrest S (1995) Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Proceedings of the sixth international conference on genetic algorithms, Morgan Kaufmann, pp 184–192

Jordehi AR (2015) Enhanced leader PSO (ELPSO): a new PSO variant for solving global optimisation problems. Appl Soft Comput 26:401–417CrossRef

Kennedy J (1997) The particle swarm: social adaptation of knowledge. In: Proceedings of the IEEE international conference on evolutionary computation, pp 303–308, https://doi.org/10.1109/ICEC.1997.592326

Kennedy J (2003) Bare bones particle swarms. In: Proceedings of the IEEE swarm intelligence symposium, pp 80–87 https://doi.org/10.1109/SIS.2003.1202251

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks, 4:1942–1948. https://doi.org/10.1109/ICNN.1995.488968

Kennedy J, Mendes R (2002) Population structure and particle swarm performance. Proc Congr Evolut Comput 2:1671–1676. https://doi.org/10.1109/CEC.2002.1004493CrossRef

Khachaturyan A, Semenovskaya S, Vainstein B (1979) A statistical-thermodynamic approach to determination of structure amplitude phases. Sov Phys Crystallogr 24(5):519–524MathSciNet

Krishnanand K, Ghose D (2009) Glowworm swarm optimisation: a new method for optimising multi-modal functions. Int J Comput Intell Stud 1(1):93–119CrossRef

Lunacek M, Whitley D (2006) The dispersion metric and the CMA evolution strategy. In: Proceedings of the 8th annual conference on genetic and evolutionary computation, ACM, New York, USA. pp 477–484, https://doi.org/10.1145/1143997.1144085

Malan KM (2014) Characterising continuous optimisation problems for particle swarm optimisation performance prediction. Ph.D. thesis, University of Pretoria

Malan KM, Engelbrecht AP (2009) Quantifying ruggedness of continuous landscapes using entropy. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1440–1447

Malan KM, Engelbrecht AP (2013) Ruggedness, funnels and gradients in fitness landscapes and the effect on PSO performance. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 963–970

Malan KM, Engelbrecht AP (2014a) Characterising the searchability of continuous optimisation problems for PSO. Swarm Intell 8(4):275–302CrossRef

Malan KM, Engelbrecht AP (2014) A progressive random walk algorithm for sampling continuous fitness landscapes. In: Proceedings of the IEEE congress on evolutionary computation, pp 2507–2514

Malik RF, Rahman TA, Hashim SZM, Ngah R (2007) New particle swarm optimizer with sigmoid increasing inertia weight. Int J Comput Sci Secur 1(2):35–44

Meng XB, Gao XZ, Lu L, Liu Y, Zhang H (2016) A new bio-inspired optimisation algorithm: bird swarm algorithm. J Exp Theor Artif Intell 28(4):673–687CrossRef

Mersmann O, Bischl B, Trautmann H, Preuss M, Weihs C, Rudolph G (2011) Exploratory landscape analysis. In: Proceedings of the 13th annual conference on genetic and evolutionary computation, ACM, pp 829–836

Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51–67CrossRef

Mishra SK (2006a) Performance of repulsive particle swarm method in global optimization of some important test functions: A fortran program. Tech. rep, Social Science Research Network

Mishra SK (2006) Some new test functions for global optimization and performance of repulsive particle swarm method. Tech. Rep. 2718, University Library of Munich, Germany

Parpinelli RS, Lopes HS (2011) New inspirations in swarm intelligence: a survey. Int J Bio-Inspir Comput 3(1):1–16CrossRef

Peer ES, Van Den Bergh F, Engelbrecht AP (2003) Using neighbourhoods with the guaranteed convergence PSO. In: Proceedings of the IEEE swarm intelligence symposium, IEEE, pp 235–242

Price KV, Storn RM, Lampinen JA (2005) Unconstrained unimodal test functions. Differential evolution a practical approach to global optimization. Springer-Verlag, Berlin, pp 514–533MATH

Rahnamayan S, Tizhoosh HR, Salama MM (2007) A novel population initialization method for accelerating evolutionary algorithms. Comput Math Appl 53(10):1605–1614MathSciNetCrossRef

Spearman C (1904) The proof and measurement of association between two things. Am J Psychol 15(1):72–101CrossRef

Van Aardt WA, Bosman AS, Malan KM (2017) Characterising neutrality in neural network error landscapes. In: Proceedings of the IEEE congress on evolutionary computation, IEEE, pp 1374–1381

Van Den Bergh F (2001) An analysis of particle swarm optimizers. Ph.D. thesis, University of Pretoria South Africa

Van Den Bergh F, Engelbrecht AP (2010) A convergence proof for the particle swarm optimiser. Fundamenta Informaticae 105(4):341–374MathSciNetCrossRef

Vassilev VK, Fogarty TC, Miller JF (2003) Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. Advances in evolutionary computing. Springer, Berlin, pp 3–44CrossRef

Verel S, Collard P, Clergue M (2003) Where are bottlenecks in NK fitness landscapes? Proc IEEE Congr Evolut Comput 1:273–280

Wright S (1932) The roles of mutation, inbreeding, crossbreeding, and selection in evolution. In: Proceedings of the sixth international congress on genetics, pp 356–366

Yang XS (2009) Firefly algorithms for multimodal optimization. In: Proceedings of the international symposium on stochastic algorithms, Springer, pp 169–178

Yang XS (2010) Nature-inspired metaheuristic algorithms. Luniver Press, UK

Yang XS (2010) A new metaheuristic bat-inspired algorithm. Nature inspired cooperative strategies for optimization. Springer, Berlin, pp 65–74CrossRef

Yang XS, Deb S (2009) Cuckoo search via Lévy flights. In: Proceedings of the world congress on nature & biologically inspired computing, IEEE, pp 210–214

Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evolut Comput 3(2):82–102CrossRef

Zhang L, Yu H, Hu S (2003) A new approach to improve particle swarm optimization. In: Proceedings of the genetic and evolutionary computation conference, Springer, pp 134–139

Titel: The influence of fitness landscape characteristics on particle swarm optimisers
verfasst von: A P Engelbrecht
P Bosman
K M Malan
Publikationsdatum: 11.01.2021
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2022
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-020-09835-x

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 2/2022

Gamesourcing: an unconventional tool to assist the solution of the traveling salesman problem

Analyzing randomness effects on the reliability of exploratory landscape analysis

The fractal geometry of fitness landscapes at the local optima level

Classifying Metaheuristics: Towards a unified multi-level classification system

Understanding measure-driven algorithms solving irreversibly ill-conditioned problems

Comparison of synchronous and asynchronous parallelization of extreme surrogate-assisted multi-objective evolutionary algorithm