Evolution Framework
home
GraphMeister application
source code

1 What is GraphMeister?

GraphMeister addresses the following NP-complete variation on the problem of Hamiltonian cycles: Let G be a connected weighted oriented graph with a distinguished base vertex k. Let t be a positive natural number. Find a t-tuple (p1, ..,pt) of pathes starting and ending in v such that each vertex of G is passed by one of the pathes and the maximum of the lengthes of p1,..,pt is minimal. The length of a path is defined as the sum of the weights of its edges.

Being a genetic algorithm, GraphMeister creates a population of random path tuples in G which start and end in k, and then evolves new pathes from the existing ones. The number of parent pathes needed to produce a child path is 2.
 

2 How does it work?

The edges starting from a vertex are internally numbered. A path is described by the sequence of numbers of consecutive edges it takes. These numbers are the genes of the path. It is assumed that there are never more than 7 edges starting from one vertex, so a gene is an octal digit. 7 means that the genome ends at this point, values x between 0 and 6 are interpreted as edge indices (if the number n of edges is less than n, we take x mod n). Now, if the genes are random values, the path will probably not end at k when its genome has reached its end, so it is complemented by a shortest path back to k (it is easy to compute shortest pathes from each vertex to k, GraphMeister performs that on the fly when it loads the graph (Even though it's easy, it can be time-consuming if the graph is big, hence the truth is that GraphMeister stores the computed return pathes in a file to read them in when the graph is loaded next time.)).
 

3 How is it used?

3.1 Startup

Let your CLASSPATH point to Evolution.jar, JGL3.1.0.jar and swingall.jar, and execute GraphMeister.jar. If nothing goes wrong, the main window will appear
main window 1
(check out my cool cursor for left-handed people :-) and tell you that it has no graph. By hitting the button "New Graph" you will be presented a dialog allowing you to choose a graph file, which you will need to have prepared prior to starting GraphMeister.
 

3.2 The graph file

The graph file contains all the information describing our graph. It is a text file with pretty simple syntax. The first line is the number n of vertices, including he base vertex k. The vertices are numbered from 0 (this is k), to n-1. The following lines each represent 1 or 2 edges and have the form

v    w    l    c

(whitespace between v, w, and l; between l and c no whitespace is needed) where v and w are vertex numbers, l is a floating-point number (the length (weight) of the edge(s)), and c is the optional character '!'. This line means: draw an edge of length l from v to w; if c ='!', that's all (a one-way edge), if c is missing, draw an edge of the same length l  from w to v  too (these 2 edges may be regarded as a 2-way edge). Here is an example. (See what it is? It is the triangle bounded by Limmatstr, Langstr and Röntgenstr in Kreis 5 of Zurich, Switzerland. One-way streets are respected. The base vertex is at the crossing of Röntgenstr and Heinrichstr, where I used to live in the squatted house Heinrichstr 137.)

If the graph described by this file is disconnected, GraphMeister will detect that and complain. The return pathes will be written into a file in the same directory as the graph file, the name of which is equal to the name of the graph file, with ".rp" appended.

By the way, the file I/O is the reason that GraphMeister cannot be an applet.
 

3.3 The pool

Once the graph is loaded and the return pathes calculated or read in, a genetic pool has to be created. Hitting "New Pool" brings up the following dialog
pool dialog

where you can enter the pool size, i.e. the number of individuals of the population, the "number of trucks", i.e. t, and the maximal path length. Press "OK", and GraphMeister will beep at you if entered nonsense. Otherwise, the pool will be created. You can cancel the pool creation by hitting "Cancel" in the main window:

main window 2

A future version will provide some information on the progress of the pool creation.
 
 

3.4 Evolution

Hitting the "Evolve" button produces the following dialog box
evolve dialog

where you have to enter the number of individuals to be replaced in each new generation, the mutation rate, the inertia, and the number of generations to breed. Cf the Evolution Framework manual for the definition of these terms.

Hitting "OK" will cause GraphMeister to beep at you if you entered nonsense, otherwise evolution will start, and the main window informs you about the progress and the current best individual.
 

3.5 Results

The whole population can be viewed by hitting the button "Show Results" (this even works while evolution is in progress). The results are presented in the following form:
result window

The left-hand panel of the horizontally split pane is the list of individuals: each line corresponds to an individual, the 1st number in the line is the index (the smaller, the better), the 2nd the number of vertices passed by this individual, the 3rd the maximum of the lengthes of the pathes of this individual (remember that an individual is a t-tuple of pathes), and the last number in this row is the value of the fitness function for this individual. In the right-hand panel you see the sequence of vertices passed by the pathes (trucks) that make up the individual.
 

4. To do


Evolution Framework
home