Free cookie consent management tool by TermsFeed Policy Generator

source: branches/NSGA2/HeuristicLab.Algorithms.NSGA2/3.3/NSGA2.cs @ 4514

Last change on this file since 4514 was 4514, checked in by abeham, 12 years ago

#1040

  • Added SelectedParents parameter to define the size of the offspring population
File size: 18.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Random;
34
35namespace HeuristicLab.Algorithms.NSGA2 {
36  /// <summary>
37  /// The Nondominated Sorting Genetic Algorithm II was introduced in Deb et al. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), pp. 182-197.
38  /// </summary>
39  [Item("NSGA-II", "The Nondominated Sorting Genetic Algorithm II was introduced in Deb et al. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), pp. 182-197.")]
40  [Creatable("Algorithms")]
41  [StorableClass]
42  public class NSGA2 : EngineAlgorithm {
43    #region Problem Properties
44    public override Type ProblemType {
45      get { return typeof(IMultiObjectiveProblem); }
46    }
47    public new IMultiObjectiveProblem Problem {
48      get { return (IMultiObjectiveProblem)base.Problem; }
49      set { base.Problem = value; }
50    }
51    #endregion
52
53    #region Parameter Properties
54    private ValueParameter<IntValue> SeedParameter {
55      get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
56    }
57    private ValueParameter<BoolValue> SetSeedRandomlyParameter {
58      get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
59    }
60    private ValueParameter<IntValue> PopulationSizeParameter {
61      get { return (ValueParameter<IntValue>)Parameters["PopulationSize"]; }
62    }
63    private ConstrainedValueParameter<ISelector> SelectorParameter {
64      get { return (ConstrainedValueParameter<ISelector>)Parameters["Selector"]; }
65    }
66    private ValueParameter<PercentValue> CrossoverProbabilityParameter {
67      get { return (ValueParameter<PercentValue>)Parameters["CrossoverProbability"]; }
68    }
69    private ConstrainedValueParameter<ICrossover> CrossoverParameter {
70      get { return (ConstrainedValueParameter<ICrossover>)Parameters["Crossover"]; }
71    }
72    private ValueParameter<PercentValue> MutationProbabilityParameter {
73      get { return (ValueParameter<PercentValue>)Parameters["MutationProbability"]; }
74    }
75    private OptionalConstrainedValueParameter<IManipulator> MutatorParameter {
76      get { return (OptionalConstrainedValueParameter<IManipulator>)Parameters["Mutator"]; }
77    }
78    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
79      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
80    }
81    private ValueParameter<IntValue> MaximumGenerationsParameter {
82      get { return (ValueParameter<IntValue>)Parameters["MaximumGenerations"]; }
83    }
84    private ValueParameter<IntValue> SelectedParentsParameter {
85      get { return (ValueParameter<IntValue>)Parameters["SelectedParents"]; }
86    }
87    #endregion
88
89    #region Properties
90    public IntValue Seed {
91      get { return SeedParameter.Value; }
92      set { SeedParameter.Value = value; }
93    }
94    public BoolValue SetSeedRandomly {
95      get { return SetSeedRandomlyParameter.Value; }
96      set { SetSeedRandomlyParameter.Value = value; }
97    }
98    public IntValue PopulationSize {
99      get { return PopulationSizeParameter.Value; }
100      set { PopulationSizeParameter.Value = value; }
101    }
102    public ISelector Selector {
103      get { return SelectorParameter.Value; }
104      set { SelectorParameter.Value = value; }
105    }
106    public PercentValue CrossoverProbability {
107      get { return CrossoverProbabilityParameter.Value; }
108      set { CrossoverProbabilityParameter.Value = value; }
109    }
110    public ICrossover Crossover {
111      get { return CrossoverParameter.Value; }
112      set { CrossoverParameter.Value = value; }
113    }
114    public PercentValue MutationProbability {
115      get { return MutationProbabilityParameter.Value; }
116      set { MutationProbabilityParameter.Value = value; }
117    }
118    public IManipulator Mutator {
119      get { return MutatorParameter.Value; }
120      set { MutatorParameter.Value = value; }
121    }
122    public MultiAnalyzer Analyzer {
123      get { return AnalyzerParameter.Value; }
124      set { AnalyzerParameter.Value = value; }
125    }
126    public IntValue MaximumGenerations {
127      get { return MaximumGenerationsParameter.Value; }
128      set { MaximumGenerationsParameter.Value = value; }
129    }
130    public IntValue SelectedParents {
131      get { return SelectedParentsParameter.Value; }
132      set { SelectedParentsParameter.Value = value; }
133    }
134    private RandomCreator RandomCreator {
135      get { return (RandomCreator)OperatorGraph.InitialOperator; }
136    }
137    private SolutionsCreator SolutionsCreator {
138      get { return (SolutionsCreator)RandomCreator.Successor; }
139    }
140    private RankAndCrowdingSorter RankAndCrowdingSorter {
141      get { return (RankAndCrowdingSorter)SolutionsCreator.Successor; }
142    }
143    private NSGA2MainLoop MainLoop {
144      get { return (NSGA2MainLoop)RankAndCrowdingSorter.Successor; }
145    }
146    #endregion
147
148    [Storable]
149    private BasicMultiObjectiveQualityAnalyzer basicMOQualityAnalyzer;
150
151    [StorableConstructor]
152    public NSGA2(bool deserializing) : base(deserializing) { }
153    public NSGA2() {
154      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
155      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
156      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population of solutions.", new IntValue(100)));
157      Parameters.Add(new ConstrainedValueParameter<ISelector>("Selector", "The operator used to select solutions for reproduction."));
158      Parameters.Add(new ValueParameter<PercentValue>("CrossoverProbability", "The probability that the crossover operator is applied on two parents.", new PercentValue(0.9)));
159      Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover", "The operator used to cross solutions."));
160      Parameters.Add(new ValueParameter<PercentValue>("MutationProbability", "The probability that the mutation operator is applied on a solution.", new PercentValue(0.05)));
161      Parameters.Add(new OptionalConstrainedValueParameter<IManipulator>("Mutator", "The operator used to mutate solutions."));
162      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
163      Parameters.Add(new ValueParameter<IntValue>("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
164      Parameters.Add(new ValueParameter<IntValue>("SelectedParents", "Each two parents form a new child, typically this value should be twice the population size, but because the NSGA-II is maximally elitist it can be any multiple of 2 greater than 0.", new IntValue(200)));
165
166      RandomCreator randomCreator = new RandomCreator();
167      SolutionsCreator solutionsCreator = new SolutionsCreator();
168      RankAndCrowdingSorter rankAndCrowdingSorter = new RankAndCrowdingSorter();
169      NSGA2MainLoop mainLoop = new NSGA2MainLoop();
170     
171      OperatorGraph.InitialOperator = randomCreator;
172
173      randomCreator.RandomParameter.ActualName = "Random";
174      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
175      randomCreator.SeedParameter.Value = null;
176      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
177      randomCreator.SetSeedRandomlyParameter.Value = null;
178      randomCreator.Successor = solutionsCreator;
179
180      solutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name;
181      solutionsCreator.Successor = rankAndCrowdingSorter;
182
183      rankAndCrowdingSorter.CrowdingDistanceParameter.ActualName = "CrowdingDistance";
184      rankAndCrowdingSorter.RankParameter.ActualName = "Rank";
185      rankAndCrowdingSorter.Successor = mainLoop;
186
187      mainLoop.PopulationSizeParameter.ActualName = PopulationSizeParameter.Name;
188      mainLoop.SelectorParameter.ActualName = SelectorParameter.Name;
189      mainLoop.CrossoverParameter.ActualName = CrossoverParameter.Name;
190      mainLoop.CrossoverProbabilityParameter.ActualName = CrossoverProbabilityParameter.Name;
191      mainLoop.MaximumGenerationsParameter.ActualName = MaximumGenerationsParameter.Name;
192      mainLoop.MutatorParameter.ActualName = MutatorParameter.Name;
193      mainLoop.MutationProbabilityParameter.ActualName = MutationProbabilityParameter.Name;
194      mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
195      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
196      mainLoop.ResultsParameter.ActualName = "Results";
197
198      foreach (ISelector selector in ApplicationManager.Manager.GetInstances<ISelector>().Where(x => !(x is ISingleObjectiveSelector)).OrderBy(x => x.Name))
199        SelectorParameter.ValidValues.Add(selector);
200      ISelector tournamentSelector = SelectorParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("CrowdedTournamentSelector"));
201      if (tournamentSelector != null) SelectorParameter.Value = tournamentSelector;
202
203      ParameterizeSelectors();
204
205      basicMOQualityAnalyzer = new BasicMultiObjectiveQualityAnalyzer();
206      basicMOQualityAnalyzer.RankParameter.ActualName = "Rank";
207      basicMOQualityAnalyzer.RankParameter.Depth = 1;
208      basicMOQualityAnalyzer.ResultsParameter.ActualName = "Results";
209      ParameterizeAnalyzers();
210      UpdateAnalyzers();
211
212      AttachEventHandlers();
213    }
214
215    public override IDeepCloneable Clone(Cloner cloner) {
216      NSGA2 clone = (NSGA2)base.Clone(cloner);
217      clone.basicMOQualityAnalyzer = (BasicMultiObjectiveQualityAnalyzer)cloner.Clone(basicMOQualityAnalyzer);
218      clone.AttachEventHandlers();
219      return clone;
220    }
221
222    #region Events
223    protected override void OnProblemChanged() {
224      ParameterizeStochasticOperator(Problem.SolutionCreator);
225      ParameterizeStochasticOperator(Problem.Evaluator);
226      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
227      ParameterizeSolutionsCreator();
228      ParameterizeRankAndCrowdingSorter();
229      ParameterizeMainLoop();
230      ParameterizeSelectors();
231      ParameterizeAnalyzers();
232      ParameterizeIterationBasedOperators();
233      UpdateCrossovers();
234      UpdateMutators();
235      UpdateAnalyzers();
236      Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
237      base.OnProblemChanged();
238    }
239    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
240      ParameterizeStochasticOperator(Problem.SolutionCreator);
241      ParameterizeSolutionsCreator();
242      base.Problem_SolutionCreatorChanged(sender, e);
243    }
244    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
245      ParameterizeStochasticOperator(Problem.Evaluator);
246      ParameterizeSolutionsCreator();
247      ParameterizeRankAndCrowdingSorter();
248      ParameterizeMainLoop();
249      ParameterizeSelectors();
250      ParameterizeAnalyzers();
251      Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
252      base.Problem_EvaluatorChanged(sender, e);
253    }
254    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
255      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
256      ParameterizeIterationBasedOperators();
257      UpdateCrossovers();
258      UpdateMutators();
259      UpdateAnalyzers();
260      base.Problem_OperatorsChanged(sender, e);
261    }
262    protected override void Problem_Reset(object sender, EventArgs e) {
263      base.Problem_Reset(sender, e);
264    }
265    private void PopulationSizeParameter_ValueChanged(object sender, EventArgs e) {
266      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
267      ParameterizeSelectors();
268    }
269    private void PopulationSize_ValueChanged(object sender, EventArgs e) {
270      ParameterizeSelectors();
271    }
272    private void Evaluator_QualitiesParameter_ActualNameChanged(object sender, EventArgs e) {
273      ParameterizeRankAndCrowdingSorter();
274      ParameterizeMainLoop();
275      ParameterizeSelectors();
276      ParameterizeAnalyzers();
277    }
278    private void SelectedParentsParameter_ValueChanged(object sender, EventArgs e) {
279      SelectedParents.ValueChanged += new EventHandler(SelectedParents_ValueChanged);
280      SelectedParents_ValueChanged(null, EventArgs.Empty);
281    }
282    private void SelectedParents_ValueChanged(object sender, EventArgs e) {
283      if (SelectedParents.Value < 2) SelectedParents.Value = 2;
284      else if (SelectedParents.Value % 2 != 0) {
285        SelectedParents.Value = SelectedParents.Value + 1;
286      }
287    }
288    #endregion
289
290    #region Helpers
291    [StorableHook(HookType.AfterDeserialization)]
292    private void AttachEventHandlers() {
293      PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
294      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
295      SelectedParentsParameter.ValueChanged += new EventHandler(SelectedParentsParameter_ValueChanged);
296      SelectedParents.ValueChanged += new EventHandler(SelectedParents_ValueChanged);
297      if (Problem != null) {
298        Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
299      }
300    }
301    private void ParameterizeSolutionsCreator() {
302      SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
303      SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
304    }
305    private void ParameterizeRankAndCrowdingSorter() {
306      RankAndCrowdingSorter.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
307      RankAndCrowdingSorter.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
308    }
309    private void ParameterizeMainLoop() {
310      MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
311      MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
312      MainLoop.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
313    }
314    private void ParameterizeStochasticOperator(IOperator op) {
315      if (op is IStochasticOperator)
316        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
317    }
318    private void ParameterizeSelectors() {
319      foreach (ISelector selector in SelectorParameter.ValidValues) {
320        selector.CopySelected = new BoolValue(true);
321        selector.NumberOfSelectedSubScopesParameter.ActualName = SelectedParentsParameter.Name;
322        ParameterizeStochasticOperator(selector);
323      }
324      if (Problem != null) {
325        foreach (IMultiObjectiveSelector selector in SelectorParameter.ValidValues.OfType<IMultiObjectiveSelector>()) {
326          selector.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
327          selector.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
328        }
329      }
330    }
331    private void ParameterizeAnalyzers() {
332      if (Problem != null) {
333        basicMOQualityAnalyzer.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
334        basicMOQualityAnalyzer.QualitiesParameter.Depth = 1;
335      }
336    }
337    private void ParameterizeIterationBasedOperators() {
338      if (Problem != null) {
339        foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
340          op.IterationsParameter.ActualName = "Generations";
341          op.MaximumIterationsParameter.ActualName = "MaximumGenerations";
342        }
343      }
344    }
345    private void UpdateCrossovers() {
346      ICrossover oldCrossover = CrossoverParameter.Value;
347      CrossoverParameter.ValidValues.Clear();
348      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
349        CrossoverParameter.ValidValues.Add(crossover);
350      if (oldCrossover != null) {
351        ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType());
352        if (crossover != null) CrossoverParameter.Value = crossover;
353      }
354    }
355    private void UpdateMutators() {
356      IManipulator oldMutator = MutatorParameter.Value;
357      MutatorParameter.ValidValues.Clear();
358      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name))
359        MutatorParameter.ValidValues.Add(mutator);
360      if (oldMutator != null) {
361        IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
362        if (mutator != null) MutatorParameter.Value = mutator;
363      }
364    }
365    private void UpdateAnalyzers() {
366      Analyzer.Operators.Clear();
367      if (Problem != null) {
368        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
369          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
370            param.Depth = 1;
371          Analyzer.Operators.Add(analyzer);
372        }
373      }
374      Analyzer.Operators.Add(basicMOQualityAnalyzer);
375    }
376    #endregion
377  }
378}
Note: See TracBrowser for help on using the repository browser.