Implementation of GeneticAlgorithm.nextGeneration() is wrong

• Key: MATH-207
• Type: Bug
• Status: Closed
• Resolution: Fixed
• Priority: Major
• Assignee: Phil Steitz
• Reporter: David Stefka
• Affects Version/s: 2.0
• Fix Version/s: 2.0

Description

The implementation of GeneticAlgorithm.nextGeneration() is wrong, since the only way how a Chromosome can get into the new generation is by mutation.

Enclosed, I am sending a patch for this.

Comments

[David Stefka]

Patch for the bug

[Phil Steitz]

Patch applied to MATH_2_0 branch in r699704.

Leaving open because I think we need to either make nextGeneration public or protected or make it configurable. Interested in comments on this.

Dear Phil,

if you are interested in the topic of genetic algorithms, I am sending a
simple implementation of GA using the commons-math framework. If you find any
of the ideas in it useful, you may use it.

Best regards,
David Stefka

–
David Stefka
[e-mail] (personal mail)

[Ben McCann]

I think that making nextGeneration public would be reasonable.
A few other thoughts about the API:
All the setters should be changed to constructor arguments. If you do not call each of the setters then you are in an illegal state. You avoid the problem of having some call evolve before the mutation policy and crossover policy are set if you just make them required in the constructor.
For crossOverRate and mutationRate we should specify that the input is expected to be between 0 and 1 and throw an exception when given invalid input. It's currently not clear in the javadocs what is expected.

[Benjamin McCann]

Patch to improve the API.

[Benjamin McCann]

Any thoughts on the patch submitted to clean up the API?

[David Stefka]

I think the ideas to clean up the API are okay. However, I don't know whether the patch is against the latest version. Things are starting to be a bit messy...

[Phil Steitz]

Sorry for delay in reviewing these patches. I like both the implementation (David's first patch) and the API improvements and will apply them both if I can get answers to the following.

1) David - pls confirm that you can grant the code in your patch. It is a borderline case whether or not we need a code grant. Given that it just implements the commons-math ga framework, I think it is OK to commit without a grant; but since you did not include ASL license headers in the patch, I need you to confirm that you own the code and can freely contribute it under the terms of the Apache Contributor License Agreement. If you don't mind, it would be good to file a CLA.

2) David's patch looks like it has some JDK 1.6 dependencies. Math 2.0 targets 1.5+, so these need to be removed. I can do this; but a revised patch with these removed and ASL headers would be appreciated.

3) Ben - why expose fields as protected?

Thanks for the patches!

[David Stefka]

ad 1) what do you mean by "file a CLA"? Should I include the license header (e.g. in GeneticAlgorithm.java) to every file in the framework? I do own the code and I agree with the Apache license (http://www.apache.org/licenses/LICENSE-2.0)
ad 2) okay, i will try to make it Java 1.5+ compatible

BTW, I am currently working on a better way of representing permutations, so do not include the original patch now. I will post here a revised version of the implementation in a week or so.

[Phil Steitz]

Thanks, David!

All files should include headers like what you see in GenericAlgorithm.java or any other apache java source file. As long as you own the code and are willing to attach those headers, we should be OK. A Contributors Licence Agreement (CLA) is a good thing to have on file and will be required in any case should you become a committer. Have a look at the "Contributor License Agreements" section at http://www.apache.org/licenses/ to find the form. The form itself includes info on how to submit it.

Thanks again for your conttribution.

[David Stefka]

Hi again,

I have finished work on better representation of permutations in GA, so I am sending the implementation in a .zip file. The code includes:

• new implementation of RandomKey – chromosome representing permutations; the old PermutationChromosome implementation has been removed
• some minor improvements (chromosome's representation is held in an unmodifiable list instead of an array, better implementation of generic issues, renaming of several classes, etc.)
• GeneticAlgorithm has a static Random instance, which is used for all random numbers in the implementation. This is useful for debugging, because if the Random is initialized to a particular seed, the behavior can be reproduced. If a similar mechanism is already somewhere in the
• the code should be java 1.5 compatible
• all the files should include the Apache license headers

I have also filled and signed the CLA and sent it to [e-mail]

[David Stefka]

New implementation of basic GA algorithms

[Ben McCann]

Sorry for my delayed response. JIRA didn't email me on any of these updates for whatever reason.
There's no real need to make the fields protected in my patch. Private would be fine. I've just gotten in the habit of frequently using protected to allow easier subclassing and unit testing, but those fields all have public getters, so no harm in making them private.

[Phil Steitz]

Committed a slightly modified version of David's last patch in r784604.

Other than minor javadoc/formatting changes to make checkstyle happy, I also made the shared source of randomness pluggable.

I am not 100% happy with the static randomGenerator attached to GeneticAlgorithm, though I understand and support the need to ensure reproducibility for some applications. Comments / suggestions for better ways to do this welcome.

Leaving open as we need to update the user guide to complete this.

[Phil Steitz]

User guide updated in r789511

[Luc Maisonobe]

closing resolved issue for 2.0 release