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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Selector {
  using System;
  using System.Collections.Generic;
  using System.Linq;

  using HeuristicLab.Common;
  using HeuristicLab.Core;
  using HeuristicLab.Data;
  using HeuristicLab.Parameters;
  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Extensions;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Problem;
  using HeuristicLab.Selection;
  using Random;

  /// <summary>
  /// A lexicase selection operator which considers all successful evaluated training cases for selection.
  /// </summary>
  [Item("LexicaseSelector", "A lexicase selection operator which considers all successful evaluated training cases for selection.")]
  [StorableClass]
  public sealed class LexicaseSelector : StochasticSingleObjectiveSelector, ICaseSingleObjectiveSelector {
    public ILookupParameter<ItemArray<DoubleArray>> CaseQualitiesParameter
    {
      get { return (ILookupParameter<ItemArray<DoubleArray>>)Parameters[IntegerVectorPushProblem.CaseQualitiesScopeParameterName]; }
    }

    [StorableConstructor]
    private LexicaseSelector(bool deserializing) : base(deserializing) { }
    private LexicaseSelector(LexicaseSelector original, Cloner cloner) : base(original, cloner) { }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new LexicaseSelector(this, cloner);
    }

    public LexicaseSelector() {
      Parameters.Add(new ScopeTreeLookupParameter<DoubleArray>(
        IntegerVectorPushProblem.CaseQualitiesScopeParameterName,
        "The quality of every single training case for each individual."));
    }

    protected override IScope[] Select(List<IScope> population) {
      var selected = Apply(
        population,
        NumberOfSelectedSubScopesParameter.ActualValue.Value,
        CopySelectedParameter.Value.Value,
        MaximizationParameter.ActualValue.Value,
        RandomParameter.ActualValue,
        CaseQualitiesParameter.ActualValue);

      return selected;
    }

    public static IScope[] Apply(
      List<IScope> population,
      int count,
      bool copy,
      bool maximization,
      IRandom random,
      ItemArray<DoubleArray> caseQualities) {
      var selected = new IScope[count];
      var repeats = (int)Math.Ceiling(count / (double)population.Count);
      var caseCount = caseQualities[0].Length;
      var source = Enumerable.Range(0, population.Count).ToList();

      for (var k = 0; k < repeats; k++) {
        // The fitness cases are shuffled.
        var fitnessCaseIndexes = Enumerable.Range(0, caseCount).Shuffle(random).ToList();

        // copy list if required
        var pool = repeats == 1 ? source : new List<int>(source);
        var countLimit = Math.Min(count - k * population.Count, population.Count);

        for (var i = 0; i < countLimit; i++) {
          var candidates = pool;

          for (var j = 0; j < fitnessCaseIndexes.Count && candidates.Count > 1; j++) {
            candidates = GetBestIndividuals(maximization, caseQualities, candidates, fitnessCaseIndexes[j]);
          }

          /*  If only one individual remains, it is the chosen parent. If no more fitness cases are left, a parent is
              chosen randomly from the remaining individuals */
          var bestIndividualIndex = candidates.Count == 1 ? candidates[0] : candidates.Random(random);
          var bestIndividual = population[bestIndividualIndex];

          selected[k * population.Count + i] = copy ? (IScope)bestIndividual.Clone() : bestIndividual;

          pool.Remove(bestIndividualIndex);
        }
      }

      return selected;
    }

    private static List<int> GetBestIndividuals(bool maximization, ItemArray<DoubleArray> caseQualities, List<int> bestIndividuals, int index) {
      var bestFitness = maximization ? double.NegativeInfinity : double.PositiveInfinity;
      var result = new List<int>();

      for (var l = 0; l < bestIndividuals.Count; l++) {
        var individual = bestIndividuals[l];
        var caseQuality = caseQualities[individual][index];

        if (bestFitness.IsAlmost(caseQuality)) {
          result.Add(individual);
        } else if (maximization && bestFitness < caseQuality ||
                  !maximization && bestFitness > caseQuality) {
          bestFitness = caseQuality;
          result.Clear();
          result.Add(individual);
        }

        bestIndividuals = result;
      }

      return bestIndividuals;
    }
  }
}