# Genetic Algorithm for TSP

This is something that I am proud of and would like to have people dissect and tell me where my faults are in. I feel that if I open my best for criticism then maybe it will reveal the deep seeded bad habits in my coding.

I know about the null format for the frame in the main class is not kosher. So, please skip over that and focus more on the algorithm.

## Map

    import java.util.ArrayList;
import java.util.Random;
import java.util.*;

public class Map
{

private ArrayList<Integer> cityIndex = new ArrayList<Integer>(); //= {0,5,12,16,44,52,57,72,79,90,95}; indexes of the cities placed into the map... the values on the right are the indexes of the test map in the project description
private ArrayList<Character> cityNames = new ArrayList<Character>(); //= {'K','J','I','H','D','B','G','C','F','A','E'}; names of the cities on the map...  the values on the right are the names of the test map in the project description
private int numCities = 0; //the number of cities in the map passed in from the runner class. Can be checked with the cities passed in the runGA method to keep from crashing.
private int rows; //the number of rows in the map
private int columns; // the number of columns in the map
public int shortestRouteDistance; // the distance found to be shortest after running the GA. It is accessed from the runner class
public int[] shortestRoute; // the indexes of the shortest route found
public char[] shortestRouteNames; // the names of the waypoints in the shortes route. It is accessed from the runner class

//random variable
private Random rand = new Random();

/**
* The Map constructor takes in a 2D array of characters. It checks to see if there is a character in each of the indexes in the array
*/
public Map(char[][] array)
{
//set the rows to the height of the array
rows = array.length;
//set the columns to the width of the array
columns = array[0].length;

//add the city indexs and names to the proper arraylists
for(int i = 0; i<array.length; i++)
{
for(int j = 0; j <array[i].length; j++)
{
if(array[i][j] != ' ')
{
cityIndex.add((array[i].length * i) + (j)); // the index is calculated to be the y position times the width of the array plus the x pos
cityNames.add(array[i][j]);// the name is added to the arraylist at the same position as the index in the cityIndex arraylis
//another city was found to be passed in
numCities++;
}
}
}

}

/*
* The runGA method is the method that takes in the input from the user and spits out a fastest route.
*/
public void runGA(int cities, int popSize, int numGen, int crossProb, int mutProb)
{

int[][] newArray = new int[popSize][cities+1]; //create a 2d array to hold all the routes... the routes are held in the rows of this 2d array
int indexSR = 0; // the index of the shortest route found in each generation. The default value is 0 at each generation since the fastest route found is placed at index 0
int startRand = 1; //This variable holds the position at which to start creating random arrays. If there is no crossover or mutation the value will be one... if there is crossover or mutation the value is 2 if there is both the value is 3
int[] tempArray; //used for rearranging the newArray

newArray[0] = randArray(cities); //start the algorithm with a random array
shortestRoute = newArray[0]; //set the shortest route to the first array created

//start the generations
for(int gen = 0; gen<numGen; gen++)
{

//fill the 2d array with randomly generated routes up to the population size, starting at the correct index
for(int i = startRand; i<popSize; i++)
{
newArray[i] = randArray(cities);
}

startRand = 1; //reset the value to one

//compare all the routes and find the shortest route
for(int i = 0; i<popSize; i++)
{

if(routeDistance(newArray[i]) < routeDistance(newArray[indexSR])) //if the route distance ofthe next array is less than the shortest route found set the array to be the new shortest route
{
tempArray = newArray[indexSR]; //save old shortest route
shortestRoute = newArray[i]; //create a new shortest route
indexSR = i; // the place of the new shortest route is saved
}

}

//set the shortest route to the first route.
newArray[0] = shortestRoute;
indexSR = 0; //the shortest route is found to be the first route

//set the shortest distance to the shortest route's distance
shortestRouteDistance = routeDistance(shortestRoute);

//check for mutation. Mutation and crossover can only happen once in each generation.
if(rand.nextInt(100)<mutProb-1)
{
newArray[startRand] = mutatedArray(shortestRoute);
startRand++;
}

//check for crossover
if(rand.nextInt(100)<crossProb-1)
{
crossedArray(shortestRoute, randArray(cities));
startRand++;
}

}

//initialize the shortest route names to be the same length as the shortest route found
shortestRouteNames = new char[shortestRoute.length];

/*
* find the appropriate names by searching through the arraylists.
*/
for(int i = 0; i< shortestRouteNames.length; i++)
{
for(int j = 0; j < cityIndex.size(); j++)
{
if(shortestRoute[i] == cityIndex.get(j))
{
shortestRouteNames[i] = cityNames.get(j);
}
}
}

}

/*
* This method creates arrays with randomly accessed values from the arraylists of indexes passed in
*/
private int[] randArray(int number)
{
ArrayList<Integer> cityArrayList = new ArrayList<Integer>();
ArrayList<Integer> randCities = new ArrayList<Integer>();

//This will create a new arraylist as a copy from the city index array list
for(int i = 0; i<number; i++)
{
}

for(int i = 0; i<number; i++)
{
randCities.add(cityArrayList.remove(rand.nextInt(cityArrayList.size()))); // this will remove values from the copied arraylist randomly making a new random list
}

int[] randArray = new int[numCities+1]; //creates an array to pass back to the runGA method the +1 is to make room for the first city to be visited again at the end

//fill the array with the random arraylist
for(int i = 0; i<number; i++)
{
randArray[i] = randCities.get(i).intValue();
}

//set the last value in the array to the first value
randArray[randArray.length-1] = randArray[0];

return randArray;
}

/*
* This method switches the values in 2 indexes of the array excluding the first and last index
*/
private int[] mutatedArray(int[] array)
{
int mutIndex1 = rand.nextInt(array.length-1);
int mutIndex2 = rand.nextInt(array.length-1);
int store;

if(mutIndex1 == 0)
{
mutIndex1++;
}

if(mutIndex1 == (array.length-1))
{
mutIndex1--;
}

if(mutIndex2 == 0)
{
mutIndex2++;
}

if(mutIndex2 == (array.length-1))
{
mutIndex2--;
}

store = array[mutIndex1];
array[mutIndex1] = array[mutIndex2];
array[mutIndex2] = store;

return array;
}

private int[] crossedArray(int[] array1, int[] array2)
{
int temp;
int distance = rand.nextInt(array1.length/2);
int resetDistance = 0;

for(int i = 0; i<distance; i++)
{
temp = array1[i];
array1[i] = array2[i];
array2[i] = temp;

if(properRoute(array1) == false || properRoute(array2) == false){
for(int j = resetDistance; j <=i; j++)
{
array1[j] = array2[j];
array2[j] = temp;
resetDistance = j;
}
}
}

return array1;
}

private boolean properRoute(int[] array)
{
boolean proper = true;

for(int i: array)
{

for(int j = i; j < array.length-2; j++)
{
if(array[i] == array[j+1])
{
proper = false;
}
}

}

if(array[0] != array[array.length - 1])
{
proper = false;
}

return proper;

}

private int[] matchingNumbers(int[] array)
{
int[] matchedNumbers = new int[2];

for(int i: array)
{

for(int j = i; j < array.length-1; j++)
{
if(array[i] == array[j+1])
{
matchedNumbers[0] = i;
matchedNumbers[1] = j+1;
}
}

}

return matchedNumbers;
}

private int routeDistance(int[] array)
{

int distance = 0;

int y = array[0]/rows;
int x = array[0]%columns;
int nextY;
int nextX;

for(int i = 1; i < array.length; i++)
{
nextY = array[i]/rows;
nextX = array[i]%columns;

distance += Math.abs(y-nextY) + Math.abs(x-nextX);

y = nextY;
x = nextX;
}

return distance;
}}


