[14691] | 1 | using System;
|
---|
[16096] | 2 | using System.Collections.Generic;
|
---|
[14691] | 3 | using System.Linq;
|
---|
[14690] | 4 | using HeuristicLab.Analysis.FitnessLandscape;
|
---|
| 5 | using HeuristicLab.Data;
|
---|
| 6 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
| 7 | using HeuristicLab.Problems.QuadraticAssignment;
|
---|
| 8 | using HeuristicLab.SequentialEngine;
|
---|
| 9 |
|
---|
| 10 | namespace 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; }
|
---|
[16096] | 22 | public QAPDirectedWalk.WalkType Type { get; set; }
|
---|
[14690] | 23 |
|
---|
| 24 | public override string Name { get { return "Path-Relinking Explorer"; } }
|
---|
| 25 | public override int Effort { get { return Paths; } }
|
---|
| 26 |
|
---|
[16096] | 27 | public ISet<string> Features { get; set; }
|
---|
| 28 |
|
---|
[14690] | 29 | public PathRelinkingExplorer() {
|
---|
| 30 |
|
---|
| 31 | }
|
---|
| 32 |
|
---|
| 33 | public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
|
---|
[16096] | 34 | var calculator = new QAPDirectedWalk {
|
---|
[14690] | 35 | Problem = problem,
|
---|
| 36 | BestImprovement = true,
|
---|
| 37 | Paths = Paths,
|
---|
| 38 | Seed = seed,
|
---|
[16096] | 39 | Type = Type
|
---|
[14690] | 40 | };
|
---|
[16096] | 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 | }
|
---|
[15031] | 45 | }
|
---|
[16096] | 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");
|
---|
[15031] | 50 |
|
---|
| 51 | return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
|
---|
[16096] | 52 | result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray()) { DescriptionEffort = evaluations };
|
---|
[15031] | 53 | }
|
---|
| 54 | }
|
---|
| 55 |
|
---|
[14690] | 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 |
|
---|
[16096] | 62 | public ISet<string> Features { get; set; }
|
---|
| 63 |
|
---|
[14690] | 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 } },
|
---|
[14691] | 71 | SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
|
---|
[14690] | 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 };
|
---|
[16096] | 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 |
|
---|
[14690] | 85 | return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
|
---|
[16096] | 86 | result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray());
|
---|
[14690] | 87 | }
|
---|
| 88 | }
|
---|
[14691] | 89 |
|
---|
[14776] | 90 | public class AdaptiveWalkExplorer : InstanceExplorer {
|
---|
| 91 | public int Iterations { get; set; }
|
---|
[15031] | 92 | public int SampleSize { get; set; }
|
---|
[14776] | 93 |
|
---|
| 94 | public override string Name { get { return "Adaptive-Walk Explorer"; } }
|
---|
[16096] | 95 | private int _effort;
|
---|
| 96 | public override int Effort { get { return _effort; } }
|
---|
[14776] | 97 |
|
---|
[16096] | 98 | public ISet<string> Features { get; set; }
|
---|
| 99 |
|
---|
[14776] | 100 | public AdaptiveWalkExplorer() {
|
---|
[16096] | 101 | _effort = 0;
|
---|
[14776] | 102 | }
|
---|
| 103 |
|
---|
| 104 | public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
|
---|
| 105 | var walk = new AdaptiveWalk() {
|
---|
| 106 | SeedParameter = { Value = { Value = seed ?? 0 } },
|
---|
[15031] | 107 | SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
|
---|
[14776] | 108 | MaximumIterationsParameter = { Value = { Value = Iterations } },
|
---|
[15031] | 109 | RepetitionsParameter = { Value = { Value = 1 } },
|
---|
| 110 | SampleSizeParameter = { Value = { Value = SampleSize } }
|
---|
[14776] | 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 };
|
---|
[16096] | 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");
|
---|
[14776] | 121 |
|
---|
| 122 | return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
|
---|
[16096] | 123 | result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray());
|
---|
[14776] | 124 | }
|
---|
| 125 | }
|
---|
| 126 |
|
---|
[15031] | 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 |
|
---|
[16096] | 134 | public ISet<string> Features { get; set; }
|
---|
| 135 |
|
---|
[15031] | 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 };
|
---|
[16096] | 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");
|
---|
[15031] | 157 |
|
---|
| 158 | return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
|
---|
[16096] | 159 | result.Keys.ToArray(), result.Values.Select(x => ((DoubleValue)x).Value).ToArray());
|
---|
[15031] | 160 | }
|
---|
| 161 | }
|
---|
[16096] | 162 | /*
|
---|
[14691] | 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) {
|
---|
[14696] | 185 | Console.WriteLine("{0} not all paths present!", problem.Name);
|
---|
[14691] | 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 | }
|
---|
[16096] | 199 | }*/
|
---|
[14690] | 200 | }
|
---|