Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14691 was 14691, checked in by abeham, 7 years ago

#2457: working on identification of problem instances

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