Genetic Algorithms and Engineering Design

by Gen, Mitsuo; Cheng, Runwei

• ISBN13: 9780471127413
• ISBN10: 0471127418
• Edition: 1st
• Format: Hardcover
• Copyright: 1997-01-21
• Publisher: Wiley-Interscience

Summary

The last few years have seen important advances in the use of genetic algorithms to address challenging optimization problems in industrial engineering. Genetic Algorithms and Engineering Design is the only book to cover the most recent technologies and their application to manufacturing, presenting a comprehensive and fully up-to-date treatment of genetic algorithms in industrial engineering and operations research. Beginning with a tutorial on genetic algorithm fundamentals and their use in solving constrained and combinatorial optimization problems, the book applies these techniques to problems in specific areas-sequencing, scheduling and production plans, transportation and vehicle routing, facility layout, location-allocation, and more. Each topic features a clearly written problem description, mathematical model, and summary of conventional heuristic algorithms. All algorithms are explained in intuitive, rather than highly-technical, language and are reinforced with illustrative figures and numerical examples. Written by two internationally acknowledged experts in the field, Genetic Algorithms and Engineering Design features original material on the foundation and application of genetic algorithms, and also standardizes the terms and symbols used in other sources-making this complex subject truly accessible to the beginner as well as to the more advanced reader. Ideal for both self-study and classroom use, this self-contained reference provides indispensable state-of-the-art guidance to professionals and students working in industrial engineering, management science, operations research, computer science, and artificial intelligence. The only comprehensive, state-of-the-art treatment available on the use of genetic algorithms in industrial engineering and operations research . . . Written by internationally recognized experts in the field of genetic algorithms and artificial intelligence, Genetic Algorithms and Engineering Design provides total coverage of current technologies and their application to manufacturing systems. Incorporating original material on the foundation and application of genetic algorithms, this unique resource also standardizes the terms and symbols used in other sources-making this complex subject truly accessible to students as well as experienced professionals. Designed for clarity and ease of use, this self-contained reference: Provides a comprehensive survey of selection strategies, penalty techniques, and genetic operators used for constrained and combinatorial optimization problems Shows how to use genetic algorithms to make production schedules, solve facility/location problems, make transportation/vehicle routing plans, enhance system reliability, and much more Contains detailed numerical examples, plus more than 160 auxiliary figures to make solution procedures transparent and understandable

Author Biography

MITSUO GEN, PhD, is a professor in the Department of Industrial and Systems Engineering at the Ashikaga Institute of Technology in Japan. An associate editor of the Engineering Design and Automation Journal and Journal of Engineering Valuation & Cost Analysis, he is also a member of the international editorial advisory board of Computers & Industrial Engineering. He is the author of two other books, Linear Programming Using Turbo C and Goal Programming Using Turbo C. RUNWEI CHENG, PhD, is a visiting associate professor at the Ashikaga Institute of Technology in Japan and also an associate professor at the Institute of Systems Engineering at Northeast University in China. Both authors are internationally known experts in the application of genetic algorithms and artificial intelligence to the field of manufacturing systems.

Table of Contents

