Genetic Algorithm Home Page(Perl Version)

 

 

Abstract

Genetic Algorithms are one type of learning algorithms patterened after the processes underlying evolution; shaping a population of individuals through the survival of its most fit members. They view learning as a competition among a population of evolving candidate problem solutions. A "fitness function evaluates each solution to decide whether it will contribute to the next generation of solutions. Then through operations anlogous to gene transfer in sexual reproduction, the algorithm creates a new population of candidate solutions. After evaluating each candidate, the algorithm selects a pair for recombination. Recombination uses genetic operators to produce new solutions that combine components of their parents. The two commonly known genetic operators are as follows:

  1. Crossover: One of the genetic operator is crossover which takes the two candidate solutions and divides them, swapping components to produce two new candidates.
  2. Mutation: This is another important genetic operator. It takes a single candidate and randomly changes some aspect of it.

The genetic algorithm continues until some termination requirement is met, such as having one or more candidate solutions whose fitness exceeds some threshold.

Return to top.

Quick Description on how to run the program

How to use the Genesis GA system:
To use the Genesis GA system, do the following. Create a directory called genesis. Copy the contents of ~juell/cs724pub/genesis/* to your genesis directory. Change directory to genesis. Type the command setup. For the questions "file name" and "suffix" type f1alt (F1ALT in lower case). For all of the other questions enter a carriage return. The carriage return causes it to use the specified default values. This will run the f1alt example. There are examples 1, 2, 3, 4 and 5. It is expected, that you will take f1alt and modify it so it solves your problem. The file f1alt.c contains two functions: doinit and eval. The function doinit is called once, at the start of processing and can be used to setup variables etc. The function eval has two parameter and returns a double floating point value. The two parameters are a pointer to a buffer and the length of the buffer in bytes. Each byte in the buffer represents one bit in the chromosome. The value returned by the function is the goodness metric for the chromosome represented by the buffer. Genesis does a valley decent, so the lowest possible metric value is the best answer.After you have modified the f1alt.c, it will generate the "data" file for you.

How to use the visualization tool:
Virtual Reality Modelling Language (VRML) is used for visualizing the Genetic Algorithm program in 3D space. The student can use this visualization tool to generate the VRML world. This tool is written in perl. Now copy the perl script version9.pl to your space and run it with "perl version9.pl" that will generate different vrml worlds. Then open the ga_index.html file from the common browser. This is the main interface from where you can navigate different visualizations that are interconnected with each other.

Return to top.

VRML worlds of Genetic Algorithm

This visualization appears when you click on the GenWorld button.

  • This visualization shows all the solutions in the search space.
  • The generations between 0-9 are represented by dark gray to red, 10-19 by green to brighter green, and 20~ by dark blue to bright blue
  • Sphere surrounded by red star is the worst solution of that generation
  • Mouse over the sphere will show the information about that solution in the upper right corner of this world.
  • Mouse over the red star will also show information in the status bar.
  • Click on the red star will show another visualization with other solutions of that generation.

This visualization appears when you click on MinGen button.

  • This visualization contains only the min solutions of each generation.
  • Mouse over the sphere shows the information about that solution in the status bar.
  • Click on the sphere shows another visualizations with all other solutions of that generation in the lower frame.
  • Click on the purple square box shows the time stamp of generation. It also shows movie by changing visualizations for each generation. The movie is shown in the lower frame.
  • SpaceShip viewpoint gives a tour in the world.

This is the screen shot after you click on the purple box.

This is the screen shot after you click on the sphere.

This visualization appears when you click on the BarCahrt button.

  • This world shows all the generations at a time with the help of bar chart.
  • To view all the generations, click on the green box.
  • To on/off a particular generation, click on the red box corresponding to that generation.
  • To show the information about that generation, move the mouse over the bar chart of that generation.
  • To hide the information about that generation, again move the mouse over the bar chart of that generation.

Screen shot after clicking on the red box.

This visualization appears when you click on the SheetChart button.

  • This world shows all the generations at a time with the help of sheet chart.
  • To view all the generations, click on the green box.
  • To on/off a particular generation, click on the red box corresponding to that generation.
  • To show the information about that generation, move the mouse over the sheet chart of that generation.
  • To hide the information about that generation, again move the mouse over the sheet chart of that generation.

Screen shot after clicking on the red box.

Return to top.

Resources used for this visualization

Return to top.