Travelling salesman in java

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Travelling Salesman implemented in Java

pablopdomingos/Travelling-Salesman

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Travelling Salesman implemented in Java

Point initialPoint = new Point(48.853303, 2.354544, "Paris"); ArrayList upcoming = new ArrayList(); upcoming.add(new Point(52.516557, 13.408746, "Berlin")); upcoming.add(new Point(52.237060, 21.051575, "Warsaw")); upcoming.add(new Point(41.897041, 12.491685, "Rome")); Tree tree = new Tree.Builder() .explainCode() .generateGif() .withGifDelay(1.0) .build(); Solution solution = tree.searchInTree(upcoming, initialPoint, new StackImpl()); solution.print(); 

Generates a Gif to show how the program solved the problem step-by-step

• StackImpl() — Depth-first search
• QueueImpl() — Breadth-first search
• PriorityQueueImpl() — Breadth-first search with a priority queue

Explaining step-by-step what happening

Removing from branch node 0 Expanding node 0 ====================================== Creating node. Node id: 1 State: (Berlin) Node parent: 0 Action: Go to point (Berlin) Cost: 11.645377268483834 Depth: 1 ====================================== ====================================== Creating node. Node id: 2 State: (Warsaw) Node parent: 0 Action: Go to point (Warsaw) Cost: 19.00075734411684 Depth: 1 ====================================== ======================================

About

Travelling Salesman implemented in Java

Источник

Traveling Salesman Problem with Genetic Algorithms in Java

Genetic algorithms are a part of a family of algorithms for global optimization called Evolutionary Computation, which is comprised of artificial intelligence metaheuristics with randomization inspired by biology.

In the previous article, Introduction to Genetic Algorithms in Java, we’ve covered the terminology and theory behind all of the things you’d need to know to successfully implement a genetic algorithm.

Implementing a Genetic Algorithm

To showcase what we can do with genetic algorithms, let’s solve The Traveling Salesman Problem (TSP) in Java.

TSP formulation: A traveling salesman needs to go through n cities to sell his merchandise. There’s a road between each two cities, but some roads are longer and more dangerous than others. Given the cities and the cost of traveling between each two cities, what’s the cheapest way for the salesman to visit all of the cities and come back to the starting city, without passing through any city twice?

Although this may seem like a simple feat, it’s worth noting that this is an NP-hard problem. There’s no algorithm to solve it in polynomial time. Genetic algorithm can only approximate the solution.

Because the solution is rather long, I’ll be breaking it down function by function to explain it here. If you want to preview and/or try the entire implementation, you can find the IntelliJ project on GitHub.

Genome Representation

First, we need an individual to represent a candidate solution. Logically, for this we’ll use a class to store the random generation, fitness function, the fitness itself, etc.

To make it easier to calculate fitness for individuals and compare them, we’ll also make it implement Comparable :

public class SalesmanGenome implements Comparable < // . > 

Despite using a class, what our individual essentially is will be only one of its attributes. If we think of TSP, we could enumerate our cities from 0 to n-1 . A solution to the problem would be an array of cities so that the cost of going through them in that order is minimized.

For example, 0-3-1-2-0 . We can store that in an ArrayList because the Collections Framework makes it really convenient, but you can use any array-like structure.

The attributes of our class are as follows:

// The list with the cities in order in which they should be visited // This sequence represents the solution to the problem List genome; // Travel prices are handy to be able to calculate fitness int[][] travelPrices; // While the starting city doesn't change the solution of the problem, // it's handy to just pick one so you could rely on it being the same // across genomes int startingCity; int numberOfCities; int fitness; 

When it comes to constructors we’ll make two — one that makes a random genome, and one that takes an already made genome as an argument:

// Generates a random salesman public SalesmanGenome(int numberOfCities, int[][] travelPrices, int startingCity) < this.travelPrices = travelPrices; this.startingCity = startingCity; this.numberOfCities = numberOfCities; this.genome = randomSalesman(); this.fitness = this.calculateFitness(); > // Generates a salesman with a user-defined genome public SalesmanGenome(List permutationOfCities, int numberOfCities, int[][] travelPrices, int startingCity) < this.genome = permutationOfCities; this.travelPrices = travelPrices; this.startingCity = startingCity; this.numberOfCities = numberOfCities; this.fitness = this.calculateFitness(); > // Generates a random genome // Genomes are permutations of the list of cities, except the starting city // so we add them all to a list and shuffle private List randomSalesman()  < Listresult = new ArrayList(); for (int i = 0; i < numberOfCities; i++) < if (i != startingCity) result.add(i); > Collections.shuffle(result); return result; > 

Fitness Function

