Java and Increasing the Efficiency of Genetic Algorithms

I was wondering if I could get some advice on increasing the overall efficiency of a program that implements a genetic algorithm. Yes this is an assignment question, but I have already completed the assignment on my own and am simply looking for a way to get it to perform better Problem Description

My program at the moment reads a given chain made of the types of constituents, h or p. (For example: hphpphhphpphphhpphph) For each H and P it generated a random move (Up, Down, Left, Right) and adds the move to an arrayList contained in the "Chromosome" Object. At the start the program is generating 19 moves for 10,000 Chromosomes

   SecureRandom sec = new SecureRandom();
    byte[] sbuf = sec.generateSeed(8);
    ByteBuffer bb = ByteBuffer.wrap(sbuf);
    Random numberGen = new Random(bb.getLong());
    int numberMoves = chromosoneData.length();
    moveList = new ArrayList(numberMoves);
    for (int a = 0; a < numberMoves; a++) {
        int randomMove = numberGen.nextInt(4);
        char typeChro = chromosoneData.charAt(a);
        if (randomMove == 0) {
            moveList.add(Move.Down);
        } else if (randomMove == 1) {
            moveList.add(Move.Up);
        } else if (randomMove == 2) {
            moveList.add(Move.Left);
        } else if (randomMove == 3) {
            moveList.add(Move.Right);
        }

    }

After this comes the selection of chromosomes from the Population to crossover. My crossover function selections the first chromosome at random from the fittest 20% of the population and the other at random from outside of the top 20%. The chosen chromosomes are then crossed and a mutation function is called. I believe the area in which I am taking the biggest hit is calculating the fitness of each Chromosome. Currently my fitness function creates a 2d Array to act as a grid, places the moves in order from the move list generated by the function shown above, and then loops through the array to do the fitness calculation. (I.E. found and H at location [2,1] is Cord [1,1] [3,1] [2,0] or [2,2] also an H and if an H is found it just increments the count of bonds found)

After the calculation is complete the least fit chromosome is removed from my population and the new one is added and then the array list of chromosomes is sorted. Rinse and repeat until target solution is found

If you guys want to see more of my code to prove I actually did the work before asking for help just let me know (dont want to post to much so other students cant just copy pasta my stuff)

As suggested in the comments I have ran the profiler on my application (have never used it before, only a first year CS student) and my initial guess on where i am having issues was somewhat incorrect. It seems from what the profiler is telling me is that the big hotspots are:

1. When comparing the new chromosome to the others in the population to determine its position. I am doing this by implementing Comparable:

    public int compareTo(Chromosome other) {
        if(this.fitness >= other.fitness)
                        return 1;
             if(this.fitness ==other.fitness )
                       return 0;
                else
                        return -1;
    }

2. The other area of issue described is in my actual evolution function, consuming about 40% of the CPU time. A codesample from said method below

    double topPercentile = highestValue;
    topPercentile = topPercentile * .20;
    topPercentile = Math.ceil(topPercentile);
    randomOne = numberGen.nextInt((int) topPercentile);
    //Lower Bount for random two so it comes from outside of top 20%
    int randomTwo = numberGen.nextInt(highestValue - (int) topPercentile);
    randomTwo = randomTwo + 25;
    //System.out.println("Selecting First: " + randomOne + " Selecting Second: " + randomTwo);
    Chromosome firstChrom = (Chromosome) populationList.get(randomOne);
    Chromosome secondChrom = (Chromosome) populationList.get(randomTwo);
    //System.out.println("Selected 2 Chromosones Crossing Over");
    Chromosome resultantChromosome = firstChrom.crossOver(secondChrom);
    populationList.add(resultantChromosome);
    Collections.sort(populationList);
    populationList.remove(highestValue);
    Chromosome bestResult = (Chromosome) populationList.get(0);
   

3. The other main preformance hit is the inital population seeding which is performed by the first code sample in the post开发者_高级运维

---

I believe the area in which I am taking the biggest hit is calculating the fitness of each Chromosome

If you are not sure then I assume you have not run a profiler on the program yet.
If you want to improve the performance, profiling is the first thing you should do.

---

Instead of repeatedly sorting your population, use a collection that maintains its contents already sorted. (e.g. TreeSet)

---

If your fitness measure is consistent across generations (i.e. not dependent on other members of the population) then I hope at least that you are storing that in the Chromosome object so you only calculate it once for each member of the population. With that in place you'd only be calculating fitness on the newly generated/assembled chromosome each iteration. Without more information on how fitness if calculated it's difficult to be able to offer any optimisations in that area.

---

Your random number generator seed doesn't need to be cryptographically strong.

Random numberGen = new Random();

---

A minor speedup when seeding your population is to remove all the testing and branching:

    static Move[] moves = {Move.Down, Move.Up, Move.Left, Move.Right};

    ...

    moveList.add(moves[randomMove]);