Recent Advances in Evolutionary Computation for Combinatorial Optimization

✍ Scribed by Matthew J. Craven (auth.), Carlos Cotta, Jano van Hemert (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2008
• Tongue: English
• Leaves: 333
• Series: Studies in Computational Intelligence 153
• Edition: 1
• Category: Library

✦ Synopsis

Combinatorial optimisation is a ubiquitous discipline whose usefulness spans vast applications domains. The intrinsic complexity of most combinatorial optimisation problems makes classical methods unaffordable in many cases. To acquire practical solutions to these problems requires the use of metaheuristic approaches that trade completeness for pragmatic effectiveness. Such approaches are able to provide optimal or quasi-optimal solutions to a plethora of difficult combinatorial optimisation problems.

The application of metaheuristics to combinatorial optimisation is an active field in which new theoretical developments, new algorithmic models, and new application areas are continuously emerging. This volume presents recent advances in the area of metaheuristic
combinatorial optimisation, with a special focus on evolutionary computation methods. Moreover, it addresses local search methods and hybrid approaches. In this sense, the book includes cutting-edge theoretical, methodological, algorithmic and applied developments in the field, from respected experts and with a sound perspective.

✦ Table of Contents

Front Matter....Pages -
Front Matter....Pages 1-1
An Evolutionary Algorithm for the Solution of Two-Variable Word Equations in Partially Commutative Groups....Pages 3-19
Determining Whether a Problem Characteristic Affects Heuristic Performance....Pages 21-35
Performance and Scalability of Genetic Algorithms on NK-Landscapes....Pages 37-52
Engineering Stochastic Local Search Algorithms: A Case Study in Estimation-Based Local Search for the Probabilistic Travelling Salesman Problem....Pages 53-66
Front Matter....Pages 67-67
A Lagrangian Decomposition/Evolutionary Algorithm Hybrid for the Knapsack Constrained Maximum Spanning Tree Problem....Pages 69-85
A Hybrid Optimization Framework for Cutting and Packing Problems....Pages 87-99
A Hybrid Genetic Algorithm for the DNA Fragment Assembly Problem....Pages 101-112
A Memetic-Neural Approach to Discover Resources in P2P Networks....Pages 113-129
Front Matter....Pages 131-131
An Iterative Heuristic Algorithm for Tree Decomposition....Pages 133-150
Search Intensification in Metaheuristics for Solving the Automatic Frequency Problem in GSM....Pages 151-166
Contraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem....Pages 167-184
Front Matter....Pages 185-185
Different Codifications and Metaheuristic Algorithms for the Resource Renting Problem with Minimum and Maximum Time Lags....Pages 187-202
A Simple Optimised Search Heuristic for the Job Shop Scheduling Problem....Pages 203-218
Parallel Memetic Algorithms for Independent Job Scheduling in Computational Grids....Pages 219-239
Front Matter....Pages 241-241
Reducing the Size of Travelling Salesman Problem Instances by Fixing Edges....Pages 243-258
Algorithms for Large Directed Capacitated Arc Routing Problem Instances....Pages 259-274
An Evolutionary Algorithm with Distance Measure for the Split Delivery Capacitated Arc Routing Problem....Pages 275-294
A Permutation Coding with Heuristics for the Uncapacitated Facility Location Problem....Pages 295-307
Back Matter....Pages -

✦ Subjects

Appl.Mathematics/Computational Methods of Engineering; Software Engineering; Operations Research/Decision Theory