Search code examples
javaarraylistgenetic-algorithmtraveling-salesman

Java, genetic algorithm traveling salesman issue


Working on project for class having some issues during the crossover (I understand the issues I'll face later in the assignment, but it's how the professor asked) my chromosome 1 and 2 are reporting as the same thing.

randomNum = rand.nextInt(3);
Chromosome chromosome2 = topTen.remove(randomNum);
System.out.print(chromosome2 + "\n");
index = generation.indexOf(chromosome2);
generation.remove(index);

here is the rest of the code

public Chromosome tsp(int population, int num_generations) {    

    //Random Seed
    Random rand = new Random();
    int randomNum;

    //Generate inital population
    ArrayList<Chromosome> generation = new ArrayList<Chromosome>();
    for (int i = 0; i < population; i++) {

        //Clone original
        ArrayList<Vertex> genes = new ArrayList<Vertex>();
        for (Vertex v: vertex_list) {
            genes.add(new Vertex(v.toString()));
        }

        //Mix genes
        for (int j = genes.size() - 1; j > 1; j--) {
            randomNum = rand.nextInt(j) + 1;
            Vertex removed = genes.remove(randomNum);
            genes.add(removed);
        }

        genes.add(genes.get(0)); //Add start gene to end
        int score = checkScore(genes); //Check distance
        Chromosome chromosome = new Chromosome(genes, score); //Create chromosome
        generation.add(chromosome); //Add chromosome to generation list
    }

    //Generation Loop
    for (int i = 0; i < num_generations; i++) {
        ArrayList<Chromosome> newGen = new ArrayList<Chromosome>(); //Holds new generation
        Collections.sort(generation); //Sort generation

        //Keep top 10 from previous generation
        for (int j = 0; j < 10; j++) {
            Chromosome best = generation.remove(j);
            newGen.add(best);
        }

        //Crossover the rest of the generation
        while(!generation.isEmpty()) {

            //Pick Ten Randomly
            ArrayList<Chromosome> topTen = new ArrayList<Chromosome>();
            for (int j = 0; j < 10; j++) {
                randomNum = rand.nextInt(generation.size());
                topTen.add(generation.get(randomNum));
            }

            //Sort Those 10
            Collections.sort(topTen);

            //Get first chromosome
            randomNum = rand.nextInt(4);
            Chromosome chromosome1 = topTen.remove(randomNum);
        System.out.print(chromosome1 + "\n");
            int index = generation.indexOf(chromosome1);
            generation.remove(index); //remove extra

            //Get second chromosome
            randomNum = rand.nextInt(3);
            Chromosome chromosome2 = topTen.remove(randomNum);
        System.out.print(chromosome2 + "\n");
            index = generation.indexOf(chromosome2);
            generation.remove(index); //remove extra

        }
    }

    return generation.get(0);
}

Chromosome class constructor

public Chromosome(ArrayList<Vertex> genes, int score) {
    this.genes = genes;
    this.score = score;
}

Solution

  • Found my problem. Was adding duplicate chromosomes during the random generation of 10 chromosomes. Just need to make them unique.