Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2389-EpsLexicase/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/SingleObjective/EpsLexicaseSelection.cs @ 15946

Last change on this file since 15946 was 15946, checked in by gkronber, 6 years ago

#2389: added prototype implementation of semi-dynamic eps-lexicase selection

File size: 8.0 KB
RevLine 
[15946]1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.DataAnalysis;
32using HeuristicLab.Random;
33using HeuristicLab.Selection;
34
35namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Regression {
36  /// <summary>
37  /// eps-Lexicase Selection
38  /// </summary>
39  [Item("EpsLexicaseSelection", "")]
40  [StorableClass]
41  public sealed class EpsLexicaseSelection : StochasticSingleObjectiveSelector, ISingleObjectiveSelector {
42
43    [StorableConstructor]
44    private EpsLexicaseSelection(bool deserializing) : base(deserializing) { }
45    private EpsLexicaseSelection(EpsLexicaseSelection original, Cloner cloner) : base(original, cloner) { }
46    public override IDeepCloneable Clone(Cloner cloner) {
47      return new EpsLexicaseSelection(this, cloner);
48    }
49
50    public EpsLexicaseSelection()
51      : base() {
52      Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("Errors", 1));
53
54      var validPolicies = new ItemSet<StringValue>(new string[] { "ϵ_e", "ϵ_y", "ϵ_e,λ", "ϵ_y,λ" }.Select(s => new StringValue(s).AsReadOnly()));
55      Parameters.Add(new ConstrainedValueParameter<StringValue>("Policy", "The selection policy (see La Cava, Spector, Danai: eps-Lexicase Selection for Regression, GECCO 2016)", validPolicies));
56      Parameters.Add(new ValueParameter<DoubleValue>("ϵ", "The ϵ value for ϵ_e and ϵ_y policies", new DoubleValue(1.0)));
57      Parameters.Add(new LookupParameter<DoubleValue>("AvgConsideredTestCases", "The average number of considered test cases for selection."));
58    }
59
60    [StorableHook(HookType.AfterDeserialization)]
61    private void AfterDeserialization() {
62      // remove
63      if (!Parameters.ContainsKey("AvgConsideredTestCases")) {
64        Parameters.Add(new LookupParameter<DoubleValue>("AvgConsideredTestCases", "The average number of considered test cases for selection."));
65      }
66    }
67
68    protected override IScope[] Select(List<IScope> scopes) {
69      // NOT efficiently implemented, used only for exploration of diversity for a paper
70
71      int parentCount = NumberOfSelectedSubScopesParameter.ActualValue.Value;
72      bool copy = CopySelectedParameter.Value.Value;
73      if (!copy) throw new ArgumentException("copy is false in eps-lexicase selection.");
74      IRandom random = RandomParameter.ActualValue;
75      bool maximization = MaximizationParameter.ActualValue.Value;
76      IScope[] selected = new IScope[parentCount];
77
78      int nScopes = scopes.Count();
79      var errors = (ItemArray<DoubleArray>)((IScopeTreeLookupParameter)Parameters["Errors"]).ActualValue;
80      if (errors == null || !errors.Any())
81        throw new ArgumentException("Have not found errors of models. Have you used an analyzer that calculates the errors and stores them in the scope?");
82
83      var e = errors.Select(e_m => e_m.ToArray()).ToArray();
84      errors = null; // don't use errors
85
86
87      // see La Cava, Spector, Danai: eps-Lexicase Selection for Regression, GECCO 2016
88      var ts = Enumerable.Range(0, e.First().Length).ToArray();
89
90      double eps = ((DoubleValue)Parameters["ϵ"].ActualValue).Value;
91      var selectionPolicy = ((StringValue)Parameters["Policy"].ActualValue).Value;
92
93      var selectedScopes = new IScope[parentCount];
94      var nCasesList = new List<double>(parentCount);
95      var lambda_e = ts.Select(t=> MAD(e.Select(e_m => e_m[t]).ToArray())).ToArray(); 
96
97      for (int i = 0; i < parentCount; i++) {
98        int nCases;
99        var selectedIdx = SelectIdx(random, e, selectionPolicy, ts, eps, lambda_e, out nCases);
100        nCasesList.Add(nCases);
101        selectedScopes[i] = (IScope)(scopes[selectedIdx]).Clone();
102      }
103      Parameters["AvgConsideredTestCases"].ActualValue = new DoubleValue(nCasesList.Median());
104      return selectedScopes;
105    }
106
107    public static int SelectIdx(IRandom random, double[][] errors, string selectionPolicy, int[] ts, double eps, double[] lambda_e, out int nCases) {
108      ts.ShuffleInPlace(random);
109
110      var activeModelIdxs = new SortedSet<int>(Enumerable.Range(0, errors.Length));
111      nCases = 0;
112
113      foreach (var t in ts) {
114        if (activeModelIdxs.Count <= 1) break;
115        nCases++;
116
117        switch (selectionPolicy) {
118          case "ϵ_e": {
119              var bestError = errors.Select(err_m => err_m[t]).Min(); // as noted in corrected version of GECCO 2016 paper
120              activeModelIdxs.RemoveWhere(modelIdx => errors[modelIdx][t] > bestError * (1 + eps));
121              break;
122            }
123          case "ϵ_y": {
124              activeModelIdxs.RemoveWhere(modelIdx => errors[modelIdx][t] > eps);
125              break;
126            }
127          // Note in a corrected version of the GECCO Paper La Cava changed equations (2) and (5)
128          //    Equations 2 and 5 have been corrected to
129          //    indicate that the pass conditions for individuals in -lexicase
130          //    selection are defined relative to the best error in the population
131          //    on that training case, not in the selection pool.
132
133          // a more recent and detailed description of the algorithm is given in https://arxiv.org/pdf/1709.05394.pdf
134          // which indicates that semi-dynamic eps-lexicase performs best (Algorithm 4.2)
135          // -> we also implement semi-dynamic eps-lexicase which calculates lambda over the whole population
136
137          // I have not found a way to get reasonable convergence using MAD for lambda.
138          // If lambda_e[t] is zero this means that all models are effectively the same => select randomly.
139          // It seems that linear scaling (or the replacement of NaN outputs with the average of y)
140          // has the effect that MAD is zero (especially in the beginning), which means there is not selection pressure at the beginning.
141          //  Semi-dynamic -Lexicase Selection
142          case "ϵ_e,λ": {
143              var bestError = activeModelIdxs.Select(modelIdx => errors[modelIdx][t]).Min(); // See   https://arxiv.org/pdf/1709.05394.pdf Alg 4.2
144              activeModelIdxs.RemoveWhere(modelIdx => errors[modelIdx][t] > bestError + lambda_e[t]); // in the gecco paper the acceptance criterion is err < lambda_et this is later correct to err <= lambda_et
145              break;
146            }
147          case "ϵ_y,λ": {
148              activeModelIdxs.RemoveWhere(modelIdx => errors[modelIdx][t] > lambda_e[t]); // in the gecco paper the acceptance criterion is err < lambda_et this is later correct to err <= lambda_et
149              break;
150            }
151          default: throw new ArgumentException("unknown policy " + selectionPolicy);
152        }
153      }
154
155      if (!activeModelIdxs.Any())
156        throw new ArgumentException("nothing left in the pool");
157      else
158        return activeModelIdxs.SampleRandom(random, 1).First();
159    }
160
161    private static double MAD(double[] x) {
162      var median_x = x.Median();
163      return x.Select(xi => Math.Abs(xi - median_x)).Median();
164    }
165    private static double StdDev(double[] x) {
166      return x.StandardDeviation();
167    }
168  }
169}
Note: See TracBrowser for help on using the repository browser.