source: branches/PerformanceComparison/ProblemInstanceIdentifier/Program.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: 10.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Globalization;
4using System.Linq;
5using System.Threading.Tasks;
6using HeuristicLab.PluginInfrastructure;
7using HeuristicLab.Problems.Instances;
8using HeuristicLab.Problems.Instances.QAPLIB;
9using HeuristicLab.Problems.QuadraticAssignment;
10using HeuristicLab.Random;
11
12namespace ProblemInstanceIdentifier {
13  class Program {
14    static void Main(string[] args) {
15      //var instances = Get20DifferentClasses();
16      var instances = GetSomeRandomInstances(50, 13);
17
18      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
19      foreach (var cls in classes.OrderBy(x => x.Key)) {
20        Console.WriteLine("{0};{1}", cls.Key, cls.Count());
21      }*/
22
23      var prExplorer = new PathRelinkingExplorer() {
24        LocalOptima = false,
25        Paths = 200
26      };
27      var prOldExplorer = new PathRelinkingOldFeaturedExplorer() {
28        LocalOptima = false,
29        Paths = 200
30      };
31
32      var prLocalExplorer = new PathRelinkingExplorer() {
33        LocalOptima = true,
34        Paths = 200
35      };
36      var prOldLocalExplorer = new PathRelinkingOldFeaturedExplorer() {
37        LocalOptima = true,
38        Paths = 200
39      };
40
41      var memPrExplorer = new MemPRExplorer() {
42        IncludeLocalSearch = false,
43        Seconds = 10
44      };
45
46      //var training = GenerateData(instances, prOldExplorer, parallel: true);
47      //var standardizer = InstancesStandardizer.CreateAndApply(training);
48      //var test = GenerateData(instances, prOldExplorer, parallel: true);
49      //standardizer.Apply(test);
50      //PrintMatchResult(Compare(training, test));
51
52      //Console.WriteLine("=== Path Relinking Walk ===");
53      //ExploreMatching(instances,
54      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
55      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
56      //parallel: true);
57      //Console.WriteLine("=== Random Walk ===");
58      //ExploreMatching(instances,
59      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
60      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
61      //parallel: true);
62      //Console.WriteLine("=== Adaptive Walk ===");
63      //ExploreMatching(instances,
64      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
65      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
66      //parallel: true);
67      Console.WriteLine("=== Up/Down Walk ===");
68      ExploreMatching(instances,
69      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
70      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
71      parallel: true);
72    }
73
74    private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances, int seed) {
75      var sync = new object();
76      var provider = new OneSizeInstanceProvider();
77      var instances = new List<QuadraticAssignmentProblem>();
78      var random = new FastRandom(seed);
79      Parallel.ForEach(provider.GetDataDescriptors().Shuffle(random), desc => {
80        var qapData = provider.LoadData(desc);
81        if (instances.Count >= totalInstances) return;
82        var qap = new QuadraticAssignmentProblem();
83        qap.Load(qapData);
84        lock (sync) {
85          if (instances.Count >= totalInstances) return;
86          instances.Add(qap);
87        }
88      });
89      return instances;
90    }
91
92    private static HashSet<string> selectedInstances = new HashSet<string>() {
93      "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
94      "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50",
95      "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
96    };
97    private static List<QuadraticAssignmentProblem> Get20DifferentClasses() {
98      var sync = new object();
99
100      var qapProviders = ApplicationManager.Manager.GetInstances<ProblemInstanceProvider<QAPData>>().ToList();
101      var instances = new List<QuadraticAssignmentProblem>();
102      foreach (var provider in qapProviders) {
103        if (provider is TaillardQAPInstanceProvider) continue;
104        Parallel.ForEach(provider.GetDataDescriptors(), desc => {
105          if (!selectedInstances.Contains(desc.Name)) return;
106          //if (desc.Name == "esc16f") return;
107          var qapData = provider.LoadData(desc);
108          //if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
109          var qap = new QuadraticAssignmentProblem();
110          qap.Load(qapData);
111          lock (sync) {
112            instances.Add(qap);
113          }
114        });
115      }
116      return instances;
117    }
118
119    private static List<InstanceDescriptor> GenerateData(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer, bool parallel = false) {
120      var sync = new object();
121      var data = new List<InstanceDescriptor>();
122      Action<QuadraticAssignmentProblem> body = (qap) => {
123        var instance = explorer.Explore(qap);
124        if (instance == null) return;
125        lock (sync) {
126          data.Add(instance);
127        }
128      };
129      if (parallel) {
130        Parallel.ForEach(instances.Select(x => (QuadraticAssignmentProblem)x.Clone()), body);
131      } else {
132        foreach (var qap in instances) body(qap);
133      }
134      return data;
135    }
136
137    private static MatchResult Compare(List<InstanceDescriptor> training, List<InstanceDescriptor> test) {
138      int exactCount = 0, clsCount = 0, totalCount = 0;
139      int exactRank = 0, clsRank = 0;
140      foreach (var e in test) {
141        var ordered = training.OrderBy(x => x.CalculateSimilarity(e)).ToList();
142        var bestMatch = ordered.First();
143        if (bestMatch.Cls == e.Cls) clsCount++;
144        if (bestMatch.Name == e.Name) exactCount++;
145        var r = ordered.FindIndex((id) => id.Name == e.Name);
146        if (r < 0) continue;
147        totalCount++;
148        exactRank += r + 1;
149        clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1;
150      }
151
152      return new MatchResult() {
153        ExactCount = exactCount,
154        ClsCount = clsCount,
155        TotalCount = totalCount,
156        ExactAverageRank = exactRank / (double)totalCount,
157        ClsAverageRank = clsRank / (double)totalCount
158      };
159    }
160
161    private static void PrintMatchResult(MatchResult result) {
162      Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4:F2}",
163        result.ExactCount, result.ClsCount, result.TotalCount,
164        result.ExactAverageRank, result.ClsAverageRank);
165    }
166
167    private static void PrintData(List<InstanceDescriptor> instances) {
168      using (var iter = instances.GetEnumerator()) {
169        if (!iter.MoveNext()) return;
170        Console.WriteLine(string.Join(";", new[] {"Name", "Cls", "Dimension"}
171          .Concat(iter.Current != null ? iter.Current.FeatureNames : new [] { "(null)" })));
172        do {
173          PrintInstanceLine(iter.Current);
174        } while (iter.MoveNext());
175      }
176    }
177
178    private static void PrintInstanceLine(InstanceDescriptor instance) {
179      Console.WriteLine(string.Join(";",
180        new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)}
181          .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture)))));
182    }
183
184    private static void ExploreMatching(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] trainingExplorers, InstanceExplorer[] testExporers, bool parallel = false) {
185      var sync = new object();
186
187      var knowledgeBase = new Dictionary<InstanceExplorer, Tuple<InstancesStandardizer, List<InstanceDescriptor>>>();
188      Action<InstanceExplorer> trainingBody = (kbExplorer) => {
189        var trainingData = GenerateData(instances, kbExplorer, parallel);
190        var standardizer = InstancesStandardizer.Create(trainingData);
191        standardizer.Apply(trainingData);
192        lock (sync) {
193          knowledgeBase.Add(kbExplorer, Tuple.Create(standardizer, trainingData));
194        }
195      };
196      if (parallel) {
197        Parallel.ForEach(trainingExplorers, trainingBody);
198      } else {
199        foreach (var kbExplorer in trainingExplorers) trainingBody(kbExplorer);
200      }
201
202      var experimentBase = new Dictionary<InstanceExplorer, List<InstanceDescriptor>>();
203      Action<InstanceExplorer> testBody = (expExplorer) => {
204        var testData = GenerateData(instances, expExplorer, parallel);
205        lock (sync) {
206          experimentBase.Add(expExplorer, testData);
207        }
208      };
209      if (parallel) {
210        Parallel.ForEach(testExporers, testBody);
211      } else {
212        foreach (var expExplorer in testExporers) testBody(expExplorer);
213      }
214
215      var data = from kb in knowledgeBase
216        from exp in experimentBase
217        select new { Training = kb, Test = exp };
218
219      if (parallel) {
220        Parallel.ForEach(data, (point) => {
221          var normalizedTest = point.Test.Value.Select(x => new InstanceDescriptor(x)).ToList();
222          point.Training.Value.Item1.Apply(normalizedTest);
223          var result = Compare(point.Training.Value.Item2, normalizedTest);
224          lock (sync) {
225            Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}",
226              point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
227              result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount);
228          }
229        });
230      } else {
231        foreach (var point in data) {
232          var normalizedTest = point.Test.Value.Select(x => new InstanceDescriptor(x)).ToList();
233          point.Training.Value.Item1.Apply(normalizedTest);
234          var result = Compare(point.Training.Value.Item2, normalizedTest);
235          Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}",
236            point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
237            result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount);
238        }
239      }
240    }
241
242    private class MatchResult {
243      public int ExactCount { get; set; }
244      public int ClsCount { get; set; }
245      public int TotalCount { get; set; }
246      public double ExactAverageRank { get; set; }
247      public double ClsAverageRank { get; set; }
248    }
249  }
250}
Note: See TracBrowser for help on using the repository browser.