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

Last change on this file since 12580 was 12580, checked in by mkommend, 6 years ago

#2411: Improved performance of FastNonDominantSort by using different data structures, avoiding LINQ and caching of dictionary entries.

File size: 8.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Optimization.Operators {
33  /// <summary>
34  /// FastNonDominatedSort as described in: Deb, Pratap, Agrawal and Meyarivan, "A Fast and Elitist Multiobjective
35  /// Genetic Algorithm: NSGA-II", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002
36  /// </summary>
37  [Item("FastNonDominatedSort", @"FastNonDominatedSort as described in: Deb, Pratap, Agrawal and Meyarivan, ""A Fast and Elitist Multiobjective
38Genetic Algorithm: NSGA-II"", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002")]
39  [StorableClass]
40  public class FastNonDominatedSort : SingleSuccessorOperator, IMultiObjectiveOperator {
41    private enum DominationResult { Dominates, IsDominated, IsNonDominated };
42
43    #region Parameter properties
44    public IValueLookupParameter<BoolArray> MaximizationParameter {
45      get { return (IValueLookupParameter<BoolArray>)Parameters["Maximization"]; }
46    }
47    public IValueLookupParameter<BoolValue> DominateOnEqualQualitiesParameter {
48      get { return (ValueLookupParameter<BoolValue>)Parameters["DominateOnEqualQualities"]; }
49    }
50    public IScopeTreeLookupParameter<DoubleArray> QualitiesParameter {
51      get { return (IScopeTreeLookupParameter<DoubleArray>)Parameters["Qualities"]; }
52    }
53    public IScopeTreeLookupParameter<IntValue> RankParameter {
54      get { return (IScopeTreeLookupParameter<IntValue>)Parameters["Rank"]; }
55    }
56    #endregion
57
58    [StorableConstructor]
59    protected FastNonDominatedSort(bool deserializing) : base(deserializing) { }
60    protected FastNonDominatedSort(FastNonDominatedSort original, Cloner cloner) : base(original, cloner) { }
61    public FastNonDominatedSort() {
62      Parameters.Add(new ValueLookupParameter<BoolArray>("Maximization", "Whether each objective is maximization or minimization."));
63      Parameters.Add(new ValueLookupParameter<BoolValue>("DominateOnEqualQualities", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
64      Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("Qualities", "The qualities of a solution.", 1));
65      Parameters.Add(new ScopeTreeLookupParameter<IntValue>("Rank", "The rank of a solution.", 1));
66    }
67
68    public override IOperation Apply() {
69      bool dominateOnEqualQualities = DominateOnEqualQualitiesParameter.ActualValue.Value;
70      bool[] maximization = MaximizationParameter.ActualValue.ToArray();
71      double[][] qualities = QualitiesParameter.ActualValue.Select(x => x.ToArray()).ToArray();
72      if (qualities == null) throw new InvalidOperationException(Name + ": No qualities found.");
73
74      IScope scope = ExecutionContext.Scope;
75      int populationSize = scope.SubScopes.Count;
76
77      List<ScopeList> fronts = new List<ScopeList>();
78      Dictionary<IScope, List<int>> dominatedScopes = new Dictionary<IScope, List<int>>();
79      int[] dominationCounter = new int[populationSize];
80      ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
81
82      for (int pI = 0; pI < populationSize - 1; pI++) {
83        IScope p = scope.SubScopes[pI];
84        List<int> dominatedScopesByp;
85        if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
86          dominatedScopes[p] = dominatedScopesByp = new List<int>();
87        for (int qI = pI + 1; qI < populationSize; qI++) {
88          DominationResult test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
89          if (test == DominationResult.Dominates) {
90            dominatedScopesByp.Add(qI);
91            dominationCounter[qI] += 1;
92          } else if (test == DominationResult.IsDominated) {
93            dominationCounter[pI] += 1;
94            if (!dominatedScopes.ContainsKey(scope.SubScopes[qI]))
95              dominatedScopes.Add(scope.SubScopes[qI], new List<int>());
96            dominatedScopes[scope.SubScopes[qI]].Add(pI);
97          }
98          if (pI == populationSize - 2
99            && qI == populationSize - 1
100            && dominationCounter[qI] == 0) {
101            rank[qI] = new IntValue(0);
102            AddToFront(scope.SubScopes[qI], fronts, 0);
103          }
104        }
105        if (dominationCounter[pI] == 0) {
106          rank[pI] = new IntValue(0);
107          AddToFront(p, fronts, 0);
108        }
109      }
110      int i = 0;
111      while (i < fronts.Count && fronts[i].Count > 0) {
112        ScopeList nextFront = new ScopeList();
113        foreach (IScope p in fronts[i]) {
114          List<int> dominatedScopesByp;
115          if (dominatedScopes.TryGetValue(p, out dominatedScopesByp)) {
116            for (int k = 0; k < dominatedScopesByp.Count; k++) {
117              int dominatedScope = dominatedScopesByp[k];
118              dominationCounter[dominatedScope] -= 1;
119              if (dominationCounter[dominatedScope] == 0) {
120                rank[dominatedScope] = new IntValue(i + 1);
121                nextFront.Add(scope.SubScopes[dominatedScope]);
122              }
123            }
124          }
125        }
126        i += 1;
127        fronts.Add(nextFront);
128      }
129
130      RankParameter.ActualValue = rank;
131
132      scope.SubScopes.Clear();
133
134      for (i = 0; i < fronts.Count; i++) {
135        Scope frontScope = new Scope("Front " + i);
136        foreach (var p in fronts[i])
137          frontScope.SubScopes.Add(p);
138        if (frontScope.SubScopes.Count > 0)
139          scope.SubScopes.Add(frontScope);
140      }
141      return base.Apply();
142    }
143
144    private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
145      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
146      if (dominateOnEqualQualities) {
147        var equal = true;
148        for (int i = 0; i < left.Length; i++) {
149          if (left[i] != right[i]) {
150            equal = false;
151            break;
152          }
153        }
154        if (equal) return DominationResult.Dominates;
155      }
156
157      bool leftIsBetter = false, rightIsBetter = false;
158      for (int i = 0; i < left.Length; i++) {
159        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
160        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
161        if (leftIsBetter && rightIsBetter) break;
162      }
163
164      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
165      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
166      return DominationResult.IsNonDominated;
167    }
168
169    private static bool IsDominated(double left, double right, bool maximization) {
170      return maximization && left < right
171        || !maximization && left > right;
172    }
173
174    private static void AddToFront(IScope p, List<ScopeList> fronts, int i) {
175      if (i == fronts.Count) fronts.Add(new ScopeList());
176      fronts[i].Add(p);
177    }
178
179    public override IDeepCloneable Clone(Cloner cloner) {
180      return new FastNonDominatedSort(this, cloner);
181    }
182
183    [StorableHook(HookType.AfterDeserialization)]
184    private void AfterDeserialization() {
185      // BackwardsCompatibility3.3
186      #region Backwards compatible code, remove with 3.4
187      if (!Parameters.ContainsKey("DominateOnEqualQualities"))
188        Parameters.Add(new ValueLookupParameter<BoolValue>("DominateOnEqualQualities", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
189      #endregion
190    }
191  }
192}
Note: See TracBrowser for help on using the repository browser.