- Timestamp:
- 02/23/17 10:42:58 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs
r14690 r14691 9 9 using HeuristicLab.Problems.Instances.QAPLIB; 10 10 using HeuristicLab.Problems.QuadraticAssignment; 11 using HeuristicLab.Random; 11 12 12 13 namespace ProblemInstanceIdentifier { … … 18 19 }; 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() { 20 71 var sync = new object(); 21 72 … … 36 87 }); 37 88 } 38 39 /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls); 40 foreach (var cls in classes.OrderBy(x => x.Key)) { 41 Console.WriteLine("{0};{1}", cls.Key, cls.Count()); 42 }*/ 43 44 //var kb = GenerateKnowledgeBase(instances, 200, localOptima: false); 45 46 47 //var paths = new[] { 1, 2, 3, 5, 10, 20, 30, 50, 100, 200 }; 48 //var kbExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray(); 49 //var expExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray(); 50 //ExploreSelfIdentification(instances, kbExplorers, expExplorers); 51 52 var iterations = new[] { 100, 1000, 10000, 100000 }; 53 var kbExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(); 54 var expExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(); 55 ExploreSelfIdentification(instances, kbExplorers, expExplorers); 56 57 //ExploreMemPrIdentification(instances); 58 } 59 60 private static List<InstanceDescriptor> GenerateKnowledgeBase(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer) { 61 var headerPrinted = false; 62 var sync = new object(); 63 var kb = new List<InstanceDescriptor>(); 64 Parallel.ForEach(instances.OrderBy(x => x.Weights.Rows), qap => { 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) => { 65 96 var instance = explorer.Explore(qap); 66 lock (sync) { 67 if (!headerPrinted) { 68 headerPrinted = true; 69 Console.WriteLine(string.Join(";", 70 new [] { "Name", "Cls", "Dimension" } 71 .Concat(instance.FeatureNames))); 72 } 73 PrintInstanceLine(instance); 74 kb.Add(instance); 75 } 76 }); 77 var standardizer = InstancesStandardizer.Create(kb); 78 var normalizedKb = kb.Select(x => new InstanceDescriptor(x)).ToList(); 79 standardizer.Apply(normalizedKb); 80 Console.WriteLine(); 81 foreach (var instance in kb) { 82 PrintInstanceLine(instance); 83 } 84 //return normalizedKb; 85 return kb; 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 } 86 147 } 87 148 … … 92 153 } 93 154 94 private static void ExploreSelfIdentification(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] kbExplorer, InstanceExplorer[] expExporer) { 95 var sync = new object(); 96 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Effort", "Exp-Effort", 97 "Exact-Hits", "No-Hits", "Exact-Rank"); 98 var kbSeeds = Enumerable.Range(0, 20).ToList(); 99 var expSeeds = Enumerable.Range(20, 20).ToList(); 100 for (var r = 0; r < 10; r++) { 101 var rlokal = r; 102 Parallel.ForEach(kbExplorer, kbPaths => { 103 //foreach (var kbPaths in kbExplorer) { 104 foreach (var expPaths in expExporer) { 105 //if (expPaths > kbPaths) continue; 106 var kb = new List<InstanceDescriptor>(); 107 var exp = new List<InstanceDescriptor>(); 108 foreach (var qap in instances) { 109 kb.Add(kbPaths.Explore(qap, kbSeeds[rlokal])); 110 exp.Add(expPaths.Explore(qap, expSeeds[rlokal])); 111 } 112 var standardizer = InstancesStandardizer.Create(kb); 113 standardizer.Apply(kb); 114 standardizer.Apply(exp); 115 int exactCount = 0, clsCount = 0, missedCount = 0; 116 int exactRank = 0, clsRank = 0; 117 foreach (var e in exp) { 118 var ordered = kb.OrderBy(x => x.CalculateSimilarity(e)).ToList(); 119 var bestMatch = ordered.First(); 120 if (bestMatch.Cls == e.Cls) { 121 clsCount++; 122 if (bestMatch.Name == e.Name) exactCount++; 123 } 124 else missedCount++; 125 clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1; 126 exactRank += ordered.FindIndex((id) => id.Name == e.Name) + 1; 127 } 128 lock (sync) { 129 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths.Effort, expPaths.Effort, exactCount, 130 missedCount, exactRank / (double) exp.Count); 131 } 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); 132 203 } 133 204 }); 134 //} 135 } 136 } 137 138 private static void ExploreMemPrIdentification(List<QuadraticAssignmentProblem> instances) { 139 var sync = new object(); 140 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Runtime", "Exp-Runtime", 141 "Exact-Hits", "No-Hits", "Average-Rank"); 142 var paths = new[] { 10 }; 143 var repetitions = 10; 144 var kbSeeds = Enumerable.Range(0, repetitions).ToList(); 145 var expSeeds = Enumerable.Range(repetitions, repetitions).ToList(); 146 for (var r = 0; r < repetitions; r++) { 147 var rlokal = r; 148 Parallel.ForEach(paths, kbPaths => { 149 var memPr = new PermutationMemPR(); 150 foreach (var expPaths in paths) { 151 //if (expPaths > kbPaths) continue; 152 var kb = new List<InstanceDescriptor>(); 153 var exp = new List<InstanceDescriptor>(); 154 foreach (var qap in instances.Select(x => (QuadraticAssignmentProblem)x.Clone())) { 155 memPr.Problem = qap; 156 memPr.Prepare(true); 157 memPr.Seed = kbSeeds[rlokal]; 158 memPr.MaximumExecutionTime = TimeSpan.FromSeconds(kbPaths); 159 memPr.StartSync(); 160 if (memPr.Context.RelinkedPaths.IsEmpty) continue; 161 kb.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList())); 162 memPr.Prepare(true); 163 memPr.Seed = expSeeds[rlokal]; 164 memPr.MaximumExecutionTime = TimeSpan.FromSeconds(expPaths); 165 memPr.StartSync(); 166 if (memPr.Context.RelinkedPaths.IsEmpty) continue; 167 exp.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList())); 168 } 169 var standardizer = InstancesStandardizer.Create(kb); 170 standardizer.Apply(kb); 171 standardizer.Apply(exp); 172 int exactCount = 0, clsCount = 0, missedCount = 0; 173 int exactRank = 0, clsRank = 0; 174 foreach (var e in exp) { 175 var ordered = kb.OrderBy(x => x.CalculateSimilarity(e)).ToList(); 176 var bestMatch = ordered.First(); 177 if (bestMatch.Cls == e.Cls) { 178 clsCount++; 179 if (bestMatch.Name == e.Name) exactCount++; 180 } else missedCount++; 181 clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1; 182 exactRank += ordered.FindIndex((id) => id.Name == e.Name) + 1; 183 } 184 lock (sync) { 185 Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths, expPaths, exactCount, 186 missedCount, exactRank / (double)exp.Count); 187 } 188 } 189 }); 190 } 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; } 191 223 } 192 224 }
Note: See TracChangeset
for help on using the changeset viewer.