Genetic TSP in Java with graph expansion

By 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);
        AllPairsShortestPathData allPairsData = 
                AllPairsShortestPathSolver.solve(tspGraph);
        
        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();
                bestTour.addAll(tspGraph);
            }
        }
        
        return bestTour;
    }
    
    private static double 
        computeTourCost(List<Node> tour, AllPairsShortestPathData data) {
            
        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);
        }
        
        return tourCost;
    }
}

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<>();
        
        queue.addLast(seedNode);
        visitedSet.add(seedNode);
        
        while (!queue.isEmpty()) {
            Node currentNode = queue.removeFirst();
            visitedSet.add(currentNode);
            graph.add(currentNode);
            
            for (Node childNode : currentNode.getNeighbors()) {
                if (!visitedSet.contains(childNode)) {
                    visitedSet.add(childNode);
                    queue.addLast(childNode);
                }
            }
        }
        
        return graph;
    }
}

AllPairsShortestPathData.java:

package com.github.coderodde.tsp;

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

public final class AllPairsShortestPathData {

    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) {
        return matrix.get(tail).get(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 final class AllPairsShortestPathSolver {

    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)
                    .put(headNode, tailNode.getWeightTo(headNode));
                
                data.get(headNode)
                    .put(tailNode, tailNode.getWeightTo(headNode));
            }
        }
        
        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);
                        node2.addNeighbor(node3, tentativeCost);
                    }
                }
            }
        }
        
        return new AllPairsShortestPathData(data);
    }
}

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");
        
        n1.addNeighbor(n3, 1.0);
        n2.addNeighbor(n3, 2.0);
        n3.addNeighbor(n4, 3.0);
        n3.addNeighbor(n5, 4.0);
        n6.addNeighbor(n4, 1.0);
        n6.addNeighbor(n5, 5.0);
        
        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).

Javadoc

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.
 */
public final class AllPairsShortestPathData {
    // ...
}

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.

Leave a Reply

Your email address will not be published. Required fields are marked *