I made a program in Java that solves the traveling salesman problem with a genetic algorithm

I happened to be doing research to solve with a genetic algorithm, I made it in the sense of increasing the number of steps for the future.

What is the traveling salesman problem?

It is a problem to think about the order in which the shortest passage can be made by writing a single stroke at a certain point in $ n $. If the number of cities to write in one stroke is $ n $, the number of possible combinations is $ \ frac {(n-1)!} {2} $.

What is a genetic algorithm?

It is one of the evolutionary computations that model the evolution of living things. The combination of solutions is regarded as a chromosome, and the solution is evolved by repeating genetic manipulations such as crossover and mutation to finally find the best solution.

Class flow

Since we are programming in Java, we will look at each class in order. The class diagram is as below. Click here for the references used in the design [^ 1]

The class of this program is as follows. Class.jpg

Among them, three genetic algorithms are used: ** TourWithGA **, ** Chromosome **, and ** Individuals **.

Regarding genetic manipulation, the Chromosome class implements methods for calculating mutation and gene compatibility, and the Individual class implements crossover, gene regeneration / selection, and elite conservation as methods.

As a strategy, it is created with reference to the branch exchange crossing (EXX) method proposed by Maekawa et al. [^ 2].

Behavior of genetic algorithm

Since there is a lot of source code, please see the source code for details. I will explain the specifications by focusing on the operation in the genetic algorithm.

Map data

Enter the location of the city in the traveling salesman problem as a CSV file. The contents of the CSV file are



In the first line, enter the number of cities that can be read. From the second line onward, enter the $ x $ and $ y $ coordinates of the city.

The main class of the program is ** tspSample **. When running in java

$ java tspSample <CSV file to read>

Please execute like this.

If the reading is successful,

city_num= 52
565.000	 575.000
25.0000	 185.000
345.000	 750.000
945.000	 685.000
845.000	 655.000

In this way, the number of read cities and city data are output to the console.

Initial individual generation

Generate an initial population that genetically manipulates Individuals type children. Specifically, in the Chromosome class, it is expressed as a permutation of cities as a gene sequence. The Tour class has a method called makeTour () that randomly generates a circuit. After generating the circuit, the circuit is copied to the gene sequence.

Goodness of fit calculation

Goodness of fit is calculated based on power law scaling. The number of cities $ n $ can be obtained from the Map class, and the circuit length $ l $ can be obtained by the getDistance () method of the Tour class.

\mathrm{Fitness} = \left(\frac{n}{l} \right)^3

Play / select

In the program, we use two Individuals classes. Perform genetic manipulation with ** parents **. In the next generation, ** children ** will survive the chromosomes in their parents based on the goodness of fit of the chromosomes. $ N_ {\ mathrm {p}} $ is stored in parents, and $ N_ {\ mathrm {c}} $ is stored in children. (However, $ N_ {\ mathrm {p}} \ geq N_ {\ mathrm {c}} $)

As for survival, the top $ N_ {\ mathrm {c}} $ chromosomes in parents are survived in descending order of fitness. However, since elite individuals must always be included in the population, if the goodness of fit of the chromosome with the highest goodness of fit in the population is greater than the goodness of fit of the elite chromosome, the elite individual is the best fit in the population. Update to a high chromosome. If not, replace the $ N_ {\ mathrm {c}} $ th chromosome with an elite chromosome.

The method of selecting the parent chromosome to be genetically engineered from the surviving population children is to calculate the expected value of survival in the parent individual from the following formula when the goodness of fit of the chromosome $ C_i $ in the children is $ f_i $.

\mathrm{Experience} = \frac{N_{\mathrm{p}} \times f_i}{N_{\mathrm{c}} \times \overline{f}}

$ \ Overline {f} $ is the average goodness of fit of chromosomes in children. Select the parent chromosome as many as the expected value (rounded down to the nearest whole number) and copy it to parent. The part after the decimal point is used for roulette selection.

For all chromosomes, if you select as many parents as you expect, parents will have some empty chromosomes. The remaining parents select their parents by roulette selection.

In order to prevent the same chromosome from being selected from the selected parents, two are randomly selected from the parent chromosomes so that they do not overlap, and they are crossed.

Crossing / mutation

Crossover is based on crossover probability, and mutation is based on mutation probability. See reference [2] for more information.

Gene correction

The genetic algorithm has a strong ability to find a global optimum solution, but has a weakness in local search ability. Therefore, the gene is corrected by the 2-opt method, which is one of the sequential improvement methods for the traveling salesman problem, before the calculation of the goodness of fit.

I actually tried it

$ N_ {\ mathrm {c}} = $ 100, $ N_ {\ mathrm {p}} = $ 150, maximum number of generations: 300, crossover probability: 0.8, mutation probability: 0.1, 52 city benchmark problem Berlin52 (optimal value) : 7544.366)). .. For the completed route, the data will be output to the result.csv in the same directory.

city_num= 52
565.000  575.000
25.0000  185.000
345.000  750.000


