Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Selectors/DiversitySelector.cs @ 17141

Last change on this file since 17141 was 17141, checked in by abeham, 5 years ago

#2950: merged r17076 to stable

File size: 9.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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;
23using System.Collections.Generic;
24using HEAL.Attic;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Selection;
32
33namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
34  [StorableType("3E8EA052-3B86-4609-BD38-E3FE78DAD2FF")]
35  [Item("DiversitySelector", "A selection operator that applies a diversity penalty to the objective function before applying an inner selector.")]
36  public sealed class DiversitySelector : StochasticSingleObjectiveSelector, ISingleObjectiveSelector {
37    private const string StrictSimilarityParameterName = "StrictSimilarity";
38    private const string SimilarityWeightParameterName = "SimilarityWeight";
39    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
40    private const string SelectorParameterName = "Selector";
41    private const string DiversityParameterName = "Diversity";
42
43    public IValueParameter<ISingleObjectiveSelector> SelectorParameter {
44      get { return (IValueParameter<ISingleObjectiveSelector>)Parameters[SelectorParameterName]; }
45    }
46
47    public ISingleObjectiveSelector Selector {
48      get { return SelectorParameter.Value; }
49      set { SelectorParameter.Value = value; }
50    }
51
52    public IScopeTreeLookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
53      get { return (IScopeTreeLookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
54    }
55
56    public IScopeTreeLookupParameter<DoubleValue> DiversityParameter {
57      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters[DiversityParameterName]; }
58    }
59
60    public IFixedValueParameter<BoolValue> StrictSimilarityParameter {
61      get { return (IFixedValueParameter<BoolValue>)Parameters[StrictSimilarityParameterName]; }
62    }
63
64    public IFixedValueParameter<DoubleValue> SimilarityWeightParameter {
65      get { return (IFixedValueParameter<DoubleValue>)Parameters[SimilarityWeightParameterName]; }
66    }
67
68    public bool StrictSimilarity {
69      get { return StrictSimilarityParameter.Value.Value; }
70      set { StrictSimilarityParameter.Value.Value = value; }
71    }
72
73    public double SimilarityWeight {
74      get { return SimilarityWeightParameter.Value.Value; }
75      set { SimilarityWeightParameter.Value.Value = value; }
76    }
77
78    public DiversitySelector() : base() {
79      Parameters.Add(new FixedValueParameter<BoolValue>(StrictSimilarityParameterName, "Calculate strict similarity.", new BoolValue(true)));
80      Parameters.Add(new FixedValueParameter<DoubleValue>(SimilarityWeightParameterName, "Weight of the diversity term.", new DoubleValue(1)));
81      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression trees that should be analyzed."));
82      Parameters.Add(new ValueParameter<ISingleObjectiveSelector>(SelectorParameterName, "The inner selection operator to select the parents.", new TournamentSelector()));
83      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(DiversityParameterName, "The diversity value calcuated by the operator (output). The inner selector uses this value."));
84
85      RegisterParameterEventHandlers();
86    }
87
88    [StorableConstructor]
89    private DiversitySelector(StorableConstructorFlag _) : base(_) { }
90
91    private DiversitySelector(DiversitySelector original, Cloner cloner) : base(original, cloner) { }
92
93    public override IDeepCloneable Clone(Cloner cloner) {
94      return new DiversitySelector(this, cloner);
95    }
96
97    [StorableHook(HookType.AfterDeserialization)]
98    private void AfterDeserialization() {
99      if (!Parameters.ContainsKey(DiversityParameterName)) {
100        Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>(DiversityParameterName));
101      }
102
103      RegisterParameterEventHandlers();
104    }
105
106    #region Events
107    private void RegisterParameterEventHandlers() {
108      SelectorParameter.ValueChanged += SelectorParameter_ValueChanged;
109      CopySelectedParameter.ValueChanged += CopySelectedParameter_ValueChanged;
110      CopySelected.ValueChanged += CopySelected_ValueChanged;
111
112      MaximizationParameter.NameChanged += MaximizationParameter_NameChanged;
113      QualityParameter.NameChanged += QualityParameter_NameChanged;
114      RandomParameter.NameChanged += RandomParameter_NameChanged;
115    }
116
117    private void RandomParameter_NameChanged(object sender, EventArgs e) { ParameterizeSelector(Selector); }
118    private void QualityParameter_NameChanged(object sender, EventArgs e) { ParameterizeSelector(Selector); }
119    private void MaximizationParameter_NameChanged(object sender, EventArgs e) { ParameterizeSelector(Selector); }
120
121    private void CopySelectedParameter_ValueChanged(object sender, EventArgs e) {
122      if (CopySelected.Value != true) {
123        CopySelected.Value = true;
124      }
125      CopySelected.ValueChanged += CopySelected_ValueChanged;
126    }
127
128    private void SelectorParameter_ValueChanged(object sender, EventArgs e) {
129      ParameterizeSelector(Selector);
130    }
131
132    private void CopySelected_ValueChanged(object sender, EventArgs e) {
133      if (CopySelected.Value != true) {
134        CopySelected.Value = true;
135      }
136    }
137    #endregion
138
139    protected override IScope[] Select(List<IScope> scopes) {
140      var w = SimilarityWeight;
141      if (w.IsAlmost(0)) {
142        ApplyInnerSelector();
143        return CurrentScope.SubScopes[1].SubScopes.ToArray();  // return selected individuals (selectors create two sub-scopes with remaining and selected)
144      }
145
146      var trees = SymbolicExpressionTreeParameter.ActualValue;
147      var qualities = QualityParameter.ActualValue;
148
149      // calculate average similarity for each tree
150      var similarityMatrix = SymbolicExpressionTreeHash.ComputeSimilarityMatrix(trees, simplify: false, strict: StrictSimilarity);
151      var similarities = new double[trees.Length];
152      for (int i = 0; i < trees.Length; ++i) {
153        for (int j = 0; j < trees.Length; ++j) {
154          if (i != j) {
155            similarities[i] += similarityMatrix[i, j];
156          }
157        }
158        similarities[i] /= (trees.Length - 1);
159      }
160
161      var v = 1 - w;
162
163      var maximization = MaximizationParameter.ActualValue.Value;
164      var diversities = new ItemArray<DoubleValue>(trees.Length);
165      for (int i = 0; i < trees.Length; ++i) {
166        var q = qualities[i].Value;
167        var d = 1 - similarities[i]; // average distance
168
169        // assuming both q and d are in the interval [0, 1]
170        var value = maximization
171            ? (v * q) + (w * d)
172            : (v * q) - (w * d);
173
174        diversities[i] = new DoubleValue(value);
175      }
176
177      Selector.QualityParameter.ActualName = "Diversity";
178      DiversityParameter.ActualValue = diversities;
179      ApplyInnerSelector(); // apply inner selector
180
181      return CurrentScope.SubScopes[1].SubScopes.ToArray();
182    }
183
184    private void ParameterizeSelector(ISingleObjectiveSelector selector) {
185      selector.CopySelected = new BoolValue(true); // must always be true
186      selector.MaximizationParameter.ActualName = MaximizationParameter.Name;
187      selector.QualityParameter.ActualName = QualityParameter.Name;
188
189      IStochasticOperator stoOp = (selector as IStochasticOperator);
190      if (stoOp != null) stoOp.RandomParameter.ActualName = RandomParameter.Name;
191    }
192
193    private void ApplyInnerSelector() {
194      // necessary for inner GenderSpecificSelector to execute all operations in OperationCollection
195      Stack<IOperation> executionStack = new Stack<IOperation>();
196      executionStack.Push(ExecutionContext.CreateChildOperation(Selector));
197      while (executionStack.Count > 0) {
198        CancellationToken.ThrowIfCancellationRequested();
199        IOperation next = executionStack.Pop();
200        if (next is OperationCollection) {
201          OperationCollection coll = (OperationCollection)next;
202          for (int i = coll.Count - 1; i >= 0; i--)
203            if (coll[i] != null) executionStack.Push(coll[i]);
204        } else if (next is IAtomicOperation) {
205          IAtomicOperation operation = (IAtomicOperation)next;
206          next = operation.Operator.Execute((IExecutionContext)operation, CancellationToken);
207          if (next != null) executionStack.Push(next);
208        }
209      }
210    }
211  }
212}
Note: See TracBrowser for help on using the repository browser.