Terrain Ruggedness Index for optimization problem

Question

If I want to study the smoothness of the energy landscape of a cost function, is there any metric similar to Terrain Ruggedness Index used in geology?

Answer 1

Yes. The ruggedness of a landscape is a measure of how much variability is observed between neighbouring solutions, and it can be computed using the landscape correlation function. Rugged landscapes (with a very low correlation) typically have lots of local minima and are more difficult to traverse than smooth landscapes (correlation close to 1).

For a fixed distance $i$, the landscape correlation function is defined as \begin{equation} \rho(i) = \frac{\langle f(s)\cdot f(s^\prime)\rangle_{d(s,s^\prime)=i}-\langle f(s)\rangle^2}{\langle f^2(s)\rangle - \langle f(s)\rangle^2} \end{equation} where $f(s)$ is the objective function value of a solution $s$, $\langle f(s) \rangle$ is the average of the solution value for all the solutions $s$ in the search space $S$, and $\langle f(s)\cdot f(s^\prime)\rangle_{d(s,s^\prime)=i}$ is the average of $f(s)\cdot f(s^\prime)$ for all the pairs of solutions $s,s^\prime$ at distance $i$ in $S$.

Of course, the formula is not usable in practice, because it requires to analyze the entire search space. One alternative is to perform a random walk on the search space, and compute the empirical autocorrelation function on the sequence of solution values $f_1, f_2, \dots, f_m$ observed: \begin{equation} r(i) = \frac{1/(m-i)\cdot \sum_{k=1}^{m-i}(f_k-\bar{f})\cdot(f_{k+i}-\bar{f})}{1/m \cdot \sum_{k=1}^m (f_k-\bar{f})^2} \end{equation} where $m$ is the length of the random walk, and $\bar{f}$ is the average of the sequence of values $f_1, f_2, \dots, f_m$ observed in the random walk. This formula gives information about the correlation between solutions at distance $i$ in the random walk.

As a reference, the formulas are taken from the book "Stochastic Local Search: Foundations and Applications" (Hoos and Stützle). Course slides about this topic can be found here.