Evolutionary Computation in Combinatorial Optimization: 8th European Conference, EvoCOP 2008, Naples, Italy, March 26-28, 2008, Proceedings (Lecture Notes in Computer Science, 4972)

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

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 300
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 8th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2008, held in Naples, Italy, in March 2008. The 24 revised full papers presented were carefully reviewed and selected from 69 submissions. The papers present the latest research and discuss current developments and applications in metaheuristics - a paradigm to effectively solve difficult combinatorial optimization problems appearing in various industrial, economical, and scientific domains. Prominent examples of metaheuristics are evolutionary algorithms, simulated annealing, tabu search, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms and ant colony optimization.

✦ Table of Contents

Title Page
Preface
Organization
Table of Contents
Adaptive Tabu Tenure Computation in Local Search
Introduction
Tabu Tenure in the Literature
Time Depending Tabu Tenure
Random Bounded Tabu Tenure
Reactive Tabu Tenure
Adaptive Tabu Tenure
Adaptive Tabu Tenure in ACL_TS Method
Study of the Tabu Tenure Repartition
Comparison with the Literature
Conclusion and Perspectives
A Conflict Tabu Search Evolutionary Algorithm for Solving Constraint Satisfaction Problems
Introduction
Constraint Satisfaction Problems
The Algorithm
Representation and Initialisation
Objective Function
Conflict Tabu List
Move-Operator
Experimental Setup
Results
Conclusions
Cooperative Particle Swarm Optimization for the Delay Constrained Least Cost Path Problem
Introduction
Delay Constrained Least Cost (DCLC) Path Problem
Lagrange Relaxation for the DCLC Problem
Hybrid PSO and Noising Metahueristic for Shortest Path Problem
Network Path Encoding for the Shortest Path Computation Using Hybrid PSO Algorithm
Fitness Function
Cooperative Hybrid PSO-Noising Method Based Algorithm for DCLC Path Problem
Simulation Results and Discussion
Conclusions
Effective Neighborhood Structures for the Generalized Traveling Salesman Problem
Introduction
Previous Work
Solution Representation and Initialization
Nearest Neighbor Heuristic for the GTSP (NNH)
Generalized Insertion Heuristic for the GTSP (GIH)
Neighborhood Structures
Generalized 2-opt Neighborhood (G2-opt)
Node Exchange Neighborhood (NEN)
Variable Neighborhood Search Framework
Computational Results
Conclusions and Future Work
Efficient Local Search Limitation Strategies for Vehicle Routing Problems
Introduction
The Search Strategy
The Framework of the Local Search
The Local Search Neighborhood
The Suggested Limitation Strategies
The Applied Memetic Algorithm
Experimental Results
Experimental Setting
Analysis of the Limitation Strategies
Comparisons with Other Heuristics
Conclusion
Evolutionary Local Search for the Minimum Energy Broadcast Problem
Introduction
Minimum Energy Broadcast
Related Work
Evolutionary Local Search
Experiments
Results
Fitness Landscape Analysis
Conclusion
Exploring Multi-objective PSO and GRASP-PR for Rule Induction
Introduction
Related Work
The GRASP-PR Rule Learning Algorithm
Multiple Objective Particle Swarm
Experiments Results
Methodology
Comparison with Other Systems
Pareto Dominance
Conclusions
An Extended Beam-ACO Approach to the Time and Space Constrained Simple Assembly Line Balancing Problem
Introduction
TSALBP-1
The Algorithm
A Priority Rule Heuristic
Beam-ACO for TSALBP-1
Computational Results
Conclusions
Graph Colouring Heuristics Guided by Higher Order Graph Properties
Introduction
Representing Solutions to Graph Colouring
Combinations of Contraction Algorithms and Heuristics
Guiding Graph Colouring by Graph Properties
An Evolutionary Algorithm Based on Merge Models
Experiments and Results
Conclusions
A Hybrid Column Generation Approach for the Berth Allocation Problem
Introduction
Literature Review
BAP Modeling
The PTA/LP Method
The Population Training Algorithm
PTA and LP Interaction
Computational Experience
Conclusions
Hybrid Metaheuristic for the Prize Collecting Travelling Salesman Problem
Introduction
Literature Review
Clustering Search
CS Algorithm for PCTSP
The GRASP/VNS Metaheuristic
The Clustering Process
Computational Results
Conclusions
An ILS Based Heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Limit
Introduction
Literature Review
Iterated Local Search
Solution Procedure
Constructive Procedure
Local Search
Perturbation Mechanism
Computational Results
Conclusion
An Immune Genetic Algorithm Based on Bottleneck Jobs for the Job Shop Scheduling Problem
Introduction
Problem Formulation
The Algorithm
The Bottleneck Characteristic Values
The Immune Genetic Algorithm Based on Bottleneck Jobs
Computational Results
Testing Problem Generation and the Algorithm Parameters
Numerical Computations and Comparison
Conclusion
Improved Construction Heuristics and Iterated Local Search for the Routing and Wavelength Assignment Problem
Introduction
Related Work
Lower Bounds
Benchmark Instances and Construction Algorithms
Experimental Results
Local Search
Experimental Results
Iterated Local Search
Experimental Results
Conclusion
Improving Metaheuristic Performance by Evolving a Variable Fitness Function
Introduction
Related Work
The Variable Fitness Function
Evolution
The Case Study Problem and Solution Heuristics
Computational Experiments
Conclusions
References
Improving Query Expansion with Stemming Terms: A New Genetic Algorithm Approach
Introduction
The Query Expansion System
The Genetic Algorithm
Fitness Functions Tested
Experimental Results
Selecting the Fitness Function
Tuning the GA Parameters
Overall Performance
Analyzing a Final Query
Conclusions
Inc: An Incremental Approach for Improving Local Search Heuristics
Introduction
SAT Problem
Stochastic Local-Search Heuristics for SAT
Incremental SAT
Evolutionary Algorithms and SAT Problem
The Inc Framework
Principles Behind Inc
Inc Optimisation Via GP
Experimental Results
Conclusion
Metaheuristics for the Bi-objective Ring Star Problem
Introduction
Preliminaries
Multi-objective Optimization
The Bi-objective Ring Star Problem
Metaheuristics for the Bi-objective Ring Star Problem
A Multi-objective Local Search
Multi-objective Evolutionary Algorithms
Application to the Bi-objective Ring Star Problem
Experiments
Experimental Protocol
Computational Results and Discussion
Conclusion
Multiobjective Prototype Optimization with Evolved Improvement Steps
Introduction
Multiobjective Optimization Techniques
Singleobjective POEMS
Multiobjective POEMS
Test Data and Experimental Setup
Results
Conclusions and Future Work
Optimising Multiple Kernels for SVM by Genetic Programming
Introduction
Related Work
Support Vector Machines
The Model for Evolving Complex MKs
The GP Representation of an MK
Genetic Operations
Fitness Assignment
Comparison to the Previous Models
Experiments and Discussion
Evolving the Complex Multiple Kernel Function
Comparison between the Complex Evolved MKs and the Linear MKs
Conclusion
Optimization of Menu Layouts by Means of Genetic Algorithms
Introduction
Designing and Optimizing a Menu System
Algorithm
Chromosome Structure and Genetic Operators
Fitness Function
An Example of Application
Conclusions and Future Work
A Path Relinking Approach with an Adaptive Mechanism to Control Parameters for the Vehicle Routing Problem with Time Windows
Introduction
Problem Definition
Local Search
Neighbor List
Neighborhoods
Evaluation Function $p(\sigma_k)$
Adaptive Mechanism to Control Parameters
Path Relinking Approach
Computational Experiments
Conclusion
Reactive Stochastic Local Search Algorithms for the Genomic Median Problem
Introduction
Problem Definition and Existing Work
Tabu Search and Iterated Local Search for the GMP
Tabu Search (TS) Algorithm
Iterated Local Search (ILS) Algorithm
Tuning of MedITaS Parameters
Reactive Search
Results
Comparison between Off-Line Tuned and Reactive Algorithms
Comparison to MedRByLS
Real World Instance
Discussion
Solving Graph Coloring Problems Using Learning Automata
Introduction
Previous Work and Recent Developments
Learning Automata for SAT-Encoded GCPs
A Learning SAT Automaton
Learning Automata Random Walk (LARW)
Experimental Results
Benchmark Instances
Search Trajectory
Run-Length-Distributions (RLDs)
Mean Search Cost
Conclusions
Author Index