RaymondChiong(Ed.) Nature-InspiredAlgorithmsforOptimisation StudiesinComputationalIntelligence,Volume193 Editor-in-Chief Prof.JanuszKacprzyk SystemsResearchInstitute PolishAcademyofSciences ul.Newelska6 01-447Warsaw Poland E-mail:[email protected] Furthervolumesofthisseriescanbefoundonour Vol.182.AndrzejBargielaandWitoldPedrycz(Eds.) homepage:springer.com Human-CentricInformationProcessingThroughGranular Modelling,2009 Vol.170.LakhmiC.JainandNgocThanhNguyen(Eds.) ISBN978-3-540-92915-4 KnowledgeProcessingandDecisionMakinginAgent-Based Vol.183.MarcoA.C.PachecoandMarleyM.B.R.Vellasco Systems,2009 (Eds.) ISBN978-3-540-88048-6 IntelligentSystemsinOilFieldDevelopmentunder Vol.171.Chi-KeongGoh,Yew-SoonOngandKayChenTan Uncertainty,2009 (Eds.) ISBN978-3-540-92999-4 Multi-ObjectiveMemeticAlgorithms,2009 Vol.184.LjupcoKocarev,ZbigniewGaliasandShiguoLian ISBN978-3-540-88050-9 (Eds.) Vol.172.I-HsienTingandHui-JuWu(Eds.) IntelligentComputingBasedonChaos,2009 WebMiningApplicationsinE-CommerceandE-Services, ISBN978-3-540-95971-7 2009 Vol.185.AnthonyBrabazonandMichaelO’Neill(Eds.) ISBN978-3-540-88080-6 NaturalComputinginComputationalFinance,2009 Vol.173.TobiasGrosche ISBN978-3-540-95973-1 ComputationalIntelligenceinIntegratedAirlineScheduling, Vol.186.Chi-KeongGohandKayChenTan 2009 EvolutionaryMulti-objectiveOptimizationinUncertain ISBN978-3-540-89886-3 Environments,2009 Vol.174.AjithAbraham,RafaelFalco´nandRafaelBello(Eds.) ISBN978-3-540-95975-5 RoughSetTheory:ATrueLandmarkinDataAnalysis,2009 Vol.187.MitsuoGen,DavidGreen,OsamuKatai,BobMcKay, ISBN978-3-540-89886-3 AkiraNamatame,RuhulA.SarkerandByoung-TakZhang Vol.175.GodfreyC.OnwuboluandDonaldDavendra(Eds.) (Eds.) DifferentialEvolution:AHandbookforGlobal IntelligentandEvolutionarySystems,2009 Permutation-BasedCombinatorialOptimization,2009 ISBN978-3-540-95977-9 ISBN978-3-540-92150-9 Vol.188.AgustínGutiérrezandSantiagoMarco(Eds.) Vol.176.BeniaminoMurgante,GiuseppeBorrusoand BiologicallyInspiredSignalProcessingforChemicalSensing, AlessandraLapucci(Eds.) 2009 GeocomputationandUrbanPlanning,2009 ISBN978-3-642-00175-8 ISBN978-3-540-89929-7 Vol.189.SallyMcClean,PeterMillard,EliaEl-Darziand Vol.177.DikaiLiu,LingfengWangandKayChenTan(Eds.) ChrisNugent(Eds.) DesignandControlofIntelligentRoboticSystems,2009 IntelligentPatientManagement,2009 ISBN978-3-540-89932-7 ISBN978-3-642-00178-9 Vol.178.SwagatamDas,AjithAbrahamandAmitKonar Vol.190.K.R.Venugopal,K.G.SrinivasaandL.M.Patnaik MetaheuristicClustering,2009 SoftComputingforDataMiningApplications,2009 ISBN978-3-540-92172-1 ISBN978-3-642-00192-5 Vol.179.MirceaGh.NegoitaandSorinHintea Vol.191.ZongWooGeem(Ed.) Bio-InspiredTechnologiesfortheHardwareofAdaptive Music-InspiredHarmonySearchAlgorithm,2009 Systems,2009 ISBN978-3-642-00184-0 ISBN978-3-540-76994-1 Vol.192.AgusBudiyono,BambangRiyantoandEndra Vol.180.WojciechMitkowskiandJanuszKacprzyk(Eds.) Joelianto(Eds.) ModellingDynamicsinProcessesandSystems,2009 IntelligentUnmannedSystems:TheoryandApplications,2009 ISBN978-3-540-92202-5 ISBN978-3-642-00263-2 Vol.181.GeorgiosMiaoulisandDimitriPlemenos(Eds.) Vol.193.RaymondChiong(Ed.) IntelligentSceneModellingInformationSystems,2009 Nature-InspiredAlgorithmsforOptimisation,2009 ISBN978-3-540-92901-7 ISBN978-3-642-00266-3 Raymond Chiong (Ed.) Nature-Inspired Algorithms for Optimisation 123 RaymondChiong SwinburneUniversityofTechnology SarawakCampus,JalanSimpangTiga 93350Kuching Sarawak,Malaysia E-mail: [email protected] and SwinburneUniversityofTechnology JohnStreet,Hawthorn Victoria3122 Australia E-mail: [email protected] ISBN 978-3-642-00266-3 e-ISBN978-3-642-00267-0 DOI 10.1007/978-3-642-00267-0 Studiesin Computational Intelligence ISSN1860949X Library of Congress Control Number:2009920517 (cid:1)c 2009 Springer-Verlag Berlin Heidelberg Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse ofillustrations, recitation,broadcasting, reproductiononmicrofilm orinanyother way, and storage in data banks. Duplication of this publication or parts thereof is permittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution undertheGerman Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typeset&CoverDesign:ScientificPublishing Services Pvt. Ltd., Chennai, India. Printed in acid-free paper 9 8 7 6 5 4 3 2 1 springer.com Foreword Preface Research on stochastic optimisation methods emerged around half a century ago. One of these methods, evolutionary algorithms (EAs) first came into sight in the 1960s. At that time EAs were merely an academic curiosity without much practi- cal significance. It was not until the 1980s that the research on EAs became less theoretical and more applicable. With the dramatic increase in computational power today, many practical uses of EAs can now be found in various disciplines, including scientific and engineering fields. EAs, together with other nature-inspired approaches such as artificial neural networks, swarm intelligence, or artificial immune systems, subsequently formed the field of natural computation. While EAs use natural evolution as a paradigm for solving search and optimisation problems, other methods draw on the inspira- tion from the human brain, collective behaviour of natural systems, biological immune systems, etc. The main motivation behind nature-inspired algorithms is the success of nature in solving its own myriad problems. Indeed, many research- ers have found these nature-inspired methods appealing in solving practical prob- lems where a high degree of intricacy is involved and a bagful of constraints need to be dealt with on a regular basis. Numerous algorithms aimed at disentangling such problems have been proposed in the past, and new algorithms are being pro- posed nowadays. This book assembles some of the most innovative and intriguing nature- inspired algorithms for solving various optimisation problems. It also presents a range of new studies which are important and timely. All the chapters are written by active researchers in the field of natural computation, and are carefully pre- sented with challenging and rewarding technical content. I am sure the book will serve as a good reference for all researchers and practitioners, who can build on the many ideas introduced here and make more valuable contributions in the fu- ture. Enjoy! November 2008 Professor Zbigniew Michalewicz School of Computer Science University of Adelaide, Australia http://www.cs.adelaide.edu.au/~zbyszek/ Preface Preface Nature has always been a source of inspiration. In recent years, new concepts, techniques and computational applications stimulated by nature are being continu- ally proposed and exploited to solve a wide range of optimisation problems in di- verse fields. Various kinds of nature-inspired algorithms have been designed and applied, and many of them are producing high quality solutions to a variety of real-world optimisation tasks. The success of these algorithms has led to competi- tive advantages and cost savings not only to the scientific community but also the society at large. The use of nature-inspired algorithms stands out to be promising due to the fact that many real-world problems have become increasingly complex. The size and complexity of the optimisation problems nowadays require the development of methods and solutions whose efficiency is measured by their ability to find ac- ceptable results within a reasonable amount of time. Despite there is no guarantee of finding the optimal solution, approaches based on the influence of biology and life sciences such as evolutionary algorithms, neural networks, swarm intelligence algorithms, artificial immune systems, and many others have been shown to be highly practical and have provided state-of-the-art solutions to various optimisa- tion problems. This book provides a central source of reference by collecting and disseminat- ing the progressive body of knowledge on the novel implementations and impor- tant studies of nature-inspired algorithms for optimisation purposes. Addressing the various issues of optimisation problems using some new and intriguing intelli- gent algorithms is the novelty of this edited volume. It comprises 18 chapters, which can be categorised into the following 5 sections: • Section I Introduction • Section II Evolutionary Intelligence • Section III Collective Intelligence • Section IV Social-Natural Intelligence • Section V Multi-Objective Optimisation The first section contains two introductory chapters. In the first chapter, Weise et al. explain why optimisation problems are difficult to solve by addressing some of the fundamental issues that are often encountered in optimisation tasks such as premature convergence, ruggedness, causality, deceptiveness, neutrality, epistasis, VIII Preface robustness, overfitting, oversimplification, multi-objectivity, dynamic fitness, the No Free Lunch Theorem, etc. They also present some possible countermeasures, focusing on the stochastic based nature-inspired solutions, for dealing with these problematic features. This is probably the very first time in the literature that all these features have been discussed within a single document. Their discussion also leads to the conclusion of why so many different types of algorithms are needed. While parallels can certainly be drawn between these algorithms and various natural processes, the extent of the natural inspiration is not always clear. Steer et al. thus attempt to clarify what it means to say an algorithm is nature-inspired and examine the rationale behind the use of nature as a source of inspiration for such algorithm in the second chapter. In addition, they also discuss the features of na- ture which make it a valuable resource in the design of successful new algorithms. Finally, the history of some well-known algorithms are discussed, with particular focus on the role nature has played in their development. The second section of this book deals with evolutionary intelligence. It contains six chapters, presenting several novel algorithms based on simulated learning and evolution – a process of adaptation that occurs in nature. The first chapter in this section by Salomon and Arnold describes a hybrid evolutionary algorithm, called the Evolutionary-Gradient-Search (EGS) procedure. This procedure initially uses random variations to estimate the gradient direction, and then deterministically searches along that direction in order to advance to the optimum. The idea behind it is to utilise all individuals in the search space to gain as much information as possible, rather than selecting only the best offspring. Through both theoretical analysis and empirical studies, the authors show that the EGS procedure works well on most optimisation problems where evolution strategies also work well, in particular those with unimodal functions. Besides that, this chapter also discusses the EGS procedure’s behaviour in the presence of noise. Due to some performance degradations, the authors introduce the concept of inverse mutation, a new idea that proves very useful in the presence of noise, which is omnipresent in almost any real-world application. In an attempt to address some limitations of the standard genetic algorithm, Le- naerts et al. in the second chapter of this section present an algorithm that mimics evolutionary transitions from biology called the Evolutionary Transition Algo- rithm (ETA). They use the Binary Constraint Satisfaction Problem (BINCSP) as an illustration to show how ETA is able to evolve increasingly complex solutions from the interactions of simpler evolving solutions. Their experimental results on BINCSP confirm that the ETA is a promising approach that requires more exten- sive investigation from both theoretical and practical optimisation perspectives. Following which, Tenne proposes a new model-assisted Memetic Algorithm for expensive optimisation problems. The proposed algorithm uses a radial basis function neural network as a global model and performs a global search on this model. It then uses a local search with a trust-region framework to converge to a true optimum. The local search uses Kriging models and adapts them during the search to improve convergence. The author benchmarks the proposed algorithm Preface IX against four model-assisted evolutionary algorithms using eight well-known mathematical test functions, and shows that this new model-assisted Memetic Al- gorithm is able to outperform the four reference algorithms. Finally, the proposed algorithm is applied to a real-world application of airfoil shape optimisation, where better performance than the four reference algorithms is also obtained. In the next chapter, Wang and Li propose a new self-adaptive estimation of dis- tribution algorithm (EDA) for large scale global optimisation (LSGO) called the Mixed model Uni-variate EDA (MUEDA). They begin with an analysis on the behaviour and performances of uni-variate EDAs with different kernel probability densities via fitness landscape analysis. Based on the analysis, the self-adaptive MUEDA is devised. To assess the effectiveness and efficiency of MUEDA, the authors test it on typical function optimisation tasks with dimensionality scaling from 30 to 1500. Compared to other recently published LSGO algorithms, the MUEDA shows excellent convergence speed, final solution quality and dimen- sional scalability. Subsequently, Tirronen and Neri propose a Differential Evolution (DE) with integrated fitness diversity self-adaptation. In their algorithm, the authors intro- duce a modified probabilistic criterion which is based on a novel measurement of the fitness diversity. In addition, the algorithm contains an adaptive population size which is determined by variations in the fitness diversity. Extensive experi- mental studies have been carried out, where the proposed DE is being compared to a standard DE and four modern DE based algorithms. Numerical results show that the proposed DE is able to produce promising solutions and is competitive with the modern DEs. Its convergence speed is also comparable to those state-of-the-art DE based algorithms. In the final chapter of this section, Patel uses genetic algorithms to optimise a class of biological neural networks, called Central Pattern Generators (CPGs), with a view to providing autonomous, reactive and self-modulatory control for practical engineering solutions. This work is precursory to producing controllers for marine energy devices with similar locomotive properties. Neural circuits are evolved using evolutionary techniques. The lamprey CPG, responsible for swim- ming movements, forms the basis of evolution, and is optimised to operate with a wider range of frequencies and speeds. The author demonstrates via experimental results that simpler versions of the CPG network can be generated, whilst outper- forming the swimming capabilities of the original CPG network. The third section deals with collective intelligence, a term applied to any situation in which indirect influences cause the emergence of collaborative effort. Four chap- ters are presented, each addressing one novel algorithm. The first chapter of the sec- tion by Bastos Filho et al. gives an overview of a new algorithm for searching in high-dimensional spaces, called the Fish School Search (FSS). Based on the behav- iours of fish schools, the FSS works through three main operators: feeding, swim- ming and breeding. Via empirical studies, the authors demonstrate that the FSS is quite promising for dealing with high-dimensional problems with multimodal functions. In particular, it has shown great capability in finding balance between X Preface exploration and exploitation, self-adapting swiftly out of local minima, and self- regulating the search granularity. The next chapter by Tan and Zhang presents another new swarm intelligence algorithm called the Magnifier Particle Swarm Optimisation (MPSO). Based on the idea of magnification transformation, the MPSO enlarges the range around each generation’s best individual, while the velocity of particles remains un- changed. This enables a much faster convergence speed and better optimisation solving capability. The authors compare the performance of MPSO to the Stan- dard Particle Swarm Optimisation (SPSO) using the thirteen benchmark test func- tions from CEC 2005. The experimental results show that the proposed MPSO is indeed able to tremendously speed up the convergence and maintain high accuracy in searching for the global optimum. Finally, the authors also apply the MPSO to spam detection, and demonstrate that the proposed MPSO achieves promising re- sults in spam email classification. Mezura-Montes and Flores-Mendoza then present a study about the behaviour of Particle Swarm Optimisation (PSO) in constrained search spaces. Four well- known PSO variants are used to solve a set of test problems for comparison pur- poses. Based on the comparative study, the authors identify the most competitive PSO variant and improve it with two simple modifications related to the dynamic control of some parameters and a variation in the constraint-handling technique, resulting in a new Improved PSO (IPSO). Extensive experimental results show that the IPSO is able to improve the results obtained by the original PSO variants significantly. The convergence behaviour of the IPSO suggests that it has better exploration capability for avoiding local optima in most of the test problems. Fi- nally, the authors compare the IPSO to four state-of-the-art PSO-based ap- proaches, and confirm that it can achieve competitive or even better results than these approaches, with a moderate computational cost. The last chapter of this section by Rabanal et al. describes an intriguing algo- rithm called the River Formation Dynamics (RFD). This algorithm is inspired by how water forms rivers by eroding the ground and depositing sediments. After drops transform the landscape by increasing or decreasing the altitude of different areas, solutions are given in the form of paths of decreasing altitudes. Decreasing gradients are constructed, and these gradients are followed by subsequent drops to compose new gradients and reinforce the best ones. The authors apply the RFD to solve three NP-complete problems, and compare its performance to Ant Colony Optimisation (ACO). While the RFD normally takes longer than ACO to find good solutions, it is usually able to outperform ACO in terms of solution quality after some additional time passes. The fourth section contains two survey chapters. The first survey chapter by Neme and Hernández discusses optimisation algorithms inspired by social phenomena in human societies. This study is highly important as majority of the natural algorithms in the optimisation domain are inspired by either biological phenomena or social behaviours of mainly animals and insects. As social phenom- ena often arise as a result of interaction among individuals, the main idea behind Preface XI algorithms inspired by social phenomena is that the computational power of the inspired algorithms is correlated to the richness and complexity of the correspond- ing social behaviour. Apart from presenting social phenomena that have motivated several optimisation algorithms, the authors also refer to some social processes whose metaphor may lead to new algorithms. Their hypothesis is that some of these phenomena - the ones with high complexity, have more computational power than other, less complex phenomena. The second survey chapter by Bernardino and Barbosa focuses on the applica- tions of Artificial Immune Systems (AISs) in solving optimisation problems. AISs are computational methods inspired by the natural immune system. The main types of optimisation problems that have been considered include the unconstrained opti- misation problems, the constrained optimisation problems, the multimodal optimisa- tion problems, as well as the multi-objective optimisation problems. While several immune mechanisms are discussed, the authors have paid special attention to two of the most popular immune methodologies: clonal selection and immune networks. They remark that even though AISs are good for solving various optimisation prob- lems, useful features from other techniques are often combined with a “pure” AIS in order to generate hybridised AIS methods with improved performance. The fifth section deals with multi-objective optimisation. There are four chap- ters in this section. It starts with a chapter by Jaimes et al. who present a compara- tive study of different ranking methods on many-objective problems. The authors consider an optimisation problem to be a many-objective optimisation problem (instead of multi-objective) when it has more than 4 objectives. Their aim is to in- vestigate the effectiveness of different approaches in order to find out the advan- tages and disadvantages of each of the ranking methods studied and, in general, their performance. The results presented can be an important guide for selecting a suitable ranking method for a particular problem at hand, developing new ranking schemes or extending the Pareto optimality relation. Next, Nebro and Durillo present an interesting chapter that studies the effect of applying a steady-state selection scheme to Non-dominated Sorting Genetic Algo- rithm II (NSGA-II), a fast and elitist Multi-Objective Evolutionary Algorithm (MOEA). This work is definitely a timely and important one, since not many non- generational MOEAs exist. The authors use a benchmark composed of 21 bi- objective problems for comparing the performance of both the original and the steady-state versions of NSGA-II in terms of the quality of the obtained solutions and their convergence speed towards the optimal Pareto front. Comparative studies between the two versions as well as four state-of-the-art multi-objective optimisers not only demonstrate the significant improvement obtained by the steady-state scheme over the generational one in most of the problems, but also its competitive- ness with the state-of-the-art algorithms regarding the quality of the obtained ap- proximation sets and the convergence speed. The following chapter by Tan and Teo proposes two new co-evolutionary algo- rithms for multi-objective optimisation based on the Strength Pareto Evolutionary Algorithm 2 (SPEA2), another state-of-the-art MOEA. The two new algorithms