Ignore:
Timestamp:
04/10/17 00:27:31 (2 years ago)
Author:
pkimmesw
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs

    r14778 r14834  
    2020#endregion
    2121
    22 using System;
    23 using System.Collections.Generic;
    24 using System.Linq;
    25 using HeuristicLab.Common;
    26 using HeuristicLab.Core;
    27 using HeuristicLab.Data;
    28 using HeuristicLab.Parameters;
    29 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    30 using HeuristicLab.Random;
    31 using HeuristicLab.Selection;
     22namespace HeuristicLab.Problems.ProgramSynthesis.Push.Selector {
     23  using System;
     24  using System.Collections.Generic;
     25  using System.Linq;
    3226
    33 namespace HeuristicLab.Misc {
    34   using HeuristicLab.Problems.ProgramSynthesis.Push.Selector;
     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;
    3536
    3637  /// <summary>
     
    4445    public ILookupParameter<ItemArray<DoubleArray>> CaseQualitiesParameter
    4546    {
    46       get { return (ILookupParameter<ItemArray<DoubleArray>>)Parameters["CaseQualities"]; }
     47      get { return (ILookupParameter<ItemArray<DoubleArray>>)Parameters[PushProblem.CaseQualitiesScopeParameterName]; }
    4748    }
    4849
     
    5455    }
    5556
    56     public LexicaseSelector()
    57       : base() {
    58       Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>("CaseQualities", "The quality of every single training case for each individual."));
     57    public LexicaseSelector() {
     58      this.Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>(
     59        PushProblem.CaseQualitiesScopeParameterName,
     60        "The quality of every single training case for each individual."));
    5961    }
    6062
    61     protected override IScope[] Select(List<IScope> scopes) {
    62       int count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
    63       bool copy = CopySelectedParameter.Value.Value;
    64       IRandom random = RandomParameter.ActualValue;
    65       bool maximization = MaximizationParameter.ActualValue.Value;
    66       List<double> qualities = QualityParameter.ActualValue.Where(x => IsValidQuality(x.Value)).Select(x => x.Value).ToList();
    67       List<DoubleArray> caseQualities = CaseQualitiesParameter.ActualValue.ToList();
     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));
    6873
    69       // remove scopes, qualities and case qualities, if the case qualities are empty
    70       var removeindices = Enumerable.Range(0, caseQualities.Count)
    71                                     .Zip(caseQualities, (i, c) => new { Index = i, CaseQuality = c })
    72                                     .Where(c => c.CaseQuality.Count() == 0)
    73                                     .Select(c => c.Index)
    74                                     .Reverse();
    75       foreach (var i in removeindices) {
    76         scopes.RemoveAt(i);
    77         qualities.RemoveAt(i);
    78         caseQualities.RemoveAt(i);
     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        }
    7993      }
    8094
    81       if (caseQualities.Any(x => x.Count() != caseQualities[0].Length)) { throw new ArgumentException("Not all case qualities have the same length"); }
    82 
    83       IScope[] selected = new IScope[count];
    84 
    85       for (int i = 0; i < count; i++) {
    86         int index = LexicaseSelect(caseQualities, RandomParameter.ActualValue, maximization);
    87 
    88         if (copy)
    89           selected[i] = (IScope)scopes[index].Clone();
    90         else {
    91           selected[i] = scopes[index];
    92           scopes.RemoveAt(index);
    93           qualities.RemoveAt(index);
    94           caseQualities.RemoveAt(index);
    95         }
    96       }
    9795      return selected;
    9896    }
    9997
    100     private int LexicaseSelect(List<DoubleArray> caseQualities, IRandom random, bool maximization) {
    101       IList<int> candidates = Enumerable.Range(0, caseQualities.Count()).ToList();
    102       IEnumerable<int> order = Enumerable.Range(0, caseQualities[0].Count()).Shuffle(random);
     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>>();
    103101
    104       foreach (int curCase in order) {
    105         List<int> nextCandidates = new List<int>();
    106         double best = maximization ? double.NegativeInfinity : double.PositiveInfinity;
    107         foreach (int candidate in candidates) {
    108           if (caseQualities[candidate][curCase].IsAlmost(best)) {
    109             // if the individuals is as good as the best one, add it
    110             nextCandidates.Add(candidate);
    111           } else if (((maximization) && (caseQualities[candidate][curCase] > best)) ||
    112              ((!maximization) && (caseQualities[candidate][curCase] < best))) {
    113             // if the individuals is better than the best one, remove all previous candidates and add the new one
    114             nextCandidates.Clear();
    115             nextCandidates.Add(candidate);
    116             // also set the nes best quality value
    117             best = caseQualities[candidate][curCase];
    118           }
    119           // else {do nothing}
     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);
    120113        }
    121114
    122         if (nextCandidates.Count == 1) {
    123           return nextCandidates.First();
    124         } else if (nextCandidates.Count < 1) {
    125           return candidates.SampleRandom(random);
    126         }
    127         candidates = nextCandidates;
     115        bestIndividuals = result;
    128116      }
    129117
    130 
    131       if (candidates.Count == 1) {
    132         return candidates.First();
    133       }
    134       return candidates.SampleRandom(random);
     118      return bestIndividuals;
    135119    }
    136120  }
Note: See TracChangeset for help on using the changeset viewer.