Travelling Salesman Problem solver

Question

I am writing a program that can implement algorithms to solve the TSP. My goals:

• The solver can record every algorithm step, so that the whole solving process can be later visualised by charts or animations
• It's easy to add new algorithm implementation
• End user has full control over the simulation parameters

I tried to do this before a year ago and even asked. Thought I will try this again with more knowledge.

Point - a basic structure used across the application to represent cities.

public class Point {

    private final double x;
    private final double y;

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public Point(Random r, int rangeX, int rangeY) {
        this.x = r.nextInt(rangeX);
        this.y = r.nextInt(rangeY);
    }

    public double calculateDistanceToPoint(Point p) {
        return Math.sqrt((this.x - p.x) * (this.x - p.x) + (this.y - p.y) * (this.y - p.y));
    }
}

---

General solver

public abstract class TSPSolver {

    protected ArrayList<Point> initialSetOfPoints = new ArrayList<>();

    public abstract void solve();

    public TSPSolver(int noOfPoints, Random r, int rangeX, int rangeY) {
        for (int i = 0; i < noOfPoints; i++) {
            addPoint(new Point(r, rangeX, rangeY));
        }
    }

    public TSPSolver(ArrayList<Point> points) {
        initialSetOfPoints = points;
    }

    public void addPoint(Point p) {
        initialSetOfPoints.add(p);
    }
}

---

Solver that can record and store history

public abstract class RecordableTSPSolver extends TSPSolver {

    protected SolutionHistory solutionHistory = new SolutionHistory();

    public RecordableTSPSolver(int noOfPoints, Random r, int rangeX, int rangeY) {
        super(noOfPoints, r, rangeX, rangeY);
    }

    public RecordableTSPSolver(ArrayList<Point> points) {
        super(points);
    }

    protected void recordStep(ArrayList<Point> currentSolution){
        solutionHistory.addStep(currentSolution);
    }

    public SolutionHistory getSolutionHistory() {
        return solutionHistory;
    }
}

---

Actual implementation of simulated annealing algorithm:

public class AnnealingSolver extends RecordableTSPSolver {

    private ArrayList<Point> currentSolution;
    private ArrayList<Point> newSolution;
    private ArrayList<Point> finalSolution;

    private double initialTemperature;
    private double minimalTemperature;
    private int maximumNumberOfTrials;
    private double coolingCoefficient;
    private int iterationsWithoutImprovement;

    public AnnealingSolver(int noOfPoints, Random r, int rangeX, int rangeY, double initialTemperature, double minimalTemperature, int maximumNumberOfTrials, double coolingCoefficient) {
        super(noOfPoints, r, rangeX, rangeY);
        initializeFields(initialTemperature, minimalTemperature, maximumNumberOfTrials, coolingCoefficient);
    }

    public AnnealingSolver(ArrayList<Point> points, double initialTemperature, double minimalTemperature, int maximumNumberOfTrials, double coolingCoefficient){
        super(points);
        initializeFields(initialTemperature, minimalTemperature, maximumNumberOfTrials, coolingCoefficient);
    }

    private void initializeFields(double initialTemperature, double minimalTemperature, int maximumNumberOfTrials, double coolingCoefficient) {
        this.initialTemperature = initialTemperature;
        this.minimalTemperature = minimalTemperature;
        this.maximumNumberOfTrials = maximumNumberOfTrials;
        this.coolingCoefficient = coolingCoefficient;
    }

    @Override
    public void solve() {
        currentSolution = initialSetOfPoints;
        while (solutionCanBeImproved()) {
            algorithmStep();
        }
        finalSolution = currentSolution;
    }

    public void algorithmStep() {
        newSolution = TSPUtils.swapTwoRandomEdges(currentSolution);
        if (isABetterCandidate()) {
            recordStep(newSolution);
            iterationsWithoutImprovement = 0;
            currentSolution = newSolution;
        } else {
            iterationsWithoutImprovement++;
        }
        lowerTemperature();
    }

    private boolean solutionCanBeImproved() {
        return initialTemperature > minimalTemperature && iterationsWithoutImprovement < maximumNumberOfTrials;
    }

    private void lowerTemperature() {
        initialTemperature = coolingCoefficient * initialTemperature;
    }

    private boolean isABetterCandidate() {
        double travelCostDifference = getTravelCostDifference();
        return travelCostDifference < 0 || (travelCostDifference > 0 && Math.exp(-travelCostDifference / initialTemperature) > Math.random());
    }

    private double getTravelCostDifference() {
        return TSPUtils.getTotalTourCost(newSolution) - TSPUtils.getTotalTourCost(currentSolution);
    }

    public ArrayList<Point> getFinalSolution() {
        return finalSolution;
    }
}

---

Utils class

public class TSPUtils {

    private TSPUtils(){}

