source: branches/2745_EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/DiscreteEGO/DiscreteInfillSolver.cs @ 17915

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Threading;
using System.Linq;
using System.Collections.Generic;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Problems.DataAnalysis;

namespace HeuristicLab.Algorithms.EGO {
  [Item("DiscreteInfillSolver", "An IntegerVectorCreator that creates candidates by optimizing an infill-subproblem")]
    [StorableType("50004a0b-b3aa-438c-bd80-bd5ff1763683")]
    public class DiscreteInfillSolver : IntegerVectorCreator, ICancellableOperator {

    public ILookupParameter<IAlgorithm> InfillOptimizationAlgorithmParamter => (ILookupParameter<IAlgorithm>)Parameters["InfillAlgorithm"];
    public ILookupParameter<IRegressionSolution> ModelParameter => (ILookupParameter<IRegressionSolution>)Parameters["Model"];
    public ILookupParameter<BoolValue> MaximizationParameter => (ILookupParameter<BoolValue>)Parameters["Maximization"];
    public ILookupParameter<BoolValue> RemoveDuplicatesParameter => (ILookupParameter<BoolValue>)Parameters["RemoveDuplicates"];
    public IFixedValueParameter<DoubleValue> DuplicateCutoffParameter => (IFixedValueParameter<DoubleValue>)Parameters["Duplicates Cutoff"];
    public ILookupParameter<IntMatrix> InfillBoundsParameter => (ILookupParameter<IntMatrix>)Parameters["InfillBounds"];

    public CancellationToken Cancellation { get; set; }

    [StorableConstructor]
    protected DiscreteInfillSolver(StorableConstructorFlag 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 });
      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Whether the original problem is a maximization problem") { Hidden = true });
      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<IntMatrix>("InfillBounds", "The bounds applied for infill solving") { Hidden = true });
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new DiscreteInfillSolver(this, cloner);
    }

    protected override IntegerVector Create(IRandom random, IntValue length, IntMatrix bounds) {
      var infillBounds = InfillBoundsParameter.ActualValue;
      if (infillBounds != null && infillBounds.Rows > 0) {
        bounds = infillBounds;
      }

      var alg = InfillOptimizationAlgorithmParamter.ActualValue;
      var model = ModelParameter.ActualValue;
      var max = MaximizationParameter.ActualValue.Value;
      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;

      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.Columns>2?bounds[dim % bounds.Rows, 2]:1 * 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 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.Columns>2?b[bi, 2]:1;
      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;
      infillProblem.Encoding.Bounds = bounds;
      infillProblem.Initialize(model, maximization);
      var res = EgoUtilities.SyncRunSubAlgorithm(algorithm, random.Next(int.MaxValue), Cancellation);
      var v = res[DiscreteInfillProblem.BestInfillSolutionResultName].Value as IntegerVector;
      algorithm.Runs.Clear();
      return v;
    }

    private static double GetMinDifference(IDataset data, IntegerVector r) {
      var mind = double.MaxValue;
      for (var i = 0; i < data.Rows; i++) {
        var d = 0.0;
        for (var j = 0; j < r.Length; j++) {
          var d2 = data.GetDoubleValue("input" + j, i) - r[j];
          d += d2 * d2;
        }
        if (!(d < mind)) continue;
        mind = d;
      }
      return mind;
    }



  }
}