The Royal Road for Genetic Algorithms

Genetic algorithms (GAs) play a major role in many artificial-life systems,but there is often little detailed understanding of why the GA performs as it does, and little theoretical basis on which to characterize the types of fitness landscapes that lead to successful GA performance. In this paper we propose a strategy for addressing these issues. Our strategy consists of defining a set of features of fitness landscapes that are particular lyrel- evant to the GA, and experimentally study-

ing how various configurations of these features affect the GA’s performance along a number of dimensions. In this paper we informally describe an initial set of proposed feature classes, describe in detail one such class (Royal Road" functions), and present some initial experimental results concerning the role of crossover and building blocks"on landscapes constructed from features of this class. 1 Introduction Evolutionary processes are central to our understanding of natural living systems, and will play an equally central role in attempts to create and study artificial life. Genetic algorithms (GAs) [13, 9] are an idealized computational model of Darwinian evolution based on the principles of genetic variation and natural selection. GAs have been employed in many artificial-life systems as a means of evolving artificial organisms, simulating ecologies, and modeling population evolution. In these and other applications, the GA’s task ⁄In Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life Cambridge, MA: MIT Press, 1992. is to search a fitness landscape for high values (where fitness can be either explicitly or implicitly defined), and GAs have been demonstrated to be efficient and powerful search techniques for a range of such problems (e.g., there are several examples in [19]). How- ever, the details of how the GA goes about searching a given landscape are not well understood. Consequently, there is little general understanding of what makes a problem hard or easy for a GA, and in particular, of the effects of various landscape features on the GA’s performance. In this paper we propose some new methods for addressing these fundamental issues concerning GAs, and present some initial experimental results. Our strategy involves defining a set of landscape features that are of particular relevance to GAs, constructing classes of landscapes containing these features in varying degrees, and studying in detail the effects of these features on the GA’s behavior. The idea is that this strategy will lead to a better understanding of how the GA works, and a better ability to predict the GA’s likely performance on a given landscape. Such long- term results would be of great importance to all researchers who use GAs in their models; we hope that they will also shed light on natural evolutionary systems. To date, several properties of fitness landscapes have been identified that can make the search for high-fitness values easy or hard for the GA. These include deception, sampling error, and the number of local optima in the landscape...

Website: web.cecs.pdx.edu | Filesize: -
No of Page(s): 11
Download The Royal Road for Genetic Algorithms: Fitness Landscapes and GA ....pdf