Top

Social Network Analysis and Mining

Published in:

01-12-2015 | Original Article

Using network science to assess particle swarm optimizers

Authors: Marcos Oliveira, Carmelo J. A. Bastos-Filho, Ronaldo Menezes

Published in: Social Network Analysis and Mining | Issue 1/2015

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

search-config

AI-assisted search

Off

Abstract

Particle swarm optimizers (PSO) have been extensively used in optimization problems, but the scientific community still lacks proper mechanisms to analyze the swarm behavior during the optimization (execution) process. In this paper, we propose to assess the swarm information flow based on particle interactions. We introduce the concept of the swarm influence graph to capture the information exchange between the particles in a given iteration during the execution of the algorithm. We propose that analysis of this graph to find its number of components and its overall structure may be used to define a fingerprint for the swarm search behavior. We simulated the PSO algorithm with three different communication topologies and we showed that each topology leads to different communication signatures. Also, we showed that, in the case of a dynamic topology, this signature is related to the stagnation of the swarm.

previous article Temporal influence over the Last.fm social network

next article A simulation method for social networks

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 "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

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

Albert R, Barabasi AL (2002) Statistical mechanics of complex networks. Rev Mod Phys 74:47. doi:10.1103/RevModPhys.74.47 MATHMathSciNetCrossRef

Barabasi AL, Albert R (1999) Emergence of scaling in random networks. Science 286:509–512MathSciNetCrossRef

Bastos-Filho CJA, Lima-Neto FB, Lins AJCC, Nascimento AIS, Lima MP (2008) A novel search algorithm based on fish school behavior. In: IEEE international conference on systems, man and cybernetics, pp 2646–2651

Bratton D, Kennedy J (2007) Defining a standard for particle swarm optimization. In: Swarm intelligence symposium, SIS 2007. IEEE Press, New York, pp 120–127. doi:10.1109/SIS.2007.368035

Clerc M, Kennedy J (2002) The particle swarm: explosion, stability, and convergence in a multidimensional complex space. IEEE Trans Evol Comput 6(1):58–73. doi:10.1109/4235.985692

Cvetković D, Rowlinson P, Simić S (2010) An introduction to the theory of graph spectra, 1st edn. Cambridge University Press, New YorkMATH

Dorigo M, DiCaro G (1999) Ant colony optimization: a new meta-heuristic. In: Proceedings of the congress on evolutionary computation. IEEE Press, New York, pp 1470–1477

Dorogovtsev SN, Goltsev AV, Mendes JFF, Samukhin AN (2003) Spectra of complex networks. Phys Rev E 68:046–109. doi:10.1103/PhysRevE.68.046109

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. 10.1109/MHS.1995.494215

Eberhart R, Simpson P, Dobbins R (1996) Computational intelligence PC tools. Academic Press Professional Inc., New York

Engelbrecht AP (2007) Computational intelligence: an introduction. Wiley, New York

Farkas IJ, Derényi I, Barabási AL, Vicsek T (2001) Spectra of “real-world” graphs: beyond the semicircle law. Phys Rev E Stat Nonlin Soft Matter Phys 64(2 Pt 2). http://view.ncbi.nlm.nih.gov/pubmed/11497741

Godoy A, Von Zuben F (2009) A complex neighborhood based particle swarm optimization. In: CEC ’09. IEEE congress on evolutionary computation. pp 720–727. doi:10.1109/CEC.2009.4983016

Janson S, Middendorf M (2005) A hierarchical particle swarm optimizer and its adaptive variant. IEEE Trans Syst Man Cybern Part B Cybern 35(6):1272–1282. doi:10.1109/TSMCB.2005.850530

Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. In: Technical report, Erciyes University, Engineering Faculty, Computer Engineering Department

Kennedy J (1997) The particle swarm: social adaptation of knowledge. In: IEEE international conference on evolutionary computation. IEEE Press, New York, pp 303–308

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

Kennedy J, Eberhart RC (2001) Swarm intelligence. Morgan Kaufmann Publishers Inc., San Francisco

