Package com.rubecula.darwin.examples.travelingsalesman

Traveling Salesman Example

See:
Description

Interface Summary

Swap<T>
TakesTravelTime
TravelTimes

Class Summary

Allele_Number	This class is at the heart of the solution to the traveling salesman problem.
Census_TS
CircularLinkedList<E>
Client
ClientMap	This is a map of all the clients.
ControlPanel_TS
EcoFactor_Clients	This eco factor represents the clients that currently need to be visited and their two-dimensional locations.
EcoFactor_TravelTimes	This eco factor represents the travel times between various clients.
EcoFactor_TS
Environment_TS
ExPhen_TS
Expresser_TS
FitnessEngine_TS
Locus_TS
Messages
Mortality_TS
Mutator_TS
OptionsPanel_TS
Organism_TS
Painter_TS
Phenotype_TS
Population_TS	Population model for the Traveling Salesman
Randomizer_TS
Registry_TS
Route	Class to represent a route between Client objects.
RouteFitness
TravelingSalesman
TravelingSalesmanOld	Example application which runs the peppered moth evolution without an interactive user interface.
TravelTimes_Map
Visualization_TS
VisualizationFactory_TS

Package com.rubecula.darwin.examples.travelingsalesman Description

Traveling Salesman Example

Contents:

• Copyright Notice
• Overview

Copyright Notice

Darwin Framework Project.
Copyright (C) 2003, 2007, 2009 Rubecula Software.
This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

Back to Top

Traveling Salesman Example

The Traveling Salesman Example is a non-biological example and utilizes an asexual evolutionary mechanism. The genome of the traveling salesman solution is haploid. The traveling salesman problem is one of the "NP-complete" problems and thus cannot readily be solved analytically. For more information on the problem see Wikipedia.

The method of solution in this Darwin application is described herein. Each organism represents a possible solution to a generic traveling salesman problem. In particular, the genome of an organism is a set of genes each of which can be one of two alleles: a stepper and a shifter. Each allele is followed by a number: for the stepper, it is the number of steps from our current position in the client list to a new position (when we get to the Nth position, we go back to the 0th position. The shifter number is the number of steps from our current position in the client list to the client which will be shifted to be immediately before the position we are currently at.

The numbers in the genome are of unlimited size, and are in base 3. A represents 0, C represents 1, G represents 2 and T is the terminator. For example:

        AT: 0
        CT: 1
        GT: 2
        CAT: 3
        CCT: 4
        CGT: 5
        GAT: 6
        GCT: 7
        GGT: 8
        CAAT: 9
        etc.
        

The codes for the two types (alleles) of gene are: TT (stepper), AAT (shifter). As the evolution of solutions continues, mutations arise which can lengthen a genome by inserting a new base, shorten it by removing a base, or simply to change the value of a base by replacing it by another.
The client set is not fixed but is part of the environment, and thus can be changed at any time. Indeed, after each generation, the client set is replaced by the newly ordered client set corresponding to the fastest route. We can think of this as an extended phenotype: we actually change the environment each generation. Fitness of a specific organism (with its specific genome) is determined according to the properties of the clients themselves. There is at least one ecofactor representing a depot - the starting and ending point of the route. Multiple depots are not yet implemented.
Fitness is determined by finding the actual sequence of clients specified by an organism's genome, then calculating the time taken to visit the clients in that sequence. The example provided is of Boston (home), 7 other cities in New England plus New York. Each is represented by two coordinates (kilometres from an abitrary origin). Furthermore, some of the cities have reduced speeds between that city and certain others.
During each generation, the fittest solutions are always reprieved from immediate death. This is not entirely satisfactory but this simulation does not in general work as well as a sex-based scheme with control population might (like the peppered moth).

A client can be added to the client list at any time (we usually add it to the end).

All classes in this application-specific package are, by definition, permanent.