595.000  360.000
1340.00  725.000
1740.00  245.000
    0    7742.647
    1    7742.647
    2    7742.647
    3    7742.647
    4    7544.366
    5    7544.366
    6    7544.366


  294    7544.366
  295    7544.366
  296    7544.366
  297    7544.366
  298    7544.366
  299    7544.366
  300    7544.366
Processing time: 3157/ms

at the end

This branch exchange crossing is said to be the second best method after the branch assembly crossing method in solving the cyclic scheduling problem with a genetic algorithm. Currently, the method using branch assembly crossover is said to be the best method for solving the genetic algorithm for the traveling salesman problem. I would like to try it someday. Since I am studying scheduling problems, I would like to create a program that solves scheduling problems.

Source code

The source code is open to the public. The code may be dirty because I was in a lab that doesn't use much Java ... (Please feel free to give me advice.) https://github.com/SHIMADONBEY/GAwithTSP.git


[^ 2]: Maekawa, Tamaki, Kita, Nishikawa: A solution to the traveling salesman problem using a genetic algorithm, Proceedings of the Society of Automatic Measurements, Vol. 31, No. 5, pp. 598-605, 1995.

[^ 1]: Hatayama: GA Object Oriented Modeling, Ibaraki University Faculty of Engineering Graduation Research, 2010.

Recommended Posts

I made a program in Java that solves the traveling salesman problem with a genetic algorithm
I made a primality test program in Java
I made a simple calculation problem game in Java
[Beginner] I made a program to sell cakes in Java
How to deal with the type that I thought about writing a Java program for 2 years
Sample program that returns the hash value of a file in Java
I wrote a primality test program in Java
I made a rock-paper-scissors game in Java (CLI)
I wrote a prime factorization program in Java
I tried to make a program that searches for the target class from the process that is overloaded with Java
I made a Wrapper that calls KNP from Java
I tried to implement the Euclidean algorithm in Java
[Java] The problem that true was returned as a result of comparing Integer with ==
I made a JAVA framework "numatrix" that easily generates unique numbers in a distributed environment & multithreading.
A program (Java) that outputs the sum of odd and even numbers in an array
I made roulette in Java.
I made a mod that instantly calls a vehicle with Minecraft
Even in Java, I want to output true with a == 1 && a == 2 && a == 3
I made the "Sunshine Ikezaki game" I saw on Twitter in Java.
I can't create a Java class with a specific name in IntelliJ
I recently made a js app in the rumored Dart language
[Java] I want to perform distinct with the key in the object
Ruby: I made a FizzBuzz program!
I created a PDF in Java.
I made a shopify app @java
I made a GUI with Swing
I made an annotation in Java.
I tried to solve the past 10 questions that should be solved after registering with AtCoder in Java
A story that addresses the problem that REMOTE_ADDR cannot be acquired in a cluster built with Docker Swarm + Traefik (1.7).
I tried to make a sample program using the problem of database specialist in Domain Driven Design
Declare a method that has a Java return value with the return value data type
Dispatcher Pattern (a new design pattern that solves the Visitor Pattern's Expression Problem)
I tried learning Java with a series that beginners can understand clearly
Even in Java, I want to output true with a == 1 && a == 2 && a == 3 (PowerMockito edition)
I tried to solve the tribonacci sequence problem in Ruby, with recursion.
I wrote a Lambda function in Java and deployed it with SAM
I want to ForEach an array with a Lambda expression in Java
I made a class that can use JUMAN and KNP from Java
[LINE BOT] I made a ramen BOT with Java (Maven) + Heroku + Spring Boot (1)
[Java] Implement a function that uses a class implemented in the Builder pattern
I made a site that summarizes information on carbohydrate restriction with Vue.js
I tried a calendar problem in Ruby
After verifying the Monty Hall problem with Ruby, a story that I could understand well and did not understand well
I tried the new era in Java
I made a risky die with Ruby
I made a rock-paper-scissors app with kotlin
Split a string with ". (Dot)" in Java
I can't use SQS that can read the questionnaire with a scanner → I could use it after changing the java ver
I made a new Java deployment tool
I made a rock-paper-scissors app with android
Creating a sample program using the problem of a database specialist in DDD Improvement 2
Let's make a calculator application with Java ~ Create a display area in the window
Even in Java, I want to output true with a == 1 && a == 2 && a == 3 (Javassist second decoction)
Until you run a Java program with the AWS SDK local to Windows
Creating a sample program using the problem of a database specialist in DDD Improvement 1
I didn't know that inner classes could be defined in the [Java] interface
Validate the identity token of a user authenticated with AWS Cognito in Java
Even in Java, I want to output true with a == 1 && a == 2 && a == 3 (black magic edition)
Even in Java, I want to output true with a == 1 && a == 2 && a == 3 (gray magic that is not so much as black magic)
Even in Java, I want to output true with a == 1 && a == 2 && a == 3 (Royal road edition that is neither magic nor anything)
I made a Diff tool for Java files