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 !