Introduction

This page contains demos of some of the results that have been achieved with GAs.

Review/Summary

Some notes from this excellent tutorial.

• Genetic Algorithms are a form of evolutionary computation, a form of computation that is inspired by natural evolutionary mechanisms.

• Biological Analogy: All organisms are made up of cells containing strings of DNA known as chromosomes which are composed of genestraits by expressing alleles, e.g., blue eye color. During sexual reproduction genetic material from one parent is recombined with genetic material from the other parent to form a new individual. This is called crossover. There can also be mutaation, which are small, random changes to the DNA. In nature an organism's fitness is determined by its environment.

• The Genetic Algorithm (GA) is a heuristic search algorithm that searches through an intractable search space by using crossover and mutation to vary a population of chromosomes until a certain fitness criterion is reached.

• NP Hard Problems. GAs are used on NP hard problems. An NP-hard problem is one for which it is possible to guess a solution by some non-deterministic algorithm that can be checked in polynomial time but for which there is no known polynomial time deterministic solution. (NP Hard List)

• Here's the Basic Algorithm

      procedure genetic_algorithm {
         set time t = 0;
         initialize the population, P(t);
         while the termination condition is not met do {
             evaluate the fitness of each member of P(t);
             select most fit members from P(t);
             produce the offspring of pairs of members using genetic operator;
             replace the weakest candidates of P(t) with these offspring;
             set time t = t + 1;
         }
      }
  

  GA Overview

  Selected Demos

  • Virtual Creatures
  • Traveling Salesman Problem
  • Auto Adaptable Walking Robot

  Hands-on Exercise

  We will be using the Java GA Toolkit to analyze and experiment with the Traveling Salesman Problem.

  1. Download and unzip the GaPlayground.zip file.

  2. Review the GaaFileHelp.txt. This describes the various parameters that must be set in order to specifiy a GA. It's terse but we can figure it out.

  3. Review the TspDemo.par parameter file. This Demo has 20 cities arranged on a circle. So the optimal path is easy to see (for humans). The GA sets up a population of 30 chromosomes, each of which contains 29 genes, one for each city. Each gene is represented by a 2-dimenional vector.

  4. To run Gaa on the TspDemo GA type the following command on the command line from within the GaPlayground directory:

     $ java -classpath gaa.jar:ScsGrid.jar:tabsplitter.jar:. GaaApplet TspDemo.par &