1 Foundations of Genetic Algorithms	1	(41)
1.1 Introduction	1	(6)
1.1.1 General Structure of Genetic Algorithms	1	(3)
1.1.2 Exploitation and Exploration	4	(1)
1.1.3 Population-Based Search	5	(1)
1.1.4 Meta-heuristics	6	(1)
1.1.5 Major Advantages	6	(1)
1.1.6 Genetic Algorithm Vocabulary	7	(1)
1.2 Examples with Simple Genetic Algorithms	7	(9)
1.2.1 Optimization Problem	7	(8)
1.2.2 Word-Matching Problem	15	(1)
1.3 Encoding Problem	16	(4)
1.4 Selection	20	(11)
1.4.1 Sampling Space	21	(1)
1.4.2 Sampling Mechanism	22	(3)
1.4.3 Selection Probability	25	(4)
1.4.4 Selective Pressures	29	(2)
1.5 Hybrid Genetic Algorithms	31	(3)
1.5.1 Lamarckian Evolution	32	(1)
1.5.2 Memetic Algorithms	33	(1)
1.6 Important Events in the Genetic Algorithm Community	34	(8)
1.6.1 Books on Genetic Algorithms	34	(1)
1.6.2 Conferences and Workshops	35	(4)
1.6.3 Journals and Special Issues on Genetic Algorithms	39	(1)
1.6.4 Public-Accessible Internet Service for Genetic Algorithm Information	40	(2)
2 Constrained Optimization Problems	42	(55)
2.1 Unconstrained Optimization	42	(7)
2.1.1 Ackley's Function	43	(1)
2.1.2 Genetic Algorithm Approach for Minimization of Achley's Function	44	(5)
2.2 Nonlinear Programming	49	(19)
2.2.1 Handling Constraints	49	(2)
2.2.2 Penalty Function	51	(8)
2.2.3 Genetic Operators	59	(5)
2.2.4 Numerical Examples	64	(4)
2.3 Stochastic Optimization	68	(8)
2.3.1 Mathematical Model	68	(1)
2.3.2 Monte Carlo Simulation	69	(1)
2.3.3 Evolution Program for Stochastic Optimization Problems	70	(6)
2.4 Nonlinear Goal Programming	76	(7)
2.4.1 Formulation of Nonlinear Goal Programming	77	(1)
2.4.2 Genetic Algorithms for Nonlinear Goal Programming	78	(2)
2.4.3 Numerical Examples	80	(3)
2.5 Interval Programming	83	(14)
2.5.1 Introduction	84	(6)
2.5.2 Genetic Algorithm	90	(5)
2.5.3 Numerical Example	95	(2)
3 Combinatorial Optimization Problems	97	(36)
3.1 Introduction	97	(1)
3.2 Knapsack Problem	98	(5)
3.2.1 Binary Representation Approach	99	(2)
3.2.2 Order Representation Approach	101	(1)
3.2.3 Variable-Length Representation Approach	101	(2)
3.3 Quadratic Assignment Problem	103	(4)
3.3.1 Encoding	104	(1)
3.3.2 Genetic Operators	105	(2)
3.4 Minimum Spanning Tree Problem	107	(11)
3.4.1 Problem Description	108	(1)
3.4.2 Tree Encodings	109	(4)
3.4.3 Genetic Algorithm Approach	113	(5)
3.5 Traveling Salesman Problem	118	(10)
3.5.1 Representation	118	(1)
3.5.2 Crossover Operators	119	(6)
3.5.3 Mutation Operators	125	(3)
3.6 Film-Copy Deliverer Problem	128	(5)
3.6.1 Representation	128	(2)
3.6.2 Genetic Operators	130	(3)
4 Reliability Optimization Problems	133	(40)
4.1 Introduction	133	(6)
4.1.1 Combinatorial Aspects of System Reliability	134	(2)
4.1.2 Reliability Optimization Models with Several Failure Modes	136	(2)
4.1.3 Reliability Optimization Models with Alternative Design	138	(1)
4.2 Simple Genetic Algorithm for Reliability Optimization	139	(5)
4.2.1 Problem Formulation	139	(2)
4.2.2 Genetic Algorithm and Numerical Example	141	(3)
4.3 Reliability Optimization with Redundant Unit and Alternative Design	144	(7)
4.3.1 Problem Formulation	144	(1)
4.3.2 Genetic Algorithm and Numerical Example	145	(6)
4.4 Reliability Optimization with Redundant Mixing Components	151	(5)
4.4.1 Problem Formulation	151	(2)
4.4.2 Genetic Algorithm and Numerical Example	153	(3)
4.5 Reliability Optimization with Fuzzy Goal and Fuzzy Constraints	156	(7)
4.5.1 Problem Formulation	156	(3)
4.5.2 Genetic Algorithm and Numerical Example	159	(4)
4.6 Reliability Optimization with Interval Coefficients	163	(10)
4.6.1 Problem Formulation	163	(3)
4.6.2 Genetic Algorithm	166	(3)
4.6.3 Numerical Example	169	(4)
5 Flow-Shop Sequencing Problems	173	(17)
5.1 Introduction	173	(1)
5.2 Two-Machine Flow-Shop Problem	174	(2)
5.3 Heuristics for General m-Machine Problems	176	(3)
5.3.1 Palmer's Heuristic Algorithm	176	(1)
5.3.2 Gupta's Heuristic Algorithm	176	(1)
5.3.3 CDS Heuristic Algorithm	177	(1)
5.3.4 RA Heuristic Algorithm	178	(1)
5.3.5 NEH Heuristic Algorithm	178	(1)
5.4 Gen. Tsujimura, and Kubota's Approach	179	(3)
5.4.1 Representation	179	(1)
5.4.2 Evaluation Function	179	(1)
5.4.3 Crossover and Mutation	179	(1)
5.4.4 Examples	180	(2)
5.5 Reeve's Approach	182	(4)
5.5.1 Initial Population	182	(1)
5.5.2 Genetic Operators	182	(1)
5.5.3 Selection	183	(2)
5.5.4 Numerical Example	185	(1)
5.6 Ischibuchi, Yamamoto, Murata, and Tanaka's Approach	186	(4)
5.6.1 Fuzzy Flow-Shop Problem	186	(1)
5.6.2 Hybrid Genetic Algorithm	187	(2)
5.6.3 Numerical Example	189	(1)
6 Job-Shop Scheduling Problems	190	(44)
6.1 Introduction	190	(1)
6.2 Classical Job-Shop Model	191	(6)
6.2.1 IP Model	193	(2)
6.2.2 LP Model	195	(1)
6.2.3 Graph Model	196	(1)
6.3 Conventional Heuristics	197	(5)
6.3.1 Priority Dispatching Heuristics	197	(2)
6.3.2 Randomized Dispatching Heuristic	199	(2)
6.3.3 Shifting Bottleneck Heuristic	201	(1)
6.4 Genetic Algorithms for Job-Shop Scheduling Problems	202	(21)
6.4.1 Representation	202	(12)
6.4.2 Discussion	214	(3)
6.4.3 Hybrid Genetic Search	217	(6)
6.5 Gen, Tsujimura, and Kubota's Approach	223	(3)
6.6 Cheng, Gen, and Tsujimura's Approach	226	(2)
6.7 Falkenauer and Bouffouix's Approach	228	(2)
6.8 Dorndorf and Pesch's Approach	230	(1)
6.9 Computational Results and Discussion	231	(3)
7 Machine Scheduling Problems	234	(28)
7.1 Introduction	234	(10)
7.1.1 Single-Machine Sequencing Problem	235	(4)
7.1.2 Earliness and Tardiness Scheduling Problems	239	(3)
7.1.3 Parallel Machine Scheduling Problem	242	(2)
7.2 Cleveland and Smith's Approach	244	(3)
7.2.1 Genetic Operators	245	(1)
7.2.2 Selection	246	(1)
7.3 Gupta, Gupta, and Kumar's Approach	247	(2)
7.3.1 Evaluation Function	247	(1)
7.3.2 Replacement Strategy	247	(1)
7.3.3 Convergence Policy	248	(1)
7.3.4 Overall Procedure	248	(1)
7.4 Lee and Kim's Approach	249	(4)
7.4.1 Representation	250	(1)
7.4.2 Parallel Subpopulations	251	(1)
7.4.3 Crossover and Mutation	252	(1)
7.4.4 Evaluation and Selection	252	(1)
7.4.5 Parallel Genetic Algorithm	253	(1)
7.5 Cheng and Gen's Approach	253	(9)
7.5.1 Representation and Initialization	254	(1)
7.5.2 Crossover	255	(1)
7.5.3 Mutation	255	(3)
7.5.4 Determining the Best Due Date	258	(1)
7.5.5 Evaluation and Selection	259	(1)
7.5.6 Numerical Example	260	(2)
8 Transportation Problems	262	(30)
8.1 Introduction	262	(1)
8.2 Linear Transportation Problem	263	(8)
8.2.1 Formulation of LTP	263	(2)
8.2.2 Representation	265	(1)
8.2.3 Genetic Operation	266	(5)
8.3 Bicriteria Linear Transportation Problem	271	(7)
8.3.1 Formulation of BLTP	271	(1)
8.3.2 Evaluation	271	(2)
8.3.3 Overall Procedure	273	(3)
8.3.4 Numerical Examples	276	(2)
8.4 Bicriteria Solid Transportation Problem	278	(5)
8.4.1 Formulation of BSTP	278	(1)
8.4.2 Initialization	279	(1)
8.4.3 Genetic Operation	279	(2)
8.4.4 Numerical Examples	281	(2)
8.5 Fuzzy Multicriteria Solid Transportation Problem	283	(9)
8.5.1 Problem Formulation	283	(1)
8.5.2 Genetic Algorithm Approach	284	(5)
8.5.3 Numerical Example	289	(3)
9 Facility Layout Design Problems	292	(38)
9.1 Introduction	292	(1)
9.2 Machine Layout Problem	293	(2)
9.3 Single-Row Machine Layout Problem	295	(4)
9.3.1 Mathematical Model	295	(1)
9.3.2 Genetic Algorithm for Single-Row Machine Layout Problem	296	(3)
9.4 Multiple-Row Machine Layout Problem	299	(11)
9.4.1 Mathematical Model	299	(2)
9.4.2 Representation	301	(3)
9.4.3 Initialization	304	(2)
9.4.4 Crossover	306	(1)
9.4.5 Mutation	307	(2)
9.4.6 Evaluation Function	309	(1)
9.4.7 Example	310	(1)
9.5 Fuzzy Facility Layout Problem	310	(20)
9.5.1 Facility Layout Problem	312	(1)
9.5.2 Fuzzy Interflow	312	(2)
9.5.3 Representation	314	(1)
9.5.4 Initialization	314	(2)
9.5.5 Crossover	316	(1)
9.5.6 Mutation	317	(2)
9.5.7 Constructing a Layout from a Chromosome	319	(4)
9.5.8 Evaluation and Selection	323	(1)
9.5.9 Numerical Example	323	(7)
10 Selected Topics in Engineering Design	330	(50)
10.1 Resource-Constrained Project Scheduling Problems	330	(11)
10.1.1 Problem Statement	331	(1)
10.1.2 Hybrid Genetic Algorithms	332	(6)
10.1.3 Examples	338	(3)
10.2 Fuzzy Vehicle Routing and Scheduling Problem	341	(18)
10.2.1 Problem Formulation	342	(5)
10.2.2 Related Genetic Algorithm Studies	347	(1)
10.2.3 Hybrid Genetic Algorithm	348	(9)
10.2.4 Experimental Results	357	(2)
10.3 Location-Allocation Problem	359	(7)
10.3.1 Location-Allocation Model	360	(1)
10.3.2 Hybrid Evolutionary Method	361	(4)
10.3.3 Numerical Example	365	(1)
10.4 Obstacle Location-Allocation Problem	366	(7)
10.4.1 Obstacle Location-Allocation Model	367	(3)
10.4.2 Feasibility of Location	370	(1)
10.4.3 Shortest Path of Avoiding Obstacles	370	(1)
10.4.4 Hybrid Evolutionary Method	370	(1)
10.4.5 Case Study	371	(2)
10.5 Production Plan Problem	373	(7)
10.5.1 Formulation of Production Plan Problem	374	(1)
10.5.2 Evolution Program for Production Plan Problem	375	(3)
10.5.3 Example	378	(2)
Bibliography	380	(27)
Index	407