Algorithms' local potential-breakfast included?
Nicole Weicker, Karsten Weicker · 2003
Most "no free lunch"-theorems do not make constructive statements since they are averaging over all possible problems or situations. Thus, they are of little help in practice. This work presents a different approach by examining the local potential of evolutionary algorithms for nearly arbitrary but fixed problems. Under certain assumptions concerning the locality of the algorithms it is shown that no local (non-adapting) search algorithm is superior to all other algorithms for all possible populations. Moreover, this approach provides a means to compare two algorithms in specific situations. Contrary to many papers, this possible comparison aims not at a general preference of one algorithm but rather at giving insights into the possibilities to adapt an algorithm to the current state of the search.