Changeset 12034

Timestamp:

02/18/15 11:45:29 (9 years ago)

Author:

mkommend

Message:

#2321: Added option for treatment of solutions with equal quality values in NSGA-II.

Location:

branches/NSGA-II Changes

Files:

• HeuristicLab.Algorithms.NSGA2/3.3/NSGA2.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.NSGA2/3.3/NSGA2MainLoop.cs (modified) (3 diffs)
• HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs (modified) (9 diffs)
• HeuristicLab.Optimization.Operators/3.3/MultiObjective/RankAndCrowdingSorter.cs (modified) (5 diffs)

branches/NSGA-II Changes/HeuristicLab.Algorithms.NSGA2/3.3/NSGA2.cs

@@ -88 +88 @@
       get { return (ValueParameter<IntValue>)Parameters["SelectedParents"]; }
     }
+
+    private IFixedValueParameter<BoolValue> TreatSolutionsWithEqualQualityAsDominatedParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters["TreatSolutionsWithEqualQualityAsDominated"]; }
+    }
     #endregion
 
@@ -135 +139 @@
       set { SelectedParentsParameter.Value = value; }
     }
+    public bool TreatSolutionsWithEqualQualityAsDominated {
+      get { return TreatSolutionsWithEqualQualityAsDominatedParameter.Value.Value; }
+      set { TreatSolutionsWithEqualQualityAsDominatedParameter.Value.Value = value; }
+    }
+
     private RandomCreator RandomCreator {
       get { return (RandomCreator)OperatorGraph.InitialOperator; }
@@ -171 +180 @@
       Parameters.Add(new ValueParameter<IntValue>("MaximumGenerations", "The maximum number of generations which should be processed.", new IntValue(1000)));
       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)));
