A new method for developing good value-ordering strategies in constraint satisfaction search is presented. Using an evolutionary technique called SANE, in which individual neurons evolve to cooperate and form a neural network, problem-specific knowledge can be discovered that results in better value-ordering decisions than those based on problem-general heuristics. A neural network was evolved in a chronological backtrack search to decide the ordering of cars in a resource-limited assembly line. The network required 1/30 of the backtracks of random ordering and 1/3 of the backtracks of the maximization of future options heuristic. The SANE approach should extend well to other domains where heuristic information is either difficult to discover or problem-specific.

PDF, PS

Technical Report AI94-218, Department of Computer Sciences, The University of Texas at Austin, 1994.

@TechReport{moriarty:constraint, title={Evolutionary Neural Networks For Value Ordering In Constraint Satisfaction Problems}, author={David E. Moriarty and Risto Miikkulainen}, number={AI94-218}, institution={Department of Computer Sciences, The University of Texas at Austin}, pages={11}, url="http://www.cs.utexas.edu/users/ai-lab/?moriarty:constraint", year={1994} }