source: branches/ALPS/HeuristicLab.Algorithms.ALPS.SteadyState/3.3/AlpsSsMover.cs @ 12534

#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

using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;

namespace HeuristicLab.Algorithms.ALPS.SteadyState {
  [Item("AlpsSsMover", "")]
  [StorableClass]
  public class AlpsSsMover : SingleSuccessorOperator, IStochasticOperator {
    #region Parameter Properties
    private ILookupParameter<IntValue> LayerParameter {
      get { return (ILookupParameter<IntValue>)Parameters["Layer"]; }
    }
    private ILookupParameter<IntValue> TargetIndexParameter {
      get { return (ILookupParameter<IntValue>)Parameters["TargetIndex"]; }
    }
    private ILookupParameter<IntValue> LayerSizeParameter {
      get { return (ILookupParameter<IntValue>)Parameters["LayerSize"]; }
    }
    private ILookupParameter<IntValue> NumberOfLayersParameter {
      get { return (ILookupParameter<IntValue>)Parameters["NumberOfLayers"]; }
    }
    private ILookupParameter<IScope> WorkingScopeParameter {
      get { return (ILookupParameter<IScope>)Parameters["WorkingScope"]; }
    }
    private ILookupParameter<IScope> LayersScopeParameter {
      get { return (ILookupParameter<IScope>)Parameters["LayersScope"]; }
    }
    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    }
    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ValueLookupParameter<BoolValue> MaximizationParameter {
      get { return (ValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
    }
    public IScopeTreeLookupParameter<IntValue> EvalsCreatedParameter {
      get { return (IScopeTreeLookupParameter<IntValue>)Parameters["EvalsCreated"]; }
    }
    public IScopeTreeLookupParameter<IntValue> EvalsMovedQualityParameter {
      get { return (IScopeTreeLookupParameter<IntValue>)Parameters["EvalsMoved"]; }
    }
    private ILookupParameter<IntValue> EvaluatedSolutionsParameter {
      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
    }
    private ILookupParameter<IntArray> AgeLimitsParameter {
      get { return (ILookupParameter<IntArray>)Parameters["AgeLimits"]; }
    }
    private ILookupParameter<IntValue> ElitesParameter {
      get { return (ILookupParameter<IntValue>)Parameters["Elites"]; }
    }
    #endregion

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

    public AlpsSsMover()
      : base() {
      Parameters.Add(new LookupParameter<IntValue>("Layer"));
      Parameters.Add(new LookupParameter<IntValue>("TargetIndex"));
      Parameters.Add(new LookupParameter<IntValue>("LayerSize"));
      Parameters.Add(new LookupParameter<IntValue>("NumberOfLayers"));
      Parameters.Add(new LookupParameter<IScope>("WorkingScope"));
      Parameters.Add(new LookupParameter<IScope>("LayersScope"));
      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality"));
      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
      Parameters.Add(new ScopeTreeLookupParameter<IntValue>("EvalsCreated"));
      Parameters.Add(new ScopeTreeLookupParameter<IntValue>("EvalsMoved"));
      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions"));
      Parameters.Add(new LookupParameter<IntArray>("AgeLimits"));
      Parameters.Add(new LookupParameter<IntValue>("Elites"));
    }

    private int n;
    private int m;
    private int evals;
    private int popSize;
    private IScope layers;
    private IRandom rand;
    private string qualityVariableName;
    private IntArray ageLimits;
    private bool maximization;
    private int elites;
    public override IOperation Apply() {
      int i = LayerParameter.ActualValue.Value;
      int j = TargetIndexParameter.ActualValue.Value;
      n = NumberOfLayersParameter.ActualValue.Value;
      m = LayerSizeParameter.ActualValue.Value;
      evals = EvaluatedSolutionsParameter.ActualValue.Value;
      popSize = n * m;
      rand = RandomParameter.ActualValue;
      qualityVariableName = QualityParameter.TranslatedName;
      ageLimits = AgeLimitsParameter.ActualValue;
      maximization = MaximizationParameter.ActualValue.Value;
      elites = ElitesParameter.ActualValue.Value;

      layers = LayersScopeParameter.ActualValue;
      var newIndividual = (IScope)WorkingScopeParameter.ActualValue.Clone();
      newIndividual.Name = j.ToString();

      TryMoveUp(i, j);
      var currentLayer = layers.SubScopes[i];
      currentLayer.SubScopes[j] = newIndividual;

      return base.Apply();
    }
    private void TryMoveUp(int i, int j) {
      var currentLayer = layers.SubScopes[i];
      var currentIndividual = currentLayer.SubScopes[j];
      ((IntValue)currentIndividual.Variables["LastMove"].Value).Value = evals;

      if (i < n - 1) {
        var nextLayer = layers.SubScopes[i + 1];
        int? k = FindReplaceable(nextLayer, currentIndividual);

        if (k.HasValue) {
          TryMoveUp(i + 1, k.Value);
          nextLayer.SubScopes[k.Value] = currentIndividual;
        }
      }
    }
    private int? FindReplaceable(IScope layer, IScope replacingCandidate) {
      int layerNumber = ((IntValue)layer.Variables["Layer"].Value).Value;

      var individuals = (
        from individual in layer.SubScopes
        let quality = ((DoubleValue)individual.Variables[qualityVariableName].Value).Value
        let evalsCreated = ((IntValue)individual.Variables["EvalsCreated"].Value).Value
        let lastMove = ((IntValue)individual.Variables["LastMove"].Value).Value
        let age = (evals - evalsCreated) / popSize
        select new { individual, quality, age, lastMove }
        ).Select((x, index) => new { index, x.individual, x.quality, x.age, x.lastMove })
        .ToList();

      var ageLimit = layerNumber < n - 1 ? ageLimits[layerNumber] : int.MaxValue;

      // Individuals which are too old are first priority to be replaced
      var toOldIndividual = individuals.FirstOrDefault(x => x.age >= ageLimit);
      if (toOldIndividual != null)
        return toOldIndividual.index;

      double replacingCandidateQuality = ((DoubleValue)replacingCandidate.Variables[qualityVariableName].Value).Value;
      var worseIndividuals = individuals.Where(individual =>
            maximization
              ? individual.quality < replacingCandidateQuality
              : individual.quality > replacingCandidateQuality)
           .ToList();
      // Then take the worst individual where the last move happed m * n evaluations ago
      int lastMoveLimit = evals - m * n;
      var worstIndividual = worseIndividuals.LastOrDefault(individual => individual.lastMove < lastMoveLimit);
      if (worstIndividual != null)
        return worstIndividual.index;
      // If no individual moved n * m evaluations ago, take the worst
      worstIndividual = worseIndividuals.LastOrDefault();
      if (worstIndividual != null)
        return worstIndividual.index;

      // No individual found for replacement
      return null;
    }
  }
}