Recent Advances in Evolutionary Computation for Combinatorial Optimization (Studies in Computational Intelligence, 153)

✍ Scribed by Carlos Cotta (editor), Jano van Hemert (editor)

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 362
• 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

Title Page
Preface
Contents
List of Contributors
An Evolutionary Algorithm for the Solution of Two-Variable Word Equations in Partially Commutative Groups
Introduction
History and Background
Partially Commutative Groups
Statement of Problem
Genetic Algorithms on the Group $V_n$
An Introduction to the Approach
The Representation and Computation of Words
Reproduction
The Cost Function
Selection Algorithms
Traceback
General Description of Traceback Procedure
Example of Traceback on a Given Instance
Setup of the Evolutionary Algorithm
Specification of Output Alphabet
The Algorithm and Its Parameters
Method of Testing
Results
Discussion
Conclusions
Determining Whether a Problem Characteristic Affects Heuristic Performance A Rigorous Design of Experiments Approach
Introduction and Motivation
Background
Method
Response Variables
Instances
Factors, Levels and Ranges
Experiment Design, Power and Replicates
Performing the Experiment
Analysis
Transformations
Outliers
Results
Related Work
Conclusions
Implications
Assumptions and Restrictions
Future Work
Performance and Scalability of Genetic Algorithms on NK-Landscapes
Introduction
Epistasis and NK-Landscapes
Related Works
The Algorithms
GA-SRM
RBC+
Configurations for Performance Observation
Performance Observation, Insights on GA Behavior, and Discussion
Selection
Duplicates Elimination
Parallel Varying-Mutation
No Crossover
Epitasis Pattern and Mutation Strategy
Conclusions
Engineering Stochastic Local Search Algorithms: A Case Study in Estimation-Based Local Search for the Probabilistic Travelling Salesman Problem
Introduction
The Probabilistic Travelling Salesman Problem
Iterative Improvement Algorithms for the PTSP
Engineering an Iterative Improvement Algorithm for the PTSP
Introducing TSP Speed-Up Techniques
Estimation-Based Local Search
Improving the Estimation-Based Local Search
Estimation Based Iterated Local Search
Conclusions
Hybrid Approaches
A Lagrangian Decomposition/Evolutionary Algorithm Hybrid for the Knapsack Constrained Maximum Spanning Tree Problem
Introduction
Previous Work
Lagrangian Decomposition for the KCMST Problem
Solving the Lagrangian Dual Problem
Strength of the Lagrangian Decomposition
Deriving Lower Bounds
A Suitable Evolutionary Algorithm
Hybrid Lagrangian Evolutionary Algorithm
Computational Results
Test Instances
Parameter Settings
Comparing LR and LD
LD Combined with LS and EA
Conclusions
A Hybrid Optimization Framework for Cutting and Packing Problems Case Study on Constrained 2D Non-guillotine Cutting
Introduction
Related Work
Outline of Some Hybrid Metaheuristic Approaches
The Constrained Two-Dimensional Non-guillotine Cutting Problem
Hybrid Framework
Case Study
Computational Experiments
Final Remarks
A Hybrid Genetic Algorithm for the DNA Fragment Assembly Problem
Introduction
The DNA Fragment Assembly Problem
Algorithms
Genetic Algorithm
Problem Aware Local Search (PALS)
Hybrid Approach
Experimental Results
Target Problem Instances and Parameter Settings
Performance Analysis
Conclusions
A Memetic-Neural Approach to Discover Resources in P2P Networks
Introduction
NeuroSearch - Neural Network Based Query Forwarding
The Set of the Neural Network Inputs
Input Scaling
Calculation of the Neural Network Output
The Optimization Problem
Fitness Formulation
Features of the Decision Space and the Fitness Landscape
The Adaptive Global-Local Memetic Algorithm
Initialization
Parent Selection and Variation Operators
Fitness Function
Local Searchers
Adaptation
Coordination of the Local Searchers
Dynamic Population Size in Survivor Selection
Numerical Results
Conclusion
Constrained Problems
An Iterative Heuristic Algorithm for Tree Decomposition
Introduction
Algorithms for Tree Decompositions
An Iterative Local Search Algorithm
Local Search Techniques
Perturbation
Acceptance of Solution in Iterated Algorithm
Evaluation of Algorithms
Comparison with Results in Literature
Conclusions
Search Intensification in Metaheuristics for Solving the Automatic Frequency Problem in GSM
Introduction
Frequency Planning in GSM Networks
The GSM System
The Automatic Frequency Planning Problem
Algorithms for Solving the AFP Problem
Fitness Function
Solution Encoding
(1, {\lambda}$) EA
Simulated Annealing
Solution Initialization
Perturbation Operator
Experiments
GSM Instance Used
Results
Conclusions and Future Work
Contraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem
Introduction
Representing Solutions to Graph Colouring as Homomorphisms
Vertex Colouring by Graph Homomorphisms
Merge Operations as Atomic Transformation Steps of the Homomorphisms
Information Derived from the Data Structures
Heuristics Based on Merge Model Structures
An Evolutionary Algorithm Based on Merge Models
Experiments and Results
Conclusions
Scheduling
Different Codifications and Metaheuristic Algorithms for the Resource Renting Problem with Minimum and Maximum Time Lags
Introduction
Preliminaries
Model of the Problem
Candidates for Optimal Solution
Metaheuristic Algorithms for the RRP
Algorithm Adapted from a Regular Problem (adapGA)
Specially Designed Algorithm (specGA)
Improved Algorithm (finalGA)
An Iterated Greedy Approach for the RRP (IG)
Computational Results
Test Bed
Comparison between the Metaheuristic Algorithms
Comparison with $B&B_N$
Summary and Concluding Remarks
A Simple Optimised Search Heuristic for the Job Shop Scheduling Problem
Introduction
The Job Shop Scheduling Problem
Review of Optimised Search Heuristics
Optimised Search Heuristic - GRASP-B&B
The Building Step
The Local Search Step
GRASP-B&B
Computational Results
Comparison to Other Procedures
Conclusions
Parallel Memetic Algorithms for Independent Job Scheduling in Computational Grids
Introduction
Job Scheduling on Computational Grids
Overview of the Taxonomy of the Parallel Models for Memetic Algorithms
Multiple Searches
Hybrid Models
Design and Implementation of the Parallel EAs (PEAs)
Extension of the MALLBA Skeletons
Communication and Migration in TLG Model for the cMAs
Design and Implementation of the Coarse-Grained Steeping Stone Level
Design and Implementation of the Fine-Grained Level
Experimental Study
Speed up Analysis
Qualitative Improvement of the Makespan Results
Conclusions
Routing and Travelling Salesman Problems
Reducing the Size of Travelling Salesman Problem Instances by Fixing Edges
Introduction
Related Work
Problem Reduction by Fixing Edges
Analysis of TSP Instances
Results of the Analysis
Experimental Setup and Results
Conclusion
Algorithms for Large Directed Capacitated Arc Routing Problem Instances Urban Solid Waste Collection Operational Support
Introduction
Urban Solid State Waste Collection
Capacitated Arc Routing Problem
Transformation into an ACVRP
New Metaheuristics
Two Phase Construction Algorithm
Multistart Algorithm
Genetic Algorithm
Data Perturbation
Computational Results
Algorithm Setting
Algorithm Comparison
Real World Cases
Results of DP Algorithm
Conclusions
An Evolutionary Algorithm with Distance Measure for the Split Delivery Capacitated Arc Routing Problem
Introduction
Problem Statement and Linear Formulation
Heuristics
Augment-Merge and Path-Scanning
Split-Insertion Heuristic for the SDCARP
Memetic Algorithm with Population Management
Chromosomes and Evaluation
Distance Measure
Initial Population
Selection, Crossover and Replacement
Local Search
General Structure of the Algorithm
Computational Results
Instances, Implementation and Parameters
Results
Conclusion
A Permutation Coding with Heuristics for the Uncapacitated Facility Location Problem
Introduction
The Problem
A Permutation Coding
The Coding and Its Evaluation
Operators
Heuristic Extensions
A Genetic Algorithm
Comparisons
Conclusion
References
References
Index
Author Index