Courses/CS 461/Winter 2006/Justin Wu/Week 9
From CSWiki
Contents |
[edit] TSP with GA
[edit] Applet
[edit] Source & Brief description
[edit] Description
This is a basic implementation of the Traveling Salesman Problem using a genetic algorithm. Unlike the models presented by Jeff and Dr. Abbott, this one is rather plain, and does not allow for the addition of nodes, the removal of nodes, or changing of node position. I use a steady state population and two point crossover, with children replacing non-mating members of the population set to be killed. Mutation is done by simply choosing random elements within the tour and swapping them.
[edit] Source
All of the following code is commented to explain what just about everything does.
[edit] City.java
Class definition for a city object. Basically does two things, 1) stores the (x,y) coordinates for each city object, and 2) houses a method which calculates the distance to another city/point (used to calculate the cost/fitness).
[edit] Chromosome.java
Class definition for a Chromosome object. Each chromosome is basically a tour, stored as a list which contains each city in its corresponding traversal order. This class also houses various methods, the most importance of which are getCost() which calculates the fitness of a given Chromosome, sortChromosome() which sorts our tour population in ascending order (so that the most fit tours are in the beginning), and mate() which is our crossover and mutation function.
[edit] TSP.java
Main class which houses the applet and handles all the graphics. It initializes and runs the main program, stopping when the score has not changed for 100 steps.
