Opened 2 years ago

Closed 2 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 2 years ago by mkommend

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

comment:2 Changed 2 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 2 years ago by mkommend

  • Status changed from new to accepted

comment:4 Changed 2 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from accepted to reviewing

comment:5 Changed 2 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 2 years ago by mkommend

  • Resolution set to done
  • Status changed from readytorelease to closed

r12703: Merged r12580 into stable.

Note: See TracTickets for help on using tickets.