You may have noticed that we called the calculateFitness() method to assign a fitness value to the object attribute during construction. The function works by following the path laid out in the genome through the price matrix, and adding up the cost.

The fitness turns out to be the actual cost of taking certain path. We’ll want to minimize this cost, so we’ll be facing a minimization problem:

public int calculateFitness() < int fitness = 0; int currentCity = startingCity; // Calculating path cost for (int gene : genome) < fitness += travelPrices[currentCity][gene]; currentCity = gene; >// We have to add going back to the starting city to complete the circle // the genome is missing the starting city, and indexing starts at 0, which is why we subtract 2 fitness += travelPrices[genome.get(numberOfCities-2)][startingCity]; return fitness; > 

The Genetic Algorithm Class

The heart of the algorithm will take place in another class, called TravelingSalesman . This class will perform our evolution, and all of the other functions will be contained within it:

private int generationSize; private int genomeSize; private int numberOfCities; private int reproductionSize; private int maxIterations; private float mutationRate; private int[][] travelPrices; private int startingCity; private int targetFitness; private int tournamentSize; private SelectionType selectionType; 

• Generation size is the number of genomes/individuals in each generation/population. This parameter is also often called the population size.
• Genome size is the length of the genome ArrayList , which will be equal to the numberOfCities-1 . The two variables are separated for clarity in the rest of the code. This parameter is also often called the chromosome length.
• Reproduction size is the number of genomes who’ll be selected to reproduce to make the next generation. This parameter is also often called the crossover rate.
• Max iteration is the maximum number of generations the program will evolve before terminating, in case there’s no convergence before then.
• Mutation rate refers to the frequency of mutations when creating a new generation.
• Travel prices is a matrix of the prices of travel between each two cities — this matrix will have 0s on the diagonal and symmetrical values in its lower and upper triangle.
• Starting city is the index of the starting city.
• Target fitness is the fitness the best genome has to reach according to the objective function (which will in our implementation be the same as the fitness function) for the program to terminate early. Sometimes setting a target fitness can shorten a program if we only need a specific value or better. Here, if we want to keep our costs bellow a certain number, but don’t care how low exactly, we can use it to set that threshold.
• Tournament size is the size of the tournament for tournament selection.
• Selection type will determine the type of selection we’re using — we’ll implement both roulette and tournament. Here’s the enum for SelectionType :

public enum SelectionType  

Selection

Although the tournament selection method prevails in most cases, there are situations where you’d want to use other methods. Since a lot of genetic algorithms use the same codebase (the individuals and fitness functions change), it’s good practice to add more options to the algorithm.

We’ll be implementing both roulette and tournament selection:

// We select reproductionSize genomes based on the method // predefined in the attribute selectionType public List selection(List population)  < Listselected = new ArrayList<>(); SalesmanGenome winner; for (int i=0; i < reproductionSize; i++) < if (selectionType == SelectionType.ROULETTE) < selected.add(rouletteSelection(population)); >else if (selectionType == SelectionType.TOURNAMENT) < selected.add(tournamentSelection(population)); >> return selected; > public SalesmanGenome rouletteSelection(List population) < int totalFitness = population.stream().map(SalesmanGenome::getFitness).mapToInt(Integer::intValue).sum(); // We pick a random value - a point on our roulette wheel Random random = new Random(); int selectedValue = random.nextInt(totalFitness); // Because we're doing minimization, we need to use reciprocal // value so the probability of selecting a genome would be // inversely proportional to its fitness - the smaller the fitness // the higher the probability float recValue = (float) 1/selectedValue; // We add up values until we reach out recValue, and we pick the // genome that crossed the threshold float currentSum = 0; for (SalesmanGenome genome : population) < currentSum += (float) 1/genome.getFitness(); if (currentSum >= recValue) < return genome; > > // In case the return didn't happen in the loop above, we just // select at random int selectRandom = random.nextInt(generationSize); return population.get(selectRandom); > // A helper function to pick n random elements from the population // so we could enter them into a tournament public static List pickNRandomElements(List list, int n) < Random r = new Random(); int length = list.size(); if (length < n) return null; for (int i = length - 1; i >= length - n; --i) < Collections.swap(list, i , r.nextInt(i + 1)); > return list.subList(length - n, length); > // A simple implementation of the deterministic tournament - the best genome // always wins public SalesmanGenome tournamentSelection(List population)  < Listselected = pickNRandomElements(population, tournamentSize); return Collections.min(selected); > 

Crossover

The crossover for TSP is atypical. Because each genome is a permutation of the list of cities, we can’t just crossover two parents conventionally. Look at the following example (the starting city 0 is implicitly the first and last step):

What would happen if we crossed these two at the point denoted with a | ?

Источник