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 7 to 10 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 $79.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 Computer Science

Microsoft Power BI For Dummies

For Dummies (Computer/Tech)

Don't Burn Anyone at the Stake Today

(and other lessons from history about living through an information crisis)

The Laws of Thought

The Quest for a Mathematical Theory of the Mind

Nexus

A Brief History of Information Networks from the Stone Age to AI

If Anyone Builds It, Everyone Dies

The Case Against Superintelligent AI

The AI Con

How To Fight Big Tech's Hype and Create the Future We Want

Atlas of the Invisible

Maps & Graphics That Will Change How You See the World

Python Crash Course

3rd Edition - A Hands-On, Project-Based Introduction to Programming

The AI-Driven Leader

Harnessing AI to Make Faster, Smarter Decisions

Empire of AI

Inside the reckless race for total domination

Hope in the Library

How Libraries Can Help Shape Our Future with Artificial Intelligence

A Cultural History of Computer Graphics

What Art Is Now

Creativity in the Age of AI

Human-Centered Solutions through Human-Computer Interaction

From Healthcare to Smart Environments

Microsoft 365 Excel All-in-One For Dummies

Excel for Dummies

Agentic AI For Dummies

For Dummies (Computer/Tech)

AI in Business For Dummies

For Dummies (Business & Personal Finance)

AI Powered B2B Marketing

Develop AI Enabled Strategies and Practices for Maximum Impact

MRI in Practice

5th Edition

Atlas of AI

Power, Politics, and the Planetary Costs of Artificial Intelligence

Computability and Computational Explanation

Elements in the Philosophy of Mathematics

Computability and Computational Explanation

Elements in the Philosophy of Mathematics

Determining Provenance from Compositional Data

Elements in Current Archaeological Tools and Techniques

The human Spark - Beyond AI

The Human Spark - Beyond AI

This product is categorised by