Opened 9 years ago
Closed 9 years ago
#2411 closed enhancement (done)
FastNonDominatedSort performance should be improved
| Reported by: | mkommend | Owned by: | mkommend |
|---|---|---|---|
| Priority: | medium | Milestone: | HeuristicLab 3.3.12 |
| Component: | Algorithms.NSGA2 | Version: | 3.3.11 |
| Keywords: | Cc: |
Description
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.
Change History (6)
comment:1 Changed 9 years ago by mkommend
comment:2 Changed 9 years ago by mkommend
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 |
comment:3 Changed 9 years ago by mkommend
- Status changed from new to accepted
comment:4 Changed 9 years ago by mkommend
- Owner changed from mkommend to abeham
- Status changed from accepted to reviewing
comment:5 Changed 9 years ago by abeham
- Owner changed from abeham to mkommend
- Status changed from reviewing to readytorelease
Changes look good, the improvements are quite nice.
comment:6 Changed 9 years ago by mkommend
- Resolution set to done
- Status changed from readytorelease to closed
Note: See
TracTickets for help on using
tickets.
r12580: Improved performance of FastNonDominantSort by using different data structures, avoiding LINQ and caching of dictionary entries.