+      Parameters.Add(new FixedValueParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated.", new BoolValue(false)));
 
       RandomCreator randomCreator = new RandomCreator();
@@ -195 +205 @@
       subScopesCounter.Successor = rankAndCrowdingSorter;
 
+      rankAndCrowdingSorter.TreatSolutionsWithEqualQualityAsDominatedParameter.ActualName = TreatSolutionsWithEqualQualityAsDominatedParameter.Name;
       rankAndCrowdingSorter.CrowdingDistanceParameter.ActualName = "CrowdingDistance";
       rankAndCrowdingSorter.RankParameter.ActualName = "Rank";
@@ -311 +322 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      if (!Parameters.ContainsKey("TreatSolutionsWithEqualQualityAsDominated"))
+        Parameters.Add(new FixedValueParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated.", new BoolValue(false)));
+      #endregion
+
       PopulationSizeParameter.ValueChanged += new EventHandler(PopulationSizeParameter_ValueChanged);
       PopulationSize.ValueChanged += new EventHandler(PopulationSize_ValueChanged);

branches/NSGA-II Changes/HeuristicLab.Algorithms.NSGA2/3.3/NSGA2MainLoop.cs

@@ -79 +79 @@
       get { return (LookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
     }
+    public IValueLookupParameter<BoolValue> TreatSolutionsWithEqualQualityAsDominatedParameter {
+      get { return (ValueLookupParameter<BoolValue>)Parameters["TreatSolutionsWithEqualQualityAsDominated"]; }
+    }
     #endregion
 
     [StorableConstructor]
     protected NSGA2MainLoop(bool deserializing) : base(deserializing) { }
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      if (!Parameters.ContainsKey("TreatSolutionsWithEqualQualityAsDominated"))
+        Parameters.Add(new ValueLookupParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
+      #endregion
+    }
+
     protected NSGA2MainLoop(NSGA2MainLoop original, Cloner cloner) : base(original, cloner) { }
     public NSGA2MainLoop()
@@ -105 +117 @@
       Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The operator used to analyze each generation."));
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of times solutions have been evaluated."));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
       #endregion
 
@@ -171 +184 @@
       subScopesCounter.ValueParameter.ActualName = EvaluatedSolutionsParameter.Name;
 
+      rankAndCrowdingSorter.TreatSolutionsWithEqualQualityAsDominatedParameter.ActualName = TreatSolutionsWithEqualQualityAsDominatedParameter.Name;
       rankAndCrowdingSorter.CrowdingDistanceParameter.ActualName = "CrowdingDistance";
       rankAndCrowdingSorter.RankParameter.ActualName = "Rank";

branches/NSGA-II Changes/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Drawing;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -40 +42 @@
     private enum DominationResult { Dominates, IsDominated, IsNonDominated };
 
+    #region Parameter properties
     public IValueLookupParameter<BoolArray> MaximizationParameter {
       get { return (IValueLookupParameter<BoolArray>)Parameters["Maximization"]; }
     }
-
+    public IValueLookupParameter<BoolValue> TreatSolutionsWithEqualQualityAsDominatedParameter {
+      get { return (ValueLookupParameter<BoolValue>)Parameters["TreatSolutionsWithEqualQualityAsDominated"]; }
+    }
     public IScopeTreeLookupParameter<DoubleArray> QualitiesParameter {
       get { return (IScopeTreeLookupParameter<DoubleArray>)Parameters["Qualities"]; }
     }
-
     public IScopeTreeLookupParameter<IntValue> RankParameter {
       get { return (IScopeTreeLookupParameter<IntValue>)Parameters["Rank"]; }
     }
+    #endregion
 
     [StorableConstructor]
@@ -57 +62 @@
     public FastNonDominatedSort() {
       Parameters.Add(new ValueLookupParameter<BoolArray>("Maximization", "Whether each objective is maximization or minimization."));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
       Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("Qualities", "The qualities of a solution.", 1));
       Parameters.Add(new ScopeTreeLookupParameter<IntValue>("Rank", "The rank of a solution.", 1));
@@ -62 +68 @@
 
     public override IOperation Apply() {
+      bool treatSolutionsWithEqualQualityAsDominated = TreatSolutionsWithEqualQualityAsDominatedParameter.ActualValue.Value;
       BoolArray maximization = MaximizationParameter.ActualValue;
       ItemArray<DoubleArray> qualities = QualitiesParameter.ActualValue;
@@ -79 +86 @@
           dominatedScopes[p] = new List<int>();
         for (int qI = pI + 1; qI < populationSize; qI++) {
-          DominationResult test = Dominates(qualities[pI], qualities[qI], maximization);
+          DominationResult test = Dominates(qualities[pI], qualities[qI], maximization, treatSolutionsWithEqualQualityAsDominated);
           if (test == DominationResult.Dominates) {
             dominatedScopes[p].Add(qI);
@@ -134 +141 @@
     }
 
-    private DominationResult Dominates(DoubleArray left, DoubleArray right, BoolArray maximizations) {
+    private static DominationResult Dominates(DoubleArray left, DoubleArray right, BoolArray maximizations, bool treatSolutionsWithEqualQualityAsDominated) {
+      if (treatSolutionsWithEqualQualityAsDominated && left.SequenceEqual(right)) return DominationResult.Dominates;
+
       bool leftIsBetter = false, rightIsBetter = false;
       for (int i = 0; i < left.Length; i++) {
@@ -141 +150 @@
         if (leftIsBetter && rightIsBetter) break;
       }
+
       if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
       if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
@@ -146 +156 @@
     }
 
-    private bool IsDominated(double left, double right, bool maximization) {
+    private static bool IsDominated(double left, double right, bool maximization) {
       return maximization && left < right
         || !maximization && left > right;
     }
 
-    private void AddToFront(IScope p, List<ScopeList> fronts, int i) {
+    private static void AddToFront(IScope p, List<ScopeList> fronts, int i) {
       if (i == fronts.Count) fronts.Add(new ScopeList());
       fronts[i].Add(p);
@@ -159 +169 @@
       return new FastNonDominatedSort(this, cloner);
     }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      if (!Parameters.ContainsKey("TreatSolutionsWithEqualQualityAsDominated"))
+        Parameters.Add(new ValueLookupParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
+      #endregion
+    }
   }
 }

branches/NSGA-II Changes/HeuristicLab.Optimization.Operators/3.3/MultiObjective/RankAndCrowdingSorter.cs

@@ -30 +30 @@
 namespace HeuristicLab.Optimization.Operators {
   public class RankAndCrowdingSorter : AlgorithmOperator, IMultiObjectiveOperator {
+    #region Parameter properties
     public ValueLookupParameter<BoolArray> MaximizationParameter {
       get { return (ValueLookupParameter<BoolArray>)Parameters["Maximization"]; }
@@ -42 +43 @@
       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["CrowdingDistance"]; }
     }
+    public IValueLookupParameter<BoolValue> TreatSolutionsWithEqualQualityAsDominatedParameter {
+      get { return (ValueLookupParameter<BoolValue>)Parameters["TreatSolutionsWithEqualQualityAsDominated"]; }
+    }
+    #endregion
 
     [StorableConstructor]
@@ -49 +54 @@
       : base() {
       Parameters.Add(new ValueLookupParameter<BoolArray>("Maximization", "For each objective a value that is true if that objective should be maximized, or false if it should be minimized."));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
       Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("Qualities", "The vector of quality values."));
       Parameters.Add(new ScopeTreeLookupParameter<IntValue>("Rank", "The rank of a solution (to which front it belongs)."));
@@ -60 +66 @@
 
       fastNonDominatedSort.MaximizationParameter.ActualName = MaximizationParameter.Name;
+      fastNonDominatedSort.TreatSolutionsWithEqualQualityAsDominatedParameter.ActualName = TreatSolutionsWithEqualQualityAsDominatedParameter.Name;
       fastNonDominatedSort.QualitiesParameter.ActualName = QualitiesParameter.Name;
       fastNonDominatedSort.RankParameter.ActualName = RankParameter.Name;
@@ -81 +88 @@
       return new RankAndCrowdingSorter(this, cloner);
     }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      if (!Parameters.ContainsKey("TreatSolutionsWithEqualQualityAsDominated"))
+        Parameters.Add(new ValueLookupParameter<BoolValue>("TreatSolutionsWithEqualQualityAsDominated", "Flag which determines wether solutions with equal quality values should be treated as dominated."));
+      #endregion
+    }
   }
 }