Algorithms for local search

So far, there have been several local search algorithms in this book, including Hill-Climbing and Simulated-Annealing. These algorithms can be directly applied to solving feasibility check tasks, provided that the correct estimation function is chosen. Since the goal is to find the assignment that ensures the execution of each expression, any evaluation function that counts the number of unexecuted expressions can be used for this purpose. In fact, it is this criterion that is used in the Min-Conf licts algorithm for CSP tasks.

All these algorithms make steps in the space of complete assignments, each time changing to the opposite (inverting) the truth value of one character. This space usually contains many local minima, for exit from which various forms of randomization are required. In recent years, many experiments have been carried out so that an acceptable compromise can be found between the desire for a “greedy” choice of the best successor and the need to get out of local minima with the help of a random choice of the next successor.

One of the simplest and most efficient algorithms that were created as a result of all this work is an algorithm called WalkSAT. At each iteration, this algorithm selects one unset expression, and in this expression selects one character to invert. This algorithm randomly switches between two ways of choosing a symbol to invert its truth value: first, the “conflict minimization” stage, in which the number of unexecuted expressions in the new state is minimized, and, second, the “random movement” stage in which one of the characters is randomly selected.

WalkSAT algorithm for verifying the feasibility by inverting the values ​​of variables at random. There are many versions of this algorithm.

function WalkSAT (clauses, p, max_flips) returns performing

saying

model or failure indicator

inputs : clauses, multiple expressions in propositional logic

p, probability of making a decision to make a move with "random

displacement, which is typically around 0.5

max_flips, the number of inversions that are allowed

perform before discarding further

attempts

model <- randomly selected assignment of values ​​true / false

characters in expressions

for i = 1 to max_flips do

if the model model runs multiple clauses

then return model

clause <- randomly selected expression from set

clauses, which is false in the model model

invert with model probability value

randomly selected character from clause

else invert the value of that character from the clause expression,

which maximizes the number of expressions executed

in a variety of clauses

return failure

Is an algorithm like WalkSAT really capable of performing productive work? Obviously, if it returns a certain model, then the input statement is indeed feasible. And what if it returns the failure indicator? Unfortunately, in this case it is impossible to determine whether the statement is impracticable, or whether this algorithm is simply required to be given a better chance of success. In this case, you can try to assign a parameter with the definition of the maximum number of inversions max_flips.

In this case, it can easily be shown that the Walks AT algorithm will eventually return some model (if it exists), provided that the probability of this is p> 0. This is due to the fact that there is always a sequence of inversions leading to an assignment that ensures the execution of the utterance, and such a sequence is ultimately generated as a result of the random selection of stages of the movement. Unfortunately, if the parameter max_flips is of infinite importance, and the statement is impracticable, this algorithm never finishes its work!

From this it follows that local search algorithms like Walks AT are most useful when you can really count on a solution; for example, tasks usually have solutions. On the other hand, a local search may not always detect impracticability, and this is precisely what is required when the task is to determine whether some statement follows from the knowledge base. For example, an agent cannot reliably use local search to prove that some square in the vampus world is safe. Instead, he can only say: "I thought about this for an hour, but I could not find at least one of the possible worlds in which this square is not safe."

And since this local search algorithm usually allows you to really quickly find a model, if it exists, then an agent using this algorithm should take into account that failure in trying to find a model of a statement using this algorithm most likely indicates that this statement is impossible. Of course, such a result is something other than proof, and the agent must think three times before risking his life based on similar results.