    public static double getTotalTourCost(ArrayList<Point> points) {
        double cost = 0;
        if (points.size() > 2) {
            for (int i = 0; i < points.size() - 1; i++) {
                cost += points.get(i).calculateDistanceToPoint(points.get(i + 1));
            }
            cost += points.get(points.size()-1).calculateDistanceToPoint(points.get(0));
        }
        return cost;
    }

    public static ArrayList<Point> swapTwoRandomEdges(ArrayList<Point> points) {
        int range1 = 0, range2 = 0, min, max;
        int noOfPoints = points.size();
        ArrayList<Point> unchangedBeginning;
        ArrayList<Point> toBeReversed;
        ArrayList<Point> unchangedEnd;
        Random random = new Random();

        while (Math.abs(range1 - range2) < 2) {
            range1 = random.nextInt(noOfPoints);
            range2 = random.nextInt(noOfPoints);
        }
        min = Math.min(range1, range2);
        max = Math.max(range1, range2);

        unchangedBeginning = new ArrayList<>(points.subList(0, min));
        toBeReversed = new ArrayList<>(points.subList(min, max));
        Collections.reverse(toBeReversed);
        unchangedEnd = new ArrayList<>(points.subList(max, noOfPoints));

        ArrayList<Point> swapped = new ArrayList<>();
        swapped.addAll(unchangedBeginning);
        swapped.addAll(toBeReversed);
        swapped.addAll(unchangedEnd);
        return swapped;
    }
}

---

My thoughts:

1. Architecture - the shown AnnealingSolver solver implementation has 8 parameters when executing on random cities, 5 when supplying own cities. That's a lot of parameters. I was tempted to introduce a builder pattern for this at some point, but I don't know if it's a good idea. Also, the constructors are repeating a lot of code - maybe I should extract the common code into a private method?
2. Architecture - the RecordableTSPSolver class seems... weak. I mean, there is nothing forcing its child class to record history. At one point I had an interface Recordable which had one method recordStep, but of course it had to be public, and it just forced behaviour, which isn't good as far as I know. So I implemented what you can see above. Or maybe leave the recordStep method as protected and abstract to force implementation in child class and prevent end user from adding history?
3. Architecture - I also feel like the implementation of recording steps is weird, because if I wanted to have a class that just extends TSPSolver, it will be the same algorithm as in RecordableTSPSolver, but just without the one line of code that records the step. I'm sure there is some neat solution for this and I will try to find it.
4. Performance - storing history is expensive, so I'm thinking of rebuilding the history mechanism so that it stores initial points and a list of changes introduced by an iteration, instead of the full list of points every time.

This is a long post, so thank you for reading and attention. Your input will be most appreciated.

Answer 1

I will first make some suggestions and then I will come up with a solution (untested).

1. TSPUtils can be dissolved by putting the algorithm into TSPSolver where I would have expected it to be. ( refactoring: inline)
2. You have abstract algorithm elements in AnnealingSolver that should be moved to TSPSolver. The problem is that they are mixed with concrete concerns. You should separate the subject "Cooling" from canBeImproved, improve and useImprovement, that can be defined genericly in TSPSolver. (abstraction, refactoring: push up methods/fields)
3. So the fields currentSolution and newSolution. They will be best placed in TSPSolver as well as EVERY TSP needs them, doesn't matter what kind of use case. (abstraction, refactoring: push up fields)
4. The recording of intermediate result until the final result should be separated from the TSPSolver-class hierachy (composition over inheritance) I suggest the listener pattern to inform interested objects about new results in an abstract way. (dependency inversion)
5. Remove the responsibility to generate Points in the construction of TSPResolver. Remove the constructor completely and control Point-generation outside. The point is you say "Yeah you will need X points, but I will not tell you how they look like". One the other hand you have a constructor that says: "You will get these point! Work with it or die!". As these statements are incompatible you have this "ugly" inititializeFields()-method called in both constructors. If they were compatible you may have constructor call chains that make such init-methods obsolete. (remove redundancy, semantic issue)
6. You should separate use case concerns from the TSPSolver class-hierarchy. Favor composition over inheritance. Remove AnnealingSolver from the class-hierarchy and pass it to the constructor of TSPSolver in an abstraction like TSPUseCase.
7. You should decide if you want to make the result immutable, once it was calculated or return always new results if the underlying data changed. In my suggestion I deleted the artefact "getFinalResult()" and return the solution immediately after solve() was called. So you may change the set of points in the AnnealingSolver and it will be considered on the next call of solve(). Be aware that this solution is not thread save.

So here the code that follows my suggestions:

AnnealingSolver

public class AnnealingSolver implements TSPUseCase {


    private double initialTemperature;
    private double minimalTemperature;
    private int maximumNumberOfTrials;
    private double coolingCoefficient;
    private List<Point> initialPoints;


    public AnnealingSolver(List<Point> initialPoints, double initialTemperature, double minimalTemperature, int maximumNumberOfTrials, double coolingCoefficient){
        this.initialPoints = initialPoints;
        this.initialTemperature = initialTemperature;
        this.minimalTemperature = minimalTemperature;
        this.maximumNumberOfTrials = maximumNumberOfTrials;
        this.coolingCoefficient = coolingCoefficient;
    }


