Differential Evolution

by Onwubolu, Godfrey C.; Davendra, Donald

• ISBN13: 9783540921509
• ISBN10: 3540921508
• Edition: CD
• Format: Hardcover
• Copyright: 2009-02-01
• Publisher: Springer Verlag

Summary

This is the first book devoted entirely to Differential Evolution (DE) for global permutative-based combinatorial optimization.Since its original development, DE has mainly been applied to solving problems characterized by continuous parameters. This means that only a subset of real-world problems could be solved by the original, classical DE algorithm. This book presents in detail the various permutative-based combinatorial DE formulations by their initiators in an easy-to-follow manner, through extensive illustrations and computer code. It is a valuable resource for professionals and students interested in DE in order to have full potentials of DE at their disposal as a proven optimizer. All source programs in C and Mathematica programming languages are downloadable from the website of Springer.

Table of Contents

Motivation for Differential Evolution for Permutative-Based Combinatorial Problems	p. 1
Introduction	p. 1
Continuous Space Optimization DE Problems	p. 2
Permutative-Based Combinatorial Optimization DE Problem	p. 2
Suitability of Differential Evolution as a Combinatorial Optimizer	p. 3
Canonical Differential Evolution for Continuous Optimization Problems	p. 4
Differential Evolution for Permutative-Based Combinatorial Optimization Problems	p. 9
Conclusions	p. 10
References	p. 11
Differential Evolution for Permutation-Based Combinatorial Problems	p. 13
Introduction	p. 13
Wide-Sense Combinatorial Optimization	p. 13
Strict-Sense Combinatorial Optimization	p. 14
Feasible Solutions versus "Repairing" Infeasible Solutions for Strict-Sense Combinatorial Optimization	p. 14
Combinatorial Problems	p. 14
Knapsack Problem	p. 15
Travelling Salesman Problem (TSP)	p. 15
Automated Drilling Location and Hit Sequencing	p. 20
Dynamic Pick and Place (DPP) Model of Placement Sequence and Magazine Assignment	p. 22
Vehicle Routing Problem	p. 25
Facility Location Problem	p. 25
Permutation-Based Combinatorial Approaches	p. 26
The Permutation Matrix Approach	p. 26
Adjacency Matrix Approach	p. 27
Relative Position Indexing	p. 27
Forward/Backward Transformation Approach	p. 28
Smallest Position Value Approach	p. 29
Discrete/Binary Approach	p. 30
Discrete Set Handling Approach	p. 31
Anatomy of Some Approaches	p. 31
Conclusions	p. 32
References	p. 33
Forward Backward Transformation	p. 35
Introduction	p. 35
Differential Evolution	p. 36
Tuning Parameters	p. 38
Discrete Differential Evolution	p. 38
Permutative Population	p. 39
Forward Transformation	p. 39
Backward Transformation	p. 40
Recursive Mutation	p. 40
Enhanced Differential Evolution	p. 41
Repairment	p. 42
Improvement Strategies	p. 45
Local Search	p. 46
Worked Example	p. 48
Flow Shop Scheduling	p. 59
Flow Shop Scheduling Example	p. 60
Experimentation for Discrete Differential Evolution Algorithm	p. 62
Experimentation for Enhanced Differential Evolution Algorithm	p. 65
Quadratic Assignment Problem	p. 68
Quadratic Assignment Problem Example	p. 69
Experimentation for Irregular QAP	p. 71
Experimentation for Regular QAP	p. 72
Traveling Salesman Problem	p. 73
Traveling Salesman Problem Example	p. 74
Experimentation on Symmetric TSP	p. 76
Experimentation on Asymmetric TSP	p. 76
Analysis and Conclusion	p. 77
References	p. 78
Relative Position Indexing Approach	p. 81
Introduction	p. 81
Two Simple Examples	p. 84
Pythagorean Triples	p. 84
Maximal Determinants	p. 86
Partitioning a Set	p. 88
Set Partitioning via Relative Position Indexing	p. 90
Set Partitioning via Knapsack Approach	p. 93
Discussion of the Two Methods	p. 95
Minimal Covering of a Set by Subsets	p. 95
An Ad Hoc Approach to Subset Covering	p. 96
Subset Covering via Knapsack Formulation	p. 98
An Assignment Problem	p. 101
Relative Position Indexing for Permutations	p. 104
Representing and Using Permutations as Shuffles	p. 106
Another Shuffle Method	p. 109
Hybridizing Differential Evolution for the Assignment Problem	p. 112
Future Directions	p. 118
References	p. 119
Smallest Position Value Approach	p. 121
Introduction	p. 121
Differential Evolution Algorithm	p. 123
Solution Representation	p. 125
An Example Instance of the GTSP	p. 126
Complete Computational Procedure of DE	p. 127
Insertion Methods	p. 129
Hybridization with Local Search	p. 131
Computational Results	p. 132
Conclusions	p. 136
References	p. 137
Discrete/Binary Approach	p. 139
Introduction	p. 139
Discrete Differential Evolution Algorithm	p. 141
Solution Representation	p. 144
Complete Computational Procedure of DDE	p. 145
NEH Heuristic	p. 146
Insertion Methods	p. 147
Destruction and Construction Procedure	p. 149
PTL Crossover Operator	p. 151
Insert Mutation Operator	p. 151
DDE Update Operations	p. 152
Hybridization with Local Search	p. 153
Computational Results	p. 154
Solution Quality	p. 155
Computation Time	p. 157
Comparison to Other Algorithms	p. 157
Conclusions	p. 160
References	p. 160
Discrete Set Handling	p. 163
Introduction	p. 163
Permutative Optimization	p. 164
Travelling Salesman Problem	p. 164
Flow Shop Scheduling Problem	p. 165
2 Opt Local Search	p. 165
Discrete Set Handling and Its Application	p. 166
Introduction and Principle	p. 166
DSH Applications on Standard Evolutionary Algorithms	p. 167
DSH Applications on Class of Genetic Programming Techniques	p. 169
Differential Evolution in Mathematica Code	p. 174
DE Flow Shop Scheduling	p. 182
DE Traveling Salesman Problem	p. 183
DE Example	p. 184
Initialization	p. 185
DSH Conversion	p. 185
Fitness Evaluation	p. 186
DE Application	p. 186
Experimentation	p. 189
Flow Shop Scheduling Tuning	p. 190
Traveling Salesman Problem Tuning	p. 194
Flow Shop Scheduling Results	p. 197
Traveling Salesman Problem Results	p. 201
Conclusion	p. 203
References	p. 203
Smallest Position Value Approach	p. 207
Clusters for the Instance 11EIL51	p. 207
Pseudo Code for Distance Calculation	p. 207
Distance (ij, dij) Information for the Instance 11EIL51	p. 208
Author Index	p. 213
Table of Contents provided by Ingram. All Rights Reserved.