source: branches/LearningClassifierSystems/HeuristicLab.Optimization.Operators.LCS/3.3/Selection/NichingTournamentSelector.cs @ 13820

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 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

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.Selection;

namespace HeuristicLab.Optimization.Operators.LCS {
  [Item("NichingTournamentSelector", "Description missing")]
  [StorableClass]
  public class NichingTournamentSelector : StochasticSingleObjectiveSelector, INichingSingleObjectiveSelector, IHierarchicalSingleObjectiveSelector {

    #region Parameter Properties
    public ValueLookupParameter<IntValue> GroupSizeParameter {
      get { return (ValueLookupParameter<IntValue>)Parameters["GroupSize"]; }
    }
    public ILookupParameter<IGAssistProblemData> GAssistNichesProblemDataParameter {
      get { return (LookupParameter<IGAssistProblemData>)Parameters["GAssistNichesProblemData"]; }
    }
    public ILookupParameter<BoolValue> NichingParameter {
      get { return (LookupParameter<BoolValue>)Parameters["Niching"]; }
    }
    public IValueLookupParameter<IntValue> ParentsPerChildParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["ParentsPerChild"]; }
    }
    public ILookupParameter<ItemArray<IGAssistIndividual>> IndividualParameter {
      get { return (ILookupParameter<ItemArray<IGAssistIndividual>>)Parameters["Individual"]; }
    }
    public ILookupParameter<ItemArray<DoubleValue>> LengthParameter {
      get { return (ILookupParameter<ItemArray<DoubleValue>>)Parameters["Length"]; }
    }
    public IValueLookupParameter<DoubleValue> LengthThresholdParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters["LengthThreshold"]; }
    }
    public IValueLookupParameter<IntValue> IterationHirachicalSelectionParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["IterationHirachicalSelection"]; }
    }

    public ILookupParameter<IntValue> IterationsParameter {
      get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
    }
    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
    }
    #endregion

    [StorableConstructor]
    protected NichingTournamentSelector(bool deserializing) : base(deserializing) { }
    protected NichingTournamentSelector(NichingTournamentSelector original, Cloner cloner)
      : base(original, cloner) {
    }
    public NichingTournamentSelector()
      : base() {
      Parameters.Add(new ValueLookupParameter<IntValue>("GroupSize", "The size of the tournament group.", new IntValue(2)));
      Parameters.Add(new LookupParameter<IGAssistProblemData>("GAssistNichesProblemData", ""));
      Parameters.Add(new LookupParameter<BoolValue>("Niching", ""));
      Parameters.Add(new ValueLookupParameter<IntValue>("ParentsPerChild", ""));
      Parameters.Add(new ScopeTreeLookupParameter<IGAssistIndividual>("Individual", ""));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Length", "The length value contained in each sub-scope which is used for selection."));
      Parameters.Add(new ValueLookupParameter<DoubleValue>("LengthThreshold", "", new DoubleValue(0.000001)));
      Parameters.Add(new ValueLookupParameter<IntValue>("IterationHirachicalSelection", "", new IntValue(24)));
      Parameters.Add(new LookupParameter<IntValue>("Iterations", ""));
      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", ""));
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new NichingTournamentSelector(this, cloner);
    }

    protected override IScope[] Select(List<IScope> scopes) {
      int count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
      bool copy = CopySelectedParameter.Value.Value;
      IRandom random = RandomParameter.ActualValue;
      bool maximization = MaximizationParameter.ActualValue.Value;
      List<double> qualities = QualityParameter.ActualValue.Where(x => IsValidQuality(x.Value)).Select(x => x.Value).ToList();
      List<double> lengths = LengthParameter.ActualValue.Select(x => x.Value).ToList();
      bool useLength = lengths.Count > 0;
      double lengtThreshold = LengthThresholdParameter.ActualValue.Value;
      List<IGAssistIndividual> individuals = IndividualParameter.ActualValue.ToList();
      int groupSize = GroupSizeParameter.ActualValue.Value;
      IScope[] selected = new IScope[count];
      bool doNiching = NichingParameter.ActualValue.Value;

      //check if list with indexes is as long as the original scope list
      //otherwise invalid quality values were filtered
      if (qualities.Count != scopes.Count || individuals.Count != scopes.Count || (useLength && lengths.Count != scopes.Count)) {
        throw new ArgumentException("The scopes contain invalid quality values (either infinity or double.NaN) on which the selector cannot operate.");
      }

      int parentsPerChild = ParentsPerChildParameter.ActualValue.Value;

      if (individuals.Any(x => x.Niche == null) && individuals.Any(x => x.Niche != null)) {
        throw new ArgumentException("Either all individuals have a default action or none.");
      }

      //null cannot be a key in a dictionary (nicheScope), therefore torunament selection has to be done differently
      //to keep it a little maintainable, the case that no default rule is used has been separated
      if (individuals.Any(x => x.Niche == null)) {
        //normal tournament selection
        for (int i = 0; i < count; i++) {
          int best = random.Next(scopes.Count);
          int index;
          for (int j = 1; j < groupSize; j++) {
            index = random.Next(scopes.Count);
            if (IsBetterHirachical(index, best, qualities, lengths, lengtThreshold, useLength, maximization)) {
              best = index;
            }
          }

          if (copy)
            selected[i] = (IScope)scopes[best].Clone();
          else {
            selected[i] = scopes[best];
            scopes.RemoveAt(best);
            qualities.RemoveAt(best);
          }
        }
      } else {
        var nicheComparer = GAssistNichesProblemDataParameter.ActualValue.GetPossibleNiches().First().Comparer;
        var selectPerNiche = new Dictionary<IGAssistNiche, int>(nicheComparer);
        var nicheScope = new Dictionary<IGAssistNiche, List<int>>(nicheComparer);
        //niching tournament selection
        for (int i = 0; i < individuals.Count; i++) {
          if (!nicheScope.ContainsKey(individuals[i].Niche)) {
            nicheScope.Add(individuals[i].Niche, new List<int>());
          }
          nicheScope[individuals[i].Niche].Add(i);
        }

        var possibleNiches = nicheScope.Keys.ToList();
        foreach (var niche in possibleNiches) {
          selectPerNiche.Add(niche, count / possibleNiches.Count);
        }

        int curCount = 0;
        while (curCount < count) {
          IGAssistNiche niche = null;
          int best = -1;
          if (doNiching) {
            niche = GetNiche(random, selectPerNiche, possibleNiches);
          } else {
            best = random.Next(scopes.Count);
          }
          for (int i = 0; i < parentsPerChild; i++) {
            int index;
            if (doNiching) {
              best = nicheScope[niche][random.Next(nicheScope[niche].Count)];
            }
            for (int j = 1; j < groupSize; j++) {
              if (niche != null) {
                index = nicheScope[niche][random.Next(nicheScope[niche].Count)];
              } else {
                index = random.Next(scopes.Count);
              }
              if (IsBetterHirachical(index, best, qualities, lengths, lengtThreshold, useLength, maximization)) {
                best = index;
              }
            }

            niche = individuals[best].Niche;

            if (copy)
              selected[curCount] = (IScope)scopes[best].Clone();
            else {
              selected[curCount] = scopes[best];
              scopes.RemoveAt(best);
              qualities.RemoveAt(best);
            }
            selectPerNiche[niche]--;
            curCount++;
          }
        }
      }
      return selected;
    }

    private bool IsBetterHirachical(int indexTrue, int indexFalse, IList<double> qualities, IList<double> length, double hierarchicalThreshold, bool useLength, bool maximization) {
      if (useLength && IterationsParameter.ActualValue.Value >= IterationHirachicalSelectionParameter.ActualValue.Value
        && Math.Abs(qualities[indexTrue] - qualities[indexFalse]) <= hierarchicalThreshold
        && length[indexTrue] != length[indexFalse]) {
        return length[indexTrue] < length[indexFalse];
      }
      return IsBetter(indexTrue, indexFalse, qualities, maximization);
    }

    private bool IsBetter(int indexTrue, int indexFalse, IList<double> qualities, bool maximization) {
      return ((maximization) && (qualities[indexTrue] > qualities[indexFalse])) ||
             ((!maximization) && (qualities[indexTrue] < qualities[indexFalse]));
    }

    private IGAssistNiche GetNiche(IRandom random, Dictionary<IGAssistNiche, int> selectPerNiche, List<IGAssistNiche> possibleNiches) {
      int sum = selectPerNiche.Values.Sum();
      if (sum <= 0) { return possibleNiches[random.Next(possibleNiches.Count)]; }
      int pos = random.Next(sum);
      int total = 0;
      IGAssistNiche niche = selectPerNiche.Keys.First();
      foreach (var item in selectPerNiche) {
        total += item.Value;
        niche = item.Key;
        if (pos < total) {
          return niche;
        }
      }
      throw new ArgumentException("error in code");
    }
  }
}