Lecture
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.
Comments
To leave a comment
Logics
Terms: Logics