Constraint Satisfaction Using a Hybrid Evolutionary Hill-Climbing Algorithm that Performs Opportunistic Arc and Path Revision

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Stochastic Search

This paper introduces a hybrid evolutionary hillclimbing algorithm that quickly solves (!onstraint, Satisfaction Problems (CSPs). This hybrid uses opportunistic arc and path revision in an interleaved fashion to reduce the size of the search space and to realize when to quit if a CSP is based on an inconsistent, constraint network. This hybrid out,performs a well known hill-climbing algorithm, the Iterat,ive Descent. Method, on a test suit,e of 750 randomly generated CSPs.