5
\$\begingroup\$

I did this code for somebody but need it to be double checked before I pass it onto them. Code seems fine but I need someone to confirm I have coded the crossover methods correctly.

Would be great if somebody that is familiar with genetic algorithms and crossover methods, could confirm that I have the correct logic and code behind each crossover method.

 //one crossover point is selected, string from beginning of chromosome to the 
 //crossover point is copied from one parent, the rest is copied from the second parent

 // One-point crossover

public void onePointCrossover(Individual indi) {
    if (SGA.rand.nextDouble() < pc) {
        // choose the crossover point 
        int xoverpoint = SGA.rand.nextInt(length);


        int tmp;
        for (int i=xoverpoint; i<length; i++){
            tmp = chromosome[i];
            chromosome[i] = indi.chromosome[i];
            indi.chromosome[i] = tmp;
        }   
    }   
}
//two crossover point are selected, binary string from beginning of chromosome to
//the first crossover point is copied from one parent, the part from
// the first to the second crossover point is copied from the second parent
// and the rest is copied from the first parent

// Two-point crossover
    public void twoPointCrossover(Individual indi) {
        if (SGA.rand.nextDouble() < pc) {
            // choose the crossover point 
            int xoverpoint = SGA.rand.nextInt(length);
            int xoverpoint2 = SGA.rand.nextInt(length);

            int tmp;
            //swap
            if (xoverpoint > xoverpoint2){
                tmp = xoverpoint;
                xoverpoint = xoverpoint2;
                xoverpoint2 = tmp;
            }

            for (int i=xoverpoint; i<xoverpoint2; i++){
                tmp = chromosome[i];
                chromosome[i] = indi.chromosome[i];
                indi.chromosome[i] = tmp;
            }   
        }   
    }

    //  For each gene, create a random number in [0,1]. If
    // the number is less than 0.5, swap the gene values in
    // the parents for this gene; otherwise, no swapping 

// Uniform Crossover
    public void UniformCrossover(Individual indi) {
        if (SGA.rand.nextDouble() < pc) {
        for (int i= 1; i<length; i++){
            boolean tmp =  SGA.rand.nextFloat() < 0.5;
            if(tmp){
                chromosome[i] = indi.chromosome[i];

            }
            }

        }

Parent 1 = chromosome Parent 2= indi.chromosome

I am turning the parents into children inplace.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I suggest you write unit tests. See JUnit. \$\endgroup\$
    – JRL
    Feb 17 '12 at 1:35
  • \$\begingroup\$ Does it work when you test it? \$\endgroup\$
    – Jivings
    Feb 17 '12 at 1:46
  • \$\begingroup\$ Yes that would be appropriate but because I am not to good with genetic algorithms I will not know what to expect from the test results. I had an algorithm for each crossover method and implemented them into java code, I just wanted to check the code is swapping and keeping the correct parts from the parents. \$\endgroup\$
    – Student
    Feb 17 '12 at 1:48
  • \$\begingroup\$ What is pc equal to? \$\endgroup\$
    – Jivings
    Feb 17 '12 at 1:48
  • \$\begingroup\$ Yes it does work when I run it and I get slightly different values each time I change the crossover methods (only when pm>0.2), which is a good sign? pc = 0.8 \$\endgroup\$
    – Student
    Feb 17 '12 at 1:57
4
\$\begingroup\$

It's difficult to just look at, but a few things jump out. More improvements than bugs:

  • For single point crossover using System.arraycopy() would be much more reliable. For example:

    System.arraycopy(parent1Genes, 0, childGenes, 0, xoverPoint);
    System.arraycopy(parent2Genes, xoverPoint, childGenes, xoverPoint, geneSize-xoverPoint);
    
  • You could use the same method for two point, but it would be slightly more complex.

  • In Uniform crossover you can use rand.nextBoolean(), which returns true or false, instead of comparing the float.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for the suggestions, I didn't quite understand how I could use rand.nextBoolean instead? \$\endgroup\$
    – Student
    Feb 17 '12 at 2:01
  • \$\begingroup\$ Well checking to see if a random double is < 0.5 is just a coin flip. So you can replace rand.nextDouble() < 0.5 with rand.nextBoolean() \$\endgroup\$
    – Jivings
    Feb 17 '12 at 8:38
2
\$\begingroup\$

A bit out of scope of the question, but one thing is if you are doing crossover directly on the parents, then the parents will not be viable for further selection. Otherwise the algorithm could do several crossovers on an already manipulated parent/child (assuming you allow the same individual to be selected for breeding more than once).

The times I have implemented this myself I always pass in the individuals for crossover and return the children. That way it is easier to keep the generations separate. An alternative would be to clone the individuals in the parent generation do the crossover and mutations on the cloned copy and use the original individuals for selection.

Your implementation looks alright to me. However as has been stated in the comments you really need to write tests for these functions. By mocking the random generation function you can control what the results should be. I.e. instead of generating random numbers like this:

SGA.rand.nextDouble()

you could have a field in your class:

pubilc class Crossover {
    private Randomizer randomizer
    public Crossover(Randomizer randomizer) {
         this.randomizer = randomizer;
    }

    public void onePointCrossover(Individual indi) {
        if (randomizer.nextDouble() < pc) {
            // do stuff 
        }
    }
}

Where Randomizer is an interface with the nextXXXX() methods you need. That way you can create mocks for the Randomizer in your test, and have a concrete implementation which delegates to SGA.rand.nextXXXX().

\$\endgroup\$
0

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.