4.7 Solving CSPs using Stochastic Local Search

About

For large CSPs, systematically searching through the space of assignments of values to variables will prove unviable. This section considers a method intended to work in these very large spaces, stochastic local search. Stochastic local search does not systematically search the whole search space but they are designed to find solutions quickly on average. It does not guarantee that a solution will be found even if one exists, and so it is not able to prove that no solution exists. It is often the method of choice for applications where solutions are known to exist or are very likely to exist.

You can run each cell by selecting it and pressing Ctrl+Enter in Windows or Shift+Return in MacOS. Alternatively, you can click the Play button in the toolbar, to the left of the stop button. For more information, check out our AISpace2 Tutorial.

Feel free to modify our codes either in this notebook or somewhere outside (e.g. python files in /aipython/). If you want to modify our codes outside, you might find this helpful for how your changes can take effect.

You need to run the following command to import our pre-defined problems.


In [ ]:
# Run this to import pre-defined problems
from aipython.cspProblem import csp_simple1, csp_simple2, csp_simple3, csp_extended1, csp_extended2, csp_extended3, csp_crossword1, csp_crossword2, csp_crossword3, csp_crossword2d, csp_five_queens, csp_eight_queens

You can also define your own problems (how?).

You need to run the following command to import utilities that support your self-defined problems.


In [ ]:
# Run this to import utilities that support self-defined problems 
from aipython.cspProblem import (AND, CSP, FALSE, IMPLIES, NOT, OR, TRUE, XOR,
                                 Constraint, Equals, GreaterThan, IsFalse,
                                 IsTrue, LessThan, meet_at)

In [ ]:
from aipython.cspSLS import SLSearcher

sls = SLSearcher(csp=csp_simple1)

# Visualization options
# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options
sls.sleep_time = 0.2 # The time, in seconds, between each step in auto solving
sls.line_width = 2.0 # The thickness of edges
sls.text_size = 13 # The fontsize of the text
sls.detail_level = 2 # 0=no text, 1=truncated text, 2=full text

# Display the widget
display(sls)
sls.search(max_steps=500, prob_best=0, prob_anycon=1.0)
# prob_best - the probability of selecting a best variable (one involving the most conflicts)
# prob_anycon - the probability that the any-conflict strategy is used,
#    which selects a variable at random that is in a conflict, assuming that it is not picking a best variable

Plotting Runtime Distributions

Due to the stochastic nature of local search, multiple runs over the same problem will yield different results. Instead, we look at the runtime distribution - the number of runs that find a solution within a given number of steps.


In [ ]:
from aipython.cspSLSPlot import Runtime_distribution

p = Runtime_distribution(csp=csp_extended, xscale='log') # xscale is either 'linear' or 'log'
p.plot_run(num_runs=100, max_steps=1000, prob_best=0, prob_anycon=1.0)
p.plot_run(num_runs=100, max_steps=1000, prob_best=0.7, prob_anycon=1.0)

In [ ]: