Free cookie consent management tool by TermsFeed Policy Generator

Ticket #1040: FastNonDominatedSort.cs

File FastNonDominatedSort.cs, 4.7 KB (added by gkronber, 14 years ago)
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 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
21using System;
22using System.Collections.Generic;
23using System.Linq;
24using System.Text;
25using HeuristicLab.Core;
26using HeuristicLab.Common;
27using HeuristicLab.Data;
28using HeuristicLab.DataAnalysis;
29using HeuristicLab.Modeling;
30using HeuristicLab.GP;
31using HeuristicLab.GP.StructureIdentification;
32using HeuristicLab.GP.Interfaces;
33
34namespace HeuristicLab.LinearRegression {
35  /// <summary>
36  /// FastNonDominatedSort as described in: Deb, Pratap, Agrawal and Meyarivan, "A Fast and Elitist Multiobjective
37  /// Genetic Algorithm: NSGA-II", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002
38  /// </summary>
39  public class FastNonDominatedSort : OperatorBase {
40    private static double constant = 1.0;
41
42    public override string Description {
43      get {
44        return
45@"FastNonDominatedSort as described in: Deb, Pratap, Agrawal and Meyarivan, ""A Fast and Elitist Multiobjective
46Genetic Algorithm: NSGA-II"", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002";
47      }
48    }
49
50
51    public FastNonDominatedSort() {
52      AddVariableInfo(new VariableInfo("Quality", "Vector of quality values", typeof(ItemList<DoubleData>), VariableKind.In));
53    }
54
55    public override IOperation Apply(IScope scope) {
56      IVariableInfo qualityInfo = GetVariableInfo("Quality");
57      Dictionary<int, List<IScope>> f = new Dictionary<int, List<IScope>>();
58      Dictionary<IScope, List<IScope>> dominatedScopes = new Dictionary<IScope, List<IScope>>();
59      Dictionary<IScope, int> dominationCounter = new Dictionary<IScope, int>();
60      Dictionary<IScope, int> rank = new Dictionary<IScope, int>();
61      foreach (IScope p in scope.SubScopes) {
62        dominatedScopes[p] = new List<IScope>();
63        dominationCounter[p] = 0;
64        foreach (IScope q in scope.SubScopes) {
65          if (Dominates(p, q, qualityInfo)) {
66            dominatedScopes[p].Add(q);
67          } else if (Dominates(q, p, qualityInfo)) {
68            dominationCounter[p] += 1;
69          }
70        }
71        if (dominationCounter[p] == 0) {
72          rank[p] = 0;
73          AddToFront(p, f, 0);
74        }
75      }
76      int i = 0;
77      while (i < f.Count && f[i].Count > 0) {
78        List<IScope> nextFront = new List<IScope>();
79        foreach (IScope p in f[i]) {
80          foreach (IScope q in dominatedScopes[p]) {
81            dominationCounter[q] -= 1;
82            if (dominationCounter[q] == 0) {
83              rank[q] = i + 1;
84              nextFront.Add(q);
85            }
86          }
87        }
88        i += 1;
89        f[i] = nextFront;
90      }
91      while (scope.SubScopes.Count > 0) scope.RemoveSubScope(scope.SubScopes[0]);
92      for (i = 0; i < f.Count; i++) {
93        Scope frontScope = new Scope("Front " + i);
94        foreach (var p in f[i]) {
95          frontScope.AddSubScope(p);
96          var rankValue = p.GetVariableValue<DoubleData>("Rank", false, false);
97          if (rankValue != null) {
98            rankValue.Data = rank[p];
99          } else {
100            p.AddVariable(new HeuristicLab.Core.Variable("Rank", new DoubleData(rank[p])));
101          }
102        }
103        if (frontScope.SubScopes.Count > 0) scope.AddSubScope(frontScope);
104      }
105      return null;
106    }
107
108    private bool Dominates(IScope p, IScope q, IVariableInfo qualityInfo) {
109      ItemList<DoubleData> qQualities = q.GetVariableValue<ItemList<DoubleData>>(qualityInfo.ActualName, false);
110      ItemList<DoubleData> pQualities = p.GetVariableValue<ItemList<DoubleData>>(qualityInfo.ActualName, false);
111      for (int i = 0; i < pQualities.Count; i++) {
112        // when any quality component of q is better than p then p doesn't dominate q
113        if (qQualities[i].Data < pQualities[i].Data) return false;
114      }
115      return true;
116    }
117
118    private void AddToFront(IScope p, Dictionary<int, List<IScope>> f, int i) {
119      if (!f.ContainsKey(i)) f[i] = new List<IScope>();
120      f[i].Add(p);
121    }
122  }
123}