Sample Problem

Now that we have a basic understanding of the genetic algorithm, let's use it to solve what will be an unconventional optimization problem. Rather than focus on the traditional numerical optimization problems, let's try to optimize a more symbolic problem of sequences of instructions (under the genre of evolutionary programming).

Overview

Consider a simple instruction set for a zero-address architecture (a stack architecture). Our virtual computer has no registers, only a stack for which instructions can manipulate the values on the stack. Our virtual computer recognizes only a handful of instructions; these are shown in Table 6.1.

 

Table 6.1: Simple Instruction Set.

Instruction	Description
DUP	Duplicate the top of the stack (stack: A => A A)
SWAP	Swap the top two elements of the stack (stack: A B => B A)
MUL	Multiply the top two elements of the stack (stack: 2 3 => 6)
ADD	Add the top two elements of the stack (stack: 2 3 => 5)
OVER	Duplicate the second item on the stack (stack: A B => B A B)
NOP	No-operation (filler)

These instructions are very simple, and can be used to solve a variety of functions. For example, if we wanted to compute the square of the top element of the stack, the following instruction sequence could be used ( assuming the top of the stack contains our input value):

• DUP

• MUL

This sequence duplicates the top of the stack and then multiples the two elements together (X * X, or X ² ).

Solution Encoding

Recall that we encode the solution of the problem, not the problem itself (since the problem is used as the fitness measure for our chromosomes). This problem is quite easy, since our chromosome simply represents a string of instructions in a contiguous block. We assign numerical values to each of the instructions (DUP = 0, through NOP = 5). Our encoding is then a contiguous string of bytes representing the stream of instructions.

Fitness Evaluation

Evaluating the fitness of a given chromosome is a simple process of executing the string of instructions that are contained within the chromosome. We prepare a simple stack of some depth, load the initial values onto the stack, and then execute each instruction sequentially until the program reaches the end, or the END instruction is reached.

The fitness value is then calculated as the difference between the resulting value on the stack to what was expected per our objective function (predefined for the test).

Recombination

For this problem, we'll use both crossover and mutation. The crossover operator simply breaks an instruction stream at a single point, and swaps the tails of each parent. Mutation is a random reassignment of the gene with a new instruction (since the chromosome represents the program, each gene is a single instruction).

On the CD  

The source code for the genetic algorithm can be found on the CD-ROM at ./software/ch6/genalg/.