- Timestamp:
- 04/26/16 00:02:05 (8 years ago)
- Location:
- branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Interfaces/IRecommendationModel.cs
r13791 r13794 22 22 using HeuristicLab.Common; 23 23 using HeuristicLab.Optimization; 24 using System;25 24 using System.Collections.Generic; 26 25 27 26 namespace HeuristicLab.OptimizationExpertSystem.Common { 28 27 public interface IRecommendationModel : IContent { 29 IEnumerable< Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance);28 IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance); 30 29 } 31 30 } -
branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs
r13791 r13794 718 718 result[problemMap[pr.Key]] = new Dictionary<long, int>(); 719 719 720 var indexMap = new BidirectionalDictionary<long, int>(); 721 var perf = new Dictionary<long, double>(); 722 var idx = 0; 723 foreach (var kvp in pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) { 724 var ert = ExpectedRuntimeHelper.CalculateErt(kvp.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime; 725 if (double.IsNaN(ert)) { 726 // algorithm can't solve that instance with the given target 727 // these are put into their own additional class 728 result[problemMap[pr.Key]][kvp.Key] = nClasses; 729 continue; 730 } 731 indexMap.Add(kvp.Key, idx); 732 perf[kvp.Key] = Math.Log10(ert); 733 idx++; 734 } 735 if (perf.Count == 0) continue; 736 737 var points = perf.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value).ToArray(); 738 int[] clusters; 739 Ckmeans1dClusters(points, nClasses, out clusters); 740 var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = perf[indexMap.GetBySecond(i)] }) 741 .GroupBy(x => x.Cluster, x => x.Perf) 742 .Select(x => new { Cluster = x.Key, AvgPerf = x.Average() }) 743 .OrderBy(x => x.AvgPerf) 744 .Select((c, i) => new { Cluster = c.Cluster, Rank = i }) 745 .ToDictionary(x => x.Cluster, x => x.Rank); 746 for (var i = 0; i < clusters.Length; i++) 747 result[problemMap[pr.Key]][indexMap.GetBySecond(i)] = ranks[clusters[i]]; 720 var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single()) 721 .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime); 722 var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsNaN(x.Value)) 723 .GetByCluster().ToList(); 724 var minRank = ranks.Min(x => x.Key); 725 foreach (var c in ranks) { 726 foreach (var a in c.Value) 727 result[problemMap[pr.Key]][a.Key] = c.Key == nClasses ? c.Key : c.Key - minRank; 728 } 748 729 } 749 730 return result; … … 772 753 } 773 754 774 // implement further classes and methods 775 private static SortedList<double, int> Ckmeans1dClusters(double[] estimations, int k, out int[] clusterValues) { 776 int nPoints = estimations.Length; 777 var distinct = estimations.Distinct().OrderBy(x => x).ToArray(); 778 var max = distinct.Max(); 779 if (distinct.Length <= k) { 780 var dict = distinct.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Value, y => y.Index); 781 for (int i = distinct.Length; i < k; i++) 782 dict.Add(max + i - distinct.Length + 1, i); 783 784 clusterValues = new int[nPoints]; 785 for (int i = 0; i < nPoints; i++) 786 if (!dict.ContainsKey(estimations[i])) clusterValues[i] = 0; 787 else clusterValues[i] = dict[estimations[i]]; 788 789 return new SortedList<double, int>(dict); 790 } 791 792 var n = distinct.Length; 793 var D = new double[n, k]; 794 var B = new int[n, k]; 795 796 for (int m = 0; m < k; m++) { 797 for (int j = m; j <= n - k + m; j++) { 798 if (m == 0) 799 D[j, m] = SumOfSquaredDistances(distinct, 0, j + 1); 800 else { 801 var minD = double.MaxValue; 802 var minI = 0; 803 for (int i = 1; i <= j; i++) { 804 var d = D[i - 1, m - 1] + SumOfSquaredDistances(distinct, i, j + 1); 805 if (d < minD) { 806 minD = d; 807 minI = i; 808 } 809 } 810 D[j, m] = minD; 811 B[j, m] = minI; 812 } 813 } 814 } 815 816 var centers = new SortedList<double, int>(); 817 var upper = B[n - 1, k - 1]; 818 var c = Mean(distinct, upper, n); 819 centers.Add(c, k - 1); 820 for (int i = k - 2; i >= 0; i--) { 821 var lower = B[upper - 1, i]; 822 var c2 = Mean(distinct, lower, upper); 823 centers.Add(c2, i); 824 upper = lower; 825 } 826 827 clusterValues = new int[nPoints]; 828 for (int i = 0; i < estimations.Length; i++) { 829 clusterValues[i] = centers.MinItems(x => Math.Abs(estimations[i] - x.Key)).First().Value; 830 } 831 832 return centers; 833 } 834 835 private static double SumOfSquaredDistances(double[] x, int start, int end) { 836 if (start == end) throw new InvalidOperationException(); 837 if (start + 1 == end) return 0.0; 838 double mean = 0.0; 839 for (int i = start; i < end; i++) { 840 mean += x[i]; 841 } 842 mean /= (end - start); 843 var sum = 0.0; 844 for (int i = start; i < end; i++) { 845 sum += (x[i] - mean) * (x[i] - mean); 846 } 847 return sum; 848 } 849 850 private static double Mean(double[] x, int start, int end) { 851 if (start == end) throw new InvalidOperationException(); 852 double mean = 0.0; 853 for (int i = start; i < end; i++) { 854 mean += x[i]; 855 } 856 mean /= (end - start); 857 return mean; 858 } 859 860 public IEnumerable<Tuple<IAlgorithm, double>> GetAlgorithmInstanceRanking() { 755 public IEnumerable<KeyValuePair<IAlgorithm, double>> GetAlgorithmInstanceRanking() { 861 756 return RecommendationModel.GetRanking(ProblemInstances.Single(IsCurrentInstance)); 862 757 } -
branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/FixedRankModel.cs
r13791 r13794 21 21 22 22 using HeuristicLab.Optimization; 23 using System;24 23 using System.Collections.Generic; 25 24 26 25 namespace HeuristicLab.OptimizationExpertSystem.Common { 27 26 public class FixedRankModel : IRecommendationModel { 28 private readonly List< Tuple<IAlgorithm, double>> ranking;27 private readonly List<KeyValuePair<IAlgorithm, double>> ranking; 29 28 30 public FixedRankModel(IEnumerable< Tuple<IAlgorithm, double>> ranking) {31 this.ranking = new List< Tuple<IAlgorithm, double>>();29 public FixedRankModel(IEnumerable<KeyValuePair<IAlgorithm, double>> ranking) { 30 this.ranking = new List<KeyValuePair<IAlgorithm, double>>(); 32 31 foreach (var r in ranking) this.ranking.Add(r); 33 32 } 34 33 35 public IEnumerable< Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance) {34 public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) { 36 35 return ranking; 37 36 } 38 37 39 38 public static FixedRankModel GetEmpty() { 40 return new FixedRankModel(new Tuple<IAlgorithm, double>[0]);39 return new FixedRankModel(new KeyValuePair<IAlgorithm, double>[0]); 41 40 } 42 41 } -
branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs
r13791 r13794 22 22 using HeuristicLab.Collections; 23 23 using HeuristicLab.Optimization; 24 using System;25 24 using System.Collections.Generic; 26 25 using System.Linq; … … 46 45 } 47 46 48 public IEnumerable< Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance) {47 public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) { 49 48 var features = KnowledgeCenter.GetFeatures(performance.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics, medianValues); 50 49 var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0]; … … 70 69 return performances.Select(x => new { Alg = x.Key, Perf = x.Value.Average() }) 71 70 .OrderBy(x => x.Perf) 72 .Select(x => Tuple.Create(x.Alg, x.Perf));71 .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf)); 73 72 } 74 73 } -
branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/OverallBestRecommender.cs
r13791 r13794 49 49 50 50 public IRecommendationModel TrainModel(IRun[] problemInstances, KnowledgeCenter kc, string[] characteristics) { 51 var instances = new List< Tuple<IAlgorithm, double>>();51 var instances = new List<KeyValuePair<IAlgorithm, double>>(); 52 52 foreach (var relevantRuns in kc.GetKnowledgeBaseByAlgorithm()) { 53 53 var algorithm = relevantRuns.Key; … … 60 60 var count = 0; 61 61 foreach (var problemRuns in relevantRuns.Value.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)) { 62 var bkq = pis[problemRuns.Key]; 62 double bkq; 63 if (!pis.TryGetValue(problemRuns.Key, out bkq)) continue; 63 64 var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", kc.GetTarget(bkq, kc.Maximization), kc.Maximization).ExpectedRuntime; 64 65 if (double.IsNaN(ert)) ert = int.MaxValue; … … 67 68 } 68 69 avgERT /= count; 69 instances.Add( Tuple.Create((IAlgorithm)algorithm.Clone(), avgERT));70 instances.Add(new KeyValuePair<IAlgorithm, double>(algorithm, avgERT)); 70 71 } 71 72 72 return new FixedRankModel(instances.OrderBy(x => x. Item2));73 return new FixedRankModel(instances.OrderBy(x => x.Value)); 73 74 } 74 75 }
Note: See TracChangeset
for help on using the changeset viewer.