Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 15601 was 8172, checked in by gkronber, 12 years ago

#1797: adapted return type of ConstrainedValueParameter properties in FLA branch.

File size: 11.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Analysis.FitnessLandscape.DistanceCalculators;
5using HeuristicLab.Common;
6using HeuristicLab.Core;
7using HeuristicLab.Data;
8using HeuristicLab.Operators;
9using HeuristicLab.Optimization;
10using HeuristicLab.Parameters;
11using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
12using HeuristicLab.PluginInfrastructure;
13
14namespace HeuristicLab.Analysis.FitnessLandscape {
15  [Item("NeutralSelector", "A selection operator that explores neutral areas.")]
16  [StorableClass]
17  public class NeutralSelector : SingleSuccessorOperator, ISingleObjectiveSelector {
18
19    public override bool CanChangeName {
20      get { return false; }
21    }
22
23    #region Parameters
24    public ScopeParameter CurrentScopeParameter {
25      get { return (ScopeParameter)Parameters["CurrentScope"]; }
26    }
27    protected IValueParameter<BoolValue> CopySelectedParameter {
28      get { return (IValueParameter<BoolValue>)Parameters["CopySelected"]; }
29    }
30    public IValueLookupParameter<IntValue> NumberOfSelectedSubScopesParameter {
31      get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfSelectedSubScopes"]; }
32    }
33    public IValueLookupParameter<BoolValue> MaximizationParameter {
34      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
35    }
36    public ILookupParameter<ItemArray<DoubleValue>> QualityParameter {
37      get { return (ILookupParameter<ItemArray<DoubleValue>>)Parameters["Quality"]; }
38    }
39    public ScopePathLookupParameter<DoubleValue> BaseQualityParameter {
40      get { return (ScopePathLookupParameter<DoubleValue>)Parameters["BaseQuality"]; }
41    }
42    public ScopePathLookupParameter<IItem> BaseSolutionParameter {
43      get { return (ScopePathLookupParameter<IItem>)Parameters["BaseSolution"]; }
44    }
45    public ScopePathLookupParameter<IItem> StartingPointParameter {
46      get { return (ScopePathLookupParameter<IItem>)Parameters["StartingPoint"]; }
47    }
48    public ILookupParameter<ItemArray<IItem>> SolutionParameter {
49      get { return (ILookupParameter<ItemArray<IItem>>)Parameters["Solution"]; }
50    }
51    public IConstrainedValueParameter<IItemDistanceCalculator> SolutionDistanceCalculatorParameter {
52      get { return (IConstrainedValueParameter<IItemDistanceCalculator>)Parameters["SolutionDistanceCalculator"]; }
53    }
54    public ValueLookupParameter<DoubleValue> EpsilonParameter {
55      get { return (ValueLookupParameter<DoubleValue>)Parameters["Epsilon"]; }
56    }
57    public ILookupParameter<DoubleValue> CurrentFractionOfNeutralNeighborsParameter {
58      get { return (LookupParameter<DoubleValue>)Parameters["CurrentFractionOfNeutralNeighbors"]; }
59    }
60    public LookupParameter<DoubleValue> CurrentNeutralDistanceParameter {
61      get { return (LookupParameter<DoubleValue>)Parameters["CurrentNeutralDistance"]; }
62    }
63    public LookupParameter<IRandom> RandomParameter {
64      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
65    }
66    #endregion
67
68    #region Parameter Values
69    protected IScope CurrentScope {
70      get { return CurrentScopeParameter.ActualValue; }
71    }
72    public BoolValue CopySelected {
73      get { return CopySelectedParameter.Value; }
74      set { CopySelectedParameter.Value = value; }
75    }
76    protected double CurrentNeutralDistance {
77      set {
78        if (CurrentNeutralDistanceParameter.ActualValue == null)
79          CurrentNeutralDistanceParameter.ActualValue = new DoubleValue(value);
80        else
81          CurrentNeutralDistanceParameter.ActualValue.Value = value;
82      }
83
84    }
85    protected double CurrentFractionOfNeutralNeighbors {
86      get { return CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value; }
87      set {
88        if (CurrentFractionOfNeutralNeighborsParameter.ActualValue == null)
89          CurrentFractionOfNeutralNeighborsParameter.ActualValue = new DoubleValue(value);
90        else
91          CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value = value;
92      }
93    }
94    #endregion
95
96    #region Construction & Cloning
97    [StorableConstructor]
98    protected NeutralSelector(bool deserializing) : base(deserializing) { }
99    protected NeutralSelector(NeutralSelector original, Cloner cloner) : base(original, cloner) { }
100    public NeutralSelector() {
101      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope from which sub-scopes should be selected."));
102      Parameters.Add(new ValueParameter<BoolValue>("CopySelected", "True if the selected sub-scopes should be copied, otherwise false.", new BoolValue(true)));
103      Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfSelectedSubScopes", "The number of sub-scopes which should be selected."));
104      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the current problem is a maximization problem, otherwise false."));
105      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality value contained in each sub-scope which is used for selection."));
106      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."));
107      Parameters.Add(new ValueLookupParameter<DoubleValue>("Epsilon", "Maximum delta accepted as neutral mutation.", new DoubleValue(0)));
108      Parameters.Add(new ScopePathLookupParameter<IItem>("BaseSolution", "Previous solution in neutral walk."));
109      Parameters.Add(new ScopePathLookupParameter<IItem>("StartingPoint", "Starting point of neutral walk (broken by non neutral transition through fallback selector)"));
110      Parameters.Add(new ScopeTreeLookupParameter<IItem>("Solution", "Current solution"));
111      Parameters.Add(new ConstrainedValueParameter<IItemDistanceCalculator>("SolutionDistanceCalculator", "Operator to calculate distances between the base item and the current item."));
112      Parameters.Add(new LookupParameter<DoubleValue>("CurrentNeutralDistance", "The distance of the current item to the starting point of the neutral (portion of the) walk."));
113      Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The fraction of examined neighbors that have the same fitness value (within epsilon)"));
114      Parameters.Add(new LookupParameter<IRandom>("Random", "Random number generator for breaking ties in the ordering."));
115      CopySelectedParameter.Hidden = true;
116      MaximizationParameter.Hidden = true;
117      NumberOfSelectedSubScopesParameter.Hidden = true;
118      BaseQualityParameter.Hidden = false;
119      QualityParameter.Hidden = false;
120      BaseSolutionParameter.Hidden = false;
121      StartingPointParameter.Hidden = true;
122      SolutionParameter.Hidden = false;
123      SolutionDistanceCalculatorParameter.Hidden = false;
124      StartingPointParameter.Hidden = false;
125      BaseQualityParameter.ActualName = "Quality";
126      BaseSolutionParameter.Path = "../Remaining/{0}";
127      BaseQualityParameter.Path = "../Remaining/{0}";
128      StartingPointParameter.Path = "..";
129      foreach (var v in ApplicationManager.Manager.GetInstances<IItemDistanceCalculator>())
130        SolutionDistanceCalculatorParameter.ValidValues.Add(v);
131    }
132    public override IDeepCloneable Clone(Cloner cloner) {
133      return new NeutralSelector(this, cloner);
134    }
135    [StorableHook(HookType.AfterDeserialization)]
136    private void AfterDeserialization() {
137      if (!Parameters.ContainsKey("CurrentFractionOfNeutralNeighbors"))
138        Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The fraction of examined neighbors that have the same fitness (within epsilon)"));
139    }
140    #endregion
141
142    private static double Squash(double d, double eps) {
143      return d <= eps ? 0 : d;
144    }
145
146    public sealed override IOperation Apply() {
147      var calc = (IItemDistanceCalculator)SolutionDistanceCalculatorParameter.ActualValue;
148      var baseQuality = BaseQualityParameter.ActualValue.Value;
149      var startingPoint = StartingPointParameter.ActualValue;
150      var baseSolution = BaseSolutionParameter.ActualValue;
151      var items = SolutionParameter.ActualValue;
152      var eps = EpsilonParameter.ActualValue.Value;
153      var random = RandomParameter.ActualValue;
154      double currentNeutralDistance;
155
156      if (startingPoint == null) {
157        currentNeutralDistance = 0;
158        CurrentNeutralDistance = 0;
159        startingPoint = baseSolution;
160        StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
161      } else {
162        currentNeutralDistance = calc.Distance(startingPoint, baseSolution);
163      }
164
165      var neighbors = QualityParameter.ActualValue
166        .Zip(items, (q, i) => new { Quality = q.Value, Item = i })
167        .Select((p, i) => new {
168          Idx = i,
169          Diff = Squash(Math.Abs(baseQuality - p.Quality), eps),
170          StartDist = calc.Distance(startingPoint, p.Item),
171          BaseDist = calc.Distance(baseSolution, p.Item)
172        })
173        .Where(n => n.BaseDist > 0)
174        .ToList();
175      if (neighbors.Count > 0) {
176        if (random != null)
177          neighbors.Shuffle(random);
178        var mostDistantNeutralNeighbor =
179          neighbors.Where(n => n.Diff == 0).OrderByDescending(n => n.StartDist).FirstOrDefault();
180        if (mostDistantNeutralNeighbor != null && mostDistantNeutralNeighbor.StartDist > currentNeutralDistance) {
181          if (currentNeutralDistance == 0) {
182            StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
183            CurrentNeutralDistance = mostDistantNeutralNeighbor.BaseDist;
184          } else {
185            CurrentNeutralDistance = mostDistantNeutralNeighbor.StartDist;
186          }
187          Select(mostDistantNeutralNeighbor.Idx);
188        } else {
189          var mostDistantNonNeutralNeighbor = neighbors.Where(n => n.Diff > 0).OrderByDescending(n => n.StartDist).FirstOrDefault();
190          if (mostDistantNonNeutralNeighbor != null) {
191            Select(mostDistantNonNeutralNeighbor.Idx);
192          } else {
193            var mostDistantNeighbor = neighbors.OrderByDescending(n => n.StartDist).FirstOrDefault();
194            Select(mostDistantNeighbor.Idx);
195          }
196          if (currentNeutralDistance > 0)
197            StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
198          CurrentNeutralDistance = 0;
199        }
200        CurrentFractionOfNeutralNeighbors = 1.0 * neighbors.Count(n => n.Diff == 0) / neighbors.Count;
201      }
202      return base.Apply();
203    }
204
205    private void Select(int i) {
206      List<IScope> scopes = new List<IScope>(CurrentScope.SubScopes);
207      bool copy = CopySelectedParameter.Value.Value;
208      bool maximization = MaximizationParameter.ActualValue.Value;
209      IScope[] selected = new IScope[1];
210      if (copy) {
211        selected[0] = (IScope)scopes[i].Clone();
212      } else {
213        selected[0] = scopes[i];
214        scopes[i] = null;
215        scopes.RemoveAll(x => x == null);
216      }
217      CurrentScope.SubScopes.Clear();
218      IScope remainingScope = new Scope("Remaining");
219      remainingScope.SubScopes.AddRange(scopes);
220      CurrentScope.SubScopes.Add(remainingScope);
221      IScope selectedScope = new Scope("Selected");
222      selectedScope.SubScopes.AddRange(selected);
223      CurrentScope.SubScopes.Add(selectedScope);
224    }
225  }
226}
Note: See TracBrowser for help on using the repository browser.