Evolutionary Optimization

by Sarker, Ruhul Amin; Mohammadian, Masoud; Yao, Xin

• ISBN13: 9780792376545
• ISBN10: 0792376544
• Format: Hardcover
• Copyright: 2002-02-01
• Publisher: Kluwer Academic Pub

Summary

The use of evolutionary computation techniques has grown considerably over the past several years. Over this time, the use and applications of these techniques have been further enhanced resulting in a set of computational intelligence (also known as modern heuristics) tools that are particularly adept for solving complex optimization problems. Moreover, they are characteristically more robust than traditional methods based on formal logics or mathematical programming for many real world OR/MS problems. Hence, evolutionary computation techniques have dealt with complex optimization problems better than traditional optimization techniques although they can be applied to easy and simple problems where conventional techniques work well. Clearly there is a need for a volume that both reviews state-of-the-art evolutionary computation techniques, and surveys the most recent developments in their use for solving complex OR/MS problems. This volume on Evolutionary Optimization seeks to fill this need. Evolutionary Optimization is a volume of invited papers written by leading researchers in the field. All papers were peer reviewed by at least two recognized reviewers. The book covers the foundation as well as the practical side of evolutionary optimization.

Table of Contents

Preface	ix
Contributing Authors	xi
Part I Introduction
Conventional Optimization Techniques	3	(24)
Mark S. Hillier
Frederick S. Hillier
Classifying Optimization Models	4	(2)
Linear Programming	6	(3)
Goal Programming	9	(1)
Integer Programming	10	(3)
Nonlinear Programming	13	(9)
Simulation	22	(3)
Further Reading	25	(2)
Evolutionary Computation	27	(30)
Xin Yao
What Is Evolutionary Computation	27	(8)
A Brief Overview of Evolutionary Computation	35	(4)
Evolutionary Algorithm and Generate-and-Test Search Algorithm	39	(1)
Search Operators	40	(6)
Summary	46	(11)
Part II Single Objective Optimization
Evolutionary Algorithms and Constrained Optimization	57	(30)
Zbigniew Michalewicz
Martin Schmidt
Introduction	57	(1)
General considerations	58	(10)
Numerical optimization	68	(11)
Final Remarks	79	(8)
Constrained Evolutionary Optimization	87	(30)
Thomas Runarsson
Xin Yao
Introduction	87	(2)
The Penalty Function Method	89	(4)
Stochastic Ranking	93	(2)
Global Competitive Ranking	95	(2)
How Penalty Methods Work	97	(3)
Experimental Study	100	(6)
Conclusion	106	(11)
Appendix: Test Function Suite	109	(8)
Part III Multi-Objective Optimization
Evolutionary Multiobjective Optimization	117	(30)
Carlos A. Coello Coello
Introduction	118	(1)
Definitions	118	(1)
Historical Roots	119	(2)
A Quick Survey of EMOO Approaches	121	(7)
Current Research	128	(6)
Future Research Paths	134	(1)
Summary	135	(12)
MEA for Engineering Shape Design	147	(30)
Kalyanmoy Deb
Tushar Goel
Introduction	147	(2)
Multi-Objective Optimization and Pareto-Optimality	149	(2)
Elitist Non-dominated Sorting GA (NSGA-II)	151	(4)
Hybrid Approach	155	(4)
Optimal Shape Design	159	(3)
Simulation Results	162	(10)
Conclusion	172	(5)
Assessment Methodologies for MEAs	177	(22)
Ruhul Sarker
Carlos A. Coello Coello
Introduction	177	(1)
Assessment Methodologies	178	(8)
Discussion	186	(2)
Comparing Two Algorithms: An Example	188	(3)
Conclusions and Future Research Paths	191	(8)
Part IV Hybrid Algorithms
Hybrid Genetic Algorithms	199	(30)
Jeffrey A. Joines
Michael G. Kay
Introduction	199	(3)
Hybridizing GAs with Local Improvement Procedures	202	(16)
Adaptive Memory GA's	218	(7)
Summary	225	(4)
Combining choices of heuristics	229	(24)
Peter Ross
Emma Hart
Introduction	229	(3)
GAs and parameterised algorithms	232	(3)
Job Shop Scheduling	235	(6)
Scheduling chicken catching	241	(3)
Timetabling	244	(4)
Discussion and future directions	248	(5)
Nonlinear Constrained Optimization	253	(26)
Benjamin W. Wah
Yi-Xin Chen
Introduction	253	(4)
Previous Work	257	(6)
A General Framework to look for SPdn	263	(5)
Experimental Results	268	(5)
Conclusions	273	(6)
Part V Parameter Selection in EAs
Parameter Selection	279	(30)
Zbigniew Michalewicz
Agoston E. Eiben
Robert Hinterding
Introduction	279	(2)
Parameter tuning vs. parameter control	281	(3)
An example	284	(6)
Classification of Control Techniques	290	(4)
Various forms of control	294	(3)
Discussion	297	(12)
Part VI Application of EAs to Practical Problems
Design of Production Facilities	309	(20)
Alice E. Smith
Bryan A. Norman
Introduction	309	(3)
Design for Material Flow When the Number of I/O Points is Unconstrained	312	(3)
Design for Material Flow for a Single I/O Point	315	(3)
Considering Intradepartmental Flow	318	(3)
Material Handling System Design	321	(2)
Concluding Remarks	323	(6)
Virtual Population and Acceleration Techniques	329	(20)
Kit Po Wong
An Li
Introduction	329	(2)
Concept of Virtual Population	331	(1)
Solution Acceleration Techniques	332	(2)
Accelerated GA and Acceleration Schemes	334	(1)
Validation of Methods	335	(1)
Further Improvement: Refined Scheme (c)	336	(1)
The Load Flow Problem in Electrical Power Networks	337	(1)
Accelerated Constrained Genetic Algorithms for Load Flow Calculation	338	(1)
Klos-Kerner 11-Node System Studies	339	(4)
Conclusions	343	(6)
Part VII Applciation of EAs to Theoretical Problems
Methods for the analysis of EAs on pseudo-boolean functions	349	(22)
Ingo Wegener
Introduction	349	(2)
Optimization of Pseudo-boolean functions	351	(1)
Performance measures	352	(1)
Selected functions	353	(2)
Tail inequalities	355	(2)
The coupon collector's theorem	357	(1)
The gambler's ruin problem	358	(1)
Upper bounds by artificial fitness levels	359	(3)
Lower bounds by artificial fitness levels	362	(1)
Potential functions	363	(2)
Investigations of typical runs	365	(6)
A GA Heuristic For Finite Horizon POMDPs	371	(28)
Alex Z.-Z. Lin
James C. Bean
Chelsea C. White III
Introduction	371	(1)
Partially Observed MDP	372	(4)
Basics of Genetic Algorithms	376	(4)
Proposed Genetic Algorithm Heuristic	380	(7)
Heuristic Performance Measures	387	(3)
Numerical Results	390	(1)
Summary	391	(8)
Appendix	397	(2)
Finding Good k-Tree Subgraphs	399	(16)
Elham Ghashghai
Ronald L. Rardin
Introduction	399	(1)
k-Trees	400	(1)
Algorithm Paradigm and Terminology	401	(2)
Genetic Algorithm Implementation	403	(3)
Computational Results	406	(6)
Concluding Remarks and Further Research	412	(3)
Index	415