Metaheuristics for Hard Optimization

Methods and Case Studies

By: A. Chatterjee (Translator), Johann Dréo, Alain Pétrowski

Write A Review

Hardcover | 24 November 2005

At a Glance

Hardcover
388 Pages

Dimensions(cm)
24.13 x 15.24 x 2.54

Hardcover

$84.99

or 4 interest-free payments of $21.25 with

Ships in 5 to 7 business days

Metaheuristics for Hard Optimization comprises of three parts. The first part is devoted to the detailed presentation of the four most widely known metaheuristics:

* the simulated annealing method,

* tabu search,

* the evolutionary algorithms,

* ant colony algorithms.

Each one of these metaheuristics is actually a family of methods, of which the essential elements are discussed. In the second part, the book presents some other less widespread metaheuristics, then, extensions of metaheuristics and some ways of research are described . The problem of the choice of a metaheuristic is posed and solution methods are discussed. The last part concentrates on three case studies from telecommunications, air traffic control, and vehicle routing.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $89.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

Introduction	p. 1
Presentation of the Main Metaheuristics
Simulated Annealing	p. 23
Introduction	p. 23
Presentation of the method	p. 24
Analogy between an optimization problem and some physical phenomena	p. 24
Real annealing and simulated annealing	p. 25
Simulated annealing algorithm	p. 25
Theoretical approaches	p. 27
Theoretical convergence of simulated annealing	p. 27
Configuration space	p. 28
Rules of acceptance	p. 30
Annealing scheme	p. 30
Parallelization of the simulated annealing algorithm	p. 32
Some applications	p. 35
Benchmark problems of combinatorial optimization	p. 35
Layout of electronic circuits	p. 36
Search for an equivalent schema in electronics	p. 40
Practical applications in various fields	p. 42
Advantages and disadvantages of the method	p. 44
Simple practical suggestions for the beginners	p. 44
Annotated bibliography	p. 45
Tabu Search	p. 47
Introduction	p. 47
The quadratic assignment problem	p. 49
Basic tabu search	p. 51
Neighborhood	p. 51
Moves, neighborhood	p. 52
Evaluation of the neighborhood	p. 54
Candidate list	p. 56
Short-term memory	p. 57
Hashing tables	p. 57
Tabu list	p. 59
Duration of tabu conditions	p. 60
Aspiration conditions	p. 66
Convergence of tabu search	p. 66
Long-term memory	p. 69
Frequency-based memory	p. 69
Obligation to carry out move	p. 71
Strategic oscillations	p. 72
Conclusion	p. 72
Annotated bibliography	p. 72
Evolutionary Algorithms	p. 75
From genetics to engineering	p. 75
The generic evolutionary algorithm	p. 77
Selection operators	p. 77
Variation operators	p. 78
The generational loop	p. 78
Solving a simple problem	p. 79
Selection operators	p. 81
Selection pressure	p. 81
Genetic drift	p. 82
Proportional selection	p. 83
Tournament selection	p. 88
Truncation selection	p. 90
Replacement selections	p. 90
Fitness function	p. 92
Variation operators and representation	p. 93
Generalities about the variation operators	p. 93
Binary representation	p. 97
Real representation	p. 101
Some discrete representations for the permutation problems	p. 108
Representation of parse trees for the genetic programming	p. 113
Particular case of the genetic algorithms	p. 118
Some considerations on the convergence of the evolutionary algorithms	p. 119
Conclusion	p. 120
Glossary	p. 121
Annotated bibliography	p. 122
Ant Colony Algorithms	p. 123
Introduction	p. 123
Collective behavior of social insects	p. 124
Self-organization and behavior	p. 124
Natural optimization: pheromonal trails	p. 127
Optimization by ant colonies and the traveling salesman problem	p. 129
Basic algorithm	p. 130
Variants	p. 131
Choice of the parameters	p. 134
Other combinatorial problems	p. 134
Formalization and properties of ant colony optimization	p. 135
Formalization	p. 135
Pheromones and memory	p. 137
Intensification/diversification	p. 137
Local search and heuristics	p. 138
Parallelism	p. 138
Convergence	p. 139
Prospect	p. 139
Continuous optimization	p. 139
Dynamic problems	p. 147
Metaheuristics and ethology	p. 147
Links with other metaheuristics	p. 148
Conclusion	p. 149
Annotated bibliography	p. 150
Variants, Extensions and Methodological Advices
Some Other Metaheuristics	p. 153
Introduction	p. 153
Some variants of simulated annealing	p. 154
Simulated diffusion	p. 154
Microcanonic annealing	p. 155
The threshold method	p. 157
"Great deluge" method	p. 157
Method of the "record to record travel"	p. 157
Noising method	p. 159
Method of distributed search	p. 159
"Alienor" method	p. 160
Particle swarm optimization method	p. 162
The estimation of distribution algorithm	p. 166
GRASP method	p. 169
"Cross-Entropy" method	p. 170
Artificial immune systems	p. 172
Method of differential evolution	p. 173
Algorithms inspired by the social insects	p. 175
Annotated bibliography	p. 176
Extensions	p. 179
Introduction	p. 179
Adaptation for the continuous variable problems	p. 179
General framework of "difficult" continuous optimization	p. 179
Some continuous metaheuristics	p. 185
Multimodal optimization	p. 196
The problem	p. 196
Niching with the sharing method	p. 196
Niching with the deterministic crowding method	p. 199
The clearing procedure	p. 201
Speciation	p. 203
Multiobjective optimization	p. 206
Formalization of the problem	p. 206
Simulated annealing based methods	p. 208
Multiobjective evolutionary algorithms	p. 211
Constrained evolutionary optimization	p. 216
Penalization methods	p. 217
Superiority of the feasible individuals	p. 219
Repair methods	p. 220
Variation operators satisfying the constraint structures	p. 221
Other methods dealing with constraints	p. 223
Conclusion	p. 223
Annotated bibliography	p. 224
Methodology	p. 225
Introduction	p. 225
Problem modeling	p. 227
Neighborhood choice	p. 228
"Simple" neighborhoods	p. 228
Ejection chains	p. 230
Decomposition into subproblems: POPMUSIC	p. 231
Conclusions on modeling and neighborhood	p. 233
Improving method, simulated annealing, taboo search...?	p. 235
Adaptive Memory Programming	p. 235
Ant colonies	p. 236
Evolutionary or memetic algorithms	p. 236
Scatter Search	p. 236
Vocabulary building	p. 238
Path relinking	p. 239
Iterative heuristics comparison	p. 240
Comparing proportion	p. 241
Comparing iterative optimization methods	p. 243
Conclusion	p. 244
Annotated bibliography	p. 247
Case Studies
Optimization of UMTS Radio Access Networks with Genetic Algorithms	p. 251
Introduction	p. 251
Introduction to mobile radio networks	p. 252
Cellular network	p. 252
Characteristic of the radio channel	p. 253
Radio interface of the UMTS	p. 255
Definition of the optimization problem	p. 261
Radio planning of a UMTS network	p. 261
Definition of the optimization problem	p. 262
Application of the genetic algorithm to automatic planning	p. 265
Coding	p. 265
Genetic operators	p. 266
Evaluation of the individuals	p. 267
Results	p. 267
Optimization of the capacity	p. 269
Optimization of the loads	p. 270
Optimization of the intercellular interferences	p. 272
Optimization of the coverage	p. 272
Optimization of the probability of access	p. 273
Conclusion	p. 274
Genetic Algorithms Applied to Air Traffic Management	p. 277
En route conflict resolution	p. 277
Complexity of the conflict resolution problem	p. 280
Existing resolution methods	p. 280
Modeling of the problem	p. 281
Implementation of the genetic algorithm	p. 285
Theoretical study of a simple example	p. 288
Numerical application	p. 292
Remarks	p. 295
Ground Traffic optimization	p. 296
Modeling	p. 296
BB: the 1-against-n resolution method	p. 300
GA and GA+BB: genetic algorithms	p. 301
Experimental results	p. 303
Conclusion	p. 306
Constraint Programming and Ant Colonies Applied to Vehicle Routing Problems	p. 307
Introduction	p. 307
Vehicle routing problems and constraint programming	p. 308
Vehicle routing problems	p. 308
Constraint programming	p. 309
Constraint programming applied to PDP: ILOG Dispatcher	p. 314
Ant colonies	p. 316
Behavior of the real ants	p. 316
Ant colonies, vehicle routing problem and constraint programming	p. 316
Ant colony algorithm with backtracking	p. 317
Experimental results	p. 323
Conclusion	p. 325
Conclusion	p. 327
Appendices
Modeling of Simulated Annealing Through the Markov Chain Formalism	p. 331
Complete Example of Implementation of Tabu Search for the Quadratic Assignment Problem	p. 339
References	p. 347
Index	p. 365
Table of Contents provided by Ingram. All Rights Reserved.

