source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs @ 14834

Last change on this file since 14834 was 14834, checked in by pkimmesw, 3 years ago

#2665 LexicaseSelector, Performance improvements, UI Fixes, Debugger only shows used stacks, fixed Debugger stepping, Added vector expressions, ERCOptions,

File size: 5.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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
22namespace HeuristicLab.Problems.ProgramSynthesis.Push.Selector {
23  using System;
24  using System.Collections.Generic;
25  using System.Linq;
26
27  using HeuristicLab.Common;
28  using HeuristicLab.Core;
29  using HeuristicLab.Data;
30  using HeuristicLab.Parameters;
31  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32  using HeuristicLab.Problems.ProgramSynthesis.Push.Extensions;
33  using HeuristicLab.Problems.ProgramSynthesis.Push.Problem;
34  using HeuristicLab.Selection;
35  using Random;
36
37  /// <summary>
38  /// A lexicase selection operator which considers all successful evaluated training cases for selection.
39  ///
40  /// ToDo: LexicaseSelector and ICaseSingleObjectiveSelector are ISingleObjectiveOperator, which contains Maximization and Qualities which is not needed
41  /// </summary>
42  [Item("LexicaseSelector", "A lexicase selection operator which considers all successful evaluated training cases for selection.")]
43  [StorableClass]
44  public sealed class LexicaseSelector : StochasticSingleObjectiveSelector, ICaseSingleObjectiveSelector {
45    public ILookupParameter<ItemArray<DoubleArray>> CaseQualitiesParameter
46    {
47      get { return (ILookupParameter<ItemArray<DoubleArray>>)Parameters[PushProblem.CaseQualitiesScopeParameterName]; }
48    }
49
50    [StorableConstructor]
51    private LexicaseSelector(bool deserializing) : base(deserializing) { }
52    private LexicaseSelector(LexicaseSelector original, Cloner cloner) : base(original, cloner) { }
53    public override IDeepCloneable Clone(Cloner cloner) {
54      return new LexicaseSelector(this, cloner);
55    }
56
57    public LexicaseSelector() {
58      this.Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>(
59        PushProblem.CaseQualitiesScopeParameterName,
60        "The quality of every single training case for each individual."));
61    }
62
63    protected override IScope[] Select(List<IScope> population) {
64      var count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
65      var copy = CopySelectedParameter.Value.Value;
66      var maximization = MaximizationParameter.ActualValue.Value;
67      var random = RandomParameter.ActualValue;
68      var selected = new IScope[count];
69      var caseQualities = CaseQualitiesParameter.ActualValue;
70      var repeats = Math.Ceiling(count / (double)population.Count);
71      var caseCount = caseQualities[0].Length;
72      var source = population.Select((x, i) => Tuple.Create(i, x));
73
74      for (var k = 0; k < repeats; k++) {
75        // The fitness cases are shuffled.
76        var fitnessCaseIndexes = Enumerable.Range(0, caseCount).Shuffle(random).ToArray();
77        var pool = source.ToList();
78        var countLimit = Math.Min(count - k * population.Count, population.Count);
79
80        for (var i = 0; i < countLimit; i++) {
81          var bestIndividuals = pool;
82
83          for (var j = 0; j < fitnessCaseIndexes.Length && bestIndividuals.Count > 1; j++)
84            bestIndividuals = GetBestIndividuals(maximization, caseQualities, bestIndividuals, fitnessCaseIndexes[j]);
85
86          /*  If only one individual remains, it is the chosen parent. If no more fitness cases are left, a parent is
87              chosen randomly from the remaining individuals */
88          var currentSelected = bestIndividuals.Count == 1 ? bestIndividuals[0] : bestIndividuals.Random(random);
89          selected[k * population.Count + i] = copy ? (IScope)currentSelected.Item2.Clone() : currentSelected.Item2;
90
91          pool.Remove(currentSelected);
92        }
93      }
94
95      return selected;
96    }
97
98    private static List<Tuple<int, IScope>> GetBestIndividuals(bool maximization, ItemArray<DoubleArray> caseQualities, List<Tuple<int, IScope>> bestIndividuals, int index) {
99      var bestFitness = maximization ? double.NegativeInfinity : double.PositiveInfinity;
100      var result = new List<Tuple<int, IScope>>();
101
102      for (var l = 0; l < bestIndividuals.Count; l++) {
103        var individual = bestIndividuals[l];
104        var caseQuality = caseQualities[individual.Item1][index];
105
106        if (bestFitness == caseQuality) {
107          result.Add(individual);
108        } else if (maximization && bestFitness < caseQuality ||
109                  !maximization && bestFitness > caseQuality) {
110          bestFitness = caseQuality;
111          result.Clear();
112          result.Add(individual);
113        }
114
115        bestIndividuals = result;
116      }
117
118      return bestIndividuals;
119    }
120  }
121}
Note: See TracBrowser for help on using the repository browser.