Random Walks and Optimization

Random walks and other stochastic components are an intrinsic part of nature-inspired metaheursitic algorithms. They are often used as random numbers and randomization techniques in metaheuristic algorithms, and the efficiency of a metaheuristic algorithm may implicitly depend on the appropriate use of such randomization. In this chapter, we first introduce the fundamental ideas of random variables and theory of random walks and Lévy flights. Then, we discuss the relationship between optimization, random walks and Markov chains, followed by the analysis of step sizes and efficiency of an algorithm using the framework of Markov chain theory.