search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
39 stars 16 forks source link

Implement NSGA-II #1040

Closed HeuristicLab-Trac-Bot closed 13 years ago

HeuristicLab-Trac-Bot commented 14 years ago

Issue migrated from trac ticket # 1040

milestone: HeuristicLab 3.3.3 | component: Algorithms.NSGA2 | priority: high | resolution: done

2010-06-16 23:24:35: @abeham created the issue

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.

HeuristicLab-Trac-Bot commented 14 years ago

2010-06-16 23:30:52: @abeham changed type from defect to feature request

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-01 13:34:09: @gkronber uploaded file CrowdedComparisonSorter.cs (2.8 KiB)

CrowdedComparisonSorter.cs

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-01 13:35:11: @gkronber uploaded file CrowdingDistanceAssignment.cs (4.0 KiB)

CrowdingDistanceAssignment.cs

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-01 13:35:18: @gkronber uploaded file FastNonDominatedSort.cs (4.7 KiB)

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-01 13:35:55: @gkronber commented

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

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-07 18:34:17: @abeham changed priority from major to critical

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-07 18:34:17: @abeham changed status from new to assigned

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-07 18:34:17: @abeham changed component from Algorithms.GeneticAlgorithm to Algorithms.NSGA2

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-07 18:34:17: @abeham edited the issue description

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-07 18:37:05: @abeham commented

r4012

  • Added empty plugin for NSGA-II
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-08 12:28:36: @abeham commented

r4017

  • Ported CrowdingDistanceAssignment operator
  • Added parameters to the alg and the main loop
    • main loop behavior is copied from the GA
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-17 01:18:09: @abeham commented

r4039

  • Ported the other two operators (FastNonDominatedSort and CrowdedComparisonSorter)
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-17 01:21:13: @abeham commented

r4040

  • Changed license text and organized usings
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-18 00:24:49: @abeham commented

r4041

  • Added CrowdedTournamentSelector
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-19 15:24:50: @abeham commented

r4045

  • Added first possibly working NSGA-II
  • Added Maximization parameter to IMultiObjectiveProblem and IMultiObjectiveSelector
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-20 11:22:03: @abeham commented

r4052

  • Added maximization parameter in constructor of CrowdedTournamentSelector
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-22 00:11:29: @abeham commented

r4067

  • Fixed some bugs in NSGA-II
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-22 16:34:26: @abeham commented

r4086

  • Added a very very basic analyzer for listing the qualities on the pareto front
HeuristicLab-Trac-Bot commented 14 years ago

2010-07-23 14:14:12: @abeham changed status from assigned to new

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-23 14:14:12: @abeham changed owner from abeham to gkronber

HeuristicLab-Trac-Bot commented 14 years ago

2010-07-23 14:14:12: @abeham commented

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.

HeuristicLab-Trac-Bot commented 14 years ago

2010-08-05 11:18:36: @gkronber commented

Added storable attribute to CrowdedTournamentSelector with r4165.

HeuristicLab-Trac-Bot commented 14 years ago

2010-08-05 13:40:13: @abeham commented

r4167

  • Added item attribute to CrowdedTournamentSelector
HeuristicLab-Trac-Bot commented 14 years ago

2010-08-05 14:07:11: @abeham commented

r4168

  • Fixed a bug in the clone method
HeuristicLab-Trac-Bot commented 14 years ago

2010-09-15 14:29:30: @abeham changed status from new to accepted

HeuristicLab-Trac-Bot commented 14 years ago

2010-09-15 14:29:30: @abeham changed owner from gkronber to abeham

HeuristicLab-Trac-Bot commented 14 years ago

2010-09-15 14:29:30: @abeham commented

NSGA-II should be exported to a feature branch meanwhile it is made release ready.

HeuristicLab-Trac-Bot commented 14 years ago

2010-09-15 14:50:04: @abeham commented

r4396

  • Moved NSGA-II into a feature-branch
HeuristicLab-Trac-Bot commented 14 years ago

2010-09-27 10:41:07: @abeham commented

r4514

  • Added SelectedParents parameter to define the size of the offspring population
HeuristicLab-Trac-Bot commented 14 years ago

2010-10-15 12:45:29: @abeham commented

r4599

  • swinkler added the missing PreBuildEvent.cmd file in the branch
HeuristicLab-Trac-Bot commented 14 years ago

2010-10-16 16:25:17: @abeham commented

r4601

  • Updated BasicMultiObjectiveQualityAnalyzer to add the scopes of the pareto front as a result object
HeuristicLab-Trac-Bot commented 13 years ago

2010-11-15 22:13:40: @s-wagner changed title from Implement Algorithms: NSGA-II to Implement NSGA-II

HeuristicLab-Trac-Bot commented 13 years ago

2010-11-22 11:42:12: @abeham changed milestone from HeuristicLab x.x.x to HeuristicLab 3.3.3

HeuristicLab-Trac-Bot commented 13 years ago

2010-11-22 13:24:49: @viikiid commented

r4902: adapted NSGAII to new cloning implementation

HeuristicLab-Trac-Bot commented 13 years ago

2010-11-22 17:03:50: @abeham commented

Replying to [comment:27 vdorfer]:

r4902: adapted NSGAII to new cloning implementation

I looked through the changes. Thx!

HeuristicLab-Trac-Bot commented 13 years ago

2010-12-21 01:09:12: @abeham changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 13 years ago

2010-12-21 01:09:12: @abeham changed owner from abeham to gkronber

HeuristicLab-Trac-Bot commented 13 years ago

2010-12-21 01:09:12: @abeham commented

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)
HeuristicLab-Trac-Bot commented 13 years ago

2010-12-21 01:19:44: @abeham commented

r5145

  • Fixed build that broke with r5143
HeuristicLab-Trac-Bot commented 13 years ago

2010-12-21 14:37:42: @abeham commented

r5148 (not migrated)

  • Removed NSGA-II branch
HeuristicLab-Trac-Bot commented 13 years ago

2011-02-04 23:26:22: @gkronber commented

Reviewed NSGA-II operators in HeuristicLab.Analysis.MultiObjective, HeuristicLab.Optimization.Operators.MultiObjective and HeuristicLab.Selection and fixed minor issues with r5438.

HeuristicLab-Trac-Bot commented 13 years ago

2011-02-04 23:28:06: @gkronber commented

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!

HeuristicLab-Trac-Bot commented 13 years ago

2011-02-04 23:31:28: @gkronber commented

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.

HeuristicLab-Trac-Bot commented 13 years ago

2011-02-04 23:32:09: @gkronber changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 13 years ago

2011-02-04 23:32:09: @gkronber changed owner from gkronber to swagner

HeuristicLab-Trac-Bot commented 13 years ago

2011-02-05 18:59:42: @mkommend changed status from readytorelease to closed

HeuristicLab-Trac-Bot commented 13 years ago

2011-02-05 18:59:42: @mkommend removed resolution