Local Search In Artificial Intelligence
Artificial intelligence is nothing more than finding the right solution at the right time.
So how does one aim to find the right solution? Through search techniques.
One such technique is local search.
Local search is a heuristic search technique. That is, it takes into consideration various information about the states, the path between them, the cost to change various states, etc. apart from the information that comes along with the state.
Now, you might be thinking as to what is local search? Like why local in the name?
Hold on a minute. Give your curiosity some time to grow. Because first, we’ll go through how local search works and in doing so, the name should be justified.
How local search works
In local search, the algorithm randomly selects a state. Weird, isn’t it?
But, once the state is selected, the algorithm then looks at all of its neighboring states and determines as to which of its neighbors is the most optimal for the problem.
This is a local approach because it does not look any further than all the neighboring states. Hence the name.
Now, once it selects the best neighbor, it moves on to that neighbor and repeats the process.
But then, how does it stop?
When the current state becomes the best and none of its neighbors outperforms it.
If this is the answer you were expecting, then my friend, you are wrong.
In fact, such a state is called a locally optimal point and is a serious problem in local search.
What?!! Yes.
So, our algorithm has not yet ended and we’ve reached a locally optimal point. Now what?
At this point, you have two options,
- Restart.
- Iteratively improve.
If you wish to restart, then you’ll restart at a different state or the same state but with slightly different search criteria. This would lead you to different neighbors, even if the initial state is the same.
As a result, you’ll reach a different locally optimal point this time. But you’ll sure reach one and then, you’ll repeat it again.
In iterative local search, you then twerk some things in the final state.
This is an interesting thing. Let me elaborate a bit on it.
Iterative Local Search
Iterative local search has a very narrow and particular set of problems that it can solve. These problems, at their core, have configurations.
Each state represents a seperate, unique configuration.
When a locally optimal point is achieved we change the configuration of the state a bit to meet our needs.
Then we are at a different state. Guess what we’ll do?
Change the configuration again. And again. And again.
Till when?
Till we don’t find an optimal solution or something else. We’ll cover this something later in the post.
Anyhow, can you think of any problem that has a configuration in its states? No? Think harder.
The classical traveling salesman problem. It could be solved in an amazing time with great accuracy using iterative local search.
Now, that you know what to do with a locally optimal point, you have come to a different problem. When to stop?
Because you will keep on encountering a locally optimal point, it’s a long term to write again and again, and you will remove it every time and then go on and on and on. Like an infinite loop.
Don’t worry, I’ll save you from this. You can thank me later. LOL!
How To Terminate A Local Search Algorithm?
There are two ways to do so. Choose what you may.
Finding the best result
As we talked earlier in iterative search, you find your result and you say, “NO MORE WORK NOW”.
And the algorithm terminates.
Let’s frame it a bit in technical words,
“When there exists no better solution to the problem than the current one, no matter how many states you pass through or steps you take, you’ve reached the most optimal solution and you stop.”
As great as it seems, it’s next to impossible. Think about it.
The problem space in many cases is infinite. You could never in your sanity be sure of such a solution.
Yes, for problems like TSP you can, but what about a search engine?
So what do they do? They do that something else that I talked about earlier. Here it comes,
Definite Time
We can’t specify the most optimal solution, so what we’ll do is specify the expected time. That is, we tell the algorithm to terminate after a particular time.
When it terminates, the best solution becomes our optimal solution.
This brings our two important properties of a local search algorithm,
- Indefinite time
- Approximation algorithm
Indefinite time
Since at any time we could terminate the algorithm and find a solution, we say that it works on indefinite time.
You could just ask anytime and the algorithm will give you something. It won’t disappoint you.
Approximation algorithm
As it gives the best solution available at that time, it is simply approximating the optimal solution to our best possible solution.
Thus it is an……approximation algorithm!!
This marks the end of this post. In my next post, I’ll cover a few important local search algorithms.