## Runner

/**
* This class is the UI for the GA. It will allow the user to create cities on a map by having
* the user click buttons on a grid (The buttons are cites, and the grid is the map). It will also take user
* input for the mutation and crossover probability, the number of generations, and population size.
*
*/

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JButton;
import javax.swing.JTextField;
import javax.swing.JLabel;
import java.awt.Color;

import java.util.Queue;

import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;

import java.lang.StringBuilder;

public class Runner
{
public static void main(String[] args)
{
//This will be submitted to the GA as the map
final char[][] mapCoords = new char[10][10];

for(int i = 0; i< 10; i++)
{
for(int j = 0; j < 10; j++)
{
//sets the default of all points in map to an empty char
mapCoords[i][j] = ' ';
}
}

//these are the names for the waypoints, set when the user clicks a button
final Queue<Character> names = new LinkedList<Character>();

//frame width and height
final int FRAME_WIDTH = 516;
final int FRAME_HEIGHT = 850;

//created frame and panel. Panel layout is taken away from the flow layout.
final JFrame myFrame = new JFrame();
myFrame.setTitle("Traveling Saleman Problem - GA solution");
myFrame.setSize(FRAME_WIDTH,FRAME_HEIGHT);
final JPanel myPanel = new JPanel();
myPanel.setLayout(null);

//button grid
final JButton[][] grid = new JButton[10][10];

for(int i = 0; i<10; i++)
{
for(int j = 0; j<10; j++)
{

//creates a grid of buttons and gives them an action command when pressed
grid[i][j] = new JButton("");
grid[i][j].setSize(45,45);
grid[i][j].setLocation((3+(j*50)),3 + (i*50));
grid[i][j].setActionCommand(i + "," + j);

}
}

//number of generation text field
final JTextField numGen = new JTextField();
numGen.setSize(60,30);
numGen.setLocation(15,515);

//label for number of generations
final JLabel genLabel = new JLabel("Number of Generations");
genLabel.setLocation(85,515);
genLabel.setSize(150,30);

//population size text field
final JTextField popSize = new JTextField();
popSize.setSize(60,30);
popSize.setLocation(15,550);

//label for population size
final JLabel popLabel = new JLabel("Population Size");
popLabel.setLocation(85,550);
popLabel.setSize(150,30);

//crossover probability text field
final JTextField crossProb = new JTextField();
crossProb.setSize(60,30);
crossProb.setLocation(15,585);

//crossover label
final JLabel crossLabel = new JLabel("Crossover Probability");
crossLabel.setLocation(85,585);
crossLabel.setSize(200,30);

//mutation probability text field
final JTextField mutProb = new JTextField();
mutProb.setSize(60,30);
mutProb.setLocation(15,620);

//mutation probability label
final JLabel mutLabel = new JLabel("Mutation Probability");
mutLabel.setLocation(85,620);
mutLabel.setSize(200,30);

//label that displays the shortest route
final JLabel arrayLabel = new JLabel();
arrayLabel.setLocation(15,675);
arrayLabel.setSize(400,30);

//label that displays the shortest route distance
final JLabel distanceLabel = new JLabel();
distanceLabel.setLocation(15,725);
distanceLabel.setSize(400,30);

//The submit button
final JButton submitButton = new JButton("Submit");
submitButton.setBackground(Color.yellow);
submitButton.setContentAreaFilled(false);
submitButton.setOpaque(true);
submitButton.setSize(80,30);
submitButton.setLocation(400,515);

//makes panel visible and close when the 'x' is hit
myFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
myFrame.setVisible(true);

/*
* Brains of the GUI- sets action and creates a GA Map
*
*/
class RunnerListener implements ActionListener
{
//character to be passed to the map
char character;

//String builder for the results
StringBuilder strBuild;
String result = " ";

//keeps count of the number of cities placed on the map
int cities = 0;

@Override
public void actionPerformed(ActionEvent e)
{

//if the submit button is pressed
if(e.getSource() == submitButton)
{
//boolean to check if the user input is proper for running the GA
boolean submit = false;

//if there is more than one cites
if(cities > 1)
{
submit = true;
}

//initializing parameters for GA
int pop = 0;
int gen = 0;
int cross = 0;
int mut = 0;

//if the input into the text fields is numeric
try{
//takes in the input from the text fields
gen = Integer.parseInt(numGen.getText());
pop = Integer.parseInt(popSize.getText());
cross = Integer.parseInt(crossProb.getText());
mut = Integer.parseInt(mutProb.getText());

}catch(NumberFormatException notNumber){
submit = false;
//if the input is not numeric the submission button will not work
System.out.println("Submit failed");
}

//if the input is valid
if(submit)
{
//System.out.println("Submit successful");

//reinitialize the string builder each submission
strBuild = new StringBuilder();
//create a new map each time the submit button is pressed
Map map = new Map(mapCoords);
//run the GA
map.runGA(cities,pop,gen,cross,mut);

//build the string for the output using the public shortest route names array in the Map class
for(int i = 0; i < map.shortestRoute.length; i++)
{
strBuild.append(map.shortestRouteNames[i] + " ");
}

//display the output
arrayLabel.setText("Shortest Route: " + strBuild.toString());
distanceLabel.setText("Distance: " + String.valueOf(map.shortestRouteDistance));
}

}else{ //if any other button is pressed outside of the submit button

//set the command to the button pressed
String command = e.getActionCommand();
//parse the command to get the x pos of the button pressed
int x = Character.getNumericValue(command.charAt(0));
//parse the command to get the y pos of the button pressed
int y = Character.getNumericValue(command.charAt(2));
//take in a new name for the city
character = names.remove();
//set the label of the button to the name of the city
grid[x][y].setText(Character.toString(character));
//place the name of the city in the map array to be passed into the GA
mapCoords[x][y] = character;
//increment count of cities... if a button is pressed twice this will crash the program
cities++;
}
}

}

//initialize a listener
RunnerListener myListener = new RunnerListener();

//give each of the map buttons the listener
for(int i = 0; i<10; i++)
{
for(int j = 0; j<10;j++)
{

}

}

//give the submit button the listener
}

}

