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

using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Selection;
using HeuristicLab.PluginInfrastructure;
using HeuristicLab.Operators;
using System;
using HeuristicLab.Analysis.FitnessLandscape.DistanceCalculators;

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 ConstrainedValueParameter<IItemDistanceCalculator> SolutionDistanceCalculatorParameter {
      get { return (ConstrainedValueParameter<IItemDistanceCalculator>)Parameters["SolutionDistanceCalculator"]; }
    }
    public ValueLookupParameter<DoubleValue> EpsilonParameter {
      get { return (ValueLookupParameter<DoubleValue>)Parameters["Epsilon"]; }
    }
    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; }
    }
    #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<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);
    }
    #endregion

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

    public sealed override IOperation Apply() {
      IItemDistanceCalculator calc = (IItemDistanceCalculator)SolutionDistanceCalculatorParameter.ActualValue;
      double baseQuality = BaseQualityParameter.ActualValue.Value;
      IItem startingPoint = StartingPointParameter.ActualValue;
      IItem baseSolution = BaseSolutionParameter.ActualValue;
      ItemArray<IItem> items = SolutionParameter.ActualValue;
      double eps = EpsilonParameter.ActualValue.Value;
      IRandom random = RandomParameter.ActualValue;
      double baseDistance = 0;
      if (startingPoint != null) {
        baseDistance = calc.Distance(baseSolution, startingPoint);
        baseSolution = startingPoint;
      }

      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),
          Dist=calc.Distance(baseSolution, p.Item)
        })        
        .ToList();
      if (random != null)
        neighbors.Shuffle(random);
      var mostDistantNeutralNeighbor = neighbors.Where(n => n.Diff == 0).OrderByDescending(n => n.Dist).FirstOrDefault();
      if (mostDistantNeutralNeighbor != null && mostDistantNeutralNeighbor.Dist > baseDistance) {
        Select(mostDistantNeutralNeighbor.Idx);
        if (startingPoint == null)
          StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
        CurrentNeutralDistanceParameter.ActualValue = new DoubleValue(mostDistantNeutralNeighbor.Dist);
      } else {
        var mostDistantNeighbor = neighbors.OrderByDescending(n => n.Dist).FirstOrDefault();
        Select(mostDistantNeighbor.Idx);
        StartingPointParameter.ActualValue = (IItem)items[mostDistantNeighbor.Idx].Clone();
        CurrentNeutralDistanceParameter.ActualValue = new DoubleValue(0);
      }
      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);
    }
  }
}