source: branches/2457_ExpertSystem/ProblemInstanceIdentifier/InstanceExplorer.cs @ 16096

Last change on this file since 16096 was 16096, checked in by abeham, 2 years 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: 8.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Analysis.FitnessLandscape;
5using HeuristicLab.Data;
6using HeuristicLab.Encodings.PermutationEncoding;
7using HeuristicLab.Problems.QuadraticAssignment;
8using HeuristicLab.SequentialEngine;
9
10namespace ProblemInstanceIdentifier {
11  public abstract class InstanceExplorer {
12
13    public abstract string Name { get; }
14    public abstract int Effort { get; }
15    protected InstanceExplorer() { }
16
17    public abstract InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null);
18  }
19
20  public class PathRelinkingExplorer : InstanceExplorer {
21    public int Paths { get; set; }
22    public QAPDirectedWalk.WalkType Type { get; set; }
23
24    public override string Name { get { return "Path-Relinking Explorer"; } }
25    public override int Effort { get { return Paths; } }
26
27    public ISet<string> Features { get; set; }
28
29    public PathRelinkingExplorer() {
30     
31    }
32
33    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
34      var calculator = new QAPDirectedWalk {
35        Problem = problem,
36        BestImprovement = true,
37        Paths = Paths,
38        Seed = seed,
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  }
55
56  public class RandomWalkExplorer : InstanceExplorer {
57    public int Iterations { get; set; }
58
59    public override string Name { get { return "Random-Walk Explorer"; } }
60    public override int Effort { get { return Iterations; } }
61
62    public ISet<string> Features { get; set; }
63
64    public RandomWalkExplorer() {
65
66    }
67
68    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
69      var walk = new RandomWalk() {
70        SeedParameter = { Value = { Value = seed ?? 0 } },
71        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
72        MaximumIterationsParameter = { Value = { Value = Iterations } },
73        RepetitionsParameter = { Value = { Value = 1 } }
74      };
75      walk.Problem = problem;
76      walk.Engine = new SequentialEngine();
77      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
78      var calculator = new RandomWalkCalculator(walk) { Problem = problem };
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());
87    }
88  }
89
90  public class AdaptiveWalkExplorer : InstanceExplorer {
91    public int Iterations { get; set; }
92    public int SampleSize { get; set; }
93
94    public override string Name { get { return "Adaptive-Walk Explorer"; } }
95    private int _effort;
96    public override int Effort { get { return _effort; } }
97
98    public ISet<string> Features { get; set; }
99
100    public AdaptiveWalkExplorer() {
101      _effort = 0;
102    }
103
104    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
105      var walk = new AdaptiveWalk() {
106        SeedParameter = { Value = { Value = seed ?? 0 } },
107        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
108        MaximumIterationsParameter = { Value = { Value = Iterations } },
109        RepetitionsParameter = { Value = { Value = 1 } },
110        SampleSizeParameter = { Value = { Value = SampleSize } }
111      };
112      walk.Problem = problem;
113      walk.Engine = new SequentialEngine();
114      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
115      var calculator = new AdaptiveWalkCalculator(walk) { Problem = problem };
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());
124    }
125  }
126
127  public class UpDownWalkExplorer : InstanceExplorer {
128    public int Iterations { get; set; }
129    public int SampleSize { get; set; }
130
131    public override string Name { get { return "Up/Down-Walk Explorer"; } }
132    public override int Effort { get { return Iterations * SampleSize; } }
133
134    public ISet<string> Features { get; set; }
135
136    public UpDownWalkExplorer() {
137
138    }
139
140    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
141      var walk = new UpDownWalk() {
142        SeedParameter = { Value = { Value = seed ?? 0 } },
143        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
144        MaximumIterationsParameter = { Value = { Value = Iterations } },
145        RepetitionsParameter = { Value = { Value = 1 } },
146        SampleSizeParameter = { Value = { Value = SampleSize } }
147      };
148      walk.Problem = problem;
149      walk.Engine = new SequentialEngine();
150      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
151      var calculator = new UpDownWalkCalculator(walk) {  Problem = problem };
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  /*
163  public class MemPRExplorer : InstanceExplorer {
164    public int Seconds { get; set; }
165
166    public bool IncludeLocalSearch { get; set; }
167
168    public override string Name { get { return "MemPR Explorer"; } }
169    public override int Effort { get { return Seconds; } }
170
171    public MemPRExplorer() {
172
173    }
174
175    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
176      var memPr = new PermutationMemPR();
177      memPr.Problem = problem;
178      memPr.Prepare(true);
179      memPr.MaximumExecutionTime = TimeSpan.FromSeconds(Seconds);
180      memPr.SetSeedRandomly = !seed.HasValue;
181      memPr.Seed = seed ?? 0;
182      memPr.StartSync();
183      if (memPr.Context.RelinkedPaths.IsEmpty
184        || IncludeLocalSearch && memPr.Context.LocalSearchPaths.IsEmpty) {
185        Console.WriteLine("{0} not all paths present!", problem.Name);
186        return null;
187      };
188
189      var features = PermutationPathAnalysis.GetCharacteristics(memPr.Context.RelinkedPaths.Paths.ToList());
190      var result = features.GetValues();
191      var resultNames = features.GetNames();
192      if (IncludeLocalSearch) {
193        features = PermutationPathAnalysis.GetCharacteristics(memPr.Context.LocalSearchPaths.Paths.ToList());
194        result = result.Concat(features.GetValues()).ToArray();
195        resultNames = resultNames.Concat(features.GetNames()).ToArray();
196      }
197      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows, resultNames, result);
198    }
199  }*/
200}
Note: See TracBrowser for help on using the repository browser.