#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 . */ #endregion using System; using System.Collections.Generic; using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Regression { [Item("SymbolicRegressionSingleObjectiveOSGAEvaluator", "An evaluator which tries to predict when a child will not be able to fullfil offspring selection criteria, to save evaluation time.")] [StorableClass] public class SymbolicRegressionSingleObjectiveOsgaEvaluator : SymbolicRegressionSingleObjectiveEvaluator { private const string RelativeParentChildQualityThresholdParameterName = "RelativeParentChildQualityThreshold"; private const string RelativeFitnessEvaluationIntervalSizeParameterName = "RelativeFitnessEvaluationIntervalSize"; private const string ResultCollectionParameterName = "Results"; private const string AggregateStatisticsParameterName = "AggregateStatistics"; private const string ActualSelectionPressureParameterName = "SelectionPressure"; private const string UseAdaptiveQualityThresholdParameterName = "UseAdaptiveQualityThreshold"; private const string UseFixedEvaluationIntervalsParameterName = "UseFixedEvaluationIntervals"; private const string PreserveResultCompatibilityParameterName = "PreserveEvaluationResultCompatibility"; #region parameters public IFixedValueParameter PreserveResultCompatibilityParameter { get { return (IFixedValueParameter)Parameters[PreserveResultCompatibilityParameterName]; } } public IFixedValueParameter UseFixedEvaluationIntervalsParameter { get { return (IFixedValueParameter)Parameters[UseFixedEvaluationIntervalsParameterName]; } } public IFixedValueParameter UseAdaptiveQualityThresholdParameter { get { return (IFixedValueParameter)Parameters[UseAdaptiveQualityThresholdParameterName]; } } public ILookupParameter ActualSelectionPressureParameter { get { return (ILookupParameter)Parameters[ActualSelectionPressureParameterName]; } } public ILookupParameter ResultCollectionParameter { get { return (ILookupParameter)Parameters[ResultCollectionParameterName]; } } public IValueParameter AggregateStatisticsParameter { get { return (IValueParameter)Parameters[AggregateStatisticsParameterName]; } } public IValueLookupParameter ComparisonFactorParameter { get { return (ValueLookupParameter)Parameters["ComparisonFactor"]; } } public IFixedValueParameter RelativeParentChildQualityThresholdParameter { get { return (IFixedValueParameter)Parameters[RelativeParentChildQualityThresholdParameterName]; } } public IFixedValueParameter RelativeFitnessEvaluationIntervalSizeParameter { get { return (IFixedValueParameter)Parameters[RelativeFitnessEvaluationIntervalSizeParameterName]; } } public IScopeTreeLookupParameter ParentQualitiesParameter { get { return (IScopeTreeLookupParameter)Parameters["ParentQualities"]; } } #endregion #region parameter properties public bool AggregateStatistics { get { return AggregateStatisticsParameter.Value.Value; } set { AggregateStatisticsParameter.Value.Value = value; } } public bool PreserveResultCompatibility { get { return PreserveResultCompatibilityParameter.Value.Value; } set { PreserveResultCompatibilityParameter.Value.Value = value; } } public bool UseFixedEvaluationIntervals { get { return UseFixedEvaluationIntervalsParameter.Value.Value; } set { UseFixedEvaluationIntervalsParameter.Value.Value = value; } } public bool UseAdaptiveQualityThreshold { get { return UseAdaptiveQualityThresholdParameter.Value.Value; } set { UseAdaptiveQualityThresholdParameter.Value.Value = value; } } public double RelativeParentChildQualityThreshold { get { return RelativeParentChildQualityThresholdParameter.Value.Value; } set { RelativeParentChildQualityThresholdParameter.Value.Value = value; } } public double RelativeFitnessEvaluationIntervalSize { get { return RelativeFitnessEvaluationIntervalSizeParameter.Value.Value; } set { RelativeFitnessEvaluationIntervalSizeParameter.Value.Value = value; } } #endregion public override bool Maximization { get { return true; } } // keep track of statistics public double AdjustedEvaluatedSolutions { get; set; } public IntMatrix RejectedStats { get; set; } public IntMatrix TotalStats { get; set; } public SymbolicRegressionSingleObjectiveOsgaEvaluator() { Parameters.Add(new ValueLookupParameter("ComparisonFactor", "Determines if the quality should be compared to the better parent (1.0), to the worse (0.0) or to any linearly interpolated value between them.")); Parameters.Add(new FixedValueParameter(RelativeParentChildQualityThresholdParameterName, new PercentValue(0.9))); Parameters.Add(new FixedValueParameter(RelativeFitnessEvaluationIntervalSizeParameterName, new PercentValue(0.1))); Parameters.Add(new LookupParameter(ResultCollectionParameterName)); Parameters.Add(new ScopeTreeLookupParameter("ParentQualities") { ActualName = "Quality" }); Parameters.Add(new ValueParameter(AggregateStatisticsParameterName, new BoolValue(false))); Parameters.Add(new LookupParameter(ActualSelectionPressureParameterName)); Parameters.Add(new FixedValueParameter(UseAdaptiveQualityThresholdParameterName, new BoolValue(false))); Parameters.Add(new FixedValueParameter(UseFixedEvaluationIntervalsParameterName, new BoolValue(false))); Parameters.Add(new FixedValueParameter(PreserveResultCompatibilityParameterName, new BoolValue(false))); RejectedStats = new IntMatrix(); TotalStats = new IntMatrix(); } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { if (!Parameters.ContainsKey(ActualSelectionPressureParameterName)) Parameters.Add(new LookupParameter(ActualSelectionPressureParameterName)); if (!Parameters.ContainsKey(UseAdaptiveQualityThresholdParameterName)) Parameters.Add(new FixedValueParameter(UseAdaptiveQualityThresholdParameterName, new BoolValue(false))); if (!Parameters.ContainsKey(UseFixedEvaluationIntervalsParameterName)) Parameters.Add(new FixedValueParameter(UseFixedEvaluationIntervalsParameterName, new BoolValue(false))); if (!Parameters.ContainsKey(PreserveResultCompatibilityParameterName)) Parameters.Add(new FixedValueParameter(PreserveResultCompatibilityParameterName, new BoolValue(false))); } [StorableConstructor] protected SymbolicRegressionSingleObjectiveOsgaEvaluator(bool deserializing) : base(deserializing) { TotalStats = new IntMatrix(); RejectedStats = new IntMatrix(); } protected SymbolicRegressionSingleObjectiveOsgaEvaluator(SymbolicRegressionSingleObjectiveOsgaEvaluator original, Cloner cloner) : base(original, cloner) { if (original.TotalStats != null) TotalStats = cloner.Clone(original.TotalStats); if (original.RejectedStats != null) RejectedStats = cloner.Clone(original.RejectedStats); } public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicRegressionSingleObjectiveOsgaEvaluator(this, cloner); } public override void ClearState() { base.ClearState(); RejectedStats = new IntMatrix(); TotalStats = new IntMatrix(); AdjustedEvaluatedSolutions = 0; } public override IOperation InstrumentedApply() { var solution = SymbolicExpressionTreeParameter.ActualValue; IEnumerable rows = GenerateRowsToEvaluate(); var interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue; var estimationLimits = EstimationLimitsParameter.ActualValue; var problemData = ProblemDataParameter.ActualValue; var applyLinearScaling = ApplyLinearScalingParameter.ActualValue.Value; double quality; var parentQualities = ParentQualitiesParameter.ActualValue; // parent subscopes are not present during evaluation of the initial population if (parentQualities.Length > 0) { quality = Calculate(interpreter, solution, estimationLimits, problemData, rows); } else { quality = Calculate(interpreter, solution, estimationLimits.Lower, estimationLimits.Upper, problemData, rows, applyLinearScaling); } QualityParameter.ActualValue = new DoubleValue(quality); return base.InstrumentedApply(); } public static double Calculate(ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, ISymbolicExpressionTree solution, double lowerEstimationLimit, double upperEstimationLimit, IRegressionProblemData problemData, IEnumerable rows, bool applyLinearScaling) { IEnumerable estimatedValues = interpreter.GetSymbolicExpressionTreeValues(solution, problemData.Dataset, rows); IEnumerable targetValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, rows); OnlineCalculatorError errorState; double r; if (applyLinearScaling) { var rCalculator = new OnlinePearsonsRCalculator(); CalculateWithScaling(targetValues, estimatedValues, lowerEstimationLimit, upperEstimationLimit, rCalculator, problemData.Dataset.Rows); errorState = rCalculator.ErrorState; r = rCalculator.R; } else { IEnumerable boundedEstimatedValues = estimatedValues.LimitToRange(lowerEstimationLimit, upperEstimationLimit); r = OnlinePearsonsRCalculator.Calculate(targetValues, boundedEstimatedValues, out errorState); } if (errorState != OnlineCalculatorError.None) return double.NaN; return r * r; } private double Calculate(ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, ISymbolicExpressionTree solution, DoubleLimit estimationLimits, IRegressionProblemData problemData, IEnumerable rows) { var lowerEstimationLimit = EstimationLimitsParameter.ActualValue.Lower; var upperEstimationLimit = EstimationLimitsParameter.ActualValue.Upper; var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(solution, problemData.Dataset, rows).LimitToRange(lowerEstimationLimit, upperEstimationLimit); var targetValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, rows).ToList(); var parentQualities = ParentQualitiesParameter.ActualValue.Select(x => x.Value); var minQuality = double.MaxValue; var maxQuality = double.MinValue; foreach (var quality in parentQualities) { if (minQuality > quality) minQuality = quality; if (maxQuality < quality) maxQuality = quality; } var comparisonFactor = ComparisonFactorParameter.ActualValue.Value; var parentQuality = minQuality + (maxQuality - minQuality) * comparisonFactor; #region fixed intervals if (UseFixedEvaluationIntervals) { double threshold = parentQuality * RelativeParentChildQualityThreshold; if (UseAdaptiveQualityThreshold) { var actualSelectionPressure = ActualSelectionPressureParameter.ActualValue; if (actualSelectionPressure != null) threshold = parentQuality * (1 - actualSelectionPressure.Value / 100.0); } var estimatedEnumerator = estimatedValues.GetEnumerator(); var targetEnumerator = targetValues.GetEnumerator(); var rcalc = new OnlinePearsonsRCalculator(); var trainingPartitionSize = problemData.TrainingPartition.Size; var interval = (int)Math.Floor(trainingPartitionSize * RelativeFitnessEvaluationIntervalSize); var calculatedRows = 0; #region aggregate statistics if (AggregateStatistics) { var trainingEnd = problemData.TrainingPartition.End; double quality = 0; int intervalCount = 0, rejectionInterval = 0; var predictedRejected = false; while (estimatedEnumerator.MoveNext() & targetEnumerator.MoveNext()) { var estimated = estimatedEnumerator.Current; var target = targetEnumerator.Current; rcalc.Add(target, estimated); ++calculatedRows; if (calculatedRows % interval == 0 || calculatedRows == trainingPartitionSize) { intervalCount++; if (predictedRejected) continue; var r = rcalc.ErrorState == OnlineCalculatorError.None ? rcalc.R : 0d; quality = r * r; if (!(quality > threshold)) { rejectionInterval = intervalCount - 1; predictedRejected = true; } } } var actualQuality = rcalc.ErrorState == OnlineCalculatorError.None ? rcalc.R : 0d; actualQuality *= actualQuality; if (!predictedRejected) quality = actualQuality; var actuallyRejected = !(actualQuality > parentQuality); if (RejectedStats.Rows == 0 || TotalStats.Rows == 0) { RejectedStats = new IntMatrix(2, intervalCount + 1); RejectedStats.RowNames = new[] { "Predicted", "Actual" }; RejectedStats.ColumnNames = Enumerable.Range(1, RejectedStats.Columns).Select(x => string.Format("0-{0}", Math.Min(trainingEnd, x * interval))); TotalStats = new IntMatrix(2, 1); TotalStats.RowNames = new[] { "Predicted", "Actual" }; TotalStats.ColumnNames = new[] { "Rejected" }; } if (actuallyRejected) { TotalStats[0, 0]++; // prediction true TotalStats[1, 0]++; RejectedStats[0, rejectionInterval]++; RejectedStats[1, rejectionInterval]++; } else { if (predictedRejected) { RejectedStats[0, rejectionInterval]++; TotalStats[0, 0]++; } } return quality; } #endregion else { while (estimatedEnumerator.MoveNext() & targetEnumerator.MoveNext()) { rcalc.Add(targetEnumerator.Current, estimatedEnumerator.Current); ++calculatedRows; if (calculatedRows % interval == 0 || calculatedRows == trainingPartitionSize) { var q = rcalc.ErrorState != OnlineCalculatorError.None ? double.NaN : rcalc.R; var quality = q * q; if (!(quality > threshold)) { AdjustedEvaluatedSolutions += (double)calculatedRows / problemData.TrainingPartition.Size; return quality; } } } var r = rcalc.ErrorState != OnlineCalculatorError.None ? double.NaN : rcalc.R; var actualQuality = r * r; AdjustedEvaluatedSolutions += 1d; return actualQuality; } #endregion } else { var lsc = new OnlineLinearScalingParameterCalculator(); var rcalc = new OnlinePearsonsRCalculator(); var interval = (int)Math.Round(RelativeFitnessEvaluationIntervalSize * problemData.TrainingPartition.Size); var quality = 0d; var calculatedRows = 0; var cache = PreserveResultCompatibility ? new List(problemData.TrainingPartition.Size) : null; foreach (var target in estimatedValues.Zip(targetValues, (e, t) => new { EstimatedValue = e, ActualValue = t })) { if (cache != null) cache.Add(target.EstimatedValue); lsc.Add(target.EstimatedValue, target.ActualValue); rcalc.Add(target.EstimatedValue, target.ActualValue); calculatedRows++; if (calculatedRows % interval != 0) continue; var alpha = lsc.Alpha; var beta = lsc.Beta; if (lsc.ErrorState != OnlineCalculatorError.None) { alpha = 0; beta = 1; } var calc = (OnlinePearsonsRCalculator)rcalc.Clone(); foreach (var t in targetValues.Skip(calculatedRows)) { var s = (t - alpha) / beta; // scaled target calc.Add(s, t); // add pair (scaled, target) to the calculator } var r = calc.ErrorState == OnlineCalculatorError.None ? calc.R : 0d; quality = r * r; if (!(quality > parentQuality)) { AdjustedEvaluatedSolutions += (double)calculatedRows / problemData.TrainingPartition.Size; return quality; } } if (PreserveResultCompatibility) { // get quality for all the rows. to ensure reproducibility of results between this evaluator // and the standard one, we calculate the quality in an identical way (otherwise the returned // quality could be slightly off due to rounding errors (in the range 1e-15 to 1e-16) var applyLinearScaling = ApplyLinearScalingParameter.ActualValue.Value; double r; OnlineCalculatorError calculatorError; if (applyLinearScaling) { var alpha = lsc.Alpha; var beta = lsc.Beta; if (lsc.ErrorState != OnlineCalculatorError.None) { alpha = 0; beta = 1; } var boundedEstimatedValues = cache.Select(x => x * beta + alpha).LimitToRange(estimationLimits.Lower, estimationLimits.Upper); r = OnlinePearsonsRCalculator.Calculate(boundedEstimatedValues, targetValues, out calculatorError); } else { var boundedEstimatedValues = cache.LimitToRange(estimationLimits.Lower, estimationLimits.Upper); r = OnlinePearsonsRCalculator.Calculate(boundedEstimatedValues, targetValues, out calculatorError); } quality = calculatorError == OnlineCalculatorError.None ? r * r : 0d; } AdjustedEvaluatedSolutions += 1d; return quality; } } public override double Evaluate(IExecutionContext context, ISymbolicExpressionTree tree, IRegressionProblemData problemData, IEnumerable rows) { SymbolicDataAnalysisTreeInterpreterParameter.ExecutionContext = context; EstimationLimitsParameter.ExecutionContext = context; ApplyLinearScalingParameter.ExecutionContext = context; var interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue; var estimationLimits = EstimationLimitsParameter.ActualValue; var applyLinearScaling = ApplyLinearScalingParameter.ActualValue.Value; double r2 = Calculate(interpreter, tree, estimationLimits.Lower, estimationLimits.Upper, problemData, rows, applyLinearScaling); SymbolicDataAnalysisTreeInterpreterParameter.ExecutionContext = null; EstimationLimitsParameter.ExecutionContext = null; ApplyLinearScalingParameter.ExecutionContext = null; return r2; } } }