1995 · 116 citations · 12 references
Natural SciencesDecision SciencesIndustrial EngineeringAlgorithmsOptimizationSchedulingCombinatorial OptimizationConstraint SatisfactionEvolutionary ComputationGenetic AlgorithmsHeuristic OptimizationMetaheuristic OptimizationEvolutionary AlgorithmsGenetic Algorithm OptimizationHybrid Evolutionary AlgorithmsHybrid Genetic AlgorithmsTimetabling
In this paper, we present a powerful hybrid genetic algorithm based around a heuristic timetabling framework. This combines a direct representation of the timetable with heuristic crossover operators to ensure that the most fundamental constraints are never violated. We explain how the population is seeded so as to produce a solution which cannot be outperformed by the heuristic method alone. We also see how the algorithm is guaranteed to always produce a feasible solution by hard coding constraints which must not be broken. Hybrid crossover operators are used, which propagate the most desirable features of the timetable to produce good quality solutions, even for large and highly constrained problems. Finally, we present the results from applying the algorithm to a particularly difficult problem, and demonstrate the variety of possible timetables that can be generated, depending upon the requirements of the user. 1 INTRODUCTION Recently, there has been a lot of attention paid to the...
12
New methods to color the vertices of a graph
Daniel Brélaz · Communications of the ACM · 1979 · 1.6K citations · Full text