Tao / Zhang / Laili Configurable Intelligent Optimization Algorithm

Design and Practice in Manufacturing
2015
ISBN: 978-3-319-08840-2
Verlag: Springer Nature Switzerland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 364 Seiten

Reihe: Springer Series in Advanced Manufacturing

Presenting the concept and design and implementation of configurable intelligent optimization algorithms in manufacturing systems, this book provides a new configuration method to optimize manufacturing processes. It provides a comprehensive elaboration of basic intelligent optimization algorithms, and demonstrates how their improvement, hybridization and parallelization can be applied to manufacturing. Furthermore, various applications of these intelligent optimization algorithms are exemplified in detail, chapter by chapter. The intelligent optimization algorithm is not just a single algorithm; instead it is a general advanced optimization mechanism which is highly scalable with robustness and randomness. Therefore, this book demonstrates the flexibility of these algorithms, as well as their robustness and reusability in order to solve mass complicated problems in manufacturing. Since the genetic algorithm was presented decades ago, a large number of intelligent optimization algorithms and their improvements have been developed. However, little work has been done to extend their applications and verify their competence in solving complicated problems in manufacturing.This book will provide an invaluable resource to students, researchers, consultants and industry professionals interested in engineering optimization. It will also be particularly useful to three groups of readers: algorithm beginners, optimization engineers and senior algorithm designers. It offers a detailed description of intelligent optimization algorithms to algorithm beginners; recommends new configurable design methods for optimization engineers, and provides future trends and challenges of the new configuration mechanism to senior algorithm designers.

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.

Autoren/Hrsg.

Tao, Fei

Zhang, Lin

Laili, Yuanjun

Inhaltsverzeichnis

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