Metaheuristics From Design to Implementation

by Talbi, El-Ghazali

• ISBN13: 9780470278581
• ISBN10: 0470278587
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-06-22
• Publisher: Wiley

Summary

Metaheuristics provides a complete background of metaheuristics, enabling readers to design and deploy powerful algorithms to solve complex optimization problems in a diverse range of industries. Using case studies in different domains, including telecommunications, transportation and logistics, bioinformatics, design engineering, and scheduling provides clear information for these diverse markets. The book is an effective resource for engineers, researchers, and developers, and an ideal text for graduate students in computer science, bioinformatics, electrical engineering, and applied mathematics courses.

Author Biography

El-ghazali Talbi is a full Professor in Computer Science at the University of Lille (France), and head of the optimization group of the Computer Science Laboratory (L.I.F.L.). His current research interests are in the fields of metaheuristics, parallel algorithms, multi-objective combinatorial optimization, cluster and grid computing, hybrid and cooperative optimization, and application to bioinformatics, networking, transportation, and logistics. He is the founder of the conference META (International Conference on Metaheuristics and Nature Inspired Computing), and is head of the INRIA Dolphin project dealing with robust multi-objective optimization of complex systems.

Table of Contents

Preface

Acknowledgments

Glossary

Common Concepts for Metaheuristics

Optimization Models

Classical Optimization Models

Complexity Theory

Complexity of Algorithms

Complexity of Problems

Other Models for Optimization

Optimization Under Uncertainty

Dynamic Optimization

Multiperiodic Optimization

Robust Optimization

Optimization Methods

Exact Methods

Approximate Algorithms

Approximation Algorithms

Metaheuristics

Greedy Algorithms

When Using Metaheuristics

Main Common Concepts for Metaheuristics

Representation

Linear Representations

Nonlinear Representations

Representation-Solution Mapping

Direct Versus Indirect Encodings

Objective Function

Self-Sufficient Objective Functions

Guiding Objective Functions

Representation Decoding

Interactive Optimization

Relative and Competitive Objective Functions

Meta-Modeling

Constraint Handling

Reject Strategies

Penalizing Strategies

Repairing Strategies

Decoding Strategies

Preserving Strategies

Parameter Tuning

Off-Line Parameter Initialization

Online Parameter Initialization

Performance Analysis of Metaheuristics

Experimental Design

Measurement

Quality of Solutions

Computational Effort

Robustness

Statistical Analysis

Ordinal Data Analysis

Reporting

Software Frameworks for Metaheuristics

Why a Software Framework for Metaheuristics?

Main Characteristics of Software Frameworks

ParadisEO Framework

ParadisEO Architecture

Conclusions

Exercises

Single-Solution Based Metaheuristics

Common Concepts for Single-Solution Based Metaheuristics

Neighborhood

Very Large Neighborhoods

Heuristic Search in Large Neighborhoods

Exact Search in Large Neighborhoods

Polynomial-Specific Neighborhoods

Initial Solution

Incremental Evaluation of the Neighborhood

Fitness Landscape Analysis

Distances in the Search Space

Landscape Properties

Distribution Measures

Correlation Measures

Breaking Plateaus in a Flat Landscape

Local Search

Selection of the Neighbor

Escaping from Local Optima

Simulated Annealing

Move Acceptance

Cooling Schedule

Initial Temperature

Equilibrium State

Cooling

Stopping Condition

Other Similar Methods

Threshold Accepting

Record-to-Record Travel

Great Deluge Algorithm

Demon Algorithms

Tabu Search

Short-Term Memory

Medium-Term Memory

Long-Term Memory

Iterated Local Search

Perturbation Method

Acceptance Criteria

Variable Neighborhood Search

Variable Neighborhood Descent

General Variable Neighborhood Search

Guided Local Search

Other Single-Solution Based Metaheuristics

Smoothing Methods

Noisy Method

GRASP

S-Metaheuristic Implementation Under ParadisEO

Common Templates for Metaheuristics

Common Templates for S-Metaheuristics

Local Search Template

Simulated Annealing Template

Tabu Search Template

Iterated Local Search Template

Conclusions

Exercises

Population-Based Metaheuristics

Common Concepts for Population-Based Metaheuristics

Initial Population

Random Generation

Sequential Diversification

Parallel Diversification

Heuristic Initialization

Stopping Criteria

Evolutionary Algorithms

Genetic Algorithms

Evolution Strategies

Evolutionary Programming

Genetic Programming

Common Concepts for Evolutionary Algorithms

Selection Methods

Roulette Wheel Selection

Stochastic Universal Sampling

Tournament Selection

Rank-Based Selection

Reproduction

Mutation

Recombination or Crossover

Replacement Strategies

Other Evolutionary Algorithms

Estimation of Distribution Algorithms

Differential Evolution

Coevolutionary Algorithms

Cultural Algorithms

Scatter Search

Path Relinking

Swarm Intelligence

Ant Colony Optimization Algorithms

ACO for Continuous Optimization Problems

Particle Swarm Optimization

Artificial Immune Systems

Natural Immune System

Clonal Selection Theory

Negative Selection Principle

Immune Network Theory

Danger Theory

P-metaheuristics Implementation under ParadisEO

Common Components and Programming Hints

Main Core TemplatesùParadisEO-EOÆs Functors

Representation

Fitness Function

