Introduction

The motivation behind the developement of Flexible_GA is to simplify the programmer's problem when he/she desires to obtain an Genetic Algorithm (GA) that can solve a new problem. Three different versions of the GA have been previously developed:

• Traveling Salesman

  The Travelling Salesman problem: a gene is represented by an integer which is the identifier of a node/town on the proposed best route, and the chromosome is the whole list of nodes in order for the route. The problem is to find the circular route in a weighted graph that passes through each node once and only once with a minimal value of the sum of the arc distances.

• GenBitEvolve

  The GenBitEvolve problem: a gene is represented by a bit value, with the chromosome being effectively a bit string that can be mapped into a value for a variable. The problem involves the maximization of the value of a function of that variable.

• SinSeries

  The SinSeries problem: a gene is the floating-point value of a coefficient in a power series, with the chromosome being all the coefficients of the series of powers of angle^x, where 0 <= x <= n. The problem involves evolving the values of the individual coefficients so that the power series simulates the sine function.

Flexible_GA was designed to not only solve each of the three different problems; The GA provides a framework for expanding the range of problems to be solved to suit the needs of the implmentor. The "How-To" link above outlines the use of Flexible_GA, as well as a detailed instructions for modifying the existing code to tackle new problems.

^ TOP

Projects Using Flexible_GA

TSP Module for ArcView GIS 3.2a

ArcView is a desktop geographical information system that allows users to create dynamic maps, which can include information from many sources. Most of the data used in ArcView has a geographical componenet, which is directly connected to a physical location. This location can be part of a particular convention, such as a global positioning system (gps). The pictures below feature an elevation map, with geo-referenced well locations. The coordinates of each well can be fed as input to the Flexible_GA TSP algorithm. Two utilities were written to aid in the operation: the first converted the exported GIS coordinate file into a coordinate file used by Flexible_GA, and the second convert the winning tour into a line file, required for plotting the ending path on ArcView.

• Isolated layer showing 194 wells
  
  
• Starting TSP path plot of the wells
  
  
• Final TSP path plot
  
  
• Orthographic layer with TSP plot
  
  
• Data clollected on 20 runs of the Flexible_GA TSP on the 194 wells:
  • Log FIles
  • Screen Shots
  • Statistics

A

^ TOP

Downloads

• Flexible_GA 1.0

  TAR

  flexible_ga-1.0.tgz (5.7 MB)

  ZIP

  flexible_ga-1.0.zip (5.8 MB)

• PlotMatrix: Java TSP Plotting program

  TAR

  plotmatrix.tgz (7K)

  ZIP

  plotmatrix.zip (10K)

^ TOP

Flexible_GA Snapshots

TSP: Before and after

A random stating tour, and near-optimal final tour of a 225 node graph. Graph images of output tour file generated by "PlotMatrix" (see Downloads link)

• starting random tour, value:
  
• finished tour, value: 127283.070313
  

^ TOP

TSP Data

The following site contains all data gathered from runs conducted on graphs ranging from 225 to 984 nodes, using two different algorithms. The first (rungenalg) is the "classic" genetic algorithm, while the second (rungendrift) introduces the concept of genetic drift. The tests were also conducted with two different starting tours. One was completely random, the second was a partially evolved "blank" tour. The blank tour had a signifigantly lower weighted value than the random tour. The purpose was to see if we could get a better value from a lower starting tour.

• http://dreadnought.cse.nau.edu/~rbs