    @Override
    public void useImprovement(List<Point> points) {
        lowerTemperature();
    }


    @Override
    public boolean solutionCanBeImproved(int iterationsWithoutImprovement) {
        return initialTemperature > minimalTemperature && iterationsWithoutImprovement < maximumNumberOfTrials;
    }


    private void lowerTemperature() {
        initialTemperature = coolingCoefficient * initialTemperature;
    }


    @Override
    public boolean isABetterCandidate(double travelCostDifference) {
        return travelCostDifference < 0 || (travelCostDifference > 0 && Math.exp(-travelCostDifference / initialTemperature) > Math.random());
    }


    @Override
    public List<Point> getInitialPoints() {
        return this.initialPoints;
    }

}

SolutionHistory

public class SolutionHistory {

    public void addStep(List<Point> currentSolution) {
        for (Point point : currentSolution) {
            System.out.println(point.getX() + " " + point.getY());
        }
        // TODO ...
    }

}

TSPRecorder

public class TSPRecorder implements TSPSolverListener {


    protected SolutionHistory solutionHistory = new SolutionHistory();


    public SolutionHistory getSolutionHistory() {
        return solutionHistory;
    }


    @Override
    public void onNewSolution(List<Point> points) {
        solutionHistory.addStep(points);
    }


}

TSPSolver

public class TSPSolver {

    private int iterationsWithoutImprovement;

    private List<Point> currentSolution;
    private List<Point> newSolution;

    private TSPUseCase tspUseCase;

    private Set<TSPSolverListener> listeners;

    public TSPSolver(TSPUseCase tspUseCase) {
        this.tspUseCase = tspUseCase;
        this.listeners = new HashSet<>();
    }

    public static double getTotalTourCost(List<Point> points) {
        double cost = 0;
        if (points.size() > 2) {
            for (int i = 0; i < points.size() - 1; i++) {
                cost += points.get(i).calculateDistanceToPoint(points.get(i + 1));
            }
            cost += points.get(points.size()-1).calculateDistanceToPoint(points.get(0));
        }
        return cost;
    }

    public static ArrayList<Point> swapTwoRandomEdges(List<Point> points) {
        int range1 = 0, range2 = 0, min, max;
        int noOfPoints = points.size();
        ArrayList<Point> unchangedBeginning;
        ArrayList<Point> toBeReversed;
        ArrayList<Point> unchangedEnd;
        Random random = new Random();

        while (Math.abs(range1 - range2) < 2) {
            range1 = random.nextInt(noOfPoints);
            range2 = random.nextInt(noOfPoints);
        }
        min = Math.min(range1, range2);
        max = Math.max(range1, range2);

        unchangedBeginning = new ArrayList<>(points.subList(0, min));
        toBeReversed = new ArrayList<>(points.subList(min, max));
        Collections.reverse(toBeReversed);
        unchangedEnd = new ArrayList<>(points.subList(max, noOfPoints));

        ArrayList<Point> swapped = new ArrayList<>();
        swapped.addAll(unchangedBeginning);
        swapped.addAll(toBeReversed);
        swapped.addAll(unchangedEnd);
        return swapped;
    }


    protected double getTravelCostDifference() {
        return getTotalTourCost(newSolution) - getTotalTourCost(currentSolution);
    }


    public List<Point> solve() {

        currentSolution = tspUseCase.getInitialPoints();

        while (canBeImproved()) {
            improve();
            useImprovement();
        }

        return currentSolution;
    }


    protected void improve() {
        newSolution = swapTwoRandomEdges(currentSolution);
        if (isABetterCandidate()) {
            iterationsWithoutImprovement = 0;
            currentSolution = newSolution;
            notifyOnNewSolution();
        } else {
            iterationsWithoutImprovement++;
        }
    }


    private void notifyOnNewSolution() {
        for (TSPSolverListener listener : listeners) {
            listener.onNewSolution(currentSolution);
        }
    }

    protected int getIterationsWithoutImprovement() {
        return iterationsWithoutImprovement;
    }


    private boolean isABetterCandidate() {
        return this.tspUseCase.isABetterCandidate(getTravelCostDifference());
    }


    private boolean canBeImproved() {
        return this.tspUseCase.solutionCanBeImproved(getIterationsWithoutImprovement());
    }


    private void useImprovement() {
        this.tspUseCase.useImprovement(this.currentSolution);
    }


    public void add(TSPSolverListener listener) {
        listeners.add(listener);
    }

}

TSPSolverListener

public interface TSPSolverListener {

    void onNewSolution(List<Point> points);

}

TSPUseCase

public interface TSPUseCase {

    List<Point> getInitialPoints();

    void useImprovement(List<Point> points);

    boolean solutionCanBeImproved(int iterationsWithoutImprovement);

    boolean isABetterCandidate(double travelCostDifference);

}