3
\$\begingroup\$

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);
    }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ Please fix your code formatting. \$\endgroup\$ – Jamal May 4 '15 at 3:04
  • \$\begingroup\$ 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? \$\endgroup\$ – h.j.k. May 4 '15 at 5:45
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – h.j.k. May 4 '15 at 5:52
  • \$\begingroup\$ @h.j.k. a constructor, ha? that's embarrassing, I missed that. I updated my answer to reflect that fact. \$\endgroup\$ – Daniel Sokolov May 4 '15 at 10:47
  • \$\begingroup\$ @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. \$\endgroup\$ – llamaCaraDara May 4 '15 at 14:35
  • \$\begingroup\$ 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?) \$\endgroup\$ – Daniel Sokolov May 4 '15 at 14:58
  • \$\begingroup\$ 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 \$\endgroup\$ – Daniel Sokolov May 4 '15 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.