How does natural selection process escape from local optima?
From your profile, I see that you have some knowledge in computer science so I will try to use some terms from the field of machine learning!

Natural Selection

Natural Selection (NS) can only lead a population toward local optimum. In other words, NS is like a greedy algorithm. Mutations and genetic drift do not behave like a greedy algorithm.

Genetic drift

Genetic drift may allow to go toward the other direction than the heuristic of NS allowing eventually to reach another attractor. This concept is called shifting balance theory.

Mutations

Mutations can allow all sorts of jump! Mutations Causing large jumps are generally called large-effect mutations (see this section of the wikipedia article for more information).

Fitness landscape changes through time

Also note that the fitness landscape is not stable over time. The fitness landscape depends upon the environment the individuals experience. It would therefore be naive to assume that a specific population had to go through a specific fitness valley in the past just because the valley exists today.

Sexual reproduction and recombination

The fitness landscape analogy depicts the genotype - fitness relationship (some fitness landscape depict the phenotype - fitness relationship but I will ignore them here) for a given individual. One can place all individuals of a population over this landscape and may have some feeling of where the population position over the landscape is. However, this may be misleading.

The fitness landscape is highly multidimensional (one dimension for each amino acid and there are billions of them) and therefore through sexual reproduction and recombination, it is possible that an offspring finds itself in a totally different attractor than the rest of the population. As such, in presence of sexual reproduction and recombination, NS only could lead a jump from one attractor to another one (see Bergman and Feldman 1992). This effect is even more considerable in presence of epistasis.