# Genetic TSP in Java with graph expansion

Posted on

Problem

This post presents my take on TSP (travelling salesman problem). The idea is to:

1. Take an input node `i`,
2. Compute the entire graph `G` reachable from `i`
3. Compute the all-pairs shortest paths for `G`
4. Shuffle the current tour specified number of times and choose the shortest one

`GeneticTSPSolver.java:`

``````package com.github.coderodde.tsp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
* This class implements the genetic TSP solver.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 29, 2022)
* @since 1.6 (Mar 29, 2022)
*/
public final class GeneticTSPSolver {

public static List<Node> findTSPSolution(Node seedNode, int iterations) {
Random random = new Random();
List<Node> tspGraph = GraphExpander.expandGraph(seedNode);

List<Node> bestTour = new ArrayList<>();
double bestTourCost = Double.POSITIVE_INFINITY;

for (int i = 0; i < iterations; ++i) {
Collections.shuffle(tspGraph, random);
double currentTourCost = computeTourCost(tspGraph, allPairsData);

if (bestTourCost > currentTourCost) {
bestTourCost = currentTourCost;
bestTour.clear();
}
}

return bestTour;
}

private static double

double tourCost = 0.0;

for (int i = 0; i < tour.size(); ++i) {
int index1 = i;
int index2 = (i + 1) % tour.size();
Node node1 = tour.get(index1);
Node node2 = tour.get(index2);
tourCost += data.getEdgeCost(node1, node2);
}

}
}
``````

`GraphExpander.java:`

``````package com.github.coderodde.tsp;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
* This class provides the method for computing graphs reachable from a seed
* node.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 29, 2022)
* @since 1.6 (Mar 29, 2022)
*/
public final class GraphExpander {

public static List<Node> expandGraph(Node seedNode) {
List<Node> graph = new ArrayList<>();
Deque<Node> queue = new ArrayDeque<>();
Set<Node> visitedSet = new HashSet<>();

while (!queue.isEmpty()) {
Node currentNode = queue.removeFirst();

for (Node childNode : currentNode.getNeighbors()) {
if (!visitedSet.contains(childNode)) {
}
}
}

return graph;
}
}
``````

`AllPairsShortestPathData.java:`

``````package com.github.coderodde.tsp;

import java.util.HashMap;
import java.util.Map;

private Map<Node, Map<Node, Double>> matrix = new HashMap<>();

public AllPairsShortestPathData(Map<Node, Map<Node, Double>> matrix) {
this.matrix = matrix;
}

public double getEdgeCost(Node tail, Node head) {
}
}
``````

`AllPairsShortestPathSolver.java:`

``````package com.github.coderodde.tsp;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
* This class provides the method for computing the all-pairs shortest paths via
* Floyd-Warshall algorithm.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 29, 2022)
* @since 1.6 (Mar 29, 2022)
*/

public static AllPairsShortestPathData solve(List<Node> graph) {
Map<Node, Map<Node, Double>> data = new HashMap<>(graph.size());

for (Node node : graph) {
Map<Node, Double> row = new HashMap<>();

for (Node node2 : graph) {
row.put(node2, Double.POSITIVE_INFINITY);
}

data.put(node, row);
}

for (Node tailNode : graph) {
for (Node headNode : tailNode.getNeighbors()) {
data.get(tailNode)

}
}

for (Node node : graph) {
data.get(node).put(node, 0.0);
}

for (Node node1 : graph) {
for (Node node2 : graph) {
for (Node node3 : graph) {
double tentativeCost = data.get(node2).get(node1) +
data.get(node1).get(node3);

if (data.get(node2).get(node3) > tentativeCost) {
data.get(node2).put(node3, tentativeCost);
}
}
}
}

}
}
``````

`Node.java:`

