Configurable Intelligent Optimization Algorithm (eBook)

Dr. Fei Tao is currently a Professor at School of Automation Science and Electrical Engineering in Beihang University (Beijing University of Aeronautics and Astronautics). He obtained his Ph.D from Wuhan University of Technology in 2008. From Sep. 2007 to Mar. 2009, he worked as a research scholar and postdoctoral researcher at University of Michigan-Dearborn, USA. His research interests include service-oriented manufacturing such as cloud manufacturing and manufacturing grid, manufacturing service management and optimization, intelligent optimization theory and algorithm. He is the author of 2 monographs and over 60 journal and conference articles of these subjects. Dr. Tao was nominated and elected to be a research affiliate of CIRP (The International Academy for Production Engineering) in 2009. He is currently the editor of International Journal of Service and Computing-oriented Manufacturing (IJSCOM), and the editorial board member of International Journal of Modeling, Simulation and Scientific Computing and Journal of Industrial Engineering.Dr. Lin Zhang is a Professor of Beihang University. He received the B.S. degree in 1986 from the Department of Computer and System Science at Nankai University, China. He received the M.S. degree and the Ph.D. degree in 1989 and 1992 from the Department of Automation at Tsinghua University, China. He served as the director of CIMS Office, China National 863 Program, from 1997 to 2001. From 2002 to 2005 he worked at the US Naval Postgraduate School as a senior research associate of the US National Research Council. Currently, he serves as a member of the Board of Directors & Executive Committee of the Society for Modeling & Simulation International (SCS), the vice president of Chinese Association for System Simulation (CASS) and the Federation of Asian Simulation Societies (ASIASIM), an IEEE senior member and associate Editor-in-Chief and associate editors of 5 peer-reviewed international journals. He authored and co-authored 160 papers, 5 books and chapters. His research interests include cloud manufacturing; service computing and high performance computing; knowledge engineering; modeling, simulation and optimization for complex systems.Yuanjun Laili received the MS Degree from School of Automation Science and Electrical Engineering, Beihang University, Beijing, China, in 2012. She is studying for a Ph.D. Degree in School of Automation Science and Electrical Engineering at Beihang University. Her main research interests include intelligent optimization, mathematical programming, parallel computing and algorithms in the field of resource management in manufacturing and distributed & parallel simulation.

