Lecture Notes in Computer Science 1993 EditedbyG.Goos,J.HartmanisandJ.vanLeeuwen 3 Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo Eckart Zitzler Kalyanmoy Deb Lothar Thiele Carlos A. Coello Coello David Corne (Eds.) Evolutionary Multi-Criterion Optimization First International Conference, EMO 2001 Zurich, Switzerland, March 7-9, 2001 Proceedings 1 3 VolumeEditors EckartZitzler LotharThiele SwissFederalInstituteofTechnology,DepartmentofElectricalEngineering ComputerEngineeringandNetworksLaboratory ETHZentrum,Gloriastrasse35,8092Zurich,Switzerland E-mail:{zitzler/thiele}@tik.ee.ethz.ch KalyanmoyDeb IndianInstituteofTechnology,DepartmentofMechanicalEngineering KanpurGeneticAlgorithmsLaboratory,Kanpur,UP208016,India E-mail:[email protected] CarlosArtemioCoelloCoello CINVESTAV-IPN,ElectricalEngineeringDepartment,ComputerScienceSection Av.InstitutoPolitecnicoNacionalNo.2508 Col.SanPedroZacatenco,MexicoCity07300,Mexico E-mail:[email protected] DavidCorne UniversityofReading,DepartmentofComputerScience P.O.Box225,Whiteknights,ReadingRG66AY,UK E-mail:[email protected] Cataloging-in-PublicationDataappliedfor DieDeutscheBibliothek-CIP-Einheitsaufnahme Evolutionarymulti-criterionoptimization:firstinternationalconference; proceedings/EMO2001,Zurich,Switzerland,March7-9,2001. EckartZitzler...(ed.).-Berlin;Heidelberg;NewYork;Barcelona; HongKong;London;Milan;Paris;Singapore;Tokyo:Springer,2001 (Lecturenotesincomputerscience;Vol.1993) ISBN3-540-41745-1 CRSubjectClassification(1998):F.2,G.1.6,G.1.2,I.2.8 ISSN0302-9743 ISBN3-540-41745-1Springer-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-VerlagBerlinHeidelberg2001 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTP-Berlin,StefanSossna Printedonacid-freepaper SPIN:10782086 06/3142 543210 V Preface Multi-criterion optimization deals with multiple, often conflicting objectives which naturally arise in a real-world scenario. The (cid:12)eld of multiple criteria de- cision making (MCDM) is well established, investigated by many researchers and scientists, and widely applied in practice. Unlike in single-objective opti- mization, a multi-criterion optimization problem gives rise to a number of op- timal solutions, known as Pareto-optimal solutions, of which none can be said to be better than the others with respect to all objectives. Thus, one of the primarygoalsinmulti-criterionoptimizationisto(cid:12)ndortoapproximatetheset of Pareto-optimal solutions. Since evolutionary algorithms work with a popula- tion of solutions, they have been used in multi-criterion optimization for more than a decade. To date, there exist a number of evolutionary approaches and applicationcasestudies,demonstratingtheusefulnessande(cid:14)ciencyofevolutio- nary multi-criterion optimization (EMO). Due to the growing interest in EMO, the general chairs envisaged organizing this (cid:12)rst-ever international conference coveringallaspectsoftheintersectionofevolutionarycomputationandclassical MCDM.Theaimwastopromoteandshareresearchactivitiesinthispromising (cid:12)eld. The (cid:12)rst international conference on evolutionary multi-criterion optimiza- tion (EMO 2001) was held in Zu¨rich at the Swiss Federal Institute of Tech- nology (ETH) on March 7{9, 2001. This event included two keynote speeches, one delivered by Ralph E. Steuer on current state-of-the-art methodology and the other delivered by Ian C. Parmee on real-world applications of evolutionary techniques.Furthermore,twoextendedtutorialswerepresented,oneonclassical multiplecriteriadecisionmakingmethodologiesbyKaisaMiettinenandanother one on evolutionary algorithms by Carlos A. Coello Coello. Inresponsetothecallforpapers,87papersfrom27countriesweresubmitted, each of which was independently reviewed by at least three members of the programcommittee.Thisvolumepresentsaselectionof45oftherefereedpapers, together with contributions based on the invited talks and tutorials. We would like to express our appreciation to the keynote speakers who ac- cepted our invitation, to the tutorial organizers, to all authors who submitted papers to EMO 2001, and to Marco Laumanns and Monica Fricker for their invaluable help in organizing the conference. March 2001 Eckart Zitzler, Kalyanmoy Deb, Lothar Thiele, Carlos A. Coello Coello, and David Corne Organization EMO2001tookplacefromMarch7thto9th,2001attheSwissFederalInstitute ofTechnology(ETH)Zu¨rich,Switzerland,andwasorganizedincooperationwith ACM/SIGART,IEEENeuralNetworkCouncil,andtheInternationalSocietyfor Genetic and Evolutionary Computation (ISGEC). General Chairs Kalyanmoy Deb IIT Kanpur, India Lothar Thiele ETH Zu¨rich, Switzerland Eckart Zitzler ETH Zu¨rich, Switzerland Executive Program Committee Hojjat Adeli Ohio State University, USA Carlos A. Coello Coello CINVESTAV-IPN, Mexico David Corne University of Reading, UK Carlos Fonseca Universidade do Algarve, Portugal David E. Goldberg University of Illinois at Urbana-Champaign, USA Je(cid:11)rey Horn Northern Michigan University, USA Sourav Kundu Mastek Limited, Japan Gary B. Lamont Air Force Institute of Technology, USA Shigeru Obayashi Tohoku University, Japan Ian C. Parmee University of Plymouth, UK Carlo Poloni University of Trieste, Italy Gu¨nter Rudolph University of Dortmund, Germany J. David Scha(cid:11)er Phillips Research, USA Hans-Paul Schwefel University of Dortmund, Germany El-ghazali Talbi Universit(cid:19)edesSciencesetTechnologiesdeLille, France Program Committee Enrique Baeyens University de Valladolid, Spain Tapan P. Bagchi IIT Kanpur, India Peter J. Bentley University College London, UK Ju¨rgen Branke University of Karlsruhe, Germany Nirupam Chakraborti IIT Kharagpur, India William A. Crossley Purdue University, USA VIII Organization Dragan Cvetkovic Soliton Associates Ltd., Canada Nicole Drechsler University of Freiburg, Germany Rolf Drechsler Siemens AG, Germany Peter Fleming University of She(cid:14)eld, UK Kary Fra¨mling Helsinki University of Technology, Finland Antonio Gaspar-Cunha University of Minho, Portugal Prabhat Hajela Rensselaer Polytechnic Institute, USA Thomas Hanne Institute for Techno- and Economathematics, Germany Alberto Herreros University of Valladolid, Spain Evan J. Hughes Cran(cid:12)eld University, UK Hisao Ishibuchi Osaka Prefecture University, Japan Andrzej Jaszkiewicz Poznan University of Technology, Poland Joshua D. Knowles University of Reading, UK Petros Koumoutsakos ETH Zu¨rich, Switzerland Rajeev Kumar IIT Kharagpur, India Bill Langdon University College London, UK Marco Laumanns ETH Zu¨rich, Switzerland Mark Sh. Levin Ben-Gurion University, Israel Daniel H. Loughlin North Carolina State University, USA Filippo Menczer University of Iowa, USA Martin Middendorf University of Karlsruhe, Germany Tadahiko Murata Ashikaga Institute of Technology, Japan Pedro Oliveira Universidade do Minho, Portugal Andrzej Osyczka Cracow University of Technology, Poland S. Ranji Ranjithan North Carolina State University, USA Katya Rodriguez-Vazquez IIMAS-UNAM, Mexico Carlos Mariano Romero IMTA, Mexico Ralf Salomon University of Zu¨rich, Switzerland Marc Schoenauer Ecole Polytechnique, France Pratyush Sen University of Newcastle, UK Hisashi Tamaki Kobe University, Japan Kay Chen Tan National University, Singapore Dirk Thierens Utrecht University, The Netherlands Mark Thompson She(cid:14)eld Hallam University, UK Thanh Binh To Institute of Automation and Communication Magdeburg, Germany Marco Tomassini University of Lausanne, Switzerland David A. Van Veldhuizen US Air Force, USA Table of Contents Tutorials Some Methods for Nonlinear Multi-objective Optimization :::::::::::::: 1 Kaisa Miettinen A Short Tutorial on Evolutionary Multiobjective Optimization::::::::::: 21 Carlos A. Coello Coello Invited Talks An Overview in Graphs of Multiple Objective Programming::::::::::::: 41 Ralph E. Steuer Poor-De(cid:12)nition, Uncertainty and Human Factors { Satisfying Multiple Objectives in Real-World Decision-Making Environments ::::::::::::::: 52 I. C. Parmee Algorithm Improvements Controlled Elitist Non-dominated Sorting Genetic Algorithms for Better Convergence::::::::::::::::::::::::::::::::::::::::::::::::::::::: 67 Kalyanmoy Deb, Tushar Goel Speci(cid:12)cation of Genetic Search Directions in Cellular Multi-objective Genetic Algorithms :::::::::::::::::::::::::::::::::::::::::::::::: 82 Tadahiko Murata, Hisao Ishibuchi, Mitsuo Gen Adapting Weighted Aggregation for Multiobjective Evolution Strategies :: 96 Yaochu Jin, Tatsuya Okabe, Bernhard Sendho(cid:11) Incrementing Multi-objective Evolutionary Algorithms: Performance Studies and Comparisons ::::::::::::::::::::::::::::::::::::::::::: 111 K. C. Tan, T. H. Lee, E. F. Khor A Micro-Genetic Algorithm for Multiobjective Optimization::::::::::::: 126 Carlos A. Coello Coello, Gregorio Toscano Pulido Evolutionary Algorithms for Multicriteria Optimization with Selecting a Representative Subset of Pareto Optimal Solutions ::::::::::::::::::::: 141 Andrzej Osyczka, Stanislaw Krenich Multi-objective Optimisation Based on Relation Favour::::::::::::::::: 154 Nicole Drechsler, Rolf Drechsler, Bernd Becker X Table of Contents Performance Assessment and Comparison ComparisonofEvolutionaryandDeterministicMultiobjectiveAlgorithms for Dose Optimization in Brachytherapy :::::::::::::::::::::::::::::: 167 Natasa Milickovic, Michael Lahanas, Dimos Baltas, Nikolaos Zamboglou On The E(cid:11)ects of Archiving, Elitism, and Density Based Selection in Evolutionary Multi-objective Optimization :::::::::::::::::::::::::::: 181 Marco Laumanns, Eckart Zitzler, Lothar Thiele Global Multiobjective Optimization with Evolutionary Algorithms: Selection Mechanisms and Mutation Control :::::::::::::::::::::::::: 197 Thomas Hanne Inferential Performance Assessment of Stochastic Optimisers and the Attainment Function ::::::::::::::::::::::::::::::::::::::::::::::: 213 Viviane Grunert da Fonseca, Carlos M. Fonseca, Andreia O. Hall A Statistical Comparison of Multiobjective Evolutionary Algorithms Including the MOMGA-II::::::::::::::::::::::::::::::::::::::::::: 226 Jesse B. Zydallis, David A. Van Veldhuizen, Gary B. Lamont Performance of Multiple Objective Evolutionary Algorithms on Distribution System Design Problem { Computational Experiment ::::::: 241 Andrzej Jaszkiewicz, Maciej Hapke, Pawel Kominek Constraint Handling and Problem Decomposition An Infeasibility Objective for Use in Constrained Pareto Optimization:::: 256 Jonathan Wright, Heather Loosemore Reducing Local Optima in Single-Objective Problems by Multi-objectivization ::::::::::::::::::::::::::::::::::::::::::::::: 269 Joshua D. Knowles, Richard A. Watson, David W. Corne Constrained Test Problems for Multi-objective Evolutionary Optimization 284 Kalyanmoy Deb, Amrit Pratap, T. Meyarivan Constraint Method-Based Evolutionary Algorithm (CMEA) for Multiobjective Optimization::::::::::::::::::::::::::::::::::::::::: 299 S. Ranji Ranjithan, S. Kishan Chetan, Harish K. Dakshina Uncertainty and Noise Pareto-Front Exploration with Uncertain Objectives:::::::::::::::::::: 314 Ju¨rgen Teich Evolutionary Multi-objective Ranking with Uncertainty and Noise ::::::: 329 Evan J. Hughes