giacomelli / GeneticSharp

GeneticSharp is a fast, extensible, multi-platform and multithreading C# Genetic Algorithm library that simplifies the development of applications using Genetic Algorithms (GAs).
MIT License
1.26k stars 330 forks source link

Reinsertion / Evaluation workflow update #89

Closed jsboige closed 1 year ago

jsboige commented 3 years ago

That pull-request attempts providing fixes to the issues mentioned in issue #82. To allow for Fitness-based reinsertion to make sense, evaluation is now performed before reinsertion. Some Reinsertion classes are updated, and a new FitnessBasedElitistReinsertion class is proposed as the new default, according to the publication referenced in the earlier version. Other performance gains were obtained and checked with a profiler.

Some optimizations were rolled-backed and commented out as seen in the corresponding unit tests

The reason for that is that although the performance gains were significant on the .Net Framework, they were more negligeable or even made things worse on .Net standard. The reason I believe is that the corresponding improvement was actually implemented in the latest .Net core. It seems however that the optmization may have gone to far the other direction, and in my early tests, the performance of the new .Net standard SortedEnumerator, though pretty good fowllowed with a Take(xx) that is properly accounted for thanks to the Quicksort partitioning feature, then gets worse than the proposed Lazyxx implementation here, when the percentage of items requested by the Take(xx) call goes above 70%.

This is to say, I believe the commented code could stay for a bit, and more tests should be done to properly figure out the differences in SortedEnumerators between .Net core, and .regular .Net implementations, depending on versions. One thing is sure, the current 462 Framework does perform complete sorts, which are O(nlog(n)) with worst case already sorted for Quicksort, for OderBy(xx) followed by Take(), whereas Maxby is linear and Lazy leverages partioning to only sort the requested first elements.

giacomelli commented 1 year ago

Closing due to inactivity.

Feel free to fix the CI errors and reopen the PR.