Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/29/18 18:16:05 (6 years ago)
Author:
abeham
Message:

#2457:

  • Changed calculation of correlation length (using limit introduced Hordijk 1996)
  • Changed RuggednessCalculator (no more a HL item)
  • Added additional, information-analysis-based features for directed walks
  • Added generic DirectedWalk algorithm (as described in thesis)
  • Made OneSizeInstanceProvider parametrizable
  • Adapted program for analyzing problem instance reidentification
Location:
branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3
Files:
1 added
9 edited

Legend:

Unmodified
Added
Removed

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/InformationAnalyzer.cs

    r15279 r16096  
    2020#endregion
    2121
     22using System.Linq;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    2728using HeuristicLab.Parameters;
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using System.Linq;
    30 using System;
    3130
    3231namespace HeuristicLab.Analysis.FitnessLandscape {
    … …  
    125124      var ic = new DoubleValue(analysis.InformationContent.FirstOrDefault());
    126125      InformationContentParameter.ActualValue = ic;
    127       AddOrUpdateResult(results, InformationContentParameter.Name, ic);
     126      results.AddOrUpdateResult(InformationContentParameter.Name, ic);
    128127      var pic = new DoubleValue(analysis.PartialInformationContent.FirstOrDefault());
    129128      PartialInformationContentParameter.ActualValue = pic;
    130       AddOrUpdateResult(results, PartialInformationContentParameter.Name, pic);
     129      results.AddOrUpdateResult(PartialInformationContentParameter.Name, pic);
    131130      var dbi = new DoubleValue(analysis.DensityBasinInformation.FirstOrDefault());
    132131      DensityBasinInformationParameter.ActualValue = dbi;
    133       AddOrUpdateResult(results, DensityBasinInformationParameter.Name, dbi);
     132      results.AddOrUpdateResult(DensityBasinInformationParameter.Name, dbi);
    134133      var @is = new DoubleValue(analysis.InformationStability);
    135134      InformationStabilityParameter.ActualValue = @is;
    136       AddOrUpdateResult(results, InformationStabilityParameter.Name, @is);
     135      results.AddOrUpdateResult(InformationStabilityParameter.Name, @is);
    137136      var regularity = new DoubleValue(1.0 * analysis.Regularity / qualities.Count);
    138137      RegularityParameter.ActualValue = regularity;
    139       AddOrUpdateResult(results, RegularityParameter.Name, regularity);
     138      results.AddOrUpdateResult(RegularityParameter.Name, regularity);
    140139      var diversity = new DoubleValue(1.0 * analysis.Diversity / qualities.Count);
    141140      DiversityParameter.ActualValue = diversity;
    142       AddOrUpdateResult(results, DiversityParameter.Name, diversity);
     141      results.AddOrUpdateResult(DiversityParameter.Name, diversity);
    143142      var totalEntropy = new DoubleValue(analysis.TotalEntropy.FirstOrDefault());
    144143      TotalEntropyParameter.ActualValue = totalEntropy;
    145       AddOrUpdateResult(results, TotalEntropyParameter.Name, totalEntropy);
     144      results.AddOrUpdateResult(TotalEntropyParameter.Name, totalEntropy);
    146145      var peakIc = new DoubleValue(analysis.PeakInformationContent.Value);
    147146      PeakInformationContentParameter.ActualValue = peakIc;
    148       AddOrUpdateResult(results, PeakInformationContentParameter.Name, peakIc);
     147      results.AddOrUpdateResult(PeakInformationContentParameter.Name, peakIc);
    149148      var peakDbi = new DoubleValue(analysis.PeakDensityBasinInformation.Value);
    150149      PeakDensityBasinInformationParameter.ActualValue = peakDbi;
    151       AddOrUpdateResult(results, PeakDensityBasinInformationParameter.Name, peakDbi);
     150      results.AddOrUpdateResult(PeakDensityBasinInformationParameter.Name, peakDbi);
    152151
    153152      var itable = GetInformationTable(analysis);
    154       AddOrUpdateResult(results, InformationAnalysisParameter.Name, itable);
     153      results.AddOrUpdateResult(InformationAnalysisParameter.Name, itable);
    155154      return base.Apply();
    156155    }
    … …  
    176175      return dt;
    177176    }
    178 
    179     private static void AddOrUpdateResult(ResultCollection results, string name, IItem item, bool clone = false) {
    180       IResult r;
    181       if (!results.TryGetValue(name, out r)) {
    182         results.Add(new Result(name, clone ? (IItem)item.Clone() : item));
    183       } else r.Value = clone ? (IItem)item.Clone() : item;
    184     }
    185177  }
    186178}

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/RuggednessAnalyzer.cs

    r13583 r16096  
    2020#endregion
    2121
     22using System.Linq;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    2728using HeuristicLab.Parameters;
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using System.Linq;
    3030
    3131namespace HeuristicLab.Analysis.FitnessLandscape {
    32   [Item("Ruggedness Analyzer", "Analyzes autocorrelation for one mutation step and correlation length.")]
     32  [Item("Ruggedness Analyzer", "Analyzes autocorrelation for one mutation step and correlation length. Correlation length is calculated according to the statistical correlation length defined by Hordijk, W., 1996. A measure of landscapes. Evolutionary computation, 4(4), pp.335-360.")]
    3333  [StorableClass]
    3434  public class RuggednessAnalyzer : SingleSuccessorOperator, IQualityTrailAnalyzer {
    … …  
    5050      get { return (LookupParameter<IntValue>)Parameters["CorrelationLength"]; }
    5151    }
     52    public ValueLookupParameter<DoubleValue> LimitParameter {
     53      get { return (ValueLookupParameter<DoubleValue>)Parameters["Limit"]; }
     54    }
    5255    #endregion
    5356
    … …  
    6063      Parameters.Add(new LookupParameter<DoubleValue>("AutoCorrelation1", "Autocorrelation for one mutation step."));
    6164      Parameters.Add(new LookupParameter<IntValue>("CorrelationLength", "The correlation length."));
     65      Parameters.Add(new ValueLookupParameter<DoubleValue>("Limit", "The limit for the statistical correlation length, if left empty 2 / sqrt(n), where n = length of walk will be used, as defined by Hordijk 1996."));
    6266    }
    6367
    … …  
    7074      if (qualityTrail == null || qualityTrail.Rows.Count <= 0) return base.Apply();
    7175      var results = ResultsParameter.ActualValue;
     76      var limit = LimitParameter.ActualValue?.Value;
    7277      double[] autocorrelationValues;
    73       var correlationLength = RuggednessCalculator.CalculateCorrelationLength(qualityTrail.Rows.First().Values.ToArray(), out autocorrelationValues);
     78      var correlationLength = RuggednessCalculator.CalculateCorrelationLength(qualityTrail.Rows.First().Values.ToArray(), out autocorrelationValues, limit);
    7479      var cl = new IntValue(correlationLength);
    7580      CorrelationLengthParameter.ActualValue = cl;
    76       AddOrUpdateResult(results, CorrelationLengthParameter.Name, cl);
     81      results.AddOrUpdateResult(CorrelationLengthParameter.Name, cl);
    7782      var ac1 = new DoubleValue(autocorrelationValues.Length > 1 ? autocorrelationValues[1] : 0.0);
    7883      AutoCorrelation1Parameter.ActualValue = ac1;
    79       AddOrUpdateResult(results, AutoCorrelation1Parameter.Name, ac1);
     84      results.AddOrUpdateResult(AutoCorrelation1Parameter.Name, ac1);
    8085      return base.Apply();
    81     }
    82 
    83     private static void AddOrUpdateResult(ResultCollection results, string name, IItem item, bool clone = false) {
    84       IResult r;
    85       if (!results.TryGetValue(name, out r)) {
    86         results.Add(new Result(name, clone ? (IItem)item.Clone() : item));
    87       } else r.Value = clone ? (IItem)item.Clone() : item;
    8886    }
    8987  }

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/RuggednessCalculator.cs

    r13583 r16096  
    2020#endregion
    2121
    22 using HeuristicLab.Common;
    23 using HeuristicLab.Core;
    24 using HeuristicLab.Data;
    25 using HeuristicLab.Operators;
    26 using HeuristicLab.Parameters;
    27 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2822using System;
    2923using System.Collections.Generic;
    30 using System.Linq;
    3124
    3225namespace HeuristicLab.Analysis.FitnessLandscape {
    33   [Item("Ruggedness Calculator", "Calculates ruggedness descriptors froma given quality trail.")]
    34   [StorableClass]
    35   public class RuggednessCalculator : SingleSuccessorOperator {
    36 
    37     #region Parameters
    38     public LookupParameter<DataTable> QualityTrailParameter {
    39       get { return (LookupParameter<DataTable>)Parameters["QualityTrail"]; }
    40     }
    41     public LookupParameter<IntValue> CorrelationLengthParameter {
    42       get { return (LookupParameter<IntValue>)Parameters["CorrelationLength"]; }
    43     }
    44     public LookupParameter<DoubleArray> AutoCorrelationParameter {
    45       get { return (LookupParameter<DoubleArray>)Parameters["AutoCorrelation"]; }
    46     }
    47     #endregion
    48 
    49     #region Constructors & Cloning
    50     [StorableConstructor]
    51     protected RuggednessCalculator(bool deserializing) : base(deserializing) { }
    52     protected RuggednessCalculator(RuggednessCalculator original, Cloner cloner) : base(original, cloner) { }
    53     public RuggednessCalculator() {
    54       Parameters.Add(new LookupParameter<DataTable>("QualityTrail", "Historical values of walk qualities"));
    55       Parameters.Add(new LookupParameter<IntValue>("CorrelationLength", "Average maximum distances between correlated quality values."));
    56       Parameters.Add(new LookupParameter<DoubleArray>("AutoCorrelation", "AutoCorrelation"));
    57     }
    58     public override IDeepCloneable Clone(Cloner cloner) {
    59       return new RuggednessCalculator(this, cloner);
    60     }
    61     #endregion
    62 
    63     public override IOperation Apply() {
    64       double[] qualities = QualityTrailParameter.ActualValue.Rows.First().Values.ToArray();
    65       double[] autocorrelation;
    66       CorrelationLengthParameter.ActualValue = new IntValue(CalculateCorrelationLength(qualities, out autocorrelation));
    67       AutoCorrelationParameter.ActualValue = new DoubleArray(autocorrelation);
    68       return base.Apply();
    69     }
    70 
    71     public static int CalculateCorrelationLength(double[] qualities, out double[] acf) {
     26  public static class RuggednessCalculator {
     27    /// <summary>
     28    /// Calculates statistical correlation length as defined by Hordijk, W., 1996. A measure of landscapes. Evolutionary computation, 4(4), pp.335-360.
     29    /// </summary>
     30    /// <param name="qualities">The quality trail observed.</param>
     31    /// <param name="acf">The autocorrelation values for each step s, including 0 => acf[0] = 1.</param>
     32    /// <param name="limit">The statistical limit, correlation length will be the last step before acf falls within this limit. If omitted it is calculated as 2 / sqrt(qualities.Length).</param>
     33    /// <returns>The statistical correlation length</returns>
     34    public static int CalculateCorrelationLength(double[] qualities, out double[] acf, double? limit = null) {
     35      if (!limit.HasValue) limit = 2.0 / Math.Sqrt(qualities.Length);
    7236      double[] correlations = new double[qualities.Length];
    7337      alglib.corr.corrr1dcircular(qualities, qualities.Length, qualities, qualities.Length, ref correlations);
    … …  
    8650          value = 1;
    8751        autocorrelation.Add(value);
    88         if (value < 0 && correlationLength < 0) correlationLength = counter;
     52        if (Math.Abs(value) < limit && correlationLength < 0) correlationLength = counter;
    8953      }
    9054      acf = autocorrelation.ToArray();
    9155      return correlationLength - 1;
    9256    }
    93 
    94     public static bool AnyGreaterOne(double[] values) {
    95       return values.Any(d => d > 1);
    96     }
    9757  }
    9858}

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Analysis/UpDownWalkAnalyzer.cs

    r13583 r16096  
    2020#endregion
    2121
     22using System.Linq;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    2728using HeuristicLab.Parameters;
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using System.Linq;
    3030
    3131namespace HeuristicLab.Analysis.FitnessLandscape {
    … …  
    123123              var uv = new DoubleValue(topVals.Variance());
    124124              UpperVarianceParameter.ActualValue = uv;
    125               AddOrUpdateResult(results, UpperVarianceParameter.Name, uv);
     125              results.AddOrUpdateResult(UpperVarianceParameter.Name, uv);
    126126              var ul = new DoubleValue(topLengths.Average());
    127127              UpWalkLengthParameter.ActualValue = ul;
    128               AddOrUpdateResult(results, UpWalkLengthParameter.Name, ul);
     128              results.AddOrUpdateResult(UpWalkLengthParameter.Name, ul);
    129129              var ulv = new DoubleValue(topLengths.Variance());
    130130              UpWalkLenVarParameter.ActualValue = ulv;
    131               AddOrUpdateResult(results, UpWalkLenVarParameter.Name, ulv);
     131              results.AddOrUpdateResult(UpWalkLenVarParameter.Name, ulv);
    132132            }
    133133            if (bottoms.Count > 0) {
    … …  
    136136              var lv = new DoubleValue(bottomVals.Variance());
    137137              LowerVarianceParameter.ActualValue = lv;
    138               AddOrUpdateResult(results, LowerVarianceParameter.Name, lv);
     138              results.AddOrUpdateResult(LowerVarianceParameter.Name, lv);
    139139              var dl = new DoubleValue(bottomLengths.Average());
    140140              DownWalkLengthParameter.ActualValue = dl;
    141               AddOrUpdateResult(results, DownWalkLengthParameter.Name, dl);
     141              results.AddOrUpdateResult(DownWalkLengthParameter.Name, dl);
    142142              var dlv = new DoubleValue(bottomLengths.Variance());
    143143              DownWalkLenVarParameter.ActualValue = dlv;
    144               AddOrUpdateResult(results, DownWalkLenVarParameter.Name, dlv);
     144              results.AddOrUpdateResult(DownWalkLenVarParameter.Name, dlv);
    145145            }
    146146          }
    … …  
    149149      return base.Apply();
    150150    }
    151 
    152     private static void AddOrUpdateResult(ResultCollection results, string name, IItem item, bool clone = false) {
    153       IResult r;
    154       if (!results.TryGetValue(name, out r)) {
    155         results.Add(new Result(name, clone ? (IItem)item.Clone() : item));
    156       } else r.Value = clone ? (IItem)item.Clone() : item;
    157     }
    158151  }
    159152}

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/HeuristicLab.Analysis.FitnessLandscape-3.3.csproj

    r15694 r16096  
    207207    <Compile Include="ProblemCharacteristicAnalysis\CharacteristicCalculator.cs" />
    208208    <Compile Include="ProblemCharacteristicAnalysis\CurveAnalysis.cs" />
     209    <Compile Include="Algorithms\DirectedWalk.cs" />
    209210    <Compile Include="ProblemCharacteristicAnalysis\DoubleMatrixCharacteristicCalculator.cs" />
    210211    <Compile Include="ProblemCharacteristicAnalysis\PermutationPathAnalysis.cs" />

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/CurveAnalysis.cs

    r14691 r16096  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Collections.Generic;
    324using System.Linq;
    … …  
    728    public static CurveAnalysisResult GetCharacteristics(List<List<Tuple<T, double>>> trajectories, Func<T, T, double> distFunc) {
    829      trajectories = trajectories.Where(x => x.Count > 5).ToList();
     30      var symbols = GetSymbols(trajectories);
    931      var f1 = trajectories.Select(path => ApproximateDerivative(path, distFunc).ToList()).ToList();
    1032      var f2 = f1.Select(d1 => ApproximateDerivative(d1, distFunc).ToList()).ToList();
    1133
    12       var sharpness = f1.Average(x => x.Average(y => Math.Abs(y.Item2)));//f2.Average(x => Area(x, distFunc));
     34      var sharpness = f1.Average(x => x.Average(y => Math.Abs(y.Item2)));
    1335      var bumpiness = 0.0;
    1436      var flatness = 0.0;
    15 
     37      var count = 0;
    1638      for (var p = 0; p < f2.Count; p++) {
    1739        if (f2[p].Count <= 2) continue;
     40        count++;
    1841        var bump = 0;
    1942        var flat = 0;
    … …  
    2851        flatness += flat / (f2[p].Count - 1.0);
    2952      }
    30       bumpiness /= f2.Count;
    31       flatness /= f2.Count;
    32       return new CurveAnalysisResult(sharpness, bumpiness, flatness);
     53      bumpiness /= count;
     54      flatness /= count;
     55      var per = new[] { 25, 50, 75 };
     56      return new CurveAnalysisResult(sharpness, bumpiness, flatness,
     57        per.Select(p => symbols.Downward.GetPercentileOrDefault(p, 0)).ToArray(),
     58        per.Select(p => symbols.Neutral.GetPercentileOrDefault(p, 0)).ToArray(),
     59        per.Select(p => symbols.Upward.GetPercentileOrDefault(p, 0)).ToArray());
    3360    }
    3461
    35     private static double Area(IEnumerable<Tuple<T, double>> path, Func<T, T, double> distFunc) {
    36       var iter = path.GetEnumerator();
    37       if (!iter.MoveNext()) return 0.0;
    38       var area = 0.0;
    39       var prev = iter.Current;
    40       while (iter.MoveNext()) {
    41         area += TrapezoidArea(prev, iter.Current, distFunc);
    42         prev = iter.Current;
     62    private static Symbols GetSymbols(List<List<Tuple<T, double>>> trajectories) {
     63      var sym = new Symbols();
     64      foreach (var t in trajectories) {
     65        var prev = t[0];
     66        for (var i = 1; i < t.Count; i++) {
     67          sym.Add(i / (double)t.Count, t[i].Item2, prev.Item2);
     68          prev = t[i];
     69        }
    4370      }
    44       return area;
    45     }
    46 
    47     private static double TrapezoidArea(Tuple<T, double> a, Tuple<T, double> b, Func<T, T, double> distFunc) {
    48       var area = 0.0;
    49       var dist = distFunc(a.Item1, b.Item1);
    50       if ((a.Item2 <= 0 && b.Item2 <= 0) || (a.Item2 >= 0 && b.Item2 >= 0))
    51         area += dist * (Math.Abs(a.Item2) + Math.Abs(b.Item2)) / 2.0;
    52       else {
    53         var k = (b.Item2 - a.Item2) / dist;
    54         var d = a.Item2;
    55         var x = -d / k;
    56         area += Math.Abs(x * a.Item2 / 2.0);
    57         area += Math.Abs((dist - x) * b.Item2 / 2.0);
    58       }
    59       return area;
     71      return sym;
    6072    }
    6173
    … …  
    8092  }
    8193
     94  public enum CurveAnalysisFeature { Sharpness, Bumpiness, Flatness,
     95                                     DownQ1, DownQ2, DownQ3,
     96                                     NeutQ1, NeutQ2, NeutQ3,
     97                                     UpQ1, UpQ2, UpQ3 }
     98
    8299  public class CurveAnalysisResult {
    83     public double Sharpness { get; private set; }
    84     public double Bumpiness { get; private set; }
    85     public double Flatness { get; private set; }
     100    private Dictionary<CurveAnalysisFeature, double> results = new Dictionary<CurveAnalysisFeature, double>();
    86101
    87     public string[] GetNames() {
    88       return new[] { "Sharpness", "Bumpiness", "Flatness" };
     102    public double GetValue(CurveAnalysisFeature name) {
     103      return results[name];
     104    }
     105
     106    public static IEnumerable<CurveAnalysisFeature> AllFeatures {
     107      get { return Enum.GetValues(typeof(CurveAnalysisFeature)).Cast<CurveAnalysisFeature>(); }
    89108    }
    90109
    91110    public double[] GetValues() {
    92       return new[] { Sharpness, Bumpiness, Flatness };
     111      return AllFeatures.Select(x => results[x]).ToArray();
    93112    }
    94113
    95     public CurveAnalysisResult(double sharpness, double bumpiness, double flatness) {
    96       Sharpness = sharpness;
    97       Bumpiness = bumpiness;
    98       Flatness = flatness;
     114    public CurveAnalysisResult(double sharpness, double bumpiness, double flatness, double[] down, double[] neut, double[] up) {
     115      foreach (var v in AllFeatures.Zip(new[] { sharpness, bumpiness, flatness }.Concat(down).Concat(neut).Concat(up), (n, v) => Tuple.Create(n, v))) {
     116        results[v.Item1] = v.Item2;
     117      }
     118    }
     119  }
     120
     121  public class Symbols {
     122    public Statistics Downward { get; } = new Statistics();
     123    public Statistics Neutral { get; } = new Statistics();
     124    public Statistics Upward { get; } = new Statistics();
     125
     126    public void Add(double step, double fit, double prev) {
     127      if (fit < prev) Downward.Add(step);
     128      else if (fit > prev) Upward.Add(step);
     129      else Neutral.Add(step);
     130    }
     131  }
     132
     133  public sealed class Statistics {
     134    private List<double> values = new List<double>();
     135
     136    public int Count { get { return values.Count; } }
     137
     138    public double Min { get; private set; }
     139    public double Max { get; private set; }
     140    public double Total { get; private set; }
     141    public double Mean { get; private set; }
     142    public double StdDev { get { return Math.Sqrt(Variance); } }
     143    public double Variance { get { return Count > 0 ? variance / Count : 0.0; } }
     144   
     145    private double variance;
     146    private bool sorted = false;
     147   
     148    public double GetPercentileOrDefault(int p, double @default = default(double)) {
     149      if (p < 0 || p > 100) throw new ArgumentOutOfRangeException(nameof(p), p, "Must be in range [0;100]");
     150      SortIfNecessary();
     151      if (Count == 0) return @default;
     152      else if (Count == 1) return values[0];
     153      if (p == 100) return values[Count - 1];
     154
     155      var x = p / 100.0 * (Count - 1);
     156      var inte = (int)x;
     157      var frac = x - inte;
     158
     159      return values[inte] + frac * (values[inte + 1] - values[inte]);
     160    }
     161
     162    public void Add(double value) {
     163      sorted = false;
     164      values.Add(value);
     165
     166      if (Count == 1) {
     167        Min = Max = Mean = Total = value;
     168      } else {
     169        if (value < Min) Min = value;
     170        if (value > Max) Max = value;
     171
     172        Total += value;
     173        var oldMean = Mean;
     174        Mean = oldMean + (value - oldMean) / Count;
     175        variance = variance + (value - oldMean) * (value - Mean);
     176      }
     177    }
     178
     179    public void AddRange(IEnumerable<double> values) {
     180      foreach (var v in values) Add(v);
     181    }
     182
     183    private void SortIfNecessary() {
     184      if (!sorted) {
     185        values.Sort();
     186        sorted = true;
     187      }
    99188    }
    100189  }

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/PermutationPathAnalysis.cs

    r14691 r16096  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Collections.Generic;
    324using HeuristicLab.Encodings.PermutationEncoding;

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPCharacteristicCalculator.cs

    r14678 r16096  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
     24using System.Linq;
    2225using HeuristicLab.Common;
    2326using HeuristicLab.Core;
    … …  
    2629using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2730using HeuristicLab.Problems.QuadraticAssignment;
    28 using System;
    29 using System.Collections.Generic;
    30 using System.Linq;
    3131
    3232namespace HeuristicLab.Analysis.FitnessLandscape {
    … …  
    6161        if (chara == "Dimension")
    6262          yield return new Result(chara, new IntValue(qap.Weights.Rows));
    63         if (chara == "FlowDominance")
     63        else if (chara == "FlowDominance")
    6464          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(qap.Weights)));
    65         if (chara == "DistanceDominance")
     65        else if (chara == "DistanceDominance")
    6666          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(qap.Distances)));
    67         if (chara == "FlowAsymmetry")
     67        else if (chara == "FlowAsymmetry")
    6868          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Asymmetry(qap.Weights)));
    69         if (chara == "DistanceAsymmetry")
     69        else if (chara == "DistanceAsymmetry")
    7070          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Asymmetry(qap.Distances)));
    71         if (chara == "FlowSparsity")
     71        else if (chara == "FlowSparsity")
    7272          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(qap.Weights)));
    73         if (chara == "DistanceSparsity")
     73        else if (chara == "DistanceSparsity")
    7474          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(qap.Distances)));
    75         if (chara == "FlowSkewness")
     75        else if (chara == "FlowSkewness")
    7676          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Skewness(qap.Weights)));
    77         if (chara == "DistanceSkewness")
     77        else if (chara == "DistanceSkewness")
    7878          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Skewness(qap.Distances)));
    79         if (chara == "FlowDisparity")
     79        else if (chara == "FlowDisparity")
    8080          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Disparity(qap.Weights)));
    81         if (chara == "DistanceDisparity")
     81        else if (chara == "DistanceDisparity")
    8282          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Disparity(qap.Distances)));
    8383      }

  • branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

    r15031 r16096  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
     24using System.Linq;
     25using System.Threading;
    2226using HeuristicLab.Common;
    2327using HeuristicLab.Core;
    … …  
    2933using HeuristicLab.Problems.QuadraticAssignment;
    3034using HeuristicLab.Random;
    31 using System;
    32 using System.Collections.Generic;
    33 using System.Linq;
    34 using System.Threading;
    3535
    3636namespace HeuristicLab.Analysis.FitnessLandscape {
    … …  
    3838  [StorableClass]
    3939  public class QAPDirectedWalk : CharacteristicCalculator {
     40
     41    public enum WalkType { RandomRandom, RandomGlobal, RandomLocal, LocalLocal, LocalGlobal, LocalInverse }
     42
     43    private const string NBHOOD_STR = "Swap2";
    4044   
    4145    public IFixedValueParameter<IntValue> PathsParameter {
    … …  
    5155    }
    5256
    53     public IFixedValueParameter<BoolValue> LocalOptimaParameter {
    54       get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; }
     57    public IFixedValueParameter<EnumValue<WalkType>> TypeParameter {
     58      get { return (IFixedValueParameter<EnumValue<WalkType>>)Parameters["Type"]; }
    5559    }
    5660
    … …  
    7074    }
    7175
    72     public bool LocalOptima {
    73       get { return LocalOptimaParameter.Value.Value; }
    74       set { LocalOptimaParameter.Value.Value = value; }
     76    public WalkType Type {
     77      get { return TypeParameter.Value.Value; }
     78      set { TypeParameter.Value.Value = value;}
    7579    }
    7680
    … …  
    7983    private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
    8084    public QAPDirectedWalk() {
    81       characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }
    82         .Select(x => new StringValue(x)).ToList());
     85      characteristics.AddRange(CurveAnalysisResult.AllFeatures.Select(x => new StringValue(x.ToString())));
     86      characteristics.AddRange(new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent",
     87        "DensityBasinInformation", "PartialInformationContent", "InformationStability",
     88        "Diversity", "Regularity", "TotalEntropy", "PeakInformationContent",
     89        "PeakDensityBasinInformation" }.Select(x => new StringValue(x)));
     90
    8391      Parameters.Add(new FixedValueParameter<IntValue>("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50)));
    8492      Parameters.Add(new FixedValueParameter<BoolValue>("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true)));
    8593      Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator."));
    86       Parameters.Add(new FixedValueParameter<BoolValue>("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false)));
     94      Parameters.Add(new FixedValueParameter<EnumValue<WalkType>>("Type", "Type of directed walk to perfom.", new EnumValue<WalkType>(WalkType.RandomRandom)));
    8795    }
    8896
    … …  
    95103    }
    96104
     105    private double _evaluatedSolutions;
     106
    97107    public override IEnumerable<IResult> Calculate() {
     108      _evaluatedSolutions = 0;
     109      var permutations = CalculateRelinkingPoints();
     110
     111      var trajectories = Run(permutations).ToList();
     112      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
     113
     114      #region Calculate Information Analysis Features
     115      double avgAc1 = 0, avgCorLen = 0, avgIc = 0, avgDbi = 0, avgPic = 0, avgIS = 0, avgDiv = 0,
     116        avgReg = 0, avgEnt = 0, avgPkIc = 0, avgPkDbi = 0;
     117      int count = 0;
     118      foreach (var t in trajectories) {
     119        var trail = t.Select(x => x.Item2).ToArray();
     120        if (trail.Length < 4) continue;
     121        count++;
     122        double[] acf;
     123        var len = RuggednessCalculator.CalculateCorrelationLength(trail, out acf);
     124        avgAc1 += acf[0];
     125        avgCorLen += len;
     126        var analysis = new InformationAnalysis(trail, 20, 2);
     127        avgIc += analysis.InformationContent[0];
     128        avgDbi += analysis.DensityBasinInformation[0];
     129        avgPic += analysis.PartialInformationContent[0];
     130        avgIS += analysis.InformationStability;
     131        avgDiv += analysis.Diversity;
     132        avgReg += analysis.Regularity;
     133        avgEnt += analysis.TotalEntropy[0];
     134        avgPkIc += analysis.PeakInformationContent.Value;
     135        avgPkDbi += analysis.PeakDensityBasinInformation.Value;
     136      }
     137      avgAc1 /= count;
     138      avgCorLen /= count;
     139      avgIc /= count;
     140      avgDbi /= count;
     141      avgPic /= count;
     142      avgIS /= count;
     143      avgDiv /= count;
     144      avgReg /= count;
     145      avgEnt /= count;
     146      avgPkIc /= count;
     147      avgPkDbi /= count;
     148      var isResults = new Dictionary<string, double>() {
     149        { "AutoCorrelation1", avgAc1 },
     150        { "CorrelationLength", avgCorLen },
     151        { "InformationContent", avgIc },
     152        { "DensityBasinInformation", avgDbi },
     153        { "PartialInformationContent", avgPic },
     154        { "InformationStability", avgIS },
     155        { "Diversity", avgDiv },
     156        { "Regularity", avgReg },
     157        { "TotalEntropy", avgEnt },
     158        { "PeakInformationContent", avgPkIc },
     159        { "PeakDensityBasinInformation", avgPkDbi }
     160      };
     161      #endregion
     162
     163      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
     164        if (Enum.TryParse<CurveAnalysisFeature>(chara, out var caf))
     165          yield return new Result(Type.ToString() + "-DW." + NBHOOD_STR + "." + chara, new DoubleValue(result.GetValue(caf)));
     166        else yield return new Result(Type.ToString() + "-DW." + NBHOOD_STR + "." + chara, new DoubleValue(isResults[chara]));
     167      }
     168      yield return new Result("EvaluatedSolutions", new IntValue((int)Math.Round(_evaluatedSolutions)));
     169    }
     170
     171    private IEnumerable<Permutation> CalculateRelinkingPoints() {
    98172      IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
    99173      var qap = (QuadraticAssignmentProblem)Problem;
    100       List<Permutation> permutations = CalculateRelinkingPoints(random, qap, Paths, LocalOptima);
    101 
    102       var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
    103       var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
    104 
    105       foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
    106         if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
    107         if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
    108         if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
    109       }
    110     }
    111 
    112     public static List<Permutation> CalculateRelinkingPoints(IRandom random, QuadraticAssignmentProblem qap, int pathCount, bool localOptima) {
     174      var pathCount = Paths;
     175
    113176      var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
    114       if (localOptima) {
    115         var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
    116         QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
    117       }
    118       var permutations = new List<Permutation> { perm };
    119       while (permutations.Count < pathCount + 1) {
    120         perm = (Permutation)permutations.Last().Clone();
    121         BiasedShuffle(perm, random);
    122         if (localOptima) {
     177      var startLocal = Type == WalkType.LocalGlobal || Type == WalkType.LocalLocal;
     178      var targetLocal = Type == WalkType.LocalLocal || Type == WalkType.RandomLocal;
     179      var targetGlobal = Type == WalkType.LocalGlobal || Type == WalkType.RandomGlobal;
     180      var inverseWalk = Type == WalkType.LocalInverse;
     181
     182      if (Type == WalkType.LocalInverse) pathCount--; // inverse walks equal one walk per solution
     183      for (var i = 0; i <= pathCount; i++) {
     184        var start = i % 2 == 0;
     185        var target = i % 2 == 1;
     186        if (inverseWalk || start && startLocal) {
     187          perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
    123188          var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
    124           QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     189          _evaluatedSolutions++;
     190          var evalSol = new IntValue(0);
     191          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), evalSol, qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     192          _evaluatedSolutions += evalSol.Value;
     193        } else if (target && (targetLocal || targetGlobal)) {
     194          if (targetGlobal) {
     195            perm = qap.BestKnownSolutions.SampleRandom(random);
     196          } else {
     197            perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
     198            var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
     199            _evaluatedSolutions++;
     200            var evalSol = new IntValue(0);
     201            QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), evalSol, qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     202            _evaluatedSolutions += evalSol.Value;
     203          }
     204        } else { // random
     205          BiasedShuffle(perm, random);
    125206        }
    126         if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75)
    127           permutations.Add(perm);
    128       }
    129 
    130       return permutations;
    131     }
    132 
    133     public static IEnumerable<List<Tuple<Permutation, double>>> Run(IRandom random, QuadraticAssignmentProblem qap, IEnumerable<Permutation> permutations, bool bestImprovement = true) {
     207        yield return (Permutation)perm.Clone();
     208      }
     209    }
     210
     211    private IEnumerable<List<Tuple<Permutation, double>>> Run(IEnumerable<Permutation> permutations) {
     212      if (Type == WalkType.LocalInverse) return RunInverse(permutations);
     213      return RunRegular(permutations);
     214    }
     215
     216    private IEnumerable<List<Tuple<Permutation, double>>> RunInverse(IEnumerable<Permutation> permutations) {
     217      var qap = (QuadraticAssignmentProblem)Problem;
     218      var min = qap.LowerBound.Value;
     219      var max = qap.AverageQuality.Value;
     220      var bestImprovement = BestImprovement;
     221
     222      foreach (var start in permutations) {
     223        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
     224        _evaluatedSolutions++;
     225
     226        // inverse walks are applied to all solutions
     227        Func<Tuple<Permutation, double>, IEnumerable<Tuple<Permutation, double>>> inverseNeighborFunc = (p) => RestrictedInverseNeighborhood(qap, p.Item1, p.Item2, start);
     228        var walk = DirectedWalk<Permutation>.WalkRestricted(qap.Maximization.Value, inverseNeighborFunc, start, startFitness, !bestImprovement);
     229        yield return walk.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();
     230      } // end paths
     231    }
     232
     233    private IEnumerable<List<Tuple<Permutation, double>>> RunRegular(IEnumerable<Permutation> permutations) {
    134234      var iter = permutations.GetEnumerator();
    135235      if (!iter.MoveNext()) yield break;
    136 
     236      var bestImprovement = BestImprovement;
     237
     238      var qap = (QuadraticAssignmentProblem)Problem;
    137239      var min = qap.LowerBound.Value;
    138240      var max = qap.AverageQuality.Value;
    139241
    140242      var start = iter.Current;
     243     
    141244      while (iter.MoveNext()) {
     245        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
     246        _evaluatedSolutions++;
    142247        var end = iter.Current;
    143248
    144         var walk = (bestImprovement ? BestDirectedWalk(qap, start, end) : FirstDirectedWalk(random, qap, start, end)).ToList();
    145         yield return walk.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();
     249        var invSol = new int[start.Length];
     250        Func<Tuple<Permutation, double>, IEnumerable<Tuple<Permutation, double>>> regularNeighborFunc = (p) => RestrictedNeighborhood(qap, p.Item1, p.Item2, end, invSol);
     251        var walk = DirectedWalk<Permutation>.WalkRestricted(qap.Maximization.Value, regularNeighborFunc, start, startFitness, !bestImprovement);
     252
     253        var trail = new List<Tuple<Permutation, double>>();
     254        foreach (var step in walk) {
     255          for (var i = 0; i < invSol.Length; i++)
     256            invSol[step.Item1[i]] = i;
     257          trail.Add(Tuple.Create(step.Item1, (step.Item2 - min) / (max - min)));
     258        }
     259        yield return trail;
     260
    146261        start = end;
    147262      } // end paths
    148263    }
    149264
    150     private static IEnumerable<Tuple<Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
    151       var N = qap.Weights.Rows;
    152       var sol = start;
    153       var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
    154       yield return Tuple.Create(sol, fitness);
    155 
    156       var invSol = GetInverse(sol);
    157       // we require at most N-1 steps to move from one permutation to another
    158       for (var step = 0; step < N - 1; step++) {
    159         var bestFitness = double.MaxValue;
    160         var bestIndex = -1;
    161         sol = (Permutation)sol.Clone();
    162         for (var index = 0; index < N; index++) {
    163           if (sol[index] == end[index]) continue;
    164           var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances);
    165           if (fit < bestFitness) { // QAP is minimization
    166             bestFitness = fit;
    167             bestIndex = index;
    168           }
     265    private IEnumerable<Tuple<Permutation, double>> RestrictedInverseNeighborhood(QuadraticAssignmentProblem qap, Permutation current, double currentFit, Permutation start) {
     266      var evalSolPerMove = 4.0 / current.Length;
     267      var N = current.Length;
     268      for (var index = 0; index < N; index++) {
     269        if (current[index] != start[index]) continue;
     270        for (var k = 0; k < N; k++) {
     271          if (k == index) continue;
     272          var fit = QAPSwap2MoveEvaluator.Apply(current, new Swap2Move(index, k), qap.Weights, qap.Distances);
     273          _evaluatedSolutions += evalSolPerMove;
     274          current.Swap(index, k);
     275          yield return Tuple.Create(current, currentFit + fit);
     276          current.Swap(index, k); // reverse
    169277        }
    170         if (bestIndex >= 0) {
    171           var prev = sol[bestIndex];
    172           Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
    173           fitness += bestFitness;
    174           yield return Tuple.Create(sol, fitness);
    175           invSol[prev] = invSol[end[bestIndex]];
    176           invSol[sol[bestIndex]] = bestIndex;
    177         } else break;
    178       }
    179     }
    180 
    181     private static IEnumerable<Tuple<Permutation, double>> FirstDirectedWalk(IRandom random, QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
    182       var N = qap.Weights.Rows;
    183       var sol = start;
    184       var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
    185       yield return Tuple.Create(sol, fitness);
    186 
    187       var invSol = GetInverse(sol);
    188       // randomize the order in which improvements are tried
    189       var order = Enumerable.Range(0, N).Shuffle(random).ToArray();
    190       // we require at most N-1 steps to move from one permutation to another
    191       for (var step = 0; step < N - 1; step++) {
    192         var bestFitness = double.MaxValue;
    193         var bestIndex = -1;
    194         sol = (Permutation)sol.Clone();
    195         for (var i = 0; i < N; i++) {
    196           var index = order[i];
    197           if (sol[index] == end[index]) continue;
    198           var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances);
    199           if (fit < bestFitness) { // QAP is minimization
    200             bestFitness = fit;
    201             bestIndex = index;
    202             if (bestFitness < 0) break;
    203           }
    204         }
    205         if (bestIndex >= 0) {
    206           var prev = sol[bestIndex];
    207           Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
    208           fitness += bestFitness;
    209           yield return Tuple.Create(sol, fitness);
    210           invSol[prev] = invSol[end[bestIndex]];
    211           invSol[sol[bestIndex]] = bestIndex;
    212         } else break;
    213       }
    214     }
    215 
    216     private static int[] GetInverse(Permutation p) {
    217       var inv = new int[p.Length];
    218       for (var i = 0; i < p.Length; i++) {
    219         inv[p[i]] = i;
    220       }
    221       return inv;
     278      }
     279    }
     280
     281    private IEnumerable<Tuple<Permutation, double>> RestrictedNeighborhood(QuadraticAssignmentProblem qap, Permutation current, double currentFit, Permutation target, int[] inverse) {
     282      var evalSolPerMove = 4.0 / current.Length;
     283      for (var index = 0; index < current.Length; index++) {
     284        if (current[index] == target[index]) continue;
     285        var k = inverse[target[index]];
     286        var fit = QAPSwap2MoveEvaluator.Apply(current, new Swap2Move(index, k), qap.Weights, qap.Distances);
     287        _evaluatedSolutions += evalSolPerMove;
     288        current.Swap(index, k);
     289        yield return Tuple.Create(current, currentFit + fit);
     290        current.Swap(index, k); // reverse
     291      }
    222292    }
    223293
Note: See TracChangeset for help on using the changeset viewer.