Opened 14 years ago
Closed 14 years ago
#1040 closed feature request (done)
Implement NSGA-II
| Reported by: | abeham | Owned by: | swagner |
|---|---|---|---|
| Priority: | high | Milestone: | HeuristicLab 3.3.3 |
| Component: | Algorithms.NSGA2 | Version: | 3.3.3 |
| Keywords: | Cc: |
Description (last modified by abeham)
The Non-dominated Sorting Genetic Algorithm (NSGA-II) was introduced by Deb et al. in 2002. It is among the most cited metaheuristics for multiobjective optimization.
Attachments (3)
Change History (39)
comment:1 Changed 14 years ago by abeham
- Type changed from defect to feature request
Changed 14 years ago by gkronber
Changed 14 years ago by gkronber
comment:2 Changed 14 years ago by gkronber
Attached HL version 3.2 implementation of NSGA-II specific operators.
comment:3 Changed 14 years ago by abeham
- Component changed from Algorithms.GeneticAlgorithm to Algorithms.NSGA2
- Description modified (diff)
- Priority changed from major to critical
- Status changed from new to assigned
comment:4 Changed 14 years ago by abeham
- Added empty plugin for NSGA-II
comment:5 Changed 14 years ago by abeham
- Ported CrowdingDistanceAssignment operator
- Added parameters to the alg and the main loop
- main loop behavior is copied from the GA
comment:6 Changed 14 years ago by abeham
- Ported the other two operators (FastNonDominatedSort and CrowdedComparisonSorter)
comment:7 Changed 14 years ago by abeham
- Changed license text and organized usings
comment:8 Changed 14 years ago by abeham
- Added CrowdedTournamentSelector
comment:9 Changed 14 years ago by abeham
- Added first possibly working NSGA-II
- Added Maximization parameter to IMultiObjectiveProblem and IMultiObjectiveSelector
comment:10 Changed 14 years ago by abeham
- Added maximization parameter in constructor of CrowdedTournamentSelector
comment:11 Changed 14 years ago by abeham
- Fixed some bugs in NSGA-II
comment:12 Changed 14 years ago by abeham
- Added a very very basic analyzer for listing the qualities on the pareto front
comment:13 Changed 14 years ago by abeham
- Owner changed from abeham to gkronber
- Status changed from assigned to new
The NSGA-II has been implemented with a basic analyzer and has been tested briefly. I'll reassign this ticket to gkronber for testing, code review and refactoring suggestions.
A quick note on the CrowdedTournamentSelector: I looked it up and it is described in the original paper. The paper states that a standard binary tournament selector was used but with the new partial ordering defined on rank and crowding distance comparison. This is the intended behavior of the implemented selector. However it is more general and allows group sizes of more than 2 individuals.
comment:14 Changed 14 years ago by gkronber
- Version changed from 3.3 to 3.3.0
comment:15 Changed 14 years ago by gkronber
- Version changed from 3.3.0 to 3.3.1
comment:16 Changed 14 years ago by gkronber
Added storable attribute to CrowdedTournamentSelector with r4165.
comment:17 Changed 14 years ago by abeham
- Added item attribute to CrowdedTournamentSelector
comment:18 Changed 14 years ago by abeham
- Fixed a bug in the clone method
comment:19 Changed 14 years ago by abeham
- Owner changed from gkronber to abeham
- Status changed from new to accepted
NSGA-II should be exported to a feature branch meanwhile it is made release ready.
comment:20 Changed 14 years ago by abeham
- Moved NSGA-II into a feature-branch
comment:21 Changed 14 years ago by abeham
- Added SelectedParents parameter to define the size of the offspring population
comment:22 Changed 14 years ago by abeham
- Version changed from 3.3.1 to branch
comment:23 Changed 14 years ago by abeham
- swinkler added the missing PreBuildEvent.cmd file in the branch
comment:24 Changed 14 years ago by abeham
- Updated BasicMultiObjectiveQualityAnalyzer to add the scopes of the pareto front as a result object
comment:25 Changed 14 years ago by swagner
- Summary changed from Implement Algorithms: NSGA-II to Implement NSGA-II
comment:26 Changed 14 years ago by abeham
- Milestone changed from HeuristicLab x.x.x to HeuristicLab 3.3.3
comment:27 follow-up: ↓ 28 Changed 14 years ago by vdorfer
r4902: adapted NSGAII to new cloning implementation
comment:28 in reply to: ↑ 27 Changed 14 years ago by abeham
comment:29 Changed 14 years ago by abeham
- Owner changed from abeham to gkronber
- Status changed from accepted to reviewing
- Version changed from branch to 3.3.2
- Merged NSGA-II into trunk
- Ranking and crowding operators moved to HeuristicLab.Optimization.Operators
- CrowdedTournamentSelector moved to HeuristicLab.Selection
- Pareto front analyzer moved to HeuristicLab.Analysis with a base class should there be more (as discussed with swagner and mkommend)
comment:30 Changed 14 years ago by abeham
comment:31 Changed 14 years ago by abeham
- Removed NSGA-II branch
comment:32 Changed 14 years ago by gkronber
Reviewed NSGA-II operators in HeuristicLab.Analysis.MultiObjective, HeuristicLab.Optimization.Operators.MultiObjective and HeuristicLab.Selection and fixed minor issues with r5438.
comment:33 Changed 14 years ago by gkronber
Tested NSGA-II algorithm with different parameter settings and the multi objective symbolic regression problem.
The implementation of operators is clean and especially easy to read, really nice work!
comment:34 Changed 14 years ago by gkronber
r5439: Not directly related to NSGA-II implementation but not worth a separate ticket... Made minor improvements in multi-objective symbolic regression problem to make it work better with NSGA-II.
comment:35 Changed 14 years ago by gkronber
- Owner changed from gkronber to swagner
- Status changed from reviewing to readytorelease
comment:36 Changed 14 years ago by mkommend
- Resolution set to done
- Status changed from readytorelease to closed
- Version changed from 3.3.2 to 3.3.3
CrowdedComparisonSorter.cs