How to avoid falling into the "local minima" trap?
There are several elementary techniques to try and move a search out of the basin of attraction of local optima. They include:


Probabalistically accepting worse solutions in the hope that this
will jump out of the current basin (like Metropolis-Hastings acceptance in Simulated Annealing). 
Maintaining a list of recently-encountered states (or attributes thereof) and not returning
to a recently-encountered one (like Tabu Search). 
Performing a random walk of a length determined by the current state of the search (an explicit 'Diversification strategy', e.g. as used in 'Reactive Tabu Search').


See the excellent (and free online) book 'Essentials of Metaheuristics' by Sean Luke for more details on these kind of techniques and some rules of thumb about when and how to use them.