Search, Binary Representations and Counting Optima
- 327 Downloads
Choosing a good representation is a vital component of solving any search problem. However, choosing a good representation for a problem is as difficult as choosing a good search algorithm for a problem. Wolpert and Мacready’s No Free Lunch theorem proves that no search algorithm is better than any other over all possible discrete functions. We elaborate on the No Free Lunch theorem by proving that there tend to be a small set of points that occur as local optima under almost all representations. Along with the analytical results, we provide some empirical evaluation of two representations commonly used in genetic algorithms: Binary Reflected Gray coding and standard Binary encoding.
Key wordsgenetic algorithms evolutionary computing search mathematical foundations
Unable to display preview. Download preview PDF.
- H. Mühlenbein, Evolution in time and space: The parallel genetic algorithm,In G. Rawlins, editor, Foundations of Genetic Algorithms, pp. 316–337, Morgan Kaufmann, 1991.Google Scholar
- Nicholas J. Radcliffe and Patrick D. Surry, Fundamental limitations on search algorithms: Evolutionary computing in perspective,In Jan van Leeuwen, editor, Lecture Notes in Computer Science, volume 1000 Springer-Verlag, 1995.Google Scholar
- Darrell Whitley, Keith Mathias, Soraya Rana, and John Dzubera, Evaluating evolutionary algorithms, Artificial Intelligence Journal, 85 August 1996.Google Scholar
- David H. Wolpert and William G. Macready, No free lunch theorems for search, Technical Report SFI-TR-95–02–010, Santa Fe Institute, July 1995.Google Scholar