FastNonDominatedSort performance should be improved

[HeuristicLab-Trac-Bot]

Issue migrated from trac ticket # 2411

milestone: HeuristicLab 3.3.12 | component: Algorithms.NSGA2 | priority: medium | resolution: done

2015-07-03 12:30:05: @mkommend created the issue

---

The performance of the fast nondominated sorting operator degrades drastically when larger population sizes are used in the NSGA-II. The complexity of the sorting is O(N²M) (N # population size, M# objectives), which could explain the performance hit.

[HeuristicLab-Trac-Bot]

2015-07-03 12:56:12: @mkommend commented

---

r12580: Improved performance of FastNonDominantSort by using different data structures, avoiding LINQ and caching of dictionary entries.

[HeuristicLab-Trac-Bot]

2015-07-03 13:02:45: @mkommend commented

---

r12580 achieved the following improvements : || Algorithm || Population Size || Execution time before || Execution time after || NSGA-II || 200|| 3s|| 3s|| || NSGA-II || 1,000|| 15s|| 7s|| || NSGA-II || 5,000|| 1 min 55s|| 49s|| || NSGA-II Domination || 5,000|| 1 min 42s|| 47s||

[HeuristicLab-Trac-Bot]

2015-07-03 13:02:53: @mkommend changed status from new to accepted

[HeuristicLab-Trac-Bot]

2015-07-03 13:03:12: @mkommend changed status from accepted to reviewing

[HeuristicLab-Trac-Bot]

2015-07-03 13:03:12: @mkommend changed owner from @mkommend to @abeham

[HeuristicLab-Trac-Bot]

2015-07-08 10:46:44: @abeham changed status from reviewing to readytorelease

[HeuristicLab-Trac-Bot]

2015-07-08 10:46:44: @abeham changed owner from @abeham to @mkommend

[HeuristicLab-Trac-Bot]

2015-07-08 10:46:44: @abeham commented

---

Changes look good, the improvements are quite nice.

[HeuristicLab-Trac-Bot]

2015-07-10 11:53:57: @mkommend changed status from readytorelease to closed

[HeuristicLab-Trac-Bot]

2015-07-10 11:53:57: @mkommend removed resolution

[HeuristicLab-Trac-Bot]

2015-07-10 11:53:57: @mkommend commented

---

r12703: Merged r12580 into stable.