Changeset 14577 for branches/MOCMAEvolutionStrategy

Timestamp:

01/16/17 14:25:56 (7 years ago)

Author:

bwerth

Message:

#2592 made MOCMAES compatible with MultiObjectiveBasicProblem instead of MultiObjectiveTestfunction, fixed Bug in CrowdingIndicator

Location:

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3

Files:

• CrowdingIndicator.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.MOCMAEvolutionStrategy-3.3.csproj (modified) (1 diff)
• HypervolumeIndicator.cs (modified) (2 diffs)
• IIndicator.cs (modified) (2 diffs)
• MOCMASEvolutionStrategy.cs (modified) (13 diffs)
• MinimalDistanceIndicator.cs (added)
• Plugin.cs.frame (modified) (1 diff)
• Utilities.cs (modified) (3 diffs)

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/CrowdingIndicator.cs

@@ -25 +25 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.RealVectorEncoding;
+using HeuristicLab.Optimization;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Problems.TestFunctions.MultiObjective;
 
 namespace HeuristicLab.Algorithms.MOCMAEvolutionStrategy {
@@ -33 +34 @@
   internal class CrowdingIndicator : Item, IIndicator {
 
-    public int LeastContributer<TR>(IEnumerable<TR> front, Func<TR, double[]> extractor, MultiObjectiveTestFunctionProblem problem) {
-      var bounds = problem.Bounds;
+    public int LeastContributer<TR>(IEnumerable<TR> front, Func<TR, double[]> extractor, MultiObjectiveBasicProblem<RealVectorEncoding> problem) {
+      var bounds = problem.Encoding.Bounds;
       var extracted = front.Select(extractor.Invoke).ToArray();
+      if (extracted.Length <= 2) return 0;
       var pointsums = new double[extracted.Length];
 
-      for (var dim = 0; dim < problem.Objectives; dim++) {
+      for (var dim = 0; dim < problem.Maximization.Length; dim++) {
         var arr = extracted.Select(x => x[dim]).ToArray();
         Array.Sort(arr);
-        var fmax = problem.Bounds[dim % bounds.Rows, 1];
+        var fmax = problem.Encoding.Bounds[dim % bounds.Rows, 1];
         var fmin = bounds[dim % bounds.Rows, 0];
         var pointIdx = 0;
@@ -52 +54 @@
       }
       //find min
-      return pointsums.Where(x => !double.IsInfinity(x)).ArgMin();
+      return pointsums.ArgMin();
     }
 

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/HeuristicLab.Algorithms.MOCMAEvolutionStrategy-3.3.csproj

@@ -106 +106 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="MinimalDistanceIndicator.cs" />
     <Compile Include="CrowdingIndicator.cs" />
     <Compile Include="HypervolumeIndicator.cs" />

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/HypervolumeIndicator.cs

@@ -26 +26 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.RealVectorEncoding;
+using HeuristicLab.Optimization;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.TestFunctions.MultiObjective;
@@ -33 +35 @@
   internal class HypervolumeIndicator : Item, IIndicator {
 
-    public int LeastContributer<TR>(IEnumerable<TR> front, Func<TR, double[]> extractor, MultiObjectiveTestFunctionProblem problem) {
+    public int LeastContributer<TR>(IEnumerable<TR> front, Func<TR, double[]> extractor, MultiObjectiveBasicProblem<RealVectorEncoding> problem) {
       var frontArr = front.Select(extractor.Invoke).ToList();
-      var refPoint = BuildReference(frontArr.Concat(new[] { problem.TestFunction.ReferencePoint(problem.Objectives) }), problem.Maximization);
+      if (frontArr.Count <= 1) return 0;
+      var p = problem as MultiObjectiveTestFunctionProblem;
+      var refPoint = BuildReference(p != null ? frontArr.Concat(new[] { p.TestFunction.ReferencePoint(p.Objectives) }) : frontArr, problem.Maximization);
       var hv = Hypervolume.Calculate(frontArr, refPoint, problem.Maximization);
-      return Enumerable.Range(0, frontArr.Count).Select(i => Contribution(frontArr, i, problem.Maximization, refPoint, hv)).ArgMin();
+      var contributions = Enumerable.Range(0, frontArr.Count).Select(i => Contribution(frontArr, i, problem.Maximization, refPoint, hv));
+      return contributions.ArgMin();
     }
 

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/IIndicator.cs

@@ -22 +22 @@
 using System.Collections.Generic;
 using HeuristicLab.Core;
-using HeuristicLab.Problems.TestFunctions.MultiObjective;
+using HeuristicLab.Encodings.RealVectorEncoding;
+using HeuristicLab.Optimization;
 
 namespace HeuristicLab.Algorithms.MOCMAEvolutionStrategy {
@@ -35 +36 @@
     /// <param name="problem">The problem on which the front is evaluated (!! The function itself will NOT be evluated only bounds referencePoints & other metadate will be used</param>
     /// <returns>the index of the least contributing point according to any type of quality criteria</returns>
-    int LeastContributer<TR>(IEnumerable<TR> front, Func<TR, double[]> extractor, MultiObjectiveTestFunctionProblem problem);
+    int LeastContributer<TR>(IEnumerable<TR> front, Func<TR, double[]> extractor, MultiObjectiveBasicProblem<RealVectorEncoding> problem);
   }
 }

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/MOCMASEvolutionStrategy.cs

@@ -44 +44 @@
     public override Type ProblemType
     {
-      get { return typeof(MultiObjectiveTestFunctionProblem); }
-    }
-    public new MultiObjectiveTestFunctionProblem Problem
-    {
-      get { return (MultiObjectiveTestFunctionProblem)base.Problem; }
+      get { return typeof(MultiObjectiveBasicProblem<RealVectorEncoding>); }
+    }
+    public new MultiObjectiveBasicProblem<RealVectorEncoding> Problem
+    {
+      get { return (MultiObjectiveBasicProblem<RealVectorEncoding>)base.Problem; }
       set { base.Problem = value; }
     }
+    public override bool SupportsPause
+    {
+      get { return false; }
+    }
+
     #region internal variables
     private readonly IRandom random = new MersenneTwister();
@@ -76 +81 @@
     private const string CrowdingResultName = "Crowding";
     private const string SpacingResultName = "Spacing";
-    private const string SolutionsResultName = "Pareto Front";
+    private const string CurrentFrontResultName = "Pareto Front";
     private const string BestHypervolumeResultName = "Best Hypervolume";
     private const string BestKnownHypervolumeResultName = "Best known hypervolume";
@@ -97 +102 @@
       get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyName]; }
     }
-    private IFixedValueParameter<IntValue> PopulationSizeParameter
+    public IFixedValueParameter<IntValue> PopulationSizeParameter
     {
       get { return (IFixedValueParameter<IntValue>)Parameters[PopulationSizeName]; }
     }
-    private IFixedValueParameter<IntValue> MaximumGenerationsParameter
+    public IFixedValueParameter<IntValue> MaximumGenerationsParameter
     {
       get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsName]; }
     }
