com.rubecula.darwin.examples.travelingsalesman
Class TravelingSalesmanOld

java.lang.Object
  com.rubecula.darwin.examples.travelingsalesman.TravelingSalesmanOld

public class TravelingSalesmanOld
extends java.lang.Object

Example application which runs the peppered moth evolution without an interactive user interface.

In this example, we solve the traveling salesman problem in order (N^2) time (where N is the number of clients to be visited). A brute force approach would take order (N!) time.

This solution does not guarantee to find the best solution of course (unlike the brute force approach), but it is expected to find a pretty good solution.

The specific problem is for a New England Regional Sales Manager to visit 9 of his customers in and around New England and returning home (actually, the way the problem is posed, he can start at any client and must return there). The problem where he starts from a home/depot and returns there is of course slightly different (it's simply a question of solving the given problem and then arranging to find the closest pair of points and starting/finishing with side routes from those to home/depot.

The way that this problem is solved here is to start with four clients and to find the best solution (finding the best solution for three clients is trivial -- they form a triangle). We allow the solution to converge (in practice, we wait 2*N generations) and then add a new client (arbitrarily) to the route. Again, we allow the solution to converge. Step-by-step we keep adding one client to the (hopefully) best route for the existing clients.

A route (at first it is arbitrarily chosen) based on the current list of clients forms part of the environment in which the the organisms (candidate solutions) are trying to survive. At the end of each generation, the best current route is found and all of the genomes of the organisms are now normalized such that they now express that route. That way, we retain the same population of candidate genomes. When the solution converges (currently this is somewhat arbitrarily determined - see above), a new client is added.

At any time that we pick a new best route or we add a client to the route, we must signal to the all of the organisms that the environment has changed.

Finally, once we have converged after all 9 clients have been visited we report the results and quit.

The genetics of this solution are based on an asexual, that is haploid, life form (like a bacterium). The genome of an organims is a string of instructions which express a particular route. The mechanism for expression is that we start with the current best route (part of the environment) and step through the genes of the genome. Each gene will be either a rotation or a swap. A rotation rotates the route relative to the current route and the swap switches the 0th and Nth clients of the current route.

In practice, as the problem is defined, the shortest driving time to visit all 9 clients is 888 minutes. The best that this current version of the solution has managed is 890 minutes. In order to improve the likelihood of finding the right solution, we could adjust several factors: the number of generations we allow for convergence, the population size, the mutation rate, the fitness calculation, and perhaps other factors. All of these can be configured via the configuration file beansApplication.xml in the TravelingSalesmanOld resource package.

TODO When we update the ecofactor because of higher fitness, we should double-check that we're not increasing the travel time. Unknown Task

Author:

Robin Hillyard

Constructor Summary

TravelingSalesmanOld()

Method Summary

static void

main(java.lang.String[] args)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TravelingSalesmanOld

public TravelingSalesmanOld()

Method Detail

main

public static void main(java.lang.String[] args)

Parameters:

args -