Changeset 7783


Ignore:
Timestamp:
05/07/12 15:14:47 (7 years ago)
Author:
epitzer
Message:

#1696 add neutrality breadth analysis by including and analyzing the number of possible neutral neighbors both overall and inside neutral areas

Location:
branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/Analysis/NeutralityAnalyzer.cs

    r7176 r7783  
    4848      get { return (LookupParameter<DoubleValue>)Parameters["CurrentNeutralDistance"]; }
    4949    }
     50    public LookupParameter<DoubleValue> CurrentFractionOfNeutralNeighborsParameter {
     51      get { return (LookupParameter<DoubleValue>)Parameters["CurrentFractionOfNeutralNeighbors"]; }
     52    }
    5053    public LookupParameter<DataTable> NeutralWalkDistancesTableParameter {
    5154      get { return (LookupParameter<DataTable>)Parameters["NeutralWalkDistancesTable"]; }
     
    5760      get { return (LookupParameter<DoubleValue>)Parameters["AverageNeutralWalkDistance"]; }
    5861    }
     62    public LookupParameter<DoubleValue> AverageNeutralNeighborFractionParameter {
     63      get { return (LookupParameter<DoubleValue>)Parameters["AverageNeutralNeighborFraction"]; }
     64    }
     65    public LookupParameter<DoubleValue> AverageInnerNeutralNeighborFractionParameter {
     66      get { return (LookupParameter<DoubleValue>)Parameters["AverageInnerNeutralNeighborFraction"]; }
     67    }
    5968    public LookupParameter<DoubleValue> NeutralWalkLengthVarianceParameter {
    6069      get { return (LookupParameter<DoubleValue>)Parameters["NeutralWalkLengthVariance"]; }
     
    6372      get { return (LookupParameter<DoubleValue>)Parameters["NeutralWalkDistanceVariance"]; }
    6473    }       
     74    public LookupParameter<DoubleValue> NeutralNeighborFractionVarianceParameter {
     75      get { return (LookupParameter<DoubleValue>)Parameters["NeutralNeighborFractionVariance"]; }
     76    }
     77    public LookupParameter<DoubleValue> InnerNeutralNeighborFractionVarianceParameter {
     78      get { return (LookupParameter<DoubleValue>)Parameters["InnerNeutralNeighborFractionVariance"]; }
     79    }
    6580    public LookupParameter<VariableCollection> ResultsParameter {
    6681      get { return (LookupParameter<VariableCollection>)Parameters["Results"]; }
     
    7590      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The current quality"));
    7691      Parameters.Add(new LookupParameter<DoubleValue>("CurrentNeutralDistance", "The distance of the current solution to the starting point of the neutral (portion of the) walk."));
     92      Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The current fraction of neighbors with the same fitness (within epsilon)"));
    7793      Parameters.Add(new LookupParameter<DataTable>("NeutralWalkDistancesTable", "The historical values of the current neutral distance."));
    7894      Parameters.Add(new LookupParameter<DoubleValue>("AverageNeutralWalkLength", "The average length of a neutral walk"));
    7995      Parameters.Add(new LookupParameter<DoubleValue>("AverageNeutralWalkDistance", "The average distance of the neutral walk to the starting point."));
     96      Parameters.Add(new LookupParameter<DoubleValue>("AverageNeutralNeighborFraction", "The average fraction of neutral neighbors overall."));
     97      Parameters.Add(new LookupParameter<DoubleValue>("AverageInnerNeutralNeighborFraction", "The average fraction of neutral neighbors within a neutral area."));
    8098      Parameters.Add(new LookupParameter<DoubleValue>("NeutralWalkLengthVariance", "The variance of the neutral walks lengths"));
    8199      Parameters.Add(new LookupParameter<DoubleValue>("NeutralWalkDistanceVariance", "The varaince of the neutral walks distances"));
     100      Parameters.Add(new LookupParameter<DoubleValue>("NeutralNeighborFractionVariance", "The average fraction of neutral neighbors overall."));
     101      Parameters.Add(new LookupParameter<DoubleValue>("InnerNeutralNeighborFractionVariance", "The average fraction of neutral neighbors within a neutral area."));
    82102
    83103      var resultsCollector = new ResultsCollector();
    84104      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(CurrentNeutralDistanceParameter.ActualName));
     105      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(CurrentFractionOfNeutralNeighborsParameter.ActualName));
    85106      resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>(NeutralWalkDistancesTableParameter.Name));
    86107      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(AverageNeutralWalkLengthParameter.Name));
    87108      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(AverageNeutralWalkDistanceParameter.Name));
     109      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(AverageNeutralNeighborFractionParameter.Name));
     110      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(AverageInnerNeutralNeighborFractionParameter.Name));
    88111      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(NeutralWalkLengthVarianceParameter.Name));
    89112      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(NeutralWalkDistanceVarianceParameter.Name));
     113      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(NeutralNeighborFractionVarianceParameter.Name));
     114      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>(InnerNeutralNeighborFractionVarianceParameter.Name));
    90115
    91116      OperatorGraph.InitialOperator = resultsCollector;
     
    99124    public override IOperation Apply() {
    100125      DataTable distanceTable = GetOrCreateDistanceTable();
    101       var values = distanceTable.Rows["Neutral Walk Distances"].Values;
    102       values.Add(CurrentNeutralDistanceParameter.ActualValue == null ? 0 : CurrentNeutralDistanceParameter.ActualValue.Value);
    103       List<double> lenghts = new List<double>();
    104       List<double> distances = new List<double>();
     126      var distanceValues = distanceTable.Rows["Neutral Walk Distances"].Values;
     127      var fractionValues = distanceTable.Rows["Neutral Neighbor Fractions"].Values;
     128      distanceValues.Add(CurrentNeutralDistanceParameter.ActualValue == null ? 0 : CurrentNeutralDistanceParameter.ActualValue.Value);
     129      fractionValues.Add(CurrentFractionOfNeutralNeighborsParameter.ActualValue == null ? 0 : CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value);
     130      var lengths = new List<double>();
     131      var distances = new List<double>();
     132      var innerFractions = new List<double>();
    105133      double lastValue = -1;
    106134      int lastStart = 0;
    107       for (int i = 0; i<values.Count; i++) {
    108         if (values[i] < lastValue) {
    109           lenghts.Add(i - lastStart - 1);
     135      for (int i = 0; i<distanceValues.Count; i++) {
     136        if (distanceValues[i] < lastValue) { // restart
     137          lengths.Add(i - lastStart - 1);
    110138          distances.Add(lastValue);
    111139          lastStart = i;
     140        } else { // inside neutral area
     141          innerFractions.Add(fractionValues[i]);
    112142        }
    113         lastValue = values[i];
     143        lastValue = distanceValues[i];
    114144      }
    115       if (distances.Count > 0 && lenghts.Count > 0) {
     145      if (lastStart != distanceValues.Count-1) {
     146        lengths.Add(distanceValues.Count - lastStart - 1);
     147        distances.Add(lastValue);
     148      }
     149      if (distances.Count > 0 && lengths.Count > 0) {
    116150        AverageNeutralWalkDistanceParameter.ActualValue = new DoubleValue(distances.Average());
    117151        NeutralWalkDistanceVarianceParameter.ActualValue = new DoubleValue(distances.Variance());
    118         AverageNeutralWalkLengthParameter.ActualValue = new DoubleValue(lenghts.Average());
    119         NeutralWalkLengthVarianceParameter.ActualValue = new DoubleValue(lenghts.Variance());
     152        AverageNeutralWalkLengthParameter.ActualValue = new DoubleValue(lengths.Average());
     153        NeutralWalkLengthVarianceParameter.ActualValue = new DoubleValue(lengths.Variance());
     154        AverageNeutralNeighborFractionParameter.ActualValue = new DoubleValue(fractionValues.Average());
     155        NeutralNeighborFractionVarianceParameter.ActualValue = new DoubleValue(fractionValues.Variance());
     156        AverageInnerNeutralNeighborFractionParameter.ActualValue = new DoubleValue(innerFractions.Average());
     157        InnerNeutralNeighborFractionVarianceParameter.ActualValue = new DoubleValue(innerFractions.Variance());
    120158      }
    121159      return base.Apply();
     
    127165        distancesTable = new DataTable("Neutral Walk Distances");
    128166        NeutralWalkDistancesTableParameter.ActualValue = distancesTable;
    129         var row = new DataRow("Neutral Walk Distances");
    130         distancesTable.Rows.Add(row);
     167        distancesTable.Rows.Add(new DataRow("Neutral Walk Distances"));
     168        distancesTable.Rows.Add(new DataRow("Neutral Neighbor Fractions") {VisualProperties = {SecondYAxis = true}});
    131169      }
    132170      return distancesTable;
  • branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape/NeutralSelector.cs

    r7128 r7783  
    5656      get { return (ValueLookupParameter<DoubleValue>)Parameters["Epsilon"]; }
    5757    }
     58    public ILookupParameter<DoubleValue> CurrentFractionOfNeutralNeighborsParameter {
     59      get { return (LookupParameter<DoubleValue>) Parameters["CurrentFractionOfNeutralNeighbors"]; }
     60    }
    5861    public LookupParameter<DoubleValue> CurrentNeutralDistanceParameter {
    5962      get { return (LookupParameter<DoubleValue>)Parameters["CurrentNeutralDistance"]; }
     
    7174      get { return CopySelectedParameter.Value; }
    7275      set { CopySelectedParameter.Value = value; }
     76    }
     77    protected double CurrentNeutralDistance {
     78      set {
     79        if (CurrentNeutralDistanceParameter.ActualValue == null)
     80          CurrentNeutralDistanceParameter.ActualValue= new DoubleValue(value);
     81        else
     82          CurrentNeutralDistanceParameter.ActualValue.Value = value;
     83      }
     84     
     85    }
     86    protected double CurrentFractionOfNeutralNeighbors {
     87      get { return CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value; }
     88      set {
     89        if (CurrentFractionOfNeutralNeighborsParameter.ActualValue == null)
     90          CurrentFractionOfNeutralNeighborsParameter.ActualValue = new DoubleValue(value);
     91        else
     92          CurrentFractionOfNeutralNeighborsParameter.ActualValue.Value = value;
     93      }
    7394    }
    7495    #endregion
     
    91112      Parameters.Add(new ConstrainedValueParameter<IItemDistanceCalculator>("SolutionDistanceCalculator", "Operator to calculate distances between the base item and the current item."));
    92113      Parameters.Add(new LookupParameter<DoubleValue>("CurrentNeutralDistance", "The distance of the current item to the starting point of the neutral (portion of the) walk."));
     114      Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The fraction of examined neighbors that have the same fitness value (within epsilon)"));
    93115      Parameters.Add(new LookupParameter<IRandom>("Random", "Random number generator for breaking ties in the ordering."));
    94116      CopySelectedParameter.Hidden = true;
     
    112134      return new NeutralSelector(this, cloner);
    113135    }
     136    [StorableHook(HookType.AfterDeserialization)]
     137    private void AfterDeserialization() {
     138      if (!Parameters.ContainsKey("CurrentFractionOfNeutralNeighbors"))
     139        Parameters.Add(new LookupParameter<DoubleValue>("CurrentFractionOfNeutralNeighbors", "The fraction of examined neighbors that have the same fitness (within epsilon)"));
     140    }
    114141    #endregion
    115142
     
    119146
    120147    public sealed override IOperation Apply() {
    121       IItemDistanceCalculator calc = (IItemDistanceCalculator)SolutionDistanceCalculatorParameter.ActualValue;
    122       double baseQuality = BaseQualityParameter.ActualValue.Value;
    123       IItem startingPoint = StartingPointParameter.ActualValue;
    124       IItem baseSolution = BaseSolutionParameter.ActualValue;
    125       ItemArray<IItem> items = SolutionParameter.ActualValue;
    126       double eps = EpsilonParameter.ActualValue.Value;
    127       IRandom random = RandomParameter.ActualValue;
    128       double baseDistance = 0;
    129       if (startingPoint != null) {
    130         baseDistance = calc.Distance(baseSolution, startingPoint);
    131         baseSolution = startingPoint;
     148      var calc = (IItemDistanceCalculator)SolutionDistanceCalculatorParameter.ActualValue;
     149      var baseQuality = BaseQualityParameter.ActualValue.Value;
     150      var startingPoint = StartingPointParameter.ActualValue;
     151      var baseSolution = BaseSolutionParameter.ActualValue;
     152      var items = SolutionParameter.ActualValue;
     153      var eps = EpsilonParameter.ActualValue.Value;
     154      var random = RandomParameter.ActualValue;
     155      double currentNeutralDistance;
     156
     157      if (startingPoint == null) {
     158        currentNeutralDistance = 0;
     159        CurrentNeutralDistance = 0;
     160        startingPoint = baseSolution;
     161        StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
     162      } else {
     163        currentNeutralDistance = calc.Distance(startingPoint, baseSolution);
    132164      }
    133165
     
    137169          Idx=i,
    138170          Diff=Squash(Math.Abs(baseQuality-p.Quality), eps),
    139           Dist=calc.Distance(baseSolution, p.Item)
     171          StartDist=calc.Distance(startingPoint, p.Item),
     172          BaseDist=calc.Distance(baseSolution, p.Item)
    140173        })       
     174        .Where(n => n.BaseDist > 0)
    141175        .ToList();
    142       if (random != null)
    143         neighbors.Shuffle(random);
    144       var mostDistantNeutralNeighbor = neighbors.Where(n => n.Diff == 0).OrderByDescending(n => n.Dist).FirstOrDefault();
    145       if (mostDistantNeutralNeighbor != null && mostDistantNeutralNeighbor.Dist > baseDistance) {
    146         Select(mostDistantNeutralNeighbor.Idx);
    147         if (startingPoint == null)
    148           StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
    149         CurrentNeutralDistanceParameter.ActualValue = new DoubleValue(mostDistantNeutralNeighbor.Dist);
    150       } else {
    151         var mostDistantNeighbor = neighbors.OrderByDescending(n => n.Dist).FirstOrDefault();
    152         Select(mostDistantNeighbor.Idx);
    153         StartingPointParameter.ActualValue = (IItem)items[mostDistantNeighbor.Idx].Clone();
    154         CurrentNeutralDistanceParameter.ActualValue = new DoubleValue(0);
     176      if (neighbors.Count > 0) {
     177        if (random != null)
     178          neighbors.Shuffle(random);
     179        var mostDistantNeutralNeighbor =
     180          neighbors.Where(n => n.Diff == 0).OrderByDescending(n => n.StartDist).FirstOrDefault();
     181        if (mostDistantNeutralNeighbor != null && mostDistantNeutralNeighbor.StartDist > currentNeutralDistance) {
     182          if (currentNeutralDistance == 0) {
     183            StartingPointParameter.ActualValue = (IItem) baseSolution.Clone();
     184            CurrentNeutralDistance = mostDistantNeutralNeighbor.BaseDist;
     185          } else {
     186            CurrentNeutralDistance = mostDistantNeutralNeighbor.StartDist;
     187          }
     188          Select(mostDistantNeutralNeighbor.Idx);
     189        } else {
     190          var mostDistantNonNeutralNeighbor = neighbors.Where(n => n.Diff > 0).OrderByDescending(n => n.StartDist).FirstOrDefault();
     191          if (mostDistantNonNeutralNeighbor != null) {
     192            Select(mostDistantNonNeutralNeighbor.Idx);
     193          } else {
     194            var mostDistantNeighbor = neighbors.OrderByDescending(n => n.StartDist).FirstOrDefault();
     195            Select(mostDistantNeighbor.Idx);
     196          }
     197          if (currentNeutralDistance > 0)
     198            StartingPointParameter.ActualValue = (IItem)baseSolution.Clone();
     199          CurrentNeutralDistance = 0;
     200        }
     201        CurrentFractionOfNeutralNeighbors = 1.0*neighbors.Count(n => n.Diff == 0)/neighbors.Count;
    155202      }
    156203      return base.Apply();
Note: See TracChangeset for help on using the changeset viewer.