Changeset 5212 for branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization

Timestamp:

01/05/11 02:03:20 (14 years ago)

Author:

cneumuel

Message:

#1215

• added normalization for quality values of individuals

Location:

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

Files:

• Analyzers/BestParameterConfigurationAnalyzer.cs (modified) (5 diffs)
• Encoding/ParameterConfigurationTree.cs (modified) (7 diffs)
• Evaluators/ParameterConfigurationEvaluator.cs (modified) (7 diffs)
• MetaOptimizationProblem.cs (modified) (1 diff)

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

@@ -40 +40 @@
     }
 
+    // stores the medians of the qualities of each problem
+    public LookupParameter<DoubleArray> ProblemQualityMediansParameter {
+      get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityMedians"]; }
+    }
+    public LookupParameter<ConstrainedItemList<ISingleObjectiveProblem>> ProblemsParameter {
+      get { return (LookupParameter<ConstrainedItemList<ISingleObjectiveProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
+    }
+
     public BestParameterConfigurationAnalyzer()
       : base() {
@@ -49 +57 @@
       Parameters.Add(new LookupParameter<IRun>("BestKnownSolution", "TODO The best known solution of this TSP instance."));
       Parameters.Add(new LookupParameter<RunCollection>("Population", "TODO The best known solution of this TSP instance."));
+      Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityMedians", ""));
+      Parameters.Add(new LookupParameter<ConstrainedItemList<ISingleObjectiveProblem>>(MetaOptimizationProblem.ProblemsParameterName));
     }
 
@@ -65 +75 @@
 
       int idxBest = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
-
 
       ParameterConfigurationTree best = (ParameterConfigurationTree)parameterTrees[idxBest];
@@ -87 +96 @@
 
       // population
-
       int i = 0;
       RunCollection rc = new RunCollection();
-      foreach (ParameterConfigurationTree pt in parameterTrees.OrderByDescending(x => x.BestQuality.Value)) { // todo: respect Maximization:true/false
+      foreach (ParameterConfigurationTree pt in parameterTrees.OrderBy(x => x.AverageQualityNormalized)) { // todo: respect Maximization:true/false
         IRun run = new Run();
         run.Name = string.Format("Individuum ({0})", i);
@@ -106 +114 @@
       }
 
+      // medians for the problems
+      DoubleArray medians = new DoubleArray(ProblemsParameter.ActualValue.Count);
+      for (int pi = 0; pi < ProblemsParameter.ActualValue.Count; pi++) {
+        double[] values = new double[rc.Count];
+        for (int ri = 0; ri < rc.Count; ri++) {
+          values[ri] = ((DoubleArray)rc.ElementAt(ri).Results["RunsAverageQualities"])[pi];
+        }
+        medians[pi] = values.Median();
+      }
+      ProblemQualityMediansParameter.ActualValue = medians;
+
+      if (results.ContainsKey("ProblemsAverageQualityMedians")) {
+        results["ProblemsAverageQualityMedians"].Value = medians;
+      } else {
+        results.Add(new Result("ProblemsAverageQualityMedians", medians));
+      }
+
       return base.Apply();
     }

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Encoding/ParameterConfigurationTree.cs

@@ -14 +14 @@
   [StorableClass]
   public class ParameterConfigurationTree : ValueConfiguration, IEnumerable {
-    [Storable]
-    private DoubleValue bestQuality;
-    public DoubleValue BestQuality {
-      get { return bestQuality; }
+
+    [Storable]
+    private DoubleValue averageQualityNormalized;
+    public DoubleValue AverageQualityNormalized {
+      get { return averageQualityNormalized; }
       set {
-        if (bestQuality != value) {
-          if (bestQuality != null) DeregisterQualityEvents();
-          bestQuality = value;
-          if (bestQuality != null) RegisterQualityEvents();
+        if (averageQualityNormalized != value) {
+          averageQualityNormalized = value;
           OnQualityChanged();
         }
@@ -29 +28 @@
 
     [Storable]
-    private DoubleValue averageQuality;
-    public DoubleValue AverageQuality {
-      get { return averageQuality; }
-      set { averageQuality = value; }
-    }
-
-    [Storable]
-    private DoubleValue worstQuality;
-    public DoubleValue WorstQuality {
-      get { return worstQuality; }
-      set { worstQuality = value; }
-    }
-
-    [Storable]
-    private DoubleValue qualityVariance;
-    public DoubleValue QualityVariance {
-      get { return qualityVariance; }
-      set { qualityVariance = value; }
-    }
-
-    [Storable]
-    private DoubleValue qualityStandardDeviation;
-    public DoubleValue QualityStandardDeviation {
-      get { return qualityStandardDeviation; }
-      set { qualityStandardDeviation = value; }
-    }
-
-    [Storable]
-    private TimeSpanValue averageExecutionTime;
-    public TimeSpanValue AverageExecutionTime {
-      get { return averageExecutionTime; }
-      set { averageExecutionTime = value; }
+    private DoubleArray qualitiesNormalized;
+    public DoubleArray QualitiesNormalized {
+      get { return qualitiesNormalized; }
+      set {
+        if (qualitiesNormalized != value) {
+          qualitiesNormalized = value;
+        }
+      }
+    }
+
+    [Storable]
+    private DoubleArray bestQualities;
+    public DoubleArray BestQualities {
+      get { return bestQualities; }
+      set {
+        if (bestQualities != value) {
+          bestQualities = value;
+        }
+      }
+    }
+
+    [Storable]
+    private DoubleArray averageQualities;
+    public DoubleArray AverageQualities {
+      get { return averageQualities; }
+      set { averageQualities = value; }
+    }
+
+    [Storable]
+    private DoubleArray worstQualities;
+    public DoubleArray WorstQualities {
+      get { return worstQualities; }
+      set { worstQualities = value; }
+    }
+
+    [Storable]
+    private DoubleArray qualityVariances;
+    public DoubleArray QualityVariances {
+      get { return qualityVariances; }
+      set { qualityVariances = value; }
+    }
+
+    [Storable]
+    private DoubleArray qualityStandardDeviations;
+    public DoubleArray QualityStandardDeviations {
+      get { return qualityStandardDeviations; }
+      set { qualityStandardDeviations = value; }
+    }
+
+    [Storable]
+    private ItemList<TimeSpanValue> averageExecutionTimes;
+    public ItemList<TimeSpanValue> AverageExecutionTimes {
+      get { return averageExecutionTimes; }
+      set { averageExecutionTimes = value; }
     }
 
@@ -88 +109 @@
       : base(null, algorithm.GetType()) {
       this.Optimize = true; // root must always be optimized
-      this.BestQuality = new DoubleValue();
       this.parameters = new Dictionary<string, IItem>();
 
       PopulateParameterConfigurations(algorithm);
-      Initialize();
     }
     public ParameterConfigurationTree() {
-      Initialize();
     }
     [StorableConstructor]
@@ -101 +119 @@
     protected ParameterConfigurationTree(ParameterConfigurationTree original, Cloner cloner)
       : base(original, cloner) {
-      this.bestQuality = cloner.Clone(original.BestQuality);
-      this.averageQuality = cloner.Clone(original.averageQuality);
-      this.worstQuality = cloner.Clone(original.worstQuality);
-      this.qualityStandardDeviation = cloner.Clone(original.qualityStandardDeviation);
-      this.qualityVariance = cloner.Clone(original.qualityVariance);
-      this.averageExecutionTime = cloner.Clone(original.averageExecutionTime);
+      this.bestQualities = cloner.Clone(original.BestQualities);
+      this.averageQualities = cloner.Clone(original.averageQualities);
+      this.worstQualities = cloner.Clone(original.worstQualities);
+      this.qualityStandardDeviations = cloner.Clone(original.qualityStandardDeviations);
+      this.qualityVariances = cloner.Clone(original.qualityVariances);
+      this.averageExecutionTimes = cloner.Clone(original.averageExecutionTimes);
       this.repetitions = cloner.Clone(original.repetitions);
       this.runs = cloner.Clone(original.runs);
@@ -113 +131 @@
         this.parameters.Add(p.Key, cloner.Clone(p.Value));
       }
-      Initialize();
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -120 +137 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      Initialize();
     }
     #endregion
 
-    private void Initialize() {
-      //if (algorithm != null) RegisterAlgorithmEvents();
-      if (bestQuality != null) RegisterQualityEvents();
-    }
-
     public virtual void CollectResultValues(IDictionary<string, IItem> values) {
-      values.Add("RunsAverageExecutionTime", AverageExecutionTime);
+      values.Add("RunsAverageExecutionTimes", AverageExecutionTimes);
       values.Add("Repetitions", Repetitions);
-      values.Add("RunsBestQuality", BestQuality);
-      values.Add("RunsAverageQuality", AverageQuality);
-      values.Add("RunsWorstQuality", WorstQuality);
-      values.Add("RunsQualityVariance", QualityVariance);
-      values.Add("RunsQualityStandardDeviation", QualityStandardDeviation);
+      values.Add("RunsBestQualities", BestQualities);
+      values.Add("RunsAverageQualities", AverageQualities);
+      values.Add("RunsWorstQualities", WorstQualities);
+      values.Add("RunsQualityVariances", QualityVariances);
+      values.Add("RunsQualityStandardDeviations", QualityStandardDeviations);
+      values.Add("QualitiesNormalized", QualitiesNormalized);
+      values.Add("AverageQualityNormalized", AverageQualityNormalized);
       values.Add("Runs", Runs);
     }
@@ -147 +160 @@
 
     #region Events
-    //public event EventHandler AlgorithmChanged;
-    //private void OnAlgorithmChanged() {
-    //  var handler = AlgorithmChanged;
-    //  if (handler != null) handler(this, EventArgs.Empty);
-    //}
     public event EventHandler QualityChanged;
     private void OnQualityChanged() {
       var handler = QualityChanged;
       if (handler != null) handler(this, EventArgs.Empty);
-    }
-
-    //private void RegisterAlgorithmEvents() {
-
-    //}
-    //private void DeregisterAlgorithmEvents() {
-
-    //}
-    private void RegisterQualityEvents() {
-      BestQuality.ValueChanged += new EventHandler(Quality_ValueChanged);
-    }
-    private void DeregisterQualityEvents() {
-      BestQuality.ValueChanged -= new EventHandler(Quality_ValueChanged);
     }
 

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Evaluators/ParameterConfigurationEvaluator.cs

@@ -40 +40 @@
     }
 
+    public LookupParameter<DoubleArray> ProblemQualityMediansParameter {
+      get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityMedians"]; }
+    }
+
     public IntValue Repetitions {
       get { return RepetitionsParameter.ActualValue; }
@@ -51 +55 @@
       Parameters.Add(new LookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", "Missing description."));
       Parameters.Add(new LookupParameter<IntValue>(MetaOptimizationProblem.RepetitionsParameterName, "Number of evaluations on one problem."));
+      Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityMedians", ""));
     }
 
@@ -66 +71 @@
       IItemList<ISingleObjectiveProblem> problems = ProblemsParameter.ActualValue;
 
+      double[] medians;
+      if (ProblemQualityMediansParameter.ActualValue == null) {
+        // this is generation zero. no reference qualities for scaling have been calculated yet. calculate a random individuum to get reference values
+        medians = new double[problems.Count]; // todo
+        for (int i = 0; i < medians.Length; i++) {
+          medians[i] = 10;
+        }
+      } else {
+        medians = ProblemQualityMediansParameter.ActualValue.ToArray();
+      }
+
       // set parameters
       ParameterConfigurationParameter.ActualValue.Parameterize(algorithm);
       algorithm.StoreAlgorithmInEachRun = false;
 
-      List<double> qualities = new List<double>();
-      List<TimeSpan> executionTimes = new List<TimeSpan>();
+      List<List<double>> qualities = new List<List<double>>();
+      List<List<TimeSpan>> executionTimes = new List<List<TimeSpan>>();
       algorithm.Engine = new SequentialEngine.SequentialEngine();
       algorithm.Prepare(true);
@@ -77 +93 @@
       foreach (ISingleObjectiveProblem problem in problems) {
         algorithm.Problem = (IProblem)problem.Clone();
+        var problemQualities = new List<double>();
+        var problemExecutionTimes = new List<TimeSpan>();
 
         for (int i = 0; i < Repetitions.Value; i++) {
@@ -86 +104 @@
           if (algorithm.ExecutionState == ExecutionState.Paused) {
             // this parametercombination was bad. set penalty for this solution
-            qualities.Add(PenaltyQuality); // todo: respect Maximization; problem: this messes up average value; solution: use currently worst quality*2
-            executionTimes.Add(algorithm.ExecutionTime);
+            problemQualities.Add(PenaltyQuality); // todo: respect Maximization; problem: this messes up average value; solution: use currently worst quality*2
+            problemExecutionTimes.Add(algorithm.ExecutionTime);
           } else {
-            qualities.Add(((DoubleValue)algorithm.Results["BestQuality"].Value).Value);
-            executionTimes.Add(algorithm.ExecutionTime);
+            problemQualities.Add(((DoubleValue)algorithm.Results["BestQuality"].Value).Value);
+            problemExecutionTimes.Add(algorithm.ExecutionTime);
 
             // parameters will be stored in ParameterConfigurationTree anyway. they would be redundant in runs
@@ -98 +116 @@
           }
         }
+        qualities.Add(problemQualities);
+        executionTimes.Add(problemExecutionTimes);
       }
       algorithm.Prepare();
 
-      qualities = qualities.OrderBy(x => x).ToList();  // todo: respect Maximization:true/false
-
-      ParameterConfigurationParameter.ActualValue.AverageExecutionTime = new TimeSpanValue(TimeSpan.FromMilliseconds(executionTimes.Average(t => t.TotalMilliseconds)));
+      ParameterConfigurationParameter.ActualValue.AverageExecutionTimes = new ItemList<TimeSpanValue>(executionTimes.Select(t => new TimeSpanValue(TimeSpan.FromMilliseconds(t.Average(ts => ts.TotalMilliseconds)))));
       ParameterConfigurationParameter.ActualValue.Repetitions = (IntValue)Repetitions.Clone();
-      ParameterConfigurationParameter.ActualValue.BestQuality = new DoubleValue(qualities.First());
-      ParameterConfigurationParameter.ActualValue.AverageQuality = new DoubleValue(qualities.Average());
-      ParameterConfigurationParameter.ActualValue.WorstQuality = new DoubleValue(qualities.Last());
-      ParameterConfigurationParameter.ActualValue.QualityVariance = new DoubleValue(qualities.Variance());
-      ParameterConfigurationParameter.ActualValue.QualityStandardDeviation = new DoubleValue(qualities.StandardDeviation());
+      ParameterConfigurationParameter.ActualValue.BestQualities = new DoubleArray(qualities.Select(q => q.Min()).ToArray()); // todo: respect Maximization:true/false
+      ParameterConfigurationParameter.ActualValue.AverageQualities = new DoubleArray(qualities.Select(q => q.Average()).ToArray());
+      ParameterConfigurationParameter.ActualValue.WorstQualities = new DoubleArray(qualities.Select(q => q.Max()).ToArray()); // todo: respect Maximization:true/false
+      ParameterConfigurationParameter.ActualValue.QualityVariances = new DoubleArray(qualities.Select(q => q.Variance()).ToArray());
+      ParameterConfigurationParameter.ActualValue.QualityStandardDeviations = new DoubleArray(qualities.Select(q => q.StandardDeviation()).ToArray());
       ParameterConfigurationParameter.ActualValue.Runs = (RunCollection)algorithm.Runs.Clone();
 
-      double quality = ParameterConfigurationParameter.ActualValue.AverageQuality.Value; // todo: also include other measures (executiontime, variance)
-      this.QualityParameter.ActualValue = new DoubleValue(quality);
+      // normalize qualities
+      double[] qualitiesNormalized = new double[problems.Count];
+      for (int i = 0; i < problems.Count; i++) {
+        qualitiesNormalized[i] = qualities[i].Average() / medians[i];
+      }
+      ParameterConfigurationParameter.ActualValue.QualitiesNormalized = new DoubleArray(qualitiesNormalized);
+      ParameterConfigurationParameter.ActualValue.AverageQualityNormalized = new DoubleValue(qualitiesNormalized.Average());
+
+      this.QualityParameter.ActualValue = ParameterConfigurationParameter.ActualValue.AverageQualityNormalized;
 
       return base.Apply();
@@ -129 +154 @@
   }
 
+  /// <summary>
+  /// Can execute an algorithm synchronously
+  /// </summary>
   public class AlgorithmExecutor {
     private EngineAlgorithm algorithm;

branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/MetaOptimizationProblem.cs

@@ -109 +109 @@
       var validIntManipulators = new ItemSet<IIntValueManipulator>( ApplicationManager.Manager.GetInstances<IIntValueManipulator>());
       var validDoubleManipulators = new ItemSet<IDoubleValueManipulator>(ApplicationManager.Manager.GetInstances<IDoubleValueManipulator>());
-      Parameters.Add(new ConstrainedValueParameter<IIntValueManipulator>(IntValueManipulatorParameterName, "", validIntManipulators, new UniformIntValueManipulator()));
-      Parameters.Add(new ConstrainedValueParameter<IDoubleValueManipulator>(DoubleValueManipulatorParameterName, "", validDoubleManipulators, new NormalDoubleValueManipulator()));
+      Parameters.Add(new ConstrainedValueParameter<IIntValueManipulator>(IntValueManipulatorParameterName, "", validIntManipulators, validIntManipulators.First()));
+      Parameters.Add(new ConstrainedValueParameter<IDoubleValueManipulator>(DoubleValueManipulatorParameterName, "", validDoubleManipulators, validDoubleManipulators.First()));
 
       Maximization = new BoolValue(false);