``````package com.github.coderodde.tsp;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
* This class defines the graph node type for the traveling salesman problem.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 29, 2022)
* @since 1.6 (Mar 29, 2022)
*/
public final class Node {

private final String name;
private final Map<Node, Double> neighborMap = new HashMap<>();

public Node(String name) {
this.name = Objects.requireNonNull(name, "The node name is null.");
}

public void addNeighbor(Node node, double weight) {
neighborMap.put(node, weight);
node.neighborMap.put(this, weight);
}

public double getWeightTo(Node node) {
return neighborMap.get(node);
}

public Collection<Node> getNeighbors() {
return neighborMap.keySet();
}

@Override
public boolean equals(Object o) {
if (!(o instanceof Node)) {
return false;
}

Node other = (Node) o;
return name.equals(other.name);
}

@Override
public int hashCode() {
int hash = 5;
hash = 59 * hash + Objects.hashCode(this.name);
return hash;
}

@Override
public String toString() {
return name;
}
}
``````

`Demo.java:`

``````package com.github.coderodde.tsp;

import java.util.List;

public final class Demo {

public static void main(String[] args) {
Node n1 = new Node("1");
Node n2 = new Node("2");
Node n3 = new Node("3");
Node n4 = new Node("4");
Node n5 = new Node("5");
Node n6 = new Node("6");

List<Node> tour = GeneticTSPSolver.findTSPSolution(n3, 3);

System.out.println("Tour:");

for (Node node : tour) {
System.out.println(node);
}

System.out.println("nCost: " + computeCost(tour));
}

private static double computeCost(List<Node> tour) {
double cost = 0.0;

for (int i = 0; i < tour.size(); ++i) {
int index1 = i;
int index2 = (i + 1) % tour.size();
Node node1 = tour.get(index1);
Node node2 = tour.get(index2);
cost += node1.getWeightTo(node2);
}

return cost;
}
}
```

**Critique request**

As always, please tell me anything that comes to mind.
``````

Solution

## Naming

You chose some confusing names.

• `tspGraph` is not a graph, but a path/tour through the graph, and the “tsp” prefix is not helpful, as in your program everything is about the Travelling Salesman Problem. I’d call the variable `candidateTour`.

• `List<Node> graph = new ArrayList<>();` in `GraphExpander`. Again, this isn’t a graph. This time it’s just a collection of nodes, the ones reachable from a given start node. So, I’d call it `reachableNodes`.

• `AllPairsShortestPathData.getEdgeCost()` If I understand correctly, this can be a multi-edge accumulated cost, if the two nodes aren’t adjacent. Your class name reflects that it isn’t about edges, but paths. But the access method is misleading. So, the name should be `getShortestPathCost(Node start, Node end)`.

You placed a few Javadoc comments, but not enough to understand your code, and the naming isn’t self-explanatory. My understanding of e.g. the `AllPairsShortestPathData` class would give Javadoc like:

``````/**
* The "matrix" of shortest-path (multi-step) costs when travelling
* from one node to another.
*/
// ...
}
``````

And in

``````/**
* This class provides the method for computing graphs reachable from a seed
* node.
* ...
*/
public final class GraphExpander {
// ...
}
``````

it should be “nodes” instead of “graphs”.

## Unit Tests

There are no unit tests.

Although the exact outcome of a random-based algorithm is unpredictable, you should create tests whether the resulting path is indeed a valid solution (visits each city, only connects neighbor cities, and so on).

For the lower-level classes, where no randomness is involved, test cases with specific result expectations can easily be created.

## Algorithm

I wouldn’t call your algorithm “genetic” (see Wikipedia). It’s pure Monte-Carlo. A genetic algorithm incrementally modifies and/or combines good candidates to reach even better ones. The key concepts of

• a population,
• crossover and
• mutation

all aren’t present in your program.

You use `Collections.shuffle()` to create the next candidate from a given one, which gives a completely random result, independent of the previous candidate. That’s a very “poor man’s” version of mutation, so much that it doesn’t deserve that label.

Your algorithm just calculates N random tours and returns the shortest one.

Finally, I’m not convinced that your program gives valid solutions for the classic Travelling Salesman Problem, where each city has to be visited exactly once. Your usage of the `AllPairsShortestPathData` class seems to imply that you also allow connections with intermediate city visits, but I might be wrong here.

You should state clearly which variant of the TSP you solve.