• Please fix your code formatting. Commented May 4, 2015 at 3:04
• import java.util.* and you call your class Map... yikes, if you use the other Map (as linked), your code will fail terribly. May I suggest a better class name? Commented May 4, 2015 at 5:45

Firstly, I would create a helper class called NamedIndex and use it instead of the 4 collections ArrayList<NamedIndex> cities...
NamedIndex[] shortestRoute...

Constructors are a special function type. Exception in a c-tor, could lead to memory leaks. They also follow different rules when inheritance is in play. So, it's advisable to keep the constructor logic to the minimum. I would move the cities construction logic to a dedicated method,say, private ArrayList<NamedIndex> BuildCitiesList(char[][] array)

Below are some more suggestions in form of your code suggested code reasoning

for(int i = 0; i<array.length; i++)
{
for(int j = 0; j <array[i].length; j++)


replace with

for(int r = 0; r<rows; r++)
{
for(int c = 0; c <array[r]; c++)


r stands for row, c for column. again helps readability and following the code logic more easiliy.

(array[i].length * i) + (j)


replace with

int oneDIndex = (columns * r) + (c);


it's always better to name "non-trivial" formulas. With proper naming this would avoid the need for the comment.

runGA is too long.
Personally, I try to limit my functions to 10 lines of code. I would create several sub functions:

GenerateRoutes - (first loop, starting with comment '//compare all the routes and find the shortest route')
FindShortestRoute - (second loop, starting with comment '//compare all the routes and find the shortest route')
SkipMutationAndCrossover - two checks at the end of the loop

• There are a few reasons why your suggestions can be further improved... Map is unfortunately the class name, not a return type. Java methods are often given the camelCase treatment, as opposed to .net's PascalCasing. It'll also be more beneficial if you can explain why and how to split into the methods you describe... Commented May 4, 2015 at 5:52
• @h.j.k. a constructor, ha? that's embarrassing, I missed that. I updated my answer to reflect that fact. Commented May 4, 2015 at 10:47
• @h.j.k. I really should have done more research before naming that class. Daniel, thank you for your answer! There is a lot of useful information in it! From now on I will try to be more conscious about readability. I'm a college student and up to this point the only ones that need to read my code have been me and my professors. I have a question about creating a helper class though. If I create it and use it's objects in the calculations, will it slow down the program at all? This algorithm is meant to be run at half a million generations and will need to be as efficient as possible. Commented May 4, 2015 at 14:35
• Short answer - no. I don't think it would affect performance. Especially for large arrays. Are you sure you're going to have enough memory to store all data?) Commented May 4, 2015 at 14:58
• Slightly longer answer. I think you should focus on selecting the correct data structures and (maybe) a way to distribute you're calculations among several machines. Doing so, would have much more significant impact on the running times Commented May 4, 2015 at 15:02