-    private IFixedValueParameter<IntValue> MaximumEvaluatedSolutionsParameter
+    public IFixedValueParameter<IntValue> MaximumEvaluatedSolutionsParameter
     {
       get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluatedSolutionsName]; }
     }
-    private IFixedValueParameter<DoubleValue> InitialSigmaParameter
+    public IFixedValueParameter<DoubleValue> InitialSigmaParameter
     {
       get { return (IFixedValueParameter<DoubleValue>)Parameters[InitialSigmaName]; }
     }
-    private IConstrainedValueParameter<IIndicator> IndicatorParameter
+    public IConstrainedValueParameter<IIndicator> IndicatorParameter
     {
       get { return (IConstrainedValueParameter<IIndicator>)Parameters[IndicatorName]; }
@@ -254 +259 @@
     private DoubleMatrix ResultsSolutions
     {
-      get { return ((DoubleMatrix)Results[SolutionsResultName].Value); }
-      set { Results[SolutionsResultName].Value = value; }
+      get { return ((DoubleMatrix)Results[CurrentFrontResultName].Value); }
+      set { Results[CurrentFrontResultName].Value = value; }
     }
     private ScatterPlotContent ResultsScatterPlot
@@ -273 +278 @@
       Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsName, "The maximum number of generations which should be processed.", new IntValue(1000)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluatedSolutionsName, "The maximum number of evaluated solutions that should be computed.", new IntValue(int.MaxValue)));
-      var set = new ItemSet<IIndicator> { new HypervolumeIndicator(), new CrowdingIndicator() };
+      var set = new ItemSet<IIndicator> { new HypervolumeIndicator(), new CrowdingIndicator(), new MinimalDistanceIndicator() };
       Parameters.Add(new ConstrainedValueParameter<IIndicator>(IndicatorName, "The selection mechanism on non-dominated solutions", set, set.First()));
     }
