SAC 2000: Electronic Proceedings

Evolutionary Computation and Optimization Track

Track chairs:Roger L. Wainwright, University of Tulsa
Guenther R. Raidl, Vienna University of Technology
The following papers submitted to the Evolutionary Computation and Optimization Track in SAC 2000 are available on-line:
Simulation of Imprecise Ordinary Differential Equations Using Evolutionary Algorithms
Christoph ReichFH Furtwangen

This paper proposes a new approach, Interactive Evolutionary Algorithm Approach, for solving differential equations given imprecise initial values and/or imprecise differential equation parameters. A modified Evolutionary Algorithm with fuzzy sets representing the imprecise values simulates an imprecise ordinary differential equation.

Full paper
A Weighted Coding in a Genetic Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
Guenther R. RaidlVienna University of Technology, Austria
Bryant A. JulstromSt. Cloud State University, MN, USA

The coding by which chromosomes represent candidate solutions is a fundamental design choice in a genetic algorithm. This paper describes a novel coding of spanning trees in a genetic algorithm for the degree-constrained minimum spanning tree problem. For a connected, weighted graph, this problem seeks to identify the shortest spanning tree whose degree does not exceed an upper bound k>=2. In the coding, chromosomes are strings of numerical weights associated with the target graph's vertices. The weights temporarily bias the graph's edge costs, and an extension of Prim's algorithm, applied to the biased costs, identifies the feasible spanning tree a chromosome represents. This decoding algorithm enforces the degree constraint, so that all chromosomes represent valid solutions and there is no need to discard, repair, or penalize invalid chromosomes. On a set of hard graphs whose unconstrained minimum spanning trees are of high degree, a genetic algorithm that uses this coding identifies degree-constrained minimum spanning trees that are on average shorter than those found by several competing algorithms.

Full paper
Solving Very Large Crew Scheduling Problems to Optimality
Tallys Hoover YunesUniversity of Campinas
Arnaldo Vieira MouraUniversity of Campinas
Cid Carvalho de SouzaUniversity of Campinas

In this article, we present a hybrid methodology for the exact solution of large scale real world crew scheduling problems. Our approach integrates mathematical programming and constraint satisfaction techniques, taking advantage of their particular abilities in modeling and solving specific parts of the problem. An Integer Programming framework was responsible for guiding the overall search process and for obtaining lower bounds on the value of the optimal solution. Complex constraints were easily expressed, in a declarative way, using a Constraint Logic Programming language. Moreover, with an effective constraint-based model, the huge space of feasible solutions could be implicitly considered in a fairly efficient way. Our code was tested on real problem instances arising from the daily operation of an ordinary urban transit company that serves a major metropolitan area with an excess of two million inhabitants. Using a typical desktop PC, we were able find, in an acceptable running time, an optimal solution to instances with more than 1.5 billion entries.

Full paper
An Adaptive Evolutionary Algorithm for the Satisfiability Problem
Claudio RossiUniv. of Bologna, Padova and Venice Consortium
Elena MarchioriFree University Amsterdam
Joost N. KokLIACS, Leiden University

This paper introduces an adaptive heuristic-based evolutionary algorithm for the Satisfiability problem (SAT). The algorithm uses information about the best solutions found in the recent past in order to dynamically adapt the search strategy. Extensive experiments on standard benchmark problems are performed in order to asses the effectiveness of the algorithm. The results of the experiments indicate that this technique is rather successful: it improves on previous approaches based on evolutionary computation and it is competitive with the best heuristic algorithms for SAT.

Full paper
Page generated: 17:59 14 Feb 2000 by