Muutke küpsiste eelistusi

Metaheuristics 1st ed. 2016 [Kõva köide]

Edited by
  • Formaat: Hardback, 489 pages, kõrgus x laius: 235x155 mm, kaal: 8808 g, 69 Illustrations, color; 112 Illustrations, black and white; XVI, 489 p. 181 illus., 69 illus. in color., 1 Hardback
  • Ilmumisaeg: 02-Jan-2017
  • Kirjastus: Springer International Publishing AG
  • ISBN-10: 3319454013
  • ISBN-13: 9783319454016
Teised raamatud teemal:
  • Kõva köide
  • Hind: 141,35 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 166,29 €
  • Säästad 15%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
Metaheuristics 1st ed. 2016Suurem pilt
  • Formaat: Hardback, 489 pages, kõrgus x laius: 235x155 mm, kaal: 8808 g, 69 Illustrations, color; 112 Illustrations, black and white; XVI, 489 p. 181 illus., 69 illus. in color., 1 Hardback
  • Ilmumisaeg: 02-Jan-2017
  • Kirjastus: Springer International Publishing AG
  • ISBN-10: 3319454013
  • ISBN-13: 9783319454016
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9783319454016.html
Märksõnad:
Metaheuristics exhibit desirable properties like simplicity, easy parallelizability, and ready applicability to different types of optimization problems. After a comprehensive introduction to the field, the contributed chapters in this book include explanations of the main metaheuristics techniques, including simulated annealing, tabu search, evolutionary algorithms, artificial ants, and particle swarms, followed by chapters that demonstrate their applications to problems such as multiobjective optimization, logistics, vehicle routing, and air traffic management.The authors are leading researchers in this domain, with considerable teaching and applications experience, and the book will be of value to industrial practitioners, graduate students, and research academics.

Introduction.- Simulated Annealing.- Tabu Search.- Search in Variable Neighborhoods.- The GRASP Search Algorithm.- Evolutionary Algorithms.- Artificial Ants.- Particle Swarms.- Other Metaheuristics.- Other Social Insect Algorithms.- Extending Evolutionary Algorithms for Multiobjective Optimization.- Extending Evolutionary Algorithms for Optimization Under Constraints.- Modeling and Comparison Methods.- Hybrid Metaheuristics for Optimizing Logistics.- Metaheuristics for Vehicle Routing Problems.- Applications in Air Traffic Management.

Arvustused

The books chapters are written by prominent researchers in the metaheuristics field. They include adequate references, and many contain annotated bibliographies. This book will be useful for academicians, problem solvers in industry, practitioners, students, and researchers. (S. V. Nagaraj, Computing Reviews, January, 2018)









