Lecture Notes in Computer Science 4446 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Carlos Cotta Jano van Hemert (Eds.) Evolutionary Computation in Combinatorial Optimization 7th European Conference, EvoCOP 2007 Valencia, Spain, April 11-13, 2007 Proceedings 1 3 VolumeEditors CarlosCotta UniversidaddeMálaga,Dept.LenguajesyCienciasdelaComputación ETSIInformática,CampusTeatinos,29071Málaga,Spain E-mail:[email protected] JanovanHemert UniversityofEdinburgh,Nationale-ScienceInstitute 15SouthCollegeStreet,EdinburghEH89AA,UK E-mail:[email protected] Coverillustration:Morphogenesisseries#12byJonMcCormack,2006 LibraryofCongressControlNumber:2007923599 CRSubjectClassification(1998):F.1,F.2,G.1.6,G.2.1,G.1 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-71614-9SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-71614-3SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2007 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:12041480 06/3180 543210 Preface Metaheuristics have often been shown to be effective for difficult combinatorial optimizationproblemsappearinginvariousindustrial,economical,andscientific domains. Prominent examples of metaheuristics are evolutionary algorithms, simulated annealing, tabu search, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and ant colony optimization. Successfully solved problems include scheduling, timetabling, network design, transportationanddistribution,vehiclerouting,thetravelingsalesmanproblem, satisfiability, packing and cutting, and general mixed integer programming. EvoCOP began in 2001 and has been held annually since then. It was the first event specifically dedicated to the application of evolutionary computation andrelatedmethods to combinatorialoptimizationproblems.Originallyheldas a workshop,EvoCOPbecame a conference in 2004.The events gaveresearchers an excellent opportunity to present their latest research and to discuss current developments and applications as well as providing for improved interaction between members of this scientific community. Following the general trend of hybrid metaheuristics and diminishing boundaries between the different classes of metaheuristics, EvoCOP has broadened its scope over the last years and invitedsubmissionsonanykindofmetaheuristicforcombinatorialoptimization. This volume contains the proceedings of EvoCOP 2007, the seventh Euro- pean Conference on EvolutionaryComputation in CombinatorialOptimization. It was held in Valencia, Spain, April 11–13, 2007, jointly with EuroGP 2007, the Tenth European Conference on Genetic Programming, EvoBIO 2007, the Fifth European Conference on Evolutionary Computation and Machine Learn- ing in Bioinformatics, and EvoWorkshops 2007, which consisted of the follow- ing sevenindividualworkshops:EvoCOMNET,the FourthEuropeanWorkshop on the Application of Nature-Inspired Techniques to Telecommunication Net- works and Other Connected Systems; EvoFIN, the First European Workshop on Evolutionary Computation in Finance and Economics; EvoIASP, the Ninth European Workshop on Evolutionary Computation in Image Analysis and Sig- nal Processing; EvoInteraction, the Second European Workshop on Interactive Evolution and Humanized Computational Intelligence; EvoMUSART, the Fifth European Workshop on Evolutionary Music and Art; EvoSTOC, the Fourth European Workshop on Evolutionary Algorithms in Stochastic and Dynamic Environments, and EvoTransLog, the First European Workshop on Evolution- ary Computation in Transportation and Logistics. Since 2007, all these events aregroupedunderthecollectivenameEvoStar,andconstituteEurope’spremier co-located meetings on evolutionary computation. Accepted papers of previous EvoCOP editions were published by Springer in the series Lecture Notes in Computer Science (LNCS – Volumes 2037, 2279, 2611, 3004,3448, and 3906). Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. VI Preface EvoCOP Submitted Accepted Acceptance ratio 2001 31 23 74.2% 2002 32 18 56.3% 2003 39 19 48.7% 2004 86 23 26.7% 2005 66 24 36.4% 2006 77 24 31.2% 2007 81 21 25.9% The rigorous, double-blind reviewing process of EvoCOP 2007 resulted in a strong selection among the submitted papers; the acceptance rate was 25.9%. EachpaperwasreviewedbyatleastthreemembersoftheInternationalProgram Committee.Allacceptedpaperswerepresentedorallyatthe conferenceandare included in this proceedings volume. We would like to credit the members of our Program Committee, to whom we are very grateful for their quick and thorough work and the valuable advice on how to improve papers for the final publication. EvoCOP 2007 contributions deal with representations, heuristics, analysisofproblemstructures,andcomparisonsofalgorithms.Thelistofstudied combinatorial optimization problems includes prominent examples like graph coloring, knapsack problems, the traveling salesperson problem, scheduling, as well as specific real-worldproblems. Wewouldliketoexpressoursinceregratitudetotheinternationallyrenowned invited speakers who gave the keynote talks at the conference: Ricard V. Sol´e, headoftheComplexSystemsLabattheUniversityPompeuFabra,ChrisAdami, head of the Digital Life Lab at the California Institute of Technology,and Alan Bundy, from the Centre for Intelligent Systems and their Applications, School of Informatics at the University of Edinburgh. The success of the conference resulted from the input of many people, to whom we would like to express our appreciation. We thank Marc Schoenauer forprovidingthe Web-basedconferencemanagementsystem.The localorganiz- ers, led by Anna Isabel Esparcia-Alc´azar, did an extraordinary job for which we are very grateful. We thank the Universidad Polit´ecnica de Valencia, Spain, for their institutional and financial support and for providing premises and ad- ministrative assistance,the Instituto Tecnolo´gico de Inform´atica in Valencia for cooperation and help with local arrangements, and the Spanish Ministerio de Educacio´ny Ciencia for their financialsupport. Thanks arealsodue to Jennifer Willies and the Centre for Emergent Computing at Napier University in Edin- burgh, Scotland, for administrative support and event coordination. Last, but not least, we would especially like to thank Jens Gottlieb and Gu¨nther Raidl for their support and guidance, to whom we owe a lot. From their hard work and dedication, EvoCOP 2007 has now become one of the reference events in evolutionary computation. April 2007 Carlos Cotta Jano van Hemert Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Organization EvoCOP 2007 was organized jointly with EuroGP 2007, EvoBIO 2007, and EvoWorkshops 2007. Organizing Committee Chairs Carlos Cotta, Universidad de Ma´laga, Spain, Jano van Hemert, University of Edinburgh, UK Local Chair Anna Isabel Esparcia-Alca´zar,Universidad Polit´ecnica de Valencia, Spain Publicity Chair Leonardo Vanneschi, University of Milano-Bicocca, Italy EvoCOP Steering Committee Carlos Cotta, Universidad de Ma´laga, Spain, Jens Gottlieb, SAP AG, Germany, Jano van Hemert, University of Edinburgh, UK, Gu¨nther Raidl, Vienna University of Technology, Austria Program Committee Adnan Acan, Eastern Mediterranean University, Turkey Hern´an Aguirre, Shinshu University, Japan Enrique Alba, Universidad de Ma´laga, Spain Mehmet Emin Aydin, London South Bank University, UK Ruibin Bai, University of Nottingham, UK Christian Bierwirth, University of Bremen, Germany Christian Blum, Universitat Polit`ecnica de Catalunya, Spain Peter Brucker, University of Osnabru¨ck, Germany Edmund Burke, University of Nottingham, UK Pedro Castillo, Universidad de Granada, Spain David W. Corne, Heriot-Watt University, UK Ernesto Costa, University of Coimbra, Portugal Carlos Cotta, Universidad de Ma´laga, Spain Peter I. Cowling, University of Bradford, UK Bart Craenen, Napier University, Edinburgh, UK Keshav Dahal, University of Bradford, UK David Davis, NuTech Solutions Inc., USA Karl F. Do¨rner, University of Vienna, Austria Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. VIII Organization Anton V. Eremeev, Omsk Branch of Sobolev Institute of Mathematics, Russia Jeroen Eggermont, University of Leiden, The Netherlands Antonio J. Ferna´ndez, Universidad de Ma´laga, Spain Francisco Fern´andez de Vega, Universidad de Extremadura, Spain David B. Fogel, Natural Selection, Inc., USA Bernd Freisleben, University of Marburg, Germany Jos´e E. Gallardo, Universidad de Ma´laga, Spain Michel Gendreau, Universit´e de Montr´eal, Canada Jens Gottlieb, SAP AG, Germany Joern Grahl, University of Mannheim, Germany Walter Gutjahr, University of Vienna, Austria Jin-Kao Hao, University of Angers, France Emma Hart, Napier University, Edinburgh, UK Richard F. Hartl, University of Vienna, Austria Geir Hasle, SINTEF, Norway Jano van Hemert, University of Edinburgh, UK Juhos Istva´n, University of Szeged, Hungary Bryant A. Julstrom, St. Cloud State University, USA Graham Kendall, University of Nottingham, UK Joshua D. Knowles, University of Manchester, UK Gary A. Kochenberger,University of Colorado, USA Mario K¨oppen, Fraunhofer IPK, Germany JozefJ.Kratica,SerbianAcademyofSciencesandArts,SerbiaandMontenegro Rhyd Lewis, Cardiff University, UK Andrea Lodi, University of Bologna, Italy Jos´e Antonio Lozano, University of the Basque Country, Spain Arne Løkketangen, Molde University College, Norway Vittorio Maniezzo, University of Bologna, Italy Dirk C. Mattfeld, Technical University Braunschweig,Germany Helmut A. Mayer, University of Salzburg, Austria Barry McCollum, Queen’s University Belfast, UK Juan Julia´n Merelo-Guervo´s,Universidad de Granada, Spain Daniel Merkle, University of Leipzig, Germany Peter Merz, University of Kaiserslautern,Germany Martin Middendorf, University of Leipzig, Germany Pablo Moscato, The University of Newcastle, Australia Christine L. Mumford, Cardiff University, UK Francisco J. B. Pereira,University of Coimbra, Portugal Adam Prugel-Bennett, University of Southampton, UK Jakob Puchinger, University of Melbourne, Australia Gu¨nther R. Raidl, Vienna University of Technology, Austria Marcus C. Randall, Bond University, Australia Colin Reeves, Coventry University, UK Marc Reimann, ETH Zurich, Switzerland Andrea Roli, University of Bologna,Italy Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Organization IX Roberto Santana, University of the Basque Country, Spain Marc Schoenauer, INRIA, France Marc Sevaux, University of South Brittany, France Christine Solnon, University Lyon I, France Giovanni Squillero, Politecnico di Torino, Italy Thomas Stu¨tzle, Universit´e Libre de Bruxelles, Belgium El-ghazaliTalbi, INRIA Futurs – Lille, France Jorge Tavares, University of Coimbra, Portugal Stefan Voß, University of Hamburg, Germany Ingo Wegener, University of Dortmund, Germany Fatos Xhafa, Universitat Polit`ecnica de Catalunya, Spain Takeshi Yamada, NTT Communication Science Laboratories,Japan Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. Table of Contents A New Local Search Algorithm for the DNA Fragment Assembly Problem ........................................................ 1 Enrique Alba and Gabriel Luque A Hybrid Immune-Based System for the Protein Folding Problem...... 13 Carolina P. de Almeida, Richard A. Gon¸calves, and Myriam R. Delgado A Genetic Algorithm for the Resource Renting Problem with Minimum and Maximum Time Lags......................................... 25 Francisco Ballest´ın A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem........................................... 36 Christian Blum, Carlos Cotta, Antonio J. Ferna´ndez, and Jos´e E. Gallardo Genetic Algorithms for Word Problems in Partially Commutative Groups ......................................................... 48 Matthew J. Craven A GRASP and Branch-and-Bound Metaheuristic for the Job-Shop Scheduling ...................................................... 60 Susana Fernandes and Helena R. Louren¸co Reducing the Size of Traveling Salesman Problem Instances by Fixing Edges .......................................................... 72 Thomas Fischer and Peter Merz Iterated k-Opt Local Search for the Maximum Clique Problem......... 84 Kengo Katayama, Masashi Sadamatsu, and Hiroyuki Narihisa Accelerating Local Search in a Memetic Algorithm for the Capacitated Vehicle Routing Problem.......................................... 96 Marek Kubiak and Przemysl(cid:2)aw Weso(cid:2)lek Evolutionary Algorithms for Real-World Instances of the Automatic Frequency Planning Problem in GSM Networks...................... 108 Francisco Luna, Enrique Alba, Antonio J. Nebro, and Salvador Pedraza A New Metaheuristic for the Vehicle Routing Problem with Split Demands ....................................................... 121 Enrique Mota, Vicente Campos, and A´ngel Corbera´n Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark. XII Table of Contents Generation of Tree Decompositions by Iterated Local Search .......... 130 Nysret Musliu Edge Assembly Crossover for the Capacitated Vehicle Routing Problem ........................................................ 142 Yuichi Nagata Tackling the Container Loading Problem: A Hybrid Approach Based on Integer Linear Programming and Genetic Algorithms .............. 154 Napole˜ao Nepomuceno, Pl´acido Pinheiro, and Andr´e L.V. Coelho A Population-Based Local Search for Solving a Bi-objective Vehicle Routing Problem ................................................ 166 Joseph M. Pasia, Karl F. Doerner, Richard F. Hartl, and Marc Reimann Combining LagrangianDecomposition with an Evolutionary Algorithm for the Knapsack Constrained Maximum Spanning Tree Problem ...... 176 Sandro Pirkwieser, Gu¨nther R. Raidl, and Jakob Puchinger Exact/Heuristic Hybrids Using rVNS and Hyperheuristics for Workforce Scheduling............................................. 188 Stephen Remde, Peter Cowling, Keshav Dahal, and Nic Colledge An Analysis of Problem Difficulty for a Class of Optimisation Heuristics....................................................... 198 Enda Ridge and Daniel Kudenko A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem ............................................... 210 Alok Singh and Anurag Singh Baghel A Hybrid Method for Solving Large-Scale Supply Chain Problems...... 219 Steffen Wolf and Peter Merz CrossoverOperators for the Car Sequencing Problem................. 229 Arnaud Zinflou, Caroline Gagn´e, and Marc Gravel Author Index.................................................. 241 Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.