#region License Information /* HeuristicLab * Copyright (C) 2002-2012 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.Collections.Generic; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; using HeuristicLab.Operators; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Regression { [Item("ReplaceBranchMoveSoftTabuCriterion", @"")] [StorableClass] public class ReplaceBranchMoveSoftTabuCriterion : SingleSuccessorOperator, ISymbolicExpressionTreeMoveOperator, ITabuChecker { public override bool CanChangeName { get { return false; } } public ILookupParameter ReplaceBranchMoveParameter { get { return (LookupParameter)Parameters["ReplaceBranchMove"]; } } public ILookupParameter SymbolicExpressionTreeParameter { get { return (LookupParameter)Parameters["SymbolicExpressionTree"]; } } public ILookupParameter> TabuListParameter { get { return (ILookupParameter>)Parameters["TabuList"]; } } public ILookupParameter MoveTabuParameter { get { return (ILookupParameter)Parameters["MoveTabu"]; } } public IValueLookupParameter MaximizationParameter { get { return (IValueLookupParameter)Parameters["Maximization"]; } } public ILookupParameter MoveQualityParameter { get { return (ILookupParameter)Parameters["MoveQuality"]; } } public ValueParameter UseQualityAspirationCriterionParameter { get { return (ValueParameter)Parameters["UseQualityAspirationCriterion"]; } } public ValueParameter UseSemanticAspirationCriterionParameter { get { return (ValueParameter)Parameters["UseSemanticAspirationCriterion"]; } } public ILookupParameter SemanticAspirationParameter { get { return (ILookupParameter)Parameters["SemanticAspirations"]; } } public ILookupParameter QualityAspirationParameter { get { return (ILookupParameter)Parameters["QualityAspirations"]; } } public BoolValue UseQualityAspirationCriterion { get { return UseQualityAspirationCriterionParameter.Value; } set { UseQualityAspirationCriterionParameter.Value = value; } } public BoolValue UseSemanticAspirationCriterion { get { return UseSemanticAspirationCriterionParameter.Value; } set { UseSemanticAspirationCriterionParameter.Value = value; } } [StorableConstructor] protected ReplaceBranchMoveSoftTabuCriterion(bool deserializing) : base(deserializing) { } protected ReplaceBranchMoveSoftTabuCriterion(ReplaceBranchMoveSoftTabuCriterion original, Cloner cloner) : base(original, cloner) { } public ReplaceBranchMoveSoftTabuCriterion() : base() { Parameters.Add(new LookupParameter("ReplaceBranchMove", "The move to evaluate.")); Parameters.Add(new LookupParameter("MoveTabu", "The variable to store if a move was tabu.")); Parameters.Add(new LookupParameter("SymbolicExpressionTree", "The solution as symbolic expression tree.")); Parameters.Add(new LookupParameter>("TabuList", "The tabu list.")); Parameters.Add(new ValueParameter("UseQualityAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true))); Parameters.Add(new ValueParameter("UseSemanticAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true))); Parameters.Add(new ValueLookupParameter("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem.")); Parameters.Add(new LookupParameter("MoveQuality", "The quality of the current move.")); Parameters.Add(new LookupParameter("SemanticAspirations")); Parameters.Add(new LookupParameter("QualityAspirations")); } public override IDeepCloneable Clone(Cloner cloner) { return new ReplaceBranchMoveSoftTabuCriterion(this, cloner); } public override IOperation Apply() { ItemList tabuList = TabuListParameter.ActualValue; var move = ReplaceBranchMoveParameter.ActualValue; bool isTabu = true; bool useQualityAspiration = UseQualityAspirationCriterion.Value; bool useSemanticAspiration = UseSemanticAspirationCriterion.Value; bool maximization = MaximizationParameter.ActualValue.Value; double moveQuality = MoveQualityParameter.ActualValue.Value; List path = new List(); path.Add(move.SubtreeIndex); var parent = move.Parent.Parent; var child = move.Parent; while (parent != null) { path.Add(parent.IndexOfSubtree(child)); child = parent; parent = parent.Parent; } path.Reverse(); isTabu = false; int semanticAspirations = 0; int qualityAspirations = 0; // run through the tabu list backwards so that we can break at the most recent relevant change for (int i = tabuList.Count - 1; i >= 0 && isTabu == false; i--) { var tabuAttribute = tabuList[i]; var absTabuAttribute = tabuAttribute as ChangeNodeTypeMoveAbsoluteAttribute; // three aspiration criteria if (useQualityAspiration && IsBetter(maximization, moveQuality, absTabuAttribute.MoveQuality)) { qualityAspirations++; continue; } if (BeginsWith(path, absTabuAttribute.Path)) break; // not necessary to check the remainder of the tabu list isTabu = IsSamePath(path, absTabuAttribute.Path); // check semantic aspiration criterion only afterwards because it is expansive to evaluate if (isTabu && useSemanticAspiration && IsLessSimilar(absTabuAttribute, move)) { isTabu = false; semanticAspirations++; } } MoveTabuParameter.ActualValue = new BoolValue(isTabu); var semAsp = SemanticAspirationParameter.ActualValue ?? new DoubleValue(); var qualAsp = QualityAspirationParameter.ActualValue ?? new DoubleValue(); semAsp.Value += semanticAspirations; qualAsp.Value += qualityAspirations; SemanticAspirationParameter.ActualValue = semAsp; QualityAspirationParameter.ActualValue = qualAsp; return base.Apply(); } // checks wether the path to the node is the same or the tabu path is a parent private bool IsSamePath(List path, int[] tabuPath) { if (tabuPath.Length != path.Count) return false; for (int j = 0; j < tabuPath.Length; j++) { if (tabuPath[j] != path[j]) { return false; } } return true; } private bool IsLessSimilar(ChangeNodeTypeMoveAbsoluteAttribute tabuAttribute, ReplaceBranchMove move) { // check correlations // R(prev, next) // R(current, next) // tabu = R(prev,next) > R(current,next) // == the new move would be closer to the original than the previous move OnlineCalculatorError error; double rPrevNext = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.NewOutput, out error); if (error != OnlineCalculatorError.None) rPrevNext = 0.0; double rPrevCurrent = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.OriginalOutput, out error); if (error != OnlineCalculatorError.None) rPrevCurrent = 0.0; return rPrevNext < rPrevCurrent; } private bool BeginsWith(List path, int[] prefix) { if (path.Count <= prefix.Length) return false; for (int j = 0; j < prefix.Length; j++) if (prefix[j] != path[j]) return false; return true; } private bool IsBetter(bool maximization, double lhs, double rhs) { return maximization ? lhs > rhs : lhs < rhs; } } }