Changeset 15343 for branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/DiscreteEGO/DiscreteInfillSolver.cs

Timestamp:

08/29/17 11:28:16 (7 years ago)

Author:

bwerth

Message:

#2745 added discretized EGO-version for use with IntegerVectors

Location:

branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/DiscreteEGO

Files:

• . (added)
• DiscreteInfillSolver.cs (copied) (copied from branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/Operators/InfillSolver.cs) (6 diffs)

branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/DiscreteEGO/DiscreteInfillSolver.cs

@@ -22 +22 @@
 using System;
 using System.Threading;
+using System.Linq;
+using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Encodings.RealVectorEncoding;
+using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
@@ -32 +34 @@
 
 namespace HeuristicLab.Algorithms.EGO {
-  /// <summary>
-  /// A base class for operators that manipulate real-valued vectors.
-  /// </summary>
-  [Item("InfillSolver", "A RealVectorCreator that creates candidates by optimizing an infill-subproblem")]
+  [Item("DiscreteInfillSolver", "An IntegerVectorCreator that creates candidates by optimizing an infill-subproblem")]
   [StorableClass]
-  public class InfillSolver : RealVectorCreator, ICancellableOperator {
+  public class DiscreteInfillSolver : IntegerVectorCreator, ICancellableOperator {
 
     public ILookupParameter<IAlgorithm> InfillOptimizationAlgorithmParamter => (ILookupParameter<IAlgorithm>)Parameters["InfillAlgorithm"];
@@ -44 +43 @@
     public ILookupParameter<BoolValue> RemoveDuplicatesParameter => (ILookupParameter<BoolValue>)Parameters["RemoveDuplicates"];
     public IFixedValueParameter<DoubleValue> DuplicateCutoffParameter => (IFixedValueParameter<DoubleValue>)Parameters["Duplicates Cutoff"];
-    public ILookupParameter<DoubleMatrix> InfillBoundsParameter => (ILookupParameter<DoubleMatrix>)Parameters["InfillBounds"];
+    public ILookupParameter<IntMatrix> InfillBoundsParameter => (ILookupParameter<IntMatrix>)Parameters["InfillBounds"];
 
     public CancellationToken Cancellation { get; set; }
 
     [StorableConstructor]
-    protected InfillSolver(bool deserializing) : base(deserializing) { }
-    protected InfillSolver(InfillSolver original, Cloner cloner) : base(original, cloner) { }
-    public InfillSolver() {
+    protected DiscreteInfillSolver(bool deserializing) : base(deserializing) { }
+    protected DiscreteInfillSolver(DiscreteInfillSolver original, Cloner cloner) : base(original, cloner) { }
+    public DiscreteInfillSolver() {
       Parameters.Add(new LookupParameter<IAlgorithm>("InfillAlgorithm", "The algorithm used to optimize the infill problem") { Hidden = true });
       Parameters.Add(new LookupParameter<IRegressionSolution>("Model", "The RegressionSolution upon which the InfillProblem operates") { Hidden = true });
@@ -57 +56 @@
       Parameters.Add(new LookupParameter<BoolValue>("RemoveDuplicates", "Whether duplicates shall be removed") { Hidden = true });
       Parameters.Add(new FixedValueParameter<DoubleValue>("Duplicates Cutoff", "The cut off radius for", new DoubleValue(0.01)) { Hidden = false });
-      Parameters.Add(new LookupParameter<DoubleMatrix>("InfillBounds", "The bounds applied for infill solving") { Hidden = true });
+      Parameters.Add(new LookupParameter<IntMatrix>("InfillBounds", "The bounds applied for infill solving") { Hidden = true });
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new InfillSolver(this, cloner);
+      return new DiscreteInfillSolver(this, cloner);
     }
 
-    protected override RealVector Create(IRandom random, IntValue length, DoubleMatrix bounds) {
+    protected override IntegerVector Create(IRandom random, IntValue length, IntMatrix bounds) {
       var infillBounds = InfillBoundsParameter.ActualValue;
       if (infillBounds != null && infillBounds.Rows > 0) {
@@ -75 +74 @@
       var res = OptimizeInfillProblem(alg, model, max, bounds, length.Value, random);
       var rad = DuplicateCutoffParameter.Value.Value;
-      if (!RemoveDuplicatesParameter.ActualValue.Value || !(GetMinDifference(model.ProblemData.Dataset, res) < rad * rad)) return res;
-      for (var i = 0; i < res.Length; i++) res[i] += random.NextDouble() * rad * 2;
+      if (!RemoveDuplicatesParameter.ActualValue.Value || GetMinDifference(model.ProblemData.Dataset, res) >= rad * rad) return res;
+
+      bool changed = false;
+      var steps = 0;
+      var dims = new List<int>();
+
+      //TODO this may take a long time to compute if many samples have already been evaluated in the surrounding area
+      //as the preferred region can not be sampled denser and denser due to the disceretization, the variance between two sampled points may be impossible to decease
+
+      //TODO speed up GetMinDifferecnce via tree-structure
+      while (!changed || GetMinDifference(model.ProblemData.Dataset, res) < rad * rad) {
+        if (dims.Count == 0) {
+          if (!changed && steps > 0) throw new ArgumentException("Can not avoid duplicate");
+          dims = Enumerable.Range(0, res.Length).ToList();
+          steps++;
+          changed = false;
+        }
+        var i = random.Next(dims.Count);
+        var dim = dims[i];
+        dims.RemoveAt(i);
+        var step = bounds[dim % bounds.Rows, 2] * steps;
+        var low = checkIntBounds(bounds, dim, res[dim] - step);
+        var high = checkIntBounds(bounds, dim, res[dim] + step);
+        if (!low && !high) continue;
+        else if (low && high) res[dim] += (random.NextDouble() < 0.5 ? -step : step);
+        else if (low) res[dim] -= step;
+        else res[dim] += step;
+        changed = true;
+      }
       return res;
     }
 
-    private RealVector OptimizeInfillProblem(IAlgorithm algorithm, IRegressionSolution model, bool maximization, DoubleMatrix bounds, int length, IRandom random) {
-      var infillProblem = algorithm.Problem as InfillProblem;
+
+    private bool checkIntBounds(IntMatrix b, int row, int value) {
+      var bi = row % b.Rows;
+      var l = b[bi, 0];
+      var h = b[bi, 1];
+      var s = b[bi, 2];
+      return l <= value && h >= value && (value - l) % s == 0;
+    }
+
+    private IntegerVector OptimizeInfillProblem(IAlgorithm algorithm, IRegressionSolution model, bool maximization, IntMatrix bounds, int length, IRandom random) {
+      var infillProblem = algorithm.Problem as DiscreteInfillProblem;
       if (infillProblem == null) throw new ArgumentException("The algortihm has no InfillProblem to solve");
       infillProblem.Encoding.Length = length;
@@ -87 +122 @@
       infillProblem.Initialize(model, maximization);
       var res = EgoUtilities.SyncRunSubAlgorithm(algorithm, random.Next(int.MaxValue), Cancellation);
-      var v = res[InfillProblem.BestInfillSolutionResultName].Value as RealVector;
+      var v = res[DiscreteInfillProblem.BestInfillSolutionResultName].Value as IntegerVector;
       algorithm.Runs.Clear();
       return v;
     }
 
-    private static double GetMinDifference(IDataset data, RealVector r) {
+    private static double GetMinDifference(IDataset data, IntegerVector r) {
       var mind = double.MaxValue;
       for (var i = 0; i < data.Rows; i++) {