Opened 9 years ago

Closed 8 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)

CrowdedComparisonSorter.cs (2.8 KB) - added by gkronber 9 years ago.
CrowdedComparisonSorter.cs
CrowdingDistanceAssignment.cs (4.0 KB) - added by gkronber 9 years ago.
CrowdingDistanceAssignment.cs
FastNonDominatedSort.cs (4.7 KB) - added by gkronber 9 years ago.

Download all attachments as: .zip

Change History (39)

comment:1 Changed 9 years ago by abeham

  • Type changed from defect to feature request

Changed 9 years ago by gkronber

CrowdedComparisonSorter.cs

Changed 9 years ago by gkronber

CrowdingDistanceAssignment.cs

Changed 9 years ago by gkronber

comment:2 Changed 9 years ago by gkronber

Attached HL version 3.2 implementation of NSGA-II specific operators.

comment:3 Changed 9 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 9 years ago by abeham

r4012

  • Added empty plugin for NSGA-II

comment:5 Changed 9 years ago by abeham

r4017

  • Ported CrowdingDistanceAssignment operator
  • Added parameters to the alg and the main loop
    • main loop behavior is copied from the GA

comment:6 Changed 9 years ago by abeham

r4039

  • Ported the other two operators (FastNonDominatedSort and CrowdedComparisonSorter)

comment:7 Changed 9 years ago by abeham

r4040

  • Changed license text and organized usings

comment:8 Changed 9 years ago by abeham

r4041

  • Added CrowdedTournamentSelector

comment:9 Changed 9 years ago by abeham

r4045

  • Added first possibly working NSGA-II
  • Added Maximization parameter to IMultiObjectiveProblem and IMultiObjectiveSelector

comment:10 Changed 9 years ago by abeham

r4052

  • Added maximization parameter in constructor of CrowdedTournamentSelector

comment:11 Changed 9 years ago by abeham

r4067

  • Fixed some bugs in NSGA-II

comment:12 Changed 9 years ago by abeham

r4086

  • Added a very very basic analyzer for listing the qualities on the pareto front

comment:13 Changed 9 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 8 years ago by gkronber

  • Version changed from 3.3 to 3.3.0

comment:15 Changed 8 years ago by gkronber

  • Version changed from 3.3.0 to 3.3.1

comment:16 Changed 8 years ago by gkronber

Added storable attribute to CrowdedTournamentSelector with r4165.

comment:17 Changed 8 years ago by abeham

r4167

  • Added item attribute to CrowdedTournamentSelector

comment:18 Changed 8 years ago by abeham

r4168

  • Fixed a bug in the clone method

comment:19 Changed 8 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 8 years ago by abeham

r4396

  • Moved NSGA-II into a feature-branch

comment:21 Changed 8 years ago by abeham

r4514

  • Added SelectedParents parameter to define the size of the offspring population

comment:22 Changed 8 years ago by abeham

  • Version changed from 3.3.1 to branch

comment:23 Changed 8 years ago by abeham

r4599

  • swinkler added the missing PreBuildEvent.cmd file in the branch

comment:24 Changed 8 years ago by abeham

r4601

  • Updated BasicMultiObjectiveQualityAnalyzer to add the scopes of the pareto front as a result object

comment:25 Changed 8 years ago by swagner

  • Summary changed from Implement Algorithms: NSGA-II to Implement NSGA-II

comment:26 Changed 8 years ago by abeham

  • Milestone changed from HeuristicLab x.x.x to HeuristicLab 3.3.3

comment:27 follow-up: Changed 8 years ago by vdorfer

r4902: adapted NSGAII to new cloning implementation

comment:28 in reply to: ↑ 27 Changed 8 years ago by abeham

Replying to vdorfer:

r4902: adapted NSGAII to new cloning implementation

I looked through the changes. Thx!

comment:29 Changed 8 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from accepted to reviewing
  • Version changed from branch to 3.3.2

r5143

  • 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 8 years ago by abeham

r5145

  • Fixed build that broke with r5143

comment:31 Changed 8 years ago by abeham

r5148

  • Removed NSGA-II branch

comment:32 Changed 8 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 8 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 8 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 8 years ago by gkronber

  • Owner changed from gkronber to swagner
  • Status changed from reviewing to readytorelease

comment:36 Changed 8 years ago by mkommend

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.2 to 3.3.3
Note: See TracTickets for help on using tickets.