Ivan Zelinka Guanrong Chen (cid:129) Editors Evolutionary Algorithms, Swarm Dynamics and Complex Networks Methodology, Perspectives and Implementation 123 Editors IvanZelinka Guanrong Chen Department ofComputer Science Department ofElectronic Engineering Faculty of Electrical Engineering City University of HongKong andComputer ScienceVŠB-TUO Kowloon, HongKong Ostrava, Poruba China Czech Republic ISSN 2194-7287 ISSN 2194-7295 (electronic) Emergence, Complexity andComputation ISBN978-3-662-55661-0 ISBN978-3-662-55663-4 (eBook) https://doi.org/10.1007/978-3-662-55663-4 LibraryofCongressControlNumber:2017948219 ©Springer-VerlagGmbHGermany2018 Foreword SeveralnaturalprocessesincludingDarwinianevolution,thecollectivebehaviorof socialcreaturesandtheirforagingstrategiesarecenteredaroundtheclassicaltaskof optimization. For more than half a century now, researchers have been drawing inspirations from the life-supporting activities and adaptation mechanisms of nat- ural creatures to design algorithms that can solve complex and mathematically intractablesearchandoptimizationproblemswhichareubiquitousindisciplinesof science and technology. Currently, the field of such nature-inspired algorithms is growing at a spectacular rate, and new algorithmic variants are continually emerging to meet the fast-growing challenges of the real-world optimization problems,forwhichnomathematicallyguaranteedmethodsareavailable.Thetwo main families of algorithms that primarily constitute this field today are the evo- lutionary computing methods and the swarm intelligence algorithms. The book edited by Profs. Ivan Zelinka and Guanrong Chen takes a very dif- ferent and elegant view of the fundamental algorithms belonging to evolutionary computing and swarm intelligence: how to obtain an insight into the dynamics of such algorithms by modeling them through the dynamics of an equivalent social network? This view enables researchers to gain valuable information about the search dynamics of these algorithms, thereby predicting the useful ranges of the associated control parameters and applicability to various real-life problems, by analyzing the equivalent social network. The book presents a well-organized col- lection of 14 comprehensive chapters divided into three parts. The reader is care- fullynavigatedthroughtheefficaciesofcomplexnetworks,swarmandevolutionary dynamics, and their randomization aspects. The exposure of the material is lucid. Quite complicated concepts are presented in a clear and convincing way which attributedtotheexpertiseofthechapterauthorsandtheEditors.Thefinalchapters ofthebook(likeChaps.11and12)provideveryinterestingextensionsoftheideas presentedpreviouslytowardsmorepracticalscenarios,forexample,Chap.11deals with the dynamics and communications of swarm virus seen through the lens of complex networks. In the exposure of the material, the authors have achieved a sound balance between the theory and practice. This book is the first of its kind, presenting a very interesting intersection of three fast-growing research fields of the swarm and evolutionary computing, complex networks, and CML systems. The idea of their mutual intersection is not very typical in the existing literature, and this is probably one of the main reasons why this edition should be especially valuable for the scientific and engineering research community. Finally,Imustconcludethatthisisnotonlyanurgentlyneededandverytimely volume, but also an authoritative and exceptionally well-compiled treatise of the fascinating topic of unification of the meta-heuristic dynamics and complex networks. Swagatam Das Indian Statistical Institute, Kolkata, India Preface Evolutionary algorithms constitute a class of well-known numerical methods, which are based on the Darwinian theory of evolution and Mendelian theory of heritage. They are partly based on random and partly based on deterministic principles.Duetothisnature,itischallengingtopredictitsperformanceinsolving complex nonlinear problems. Many techniques and hybridization methods have been developed to improve the algorithmic performances. These methods are typicallybasedonstatisticalapproachesandusuallyleadtoarecommendedsetting foragivenalgorithmoraclassofalgorithms.Also,verydiversehybridizationsare suggested by utilizing deterministic chaos instead of using other pseudorandom number generators, showing promising features and unique advantages. Recently, the study of evolutionary dynamics is focused not only on the traditional investi- gations, but also on the understanding and analyzing new principles, with the intentionofcontrollingandutilizingtheirpropertiesandperformancestowardmore effective real-world applications. This book, based on many years of intensive research of the authors, is proposing novel ideas about advancing evolutionary dynamics toward new phe- nomena including many new topics, even the dynamics of equivalent social net- works.Infact,itincludesmoreadvancedcomplexnetworksandincorporatesthem with the CMLs (coupled map lattices), which are usually used for spatiotemporal complex systems simulation and analysis, based on the observation that chaos in CML can be controlled, so does evolution dynamics. It will be shown that evo- lutionary algorithmscanbeunderstood justlikedynamicalsystemswith feedback. Thus, at least in theory, all engineering control methods can be applied. All such ideas will be illustrated and discussed in the following chapters. All the chapter authorsare,tothebestofourknowledge,originatorsoftheideasmentionedabove and researchers on evolutionary algorithms and chaotic dynamics as well as complex networks, who will provide benefits to the readers regarding modern scientific research on related subjects. Theorganizationofthechaptersinthebookisasfollows.Thebookconsistsof three parts. The first part (Theory) discusses and explains basic ideas about swarm dynamics and evolutionary algorithms related to complex networks and CML systems.Chapter1presentsmostimportantnotionswithcomprehensivereferences. Chapter2discusseshowtocreatenetworksfromevolutionarydynamics,basedon a few selected evolutionary algorithms, like ant colony optimization, with original experimentsandvisualizations.Thesecondpart(Applications)showshowtheidea abovecanbeappliedtodevelopingvariouseffectivealgorithmsandwhatlevelsof success it can reach to. Chapter 3 reports the use of the differential evolution algorithms and its conversion into networks with performance improvements. Chapters 4–6 explain, in more details, the conversion, analysis, and improvement oftheSOMAalgorithmusingthecomplexnetworkframework.InChap.7,theuse of complex networks in particle swarm algorithms is discussed, followed by an investigationofartificialbeecolonyalgorithmsinChap.8.Chapter9thenpresents differentviewsonhowrandomizationandcomplexnetworkscanbeconstructedfor meta-heuristic algorithms. The last part (Miscellanies) contains a few interesting chapters as possible extensions of the above-discussed ideas to other directions. Chapter 11 discusses possibilities for dynamics and communications of swarm computer viruses to be visualized as a network. This can be necessary for its analysis and prevention in the future. Today, the most advanced virus-attacking technology is perhaps Botnet or viruses developed based on the CnC (command andcontrol)technology,e.g.,StuxnetorGauss.Suchnewviraltechnologiescanbe usednotonlyforswarmintelligence,butalsofortheevolutionofviruscodes.This chapter predicts the future merging of technologies such as swarm intelligence, evolution dynamics, and complex networks. Chapter 12 further explains how networks are related totheway they areextended tocellular automata. Chapter 13 studies the topic of this book but from an opposite point of view as for how evolutionary dynamics can be used to design power grid networks. Chapter 14 discusses the dynamic analysis of genetic regulatory networks which can be an inspiration to be applied to topics mentioned above. Regarding the readership of the book, it presents instructional materials for senior undergraduate and graduate students in computer science, physics, applied mathematics and engineering, among others, who are working in the fields of complex networks and evolutionary algorithms, and even chaotic dynamics. Researchers who want to learn more on how evolutionary algorithms can be con- structed, analyzed, or controlled, as well as the relationships among swarm dynamics, complex networks, and CML systems, will find this book very useful. Thebookwillbearesourcehandbookandmaterialcollectionforpractitionerswho wanttoapplythesemethodstosolvereal-lifeproblemsinchallengingapplications. Thisbookisbynomeanscomprehensiveonthethreefieldsofresearchduetoits pagelimitation.Onlyselectedbasicideasandmainresultsarereported.Forfurther info, it is recommended to read referenced literature, which contains all relevant researchresultsandthelatestresearchprogress.Theeditorsandthechapterauthors hope that the readers will find the book informative and valuable for their studies, experiments, and simulations. Ostrava, Czech Republic Ivan Zelinka Kowloon, Hong Kong Guanrong Chen June 2017 Contents Part I Theory 1 Swarm and Evolutionary Dynamics as a Network. .... ..... .... 3 Ivan Zelinka 2 Evolutionary Dynamics and Its Network Visualization - Selected Examples . .... .... .... ..... .... .... .... .... .... ..... .... 31 Orkhan Yarakhmedov, Victor Polyakh, Ivan Chernogorov and Ivan Zelinka Part II Applications 3 Differential Evolution Dynamics Modeled by Social Networks ........ 67 Lenka Skanderová and Ivan Zelinka 4 Conversion of SOMA Algorithm into Complex Networks .... .... 101 Lukáš Tomaszek and Ivan Zelinka 5 Analysis of SOMA Algorithm Using Complex Network. ..... .... 115 Lukáš Tomaszek and Ivan Zelinka 6 Improvement of SOMA Algorithm Using Complex Networks. .... 131 Lukáš Tomaszek and Ivan Zelinka 7 Complex Networks in Particle Swarm... .... .... .... ..... .... 145 Michal Pluhacek, Roman Šenkeřík, Adam Viktorin and Tomas Kadavy 8 Comparison of Vertex Centrality Measures inComplexNetwork Analysis Based on Adaptive Artificial Bee Colony Algorithm . .... 161 Magdalena Metlicka and Donald Davendra 9 Randomization and Complex Networks for Meta-Heuristic Algorithms.... .... .... ..... .... .... .... .... .... ..... .... 177 Roman Šenkeřík, Ivan Zelinka, Michal Pluhacek, Adam Viktorin, Jakub Janostik and Zuzana Kominkova Oplatkova 10 Gallery of Evolutionary Networks.. .... .... .... .... ..... .... 195 Ivan Zelinka, Roman Šenkeřík and Michal Pluháček Part III Miscellanies 11 Swarm Virus, Evolution, Behavior and Networking.... ..... .... 213 Lubomir Sikora and Ivan Zelinka 12 Simple Networks on Complex Cellular Automata: From de Bruijn Diagrams to Jump-Graphs.. .... .... .... .... ..... .... 241 Genaro J. Martínez, Andrew Adamatzky, Bo Chen, Fangyue Chen and Juan C. Seck-Tuoh-Mora 13 AHybridMulti-objectiveEvolutionaryApproachforPowerGrid Topology Design ... .... ..... .... .... .... .... .... ..... .... 265 Xiaowen Bi and Wallace K.S. Tang 14 Dynamic Analysis of Genetic Regulatory Networks with Delays..... . 285 Zhi-Hong Guan and Guang Ling 15 Frontiers . .... .... .... ..... .... .... .... .... .... ..... .... 311 Ivan Zelinka Acronyms ABC Artificial bee colony, heuristic algorithm ACO Ant colony optimization, heuristic algorithm based on biological ant behavior Best The best individual, DE Betweenness centrality Graph attributes CA Cellular automata CF Cost function, used to evaluate individual quality Chaotic map Simple iterative description of chaotic systems Closeness centrality Graph attributes CML Coupled map lattices, simple model used to simulate spatiotemporal deterministic chaos CnC Command and control, technology used to control computer viruses in a centralized manner CNCML CMLsystemthatiscreatedonschemeEA!CN!CML CN Complex network, graph (network) with nontrivial topological features—features that do not occur in simple networks such as lattices or random graphs, usually occur in graphs modeling of real systems. CNS Complex network structure CPRNG Chaotic pseudorandom number generator, deterministic chaos is used here instead of classical formulas for PRNG CR Crossover threshold, DE DE Differential evolution Degree centrality Graph attributes EA Evolutionary algorithms ECT Evolutionary computational techniques EP Evolutionary programming ES Evolutionary strategies