Contents

• Introduction
• Genetic Algorithm Function Description
  • @GENALG
• An Example: Finding the Minimum of a Bumpy Function
• Conclusion

Introduction

Genetic algorithms (GA) solve optimization problems by modeling potential solutions as chromosomes which can breed with one another to produce better solutions through the forces of natural selection. Each solution or chromosome is made up of individual genes which are either one or zero. The fitness of a solution is determined by plugging the values of its genes into a function that returns a numerical fitness score. GA proceeds by randomly selecting two chromosomes and connecting a portion of one with a portion of the other to create an offspring chromosome. GA also injects some mutations by randomly flipping the value of a gene in a chromosome. If the fitness of the offspring is improved, it will probably survive to reproduce itself. However, if the fitness score is worse, the offspring will eventually die off. Over the course of generations, the fittest chromosomes will be represented more often in the total population. Hopefully, one of these fit chromosomes will be the optimal solution to the problem.

The ga plug-in lets you solve 1/0 combinatorial problems using GA in concert with the NExS spreadsheet. ga adds one new function to your spreadsheet: @GENALG for specifying the locations of your adjustable variables, the objective function you are trying to minimize or maximize, and some operational parameters that control the GA.

Genetic Algorithm Function Description

@GENALG

Syntax: @GENALG(M,F,V,S,G,P,U)

M = either of the strings ``MIN'' or ``MAX'' depending upon whether the fitness function is to be minimized or maximized, respectively.

F = any valid NExS cell expression that returns a numerical result which we will term the fitness. The expression can be linear or nonlinear in nature.

V = a range of cells containing ones or zeroes whose values affect the value of the F fitness expression.

S = either of the strings ``RANDOM'' or ``FIXED''. If ``RANDOM'' is chosen, then the initial population of solutions will contain randomly chosen ones and zeroes. If ``FIXED'' is chosen, a random set of solutions will still be generated, but a single seed solution will be added composed of the values initially found in the V range of cells. If not explicitly listed, this parameter defaults to ``RANDOM''.

G = any valid NExS expression that specifies the number of generations over which the populations of chromosomes will evolve. If not explicitly given, this parameter defaults to 10.

P = any valid NExS expression that specifies the size of the population of chromosomes that will be bred. If not explicitly given, this parameter defaults to 4 times the number of genes in a chromosome (i.e., four times the number of cells in V).

U = any valid NExS expresson that specifies the percentage of times a chromosome will be subjected to a mutation of a single gene. The remainder of the time, the chromosome will engage in normal breeding. If not explicitly given, this parameter defaults to 0.

The @GENALG function always returns 1. As @GENALG operates, it places status information in the three cells immediately below it:

1. the current generation,
2. the average fitness of the total population of chromosomes,
3. the fitness of the fittest chromosome in the population.

An Example: Finding the Minimum of a Bumpy Function

The use of ga is best shown by example. The spreadsheet for this roblem i mplein ex1.xs3. You can view the spreadsheet using the command nexs &. Once the spreadsheet is active, you must go under the Connections menu and allow NExS to Accept Connections. Then you must issue the command ga & to start the genetic algorithm plug-in which will connect itself to your NExS spreadsheet. Finally, use the File -> Open... dialog to read in the contents of the ex1.xs3 sheet.

ex1.xs3 describes the following function:

@COS(@PI/2*X/1000) - 0.1*@SIN(@PI/2*X/100)

which looks like this:

Standard gradient-ascent optimization algorithms will usually get stuck on one of the peaks on the sides of the large mountain. The hope is that a GA can evolve a population of solutions that will pin-point the highest peak at the top of the mountain.

But how do we represent a real variable like X using a set of 1/0 variables? That's simply done by using the 1/0 variables as a binary representation of X. The 1/0 variables in A1..K1 are used to calculate the signed integer value in cell L1:

L1 = -A1*2**10 + B1*2**9 + C1*2**8 + D1*2**7 + E1*2**6 +
      F1*2**5  + G1*2**4 + H1*2**3 + I1*2**2 + J1*2**1 + K1

The value in L1 is used in the fitness function in cell M1:

@COS(@PI/2*L1/1000) - 0.1*@SIN(@PI/2*L1/100)

The GA function for solving this problem is written in cell N1 as follows:

@GENALG("MAX",M1,A1..K1)

This will attempt to maximize the fitness given by the function in cell M1 as it is affected by the 1/0 variables in range A1..K1. After @GENALG iterates for several generations, the final answer given is X = -88 with a fitness value of 1.0886902. This is close to optimal.

You can specify values for some of the control parameters to try to improve the final result of the @GENALG function. To seed your population with your current fittest solutions, use the following:

@GENALG("MAX",M1,A1..K1,"FIXED")

To evolve over twenty generations, do the following:

@GENALG("MAX",M1,A1..K1,"FIXED",20)

To get more diversity in your potential solutions, use bigger populations like so:

@GENALG("MAX",M1,A1..K1,"FIXED",20,100)

Finally, to get unexpected variations on your solutions, apply some mutations as follows:

@GENALG("MAX",M1,A1..K1,"FIXED",20,100,0.05)

Conclusion

We discussed principles of genetic algorithms, the format of the @GENALG function provided by the ga NExS plug-in, and gave some examples of its use. Quite frankly, the examples are kind of cheesy. You can probably find better ones. Get any recent book on numerical optimization and it will have a section on GA. Try some of them using @GENALG. If @GENALG won't work, you can modify the code to provide what you need. Let us know what you've found!