Fundamental Limitations on Search Algorithms: Evolutionary Computing in Perspective

Abstract. The past twenty years has seen a rapid growth of interest in stochas-tic search algorithms, particularly those inspired by natural processes in physics and biology. Impressive results have been demonstrated on complex practical op-timisation problems and related search applications taken from a variety of fields, but the theoretical understanding of these algorithms remains weak. This results partly from the insufficient attention that has been paid to results showing certain fundamental limitations on universal search algorithms, including the so-called “No Free Lunch ” Theorem. This paper extends these results and draws out some of their implications for the design of search algorithms, and for the construction of useful representations. The resulting insights focus attention on tailoring alg-orithms and representations to particular problem classes by exploiting domain knowledge. This highlights the fundamental importance of gaining a better the-oretical grasp of the ways in which such knowledge may be systematically ex-ploited as a major research agenda for the future.