source: branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs @ 15031

Last change on this file since 15031 was 15031, checked in by abeham, 3 years ago

#2457: worked on code for eurocast paper

File size: 9.6 KB
Line 
1using System;
2using System.Linq;
3using HeuristicLab.Algorithms.MemPR.Permutation;
4using HeuristicLab.Analysis.FitnessLandscape;
5using HeuristicLab.Data;
6using HeuristicLab.Encodings.PermutationEncoding;
7using HeuristicLab.Problems.QuadraticAssignment;
8using HeuristicLab.Random;
9using HeuristicLab.SequentialEngine;
10
11namespace ProblemInstanceIdentifier {
12  public abstract class InstanceExplorer {
13
14    public abstract string Name { get; }
15    public abstract int Effort { get; }
16    protected InstanceExplorer() { }
17
18    public abstract InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null);
19  }
20
21  public class PathRelinkingExplorer : InstanceExplorer {
22    public int Paths { get; set; }
23    public bool LocalOptima { get; set; }
24
25    public override string Name { get { return "Path-Relinking Explorer"; } }
26    public override int Effort { get { return Paths; } }
27
28    public PathRelinkingExplorer() {
29     
30    }
31
32    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
33      var walk = new QAPDirectedWalk {
34        Problem = problem,
35        BestImprovement = true,
36        Paths = Paths,
37        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
107
108  public class RandomWalkExplorer : InstanceExplorer {
109    public int Iterations { get; set; }
110
111    public override string Name { get { return "Random-Walk Explorer"; } }
112    public override int Effort { get { return Iterations; } }
113
114    public RandomWalkExplorer() {
115
116    }
117
118    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
119      var walk = new RandomWalk() {
120        SeedParameter = { Value = { Value = seed ?? 0 } },
121        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
122        MaximumIterationsParameter = { Value = { Value = Iterations } },
123        RepetitionsParameter = { Value = { Value = 1 } }
124      };
125      walk.Problem = problem;
126      walk.Engine = new SequentialEngine();
127      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
128      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());
133    }
134  }
135
136  public class AdaptiveWalkExplorer : InstanceExplorer {
137    public int Iterations { get; set; }
138    public int SampleSize { get; set; }
139
140    public override string Name { get { return "Adaptive-Walk Explorer"; } }
141    public override int Effort { get { return Iterations * SampleSize; } }
142
143    public AdaptiveWalkExplorer() {
144
145    }
146
147    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
148      var walk = new AdaptiveWalk() {
149        SeedParameter = { Value = { Value = seed ?? 0 } },
150        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
151        MaximumIterationsParameter = { Value = { Value = Iterations } },
152        RepetitionsParameter = { Value = { Value = 1 } },
153        SampleSizeParameter = { Value = { Value = SampleSize } }
154      };
155      walk.Problem = problem;
156      walk.Engine = new SequentialEngine();
157      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
158      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());
163    }
164  }
165
166  public class UpDownWalkExplorer : InstanceExplorer {
167    public int Iterations { get; set; }
168    public int SampleSize { get; set; }
169
170    public override string Name { get { return "Up/Down-Walk Explorer"; } }
171    public override int Effort { get { return Iterations * SampleSize; } }
172
173    public UpDownWalkExplorer() {
174
175    }
176
177    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
178      var walk = new UpDownWalk() {
179        SeedParameter = { Value = { Value = seed ?? 0 } },
180        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
181        MaximumIterationsParameter = { Value = { Value = Iterations } },
182        RepetitionsParameter = { Value = { Value = 1 } },
183        SampleSizeParameter = { Value = { Value = SampleSize } }
184      };
185      walk.Problem = problem;
186      walk.Engine = new SequentialEngine();
187      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
188      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
196  public class MemPRExplorer : InstanceExplorer {
197    public int Seconds { get; set; }
198
199    public bool IncludeLocalSearch { get; set; }
200
201    public override string Name { get { return "MemPR Explorer"; } }
202    public override int Effort { get { return Seconds; } }
203
204    public MemPRExplorer() {
205
206    }
207
208    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
209      var memPr = new PermutationMemPR();
210      memPr.Problem = problem;
211      memPr.Prepare(true);
212      memPr.MaximumExecutionTime = TimeSpan.FromSeconds(Seconds);
213      memPr.SetSeedRandomly = !seed.HasValue;
214      memPr.Seed = seed ?? 0;
215      memPr.StartSync();
216      if (memPr.Context.RelinkedPaths.IsEmpty
217        || IncludeLocalSearch && memPr.Context.LocalSearchPaths.IsEmpty) {
218        Console.WriteLine("{0} not all paths present!", problem.Name);
219        return null;
220      };
221
222      var features = PermutationPathAnalysis.GetCharacteristics(memPr.Context.RelinkedPaths.Paths.ToList());
223      var result = features.GetValues();
224      var resultNames = features.GetNames();
225      if (IncludeLocalSearch) {
226        features = PermutationPathAnalysis.GetCharacteristics(memPr.Context.LocalSearchPaths.Paths.ToList());
227        result = result.Concat(features.GetValues()).ToArray();
228        resultNames = resultNames.Concat(features.GetNames()).ToArray();
229      }
230      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows, resultNames, result);
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.