Why is a mix of greedy and random usually "best" for stochastic local search?

Question

I read that a mix of "greedy" and "random" are ideal for stochastic local search (SLS), but I'm not sure why. It mentioned that the greedy finds the local minima and the randomness avoids getting trapped by the minima. What is the minima and how can you get trapped? Also, how does randomness avoid this? It seems like if it's truly random there's always a chance of ending up searching solutions that lead to dead ends multiple times (which seems like a waste of processing and avoidable)?

Answer 1

As an example of local/global minima, imagine being on a rugged, mountainous landscape, and you want to find the lowest point within some area. For a greedy search, every step you take will take you downhill. If you go downhill long enough, you'll eventually find a flat spot, which is a minimum - from here, there's no step you can take that will get you any lower. However, there's a nearby ridge, which if you crossed it, you could continue downhill to find an even lower spot, the global minimum (the true lowest point). Using your greedy approach, you'll never go uphill to cross the ridge, so you'll be stuck in the local minimum forever. If you occasionally take random steps (other than directly downhill), you have the opportunity to cross ridges that separate local minima, and you have a better chance of finding the global minimum. You are correct that in many cases, the random step won't help you cross a ridge, and will just take you up a mountain in the wrong direction, which is a waste of time. But unless we allow the algorithm to "explore" a bit, it will be content that the first minimum it finds is the best one, and will never get to the bottom.

Answer 2

The greedy action is the action that maximises some quantity in the present or near future. A stochastic action is an action that is random (it can be the greedy action or any other possible action).

For example, suppose that you are hungry. You can either choose to eat pizza, salad, fruits or fish. Pizza is your favourite food. On the other hand, you don't like much salad, fruits and fish, but you know that they are healthier than pizza. If you choose to eat pizza, then this is a greedy action. What quantiy are you maximising if you choose pizza? Your current happiness. If you randomly pick one of those (either pizza, salad, fruits or fish), then this is a stochastic (or random) action. The stochastic action can also happen to be pizza, but, in the next day, it might not be pizza, and, in general, it will not always be pizza.

Suppose that you always choose pizza. What's going to happen? In the long run, you will get fatter and your health will deteriorate. However, everytime you choose pizza, you will get happier in that moment (local maximum). If you randomly choose the food every time you want to eat, then it is more likely that you will eat also salad, fruits and fish. In the long run, this could be more beneficial for your health, hence this could avoid you getting trapped in the local maximum (being happy in the moment that you eat, but unhappier later in life because of the possible health problems).

In the context of artificial intelligence, the ideas are the same. There are several algorithms that use stochastic actions in order to avoid getting trapped in local extrema. For example, simulated annealing, ant colony optimisation algorithms, $Q$-learning (using $\epsilon$-greedy) or genetic algorithms. An example of local search (or greedy) algorithm is 2-opt (for the TSP problem).