Lab 3020 - Genetic Algorithm Exploration

Description

By the year 2025, it is predicted that a computer will have the processsing power of the human mind. It seems to me that the software for such computational giants will have to be fundamentally different than what we write today.

For most of the projects I use in class, there is a desired outcome and an algorithm students develop and implement to achieve that outcome. In 1956, Isacc Asimov wrote his short story Someday, containing these lines:

The world needs more people who can design advanced computer circuits and do proper programming...     Programming: that's when you set up problems for the giant computers like Multivac to work on.

It gets harder all the time to find people who can really run computers. Anyone can keep an eye on the controls and check off answers and put through routine problems. The trick is to expand research and figure out ways to ask the right questions, and that's hard.

It's been almost 50 years since Asimov's short story appeared in Earth is Room Enough. It was prophetic in many ways. Today we are expanding research and have powerful computers that can give us answers to the right questions - difficult questions - if we know how to ask them and let the computer figure out how to solve them.

The idea of a "genetic algorithm" caught my interest as one way to use computational power to solve problems where the exact sequence of steps is not known in advance. Basically, the idea is to develop a small group of possible solutions, try them out, see which ones worked best, then generate new possibilites based on the best characteristics of the first generation. This process continues until a workable solution is found.

I set out to develop a student lab that would be a Genetic Algorithm Exploration suitable for use in a high school classroom. This lab can be implemented using many different data structures. For example, the list of steps for each path could be implemented as a linked list. The roulette wheel algorithm could be implemented in a circular linked list. A backtracking algorithm to remove any loops from the path could be implemented with a stack, or a linked list using bidirectional ListIterators could work.

This project can easily be extended. For example, a simplistic crossover mechanism to combine the genetic material (paths) of two selected parents works, but there is room for improvement. Since the output is primarily visual, changes in the combining and mutating functions for creating offspring are immediately observable. Here is a sample output of a run of this program:

ga picture

This project is also structured such that it can be broken into pieces and each piece worked on independently by students or teams of students.

The Project

In this project, we will use a Genetic Algorithm (GA) to find a path through a world, as shown above. It's not a maze; there are many paths from the upper left to the lower right target. Therefore techniques suitable for mazes, with their one entrance, one exit and one path between them, do not apply. The result shown is the first path that found its way through the world one one of several potential paths. The goal of a GA is to find a solution to a problem, not guaranteeing it is the optimum solution.

The Algorithm

Initially, you need to load a world map for the GA to traverse. The example world.txt file provided shows the simple plain-text format of the map. If you create you own, I suggest you place wall obstacles at interesting places to test your program. Be sure to include several paths to the goal. The start location is the red square in the upper left. The goal is the red square in the lower right.

The baisc algorithm is to start with a handful of possible solutions, try them out, select the best of those, and breed a new generation. Try those out, select the best, breed again and repeat until the solution is found.

Here is a more detailed algorithm for this GA problem. This algorithm was used in the solution, but intentionally leaves room for experimentation and improvement.

Load the world, setup initial display.
Randomly set up 12 short paths to get the GA started.

While the path to the goal has not been found:

    Try the current group of paths (12) by having them walk 
    on the map.  If the path hits a wall, don't move but
    just move on to the next step.
    
    Evaluate the fitness of each path based on how close to the
    goal it ended.
    
    Generate 12 new paths, in groups of four, to replace the initial paths:

    First four replacement paths:
        Select two paths, usually the best ones but not always.
        These paths are parents.
        Make two children using genetic info from each parent.
        Mutate the children.
        Add one step to the children.
        Add one step to a copy of the parents.
        Save (these four) paths.

    Second four replacement paths:
        Get four new candidates by repeating the process
        for the first four.

    Last four replacement paths:
        Make four renegades - like a parent to a point but
        then off on their own.
        Save these four paths
    
    This gives twelve paths total, all with the same path sequence 
    length, all descended from the best of the previous generation.

The process of testing, generating evolved offspring, and continuing util the solution is found is our example of a GA. You mission is to code the essential parts of the project, while others (the controller and the view components) are provided for you.

Files/Classes Required

The Java source code explained and provided in this section is enough to get started with your GA Exploration. Download all the java source files into one directory, type javac *java and then java GA to see the skeleton code operate. It simply draws an empty world, waits for you to click the Run button, then steps across diagonally to show the simulation timer firing.

Files/Classes
GA Genetic Algorithm controller class. Sets up the model and the view for the project. (complete code provided)
GAview Genetic Algorithm view class. Simply displays the grid. Has one method of interest: updateView which requests a repaint. (complete code provided)
GAmodel Genetic Algorithm model class. Constructor must load the data file, populate the grid and generate the initial candidates. Has a timer method to run the simulation. tracePath takes a path and puts it in the grid so it can be displayed by the view component. actionPerformed: get here each step of the simulation. makes 12 new paths, traces them out, checks to see if goal was reached and if so, forces final view. (skeleton code provided)
Path Path class. A Path is a sequence of directions (L, R, U, or D) in a string that would like to get to the goal and a group of methods for dealing with the path. Each Path has an id for graphing purposes. Important: here is where new paths are born. methods of importance: addStep(), mutate(), and prunePath(). (no code provided: student exercise)
RouletteWheel This class is used to choose parents for breeding as described in the notes below. (no code provided: student exercise)
world.txt A simple text file describing one possible world for the GA to solve.
Notes on Genetics

The Path class has the ability to generate a new path from the genetic material of two parents. The genetic material in this simulation is nothing more than the path. What is required is a constructor that takes two parents as arguments. Extracting their DNA (paths), combine the information in some interesting way. The resulting child may be more fit that either parent (as determined by where it ends after walking through the map). This requires a crossover and a mutation. There are several good references for these techniques, including this one.

Notes on the Roulette Wheel

Usually in a roulette wheel, every possible outcome has equal probablility. That's because the sectors are all of equal angles. For a genetic algorithm to pick parents that are more likely to produce superior offspring, all potential parents (paths) can be thought of as being on the roulette wheel with varying sector angles. In our proposed solution, there are twelve paths to choose from. If they were equally fit, each would occupy (360/12) or 30 degrees on the wheel.

A particularly fit parent may be on the wheel with an angle of greater than 30 degrees while one less fit would occupy less than 30 degrees. If you then think of spinning the wheel, you are more likely to get a parent that has shown to be more fit, but you are not guaranteed that outcome. This variability allows a diverse population to try to navigate the world map searching for the goal.

Notes on Mutation

In nature, a small change in DNA can make a big change in the organism's behavior. Similarly, changing one turn left to a turn right may change the path significantly. After a child is created from the paths of both parents, the childs path may be mutated at a random place to a random direction.

Notes on the addStep method

The purpose of the organism is to go somewhere. With this in mind, random motion is not a good choice. Random motion would, over time, result on average in no movement at all. The addStep method of path adds another step on the end of the path. The initial paths start short but must grow as the simulation proceeds. Since the organism wants to go somewhere (to the goal), usually it should continue going in the direction it is already going. Suggested: 50% probability of continuing in same direction, 25% probability of turning left, 25% probability of turning right.


Copyright © 2010 by Asylum Computer Services LLC Return to CS Labs