source: branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs @ 16096

Last change on this file since 16096 was 16096, checked in by abeham, 21 months ago

#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
File size: 13.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Problems.QuadraticAssignment;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Analysis.FitnessLandscape {
37  [Item("Directed Walk (QAP-specific)", "")]
38  [StorableClass]
39  public class QAPDirectedWalk : CharacteristicCalculator {
40
41    public enum WalkType { RandomRandom, RandomGlobal, RandomLocal, LocalLocal, LocalGlobal, LocalInverse }
42
43    private const string NBHOOD_STR = "Swap2";
44   
45    public IFixedValueParameter<IntValue> PathsParameter {
46      get { return (IFixedValueParameter<IntValue>)Parameters["Paths"]; }
47    }
48
49    public IFixedValueParameter<BoolValue> BestImprovementParameter {
50      get { return (IFixedValueParameter<BoolValue>)Parameters["BestImprovement"]; }
51    }
52
53    public IValueParameter<IntValue> SeedParameter {
54      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
55    }
56
57    public IFixedValueParameter<EnumValue<WalkType>> TypeParameter {
58      get { return (IFixedValueParameter<EnumValue<WalkType>>)Parameters["Type"]; }
59    }
60
61    public int Paths {
62      get { return PathsParameter.Value.Value; }
63      set { PathsParameter.Value.Value = value; }
64    }
65
66    public bool BestImprovement {
67      get { return BestImprovementParameter.Value.Value; }
68      set { BestImprovementParameter.Value.Value = value; }
69    }
70
71    public int? Seed {
72      get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; }
73      set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; }
74    }
75
76    public WalkType Type {
77      get { return TypeParameter.Value.Value; }
78      set { TypeParameter.Value.Value = value;}
79    }
80
81    [StorableConstructor]
82    private QAPDirectedWalk(bool deserializing) : base(deserializing) { }
83    private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
84    public QAPDirectedWalk() {
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
91      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)));
92      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)));
93      Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator."));
94      Parameters.Add(new FixedValueParameter<EnumValue<WalkType>>("Type", "Type of directed walk to perfom.", new EnumValue<WalkType>(WalkType.RandomRandom)));
95    }
96
97    public override IDeepCloneable Clone(Cloner cloner) {
98      return new QAPDirectedWalk(this, cloner);
99    }
100
101    public override bool CanCalculate() {
102      return Problem is QuadraticAssignmentProblem;
103    }
104
105    private double _evaluatedSolutions;
106
107    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() {
172      IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
173      var qap = (QuadraticAssignmentProblem)Problem;
174      var pathCount = Paths;
175
176      var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
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);
188          var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
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);
206        }
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) {
234      var iter = permutations.GetEnumerator();
235      if (!iter.MoveNext()) yield break;
236      var bestImprovement = BestImprovement;
237
238      var qap = (QuadraticAssignmentProblem)Problem;
239      var min = qap.LowerBound.Value;
240      var max = qap.AverageQuality.Value;
241
242      var start = iter.Current;
243     
244      while (iter.MoveNext()) {
245        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
246        _evaluatedSolutions++;
247        var end = iter.Current;
248
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
261        start = end;
262      } // end paths
263    }
264
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
277        }
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      }
292    }
293
294    // permutation must be strictly different in every position
295    private static void BiasedShuffle(Permutation p, IRandom random) {
296      for (var i = p.Length - 1; i > 0; i--) {
297        // Swap element "i" with a random earlier element (excluding itself)
298        var swapIndex = random.Next(i);
299        var h = p[swapIndex];
300        p[swapIndex] = p[i];
301        p[i] = h;
302      }
303    }
304  }
305}
Note: See TracBrowser for help on using the repository browser.