Royal Road Functions

The Schema Theorem, by itself, addresses the positive effects of selection (allocating increasing samples of schemas with observed high performance) but only the negative aspects of crossover—that is, the extent to which it disrupts schemas. It does not address the question of how crossover works to recombine highly fit schemas, even though this is seen by many as the major source of the search power of genetic algorithms. The Building Block Hypothesis states that crossover combines short, observed high-performance schemas into increasingly fit candidate solutions, but does not give any detailed description of how this combination

To investigate schema processing and recombination in more detail, Stephanie Forrest, John Holland, and I designed a class of fitness landscapes, called Royal Road functions, that were meant to capture the essence of building blocks in an idealized form (Mitchell, Forrest, and Holland 1992; Forrest and Mitchell 1993b; Mitchell, Holland, and Forrest 1994).

The Building Block Hypothesis suggests two features of fitness landscapes that are particularly relevant to genetic algorithms: the presence of short, low-order, highly fit schemas; and the presence of intermediate "stepping stones"—intermediate-order higher-fitness schemas that result from combinations of the lower-order schemas and that, in turn, can combine to create even higher-fitness schemas.

A fitness function (Royal Road R i) that explicitly contains these features is illustrated in figure 4.1. R1 is defined using a list of schemas sj. Each sis given with a coefficient sj. The fitness R1 (X)of a bit string x is defined as

For example, if x is an instance of exactly two of the order-8 schemas, R1(x)= 16. Likewise, R1(111-1) = 64.

11I11III----------------------------------------

11111111 -------—

11 111 111 •""*••

;

""" :

i mini------------

1

------iiuuii------;

«^•uniiiiiimmiimimiimninnmmiiimminiiumu

Figure 4.1: An optimal string broken up into eight building blocks. The function R1(x) (where x is a bit string) is computed by summing the coefficients cs corresponding to each of the given schemas of which x is an instance. For example, R1(1111111100.. .0) = 8, and R1(1111111100.. .011111111) = 16. Here cs = order(s).

Given the Building Block Hypothesis, one might expect that the building-block structure of R1 will lay out a "royal road" for the GA to follow to the optimal string. One might also expect that the GA will outperform simple hill-climbing schemes, since a large number of bit positions must be optimized simultaneously in order to move from an instance of a lower-order schema (e.g., 11111111 **•••*) to an instance of a higherorder intermediate schema (e.g., 11111111 ******** 11111111 **...*). However, as will be described below, these expectations were overturned.

Fitness Resolution Fortress

Fitness Resolution Fortress

Learning About Fitness Resolution Fortress Can Have Amazing Benefits For Your Life And Success! Start Planning To Have Excellent Health And Fitness Today!

Get My Free Ebook


Post a comment