To Stephen D. Scott's home page
Abstract
Genetic algorithms, while robust solution space searching methods, do not perform well when faced with general constraints. In some applications, for example the Traveling Salesperson Problem, problem-specific operators and codings can be developed. However, general constraints are still problematic. Described here are general methods to find an optimal or near-optimal solution to a problem while violating few if any constraints. We start by defining a function which measures the validity of a string. Validity measures how well a string satisfies the constraints. A method to approximate validity is also given. The structure of genetic algorithm is modified to incorporate the validity of strings. Preliminary experiments are performed and the results show that this theory has promise.
To Stephen D. Scott's home page
Last modified 06 June 2000.