7
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ which chapter of the book have you taken the formulae from? $\endgroup$ Jun 9 at 13:54
  • 1
    $\begingroup$ Chapter 5 "Search space structure and SLS performance", and section 5.4 is about the ruggedness. $\endgroup$ Jun 9 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.