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/ProblemCharacteristicAnalysis/QAP
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • 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.