source: branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/NeutralSelector.cs @ 12095

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Analysis.FitnessLandscape.DistanceCalculators;
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.PluginInfrastructure;

namespace HeuristicLab.Analysis.FitnessLandscape {
  [Item("NeutralSelector", "A selection operator that explores neutral areas.")]
  [StorableClass]
  public class NeutralSelector : SingleSuccessorOperator, ISingleObjectiveSelector {

    public override bool CanChangeName {
      get { return false; }
    }

    #region Parameters
    public ScopeParameter CurrentScopeParameter {
      get { return (ScopeParameter)Parameters["CurrentScope"]; }
    }
    protected IValueParameter<BoolValue> CopySelectedParameter {
      get { return (IValueParameter<BoolValue>)Parameters["CopySelected"]; }
    }
    public IValueLookupParameter<IntValue> NumberOfSelectedSubScopesParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfSelectedSubScopes"]; }
    }
    public IValueLookupParameter<BoolValue> MaximizationParameter {
      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
    }
    public ILookupParameter<ItemArray<DoubleValue>> QualityParameter {
      get { return (ILookupParameter<ItemArray<DoubleValue>>)Parameters["Quality"]; }
    }
    public ScopePathLookupParameter<DoubleValue> BaseQualityParameter {
      get { return (ScopePathLookupParameter<DoubleValue>)Parameters["BaseQuality"]; }
    }
    public ScopePathLookupParameter<IItem> BaseSolutionParameter {
      get { return (ScopePathLookupParameter<IItem>)Parameters["BaseSolution"]; }
    }
    public ScopePathLookupParameter<IItem> StartingPointParameter {
      get { return (ScopePathLookupParameter<IItem>)Parameters["StartingPoint"]; }
    }
    public ILookupParameter<ItemArray<IItem>> SolutionParameter {
      get { return (ILookupParameter<ItemArray<IItem>>)Parameters["Solution"]; }
    }
    public IConstrainedValueParameter<IItemDistanceCalculator> SolutionDistanceCalculatorParameter {
      get { return (IConstrainedValueParameter<IItemDistanceCalculator>)Parameters["SolutionDistanceCalculator"]; }
    }
    public ValueLookupParameter<DoubleValue> EpsilonParameter {
      get { return (ValueLookupParameter<DoubleValue>)Parameters["Epsilon"]; }
    }
    public ILookupParameter<DoubleValue> CurrentFractionOfNeutralNeighborsParameter {
      get { return (LookupParameter<DoubleValue>)Parameters["CurrentFractionOfNeutralNeighbors"]; }
    }
    public LookupParameter<DoubleValue> CurrentNeutralDistanceParameter {
      get { return (LookupParameter<DoubleValue>)Parameters["CurrentNeutralDistance"]; }
    }
    public LookupParameter<IRandom> RandomParameter {
      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    }
    #endregion

    #region Parameter Values
    protected IScope CurrentScope {
      get { return CurrentScopeParameter.ActualValue; }
    }
    public BoolValue CopySelected {
      get { return CopySelectedParameter.Value; }
      set { CopySelectedParameter.Value = value; }
    }
    protected double CurrentNeutralDistance {
      set {
        if (CurrentNeutralDistanceParameter.ActualValue == null)
          CurrentNeutralDistanceParameter.ActualValue = new DoubleValue(value);
        else
          CurrentNeutralDistanceParameter.ActualValue.Value = value;
      }

    }
    protected double CurrentFractionOfNeutralNeighbors {
      get { return CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value; }
      set {
        if (CurrentFractionOfNeutralNeighborsParameter.ActualValue == null)
          CurrentFractionOfNeutralNeighborsParameter.ActualValue = new DoubleValue(value);
        else
          CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value = value;
      }
    }
    #endregion

