Changeset 6018 for branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers

Timestamp:

04/17/11 18:22:28 (13 years ago)

Author:

cneumuel

Message:

#1215

• support for maximization problems
• made base level algorithms stoppable
• optimization for multiple goals possible (AverageQuality, AverageDeviation, AverageEvaluatedSolutions)
• lots of fixes

Location:

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers

Files:

• BestParameterConfigurationAnalyzer.cs (modified) (6 diffs)
• PMOBestSolutionHistoryAnalyzer.cs (modified) (4 diffs)
• PMOProblemQualitiesAnalyzer.cs (modified) (5 diffs)
• ReferenceQualityAnalyzer.cs (modified) (6 diffs)
• SolutionCacheAnalyzer.cs (modified) (3 diffs)

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers/BestParameterConfigurationAnalyzer.cs

@@ -7 +7 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
-using System;
 
 namespace HeuristicLab.Problems.MetaOptimization {
@@ -39 +37 @@
       get { return (LookupParameter<RunCollection>)Parameters["Population"]; }
     }
-    public LookupParameter<DoubleArray> ProblemQualityReferencesParameter {
-      get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityReferences"]; }
-    }
     public LookupParameter<ConstrainedItemList<IProblem>> ProblemsParameter {
       get { return (LookupParameter<ConstrainedItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
+    }
+    public LookupParameter<BoolValue> MaximizationParameter {
+      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
     }
 
@@ -55 +53 @@
       Parameters.Add(new LookupParameter<IRun>("BestKnownSolution", ""));
       Parameters.Add(new LookupParameter<RunCollection>("Population", ""));
-      Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityReferences", ""));
       Parameters.Add(new LookupParameter<ConstrainedItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName));
+      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Set to false if the problem should be minimized."));
     }
 
@@ -71 +69 @@
       DoubleValue bestKnownQuality = BestKnownQualityParameter.ActualValue;
       ItemArray<ParameterConfigurationTree> parameterTrees = ParameterConfigurationParameter.ActualValue;
+      bool maximization = MaximizationParameter.ActualValue.Value;
 
-      int idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
+      int idxBest;
+      if (maximization)
+        idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).Last().index;
+      else
+        idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
 
       ParameterConfigurationTree best = (ParameterConfigurationTree)parameterTrees[idxBest];
@@ -79 +82 @@
       best.CollectParameterValues(bestRun.Parameters);
 
-      if (bestKnownQuality == null || qualities[idxBest].Value < bestKnownQuality.Value) { // todo: respect Maximization:true/false
+      if (bestKnownQuality == null || 
+        (!maximization && (qualities[idxBest].Value < bestKnownQuality.Value) ||
+        (maximization && (qualities[idxBest].Value > bestKnownQuality.Value)))) {
         BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[idxBest].Value);
 
@@ -96 +101 @@
       int i = 0;
       RunCollection rc = new RunCollection();
-      foreach (ParameterConfigurationTree pt in parameterTrees.OrderBy(x => x.AverageQualityNormalized)) { // todo: respect Maximization:true/false
+      foreach (ParameterConfigurationTree pt in (maximization ? parameterTrees.OrderByDescending(x => x.Quality) : parameterTrees.OrderBy(x => x.Quality))) {
         rc.Add(pt.ToRun(string.Format("Individual {0} ({1})", i, pt.ParameterInfoString)));
         i++;

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers/PMOBestSolutionHistoryAnalyzer.cs

@@ -7 +7 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
-using System;
-using HeuristicLab.Analysis;
 
 namespace HeuristicLab.Problems.MetaOptimization {
@@ -34 +31 @@
       get { return (LookupParameter<IntValue>)Parameters["Generations"]; }
     }
+    public LookupParameter<BoolValue> MaximizationParameter {
+      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
 
     public PMOBestSolutionHistoryAnalyzer()
@@ -42 +42 @@
       Parameters.Add(new LookupParameter<ConstrainedItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName));
       Parameters.Add(new LookupParameter<IntValue>("Generations", ""));
+      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Set to false if the problem should be minimized."));
     }
 
@@ -56 +57 @@
       ItemArray<ParameterConfigurationTree> parameterTrees = ParameterConfigurationParameter.ActualValue;
       int currentGeneration = GenerationsParameter.ActualValue.Value;
-      int idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index; // todo: respect Min/Max
+      bool maximization = MaximizationParameter.ActualValue.Value;
+
+      int idxBest;
+      if (maximization)
+        idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).Last().index;
+      else
+        idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
+
       ParameterConfigurationTree best = parameterTrees[idxBest];
 

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers/PMOProblemQualitiesAnalyzer.cs

@@ -1 +1 @@
 using System.Linq;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -7 +8 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
-using System;
-using HeuristicLab.Analysis;
 
 namespace HeuristicLab.Problems.MetaOptimization {
@@ -31 +29 @@
       get { return (LookupParameter<ConstrainedItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
     }
+    public LookupParameter<BoolValue> MaximizationParameter {
+      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
 
     public PMOProblemQualitiesAnalyzer()
@@ -38 +39 @@
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", ""));
       Parameters.Add(new LookupParameter<ConstrainedItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName));
+      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Set to false if the problem should be minimized."));
     }
 
@@ -51 +53 @@
       ResultCollection results = ResultsParameter.ActualValue;
       ItemArray<ParameterConfigurationTree> parameterTrees = ParameterConfigurationParameter.ActualValue;
-      int idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index; // todo: respect Min/Max
-      int idxWorst = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).Last().index;
-      
+      bool maximization = MaximizationParameter.ActualValue.Value;
+
+      int idxBest ;
+      int idxWorst;
+      if (maximization) {
+        idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).Last().index;
+        idxWorst = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
+      } else {
+        idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
+        idxWorst = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).Last().index;
+      }
+
       int problemCount = ProblemsParameter.ActualValue.Count;
 

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers/ReferenceQualityAnalyzer.cs

