Free cookie consent management tool by TermsFeed Policy Generator

Changeset 16096


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
Files:
1 added
14 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

  • branches/2457_ExpertSystem/HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs

    r15031 r16096  
    33using System.Linq;
    44using System.Text.RegularExpressions;
     5using HeuristicLab.Common;
    56
    67namespace HeuristicLab.Problems.Instances.QAPLIB {
     8  public class OneSize10InstanceProvider : OneSizeInstanceProvider {
     9    public OneSize10InstanceProvider() : base(10) { }
     10  }
     11  public class OneSize25InstanceProvider : OneSizeInstanceProvider {
     12    public OneSize25InstanceProvider() : base(25) { }
     13  }
     14  public class OneSize50InstanceProvider : OneSizeInstanceProvider {
     15    public OneSize50InstanceProvider() : base(50) { }
     16  }
     17  public class OneSize100InstanceProvider : OneSizeInstanceProvider {
     18    public OneSize100InstanceProvider() : base(100) { }
     19  }
     20
    721  public class OneSizeInstanceProvider : ProblemInstanceProvider<QAPData> {
     22    public override string Name { get { return "One Size (n = " + Dimension + ")"; } }
     23    public override string Description { get { return "Instances from various libraries reduced to a dimension of " + Dimension + "."; } }
     24    public override Uri WebLink { get { return null; } }
     25    public override string ReferencePublication {
     26      get {
     27        return
     28@"A. Beham, E. Pitzer, S. Wagner, M. Affenzeller. 2017.
     29Integrating Exploratory Landscape Analysis into Metaheuristic Algorithms.
     30Lecture Notes in Computer Science 10671, Las Palmas de Gran Canaria, Spanien, pp. 473-480";
     31      }
     32    }
     33
     34    public int Dimension { get; private set; }
     35
     36    public OneSizeInstanceProvider(int dimension) {
     37      Dimension = dimension;
     38    }
     39
    840    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    941      var drezner = new DreznerQAPInstanceProvider();
    1042      foreach (var desc in drezner.GetDataDescriptors()) {
    1143        var dim = int.Parse(Regex.Match(desc.Name, "dre(?<g>\\d+)").Groups["g"].Value);
    12         if (dim < 25) continue;
    13         yield return new OneSizeDataDescriptor(desc.Name + (dim == 25 ? "" : "-25"), desc.Description, drezner, desc);
     44        if (dim < Dimension) continue;
     45        yield return new OneSizeDataDescriptor(desc.Name + (dim == Dimension ? "" : "-" + Dimension), desc.Description, drezner, desc);
    1446      }
    1547      // Microarray instances are all greater than 25 dimensions
    1648      var microarray = new MicroarrayQAPInstanceProvider();
    1749      foreach (var desc in microarray.GetDataDescriptors()) {
    18         yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, microarray, desc);
     50        var instance = microarray.LoadData(desc);
     51        if (instance.Dimension < Dimension) continue;
     52        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == Dimension ? "" : "-" + Dimension), desc.Description, microarray, desc);
    1953      }
    2054      var qaplib = new QAPLIBInstanceProvider();
    2155      foreach (var desc in qaplib.GetDataDescriptors()) {
    2256        var instance = qaplib.LoadData(desc);
    23         if (instance.Dimension < 25) continue;
    24         yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == 25 ? "" : "-25"), desc.Description, qaplib, desc);
     57        if (instance.Dimension < Dimension) continue;
     58        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == Dimension ? "" : "-" + Dimension), desc.Description, qaplib, desc);
    2559      }
    2660      // Taillard's instances are basically from the same distribution
    2761      // to avoid over-representation in the set only the tai27e are taken and reduced to 25 dimension
    2862      var taillard = new TaillardQAPInstanceProvider();
    29       foreach (var desc in taillard.GetDataDescriptors()) {
    30         if (!desc.Name.StartsWith("tai27e")) continue;
    31         yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, taillard, desc);
     63      var count = 0;
     64      foreach (var desc in taillard.GetDataDescriptors().OrderBy(x => x.Name, new NaturalStringComparer())) {
     65        var dim = int.Parse(Regex.Match(desc.Name, "tai(?<g>\\d+)e").Groups["g"].Value);
     66        if (dim < Dimension) continue;
     67        yield return new OneSizeDataDescriptor(desc.Name + (dim == Dimension ? "" : "-" + Dimension), desc.Description, taillard, desc);
     68        if (++count == 10) break;
    3269      }
    3370    }
    … …  
    3673      var desc = (OneSizeDataDescriptor)descriptor;
    3774      var data = desc.ActualProvider.LoadData(desc.ActualDescriptor);
    38       data.BestKnownAssignment = null;
    39       data.BestKnownQuality = null;
    40       if (data.Dimension <= 25) {
     75
     76      if (data.Dimension <= Dimension) {
    4177        return data;
    4278      }
    … …  
    4682      Shuffle(tmp, rand);
    4783      var throwAway = new bool[data.Dimension];
    48       foreach (var t in tmp.Take(data.Dimension - 25))
     84      foreach (var t in tmp.Take(data.Dimension - Dimension))
    4985        throwAway[t] = true;
    5086
    51       var weights = new double[25, 25];
    52       var distances = new double[25, 25];
     87      var weights = new double[Dimension, Dimension];
     88      var distances = new double[Dimension, Dimension];
    5389      var k = 0;
    5490      for (var i = 0; i < data.Dimension; i++) {
    … …  
    68104      data.BestKnownAssignment = null;
    69105      data.BestKnownQuality = null;
    70       data.Dimension = 25;
    71       data.Name += "-25";
    72       data.Description += " (reduced to 25 dimensions)";
     106      data.Dimension = Dimension;
     107      data.Name += "-" + Dimension;
     108      data.Description += " (reduced to " + Dimension + " dimensions)";
    73109
    74110      return data;
    75111    }
    76 
    77     public override string Name { get { return "One Size"; } }
    78     public override string Description { get { return string.Empty; } }
    79     public override Uri WebLink { get { return null; } }
    80     public override string ReferencePublication { get { return string.Empty; } }
    81112   
    82113    private static void Shuffle(int[] p, Random random) {

  • branches/2457_ExpertSystem/ProblemInstanceIdentifier/InstanceDescriptor.cs

    r15031 r16096  
    1 using System;
    2 using System.Collections.Generic;
     1using System.Collections.Generic;
    32using System.Linq;
    43using System.Text.RegularExpressions;
    5 using HeuristicLab.Analysis.FitnessLandscape;
    64using HeuristicLab.Common;
    7 using HeuristicLab.Encodings.PermutationEncoding;
    85using HeuristicLab.Problems.QuadraticAssignment;
    96
    … …  
    1613    public string[] FeatureNames { get; set; }
    1714    public double[] FeatureValues { get; set; }
     15
     16    public double DescriptionEffort { get; set; }
    1817   
    1918    private InstanceDescriptor() { }
    … …  
    3332      FeatureNames = (string[])other.FeatureNames.Clone();
    3433      FeatureValues = (double[]) other.FeatureValues.Clone();
     34      DescriptionEffort = other.DescriptionEffort;
    3535    }
    3636
    … …  
    4141        Dimension = qap.Weights.Rows,
    4242        FeatureNames = new string[0],
    43         FeatureValues = new double[0]
    44       };
    45     }
    46 
    47     public static InstanceDescriptor FromPaths(QuadraticAssignmentProblem qap, List<List<Tuple<Permutation, double>>> trajectories) {
    48       var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
    49 
    50       return new InstanceDescriptor() {
    51         Name = qap.Name,
    52         Cls = GetClass(qap.Name),
    53         Dimension = qap.Weights.Rows,
    54         FeatureNames = result.GetNames(),
    55         FeatureValues = result.GetValues()
     43        FeatureValues = new double[0],
     44        DescriptionEffort = 0
    5645      };
    5746    }

  • branches/2457_ExpertSystem/ProblemInstanceIdentifier/InstanceExplorer.cs

    r15031 r16096  
    11using System;
     2using System.Collections.Generic;
    23using System.Linq;
    3 using HeuristicLab.Algorithms.MemPR.Permutation;
    44using HeuristicLab.Analysis.FitnessLandscape;
    55using HeuristicLab.Data;
    66using HeuristicLab.Encodings.PermutationEncoding;
    77using HeuristicLab.Problems.QuadraticAssignment;
    8 using HeuristicLab.Random;
    98using HeuristicLab.SequentialEngine;
    109
    … …  
    2120  public class PathRelinkingExplorer : InstanceExplorer {
    2221    public int Paths { get; set; }
    23     public bool LocalOptima { get; set; }
     22    public QAPDirectedWalk.WalkType Type { get; set; }
    2423
    2524    public override string Name { get { return "Path-Relinking Explorer"; } }
    2625    public override int Effort { get { return Paths; } }
    2726
     27    public ISet<string> Features { get; set; }
     28
    2829    public PathRelinkingExplorer() {
    2930     
    … …  
    3132
    3233    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
    33       var walk = new QAPDirectedWalk {
     34      var calculator = new QAPDirectedWalk {
    3435        Problem = problem,
    3536        BestImprovement = true,
    3637        Paths = Paths,
    3738        Seed = seed,
    38         LocalOptima = LocalOptima
    39       };
    40       var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value);
    41 
    42       return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
    43         features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    44     }
    45   }
    46 
    47   public class PathRelinkingOldFeaturedExplorer : InstanceExplorer {
    48     public int Paths { get; set; }
    49     public bool LocalOptima { get; set; }
    50 
    51     public override string Name { get { return "Path-Relinking Explorer"; } }
    52     public override int Effort { get { return Paths; } }
    53 
    54     public PathRelinkingOldFeaturedExplorer() {
    55 
    56     }
    57 
    58     public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
    59       var random = new MersenneTwister();
    60       var samples = QAPDirectedWalk.CalculateRelinkingPoints(random, problem, Paths, LocalOptima);
    61       var trajectories = QAPDirectedWalk.Run(random, problem, samples);
    62 
    63       double avgAc1 = 0, avgCorLen = 0, avgIc = 0, avgDbi = 0, avgPic = 0, avgIs = 0, avgDiv = 0,
    64         avgReg = 0, avgEnt = 0, avgPkIc = 0, avgPkDbi = 0;
    65       int count = 0;
    66       foreach (var t in trajectories) {
    67         var trail = t.Select(x => x.Item2).ToArray();
    68         if (trail.Length < 4) continue;
    69         count++;
    70         double[] acf;
    71         var len = RuggednessCalculator.CalculateCorrelationLength(trail, out acf);
    72         avgAc1 += acf[0];
    73         avgCorLen += len;
    74         var analysis = new InformationAnalysis(trail, 20, 2);
    75         avgIc += analysis.InformationContent[0];
    76         avgDbi += analysis.DensityBasinInformation[0];
    77         avgPic += analysis.PartialInformationContent[0];
    78         avgIs += analysis.InformationStability;
    79         avgDiv += analysis.Diversity;
    80         avgReg += analysis.Regularity;
    81         avgEnt += analysis.TotalEntropy[0];
    82         avgPkIc += analysis.PeakInformationContent.Value;
    83         avgPkDbi += analysis.PeakDensityBasinInformation.Value;
    84       }
    85       avgAc1 /= count;
    86       avgCorLen /= count;
    87       avgIc /= count;
    88       avgDbi /= count;
    89       avgPic /= count;
    90       avgIs /= count;
    91       avgDiv /= count;
    92       avgReg /= count;
    93       avgEnt /= count;
    94       avgPkIc /= count;
    95       avgPkDbi /= count;
    96 
    97       return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
    98         new[] { "Autocorrelation(1)", "CorrelationLength", "InformationContent", "DensityBasinInformation",
    99           "PartialInformationContent", "InformationStability", "Diversity", "Regularity", "TotalEntropy",
    100           "PeakInformationContent", "PeakDensityBasinInformation" },
    101         new[] { avgAc1, avgCorLen, avgIc, avgDbi,
    102           avgPic, avgIs, avgDiv, avgReg, avgEnt,
    103           avgPkIc, avgPkDbi });
    104     }
    105   }
    106 
     39        Type = Type
     40      };
     41      if (Features != null && Features.Count > 0) {
     42        foreach (var c in calculator.Characteristics.ToList()) {
     43          calculator.Characteristics.SetItemCheckedState(c, Features.Contains(c.Value));
     44        }
     45      }
     46      var result = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
     47      var evaluations = ((IntValue)result["EvaluatedSolutions"]).Value;
     48      result.Remove("EvaluatedSolutions");
     49      if (Features != null && result.Count != Features.Count) throw new InvalidOperationException("Not all features in results");
     50
     51      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
     52        result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray()) { DescriptionEffort = evaluations };
     53    }
     54  }
    10755
    10856  public class RandomWalkExplorer : InstanceExplorer {
    … …  
    11159    public override string Name { get { return "Random-Walk Explorer"; } }
    11260    public override int Effort { get { return Iterations; } }
     61
     62    public ISet<string> Features { get; set; }
    11363
    11464    public RandomWalkExplorer() {
    … …  
    12777      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
    12878      var calculator = new RandomWalkCalculator(walk) { Problem = problem };
    129       var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
    130      
    131       return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
    132         features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
     79      foreach (var c in calculator.Characteristics.ToList()) {
     80        calculator.Characteristics.SetItemCheckedState(c, Features.Contains(c.Value));
     81      }
     82      var result = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
     83      if (Features != null && result.Count != Features.Count) throw new InvalidOperationException("Not all features in results");
     84
     85      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
     86        result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    13387    }
    13488  }
    … …  
    13993
    14094    public override string Name { get { return "Adaptive-Walk Explorer"; } }
    141     public override int Effort { get { return Iterations * SampleSize; } }
     95    private int _effort;
     96    public override int Effort { get { return _effort; } }
     97
     98    public ISet<string> Features { get; set; }
    14299
    143100    public AdaptiveWalkExplorer() {
    144 
     101      _effort = 0;
    145102    }
    146103
    … …  
    157114      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
    158115      var calculator = new AdaptiveWalkCalculator(walk) { Problem = problem };
    159       var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
    160 
    161       return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
    162         features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
     116      foreach (var c in calculator.Characteristics.ToList()) {
     117        calculator.Characteristics.SetItemCheckedState(c, Features.Contains(c.Value));
     118      }
     119      var result = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
     120      if (Features != null && result.Count != Features.Count) throw new InvalidOperationException("Not all features in results");
     121
     122      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
     123        result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    163124    }
    164125  }
    … …  
    170131    public override string Name { get { return "Up/Down-Walk Explorer"; } }
    171132    public override int Effort { get { return Iterations * SampleSize; } }
     133
     134    public ISet<string> Features { get; set; }
    172135
    173136    public UpDownWalkExplorer() {
    … …  
    187150      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
    188151      var calculator = new UpDownWalkCalculator(walk) {  Problem = problem };
    189       var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
    190 
    191       return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
    192         features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    193     }
    194   }
    195 
     152      foreach (var c in calculator.Characteristics.ToList()) {
     153        calculator.Characteristics.SetItemCheckedState(c, Features.Contains(c.Value));
     154      }
     155      var result = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
     156      if (Features != null && result.Count != Features.Count) throw new InvalidOperationException("Not all features in results");
     157
     158      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
     159        result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray());
     160    }
     161  }
     162  /*
    196163  public class MemPRExplorer : InstanceExplorer {
    197164    public int Seconds { get; set; }
    … …  
    230197      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows, resultNames, result);
    231198    }
    232   }
     199  }*/
    233200}

  • branches/2457_ExpertSystem/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj

    r15694 r16096  
    9797  </ItemGroup>
    9898  <ItemGroup>
    99     <ProjectReference Include="..\HeuristicLab.Algorithms.MemPR\3.3\HeuristicLab.Algorithms.MemPR-3.3.csproj">
    100       <Project>{9d274421-6332-4fbc-aae4-467ace27c368}</Project>
    101       <Name>HeuristicLab.Algorithms.MemPR-3.3</Name>
    102     </ProjectReference>
    10399    <ProjectReference Include="..\HeuristicLab.Analysis.FitnessLandscape\3.3\HeuristicLab.Analysis.FitnessLandscape-3.3.csproj">
    104100      <Project>{5fbdcd4a-3c2a-4ec6-83ce-34b29f43621a}</Project>

  • branches/2457_ExpertSystem/ProblemInstanceIdentifier/Program.cs

    r15031 r16096  
    22using System.Collections.Generic;
    33using System.Globalization;
     4using System.IO;
    45using System.Linq;
    56using System.Threading.Tasks;
    6 using HeuristicLab.PluginInfrastructure;
    7 using HeuristicLab.Problems.Instances;
     7using HeuristicLab.Analysis.FitnessLandscape;
    88using HeuristicLab.Problems.Instances.QAPLIB;
    99using HeuristicLab.Problems.QuadraticAssignment;
    … …  
    1313  class Program {
    1414    static void Main(string[] args) {
    15       //var instances = Get20DifferentClasses();
    16       var instances = GetSomeRandomInstances(50, 13);
    1715
    1816      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
    … …  
    2119      }*/
    2220
    23       var prExplorer = new PathRelinkingExplorer() {
    24         LocalOptima = false,
    25         Paths = 200
    26       };
    27       var prOldExplorer = new PathRelinkingOldFeaturedExplorer() {
    28         LocalOptima = false,
    29         Paths = 200
    30       };
    31 
    32       var prLocalExplorer = new PathRelinkingExplorer() {
    33         LocalOptima = true,
    34         Paths = 200
    35       };
    36       var prOldLocalExplorer = new PathRelinkingOldFeaturedExplorer() {
    37         LocalOptima = true,
    38         Paths = 200
    39       };
    40 
    41       var memPrExplorer = new MemPRExplorer() {
    42         IncludeLocalSearch = false,
    43         Seconds = 10
    44       };
    45 
    46       //var training = GenerateData(instances, prOldExplorer, parallel: true);
     21      var dwFeatureSets = new Dictionary<string, HashSet<string>>() {
     22        { "SBF", new HashSet<string>() { "Sharpness", "Bumpiness", "Flatness" } },
     23        { "FRQ", new HashSet<string>() { "DownQ2", "NeutQ2", "UpQ2", "DownQ1", "NeutQ1", "UpQ1", "DownQ3", "NeutQ3", "UpQ3" } },
     24        { "SBF+FRQ", new HashSet<string>() { "Sharpness", "Bumpiness", "Flatness", "DownQ2", "NeutQ2", "UpQ2", "DownQ1", "NeutQ1", "UpQ1", "DownQ3", "NeutQ3", "UpQ3" } },
     25        { "RUG", new HashSet<string>() { "AutoCorrelation1", "CorrelationLength" } },
     26        { "IAL", new HashSet<string>() { "InformationContent", "DensityBasinInformation", "PartialInformationContent", "Regularity", "TotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation" } },
     27        { "RUG+IAL", new HashSet<string>() { "AutoCorrelation1", "CorrelationLength", "InformationContent", "DensityBasinInformation", "PartialInformationContent", "Regularity", "TotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation" } },
     28        { "SBF+IAL", new HashSet<string>() { "Sharpness", "Bumpiness", "Flatness", "InformationContent", "DensityBasinInformation", "PartialInformationContent", "Regularity", "TotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation" } },
     29        { "FRQ+IAL", new HashSet<string>() { "DownQ2", "NeutQ2", "UpQ2", "DownQ1", "NeutQ1", "UpQ1", "DownQ3", "NeutQ3", "UpQ3", "InformationContent", "DensityBasinInformation", "PartialInformationContent", "Regularity", "TotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation" } },
     30        { "SBF+FRQ+IAL", new HashSet<string>() { "Sharpness", "Bumpiness", "Flatness", "DownQ2", "NeutQ2", "UpQ2", "DownQ1", "NeutQ1", "UpQ1", "DownQ3", "NeutQ3", "UpQ3", "InformationContent", "DensityBasinInformation", "PartialInformationContent", "Regularity", "TotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation" } },
     31        { "SBF+FRQ+RUG+IAL", new HashSet<string>() { "Sharpness", "Bumpiness", "Flatness", "DownQ2", "NeutQ2", "UpQ2", "DownQ1", "NeutQ1", "UpQ1", "DownQ3", "NeutQ3", "UpQ3", "AutoCorrelation1", "CorrelationLength", "InformationContent", "DensityBasinInformation", "PartialInformationContent", "Regularity", "TotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation" } },
     32      };
     33
     34      var dwTypes = new Dictionary<string, QAPDirectedWalk.WalkType> {
     35        { "(rr)-dw", QAPDirectedWalk.WalkType.RandomRandom },
     36        { "(rl)-dw", QAPDirectedWalk.WalkType.RandomLocal },
     37        { "(ll)-dw", QAPDirectedWalk.WalkType.LocalLocal },
     38        { "(li)-dw", QAPDirectedWalk.WalkType.LocalInverse }
     39      };
     40
     41      var dwPaths = new List<int> { 1, 2, 5, 10, 20, 50, 100, 200, 500 };
     42
     43      var random = new Random();
     44      using (var writer = File.CreateText("results.csv")) {
     45        writer.AutoFlush = true;
     46        var header = string.Format("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6}\t{7}\t{8}\t{9}\t{10}\t{11}",
     47          "Rep", "FSet", "Type", "TrainEff", "TestEff", "ExCnt", "ExRnk", "ClsCnt", "ClsRnk", "TotCnt", "TrainEff2", "TestEff2");
     48        writer.WriteLine(header);
     49        Console.WriteLine(header);
     50        foreach (var dim in new[] { 20, 30, 40, 50, 100 }) {
     51          foreach (var feat in dwFeatureSets) {
     52            foreach (var type in dwTypes) {
     53              for (var rep = 0; rep < 10; rep++) {
     54                var instances = GetSomeRandomInstances(dimension: dim, totalInstances: 20, seed: random.Next());
     55
     56                var explorers = from p in dwPaths
     57                                select new PathRelinkingExplorer() { Features = feat.Value, Paths = p, Type = type.Value };
     58                ExploreMatching(writer, instances, explorers.ToArray(), explorers.ToArray(), string.Format("{0}\t{1}\t{2}", rep, feat.Key, type.Key));
     59              }
     60            }
     61          }
     62        }
     63      }
     64
     65
     66      //var training = GenerateData(instances, rrDwExplorer, parallel: true);
    4767      //var standardizer = InstancesStandardizer.CreateAndApply(training);
    48       //var test = GenerateData(instances, prOldExplorer, parallel: true);
     68      //var test = GenerateData(instances, rrDwExplorer, parallel: true);
    4969      //standardizer.Apply(test);
    5070      //PrintMatchResult(Compare(training, test));
    … …  
    6585      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
    6686      //parallel: true);
    67       Console.WriteLine("=== Up/Down Walk ===");
    68       ExploreMatching(instances,
    69       new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
    70       new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
    71       parallel: true);
    72     }
    73 
    74     private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances, int seed) {
     87      //Console.WriteLine("=== Up/Down Walk ===");
     88      //ExploreMatching(instances,
     89      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
     90      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
     91      //parallel: true);
     92    }
     93
     94    private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int dimension, int totalInstances, int seed) {
    7595      var sync = new object();
    76       var provider = new OneSizeInstanceProvider();
     96      var provider = new OneSizeInstanceProvider(dimension);
    7797      var instances = new List<QuadraticAssignmentProblem>();
    7898      var random = new FastRandom(seed);
    … …  
    87107        }
    88108      });
    89       return instances;
    90     }
    91 
    92     private static HashSet<string> selectedInstances = new HashSet<string>() {
    93       "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
    94       "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50",
    95       "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
    96     };
    97     private static List<QuadraticAssignmentProblem> Get20DifferentClasses() {
    98       var sync = new object();
    99 
    100       var qapProviders = ApplicationManager.Manager.GetInstances<ProblemInstanceProvider<QAPData>>().ToList();
    101       var instances = new List<QuadraticAssignmentProblem>();
    102       foreach (var provider in qapProviders) {
    103         if (provider is TaillardQAPInstanceProvider) continue;
    104         Parallel.ForEach(provider.GetDataDescriptors(), desc => {
    105           if (!selectedInstances.Contains(desc.Name)) return;
    106           //if (desc.Name == "esc16f") return;
    107           var qapData = provider.LoadData(desc);
    108           //if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
    109           var qap = new QuadraticAssignmentProblem();
    110           qap.Load(qapData);
    111           lock (sync) {
    112             instances.Add(qap);
    113           }
    114         });
    115       }
    116109      return instances;
    117110    }
    … …  
    155148        TotalCount = totalCount,
    156149        ExactAverageRank = exactRank / (double)totalCount,
    157         ClsAverageRank = clsRank / (double)totalCount
    158       };
    159     }
    160 
    161     private static void PrintMatchResult(MatchResult result) {
    162       Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4:F2}",
    163         result.ExactCount, result.ClsCount, result.TotalCount,
    164         result.ExactAverageRank, result.ClsAverageRank);
     150        ClsAverageRank = clsRank / (double)totalCount,
     151        TrainingDescriptionEffort = training.Average(x => x.DescriptionEffort),
     152        TestDescriptionEffort = test.Average(x => x.DescriptionEffort)
     153      };
    165154    }
    166155
    … …  
    168157      using (var iter = instances.GetEnumerator()) {
    169158        if (!iter.MoveNext()) return;
    170         Console.WriteLine(string.Join(";", new[] {"Name", "Cls", "Dimension"}
     159        Console.WriteLine(string.Join(";", new[] {"Name", "Cls", "Dimension", "Effort"}
    171160          .Concat(iter.Current != null ? iter.Current.FeatureNames : new [] { "(null)" })));
    172161        do {
    … …  
    178167    private static void PrintInstanceLine(InstanceDescriptor instance) {
    179168      Console.WriteLine(string.Join(";",
    180         new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)}
     169        new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture), instance.DescriptionEffort.ToString(CultureInfo.CurrentCulture)}
    181170          .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture)))));
    182171    }
    183172
    184     private static void ExploreMatching(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] trainingExplorers, InstanceExplorer[] testExporers, bool parallel = false) {
     173    private static void ExploreMatching(StreamWriter writer, List<QuadraticAssignmentProblem> instances, InstanceExplorer[] trainingExplorers, InstanceExplorer[] testExporers, string info, bool parallel = false) {
    185174      var sync = new object();
    186175
    … …  
    223212          var result = Compare(point.Training.Value.Item2, normalizedTest);
    224213          lock (sync) {
    225             Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}",
    226               point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
    227               result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount);
     214            string output = string.Format("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}\t{7}\t{8}\t{9}",
     215              info, point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
     216              result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount,
     217              result.TrainingDescriptionEffort, result.TestDescriptionEffort);
     218            writer.WriteLine(output);
     219            Console.WriteLine(output);
    228220          }
    229221        });
    … …  
    233225          point.Training.Value.Item1.Apply(normalizedTest);
    234226          var result = Compare(point.Training.Value.Item2, normalizedTest);
    235           Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}",
    236             point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
    237             result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount);
     227          string output = string.Format("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}\t{7}\t{8}\t{9}",
     228            info, point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
     229            result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount,
     230            result.TrainingDescriptionEffort, result.TestDescriptionEffort);
     231          writer.WriteLine(output);
     232          Console.WriteLine(output);
    238233        }
    239234      }
    … …  
    246241      public double ExactAverageRank { get; set; }
    247242      public double ClsAverageRank { get; set; }
     243
     244      public double TrainingDescriptionEffort { get; set; }
     245      public double TestDescriptionEffort { get; set; }
    248246    }
    249247  }
Note: See TracChangeset for help on using the changeset viewer.