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
minimal. The length of a path is defined as the sum of the weights of its
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?
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
(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).
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
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
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
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:
A future version will provide some information on the progress of the
Hitting the "Evolve" button produces the following dialog box
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.
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:
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
Error handling. At the moment, the only error message you get is something
like "EvolutionException caught" in the status bar of the main window.
More comprehensive source code commentation