GeneticAlgorithm.BestChromosome.Fitness decrease over time when using EliteSelection

[csbc92]

Describe the bug

Initializing and executing the Genetic Algorithm implementation with an EliteSelection seems in some cases to produce Chromosomes with decreasing fitness over time.

To Reproduce

An FsCheck project was created which generates instances of the Traveling Salesman Problem. FsCheck is an F# QuickCheck port which enables randomized testing of certain properties.

The property under test is specific to an elite selection mechanism and is informally described as

• "The n'th+ 1 generation’s best fitness is greater than or equal to the n'th generation’s best fitness."

or equally

• "The best solution must never be worse that its predecessor."

The FsCheck project is available on Github. Follow the instructions in the README to reproduce the bug. https://github.com/Vedsted/Functional-Project/tree/master/GeneticSharpIssue

It is recommended to read the README file. These lines should provide the output immediately:

git clone https://github.com/Vedsted/Functional-Project.git
cd Functional-Project
dotnet run -p GeneticSharpIssue

Expected behavior

It is expected that the Genetic Algorithm never outputs a BestChromosome which is worse than its predecessor when using EliteSelection.

Version:

NuGet package GeneticSharp v. 2.6.0

Nuget package FsCheck v. 3.0.0 Alpha 4

Sample output: It is shown from the sample below that the BestChromosome.Fitness for the TSP is decreasing in the 7th generation, when seed=781433289.

Checking GeneticAlgorithmResult:
{
         HashCode: 58225482,
         Initial: { Seed: 781433289, Termination: 500},
         Result: { Actual termination: 799, Best Chromosome: (Distance: 4288,691172664607 Fitness: 0,7855654413667696)}
}

FsCheck Trace:
Falsifiable, after 1 test (0 shrinks) (484766587145030488,7199734823952781115)
Last step was invoked with size of 2 and seed of (14439125655389665598,3384482638261145923):
Label of failing property: Fitness decreased at index: 6
For generations 1-7:
 [(Distance: 7912,566119106175 Fitness: 0,6043716940446913);
 (Distance: 7912,566119106175 Fitness: 0,6043716940446913);
 (Distance: 7912,566119106175 Fitness: 0,6043716940446913);
 (Distance: 7912,566119106175 Fitness: 0,6043716940446913);
 (Distance: 7912,566119106175 Fitness: 0,6043716940446913);
 (Distance: 7912,566119106175 Fitness: 0,6043716940446913);
 (Distance: 8262,453814942292 Fitness: 0,5868773092528854)]
Original:

with exception:
System.Exception: Expected true, got false.

Additional context

This bug was found as a part of a mini-project in the course Functional Programming and Property-based Testing, at University of Southern Denmark. The report for this project contains more information. The report can be provided if requested.

Other consequences of this unexpected behavior

If the Genetic Algorithm has a termination criteria of the n'th run where this property is violated, the output is worse that a previous best solution.

[robertvo]

i'm seeing the same issue