Kennedy J, Mendes R (2002) Population structure and particle swarm performance. In: CEC ’02. Proceedings of the 2002 congress on evolutionary computation, vol 2, pp 1671–1676. doi:10.1109/CEC.2002.1004493

Mendes R, Kennedy J, Neves J (2003) Watch thy neighbor or how the swarm can learn from its environment. In: SIS ’03. Proceedings of the 2003 swarm intelligence symposium. IEEE Press, New York, pp 88–94. doi:10.1109/SIS.2003.1202252

Mendes R, Kennedy J, Neves J (2004) The fully informed particle swarm: simpler, maybe better. IEEE Trans Evol Comput 8(3):204–210. doi:10.1109/TEVC.2004.826074

Mo S, Zeng J, Tan Y (2010) Particle swarm optimization based on self-organizing topology driven by fitness. In: CASON ’10. Proceedings of the 2010 international conference on computational aspects of social networks. IEEE Computer Society, Washington, DC, pp 23–26. doi:10.1109/CASoN.2010.13

Oliveira M, Bastos-Filho CJA, Menezes R (2013) Using network science to define a dynamic communication topology for particle swarm optimizers. In: Menezes R, Evsukoff A, González MC (eds) Complex networks, studies in computational intelligence, vol 424. Springer, Berlin, pp 39–47. doi:10.1007/978-3-642-30287-9_5

Peram T, Veeramachaneni K, Mohan C (2003) Fitness-distance-ratio based particle swarm optimization. In: SIS ’03. Proceedings of the swarm intelligence symposium. IEEE Press, New York, pp 174–181. doi:10.1109/SIS.2003.1202264

Pontes MR, Neto FBL, Bastos-Filho CJ (2011) Adaptive clan particle swarm optimization. In: 2011 IEEE symposium on swarm intelligence (SIS). IEEE Press, New York, pp 1–6

Shi Y, Eberhart R (1998) A modified particle swarm optimizer. In: IEEE world congress on computational intelligence. The 1998 IEEE international conference on evolutionary computation proceedings, pp 69–73. doi:10.1109/ICEC.1998.699146

Suganthan P (1999) Particle swarm optimiser with neighbourhood operator. In: CEC 99. Proceedings of the 1999 congress on evolutionary computation, vol 3, xxxvii+2348, p 3. doi:10.1109/CEC.1999.785514

Tang K, Li X, Suganthan PN, Yang Z, Weise T (2010) Benchmark Functions for the CEC’2010 Special Session and Competition on Large-Scale Global Optimization. Tech. rep., University of Science and Technology of China (USTC), School of Computer Science and Technology, Nature Inspired Computation and Applications Laboratory (NICAL): Héféi, Anhui, China. http://goo.gl/kz5P7d

Wang YX, Xiang QL (2008) Particle swarms with dynamic ring topology. In: Evolutionary computation. CEC 2008. IEEE world congress on computational intelligence, pp 419–423. doi:10.1109/CEC.2008.4630831

Zhan ZH, Zhang J, Li Y, Chung HH (2009) Adaptive particle swarm optimization. IEEE Trans Syst Man Cybern Part B Cybern 39(6):1362–1381CrossRef

Zhang J, Zhan Zh, Lin Y, Chen N, Zhong Jh, Chung HS, Li Y, Shi Yh (2011) Evolutionary computation meets machine learning: a survey. IEEE Comput Intell Mag 6(4):68–75MATHCrossRef

Zhou Z, Shi Y (2011) Inertia weight adaption in particle swarm optimization algorithm. In: Advances in swarm intelligence. Springer, Berlin, pp 71–79

Title: Using network science to assess particle swarm optimizers
Authors: Marcos Oliveira
Carmelo J. A. Bastos-Filho
Ronaldo Menezes
Publication date: 01-12-2015
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2015
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-015-0245-5

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2015

On the role of conductance, geography and topology in predicting hashtag virality

Automatic labeling of social network users Scientia.Net through the machine learning supervised application

Detecting topics and overlapping communities in question and answer sites

A model-independent approach for efficient influence maximization in social networks

Integrating the optimal classifier set for sentiment analysis

Community detection based on strong Nash stable graph partition

Premium Partner