Recently, I came across a real life problem of TSP. In this
problem, user is assigned a list of cities to visit, but is not required to come
back. At end point, he is again assigned to visit new set of cities.
This turns out to be a Hamiltonian path problem and not Hamiltonian cycle. I evaluated 2 different libraries for it namely JgraphtT and JGAP.
JgraphT seems to use MST-prim based approximation algorithm,
where Cost of tour in worst case is 2*optimalCost. It computes in polynomial
time and is very fast. To solve Hamiltonian path problem, you can add an extra
vertex say city 0. Next add edges from all vertices to city 0 with weight 0
(Remember input graph has to be a complete graph). After computation remove the
city 0 and all the corresponding edges.
Code for this is:
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import org.jgrapht.alg.HamiltonianCycle;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;
/**
* Using jgrpaht library
*
* @author pratyush
*
*/
public class HamiltonianCycleHelper {
private SimpleWeightedGraph<Long, DefaultWeightedEdge> g = new SimpleWeightedGraph<Long, DefaultWeightedEdge>(
DefaultWeightedEdge.class);
public void addVertex(Long id) {
g.addVertex(id);
}
public void addVertex(List<Long> ids) {
for (Long id : ids) {
g.addVertex(id);
}
}
public void addEdge(Long source, Long destination, Long weight) {
DefaultWeightedEdge edge = g.addEdge(source, destination);
g.setEdgeWeight(edge, weight);
}
public List<Long> execute() {
Set<Long> vertices = g.vertexSet();
addVertex(0l);
System.out.println(vertices);
for (Long v : vertices) {
if (v.longValue() == 0)
continue;
DefaultWeightedEdge edge = g.addEdge(0l, v);
g.setEdgeWeight(edge, 0);
}
List<Long> output = HamiltonianCycle
.getApproximateOptimalForCompleteGraph(g);
output.remove(Long.valueOf(0l));
return output;
}
public static void main(String args[]) {
List<Long> vertices = new ArrayList<Long>();
vertices.add(1l);
vertices.add(2l);
vertices.add(3l);
HamiltonianCycleHelper h = new HamiltonianCycleHelper();
h.addVertex(vertices);
h.addEdge(1l, 2l, 1l);
h.addEdge(1l, 3l, 5l);
h.addEdge(2l, 3l, 3l);
List<Long> output = h.execute();
System.out.println(output);
}
}
JgraphT results were good, but I wanted worst case cost to be better. Even though, I don’t know about genetic algorithms, I tried out JGAP library examples and it worked pretty well. If you check the example source code, you can modify the SalesmanFitnessFunction.java by commenting the return path:
protected double evaluate(final IChromosome a_subject) {
double s = 0;
Gene[] genes = a_subject.getGenes();
for (int i = 0; i < genes.length - 1; i++) {
s += m_salesman.distance(genes[i], genes[i + 1]);
}
// add cost of coming back:
//s += m_salesman.distance(genes[genes.length - 1], genes[0]);
return Integer.MAX_VALUE / 2 - s;
}
Also, modify TravellingSalesman.java, instead of just
TravellingSalesman t = new TravellingSalesman(); IChromosome optimal = t.findOptimalPath(null);Try something like:
public List<Long> compute() throws Exception {
IChromosome tempChromosome=null;
int maxEvolution = 12;
int maxPopulation = 12;
int steps = 10;
List<Long> output = new ArrayList<Long>();
double currentFitness = 0;
//Give few tries to find avg best path
while (maxEvolution <= 512) {
Configuration.reset();
setMaxEvolution(maxEvolution);
setPopulationSize(maxPopulation);
tempChromosome = findOptimalPath(null);
if (tempChromosome.getFitnessValue() > currentFitness) {
currentFitness = tempChromosome.getFitnessValue();
output = new ArrayList<Long>();
int geneVal;
Gene g[] = tempChromosome.getGenes();
for (int i = 0; i < g.length; i++) {
IntegerGene geneA = (IntegerGene) g[i];
geneVal = geneA.intValue();
output.add(geneVal);
}
}
maxEvolution += steps;
maxPopulation += steps;
}
return output;
}
Increasing the chromosome population makes computation slow, but results much better. Happy TSP solving !
