Since archives with thresholds are non-elitist, it is possible to overwrite the best elite with a solution with lower value. For instance, if you have a solution with objective 1.0 and the threshold is 0.1, adding a solution with objective 0.2 will overwrite this solution, and the best elite and objective max should be updated accordingly.
Things become a bit more complicated when you consider that a solution in another cell in the archive may now be the best elite instead.
Our best bet is likely to do an O(n) search for the best elite on every call to add(). Sorted containers (which would lead to O(log n)) are also an option. (n is the number of solutions in the archive). Performance will suffer with either of these solutions however; an O(1) solution would be optimal.
Note that we did not notice this problem previously because we always retrieve best_elite from the result_archive, which does not have thresholds.
Update: After much discussion, we have decided to leave this behavior as is. Given that users will rarely retrieve the best elite from a non-elitist archive, it is not worth the performance cost to keep track of the best elites with a sorted container or perform linear searches. We have added a test to assert this behavior and documented it where appropriate.
Description
Since archives with thresholds are non-elitist, it is possible to overwrite the best elite with a solution with lower value. For instance, if you have a solution with objective 1.0 and the threshold is 0.1, adding a solution with objective 0.2 will overwrite this solution, and the best elite and objective max should be updated accordingly.
Things become a bit more complicated when you consider that a solution in another cell in the archive may now be the best elite instead.
Our best bet is likely to do an O(n) search for the best elite on every call to add(). Sorted containers (which would lead to O(log n)) are also an option. (n is the number of solutions in the archive). Performance will suffer with either of these solutions however; an O(1) solution would be optimal.
Note that we did not notice this problem previously because we always retrieve
best_elitefrom theresult_archive, which does not have thresholds.Update: After much discussion, we have decided to leave this behavior as is. Given that users will rarely retrieve the best elite from a non-elitist archive, it is not worth the performance cost to keep track of the best elites with a sorted container or perform linear searches. We have added a test to assert this behavior and documented it where appropriate.
TODO
Questions
Status
yapfpytestpylintHISTORY.md