1 Introduction 1(18)
Patrick Siarry
1.1 "Hard" Optimization
2(2)
1.2 Source of the Effectiveness of Metaheuristics
4(1)
1.2.1 Trapping of a "Classical" Iterative Algorithm in a Local Minimum
4(1)
1.2.2 Capability of Metaheuristics to Extract Themselves from a Local Minimum
5(1)
1.3 Principles of the Most Widely Used Metaheuristics
5(9)
1.3.1 Simulated Annealing
5(2)
1.3.2 The Tabu Search Method
7(2)
1.3.3 Genetic Algorithms and Evolutionary Algorithms
9(3)
1.3.4 Ant Colony Algorithms
12(1)
1.3.5 Other Metaheuristics
13(1)
1.4 Extensions of Metaheuristics
14(1)
1.4.1 Adaptation for Problems with Continuous Variables
14(1)
1.4.2 Multiobjective Optimization
14(1)
1.4.3 Hybrid Methods
14(1)
1.4.4 Multimodal Optimization
15(1)
1.4.5 Parallelization
15(1)
1.5 Place of Metaheuristics in a Classification of Optimization Methods
15(1)
1.6 Applications of Metaheuristics
16(1)
1.7 An Open Question: The Choice of a Metaheuristic
17(1)
1.8 Outline of the Book
17(1)
References
18(1)
2 Simulated Annealing 19(32)
Patrick Siarry
2.1 Introduction
19(1)
2.2 Presentation of the Method
20(2)
2.2.1 Analogy Between an Optimization Problem and Some Physical Phenomena
20(1)
2.2.2 Real Annealing and Simulated Annealing
21(1)
2.2.3 Simulated Annealing Algorithm
21(1)
2.3 Theoretical Approaches
22(5)
2.3.1 Theoretical Convergence of Simulated Annealing
23(1)
2.3.2 Configuration Space
24(1)
2.3.3 Rules of Acceptance
25(1)
2.3.4 Program of Annealing
26(1)
2.4 Parallelization of the Simulated Annealing Algorithm
27(3)
2.5 Some Applications
30(8)
2.5.1 Benchmark Problems of Combinatorial Optimization
30(2)
2.5.2 Layout of Electronic Circuits
32(3)
2.5.3 Search for an Equivalent Schema in Electronics
35(2)
2.5.4 Practical Applications in Various Fields
37(1)
2.6 Advantages and Disadvantages of the Method
38(1)
2.7 Simple Practical Suggestions for Beginners
39(1)
2.8 Modeling of Simulated Annealing Through the Markov Chain Formalism
40(7)
2.8.1 Asymptotic Behavior of Homogeneous Markov Chains
41(1)
2.8.2 Choice of Annealing Parameters
42(5)
2.8.3 Modeling of the Simulated Annealing Algorithm by Inhomogeneous Markov Chains
47(1)
2.9 Annotated Bibliography
47(1)
References
48(3)
3 Tabu Search 51(26)
Eric Taillard
3.1 Introduction
51(2)
3.2 The Quadratic Assignment Problem
53(1)
3.2.1 Example
54(1)
3.3 Basic Tabu Search
54(9)
3.3.1 Neighborhood
55(1)
3.3.2 Moves and Neighborhoods
56(2)
3.3.3 Neighborhood Evaluation
58(2)
3.3.4 Neighborhood Limitation: Candidate List
60(1)
3.3.5 Neighborhood Extension: Ejection Chains
61(2)
3.4 Short-Term Memory
63(9)
3.4.1 Hash Table
63(1)
3.4.2 Tabu List
64(1)
3.4.3 Duration of Tabu Conditions
65(6)
3.4.4 Aspiration Conditions
71(1)
3.5 Long-Term Memory
72(3)
3.5.1 Frequency-Based Memory
72(2)
3.5.2 Forced Moves
74(1)
3.6 Convergence of Tabu Search
75(1)
3.7 Conclusion
75(1)
3.8 Annotated Bibliography
76(1)
References
76(1)
4 Variable Neighborhood Search 77(22)
Gilles Caporossi
Pierre Hansen
Nenad Mladenovic
4.1 Introduction
77(1)
4.2 Description of the Algorithm
78(7)
4.2.1 Local Search
78(3)
4.2.2 Diversification of the Search
81(2)
4.2.3 The Variable Neighborhood Search
83(2)
4.3 Illustration and Extensions
85(11)
4.3.1 Finding Extremal Graphs with VNS
86(7)
4.3.2 Improving the k-Means Algorithm
93(2)
4.3.3 Using VNS for Continuous Optimization Problems
95(1)
4.4 Conclusion
96(1)
4.5 Annotated Bibliography
96(1)
References
97(2)
5 A Two-Phase Iterative Search Procedure: The GRASP Method 99(16)
Michel Vasquez
Mirsad Buljubasic
5.1 Introduction
99(1)
5.2 General Principle Behind the Method
99(2)
5.3 Set Covering Problem
101(1)
5.4 An Initial Algorithm
102(3)
5.4.1 Constructive Phase
102(2)
5.4.2 Improvement Phase
104(1)
5.5 Benchmark
105(1)
5.6 Experiments with greedy(alpha)+descent
105(2)
5.7 Local Tabu Search
107(2)
5.7.1 The Search Space
107(1)
5.7.2 Evaluation of a Configuration
107(1)
5.7.3 Managing the Tabu List
108(1)
5.7.4 Neighborhood
108(1)
5.7.5 The Tabu Algorithm
109(1)
5.8 Experiments with greedy(alpha)+descent+Tabu
109(2)
5.9 Experiments with greedy (1) +Tabu
111(1)
5.10 Conclusion
112(1)
5.11 Annotated Bibliography
113(1)
References
113(2)
6 Evolutionary Algorithms 115(64)
Alain Petrowski
Sana Ben Hamida
6.1 From Genetics to Engineering
115(2)
6.1.1 Genetic Algorithms or Evolutionary Algorithms?
116(1)
6.2 The Generic Evolutionary Algorithm
117(3)
6.2.1 Selection Operators
117(1)
6.2.2 Variation Operators
118(1)
6.2.3 The Generational Loop
119(1)
6.2.4 Solving a Simple Problem
119(1)
6.3 Selection Operators
120(13)
6.3.1 Selection Pressure
121(1)
6.3.2 Genetic Drift
122(1)
6.3.3 Proportional Selection
123(6)
6.3.4 Tournament Selection
129(1)
6.3.5 Truncation Selection
130(1)
6.3.6 Environmental Selection
130(2)
6.3.7 Fitness Function
132(1)
6.4 Variation Operators and Representation
133(4)
6.4.1 Generalities About the Variation Operators
133(2)
6.4.2 Crossover
135(1)
6.4.3 Mutation
136(1)
6.5 Binary Representation
137(3)
6.5.1 Crossover
138(1)
6.5.2 Mutation
139(1)
6.6 Real Representation
140(9)
6.6.1 Crossover
141(4)
6.6.2 Mutation
145(4)
6.7 Some Discrete Representations for Permutation Problems
149(5)
6.7.1 Ordinal Representation
150(1)
6.7.2 Path or Sequence Representation
151(3)
6.8 Syntax Tree-Based Representation for Genetic Programming
154(8)
6.8.1 Initializing the Population
156(1)
6.8.2 Crossover
156(2)
6.8.3 Mutations
158(1)
6.8.4 Application to Symbolic Regression
159(3)
6.9 The Particular Case of Genetic Algorithms
162(1)
6.10 The Covariance Matrix Adaptation Evolution Strategy
163(10)
6.10.1 Presentation of Method
163(5)
6.10.2 The CMA-ES Algorithm
168(2)
6.10.3 Some Simulation Results
170(3)
6.11 Conclusion
173(1)
6.12 Glossary
174(1)
6.13 Annotated Bibliography
175(1)
References
175(4)
7 Artificial Ants 179(24)
Nicolas Monmarche
7.1 Introduction
179(1)
7.2 The Collective Intelligence of Ants
180(3)
7.2.1 Some Striking Facts
180(1)
7.2.2 The Chemical Communication of Ants
181(2)
7.3 Modeling the Behavior of Ants
183(2)
7.3.1 Defining an Artificial Ant
183(1)
7.3.2 Ants on a Graph
183(2)
7.4 Combinatorial Optimization with Ants
185(14)
7.4.1 The Traveling Salesman Problem
185(2)
7.4.2 The ACO Metaheuristic
187(9)
7.4.3 Convergence of ACO Algorithm
196(1)
7.4.4 Comparison with Evolutionary Algorithms
197(2)
7.5 Conclusion
199(1)
7.6 Annotated Bibliography
200(1)
References
201(2)
8 Particle Swarms 203(26)
Maurice Clerc
8.1 Unity Is Strength
203(1)
8.2 Ingredients of PSO
204(6)
8.2.1 Objects
204(1)
8.2.2 Relations
205(1)
8.2.3 Mechanisms
206(4)
8.3 Some Versions of PSO
210(5)
8.3.1
1998. A Basic Version
210(2)
8.3.2 Two Improved "Standard" Versions
212(3)
8.4 Applications and Variants
215(1)
8.5 Going Further
216(1)
8.6 Appendix
217(8)
8.6.1 A Simple Example
217(1)
8.6.2 SPSO 2011 with Distance-Fitness Correlation
217(2)
8.6.3 Comparison of Three Simple Variants
219(1)
8.6.4 About Some Traps
219(4)
8.6.5 On the Importance of the Generators of Numbers
223(2)
References
225(4)
9 Some Other Metaheuristics 229(34)
Ilhem Boussaid
9.1 Introduction
229(1)
9.2 Artificial Immune Systems
230(7)
9.2.1 Negative-Selection-Based Algorithms
232(1)
9.2.2 Clonal Selection-Based Algorithms
233(1)
9.2.3 Artificial Immune Networks
234(1)
9.2.4 Danger-Theory-Inspired Algorithms
235(1)
9.2.5 Dendritic Cell Algorithms
236(1)
9.3 Differential Evolution
237(6)
9.3.1 Mutation Schemes
239(1)
9.3.2 Crossover
240(3)
9.4 Bacterial Foraging Optimization Algorithm
243(5)
9.4.1 Chemotaxis
244(1)
9.4.2 Swarming
245(1)
9.4.3 Reproduction
246(1)
9.4.4 Elimination and Dispersal
246(2)
9.5 Biogeography-Based Optimization (BBO)
248(5)
9.6 Cultural Algorithms
253(2)
9.7 Coevolutionary Algorithms
255(1)
9.8 Conclusion
256(1)
9.9 Annotated Bibliography
257(1)
References
257(6)
10 Nature Inspires New Algorithms 263(24)
Sebastien Aupetit
Mohamed Slimane
10.1 Bees
264(6)
10.1.1 Honeybee Foraging
264(2)
10.1.2 Classical ABC Implementation
266(3)
10.1.3 Parameterization and Evolution of the Classical ABC Algorithm
269(1)
10.2 In Search of the Perfect Harmony
270(5)
10.2.1 Memory Initialization
273(1)
10.2.2 Improvisation of a New Harmony
273(1)
10.2.3 Updating of the Memory Slots
274(1)
10.2.4 Parameterization and Evolution of the Classical Algorithm
275(1)
10.3 The Echolocation Behavior of Microbats
275(5)
10.3.1 Initialization Step
277(1)
10.3.2 Moves of the Bats
278(1)
10.3.3 Update of the Emission Properties of the Ultrasound
279(1)
10.3.4 Evolution of the Algorithm
279(1)
10.4 Nature Continues to Inspire New Algorithms
280(3)
10.4.1 Bacterial Foraging Optimization
280(1)
10.4.2 Slime Mold Optimization
281(1)
10.4.3 Fireflies and Glowworms
281(1)
10.4.4 Termites
282(1)
10.4.5 Roach Infestation
282(1)
10.4.6 Mosquitoes
282(1)
10.4.7 Wasps
282(1)
10.4.8 Spiders
282(1)
10.4.9 Cuckoo Search
282(1)
10.5 Conclusion
283(1)
10.6 Annotated Bibliography
283(1)
References
283(4)
11 Extensions of Evolutionary Algorithms to Multimodal and Multiobjective Optimization 287(42)
Alain Petrowski
11.1 Introduction
287(1)
11.2 Multimodal Optimization
288(9)
11.2.1 The Problem
288(1)
11.2.2 Niching with the Sharing Method
289(2)
11.2.3 Niching with the Deterministic Crowding Method
291(1)
11.2.4 The Clearing Procedure
292(3)
11.2.5 Speciation
295(2)
11.3 Multiobjective Optimization
297(27)
11.3.1 Problem Formalization
297(2)
11.3.2 The Quality Indicators
299(3)
11.3.3 Multiobjective Evolutionary Algorithms
302(1)
11.3.4 Methods Using a Pareto Ranking
302(12)
11.3.5 Scalarization Methods
314(10)
11.4 Conclusion
324(1)
11.5 Annotated Bibliography
325(1)
References
325(4)
12 Extension of Evolutionary Algorithms to Constrained Optimization 329(28)
Sana Ben Hamida
12.1 Introduction
329(2)
12.2 Penalization
331(11)
12.2.1 "Death Penalty" Method
333(1)
12.2.2 Static Penalty Methods
334(1)
12.2.3 Dynamic Penalty Methods
334(1)
12.2.4 Adaptive Penalty Methods
335(4)
12.2.5 Self-adaptive Penalty Methods
339(2)
12.2.6 Segregated Genetic Algorithm (SGGA)
341(1)
12.3 Superiority of Feasible Solutions
342(2)
12.3.1 Method of Powel and Skolnick
342(1)
12.3.2 Deb's Method
343(1)
12.3.3 Stochastic Ranking
343(1)
12.4 Searching for Feasible Solutions
344(3)
12.4.1 Repair Methods: GENOCOP III
345(1)
12.4.2 Behavioral Memory
346(1)
12.5 Preserving the Feasibility of Solutions
347(3)
12.5.1 GENOCOP System
347(1)
12.5.2 Searching on the Boundary of the Feasible Region
348(1)
12.5.3 "Homomorphous Mapping"
349(1)
12.6 Multiobjective Methods
350(2)
12.6.1 Method of Surry et al
350(1)
12.6.2 Method of Camponogara and Talukdar
351(1)
12.6.3 IDEA Method of Singh et al
352(1)
12.7 Hybrid Methods
352(1)
12.8 Conclusion
353(1)
12.9 Annotated Bibliography
354(1)
References
354(3)
13 Methodology 357(24)
Eric Taillard
13.1 Introduction
357(2)
13.1.1 Academic Vehicle Routing Problem
358(1)
13.2 Decomposition Methods
359(5)
13.2.1 Chain of Decomposition
359(1)
13.2.2 Decomposition into Subproblems of Smaller Size
360(4)
13.3 Problem Modeling
364(2)
13.4 Population Management and Adaptive Memory Programming
366(5)
13.4.1 Evolutionary or Memetic Algorithms
367(1)
13.4.2 Scatter Search
367(1)
13.4.3 Ant Colonies
368(1)
13.4.4 Vocabulary Building
369(1)
13.4.5 Path Relinking
369(2)
13.5 Comparison of Heuristics
371(6)
13.5.1 Comparing Proportions
371(2)
13.5.2 Comparing Iterative Optimization Methods
373(4)
13.6 Conclusion
377(1)
References
378(3)
14 Optimization of Logistics Systems Using Metaheuristic-Based Hybridization Techniques 381(26)
Laurent Deroussi
Nathalie Grangeon
Sylvie Norre
14.1 Logistics Systems
382(5)
14.1.1 Definitions and General Considerations
382(1)
14.1.2 Integrated View of Supply Chain
383(1)
14.1.3 Difficulties of Performance Optimization in a Supply Chain
384(1)
14.1.4 Decision Support System
385(1)
14.1.5 Reason for Interest in Metaheuristics
386(1)
14.2 Hybridization Techniques
387(6)
14.2.1 Generalities
387(3)
14.2.2 Metaheuristic/Optimization-Method Hybridization
390(1)
14.2.3 Metaheuristic/Performance-Evaluation-Method Hybridization
391(2)
14.3 Application to Supply Chain Management
393(9)
14.3.1 Preamble
393(1)
14.3.2 Production/Distribution Planning
394(3)
14.3.3 Location-Routing Problem
397(2)
14.3.4 Multiplant Multiproduct Capacitated Lot-Sizing Problem
399(2)
14.3.5 Flexible Manufacturing System
401(1)
14.4 Conclusion
402(1)
References
403(4)
15 Metaheuristics for Vehicle Routing Problems 407(32)
Caroline Prodhon
Christian Prins
15.1 Introduction
407(1)
15.2 Vehicle Routing Problems
408(3)
15.2.1 Basic Version
408(1)
15.2.2 Variants of the Classical Vehicle Routing Problem
409(2)
15.3 Basic Heuristics and Local Search Procedures
411(7)
15.3.1 Basic Heuristics
411(1)
15.3.2 Local Search
412(6)
15.4 Metaheuristics
418(5)
15.4.1 Path Methods
419(1)
15.4.2 Population or Agent-Based Methods
420(2)
15.4.3 Evolution of the Field, and Trends
422(1)
15.5 The Split Approach
423(4)
15.5.1 Principle and Advantages
423(2)
15.5.2 Split Algorithm
425(2)
15.5.3 Integration into Heuristics and Metaheuristics
427(1)
15.6 Example of a Metaheuristic Using the Split Approach
427(3)
15.6.1 General Principle of GRASP x ELS
427(1)
15.6.2 Application to the Capacitated Vehicle Routing Problem
428(2)
15.7 Conclusion
430(1)
15.8 Annotated Bibliography
430(1)
References
431(8)
16 Applications to Air Traffic Management 439(46)
Nicolas Durand
David Gianazza
Jean-Baptiste Gotteland
Charlie Vanaret
Jean-Marc Alliot
16.1 Introduction
439(2)
16.2 Air Route Network Optimization
441(11)
16.2.1 Optimal Positioning of Nodes and Edges Using Geometric Algorithms
442(4)
16.2.2 Node Positioning with Fixed Topology, Using a Simulated Annealing or Particle Swarm Optimization Algorithm
446(1)
16.2.3 Defining 2D Corridors with a Clustering Method and a Genetic Algorithm
447(1)
16.2.4 Building Separate 3D Tubes Using an Evolutionary Algorithm and an A* Algorithm
448(4)
16.3 Airspace Optimization
452(13)
16.3.1 Airspace Sectorization
453(1)
16.3.2 Definition of Functional Airspace Blocks
454(4)
16.3.3 Prediction of ATC Sector Openings
458(7)
16.4 Departure Slot Optimization
465(2)
16.5 Airport Traffic Optimization
467(7)
16.5.1 Gate Assignment
467(1)
16.5.2 Scheduling the Aircraft on the Runway
468(2)
16.5.3 Surface Routing Optimization
470(2)
16.5.4 Global Airport Traffic Planning
472(2)
16.6 Aircraft Conflict Resolution
474(6)
16.6.1 Ant Colony Optimization Approach
476(1)
16.6.2 Free-Flight Approaches
476(2)
16.6.3 A Framework for Comparing Different Approaches
478(2)
16.7 Conclusion
480(1)
References
481(4)
Index 485
Patrick Siarry is a Professor of Automatics and Informatics at the University of Paris-Est Créteil, where he leads the Image and Signal Processing team in the Laboratoire Images, Signaux et Systèmes Intelligents (LiSSi). He has considerable teaching, research and writing experience in the areas of signal processing, control, artificial intelligence, operations research, and optimization. He presently serves as an Associate Editor of the journal Information Sciences and the journal Engineering Applications of Artificial Intelligence.