Lecture Notes in Computer Science 2632 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Tokyo Carlos M. Fonseca Peter J. Fleming Eckart Zitzler Kalyanmoy Deb Lothar Thiele (Eds.) Evolutionary Multi-Criterion Optimization Second International Conference, EMO 2003 Faro, Portugal, April 8-11, 2003 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditors CarlosM.Fonseca UniversityoftheAlgarve,FacultyofSciencesandTechnology CentreforIntelligentSystems CampusdeGambelas,8005-139Faro,Portugal E-mail:[email protected] PeterJ.Fleming UniversityofSheffield,DepartmentofAutomaticControlandSystemsEngineering MappinStreet,SheffieldS13JD,UK E-mail:P.Fleming@sheffield.ac.uk EckartZitzler LotharThiele SwissFederalInstituteofTechnology,DepartmentofElectricalEngineering ComputerEngineeringandNetworksLaboratory Gloriastraße35,8092Zu¨rich,Switzerland E-mail:{zitzler,thiele}@tik.ee.ethz.ch KalyanmoyDeb IndianInstituteofTechnology,DepartmentofMechanicalEngineering KanpurGeneticAlgorithmsLaboratory Kanpur,UP208016,India E-mail:[email protected] Cataloging-in-PublicationDataappliedfor AcatalogrecordforthisbookisavailablefromtheLibraryofCongress. BibliographicinformationpublishedbyDieDeutscheBibliothek. DieDeutscheBibliothekliststhispublicationintheDeutscheNationalbibliografie; detailedbibliographicdataisavailableintheInternetat<http://dnb.ddb.de>. CRSubjectClassification(1998):F.2,G.1.6,G.1.2,I.2.8 ISSN0302-9743 ISBN3-540-01869-7Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagBerlinHeidelbergNewYork amemberofBertelsmannSpringerScience+BusinessMediaGmbH http://www.springer.de ©Springer-VerlagBerlinHeidelberg2003 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTP-BerlinGmbH Printedonacid-freepaper SPIN:10925867 06/3142 543210 Preface The 2nd International Conference on Evolutionary Multi-Criterion Optimiza- tion (EMO 2003) was held on April 8–11, 2003, at the University of the Algarve in Faro, Portugal. This was the second international conference dedicated enti- relytothisimportanttopic,followingtheverysuccessfulEMO2001conference, whichwasheldinZu¨rich,Switzerland,inMarch2001.EMO2003wasco-located withtheIFACInternationalConferenceonIntelligentControlSystemsandSig- nal Processing (ICONS 2003), exposing EMO to a wider audience of scientists and engineers. TheEMO2003scientificprogramincludedtwokeynoteaddresses,onegiven byDavidSchafferonoptimizationandmachinelearninginindustry,andanother delivered by Pekka Korhonen on multiple-criteria decision making. In addition, three tutorials were presented, one on multicriterion decision analysis by Va- lerie Belton, another on multiobjective evolutionary algorithms by Kalyanmoy Deb, and a third on multiple objective metaheuristics by Andrzej Jaszkiewicz. The President of the Portuguese Innovation Agency, Prof. Joa˜o Silveira Lobo, and the President of the Portuguese Foundation for Science and Technology, Prof. Fernando Ramoa Ribeiro, attended the opening ceremony and the closing ceremony, respectively. Inresponsetothecallforpapers,100full-lengthpapersweresubmittedfrom 27 countries. Fifty-six papers were accepted for presentation at the conference after thorough reviewing by members of the program committee and they are contained in this volume. April 2003 Carlos M. Fonseca, Peter J. Fleming, Eckart Zitzler, Kalyanmoy Deb, and Lothar Thiele Organization EMO 2003 was organized by CSI (Centre for Intelligent Systems, University of the Algarve, Portugal) with the support of EvoNet (European Network of Excellence in Evolutionary Computing). General Chairs Carlos M. Fonseca Universidade do Algarve, Portugal Peter J. Fleming University of Sheffield, UK Eckart Zitzler ETH Zu¨rich, Switzerland Program Committee Enrique Baeyens University of Valladolid, Spain Peter Bentley University College London, UK Ju¨rgen Branke University of Karlsruhe, Germany Nirupam Chakraborti IIT, Kharagpur, India Carlos Coello Coello CINVESTAV-IPN, Mexico David Corne University of Reading, UK William Crossley Purdue University, US Dragan Cvetkovic Soliton Associates, Canada Kalyanmoy Deb IIT, Kanpur, India Rolf Drechsler University of Bremen, Germany Kary Fra¨mling Helsinki University of Technology, Finland Anto´nio Gaspar-Cunha Universidade do Minho, Portugal Tushar Goel John F. Welch Technology Centre, India Thomas Hanne Fraunhofer Institute for Industrial Mathematics, Germany Alberto Herreros University of Valladolid, Spain Jeffrey Horn Northern Michigan University, US Evan J. Hughes Cranfield University, UK Hisao Ishibuchi Osaka Prefecture University, Japan Yaochu Jin Honda R&D Europe, Germany Joshua Knowles IRIDIA, Belgium Petros Koumoutsakos ETH Zu¨rich, Switzerland Rajeev Kumar IIT, Kharagpur, India Gary B. Lamont Air Force Institute of Technology, US Marco Laumanns ETH Zu¨rich, Switzerland Daniel Loughlin MCNC Environmental Modeling Center, US Carlos Mariano Romero IMTA, Mexico VIII Organization Martin Middendorf University of Leipzig, Germany Tadahiko Murata Kansai University, Japan Shigeru Obayashi Tohoku University, Japan Pedro Oliveira Universidade do Minho, Portugal Geoffrey T. Parks Cambridge University, UK Ian C. Parmee University of the West of England, UK Amrit Pratap California Institute of Technology, US Ranji Ranjithan North Carolina State University, US Katya Rodriguez-Vazquez IIMAS-UNAM, Mexico Gu¨nter Rudolph Parsytec AG, Germany J. David Schaffer Philips Research, US Marc Schoenauer INRIA, France Hans-Paul Schwefel Universit¨at Dortmund, Germany El-ghazali Talbi LIFL, France Kay Chen Tan National University of Singapore, Singapore Lothar Thiele ETH Zu¨rich, Switzerland Dirk Thierens Utrecht University, The Netherlands Thanh Binh To Universita¨t-Otto-von-Guericke-Magdeburg, Germany David Van Veldhuizen Wright-Patterson AFB, US James F. Whidborne Kings College London, UK Local Organizing Committee Carlos M. Fonseca, CSI Pedro M. Ferreira, CSI Anto´nio E. Ruano, CSI Daniel Castro, CSI Maria G. Ruano, CSI Susy Rodrigues, FEUA Fernando Lobo, CSI EMO Steering Committee David Corne University of Reading, UK Kalyanmoy Deb IIT Kanpur, India Peter J. Fleming University of Sheffield, UK Carlos M. Fonseca Universidade do Algarve, Portugal J. David Schaffer Philips Research, US Lothar Thiele ETH Zu¨rich, Switzerland Eckart Zitzler ETH Zu¨rich, Switzerland Organization IX Acknowledgements Invited Speakers We thank the keynote and tutorial speakers for their talks given at the confe- rence. Keynote Speakers Pekka Korhonen HelsinkiSchoolofEconomicsandBusinessAd- ministration, Finland J. David Schaffer Philips Research, US Tutorial Speakers Valerie Belton University of Strathclyde, UK Kalyanmoy Deb IIT, Kanpur, India Andrzej Jaszkiewicz Poznan University of Technology, Poland Local Sponsors Support by the following organizations and companies is gratefully acknowled- ged. Universidade do Algarve – Reitoria – Faculdade de Ciˆencias e Tecnologia – Faculdade de Economia – Departamento de Engenharia Electro´nica e Inform´atica Fundac¸˜ao para a Ciˆencia e a Tecnologia Fundac¸˜ao Calouste Gulbenkian Fundac¸˜ao Oriente Fundac¸˜ao Luso-Americana para o Desenvolvimento Cˆamara Municipal de Faro Cˆamara Municipal de Tavira Governo Civil de Faro PROAlgarve Turismo do Algarve A´guas de Monchique Banco Portuguˆes do Atlˆantico Epaminondas Illy Caf´es Parmalat S.A. Refrige SINFIC Staples Office Center Table of Contents Objective Handling and Problem Decomposition The Maximin Fitness Function; Multi-objective City and Regional Planning ................................................ 1 Richard Balling Conflict, Harmony, and Independence: Relationships in Evolutionary Multi-criterion Optimisation............................ 16 Robin C. Purshouse, Peter J. Fleming Is Fitness Inheritance Useful for Real-World Applications? ............. 31 Els Ducheyne, Bernard De Baets, Robert De Wulf Use of a Genetic Heritage for Solving the Assignment Problem with Two Objectives .............................................. 43 Xavier Gandibleux, Hiroyuki Morita, Naoki Katoh Fuzzy Optimality and Evolutionary Multiobjective Optimization........ 58 M. Farina, P. Amato IS-PAES: A Constraint-Handling Technique Based on Multiobjective Optimization Concepts ............................................ 73 Arturo Herna´ndez Aguirre, Salvador Botello Rionda, Giovanni Liza´rraga Liza´rraga, Carlos A. Coello Coello A Population and Interval Constraint Propagation Algorithm .......... 88 Vincent Barichard, Jin-Kao Hao Multi-objective Binary Search Optimisation ......................... 102 Evan J. Hughes Covering Pareto Sets by Multilevel Evolutionary Subdivision Techniques . 118 Oliver Schu¨tze, Sanaz Mostaghim, Michael Dellnitz, Ju¨rgen Teich An Adaptive Divide-and-Conquer Methodology for Evolutionary Multi-criterion Optimisation........................................ 133 Robin C. Purshouse, Peter J. Fleming Multi-level Multi-objective Genetic Algorithm Using Entropy to Preserve Diversity................................................. 148 S. Gunawan, A. Farhang-Mehr, S. Azarm Solving Hierarchical Optimization Problems Using MOEAs............. 162 Christian Haubelt, Sanaz Mostaghim, Ju¨rgen Teich, Ambrish Tyagi XII Table of Contents Multiobjective Meta Level Optimization of a Load Balancing Evolutionary Algorithm............................................ 177 David J. Caswell, Gary B. Lamont Algorithm Improvements Schemata-Driven Multi-objective Optimization ....................... 192 Skander Kort A Real-Coded Predator-Prey Genetic Algorithm for Multiobjective Optimization........................................ 207 Xiaodong Li Towards a Quick Computation of Well-Spread Pareto-Optimal Solutions . 222 Kalyanmoy Deb, Manikanth Mohan, Shikhar Mishra Trade-Off between Performance and Robustness: An Evolutionary Multiobjective Approach .......................................... 237 Yaochu Jin, Bernhard Sendhoff Online Adaptation The Micro Genetic Algorithm 2: Towards Online Adaptation in Evolutionary Multiobjective Optimization............................ 252 Gregorio Toscano Pulido, Carlos A. Coello Coello Self-Adaptation for Multi-objective Evolutionary Algorithms ........... 267 Dirk Bu¨che, Sibylle Mu¨ller, Petros Koumoutsakos MOPED: A Multi-objective Parzen-Based Estimation of Distribution Algorithm for Continuous Problems ................................. 282 Mario Costa, Edmondo Minisci Test Problem Construction Instance Generators and Test Suites for the Multiobjective Quadratic Assignment Problem ..................................... 295 Joshua D. Knowles, David W. Corne Dynamic Multiobjective Optimization Problems: Test Cases, Approximation, and Applications ................................... 311 M. Farina, Kalyanmoy Deb, P. Amato No Free Lunch and Free Leftovers Theorems for Multiobjective Optimisation Problems ............................................ 327 David W. Corne, Joshua D. Knowles