RI | Publications | Improving Genetic Algorithms by Search Space Reduction (with Applications to Flow Shop Scheduling)

Text only version of this site

Improving Genetic Algorithms by Search Space Reduction (with Applications to Flow Shop Scheduling)
S. Chen and S. Smith
GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufmann, 1999.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [25 KB]
Compressed postscript (ps.gz) [35 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Crossover operators that preserve common components can also preserve representation level constraints. Consequently, these constraints can be used to beneficially reduce the search space. For example, in flow shop scheduling problems with order-based objectives (e.g. tardiness costs and earliness costs), search space reductions have been implemented with prece dence constraints. Experiments show that these (heuristically added) constraints can significantly improve the performance of Precedence Preserving Crossover--an operator which preserves common (order-based) schemata. Conversely, the performance of Uniform Order- Based Crossover (the best traditional sequencing operator) improves less--it is based on combination. Overall, the results suggest that condi tions exist where Precedence Preserving Crossover should be the best performing genetic sequencing operator.

Notes

Associated center: CIMDS
Associated lab/group: Intelligent Coordination and Logistics Laboratory

Text Reference

S. Chen and S. Smith, "Improving Genetic Algorithms by Search Space Reduction (with Applications to Flow Shop Scheduling)," GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufmann, 1999.

BibTeX Reference

@inproceedings{Chen_1999_556,
   author = "Stephen Chen and Stephen Smith",
   title = "Improving Genetic Algorithms by Search Space Reduction (with Applications to Flow Shop Scheduling)",
   booktitle = "GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference",
   year = "1999",
   publisher = "Morgan Kaufmann"
}