#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 . */ #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; /// /// A lexicase selection operator which considers all successful evaluated training cases for selection. /// /// ToDo: LexicaseSelector and ICaseSingleObjectiveSelector are ISingleObjectiveOperator, which contains Maximization and Qualities which is not needed /// [Item("LexicaseSelector", "A lexicase selection operator which considers all successful evaluated training cases for selection.")] [StorableClass] public sealed class LexicaseSelector : StochasticSingleObjectiveSelector, ICaseSingleObjectiveSelector { public ILookupParameter> CaseQualitiesParameter { get { return (ILookupParameter>)Parameters[PushProblem.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() { this.Parameters.Add(new ScopeTreeLookupParameter( PushProblem.CaseQualitiesScopeParameterName, "The quality of every single training case for each individual.")); } protected override IScope[] Select(List population) { var count = NumberOfSelectedSubScopesParameter.ActualValue.Value; var copy = CopySelectedParameter.Value.Value; var maximization = MaximizationParameter.ActualValue.Value; var random = RandomParameter.ActualValue; var selected = new IScope[count]; var caseQualities = CaseQualitiesParameter.ActualValue; var repeats = Math.Ceiling(count / (double)population.Count); var caseCount = caseQualities[0].Length; var source = population.Select((x, i) => Tuple.Create(i, x)); for (var k = 0; k < repeats; k++) { // The fitness cases are shuffled. var fitnessCaseIndexes = Enumerable.Range(0, caseCount).Shuffle(random).ToArray(); var pool = source.ToList(); var countLimit = Math.Min(count - k * population.Count, population.Count); for (var i = 0; i < countLimit; i++) { var bestIndividuals = pool; for (var j = 0; j < fitnessCaseIndexes.Length && bestIndividuals.Count > 1; j++) bestIndividuals = GetBestIndividuals(maximization, caseQualities, bestIndividuals, 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 currentSelected = bestIndividuals.Count == 1 ? bestIndividuals[0] : bestIndividuals.Random(random); selected[k * population.Count + i] = copy ? (IScope)currentSelected.Item2.Clone() : currentSelected.Item2; pool.Remove(currentSelected); } } return selected; } private static List> GetBestIndividuals(bool maximization, ItemArray caseQualities, List> bestIndividuals, int index) { var bestFitness = maximization ? double.NegativeInfinity : double.PositiveInfinity; var result = new List>(); for (var l = 0; l < bestIndividuals.Count; l++) { var individual = bestIndividuals[l]; var caseQuality = caseQualities[individual.Item1][index]; if (bestFitness == caseQuality) { result.Add(individual); } else if (maximization && bestFitness < caseQuality || !maximization && bestFitness > caseQuality) { bestFitness = caseQuality; result.Clear(); result.Add(individual); } bestIndividuals = result; } return bestIndividuals; } } }