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

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. 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