source: branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs @ 14776

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

#2457: working on MemPR integration

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