Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs @ 5143

Last change on this file since 5143 was 5143, checked in by abeham, 13 years ago

#1040

  • 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)
File size: 6.8 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.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Optimization.Operators {
32  /// <summary>
33  /// FastNonDominatedSort as described in: Deb, Pratap, Agrawal and Meyarivan, "A Fast and Elitist Multiobjective
34  /// Genetic Algorithm: NSGA-II", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002
35  /// </summary>
36  [Item("FastNonDominatedSort", @"FastNonDominatedSort as described in: Deb, Pratap, Agrawal and Meyarivan, ""A Fast and Elitist Multiobjective
37Genetic Algorithm: NSGA-II"", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002")]
38  [StorableClass]
39  public class FastNonDominatedSort : SingleSuccessorOperator {
40    private enum DominationResult { Dominates, IsDominated, IsNonDominated };
41
42    public IValueLookupParameter<BoolArray> MaximizationParameter {
43      get { return (IValueLookupParameter<BoolArray>)Parameters["Maximization"]; }
44    }
45
46    public IScopeTreeLookupParameter<DoubleArray> QualitiesParameter {
47      get { return (IScopeTreeLookupParameter<DoubleArray>)Parameters["Qualities"]; }
48    }
49
50    public IScopeTreeLookupParameter<IntValue> RankParameter {
51      get { return (IScopeTreeLookupParameter<IntValue>)Parameters["Rank"]; }
52    }
53
54    [StorableConstructor]
55    protected FastNonDominatedSort(bool deserializing) : base(deserializing) { }
56    protected FastNonDominatedSort(FastNonDominatedSort original, Cloner cloner) : base(original, cloner) { }
57    public FastNonDominatedSort() {
58      Parameters.Add(new ValueLookupParameter<BoolArray>("Maximization", "Whether each objective is maximization or minimization."));
59      Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("Qualities", "The qualities of a solution.", 1));
60      Parameters.Add(new ScopeTreeLookupParameter<IntValue>("Rank", "The rank of a solution.", 1));
61    }
62
63    public override IOperation Apply() {
64      BoolArray maximization = MaximizationParameter.ActualValue;
65      ItemArray<DoubleArray> qualities = QualitiesParameter.ActualValue;
66      if (qualities == null) throw new InvalidOperationException(Name + ": No qualities found.");
67
68      IScope scope = ExecutionContext.Scope;
69      int populationSize = scope.SubScopes.Count;
70
71      List<ScopeList> fronts = new List<ScopeList>();
72      Dictionary<IScope, List<int>> dominatedScopes = new Dictionary<IScope, List<int>>();
73      int[] dominationCounter = new int[populationSize];
74      ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
75
76      for (int pI = 0; pI < populationSize - 1; pI++) {
77        IScope p = scope.SubScopes[pI];
78        if (!dominatedScopes.ContainsKey(p))
79          dominatedScopes[p] = new List<int>();
80        for (int qI = pI + 1; qI < populationSize; qI++) {
81          DominationResult test = Dominates(qualities[pI], qualities[qI], maximization);
82          if (test == DominationResult.Dominates) {
83            dominatedScopes[p].Add(qI);
84            dominationCounter[qI] += 1;
85          } else if (test == DominationResult.IsDominated) {
86            dominationCounter[pI] += 1;
87            if (!dominatedScopes.ContainsKey(scope.SubScopes[qI]))
88              dominatedScopes.Add(scope.SubScopes[qI], new List<int>());
89            dominatedScopes[scope.SubScopes[qI]].Add(pI);
90          }
91          if (pI == populationSize - 2
92            && qI == populationSize - 1
93            && dominationCounter[qI] == 0) {
94            rank[qI] = new IntValue(0);
95            AddToFront(scope.SubScopes[qI], fronts, 0);
96          }
97        }
98        if (dominationCounter[pI] == 0) {
99          rank[pI] = new IntValue(0);
100          AddToFront(p, fronts, 0);
101        }
102      }
103      int i = 0;
104      while (i < fronts.Count && fronts[i].Count > 0) {
105        ScopeList nextFront = new ScopeList();
106        foreach (IScope p in fronts[i]) {
107          if (dominatedScopes.ContainsKey(p)) {
108            for (int k = 0; k < dominatedScopes[p].Count; k++) {
109              int dominatedScope = dominatedScopes[p][k];
110              dominationCounter[dominatedScope] -= 1;
111              if (dominationCounter[dominatedScope] == 0) {
112                rank[dominatedScope] = new IntValue(i + 1);
113                nextFront.Add(scope.SubScopes[dominatedScope]);
114              }
115            }
116          }
117        }
118        i += 1;
119        fronts.Add(nextFront);
120      }
121
122      RankParameter.ActualValue = rank;
123
124      scope.SubScopes.Clear();
125
126      for (i = 0; i < fronts.Count; i++) {
127        Scope frontScope = new Scope("Front " + i);
128        foreach (var p in fronts[i])
129          frontScope.SubScopes.Add(p);
130        if (frontScope.SubScopes.Count > 0)
131          scope.SubScopes.Add(frontScope);
132      }
133      return base.Apply();
134    }
135
136    private DominationResult Dominates(DoubleArray left, DoubleArray right, BoolArray maximizations) {
137      bool leftIsBetter = false, rightIsBetter = false;
138      for (int i = 0; i < left.Length; i++) {
139        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
140        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
141        if (leftIsBetter && rightIsBetter) break;
142      }
143      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
144      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
145      return DominationResult.IsNonDominated;
146    }
147
148    private bool IsDominated(double left, double right, bool maximization) {
149      return maximization && left < right
150        || !maximization && left > right;
151    }
152
153    private void AddToFront(IScope p, List<ScopeList> fronts, int i) {
154      if (i == fronts.Count) fronts.Add(new ScopeList());
155      fronts[i].Add(p);
156    }
157
158    public override IDeepCloneable Clone(Cloner cloner) {
159      return new FastNonDominatedSort(this, cloner);
160    }
161  }
162}
Note: See TracBrowser for help on using the repository browser.