Genetic Algorithm for TSP

Question

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++)
 {
 cityArrayList.add(cityIndex.get(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.util.LinkedList;
 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>();
 names.add('a');
 names.add('b');
 names.add('c');
 names.add('d');
 names.add('e');
 names.add('f');
 names.add('g');
 names.add('h');
 names.add('i');
 names.add('j');
 names.add('k');
 names.add('l');
 names.add('m');
 names.add('n');
 names.add('o');
 names.add('p');
 names.add('q');
 names.add('r');
 names.add('s');
 names.add('t');
 names.add('u');
 names.add('v');
 names.add('w');
 names.add('x');
 names.add('y');
 names.add('z');
 //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);
 myPanel.add(grid[i][j]);
 }
 }
 //number of generation text field 
 final JTextField numGen = new JTextField();
 numGen.setSize(60,30);
 numGen.setLocation(15,515);
 myPanel.add(numGen);
 //label for number of generations
 final JLabel genLabel = new JLabel("Number of Generations");
 genLabel.setLocation(85,515);
 genLabel.setSize(150,30);
 myPanel.add(genLabel);
 //population size text field
 final JTextField popSize = new JTextField();
 popSize.setSize(60,30);
 popSize.setLocation(15,550);
 myPanel.add(popSize);
 //label for population size
 final JLabel popLabel = new JLabel("Population Size");
 popLabel.setLocation(85,550);
 popLabel.setSize(150,30);
 myPanel.add(popLabel);
 //crossover probability text field
 final JTextField crossProb = new JTextField();
 crossProb.setSize(60,30);
 crossProb.setLocation(15,585);
 myPanel.add(crossProb);
 //crossover label
 final JLabel crossLabel = new JLabel("Crossover Probability");
 crossLabel.setLocation(85,585);
 crossLabel.setSize(200,30);
 myPanel.add(crossLabel);
 //mutation probability text field
 final JTextField mutProb = new JTextField();
 mutProb.setSize(60,30);
 mutProb.setLocation(15,620);
 myPanel.add(mutProb); 
 //mutation probability label
 final JLabel mutLabel = new JLabel("Mutation Probability");
 mutLabel.setLocation(85,620);
 mutLabel.setSize(200,30);
 myPanel.add(mutLabel);
 //label that displays the shortest route
 final JLabel arrayLabel = new JLabel();
 arrayLabel.setLocation(15,675);
 arrayLabel.setSize(400,30);
 myPanel.add(arrayLabel);
 //label that displays the shortest route distance
 final JLabel distanceLabel = new JLabel();
 distanceLabel.setLocation(15,725);
 distanceLabel.setSize(400,30);
 myPanel.add(distanceLabel);
 //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);
 myPanel.add(submitButton);
 //makes panel visible and close when the 'x' is hit
 myFrame.add(myPanel);
 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++)
 {
 grid[i][j].addActionListener(myListener);
 }
 }
 //give the submit button the listener
 submitButton.addActionListener(myListener);
 }
}

• Jamal: Please fix your code formatting.
• h.j.k.: 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?

Answer 1

My comments and suggestions are all about code readability and not algorithm correctness or efficiency.
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

• h.j.k.: 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...
• Daniel Sokolov: @h.j.k. a constructor, ha? that's embarrassing, I missed that. I updated my answer to reflect that fact.
• llamaCaraDara: @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.
• Daniel Sokolov: 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?)
• Daniel Sokolov: 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