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

#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 {

    #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"]; }
    }
    #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", ""));
    }
    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<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) {
        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;
      var nicheComparer = GAssistNichesProblemDataParameter.ActualValue.GetPossibleNiches().First().Comparer;
      var selectPerNiche = new Dictionary<IGAssistNiche, int>(nicheComparer);
      var nicheScope = new Dictionary<IGAssistNiche, List<int>>(nicheComparer);

      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 (((maximization) && (qualities[index] > qualities[best])) ||
                ((!maximization) && (qualities[index] < qualities[best]))) {
              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 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");
    }
  }
}