Initialization

Stopping Criteria, Checkpoints, and Statistics

Dynamic Parameter Management and State Loader/Register

Evolutionary Algorithms Under ParadisEO

Representation

Initialization

Evaluation

Variation Operators

Evolution Engine

Evolutionary Algorithms

Particle Swarm Optimization Under ParadisEO

Illustrative Example

Estimation of Distribution Algorithm Under ParadisEO

Conclusions

Exercises

Metaheuristics for Multiobjective Optimization

Multiobjective Optimization Concepts

Multiobjective Optimization Problems

Academic Applications

Multiobjective Continuous Problems

Multiobjective Combinatorial Problems

Real-Life Applications

Multicriteria Decision Making

Main Design Issues of Multiobjective Metaheuristics

Fitness Assignment Strategies

Scalar Approaches

Aggregation Method

Weighted Metrics

Goal Programming

Achievement Functions

Goal Attainment

-Constraint Method

Criterion-Based Methods

Parallel Approach

Sequential or Lexicographic Approach

Dominance-Based Approaches

Indicator-Based Approaches

Diversity Preservation

Kernel Methods

Nearest-Neighbor Methods

Histograms

Elitism

Performance Evaluation and Pareto Front Structure

Performance Indicators

Convergence-Based Indicators

Diversity-Based Indicators

Hybrid Indicators

Landscape Analysis of Pareto Structures

Multiobjective Metaheuristics Under ParadisEO

Software Frameworks for Multiobjective Metaheuristics

Common Components

Representation

Fitness Assignment Schemes

Diversity Assignment Schemes

Elitism

Statistical Tools

Multiobjective EAs-Related Components

Selection Schemes

Replacement Schemes

Multiobjective Evolutionary Algorithms

Conclusions and Perspectives

Exercises

Hybrid Metaheuristics

Hybrid Metaheuristics

Design Issues

Hierarchical Classification

Flat Classification

Implementation Issues

Dedicated Versus General-Purpose Computers

Sequential Versus Parallel

A Grammar for Extended Hybridization Schemes

Combining Metaheuristics with Mathematical Programming

Mathematical Programming Approaches

Enumerative Algorithms

Relaxation and Decomposition Methods

Branch and Cut and Price Algorithms

Classical Hybrid Approaches

Low-Level Relay Hybrids

Low-Level Teamwork Hybrids

High-Level Relay Hybrids

High-Level Teamwork Hybrids

Combining Metaheuristics with Constraint Programming

Constraint Programming

Classical Hybrid Approaches

Low-Level Relay Hybrids

Low-Level Teamwork Hybrids

High-Level Relay Hybrids

High-Level Teamwork Hybrids

Hybrid Metaheuristics with Machine Learning and Data Mining

Data Mining Techniques

Main Schemes of Hybridization

Low-Level Relay Hybrid

Low-Level Teamwork Hybrids

High-Level Relay Hybrid

High-Level Teamwork Hybrid

Hybrid Metaheuristics for Multiobjective Optimization

Combining Metaheuristics for MOPs

Low-Level Relay Hybrids

Low-Level Teamwork Hybrids

High-Level Relay Hybrids

High-Level Teamwork Hybrid

Combining Metaheuristics with Exact Methods for MOP

Combining Metaheuristics with Data Mining for MOP

Hybrid Metaheuristics Under ParadisEO

Low-Level Hybrids Under ParadisEO

High-Level Hybrids Under ParadisEO

Coupling with Exact Algorithms

Conclusions and Perspectives

Exercises

Parallel Metaheuristics

Parallel Design of Metaheuristics

Algorithmic-Level Parallel Model

Independent Algorithmic-Level Parallel Model

Cooperative Algorithmic-Level Parallel Model

Iteration-Level Parallel Model

Iteration-Level Model for S-Metaheuristics

Iteration-Level Model for P-Metaheuristics

Solution-Level Parallel Model

Hierarchical Combination of the Parallel Models

Parallel Implementation of Metaheuristics

Parallel and Distributed Architectures

Dedicated Architectures

Parallel Programming Environments and Middlewares

Performance Evaluation

Main Properties of Parallel Metaheuristics

Algorithmic-Level Parallel Model

Iteration-Level Parallel Model

Solution-Level Parallel Model

Parallel Metaheuristics for Multiobjective Optimization

Algorithmic-Level Parallel Model for MOP

Iteration-Level Parallel Model for MOP

Solution-Level Parallel Model for MOP

Hierarchical Parallel Model for MOP

Parallel Metaheuristics Under ParadisEO

Parallel Frameworks for Metaheuristics

Design of Algorithmic-Level Parallel Models

Algorithms and Transferred Data (What?

Transfer Control (When?

Exchange Topology (Where?

Replacement Strategy (How?

Parallel Implementation

A Generic Example

Island Model of EAs Within ParadisEO

Design of Iteration-Level Parallel Models

The Generic Multistart Paradigm

Use of the Iteration-Level Model

Design of Solution-Level Parallel Models

Implementation of Sequential Metaheuristics

Implementation of Parallel and Distributed Algorithms

Deployment of ParadisEO-PEO

Conclusions and Perspectives

Exercises

Appendix: UML and C++

A Brief Overview of UML Notations

A Brief Overview of the C++ Template Concept

References

Index

Table of Contents provided by Publisher. All Rights Reserved.