    #region Construction & Cloning
    [StorableConstructor]
    protected NeutralSelector(bool deserializing) : base(deserializing) { }
    protected NeutralSelector(NeutralSelector original, Cloner cloner) : base(original, cloner) { }
    public NeutralSelector() {
      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope from which sub-scopes should be selected."));
      Parameters.Add(new ValueParameter<BoolValue>("CopySelected", "True if the selected sub-scopes should be copied, otherwise false.", new BoolValue(true)));
      Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfSelectedSubScopes", "The number of sub-scopes which should be selected."));
      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the current problem is a maximization problem, otherwise false."));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality value contained in each sub-scope which is used for selection."));
      Parameters.Add(new ScopePathLookupParameter<DoubleValue>("BaseQuality", "The base quality value to compare to. This is required to determine wheter a local optimum has been found and the direction should be reversed."));
      Parameters.Add(new ValueLookupParameter<DoubleValue>("Epsilon", "Maximum delta accepted as neutral mutation.", new DoubleValue(0)));
      Parameters.Add(new ScopePathLookupParameter<IItem>("BaseSolution", "Previous solution in neutral walk."));
      Parameters.Add(new ScopePathLookupParameter<IItem>("StartingPoint", "Starting point of neutral walk (broken by non neutral transition through fallback selector)"));
      Parameters.Add(new ScopeTreeLookupParameter<IItem>("Solution", "Current solution"));
      Parameters.Add(new ConstrainedValueParameter<IItemDistanceCalculator>("SolutionDistanceCalculator", "Operator to calculate distances between the base item and the current item."));
      Parameters.Add(new LookupParameter<DoubleValue>("CurrentNeutralDistance", "The distance of the current item to the starting point of the neutral (portion of the) walk."));
      Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The fraction of examined neighbors that have the same fitness value (within epsilon)"));
      Parameters.Add(new LookupParameter<IRandom>("Random", "Random number generator for breaking ties in the ordering."));
      CopySelectedParameter.Hidden = true;
      MaximizationParameter.Hidden = true;
      NumberOfSelectedSubScopesParameter.Hidden = true;
      BaseQualityParameter.Hidden = false;
      QualityParameter.Hidden = false;
      BaseSolutionParameter.Hidden = false;
      StartingPointParameter.Hidden = true;
      SolutionParameter.Hidden = false;
      SolutionDistanceCalculatorParameter.Hidden = false;
      StartingPointParameter.Hidden = false;
      BaseQualityParameter.ActualName = "Quality";
      BaseSolutionParameter.Path = "../Remaining/{0}";
      BaseQualityParameter.Path = "../Remaining/{0}";
      StartingPointParameter.Path = "..";
      foreach (var v in ApplicationManager.Manager.GetInstances<IItemDistanceCalculator>())
        SolutionDistanceCalculatorParameter.ValidValues.Add(v);
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new NeutralSelector(this, cloner);
    }
    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (!Parameters.ContainsKey("CurrentFractionOfNeutralNeighbors"))
        Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The fraction of examined neighbors that have the same fitness (within epsilon)"));
    }
    #endregion

    private static double Squash(double d, double eps) {
      return d <= eps ? 0 : d;
    }

    public sealed override IOperation Apply() {
      var calc = (IItemDistanceCalculator)SolutionDistanceCalculatorParameter.ActualValue;
      var baseQuality = BaseQualityParameter.ActualValue.Value;
      var startingPoint = StartingPointParameter.ActualValue;
      var baseSolution = BaseSolutionParameter.ActualValue;
      var items = SolutionParameter.ActualValue;
      var eps = EpsilonParameter.ActualValue.Value;
      var random = RandomParameter.ActualValue;
      double currentNeutralDistance;

      if (startingPoint == null) {
        currentNeutralDistance = 0;
        CurrentNeutralDistance = 0;
        startingPoint = baseSolution;
        StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
      } else {
        currentNeutralDistance = calc.Distance(startingPoint, baseSolution);
      }

      var neighbors = QualityParameter.ActualValue
        .Zip(items, (q, i) => new { Quality = q.Value, Item = i })
        .Select((p, i) => new {
          Idx = i,
          Diff = Squash(Math.Abs(baseQuality - p.Quality), eps),
          StartDist = calc.Distance(startingPoint, p.Item),
          BaseDist = calc.Distance(baseSolution, p.Item)
        })
        .Where(n => n.BaseDist > 0)
        .ToList();
      if (neighbors.Count > 0) {
        if (random != null)
          neighbors.Shuffle(random);
        var mostDistantNeutralNeighbor =
          neighbors.Where(n => n.Diff == 0).OrderByDescending(n => n.StartDist).FirstOrDefault();
        if (mostDistantNeutralNeighbor != null && mostDistantNeutralNeighbor.StartDist > currentNeutralDistance) {
          if (currentNeutralDistance == 0) {
            StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
            CurrentNeutralDistance = mostDistantNeutralNeighbor.BaseDist;
          } else {
            CurrentNeutralDistance = mostDistantNeutralNeighbor.StartDist;
          }
          Select(mostDistantNeutralNeighbor.Idx);
        } else {
          var mostDistantNonNeutralNeighbor = neighbors.Where(n => n.Diff > 0).OrderByDescending(n => n.StartDist).FirstOrDefault();
          if (mostDistantNonNeutralNeighbor != null) {
            Select(mostDistantNonNeutralNeighbor.Idx);
          } else {
            var mostDistantNeighbor = neighbors.OrderByDescending(n => n.StartDist).FirstOrDefault();
            Select(mostDistantNeighbor.Idx);
          }
          if (currentNeutralDistance > 0)
            StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
          CurrentNeutralDistance = 0;
        }
        CurrentFractionOfNeutralNeighbors = 1.0 * neighbors.Count(n => n.Diff == 0) / neighbors.Count;
      }
      return base.Apply();
    }

    private void Select(int i) {
      List<IScope> scopes = new List<IScope>(CurrentScope.SubScopes);
      bool copy = CopySelectedParameter.Value.Value;
      bool maximization = MaximizationParameter.ActualValue.Value;
      IScope[] selected = new IScope[1];
      if (copy) {
        selected[0] = (IScope)scopes[i].Clone();
      } else {
        selected[0] = scopes[i];
        scopes[i] = null;
        scopes.RemoveAll(x => x == null);
      }
      CurrentScope.SubScopes.Clear();
      IScope remainingScope = new Scope("Remaining");
      remainingScope.SubScopes.AddRange(scopes);
      CurrentScope.SubScopes.Add(remainingScope);
      IScope selectedScope = new Scope("Selected");
      selectedScope.SubScopes.AddRange(selected);
      CurrentScope.SubScopes.Add(selectedScope);
    }
  }
}