Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HLScript/HeuristicLab.Algorithms.NSGA2/3.3/NSGA2.cs @ 12029

Last change on this file since 12029 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 19.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.NSGA2 {
37  /// <summary>
38  /// 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.
39  /// </summary>
40  [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.")]
41  [Creatable("Algorithms")]
42  [StorableClass]
43  public class NSGA2 : HeuristicOptimizationEngineAlgorithm, IStorableContent {
44    public string Filename { get; set; }
45
46    #region Problem Properties
47    public override Type ProblemType {
48      get { return typeof(IMultiObjectiveHeuristicOptimizationProblem); }
49    }
50    public new IMultiObjectiveHeuristicOptimizationProblem Problem {
51      get { return (IMultiObjectiveHeuristicOptimizationProblem)base.Problem; }
52      set { base.Problem = value; }
53    }
54    #endregion
55
56    #region Parameter Properties
57    private ValueParameter<IntValue> SeedParameter {
58      get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
59    }
60    private ValueParameter<BoolValue> SetSeedRandomlyParameter {
61      get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
62    }
63    private ValueParameter<IntValue> PopulationSizeParameter {
64      get { return (ValueParameter<IntValue>)Parameters["PopulationSize"]; }
65    }
66    public IConstrainedValueParameter<ISelector> SelectorParameter {
67      get { return (IConstrainedValueParameter<ISelector>)Parameters["Selector"]; }
68    }
69    private ValueParameter<PercentValue> CrossoverProbabilityParameter {
70      get { return (ValueParameter<PercentValue>)Parameters["CrossoverProbability"]; }
71    }
72    public IConstrainedValueParameter<ICrossover> CrossoverParameter {
73      get { return (IConstrainedValueParameter<ICrossover>)Parameters["Crossover"]; }
74    }
75    private ValueParameter<PercentValue> MutationProbabilityParameter {
76      get { return (ValueParameter<PercentValue>)Parameters["MutationProbability"]; }
77    }
78    public IConstrainedValueParameter<IManipulator> MutatorParameter {
79      get { return (IConstrainedValueParameter<IManipulator>)Parameters["Mutator"]; }
80    }
81    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
82      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
83    }
84    private ValueParameter<IntValue> MaximumGenerationsParameter {
85      get { return (ValueParameter<IntValue>)Parameters["MaximumGenerations"]; }
86    }
87    private ValueParameter<IntValue> SelectedParentsParameter {
88      get { return (ValueParameter<IntValue>)Parameters["SelectedParents"]; }
89    }
90    #endregion
91
92    #region Properties
93    public IntValue Seed {
94      get { return SeedParameter.Value; }
95      set { SeedParameter.Value = value; }
96    }
97    public BoolValue SetSeedRandomly {
98      get { return SetSeedRandomlyParameter.Value; }
99      set { SetSeedRandomlyParameter.Value = value; }
100    }
101    public IntValue PopulationSize {
102      get { return PopulationSizeParameter.Value; }
103      set { PopulationSizeParameter.Value = value; }
104    }
105    public ISelector Selector {
106      get { return SelectorParameter.Value; }
107      set { SelectorParameter.Value = value; }
108    }
109    public PercentValue CrossoverProbability {
110      get { return CrossoverProbabilityParameter.Value; }
111      set { CrossoverProbabilityParameter.Value = value; }
112    }
113    public ICrossover Crossover {
114      get { return CrossoverParameter.Value; }
115      set { CrossoverParameter.Value = value; }
116    }
117    public PercentValue MutationProbability {
118      get { return MutationProbabilityParameter.Value; }
119      set { MutationProbabilityParameter.Value = value; }
120    }
121    public IManipulator Mutator {
122      get { return MutatorParameter.Value; }
123      set { MutatorParameter.Value = value; }
124    }
125    public MultiAnalyzer Analyzer {
126      get { return AnalyzerParameter.Value; }
127      set { AnalyzerParameter.Value = value; }
128    }
129    public IntValue MaximumGenerations {
130      get { return MaximumGenerationsParameter.Value; }
131      set { MaximumGenerationsParameter.Value = value; }
132    }
133    public IntValue SelectedParents {
134      get { return SelectedParentsParameter.Value; }
135      set { SelectedParentsParameter.Value = value; }
136    }
137    private RandomCreator RandomCreator {
138      get { return (RandomCreator)OperatorGraph.InitialOperator; }
139    }
140    private SolutionsCreator SolutionsCreator {
141      get { return (SolutionsCreator)RandomCreator.Successor; }
142    }
143    private RankAndCrowdingSorter RankAndCrowdingSorter {
144      get { return (RankAndCrowdingSorter)((SubScopesCounter)SolutionsCreator.Successor).Successor; }
145    }
146    private NSGA2MainLoop MainLoop {
147      get { return FindMainLoop(RankAndCrowdingSorter.Successor); }
148    }
149    #endregion
150
151    [Storable]
152    private RankBasedParetoFrontAnalyzer paretoFrontAnalyzer;
153
154    [StorableConstructor]
155    protected NSGA2(bool deserializing) : base(deserializing) { }
156    protected NSGA2(NSGA2 original, Cloner cloner)
157      : base(original, cloner) {
158      paretoFrontAnalyzer = (RankBasedParetoFrontAnalyzer)cloner.Clone(original.paretoFrontAnalyzer);
159      AfterDeserialization();
160    }
161    public NSGA2() {
162      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
163      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
164      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population of solutions.", new IntValue(100)));
165      Parameters.Add(new ConstrainedValueParameter<ISelector>("Selector", "The operator used to select solutions for reproduction."));
166      Parameters.Add(new ValueParameter<PercentValue>("CrossoverProbability", "The probability that the crossover operator is applied on two parents.", new PercentValue(0.9)));
167      Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover", "The operator used to cross solutions."));
168      Parameters.Add(new ValueParameter<PercentValue>("MutationProbability", "The probability that the mutation operator is applied on a solution.", new PercentValue(0.05)));
169      Parameters.Add(new OptionalConstrainedValueParameter<IManipulator>("Mutator", "The operator used to mutate solutions."));
170      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
171      Parameters.Add(new ValueParameter<IntValue>("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
172      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)));
173
174      RandomCreator randomCreator = new RandomCreator();
175      SolutionsCreator solutionsCreator = new SolutionsCreator();
176      SubScopesCounter subScopesCounter = new SubScopesCounter();
177      RankAndCrowdingSorter rankAndCrowdingSorter = new RankAndCrowdingSorter();
178      ResultsCollector resultsCollector = new ResultsCollector();
179      NSGA2MainLoop mainLoop = new NSGA2MainLoop();
180
181      OperatorGraph.InitialOperator = randomCreator;
182
183      randomCreator.RandomParameter.ActualName = "Random";
184      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
185      randomCreator.SeedParameter.Value = null;
186      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
187      randomCreator.SetSeedRandomlyParameter.Value = null;
188      randomCreator.Successor = solutionsCreator;
189
190      solutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name;
191      solutionsCreator.Successor = subScopesCounter;
192
193      subScopesCounter.Name = "Initialize EvaluatedSolutions";
194      subScopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
195      subScopesCounter.Successor = rankAndCrowdingSorter;
196
197      rankAndCrowdingSorter.CrowdingDistanceParameter.ActualName = "CrowdingDistance";
198      rankAndCrowdingSorter.RankParameter.ActualName = "Rank";
199      rankAndCrowdingSorter.Successor = resultsCollector;
200
201      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
202      resultsCollector.ResultsParameter.ActualName = "Results";
203      resultsCollector.Successor = mainLoop;
204
205      mainLoop.PopulationSizeParameter.ActualName = PopulationSizeParameter.Name;
206      mainLoop.SelectorParameter.ActualName = SelectorParameter.Name;
207      mainLoop.CrossoverParameter.ActualName = CrossoverParameter.Name;
208      mainLoop.CrossoverProbabilityParameter.ActualName = CrossoverProbabilityParameter.Name;
209      mainLoop.MaximumGenerationsParameter.ActualName = MaximumGenerationsParameter.Name;
210      mainLoop.MutatorParameter.ActualName = MutatorParameter.Name;
211      mainLoop.MutationProbabilityParameter.ActualName = MutationProbabilityParameter.Name;
212      mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
213      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
214      mainLoop.ResultsParameter.ActualName = "Results";
215      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
216
217      foreach (ISelector selector in ApplicationManager.Manager.GetInstances<ISelector>().Where(x => !(x is ISingleObjectiveSelector)).OrderBy(x => x.Name))
218        SelectorParameter.ValidValues.Add(selector);
219      ISelector tournamentSelector = SelectorParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("CrowdedTournamentSelector"));
220      if (tournamentSelector != null) SelectorParameter.Value = tournamentSelector;
221
222      ParameterizeSelectors();
223
224      paretoFrontAnalyzer = new RankBasedParetoFrontAnalyzer();
225      paretoFrontAnalyzer.RankParameter.ActualName = "Rank";
226      paretoFrontAnalyzer.RankParameter.Depth = 1;
227      paretoFrontAnalyzer.ResultsParameter.ActualName = "Results";
228      ParameterizeAnalyzers();
229      UpdateAnalyzers();
230
231      AfterDeserialization();
232    }
233
234    public override IDeepCloneable Clone(Cloner cloner) {
235      return new NSGA2(this, cloner);
236    }
237
238    public override void Prepare() {
239      if (Problem != null) base.Prepare();
240    }
241
242    #region Events
243    protected override void OnProblemChanged() {
244      ParameterizeStochasticOperator(Problem.SolutionCreator);
245      ParameterizeStochasticOperator(Problem.Evaluator);
246      foreach (IOperator op in Problem.Operators.OfType<IOperator>()) ParameterizeStochasticOperator(op);
247      ParameterizeSolutionsCreator();
248      ParameterizeRankAndCrowdingSorter();
249      ParameterizeMainLoop();
250      ParameterizeSelectors();
251      ParameterizeAnalyzers();
252      ParameterizeIterationBasedOperators();
253      UpdateCrossovers();
254      UpdateMutators();
255      UpdateAnalyzers();
256      Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
257      base.OnProblemChanged();
258    }
259    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
260      ParameterizeStochasticOperator(Problem.SolutionCreator);
261      ParameterizeSolutionsCreator();
262      base.Problem_SolutionCreatorChanged(sender, e);
263    }
264    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
265      ParameterizeStochasticOperator(Problem.Evaluator);
266      ParameterizeSolutionsCreator();
267      ParameterizeRankAndCrowdingSorter();
268      ParameterizeMainLoop();
269      ParameterizeSelectors();
270      ParameterizeAnalyzers();
271      Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
272      base.Problem_EvaluatorChanged(sender, e);
273    }
274    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
275      foreach (IOperator op in Problem.Operators.OfType<IOperator>()) ParameterizeStochasticOperator(op);
276      ParameterizeIterationBasedOperators();
277      UpdateCrossovers();
278      UpdateMutators();
279      UpdateAnalyzers();
280      base.Problem_OperatorsChanged(sender, e);
281    }
282    protected override void Problem_Reset(object sender, EventArgs e) {
283      base.Problem_Reset(sender, e);
284    }
285    private void PopulationSizeParameter_ValueChanged(object sender, EventArgs e) {
286      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
287      ParameterizeSelectors();
288    }
289    private void PopulationSize_ValueChanged(object sender, EventArgs e) {
290      ParameterizeSelectors();
291    }
292    private void Evaluator_QualitiesParameter_ActualNameChanged(object sender, EventArgs e) {
293      ParameterizeRankAndCrowdingSorter();
294      ParameterizeMainLoop();
295      ParameterizeSelectors();
296      ParameterizeAnalyzers();
297    }
298    private void SelectedParentsParameter_ValueChanged(object sender, EventArgs e) {
299      SelectedParents.ValueChanged += new EventHandler(SelectedParents_ValueChanged);
300      SelectedParents_ValueChanged(null, EventArgs.Empty);
301    }
302    private void SelectedParents_ValueChanged(object sender, EventArgs e) {
303      if (SelectedParents.Value < 2) SelectedParents.Value = 2;
304      else if (SelectedParents.Value % 2 != 0) {
305        SelectedParents.Value = SelectedParents.Value + 1;
306      }
307    }
308    #endregion
309
310    #region Helpers
311    [StorableHook(HookType.AfterDeserialization)]
312    private void AfterDeserialization() {
313      PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
314      PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);
315      SelectedParentsParameter.ValueChanged += new EventHandler(SelectedParentsParameter_ValueChanged);
316      SelectedParents.ValueChanged += new EventHandler(SelectedParents_ValueChanged);
317      if (Problem != null) {
318        Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
319      }
320    }
321    private void ParameterizeSolutionsCreator() {
322      SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
323      SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
324    }
325    private void ParameterizeRankAndCrowdingSorter() {
326      RankAndCrowdingSorter.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
327      RankAndCrowdingSorter.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
328    }
329    private void ParameterizeMainLoop() {
330      MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
331      MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
332      MainLoop.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
333    }
334    private void ParameterizeStochasticOperator(IOperator op) {
335      if (op is IStochasticOperator)
336        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
337    }
338    private void ParameterizeSelectors() {
339      foreach (ISelector selector in SelectorParameter.ValidValues) {
340        selector.CopySelected = new BoolValue(true);
341        selector.NumberOfSelectedSubScopesParameter.ActualName = SelectedParentsParameter.Name;
342        ParameterizeStochasticOperator(selector);
343      }
344      if (Problem != null) {
345        foreach (IMultiObjectiveSelector selector in SelectorParameter.ValidValues.OfType<IMultiObjectiveSelector>()) {
346          selector.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
347          selector.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
348        }
349      }
350    }
351    private void ParameterizeAnalyzers() {
352      if (Problem != null) {
353        paretoFrontAnalyzer.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
354        paretoFrontAnalyzer.QualitiesParameter.Depth = 1;
355      }
356    }
357    private void ParameterizeIterationBasedOperators() {
358      if (Problem != null) {
359        foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
360          op.IterationsParameter.ActualName = "Generations";
361          op.MaximumIterationsParameter.ActualName = "MaximumGenerations";
362        }
363      }
364    }
365    private void UpdateCrossovers() {
366      ICrossover oldCrossover = CrossoverParameter.Value;
367      ICrossover defaultCrossover = Problem.Operators.OfType<ICrossover>().FirstOrDefault();
368      CrossoverParameter.ValidValues.Clear();
369      foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
370        CrossoverParameter.ValidValues.Add(crossover);
371      if (oldCrossover != null) {
372        ICrossover crossover = CrossoverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldCrossover.GetType());
373        if (crossover != null) CrossoverParameter.Value = crossover;
374        else oldCrossover = null;
375      }
376      if (oldCrossover == null && defaultCrossover != null)
377        CrossoverParameter.Value = defaultCrossover;
378    }
379    private void UpdateMutators() {
380      IManipulator oldMutator = MutatorParameter.Value;
381      MutatorParameter.ValidValues.Clear();
382      foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name))
383        MutatorParameter.ValidValues.Add(mutator);
384      if (oldMutator != null) {
385        IManipulator mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
386        if (mutator != null) MutatorParameter.Value = mutator;
387      }
388    }
389    private void UpdateAnalyzers() {
390      Analyzer.Operators.Clear();
391      if (Problem != null) {
392        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
393          foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
394            param.Depth = 1;
395          Analyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
396        }
397      }
398      Analyzer.Operators.Add(paretoFrontAnalyzer, paretoFrontAnalyzer.EnabledByDefault);
399    }
400    private NSGA2MainLoop FindMainLoop(IOperator start) {
401      IOperator mainLoop = start;
402      while (mainLoop != null && !(mainLoop is NSGA2MainLoop))
403        mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
404      if (mainLoop == null) return null;
405      else return (NSGA2MainLoop)mainLoop;
406    }
407    #endregion
408  }
409}
Note: See TracBrowser for help on using the repository browser.