Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs @ 8292

Last change on this file since 8292 was 8292, checked in by gkronber, 10 years ago

#1847: worked on move operators. version of the final EMSS submission

File size: 9.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Regression {
33  [Item("ReplaceBranchMoveSoftTabuCriterion", @"")]
34  [StorableClass]
35  public class ReplaceBranchMoveSoftTabuCriterion : SingleSuccessorOperator, ISymbolicExpressionTreeMoveOperator, ITabuChecker {
36    public override bool CanChangeName {
37      get { return false; }
38    }
39    public ILookupParameter<ReplaceBranchMove> ReplaceBranchMoveParameter {
40      get { return (LookupParameter<ReplaceBranchMove>)Parameters["ReplaceBranchMove"]; }
41    }
42    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
43      get { return (LookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
44    }
45    public ILookupParameter<ItemList<IItem>> TabuListParameter {
46      get { return (ILookupParameter<ItemList<IItem>>)Parameters["TabuList"]; }
47    }
48    public ILookupParameter<BoolValue> MoveTabuParameter {
49      get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
50    }
51    public IValueLookupParameter<BoolValue> MaximizationParameter {
52      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
53    }
54    public ILookupParameter<DoubleValue> MoveQualityParameter {
55      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
56    }
57    public ValueParameter<BoolValue> UseQualityAspirationCriterionParameter {
58      get { return (ValueParameter<BoolValue>)Parameters["UseQualityAspirationCriterion"]; }
59    }
60    public ValueParameter<BoolValue> UseSemanticAspirationCriterionParameter {
61      get { return (ValueParameter<BoolValue>)Parameters["UseSemanticAspirationCriterion"]; }
62    }
63    public ILookupParameter<DoubleValue> SemanticAspirationParameter {
64      get { return (ILookupParameter<DoubleValue>)Parameters["SemanticAspirations"]; }
65    }
66    public ILookupParameter<DoubleValue> QualityAspirationParameter {
67      get { return (ILookupParameter<DoubleValue>)Parameters["QualityAspirations"]; }
68    }
69
70    public BoolValue UseQualityAspirationCriterion {
71      get { return UseQualityAspirationCriterionParameter.Value; }
72      set { UseQualityAspirationCriterionParameter.Value = value; }
73    }
74    public BoolValue UseSemanticAspirationCriterion {
75      get { return UseSemanticAspirationCriterionParameter.Value; }
76      set { UseSemanticAspirationCriterionParameter.Value = value; }
77    }
78
79    [StorableConstructor]
80    protected ReplaceBranchMoveSoftTabuCriterion(bool deserializing) : base(deserializing) { }
81    protected ReplaceBranchMoveSoftTabuCriterion(ReplaceBranchMoveSoftTabuCriterion original, Cloner cloner) : base(original, cloner) { }
82    public ReplaceBranchMoveSoftTabuCriterion()
83      : base() {
84      Parameters.Add(new LookupParameter<ReplaceBranchMove>("ReplaceBranchMove", "The move to evaluate."));
85      Parameters.Add(new LookupParameter<BoolValue>("MoveTabu", "The variable to store if a move was tabu."));
86      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The solution as symbolic expression tree."));
87      Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
88      Parameters.Add(new ValueParameter<BoolValue>("UseQualityAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
89      Parameters.Add(new ValueParameter<BoolValue>("UseSemanticAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
90      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
91      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
92      Parameters.Add(new LookupParameter<DoubleValue>("SemanticAspirations"));
93      Parameters.Add(new LookupParameter<DoubleValue>("QualityAspirations"));
94    }
95
96    public override IDeepCloneable Clone(Cloner cloner) {
97      return new ReplaceBranchMoveSoftTabuCriterion(this, cloner);
98    }
99
100    public override IOperation Apply() {
101      ItemList<IItem> tabuList = TabuListParameter.ActualValue;
102      var move = ReplaceBranchMoveParameter.ActualValue;
103      bool isTabu = true;
104      bool useQualityAspiration = UseQualityAspirationCriterion.Value;
105      bool useSemanticAspiration = UseSemanticAspirationCriterion.Value;
106      bool maximization = MaximizationParameter.ActualValue.Value;
107      double moveQuality = MoveQualityParameter.ActualValue.Value;
108
109      List<int> path = new List<int>();
110      path.Add(move.SubtreeIndex);
111      var parent = move.Parent.Parent;
112      var child = move.Parent;
113      while (parent != null) {
114        path.Add(parent.IndexOfSubtree(child));
115        child = parent;
116        parent = parent.Parent;
117      }
118      path.Reverse();
119
120      isTabu = false;
121      int semanticAspirations = 0;
122      int qualityAspirations = 0;
123      // run through the tabu list backwards so that we can break at the most recent relevant change
124      for (int i = tabuList.Count - 1; i >= 0 && isTabu == false; i--) {
125        var tabuAttribute = tabuList[i];
126        var absTabuAttribute = tabuAttribute as ChangeNodeTypeMoveAbsoluteAttribute;
127        // three aspiration criteria
128        if (useQualityAspiration && IsBetter(maximization, moveQuality, absTabuAttribute.MoveQuality)) {
129          qualityAspirations++;
130          continue;
131        }
132        if (BeginsWith(path, absTabuAttribute.Path))
133          break; // not necessary to check the remainder of the tabu list
134
135        isTabu = IsSamePath(path, absTabuAttribute.Path);
136        // check semantic aspiration criterion only afterwards because it is expansive to evaluate
137        if (isTabu && useSemanticAspiration && IsLessSimilar(absTabuAttribute, move)) {
138          isTabu = false;
139          semanticAspirations++;
140        }
141      }
142
143      MoveTabuParameter.ActualValue = new BoolValue(isTabu);
144      var semAsp = SemanticAspirationParameter.ActualValue ?? new DoubleValue();
145      var qualAsp = QualityAspirationParameter.ActualValue ?? new DoubleValue();
146      semAsp.Value += semanticAspirations;
147      qualAsp.Value += qualityAspirations;
148      SemanticAspirationParameter.ActualValue = semAsp;
149      QualityAspirationParameter.ActualValue = qualAsp;
150      return base.Apply();
151    }
152
153    // checks wether the path to the node is the same or the tabu path is a parent
154    private bool IsSamePath(List<int> path, int[] tabuPath) {
155      if (tabuPath.Length != path.Count) return false;
156      for (int j = 0; j < tabuPath.Length; j++) {
157        if (tabuPath[j] != path[j]) {
158          return false;
159        }
160      }
161      return true;
162    }
163
164    private bool IsLessSimilar(ChangeNodeTypeMoveAbsoluteAttribute tabuAttribute, ReplaceBranchMove move) {
165      // check correlations
166      // R(prev, next)
167      // R(current, next)
168      // tabu = R(prev,next) > R(current,next)
169      // == the new move would be closer to the original than the previous move
170      OnlineCalculatorError error;
171      double rPrevNext = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.NewOutput, out error);
172      if (error != OnlineCalculatorError.None) rPrevNext = 0.0;
173      double rPrevCurrent = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.OriginalOutput,
174                                                                       out error);
175      if (error != OnlineCalculatorError.None) rPrevCurrent = 0.0;
176      return rPrevNext < rPrevCurrent;
177    }
178
179    private bool BeginsWith(List<int> path, int[] prefix) {
180      if (path.Count <= prefix.Length) return false;
181      for (int j = 0; j < prefix.Length; j++)
182        if (prefix[j] != path[j]) return false;
183      return true;
184    }
185
186    private bool IsBetter(bool maximization, double lhs, double rhs) {
187      return maximization ? lhs > rhs : lhs < rhs;
188    }
189  }
190}
Note: See TracBrowser for help on using the repository browser.