Gabriela Ochoa Francisco Chicano (Eds.) 6 2 0 Evolutionary Computation 9 S C in Combinatorial Optimization N L 15th European Conference, EvoCOP 2015 Copenhagen, Denmark, April 8–10, 2015 Proceedings 123 Lecture Notes in Computer Science 9026 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zürich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7407 Gabriela Ochoa Francisco Chicano (Eds.) (cid:129) Evolutionary Computation in Combinatorial Optimization 15th European Conference, EvoCOP 2015 – Copenhagen, Denmark, April 8 10, 2015 Proceedings 123 Editors Gabriela Ochoa Francisco Chicano Universityof Stirling Universityof Málaga Stirling Málaga UK Spain ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin ComputerScience ISBN 978-3-319-16467-0 ISBN 978-3-319-16468-7 (eBook) DOI 10.1007/978-3-319-16468-7 LibraryofCongressControlNumber:2015933497 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues SpringerChamHeidelbergNewYorkDordrechtLondon ©SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade. Coverillustration:DesignedbyMauroCastelli,ISEGI,UniversidadeNovadeLisboa,Portugal Printedonacid-freepaper SpringerInternationalPublishingAGSwitzerlandispartofSpringerScience+BusinessMedia (www.springer.com) Preface Combinatorial optimization is the discipline of decision making dealing with discrete alternatives. The field is at the interface between discrete mathematics, computing science, operational research, and recently also machine learning, and includes a diversity of algorithms and hybrid methods. Stochastic local search (metaheuristics), evolutionary, and other nature-inspired algorithms are a family of methods able to providerobust,highqualitysolutionstoproblemsofarealisticsizeinreasonabletime. These methods are also relatively simple to design and implement, and offer high flexibility. Many challenging applications in science, industry, and commerce can be formulated as optimization problems. A growing number of them have been suc- cessfully solved using the sort of computational methods mentioned above, which are the main content of these proceedings. EvoCOP was held for the first time in 2001, as the first workshop specifically devotedtoevolutionarycomputationincombinatorialoptimization.In2004itbecame aconference,andsincethenitrunsannually.Thisvolumecontainstheproceedingsof EvoCOP 2015, the 15th European Conference on Evolutionary Computation in Combinatorial Optimization, which was held in Copenhagen, Denmark, during April 8–10, 2015. EvoCOP is one of the four events of Evostar 2015. The other three are EuroGP (18th European Conference on Genetic Programming), EvoMUSART (4th InternationalConferenceonEvolutionaryandBiologicallyInspiredMusic,Sound,Art, and Design), and EvoApplications (18th European Conference on the Applications of Evolutionary Computation, formerly known as EvoWorkshops). Previous EvoCOP proceedings were published by Springer in the series Lecture Notes in Computer Science (LNCS Volumes 2037, 2279, 2611, 3004, 3448, 3906, 4446, 4972, 5482, 6022, 6622, 7245, 7832, 8600). The table in the next page reports the statistics for each conference. Thisyear,19outof46paperswereacceptedafterourrigorousdouble-blindprocess, resultingina41.3%acceptancerate,thetightersince2010.Wewouldliketothankthe quality and timeliness of our PC members work, especially since this year's time frame overlappedwiththeChristmasbreak.Decisionsconsideredboththereviewersreportand evaluationoftheProgramChairs.Thenumberofsubmissionsthisyearshowsanincrease and we hope this will be maintained as a future trend. The 19 accepted papers covered methodology, applications, and theoretical studies. The methods included evolutionary andmemetic(hybrid)algorithms,iteratedlocalsearch,variableneighborhoodsearch,ant colony optimization, artificial immune systems, hyper-heuristics, and other adaptive approaches. Theapplicationsincludedbothtraditionaldomains,suchasgraph coloring, knapsack, vehicle routing, job-shop scheduling, the p-median, and the orienteering problems; and new(er) domains such as designing deep recurrent neural networks, detecting network community structure, lock scheduling of ships, cloud resource man- agement, the firefighter problem, and AI planning. The theoretical studies involved approximation ratio, runtime, and black-box complexity analyses. The consideration of VI Preface multiple objectives, dynamic, and noisy environments was also present in a number of articles. This makes the EvoCOP proceedings an important source for current research trendsincombinatorialoptimization. EvoCOP Submitted Accepted Acceptance (%) 2015 46 19 41.3 2014 42 20 47.6 2013 50 23 46.0 2012 48 22 45.8 2011 42 22 52.4 2010 69 24 34.8 2009 53 21 39.6 2008 69 24 34.8 2007 81 21 25.9 2006 77 24 31.2 2005 66 24 36.4 2004 86 23 26.7 2003 39 19 48.7 2002 32 18 56.3 2001 31 23 74.2 We would like to express our appreciation to the various persons and institutions makingthisasuccessfulevent.First,wethanktheLocalOrganizersPaoloBurellifrom theAalborg UniversityandSebastianRisi fromtheITUniversity ofCopenhagen. We extendouracknowledgmenttoPabloGarcíaSánchezfromtheUniversidaddeGranada and Mauro Castelli from the Universidade Nova de Lisboa for excellent website and publicity material. We thank Marc Schoenauer from Inria (France) for his continued assistance in providing MyReview conference management system. Thanks are also due to Jennifer Willies and the Institute for Informatics and Digital Innovation at Edinburgh Napier University, UK, for administrative support and event coordination. Finally,wewanttothanktheNationalMuseumofDenmarkatCopenhagen,wherethe conference was held, and the prominent keynote speakers, Paulien Hogeweg from Utrecht University and Pierre-Yves Oudeyer, Research Director at Inria Paris. SpecialthanksalsotoCarlosCotta,PeterCowling,JensGottlieb,Jin-KaoHao,Jano vanHemert,PeterMerz,MartinMiddendorf,GüntherR.Raidl,andChristianBlumfor their hard work and dedication at past editions of EvoCOP, making this one of the reference international events in evolutionary computation and metaheuristics. April 2015 Gabriela Ochoa Francisco Chicano Organization EvoCOP 2015 was organized jointly with EuroGP 2015, EvoMUSART 2015, and EvoApplications 2015. Organizing Committee PC Chairs Gabriela Ochoa University of Stirling, UK Francisco Chicano University of Málaga, Spain Local Organization Paolo Burelli Aalborg University, Denmark Sebastian Risi IT University of Copenhagen, Denmark Publicity Chairs Pablo García Sánchez Universidad de Granada, Spain Mauro Castelli Universidade Nova de Lisboa, Portugal EvoCOP Steering Committee Carlos Cotta Universidad de Málaga, Spain Peter Cowling University of York, UK Jens Gottlieb SAP AG, Germany Jin-Kao Hao University of Angers, France Jano van Hemert University of Edinburgh, UK Peter Merz HannoverUniversityofAppliedSciencesandArts, Germany Martin Middendorf University of Leipzig, Germany Günther Raidl Vienna University of Technology, Austria Program Committee Adnan Acan Eastern Mediterranean University, Turkey Enrique Alba Universidad de Málaga, Spain Mehmet Emin Aydin University of Bedfordshire, UK Ruibin Bai University of Nottingham, UK Thomas Bartz-Beielstein Cologne University ofApplied Sciences,Germany Matthieu Basseur University of Angers, France Maria J. Blesa Universitat Politècnica de Catalunya, Spain Christian Blum IKERBASQUE and University of the Basque Country, Spain Sandy Brownlee University of Stirling, UK VIII Organization Pedro Castillo Universidad de Granada, Spain Francisco Chicano Universidad de Málaga, Spain Carlos Coello Coello CINVESTAV-IPN, Mexico Peter Cowling University of York, UK Karl Doerner Johannes Kepler University Linz, Austria Benjamin Doerr LIX, École Polytechnique, France Bernd Freisleben University of Marburg, Germany Adrien Goeffon University of Angers, France Jens Gottlieb SAP AG, Germany Walter Gutjahr University of Vienna, Austria Jin-Kao Hao University of Angers, France Emma Hart Edinburgh Napier University, UK Richard F. Hartl University of Vienna, Austria Geir Hasle SINTEF Applied Mathematics, Norway István Juhos University of Szeged, Hungary Graham Kendall University of Nottingham, UK Joshua Knowles University of Manchester, UK Mario Köppen Kyushu Institute of Technology, Japan Frédéric Lardeux University of Angers, France Rhyd Lewis Cardiff University, UK Arnaud Liefooghe Université des Sciences et Technologies de Lille, France José Antonio Lozano University of the Basque Country, Spain Gabriel Luque Universidad de Málaga, Spain Penousal Machado University of Coimbra, Portugal Jorge Maturana Universidad Austral de Chile, Chile Barry McCollum Queen’s University Belfast, UK David Meignan University of Osnabrück, Germany Juan Julián Merelo Universidad de Granada, Spain Peter Merz HannoverUniversityofAppliedSciencesandArts, Germany Martin Middendorf Universität Leipzig, Germany Julian Molina Universidad de Málaga, Spain Eric Monfroy University of Nantes, France Christine L. Mumford Cardiff University, UK Nysret Musliu Vienna University of Technology, Austria Gabriela Ochoa University of Stirling, UK Beatrice Ombuki-Berman Brock University, Canada Mario Pavone University of Catania, Italy Francisco J.B. Pereira University of Coimbra, Portugal Jakob Puchinger Austrian Institute of Technology, Austria Günther Raidl Vienna University of Technology, Austria Marcus Randall Bond University, Australia Marc Reimann University of Graz, Austria Eduardo Rodriguez-Tello Cinvestav - Tamaulipas, Mexico Peter Ross Edinburgh Napier University, UK Organization IX Frédéric Saubion University of Angers, France Marc Schoenauer Inria, France Patrick Siarry Université Paris-Est Créteil Val-de-Marne, France Kevin Sim Edinburgh Napier University, UK Jim Smith University of the West of England, UK Giovanni Squillero Politecnico di Torino, Italy Thomas Stützle Université Libre de Bruxelles, Belgium Andrew M. Sutton Friedrich-Schiller-University Jena, Germany El-Ghazali Talbi Université des Sciences et Technologies de Lille, France Renato Tinós University of São Paulo, Brazil Jano van Hemert University of Edinburgh, UK Nadarajen Veerapen University of Stirling, UK Sébastien Verel Université du Littoral Côte d’Opale, France Takeshi Yamada NTT Communication Science Laboratories, Japan Shengxiang Yang De Montfort University, UK