Free cookie consent management tool by TermsFeed Policy Generator

# Changeset 14818

Ignore:
Timestamp:
04/04/17 12:37:52 (7 years ago)
Message:

#2745 added several new InfillCriteria and moved Parameters from the InfillProblem to the Criteria themselves; added Sanitiy checks for GaussianProcessRegression

Location:
branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO
Files:
10 edited

Unmodified
Removed

• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/EgoUtilities.cs

 r14768 public static double GetEstimation(this IRegressionModel model, RealVector r) { var dataset = GetDataSet(new[] { new Tuple(r, 0.0) }); var dataset = GetDataSet(new[] { new Tuple(r, 0.0) }, false); return model.GetEstimatedValues(dataset, new[] { 0 }).First(); } public static double GetVariance(this IConfidenceRegressionModel model, RealVector r) { var dataset = GetDataSet(new[] { new Tuple(r, 0.0) }); var dataset = GetDataSet(new[] { new Tuple(r, 0.0) }, false); return model.GetEstimatedVariances(dataset, new[] { 0 }).First(); } public static Dataset GetDataSet(IReadOnlyList> samples) { var n = samples[0].Item1.Length + 1; var data = new double[samples.Count, n]; var names = new string[n - 1]; for (var i = 0; i < n; i++) if (i < names.Length) { names[i] = "input" + i; for (var j = 0; j < samples.Count; j++) data[j, i] = samples[j].Item1[i]; } else for (var j = 0; j < samples.Count; j++) data[j, n - 1] = samples[j].Item2; public static double GetDoubleValue(this IDataset dataset, int i, int j) { return dataset.GetDoubleValue("input" + j, i); } public static Dataset GetDataSet(IReadOnlyList> samples, bool removeDuplicates) { if (removeDuplicates) samples = RemoveDuplicates(samples); //TODO duplicates require heteroskedasticity in Models var dimensions = samples[0].Item1.Length + 1; var data = new double[samples.Count, dimensions]; var names = new string[dimensions - 1]; for (var i = 0; i < names.Length; i++) names[i] = "input" + i; for (var j = 0; j < samples.Count; j++) { for (var i = 0; i < names.Length; i++) data[j, i] = samples[j].Item1[i]; data[j, dimensions - 1] = samples[j].Item2; } return new Dataset(names.Concat(new[] { "output" }).ToArray(), data); } private static IReadOnlyList> RemoveDuplicates(IReadOnlyList> samples) { var res = new List>(); foreach (var sample in samples) { if (res.Count == 0) { res.Add(new Tuple(sample.Item1, sample.Item2, 1)); continue; } var index = res.ArgMin(x => Euclidian(sample.Item1, x.Item1)); var d = Euclidian(res[index].Item1, sample.Item1); if (d > 0.0001) res.Add(new Tuple(sample.Item1, sample.Item2, 1)); else { var t = res[index]; res.RemoveAt(index); res.Add(new Tuple(t.Item1, t.Item2 + sample.Item2, t.Item3 + 1)); } } return res.Select(x => new Tuple(x.Item1, x.Item2 / x.Item3)).ToArray(); } private static double Euclidian(IEnumerable a, IEnumerable b) { return Math.Sqrt(a.Zip(b, (d, d1) => d - d1).Sum(d => d * d)); } public static DoubleMatrix GetBoundingBox(IEnumerable vectors) { DoubleMatrix res = null; return res; } } }
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/HeuristicLab.Algorithms.EGO-3.4.csproj

 r14768 ..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll False ..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances.DataAnalysis-3.3.dll False ..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances.DataAnalysis.Views-3.3.dll False
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/InfillCriteria/ExpectedImprovement.cs

 r14768 #region ParameterProperties public IFixedValueParameter ExploitationWeightParameter { get { return Parameters[ExploitationWeightParameterName] as IFixedValueParameter; } } public IFixedValueParameter ExploitationWeightParameter => Parameters[ExploitationWeightParameterName] as IFixedValueParameter; #endregion #region Properties private double ExploitationWeight { get { return ExploitationWeightParameter.Value.Value; } } protected double ExploitationWeight => ExploitationWeightParameter.Value.Value; [Storable] protected double YMin; #endregion #region HL-Constructors, Serialization and Cloning [StorableConstructor] private ExpectedImprovement(bool deserializing) : base(deserializing) { } protected ExpectedImprovement(bool deserializing) : base(deserializing) { } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { RegisterEventhandlers(); } private ExpectedImprovement(ExpectedImprovement original, Cloner cloner) : base(original, cloner) { protected ExpectedImprovement(ExpectedImprovement original, Cloner cloner) : base(original, cloner) { RegisterEventhandlers(); } #endregion public override double Evaluate(IRegressionSolution solution, RealVector vector, bool maximization) { if (maximization) throw new NotImplementedException("Expected Improvement for maximization not yet implemented"); var model = solution.Model as IConfidenceRegressionModel; if (model == null) throw new ArgumentException("can not calculate EI without confidence measure"); public override double Evaluate(RealVector vector) { var model = RegressionSolution.Model as IConfidenceRegressionModel; var yhat = model.GetEstimation(vector); var min = solution.ProblemData.TargetVariableTrainingValues.Min(); var s = Math.Sqrt(model.GetVariance(vector)); return GetEstimatedImprovement(min, yhat, s, ExploitationWeight); return GetEstimatedImprovement(YMin, yhat, s, ExploitationWeight); } public override bool Maximization(bool expensiveProblemMaximization) { public override bool Maximization() { return true; } protected override void Initialize() { if (ExpensiveMaximization) throw new NotImplementedException("Expected Improvement for maximization not yet implemented"); var model = RegressionSolution.Model as IConfidenceRegressionModel; if (model == null) throw new ArgumentException("can not calculate EI without confidence measure"); YMin = RegressionSolution.ProblemData.TargetVariableTrainingValues.Min(); } #region Helpers private static double GetEstimatedImprovement(double ymin, double yhat, double s, double w) { protected static double GetEstimatedImprovement(double ymin, double yhat, double s, double w) { if (Math.Abs(s) < double.Epsilon) return 0; var val = (ymin - yhat) / s;
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/InfillCriteria/ExpectedQuality.cs

 r14741 using HeuristicLab.Encodings.RealVectorEncoding; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.DataAnalysis; // ReSharper disable once CheckNamespace #endregion public override double Evaluate(IRegressionSolution solution, RealVector vector, bool maximization) { return solution.Model.GetEstimation(vector); public override double Evaluate(RealVector vector) { return RegressionSolution.Model.GetEstimation(vector); } public override bool Maximization() { return ExpensiveMaximization; } protected override void Initialize() { } }
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/InfillCriteria/InfillCriterionBase.cs

 r14741 using HeuristicLab.Core; using HeuristicLab.Encodings.RealVectorEncoding; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.DataAnalysis; // ReSharper disable once CheckNamespace namespace HeuristicLab.Algorithms.EGO { [StorableClass] public abstract class InfillCriterionBase : ParameterizedNamedItem, IInfillCriterion { [Storable] protected IRegressionSolution RegressionSolution; [Storable] protected bool ExpensiveMaximization; [Storable] protected RealVectorEncoding Encoding; protected InfillCriterionBase(bool deserializing) : base(deserializing) { } protected InfillCriterionBase(InfillCriterionBase original, Cloner cloner) : base(original, cloner) { } protected InfillCriterionBase(InfillCriterionBase original, Cloner cloner) : base(original, cloner) { RegressionSolution = cloner.Clone(original.RegressionSolution); ExpensiveMaximization = original.ExpensiveMaximization; Encoding = cloner.Clone(original.Encoding); } protected InfillCriterionBase() { } public abstract double Evaluate(IRegressionSolution model, RealVector vector, bool maximization); public virtual bool Maximization(bool expensiveProblemMaximization) { return expensiveProblemMaximization; public abstract double Evaluate(RealVector vector); public abstract bool Maximization(); public void Initialize(IRegressionSolution solution, bool expensiveMaximization, RealVectorEncoding encoding) { RegressionSolution = solution; ExpensiveMaximization = expensiveMaximization; Encoding = encoding; Initialize(); } protected abstract void Initialize(); } }
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/InfillCriteria/RobustImprovement.cs

 r14768 using System; using System.Collections.Generic; using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; [StorableClass] [Item("ConfidenceBoundMeassure", "Adding or Subtracting the variance * factor to the model estimation")] public class ConfidenceBound : InfillCriterionBase { [Item("RobustImprovementMeassure", "Adding or Subtracting the variance * factor to the model estimation")] public class RobustImprovement : InfillCriterionBase { #region ParameterNames private const string ConfidenceWeightParameterName = "ConfidenceWeight"; private const string KParameterName = "NearestNeighbours"; #endregion #region ParameterProperties public IFixedValueParameter ConfidenceWeightParameter { get { return Parameters[ConfidenceWeightParameterName] as IFixedValueParameter; } } public IFixedValueParameter KParameter => Parameters[KParameterName] as IFixedValueParameter; #endregion #region Properties private double ConfidenceWeight { get { return ConfidenceWeightParameter.Value.Value; } } private int K => KParameter.Value.Value; [Storable] private double MaxSolutionDist; [Storable] //TODO use VP-Tree instead of array private RealVector[] Data; #endregion #region HL-Constructors, Serialization and Cloning [StorableConstructor] private ConfidenceBound(bool deserializing) : base(deserializing) { } private ConfidenceBound(ConfidenceBound original, Cloner cloner) : base(original, cloner) { } public ConfidenceBound() { Parameters.Add(new FixedValueParameter(ConfidenceWeightParameterName, "A value between 0 and 1 indicating the focus on exploration (0) or exploitation (1)", new DoubleValue(0.5))); private RobustImprovement(bool deserializing) : base(deserializing) { } private RobustImprovement(RobustImprovement original, Cloner cloner) : base(original, cloner) { MaxSolutionDist = original.MaxSolutionDist; Data = original.Data != null ? original.Data.Select(cloner.Clone).ToArray() : null; } public RobustImprovement() { Parameters.Add(new FixedValueParameter(KParameterName, "A value larger than 0 indicating how many nearestNeighbours shall be used to determine the RI meassure", new IntValue(3))); } public override IDeepCloneable Clone(Cloner cloner) { return new ConfidenceBound(this, cloner); return new RobustImprovement(this, cloner); } #endregion public override double Evaluate(IRegressionSolution solution, RealVector vector, bool maximization) { var model = solution.Model as IConfidenceRegressionModel; public override double Evaluate(RealVector vector) { List nearestNeighbours; List distances; Search(vector, K, out nearestNeighbours, out distances); var distVectors = nearestNeighbours.Select(x => Minus(x, vector)).ToList(); var sum = 0.0; var wsum = 1.0; //weights for angular distance var used = new HashSet(); foreach (var distVector in distVectors) { var d = Math.Pow(distances[used.Count], 0.5); if (used.Count == 0) { sum += d; } else { var w = used.Select(x => Angular(distVector, x)).Min(); sum += w * d; wsum += w; } used.Add(distVector); } sum /= wsum * MaxSolutionDist; //normalize return sum; } public override bool Maximization() { return ExpensiveMaximization; } protected override void Initialize() { var model = RegressionSolution.Model as IConfidenceRegressionModel; if (model == null) throw new ArgumentException("can not calculate EI without confidence measure"); var yhat = model.GetEstimation(vector); var s = Math.Sqrt(model.GetVariance(vector)) * ConfidenceWeight; return maximization ? yhat + s : yhat - s; Data = new RealVector[RegressionSolution.ProblemData.Dataset.Rows]; for (var i = 0; i < Data.Length; i++) { Data[i] = new RealVector(Encoding.Length); for (var j = 0; j < Encoding.Length; j++) Data[i][j] = RegressionSolution.ProblemData.Dataset.GetDoubleValue(i, j); } var maxSolution = new double[Encoding.Length]; var minSolution = new double[Encoding.Length]; for (var i = 0; i < Encoding.Length; i++) { var j = i % Encoding.Bounds.Rows; maxSolution[i] = Encoding.Bounds[j, 1]; minSolution[i] = Encoding.Bounds[j, 0]; } MaxSolutionDist = Euclidian(maxSolution, minSolution) / Data.Length; } #region Helpers private static double Euclidian(IEnumerable a, IEnumerable b) { return Math.Sqrt(a.Zip(b, (d, d1) => d - d1).Sum(d => d * d)); } private static double Angular(RealVector a, RealVector b) { var innerProduct = a.Zip(b, (x, y) => x * y).Sum(); var res = Math.Acos(innerProduct / (Norm(a) * Norm(b))) / Math.PI; return double.IsNaN(res) ? 0 : res; } private static double Norm(IEnumerable a) { return Math.Sqrt(a.Sum(d => d * d)); } private static RealVector Minus(RealVector a, RealVector b) { return new RealVector(a.Zip(b, (d, d1) => d - d1).ToArray()); } private void Search(RealVector vector, int k, out List nearestNeighbours, out List distances) { var neighbours = new SortedList(new DuplicateKeyComparer()); foreach (var n in Data) neighbours.Add(Euclidian(n, vector), n); nearestNeighbours = new List(); distances = new List(); foreach (var entry in neighbours) { nearestNeighbours.Add(entry.Value); distances.Add(entry.Key); if (distances.Count == k) break; } } #endregion public class DuplicateKeyComparer : IComparer where TKey : IComparable { public int Compare(TKey x, TKey y) { var result = x.CompareTo(y); return result == 0 ? 1 : result; } } } }
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/Interfaces/IInfillCriterion.cs

 r14741 namespace HeuristicLab.Algorithms.EGO { public interface IInfillCriterion : INamedItem { double Evaluate(IRegressionSolution model, RealVector vector, bool maximization); bool Maximization(bool expensiveProblemMaximization); double Evaluate(RealVector vector); bool Maximization(); void Initialize(IRegressionSolution solution, bool expensiveMaximization, RealVectorEncoding encoding); } }
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/Interfaces/ISurrogateAlgorithm.cs

 r14768 namespace HeuristicLab.Algorithms.EGO { public interface ISurrogateAlgorithm : IAlgorithm where T : IDeepCloneable { void SetInitialSamples(T[] i, double[] qualities); void SetInitialSamples(T[] solutions, double[] qualities); } }
• ## branches/EfficientGlobalOptimization/HeuristicLab.Algorithms.EGO/Problems/InfillProblem.cs

 r14768 using HeuristicLab.Optimization; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.DataAnalysis; namespace HeuristicLab.Algorithms.EGO { public sealed class InfillProblem : SingleObjectiveBasicProblem { public override bool Maximization => true; public override bool Maximization => true;  //This is necessary because algorithms do not expect the maximization to change #region Properties; [Storable] private SingleObjectiveBasicProblem problem; [Storable] private IRegressionSolution regressionSolution; public IInfillCriterion InfillCriterion problem = value; if (problem == null) return; Encoding = problem.Encoding as RealVectorEncoding; var enc = problem.Encoding as RealVectorEncoding; if (enc == null) throw new ArgumentException("EGO can not be performed on non-RealVectorEncodings"); Encoding = enc; SolutionCreator = new UniformRandomRealVectorCreator();//ignore Problem specific Solution Creation if (Encoding == null) throw new ArgumentException("EGO can not be performed on non-RealVectorEncodings"); } } public IRegressionSolution RegressionSolution { get { return regressionSolution; } set { regressionSolution = value; } } #endregion infillCriterion = cloner.Clone(original.InfillCriterion); problem = cloner.Clone(original.Problem); regressionSolution = cloner.Clone(original.regressionSolution); } public InfillProblem() { } public override double Evaluate(Individual individual, IRandom r) { var q = InfillCriterion.Evaluate(RegressionSolution, individual.RealVector(), Problem.Maximization); return InfillCriterion.Maximization(Problem.Maximization) ? q : -q; //This is necessary because Maximization is not supposed to change on a normal problem var q = InfillCriterion.Evaluate(individual.RealVector()); return InfillCriterion.Maximization() ? q : -q; } public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) { base.Analyze(individuals, qualities, results, random); var best = qualities.ArgMax(x => x); var qnew = InfillCriterion.Maximization(Problem.Maximization) ? qualities[best] : -qualities[best]; //var best = Maximization ? qualities.ArgMax(x => x) : qualities.ArgMin(x => x); var qnew = InfillCriterion.Maximization() ? qualities[best] : -qualities[best]; const string qname = EfficientGlobalOptimizationAlgorithm.BestInfillQualityResultName; const string sname = EfficientGlobalOptimizationAlgorithm.BestInfillSolutionResultName; var qold = results[qname].Value as DoubleValue; if (qold == null) throw new ArgumentException("Old best quality is not a double value. Conflicting Analyzers?"); if (qold.Value >= qnew == InfillCriterion.Maximization(Problem.Maximization)) return; if (qold.Value >= qnew == InfillCriterion.Maximization()) return; results[sname].Value = (RealVector)individuals[best].RealVector().Clone(); qold.Value = qnew; } }
Note: See TracChangeset for help on using the changeset viewer.