Free cookie consent management tool by TermsFeed Policy Generator

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)

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

Download all attachments as: .zip

Change History (39)

comment:1 Changed 14 years ago by abeham

  • Type changed from defect to feature request

Changed 14 years ago by gkronber

CrowdedComparisonSorter.cs

Changed 14 years ago by gkronber

CrowdingDistanceAssignment.cs

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

r4012

  • Added empty plugin for NSGA-II

comment:5 Changed 14 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 14 years ago by abeham

r4039

  • Ported the other two operators (FastNonDominatedSort and CrowdedComparisonSorter)

comment:7 Changed 14 years ago by abeham

r4040

  • Changed license text and organized usings

comment:8 Changed 14 years ago by abeham

r4041

  • Added CrowdedTournamentSelector

comment:9 Changed 14 years ago by abeham

r4045

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

comment:10 Changed 14 years ago by abeham

r4052

  • Added maximization parameter in constructor of CrowdedTournamentSelector

comment:11 Changed 14 years ago by abeham

r4067

  • Fixed some bugs in NSGA-II

comment:12 Changed 14 years ago by abeham

r4086

  • 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

r4167

  • Added item attribute to CrowdedTournamentSelector

comment:18 Changed 14 years ago by abeham

r4168

  • 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

r4396

  • Moved NSGA-II into a feature-branch

comment:21 Changed 14 years ago by abeham

r4514

  • 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

r4599

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

comment:24 Changed 14 years ago by abeham

r4601

  • 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: 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

Replying to vdorfer:

r4902: adapted NSGAII to new cloning implementation

I looked through the changes. Thx!

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

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

r5145

  • Fixed build that broke with r5143

comment:31 Changed 14 years ago by abeham

r5148

  • 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
Note: See TracTickets for help on using tickets.