Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2457_ExpertSystem/WalkExporter/DirectedWalk.cs @ 18078

Last change on this file since 18078 was 16955, checked in by abeham, 5 years ago

#2457: worked on thesis

File size: 11.2 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Threading;
5using HeuristicLab.Analysis.FitnessLandscape;
6using HeuristicLab.Core;
7using HeuristicLab.Data;
8using HeuristicLab.Encodings.PermutationEncoding;
9using HeuristicLab.Problems.Instances;
10using HeuristicLab.Problems.Instances.QAPLIB;
11using HeuristicLab.Problems.QuadraticAssignment;
12using HeuristicLab.Random;
13using static HeuristicLab.Analysis.FitnessLandscape.QAPDirectedWalk;
14
15namespace WalkExporter {
16  class DirectedWalk {
17    public int? Seed;
18    public QuadraticAssignmentProblem Problem;
19    public WalkType Type;
20    public int Paths;
21    public double EvaluatedSolutionEquiv;
22    public bool BestImprovement;
23
24
25    public static (Experiment experiment, Dictionary<int, Knowledgebase> training, Dictionary<int, Knowledgebase> test)
26        PerformExperiment(WalkType type, bool bestImprovement = true) {
27
28      string typeStr;
29      switch (type) {
30        case WalkType.RandomRandom: typeStr = "(rr)-dw"; break;
31        case WalkType.RandomLocal: typeStr = "(rl)-dw"; break;
32        case WalkType.LocalLocal: typeStr = "(ll)-dw"; break;
33        case WalkType.LocalInverse: typeStr = "(li)-dw"; break;
34        default: throw new ArgumentException(string.Format("unknown type {0}", type), "type");
35      }
36      var experiment = new Experiment() { Algorithm = typeStr, Trials = new List<Exploration>() };
37      var training = new[] { 1, 2, 5, 10, 20, 50, 100, 200, 500 }.ToDictionary(x => x, x => new Knowledgebase() { Problems = new List<ProblemInstanceDescriptor>() });
38      var test = new[] { 1, 2, 5, 10, 20, 50, 100, 200, 500 }.ToDictionary(x => x, x => new Knowledgebase() { Problems = new List<ProblemInstanceDescriptor>() });
39
40      foreach (var dimension in new[] { 20, 30, 40 }) {
41        var provider = new OneSizeInstanceProvider(dimension);
42        foreach (var desc in provider.GetDataDescriptors()) {
43          var qapData = provider.LoadData(desc);
44
45          var qap = new QuadraticAssignmentProblem();
46          qap.Load(qapData);
47          var calculator = new DirectedWalk() {
48            Problem = qap,
49            BestImprovement = bestImprovement,
50            Paths = 1000,
51            Seed = 42,
52            Type = type
53          };
54          var solutions = calculator.CalculateRelinkingPoints().ToList();
55          var walk = calculator.Run(solutions).ToList();
56
57          var exploration = new Exploration() { Problem = qapData.Name, Dimension = qapData.Dimension, Walks = new List<Walk>() };
58          foreach (var w in walk) {
59            exploration.Walks.Add(new Walk() {
60              QualityTrail = w.Select(x => x.Item2).ToList()
61            });
62          }
63          experiment.Trials.Add(exploration);
64          AddToKnowledgeBase(training, qapData, calculator, walk, 0);
65          AddToKnowledgeBase(test, qapData, calculator, walk, 500);
66        }
67      }
68      return (experiment, training, test);
69    }
70
71    private static void AddToKnowledgeBase(Dictionary<int, Knowledgebase> training, QAPData qapData, DirectedWalk calculator, List<List<Tuple<Permutation, double>>> walk, int start) {
72      foreach (var t in training.Keys) {
73        var kb = training[t];
74        var sbf = CurveAnalysis<Permutation>.GetCharacteristics(walk.Skip(start).Take(t), (left, right) => (1.0 - HammingSimilarityCalculator.CalculateSimilarity(left, right)) * left.Length);
75        var trail = walk.Skip(start).Take(t).SelectMany(x => x).Select(x => x.Item2).ToArray();
76        var ia = new InformationAnalysis(trail);
77        var clen = RuggednessCalculator.CalculateCorrelationLength(trail, out double[] acf);
78
79        var pid = new ProblemInstanceDescriptor() {
80          Name = qapData.Name,
81          Class = Util.GetGeneratorClass(qapData.Name),
82          Dimension = qapData.Dimension,
83          DescriptionEffort = calculator.EvaluatedSolutionEquiv / 1000 * t,
84          Features = new List<KeyValue>()
85        };
86        pid.Features.Add(new KeyValue { Key = "AC1", ContinuousValue = acf[1] });
87        pid.Features.Add(new KeyValue { Key = "CorrelationLength", DiscreteValue = clen });
88        foreach (var f in CurveAnalysisResult.AllFeatures.Zip(sbf.GetValues(), (a, b) => new { Feature = a, Value = b })) {
89          pid.Features.Add(new KeyValue { Key = f.Feature.ToString(), ContinuousValue = f.Value });
90        }
91        foreach (var f in ia.GetFeatures()) {
92          if (f.Item2 is double d) pid.Features.Add(new KeyValue { Key = f.Item1, ContinuousValue = d });
93          else if (f.Item2 is int i) pid.Features.Add(new KeyValue { Key = f.Item1, DiscreteValue = i });
94        }
95
96        kb.Problems.Add(pid);
97      }
98    }
99
100    public IEnumerable<Permutation> CalculateRelinkingPoints() {
101      IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
102      var pathCount = Paths;
103
104      var perm = new Permutation(PermutationTypes.Absolute, Problem.Weights.Rows, random);
105      var startLocal = Type == WalkType.LocalGlobal || Type == WalkType.LocalLocal;
106      var targetLocal = Type == WalkType.LocalLocal || Type == WalkType.RandomLocal;
107      var targetGlobal = Type == WalkType.LocalGlobal || Type == WalkType.RandomGlobal;
108      var inverseWalk = Type == WalkType.LocalInverse;
109
110      if (Type == WalkType.LocalInverse) pathCount--; // inverse walks equal one walk per solution
111      for (var i = 0; i <= pathCount; i++) {
112        var start = i % 2 == 0;
113        var target = i % 2 == 1;
114        if (inverseWalk || start && startLocal) {
115          perm = new Permutation(PermutationTypes.Absolute, Problem.Weights.Rows, random);
116          var fit = new DoubleValue(QAPEvaluator.Apply(perm, Problem.Weights, Problem.Distances));
117          EvaluatedSolutionEquiv++;
118          var evalSol = new IntValue(0);
119          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, Problem.Weights, Problem.Distances, fit, new IntValue(0), evalSol, Problem.Maximization.Value, int.MaxValue, CancellationToken.None);
120          EvaluatedSolutionEquiv += evalSol.Value;
121        } else if (target && (targetLocal || targetGlobal)) {
122          if (targetGlobal) {
123            perm = Problem.BestKnownSolutions.SampleRandom(random);
124          } else {
125            perm = new Permutation(PermutationTypes.Absolute, Problem.Weights.Rows, random);
126            var fit = new DoubleValue(QAPEvaluator.Apply(perm, Problem.Weights, Problem.Distances));
127            EvaluatedSolutionEquiv++;
128            var evalSol = new IntValue(0);
129            QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, Problem.Weights, Problem.Distances, fit, new IntValue(0), evalSol, Problem.Maximization.Value, int.MaxValue, CancellationToken.None);
130            EvaluatedSolutionEquiv += evalSol.Value;
131          }
132        } else { // random
133          BiasedShuffle(perm, random);
134        }
135        yield return (Permutation)perm.Clone();
136      }
137    }
138
139    public IEnumerable<List<Tuple<Permutation, double>>> Run(IEnumerable<Permutation> permutations) {
140      if (Type == WalkType.LocalInverse) return RunInverse(permutations);
141      return RunRegular(permutations);
142    }
143
144    private IEnumerable<List<Tuple<Permutation, double>>> RunInverse(IEnumerable<Permutation> permutations) {
145      var qap = (QuadraticAssignmentProblem)Problem;
146      var min = qap.LowerBound.Value;
147      var max = qap.AverageQuality.Value;
148      var bestImprovement = BestImprovement;
149
150      foreach (var start in permutations) {
151        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
152        EvaluatedSolutionEquiv++;
153
154        // inverse walks are applied to all solutions
155        Func<Tuple<Permutation, double>, IEnumerable<Tuple<Permutation, double>>> inverseNeighborFunc = (p) => RestrictedInverseNeighborhood(qap, p.Item1, p.Item2, start);
156        var walk = DirectedWalk<Permutation>.WalkRestricted(qap.Maximization.Value, inverseNeighborFunc, start, startFitness, !bestImprovement);
157        yield return walk.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();
158      } // end paths
159    }
160
161    private IEnumerable<List<Tuple<Permutation, double>>> RunRegular(IEnumerable<Permutation> permutations) {
162      var iter = permutations.GetEnumerator();
163      if (!iter.MoveNext()) yield break;
164      var bestImprovement = BestImprovement;
165
166      var qap = (QuadraticAssignmentProblem)Problem;
167      var min = qap.LowerBound.Value;
168      var max = qap.AverageQuality.Value;
169
170      var start = iter.Current;
171
172      while (iter.MoveNext()) {
173        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
174        EvaluatedSolutionEquiv++;
175        var end = iter.Current;
176
177        var invSol = new int[start.Length];
178        Func<Tuple<Permutation, double>, IEnumerable<Tuple<Permutation, double>>> regularNeighborFunc = (p) => RestrictedNeighborhood(qap, p.Item1, p.Item2, end, invSol);
179        var walk = DirectedWalk<Permutation>.WalkRestricted(qap.Maximization.Value, regularNeighborFunc, start, startFitness, !bestImprovement);
180
181        var trail = new List<Tuple<Permutation, double>>();
182        foreach (var step in walk) {
183          for (var i = 0; i < invSol.Length; i++)
184            invSol[step.Item1[i]] = i;
185          trail.Add(Tuple.Create(step.Item1, (step.Item2 - min) / (max - min)));
186        }
187        yield return trail;
188
189        start = end;
190      } // end paths
191    }
192
193    private IEnumerable<Tuple<Permutation, double>> RestrictedInverseNeighborhood(QuadraticAssignmentProblem qap, Permutation current, double currentFit, Permutation start) {
194      var evalSolPerMove = 4.0 / current.Length;
195      var N = current.Length;
196      for (var index = 0; index < N; index++) {
197        if (current[index] != start[index]) continue;
198        for (var k = 0; k < N; k++) {
199          if (k == index) continue;
200          var fit = QAPSwap2MoveEvaluator.Apply(current, new Swap2Move(index, k), qap.Weights, qap.Distances);
201          EvaluatedSolutionEquiv += evalSolPerMove;
202          current.Swap(index, k);
203          yield return Tuple.Create(current, currentFit + fit);
204          current.Swap(index, k); // reverse
205        }
206      }
207    }
208
209    private IEnumerable<Tuple<Permutation, double>> RestrictedNeighborhood(QuadraticAssignmentProblem qap, Permutation current, double currentFit, Permutation target, int[] inverse) {
210      var evalSolPerMove = 4.0 / current.Length;
211      for (var index = 0; index < current.Length; index++) {
212        if (current[index] == target[index]) continue;
213        var k = inverse[target[index]];
214        var fit = QAPSwap2MoveEvaluator.Apply(current, new Swap2Move(index, k), qap.Weights, qap.Distances);
215        EvaluatedSolutionEquiv += evalSolPerMove;
216        current.Swap(index, k);
217        yield return Tuple.Create(current, currentFit + fit);
218        current.Swap(index, k); // reverse
219      }
220    }
221
222    // permutation must be strictly different in every position
223    private static void BiasedShuffle(Permutation p, IRandom random) {
224      for (var i = p.Length - 1; i > 0; i--) {
225        // Swap element "i" with a random earlier element (excluding itself)
226        var swapIndex = random.Next(i);
227        var h = p[swapIndex];
228        p[swapIndex] = p[i];
229        p[i] = h;
230      }
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.