Acknowledgements 6
Contents 7
Part IIntroduction and Overview 14
1 Brief History and Overview of Intelligent Optimization Algorithms 16
1.1…Introduction 16
1.2…Brief History of Intelligent Optimization Algorithms 18
1.3…Classification of Intelligent Algorithms 21
1.4…Brief Review of Typical Intelligent Optimization Algorithms 25
1.4.1 Review of Evolutionary Learning Algorithms 25
1.4.1.1 Genetic Algorithm 26
1.4.1.2 Immune Algorithm 28
1.4.2 Review of Neighborhood Search Algorithms 29
1.4.2.1 Simulated Annealing Algorithm 30
1.4.2.2 Iterative Local Search 31
1.4.3 Review of Swarm Intelligence Algorithm 33
1.4.3.1 Ant Colony Optimization 33
1.4.3.2 Particle Swarm Optimization 34
1.5…The Classification of Current Studies on Intelligent Optimization Algorithm 36
1.5.1 Algorithm Innovation 36
1.5.2 Algorithm Improvement 37
1.5.3 Algorithm Hybridization 38
1.5.4 Algorithm Parallelization 39
1.5.5 Algorithm Application 39
1.6…Development Trends 41
1.6.1 Intellectualization 41
1.6.2 Service-Orientation 42
1.6.3 Application-Oriented 42
1.6.4 User-Centric 42
1.7…Summary 43
References 44
2 Recent Advances of Intelligent Optimization Algorithm in Manufacturing 47
2.1…Introduction 47
2.2…Classification of Optimization Problems in Manufacturing 49
2.2.1 Numerical Function Optimization 50
2.2.2 Parameter Optimization 50
2.2.3 Detection and Classification 51
2.2.4 Combinatorial Scheduling 52
2.2.5 Multi-disciplinary Optimization 53
2.2.6 Summary of the Five Types of Optimization Problems in Manufacturing 54
2.3…Challenges for Addressing Optimization Problems in Manufacturing 56
2.3.1 Balance of Multi-objectives 56
2.3.2 Handling of Multi-constraints 58
2.3.3 Extraction of Priori Knowledge 59
2.3.4 Modeling of Uncertainty and Dynamics 60
2.3.5 Transformation of Qualitative and Quantitative Features 62
2.3.6 Simplification of Large-Scale Solution Space 63
2.3.7 Jumping Out of Local Convergence 64
2.4…An Overview of Optimization Methods in Manufacturing 64
2.4.1 Empirical-Based Method 65
2.4.2 Prediction-Based Method 66
2.4.3 Simulation-Based Method 67
2.4.4 Model-Based Method 67
2.4.5 Tool-Based Method 68
2.4.6 Advanced-Computing-Technology-Based Method 68
2.4.7 Summary of Studies on Solving Methods 69
2.5…Intelligent Optimization Algorithms for Optimization Problems in Manufacturing 70
2.6…Challenges of Applying Intelligent Optimization Algorithms in Manufacturing 76
2.6.1 Problem Modeling 76
2.6.2 Algorithm Selection 77
2.6.3 Encoding Scheming 78
2.6.4 Operator Designing 79
2.7…Future Approaches for Manufacturing Optimization 79
2.8…Future Requirements and Trends of Intelligent Optimization Algorithm in Manufacturing 80
2.8.1 Integration 80
2.8.2 Configuration 81
2.8.3 Parallelization 82
2.8.4 Executing as Service 83
2.9…Summary 84
References 86
Part IIDesign and Implementation 93
3 Dynamic Configuration of Intelligent Optimization Algorithms 95
3.1…Concept and Mainframe of DC-IOA 95
3.1.1 Mainframe of DC-IOA 96
3.1.2 Problem Specification and Construction of Algorithm Library in DC-IOA 97
3.2…Case Study 102
3.2.1 Configuration System for DC-IOA 102
3.2.2 Case Study of DC-IOA 105
3.2.3 Performance Analysis 107
3.2.4 Comparison with Traditional Optimal Process 114
3.3…Summary 115
References 116
4 Improvement and Hybridization of Intelligent Optimization Algorithm 118
4.1…Introduction 118
4.2…Classification of Improvement 120
4.2.1 Improvement in Initial Scheme 120
4.2.2 Improvement in Coding Scheme 121
4.2.3 Improvement in Operator 123
4.2.4 Improvement in Evolutionary Strategy 124
4.3…Classification of Hybridization 125
4.3.1 Hybridization for Exploration 126
4.3.2 Hybridization for Exploitation 127
4.3.3 Hybridization for Adaptation 128
4.4…Improvement and Hybridization Based on DC-IA 129
4.5…Summary 135
References 135
5 Parallelization of Intelligent Optimization Algorithm 138
5.1…Introduction 138
5.2…Parallel Implementation Ways for Intelligent Optimization Algorithm 142
5.2.1 Parallel Implementation Based on Multi-core Processor 142
5.2.2 Parallel Implementation Based on Computer Cluster 143
5.2.3 Parallel Implementation Based on GPU 143
5.2.4 Parallel Implementation Based on FPGA 144
5.3…Implementation of Typical Parallel Topologies for Intelligent Optimization Algorithm 145
5.3.1 Master-Slave Topology 145
5.3.2 Ring Topology 147
5.3.3 Mesh Topology 149
5.3.4 Full Mesh Topology 151
5.3.5 Random Topology 151
5.4…New Configuration in Parallel Intelligent Optimization Algorithm 153
5.4.1 Topology Configuration in Parallelization Based on MPI 155
5.4.2 Operation Configuration in Parallelization Based on MPI 157
5.4.3 Module Configuration in Parallelization Based on FPGA 158
5.5…Summary 163
References 163
Part IIIApplication of Improved IntelligentOptimization Algorithms 166
6 GA-BHTR for Partner Selection Problem 167
6.1…Introduction 167
6.2…Description of Partner Selection Problem in Virtual Enterprise 170
6.2.1 Description and Motivation 170
6.2.2 Formulation of the Partner Selection Problem (PSP) 173
6.3…GA-BHTR for PSP 175
6.3.1 Review of Standard GA 175
6.3.2 Framewrok of GA-BHTR 176
6.3.3 Graph Generation for Representing the Precedence Relationship Among PSP 178
6.3.4 Distribute Individuals into Multiple Communities 182
6.3.5 Intersection and Mutation in GA-BHTR 185
6.3.6 Maintain Data Using the Binary Heap 187
6.3.7 The Catastrophe Operation 189
6.4…Simulation and Experiment 190
6.4.1 Effectiveness of the Proposed Transitive Reduction Algorithm 191
6.4.2 Effectiveness of Multiple Communities 192
6.4.3 Effectiveness of Multiple Communities While Considering the DISMC Problem 193
6.4.4 Effectiveness of the Catastrophe Operation 194
6.4.5 Efficiency of Using the Binary Heap 194
6.5…Summary 197
References 197
7 CLPS-GA for Energy-Aware Cloud Service Scheduling 200
7.1…Introduction 200
7.2…Related Works 202
7.3…Modeling of Energy-Aware Cloud Service Scheduling in Cloud Manufacturing 204
7.3.1 General Definition 205
7.3.2 Objective Functions and Optimization Model 207
7.3.3 Multi-Objective Optimization Model for the Resource Scheduling Problem 209
7.4…Cloud Service Scheduling with CLPS-GA 211
7.4.1 Pareto Solutions for MOO Problems 211
7.4.1.1 Domination and Non-Inferiority 211
7.4.1.2 Rank, Front and Pareto Solutions 211
7.4.2 Traditional Genetic Algorithms for MOO Problems 213
7.4.3 CLPS-GA for Addressing MOO Problems 216
7.5…Experimental Evaluation 220
7.5.1 Data and Implementation 220
7.5.2 Experiments and Results 222
7.5.3 Comparison Between TPCO and MPCO 223
7.5.4 Improvements Due to the Case Library 226
7.5.5 Comparison Between CLPS-GA and Other Enhanced GAs 227
7.6…Summary 230
References 231
Part IVApplication of Hybrid IntelligentOptimization Algorithms 234
8 SFB-ACO for Submicron VLSI Routing Optimization with Timing Constraints 235
8.1…Introduction 235
8.2…Preliminary 239
8.2.1 Terminology in Steiner Tree 239
8.2.2 Elmore Delay 240
8.2.3 Problem Formulation 241
8.3…SFB-ACO for Addressing MSTRO Problem 245
8.3.1 ACO for Path Planning with Two Endpoints 245
8.3.2 Procedure for Constructing Steiner Tree Using SFB-ACO 247
8.3.3 Constraint-Oriented Feedback in SFB-ACO 249
8.4…Implementation and Results 251
8.4.1 Parameters Selection 251
8.4.2 Improvement of Synergy 252
8.4.3 Effectiveness of Constraint-Oriented Feedback 257
8.5…Summary 262
References 262
9 A Hybrid RCO for Dual Scheduling of Cloud Service and Computing Resource in Private Cloud 265
9.1…Introduction 265
9.2…Related Works 268
9.3…Motivation Example 269
9.4…Problem Description 271
9.4.1 The Modeling of DS-CSCR in Private Cloud 271
9.4.2 Problem Formulation of DS-CSCR in Private Cloud 275
9.5…Ranking Chaos Algorithm (RCO) for DS-CSCR in Private Cloud 278
9.5.1 Initialization 279
9.5.2 Ranking Selection Operator 279
9.5.3 Individual Chaos Operator 281
9.5.4 Dynamic Heuristic Operator 283
9.5.5 The Complexity of the Proposed Algorithm 285
9.6…Experiments and Discussions 285
9.6.1 Performance of DS-CSCR Compared with Traditional Two-Level Scheduling 288
9.6.2 Searching Capability of RCO for Solving DS-CSCR 288
9.6.3 Time Consumption and Stability of RCO for Solving DS-CSCR 291
9.7…Summary 293
References 294
Part VApplication of Parallel IntelligentOptimization Algorithms 296
10 Computing Resource Allocation with PEADGA 297
10.1…Introduction 297
10.2…Related Works 300
10.3…Motivation Example of OACR 302
10.4…Description and Formulation of OACR 303
10.4.1 The Structure of OACR 304
10.4.2 The Characteristics of CRs in CMfg 306
10.4.3 The Formulation of the OACR Problem 307
10.5…NIA for Addressing OACR 314
10.5.1 Review of GA, ACO and IA 314
10.5.2 The Configuration OfNIA for the OACR Problem 317
10.5.3 The Time Complexity of the Proposed Algorithms 320
10.6…Configuration and Parallelization of NIA 322
10.7…Experiments and Discussions 324
10.7.1 The Design of the Heuristic Information in the Intelligent Algorithms 326
10.7.2 The Comparison of GA, ACO, IA and NDIA for Addressing OACR 328
10.7.3 The Performance of PNIA 332
10.8…Summary 334
References 335
11 Job Shop Scheduling with FPGA-Based F4SA 338
11.1…Introduction 338
11.2…Problem Description of Job Shop Scheduling 340
11.3…Design and Configuration of SA-Based on FPGA 340
11.3.1 FPGA-Based F4SA Design for JSSP 340
11.3.2 FPGA-Based Operators of F4SA 344
11.3.3 Operator Configuration Based on FPGA 349
11.4…Experiments and Discussions 349
11.5…Summary 351
References 351
Part VIFuture Works of Configurable IntelligentOptimization Algorithm 353
12 Future Trends and Challenges 354
12.1…Related Works for Configuration of Intelligent Optimization Algorithm 354
12.2…Dynamic Configuration for Other Algorithms 356
12.3…Dynamic Configuration on FPGA 359
12.4…The Challenges on the Development of Dynamic Configuration 361
12.5…Summary 362
References 363