Why is a mix of greedy and random usually "best" for stochastic local search?
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.