@@ -7 +7 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
-using System;
 
 namespace HeuristicLab.Problems.MetaOptimization {
@@ -17 +15 @@
   [StorableClass]
   public sealed class ReferenceQualityAnalyzer : SingleSuccessorOperator, IAnalyzer {
-    
+
     public ValueLookupParameter<ResultCollection> ResultsParameter {
       get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
@@ -27 +25 @@
       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
-    public LookupParameter<DoubleArray> ProblemQualityReferenceParameter {
-      get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityReferences"]; }
+    public LookupParameter<DoubleArray> ReferenceQualityAveragesParameter {
+      get { return (LookupParameter<DoubleArray>)Parameters["ReferenceQualityAverages"]; }
+    }
+    public LookupParameter<DoubleArray> ReferenceQualityDeviationsParameter {
+      get { return (LookupParameter<DoubleArray>)Parameters["ReferenceQualityDeviations"]; }
+    }
+    public LookupParameter<DoubleArray> ReferenceEvaluatedSolutionAveragesParameter {
+      get { return (LookupParameter<DoubleArray>)Parameters["ReferenceEvaluatedSolutionAverages"]; }
     }
     public LookupParameter<ConstrainedItemList<IProblem>> ProblemsParameter {
       get { return (LookupParameter<ConstrainedItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
+    }
+    public LookupParameter<BoolValue> MaximizationParameter {
+      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
     }
 
@@ -39 +46 @@
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", ""));
       Parameters.Add(new ScopeTreeLookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", ""));
-      Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityReferences", ""));
+      Parameters.Add(new LookupParameter<DoubleArray>("ReferenceQualityAverages", ""));
+      Parameters.Add(new LookupParameter<DoubleArray>("ReferenceQualityDeviations", ""));
+      Parameters.Add(new LookupParameter<DoubleArray>("ReferenceEvaluatedSolutionAverages", ""));
       Parameters.Add(new LookupParameter<ConstrainedItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName, ""));
+      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Set to false if the problem should be minimized."));
     }
 
@@ -54 +64 @@
       ItemArray<ParameterConfigurationTree> solutions = ParameterConfigurationParameter.ActualValue;
       ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
+      bool maximization = MaximizationParameter.ActualValue.Value;
 
-      if (ProblemQualityReferenceParameter.ActualValue == null) {
-        DoubleArray referenceQualities = CalculateReferenceQualities(solutions);
-        ProblemQualityReferenceParameter.ActualValue = referenceQualities;
-        NormalizePopulation(solutions, qualities, referenceQualities);
-        results.Add(new Result("QualityReferences", referenceQualities));
+      if (ReferenceQualityAveragesParameter.ActualValue == null) {
+        // this is generation zero. calculate the reference values and apply them on population. in future generations `AlgorithmRunsAnalyzer` will do the nomalization
+        DoubleArray referenceQualityAverages = CalculateReferenceQualityAverages(solutions, maximization);
+        DoubleArray referenceQualityDeviations = CalculateReferenceQualityDeviations(solutions, maximization);
+        DoubleArray referenceEvaluatedSolutionAverages = CalculateReferenceEvaluatedSolutionAverages(solutions, maximization);
+
+        ReferenceQualityAveragesParameter.ActualValue = referenceQualityAverages;
+        ReferenceQualityDeviationsParameter.ActualValue = referenceQualityDeviations;
+        ReferenceEvaluatedSolutionAveragesParameter.ActualValue = referenceEvaluatedSolutionAverages;
+
+        NormalizePopulation(solutions, qualities, referenceQualityAverages, referenceQualityDeviations, referenceEvaluatedSolutionAverages, 1, 1, 1, maximization);
+
+        results.Add(new Result("ReferenceQualities", referenceQualityAverages));
+        results.Add(new Result("ReferenceQualityDeviations", referenceQualityDeviations));
+        results.Add(new Result("ReferenceEvaluatedSolutionAverages", referenceEvaluatedSolutionAverages));
       }
 
@@ -65 +86 @@
     }
 
-    private DoubleArray CalculateReferenceQualities(ItemArray<ParameterConfigurationTree> solutions) {
-      DoubleArray referenceQualities = new DoubleArray(ProblemsParameter.ActualValue.Count);
+    private DoubleArray CalculateReferenceQualityAverages(ItemArray<ParameterConfigurationTree> solutions, bool maximization) {
+      DoubleArray references = new DoubleArray(ProblemsParameter.ActualValue.Count);
       for (int pi = 0; pi < ProblemsParameter.ActualValue.Count; pi++) {
-        referenceQualities[pi] = solutions.Where(x => x.AverageQualities != null).Select(x => x.AverageQualities[pi]).Min(); // todo: respect minimization / maximization
+        if (maximization)
+          references[pi] = solutions.Where(x => x.AverageQualities != null).Select(x => x.AverageQualities[pi]).Max();
+        else
+          references[pi] = solutions.Where(x => x.AverageQualities != null).Select(x => x.AverageQualities[pi]).Min();
       }
-      return referenceQualities;
+      return references;
     }
 
-    private void NormalizePopulation(ItemArray<ParameterConfigurationTree> solutions, ItemArray<DoubleValue> qualities, DoubleArray referenceQualities) {
+    private DoubleArray CalculateReferenceQualityDeviations(ItemArray<ParameterConfigurationTree> solutions, bool maximization) {
+      DoubleArray references = new DoubleArray(ProblemsParameter.ActualValue.Count);
+      for (int pi = 0; pi < ProblemsParameter.ActualValue.Count; pi++) {
+        if (maximization)
+          references[pi] = solutions.Where(x => x.QualityStandardDeviations != null).Select(x => x.QualityStandardDeviations[pi]).Max();
+        else
+          references[pi] = solutions.Where(x => x.QualityStandardDeviations != null).Select(x => x.QualityStandardDeviations[pi]).Min();
+      }
+      return references;
+    }
+
+    private DoubleArray CalculateReferenceEvaluatedSolutionAverages(ItemArray<ParameterConfigurationTree> solutions, bool maximization) {
+      DoubleArray references = new DoubleArray(ProblemsParameter.ActualValue.Count);
+      for (int pi = 0; pi < ProblemsParameter.ActualValue.Count; pi++) {
+        if (maximization)
+          references[pi] = solutions.Where(x => x.AverageEvaluatedSolutions != null).Select(x => x.AverageEvaluatedSolutions[pi]).Max();
+        else
+          references[pi] = solutions.Where(x => x.AverageEvaluatedSolutions != null).Select(x => x.AverageEvaluatedSolutions[pi]).Min();
+      }
+      return references;
+    }
+
+    private void NormalizePopulation(ItemArray<ParameterConfigurationTree> solutions, ItemArray<DoubleValue> qualities,
+          DoubleArray referenceQualityAverages,
+          DoubleArray referenceQualityDeviations,
+          DoubleArray referenceEvaluatedSolutionAverages,
+          double qualityAveragesWeight,
+          double qualityDeviationsWeight,
+          double evaluatedSolutionsWeight,
+          bool maximization) {
       for (int i = 0; i < solutions.Length; i++) {
-        qualities[i].Value = MetaOptimizationUtil.NormalizeQualities(solutions[i], referenceQualities.ToArray());
+        if (solutions[i].AverageQualities == null || solutions[i].QualityStandardDeviations == null || solutions[i].AverageEvaluatedSolutions == null) {
+          // this parameterConfigurationTree has not been evaluated correctly (due to a faulty configuration, which led to an exception)
+          // since we are in generation zero, there is no WorstQuality available for a penalty value
+          double penaltyValue = maximization ? double.MinValue : double.MaxValue;
+          qualities[i].Value = penaltyValue;
+        } else {
+          qualities[i].Value = MetaOptimizationUtil.Normalize(solutions[i],
+            referenceQualityAverages.ToArray(),
+            referenceQualityDeviations.ToArray(),
+            referenceEvaluatedSolutionAverages.ToArray(),
+            qualityAveragesWeight,
+            qualityDeviationsWeight,
+            evaluatedSolutionsWeight,
+            maximization);
+        }
       }
     }

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Analyzers/SolutionCacheAnalyzer.cs

@@ -7 +7 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
-using System;
 
 namespace HeuristicLab.Problems.MetaOptimization {
@@ -27 +25 @@
       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
-    public LookupParameter<DoubleArray> ProblemQualityReferenceParameter {
-      get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityReferences"]; }
-    }
     public LookupParameter<ConstrainedItemList<IProblem>> ProblemsParameter {
       get { return (LookupParameter<ConstrainedItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
@@ -45 +40 @@
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", ""));
       Parameters.Add(new ScopeTreeLookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", ""));
-      Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityReferences", ""));
       Parameters.Add(new LookupParameter<ConstrainedItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName, ""));
       Parameters.Add(new LookupParameter<IntValue>("Generations", ""));