12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'00) Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms Vancouver, British Columbia, Canada November 13-November 15 ISBN: 0-7695-0909-6
Abstract: Many stochastic search algorithms developed to solve large-scale constraint satisfaction problems in a practical time have the drawback of becoming stuck in locally minimal solutions which are not acceptable as solutions. We analyze a stochastic search algorithm from the viewpoint of local constraint structures of local minima. Using the graph-coloring problem with three colors, we studied the local graph structures around which concurrent conflicts arise. We present a key constraint structure, an LM pair; which may make up a local minimum, clarifying the mechanism of how conflicted coloring in an LM pair hinders stepwise refinement of hill-climbing. Experimental results show that LM pairs are strongly correlated with the search efficiency of the stochastic search algorithm.
Index Terms:
constraint theory; operations research; graph colouring; stochastic programming; local minimum structures; graph-coloring problems; stochastic constraint satisfaction; stochastic search algorithms; large-scale constraint satisfaction problems; locally minimal solutions; local constraint structures; local minima; graph-coloring problem; LM pair; stepwise refinement; hill-climbing
Citation:
F. Mizuno, S. Nishihara, "Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms," ictai, pp.0366, 12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'00), 2000 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb