Confirm code is correct - crossover methods in Java

Question

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.

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. — Student
– Student, Commented Feb 17, 2012 at 1:48
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 — Student
– Student, Commented Feb 17, 2012 at 1:57

Jivings · Accepted Answer · 2012-02-17 01:55:40Z

4

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.

answered Feb 17, 2012 at 1:55

Jivings

2,34114 silver badges17 bronze badges

\$\begingroup\$ Thank you for the suggestions, I didn't quite understand how I could use rand.nextBoolean instead? \$\endgroup\$

Student
– Student

2012-02-17 02:01:46 +00:00
Commented Feb 17, 2012 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
– Jivings

2012-02-17 08:38:00 +00:00
Commented Feb 17, 2012 at 8:38

Add a comment |

Emil L · Accepted Answer · 2012-02-17 08:26:43Z

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().

Stack Exchange Network

Confirm code is correct - crossover methods in Java

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Confirm code is correct - crossover methods in Java

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions