Courses/CS 461/Winter 2006/Jeff Bailey/Homework 6
From CSWiki
Contents |
[edit] Traveling Salesman
After working with zombies for the first bunch of weeks, I decided to abandon this model and work on something more interesting. So, for this homework I decided to port the Mason TSP to Repast. In order to make this more interesting I decided to create a clean implementation without referring to the Mason code.
[edit] Download
Unzip and double click tsp.jar to run.
[edit] TSPModel.java
This is the main repast model that controls the visual representation, reporting, and steps. There are only two methods of real importance here. First and foremost is the step method.
Step gets called at every, well, step and serves as the primary execution control. This method extracts the cycles, or potential solutions, from the current population and sorts them. This is to make it more efficient. By sorting them, I am only required to test the most fit member of the population against the current best. It is also worth noting is the redraw flag. This was added to improve performance and reduce blinking that occurs when redrawing the solution. Rather than redraw the solution at each step, I only redraw when an improved solution exists.
At the end of each step, the population evolves. The details of which will be explained later.
public void step() {
Cycle[] cycles = population.getCycles();
Arrays.sort(cycles);
boolean redraw = false;
if (cycles[0].getLength() < bestCycle.getLength()) {
setBestCycle(cycles[0]);
redraw = true;
}
if (redraw) { redraw(); }
population.evolve();
}
Additionally, I added a reset method to the model. This method is called by my Node implementation whenever it is moved by the user.
public void reset() {
bestCycle = new Cycle(bestCycle.getNodes());
population = new Population(populationSize, bestCycle, this);
}
Finally, here is the redraw method that I referred to earlier. Since nodes maintain a reference to all connecting edges, I reset the edges rather than maintain a cloned array. This keeps the memory footprint managable.
protected void redraw() {
Node[] nodes = bestCycle.getNodes();
for (int i=0; i<nodes.length; i++) {
nodes[i].clearInEdges();
nodes[i].clearOutEdges();
}
for (int i=0; i<nodes.length-1; i++) {
EdgeFactory.linkNodes(nodes[i], nodes[i+1], new Edge(Color.RED)); }
EdgeFactory.linkNodes(nodes[nodes.length-1], nodes[0], new Edge(Color.RED));
surface.updateDisplay();
}
}
[edit] Population.java
Population represents the current solution population and handles evolution.
A population is created by supplying a size and sample cycle. This cycle is repeatedly mutated until a full population has been created.
public Population(int size, Cycle cycle, TSPModel model) {
this.size = size;
this.model = model;
this.cycles = new Cycle[size];
cycles[0] = cycle;
for (int i=1; i<size; i++) {
cycles[i] = cycle.getMutation();
}
Arrays.sort(cycles);
model.setBestCycle(cycles[0]);
}
Evolution is the process of producing replacement offspring for all but the best cycle. In my implementation, the best model is always a member of the evolved population.
public void evolve() {
Cycle[] newCycles = new Cycle[size];
newCycles[0] = model.getBestCycle();
for (int i=1; i<size; i++) {
newCycles[i] = getParent().getOffspring(getParent());
}
cycles = newCycles;
}
What sets apart my implementation from the MASON implementation is that I wanted to experiment with different methods of parent selection so three main methods were used.
private Cycle getParent() {
if (LOTTERY_SELECTION.equals(model.getParentSelection())) {
return lottery();
}
else if (TOURNAMENT_SELECTION.equals(model.getParentSelection())) {
return tournament();
}
else {
return random();
}
}
[edit] Lottery Selection
This advantage to this method is that it is biased towards selecting more fit parents without excluding the least fit. This works similar to the NBA Draft Lottery.
The idea behind the lottery is this. Each member in the population has a chance to be selected but those with better fitness are slightly more likely to be selected. To accomplish this, the population is sorted by fitness, with the most fit member getting n chances to be selected where n is the size of the population.
For example, assume the population containing [A B C D E]. In order of fitness, these are sorted into [E A B D C] where E is the most fit and C is the least fit. E would have 5 chances to be selected as a parent. A would have 4 chances. B would have 3 chances, etc.
The implementation of this idea is slightly different. Rather than a true lottery, I actually use a random number generator to generate a number between 1 and n(n+1)/2. I then use this number to determine which parent to return.
In the example above, values 1 - 5 would return E, 6 - 9 would return A, 10 - 12 would return B, and so on.
private Cycle lottery() {
Arrays.sort(cycles);
int max = (size * (size + 1)) / 2;
int rnd = Random.uniform.nextIntFromTo(1, max);
int threshold = 0;
for (int i=0; i<size; i++) {
threshold += (size - i);
if (rnd <= threshold) {
return cycles[i];
}
}
return (Cycle) cycles[size-1];
}
[edit] Random Selection
Random selection selects a parent at random. This is the most basic method of parent selection where all parents are considered equally fit.
private Cycle random() {
return cycles[Random.uniform.nextIntFromTo(0, size-1)];
}
[edit] Tournament Selection
Tournament selection is the implementation that was used in the MASON example. The benefit to this algorithm is that it is very simple and guarantees that the least fit solution will never become a parent.
This method works best when populations are relatively small in relation to the problem space. For sufficiently small populations, this selection criteria is actually better (in terms of performance) than the lottery selection criteria due to its simplicity.
The algorithm is simple, randomly select two parents and return the most fit.
private Cycle tournament() {
Cycle circuit1 = random();
Cycle circuit2 = random();
return circuit1.getLength() < circuit2.getLength() ? circuit1 : circuit2;
}
[edit] Cycle.java
A cycle is simply an ordered array of nodes that indicates the order in which each node is visited. Cycle also contains a helper method for computing the length of the cycle.
public Cycle(Node[] nodes) {
this.nodes = nodes;
this.length = -1;
}
public double getLength() {
if (length < 0) {
for (int i=0; i<nodes.length-1; i++) {
double dx = nodes[i].getX() - nodes[i+1].getX();
double dy = nodes[i].getY() - nodes[i+1].getY();
length += Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
}
double dx = nodes[nodes.length-1].getX() - nodes[0].getX();
double dy = nodes[nodes.length-1].getY() - nodes[0].getY();
length += Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
}
return length;
}
A cycle is also responsible for reproduction and mutation.
public Cycle getOffspring(Cycle mate) {
return new Cycle(crossover(nodes, mate.getNodes())).getMutation();
}
public Cycle getMutation() {
int rnd = Random.uniform.nextIntFromTo(0, 4);
int i = Random.uniform.nextIntFromTo(0, nodes.length-1);
int j = Random.uniform.nextIntFromTo(0, nodes.length-1);
switch (rnd) {
case 0 : return new Cycle(invert(this.nodes, i, j));
case 1 : return new Cycle(move(this.nodes, i, j));
case 2 : return new Cycle(shuffle(this.nodes));
case 3 : return new Cycle(swap(this.nodes, i, j));
default: return new Cycle(clone(this.nodes));
}
}
[edit] Reproduction
Reproduction is handled using the universal crossover method described in the MASON example. The implementation provided was somewhat incomplete in that it did not always return a child. I made some adjustments to guarantee that a child would always be produced.
private Node[] crossover(Node[] nodes1, Node[] nodes2) {
Node[] results = new Node[nodes.length];
Node[] source = nodes1;
results[0] = source[0];
for (int i=1; i<results.length; i++) {
source = source == nodes1 ? nodes2 : nodes1;
Node node = getNext(source, results[i-1]);
if (isUnused(results, node)) { results[i] = node; continue; }
node = getPrevious(source, results[i-1]);
if (isUnused(results, node)) { results[i] = node; continue; }
source = source == nodes1 ? nodes2 : nodes1;
node = getNext(source, results[i-1]);
if (isUnused(results, node)) { results[i] = node; continue; }
node = getPrevious(source, results[i-1]);
if (isUnused(results, node)) { results[i] = node; continue; }
for (int j=0; j<source.length; j++) {
if (isUnused(results, source[j])) { results[i] = source[j]; break; }
}
}
return results;
}
[edit] Mutation
Mutations are slightly more interesting and varied.
The first mutation is invert. This mutation inverts a subcycle. If we have the cycle [A B C D E F G] and call invert with the values 2 and 5, the result would be [A B F E D C G]. Notice the subcycle [C D E F] has been reversed to [F E D C] in place.
private Node[] invert(Node[] nodes, int from, int to) {
Node[] results = clone(nodes);
if (from > to) { int temp=from; from=to; to=temp; }
int pos=0;
for (int i=0; i<from; i++) results[pos++] = nodes[i];
for (int j=to; j>from -1; j--) results[pos++] = nodes[j];
for (int i=to +1; i<nodes.length; i++) results[pos++] = nodes[i];
return results;
}
The move mutation moves a node from one position to another, collapsing all nodes to fill in the gap. If we have the cycle [A B C D E F G] and call move with the values 2 and 5, the result would be [A B D E F C G]. C has been moved from index 2 to index 5 and other nodes have been collapsed together.
private Node[] move(Node[] nodes, int from, int to) {
Node[] results = new Node[nodes.length];
int i = 0;
for (int j=0; j<nodes.length; j++) {
if (i == to) results[i++] = nodes[from];
if (j != from) results[i++] = nodes[j];
if (i == to) results[i++] = nodes[from];
}
return results;
}
The shuffle mutation randomly shuffles the entire cycle, creating an entirely random ordering. This mutation isn't so much of a mutation but a convenient way to create random ordering of nodes.
private Node[] shuffle(Node[] nodes) {
Node[] results = clone(nodes);
for (int i=0; i<results.length; i++) {
int j = Random.uniform.nextIntFromTo(0, results.length - 1);
Node node = nodes[i];
nodes[i] = nodes[j];
nodes[j] = node;
}
return results;
}
The swap mutation moves a node from one position to another. If we have the cycle [A B C D E F G] and call swap with parameters 2 and 5, the result would be [A B F D E C G]. Notice the nodes at position 2 [C] and position 5 [F] have swapped locations.
private Node[] swap(Node[] nodes, int i, int j) {
Node[] results = clone(nodes);
if (i != j) {
Node node = results[i];
results[i] = nodes[j];
results[j] = node;
}
return results;
}
[edit] Node.java
A node is simply a drawable agent. The only interesting aspect to my implementation is that I maintain a reference to the TSPModel object so that I can call reset() whenever a node is moved by the user.
When a node is moved, The Repast display makes calls to setX() and setY(). I implemented a custom setX() to handle resetting.
public void setX(int x) {
super.setX(x);
model.reset();
}
[edit] Edge.java
An edge is a connection between two nodes. My implementation allows me to set a color in the constructor. I did this so that I could support the drawing of prior solutions before I realized the performance impact this had on the model. It was eventually scrapped but the implementation remained behind.
public class Edge extends DefaultDrawableEdge {
public Edge() {
}
public Edge(Color color) {
setColor(color);
}
}
[edit] Conclusions / Discussion
After playing with this model for a few hours, I discovered some interesting facts. Initially I believed that my lottery() method of parent selection would reign supreme but this wasn't the case. I believe this was the result of a small population size. For smaller sizes, it seems that the increased calculations required to handle the lottery outweighed the benefits of better selection criteria. For populations under 15, they performed pretty evenly. When I upped the population to 25 or more, I noticed that the overhead became much less of a factor.
Random selection was pretty terrible all the way around. So long as the problem remained small, a solution could be found, but once I upped my node count to 15 or 20 nodes, random selection fell apart.