Metaheuristics for Hard Optimization

Methods and Case Studies

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Automatic Control Engineering

AI and Innovation in Human-Computer Interaction

Design Implementation and Trust-Building

AI-Driven Digital Twin and Industry 4.0

A Conceptual Framework with Applications

AI in Material Science

Revolutionizing Construction in the Age of Industry 4.0

Artificial Intelligence and Internet of Things based Augmented Trends for Data Driven Systems

Intelligent Data-Driven Systems and Artificial Intelligence

Artificial Intelligence-Based System for Gaze-Based Communication

Artificial Intelligence, Co-Creation and Creativity

The New Frontier for Innovation

Artificial Intelligence Enabled Signal Processing based Models for Neural Information Processing

Artificial Intelligence for Intelligent Systems

Fundamentals, Challenges, and Applications

Artificial Intelligence for Science and Engineering Applications

Artificial Intelligence in Medicine

Artificial Intelligence Solutions for Cyber-Physical Systems

Artificial Intelligence Systems in Environmental Engineering

Automation in Construction toward Resilience

Robotics, Smart Materials and Intelligent Systems

Autonomous Weapons Systems and the Responsibility of States

Challenges and Possibilities

Chaotic Dynamics of Fractional Discrete Time Systems

Computational Approaches in Biomaterials and Biomedical Engineering Applications

Emerging Trends in Biomedical Technologies and Health informatics

Computational Approaches in Biotechnology and Bioinformatics

Emerging Trends in Biomedical Technologies and Health informatics

Convergence of Blockchain and Internet of Things in Healthcare

Smart Engineering Systems: Design and Applications

Converging Minds

The Creative Potential of Collaborative AI

Data-Centric Artificial Intelligence for Multidisciplinary Applications

Data-Driven Modelling with Fuzzy Sets

Embracing Uncertainty

Data-Driven Modelling with Fuzzy Sets

A Neutrosophic Perspective

Deep Learning in Internet of Things for Next Generation Healthcare

Deviations in Contemporary Theatrical Anthropology

New Myths and Performative Rituals between XR, Robots and AI

This product is categorised by