@@ -331 +336 @@
       solutions = new MOCMAESIndividual[PopulationSize];
       for (var i = 0; i < PopulationSize; i++) {
-        var x = new RealVector(Problem.ProblemSize); // Uniform distibution in all dimensions assumed.
-                                                     // There is the UniformSolutionCreater associated with the Encoding, but it was considered not usable here
-        var bounds = Problem.Bounds;
-        for (var j = 0; j < Problem.ProblemSize; j++) {
+        var x = new RealVector(Problem.Encoding.Length); // Uniform distibution in all dimensions assumed.
+                                                         // There is the UniformSolutionCreater associated with the Encoding, but it was considered not usable here
+        var bounds = Problem.Encoding.Bounds;
+        for (var j = 0; j < Problem.Encoding.Length; j++) {
           var dim = j % bounds.Rows;
           x[j] = random.NextDouble() * (bounds[dim, 1] - bounds[dim, 0]) + bounds[dim, 0];
@@ -344 +349 @@
     private void InitStrategy() {
       const int lambda = 1;
-      double n = Problem.ProblemSize;
+      double n = Problem.Encoding.Length;
 
       var targetSuccessProbability = 1.0 / (5.0 + Math.Sqrt(lambda) / 2.0);
@@ -377 +382 @@
       table.Rows.Add(new DataRow(SpacingResultName));
       AddResult(TimetableResultName, "Different quality meassures in a timeseries", table);
-      AddResult(SolutionsResultName, "The current front", new DoubleMatrix());
+      AddResult(CurrentFrontResultName, "The current front", new DoubleMatrix());
       AddResult(ScatterPlotResultName, "A scatterplot displaying the evaluated solutions and (if available) the analytically optimal front", new ScatterPlotContent(null, null, null, 2));
 
-      if (Problem.BestKnownFront != null) {
-        ResultsBestKnownHypervolume = Hypervolume.Calculate(Utilities.ToArray(Problem.BestKnownFront), Problem.TestFunction.ReferencePoint(Problem.Objectives), Problem.Maximization);
+      var problem = Problem as MultiObjectiveTestFunctionProblem;
+      if (problem == null) return;
+      if (problem.BestKnownFront != null) {
+        ResultsBestKnownHypervolume = Hypervolume.Calculate(Utilities.ToArray(problem.BestKnownFront), problem.TestFunction.ReferencePoint(problem.Objectives), Problem.Maximization);
         ResultsDifferenceBestKnownHypervolume = ResultsBestKnownHypervolume;
       }
-      ResultsScatterPlot = new ScatterPlotContent(null, null, Utilities.ToArray(Problem.BestKnownFront), Problem.Objectives);
+      ResultsScatterPlot = new ScatterPlotContent(new double[0][], new double[0][], Utilities.ToArray(problem.BestKnownFront), problem.Objectives);
     }
     #endregion
@@ -411 +418 @@
     }
     private double[] Evaluate(RealVector x) {
-      var res = Problem.Evaluate(x);
+      var s = new Scope();
+      s.Variables.Add(new Variable(Problem.Encoding.Name, x));
+      var ind = new SingleEncodingIndividual(Problem.Encoding, s);
+      var res = Problem.Evaluate(ind, random);
       ResultsEvaluations++;
       return res;
     }
-    private static double[] Penalize(RealVector x, RealVector t, IEnumerable<double> fitness) {
-      var penalty = x.Select((t1, i) => t1 - t[i]).Sum(d => d * d);
-      return fitness.Select(v => v + penalty).ToArray();
+    private double[] Penalize(RealVector x, RealVector t, IEnumerable<double> fitness) {
+      var penalty = x.Zip(t, (a, b) => (a - b) * (a - b)).Sum() * 1E-6;
+      return fitness.Select((v, i) => Problem.Maximization[i] ? v - penalty : v + penalty).ToArray();
     }
     private RealVector ClosestFeasible(RealVector x) {
-      var bounds = Problem.Bounds;
+      var bounds = Problem.Encoding.Bounds;
       var r = new RealVector(x.Length);
       for (var i = 0; i < x.Length; i++) {
@@ -429 +439 @@
     }
     private bool IsFeasable(RealVector offspring) {
-      var bounds = Problem.Bounds;
+      var bounds = Problem.Encoding.Bounds;
       for (var i = 0; i < offspring.Length; i++) {
         var dim = i % bounds.Rows;
@@ -452 +462 @@
       }
 
+
       //now use the indicator to deselect the approximatingly worst elements of the last selected front
       var front1 = fronts[rank];
+      front1.Sort(new HelpComparer());
       for (; popSize > length; popSize--) {
         var lc = Indicator.LeastContributer(front1.ToArray(), x => x.PenalizedFitness, Problem);
@@ -486 +498 @@
     }
     private void AnalyzeQualityIndicators() {
-      var front = NonDominatedSelect.GetDominatingVectors(solutions.Select(x => x.Fitness), Problem.TestFunction.ReferencePoint(Problem.Objectives), Problem.Maximization, true).ToArray();
-      var bounds = Problem.Bounds.CloneAsMatrix();
+      var problem = Problem as MultiObjectiveTestFunctionProblem;
+      if (problem == null) return;
+
+      var front = NonDominatedSelect.GetDominatingVectors(solutions.Select(x => x.Fitness), problem.TestFunction.ReferencePoint(problem.Objectives), Problem.Maximization, true).ToArray();
+      if (front.Length == 0) return;
+      var bounds = problem.Bounds.CloneAsMatrix();
       ResultsCrowding = Crowding.Calculate(front, bounds);
       ResultsSpacing = Spacing.Calculate(front);
-      ResultsGenerationalDistance = Problem.BestKnownFront != null ? GenerationalDistance.Calculate(front, Utilities.ToArray(Problem.BestKnownFront), 1) : double.NaN;
-
-      ResultsInvertedGenerationalDistance = Problem.BestKnownFront != null ? InvertedGenerationalDistance.Calculate(front, Utilities.ToArray(Problem.BestKnownFront), 1) : double.NaN;
-
-      ResultsHypervolume = Hypervolume.Calculate(front, Problem.TestFunction.ReferencePoint(Problem.Objectives), Problem.Maximization);
+      ResultsGenerationalDistance = problem.BestKnownFront != null ? GenerationalDistance.Calculate(front, Utilities.ToArray(problem.BestKnownFront), 1) : double.NaN;
+
+      ResultsInvertedGenerationalDistance = problem.BestKnownFront != null ? InvertedGenerationalDistance.Calculate(front, Utilities.ToArray(problem.BestKnownFront), 1) : double.NaN;
+
+      ResultsHypervolume = Hypervolume.Calculate(front, problem.TestFunction.ReferencePoint(problem.Objectives), Problem.Maximization);
       ResultsBestHypervolume = Math.Max(ResultsHypervolume, ResultsBestHypervolume);
       ResultsDifferenceBestKnownHypervolume = ResultsBestKnownHypervolume - ResultsBestHypervolume;
@@ -510 +526 @@
     #endregion
 
-
+    private class HelpComparer : IComparer<MOCMAESIndividual> {
+      public int Compare(MOCMAESIndividual x, MOCMAESIndividual y) {
+        return x.PenalizedFitness[0].CompareTo(y.PenalizedFitness[0]);
+      }
+    }
 
     #region Helpers

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/Plugin.cs.frame

@@ -33 +33 @@
   [PluginDependency("HeuristicLab.Common", "3.3")]
   [PluginDependency("HeuristicLab.Core", "3.3")]
-  [PluginDependency("HeuristicLab.Core.Views", "3.3")]
   [PluginDependency("HeuristicLab.Data", "3.3")]
   [PluginDependency("HeuristicLab.Encodings.RealVectorEncoding", "3.3")]
-  [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]
-  [PluginDependency("HeuristicLab.Optimization.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Parameters", "3.3")]
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
-  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
   [PluginDependency("HeuristicLab.Problems.TestFunctions.MultiObjective", "3.3")]
   [PluginDependency("HeuristicLab.Random", "3.3")]

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/Utilities.cs

@@ -5 +5 @@
   internal static class Utilities {
     internal static double[][] ToArray(DoubleMatrix m) {
+      if (m == null) return null;
       var i = m.Rows - 1;
       var a = new double[i][];
@@ -16 +17 @@
 
     public static int ArgMin<T>(IEnumerable<T> values, IComparer<T> comparer) {
-      var mindex = 0;
+      var mindex = -1;
       var min = default(T);
       var i = 0;
@@ -30 +31 @@
     }
     public static int ArgMax<T>(IEnumerable<T> values, IComparer<T> comparer) {
-      var mindex = 0;
+      var mindex = -1;
       var min = default(T);
       var i = 0;