1 | using System;
|
---|
2 | using System.Linq;
|
---|
3 | using System.Threading;
|
---|
4 | using HeuristicLab.Common;
|
---|
5 | using HeuristicLab.Core;
|
---|
6 | using HeuristicLab.Data;
|
---|
7 | using HeuristicLab.Operators;
|
---|
8 | using HeuristicLab.Optimization;
|
---|
9 | using HeuristicLab.Parameters;
|
---|
10 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
11 | using System.Collections.Generic;
|
---|
12 | using HeuristicLab.Algorithms.GeneticAlgorithm;
|
---|
13 | using System.Threading.Tasks;
|
---|
14 | using System.Diagnostics;
|
---|
15 | using System.Reflection;
|
---|
16 |
|
---|
17 | namespace HeuristicLab.Problems.MetaOptimization {
|
---|
18 | /// <summary>
|
---|
19 | /// A base class for operators which evaluate TSP solutions.
|
---|
20 | /// </summary>
|
---|
21 | [Item("ParameterConfigurationEvaluator", "A base class for operators which evaluate Meta Optimization solutions.")]
|
---|
22 | [StorableClass]
|
---|
23 | public class ParameterConfigurationEvaluator : SingleSuccessorOperator, IParameterConfigurationEvaluator {
|
---|
24 | private const double PenaltyQuality = 100000.0; // todo: use something better
|
---|
25 |
|
---|
26 | public ILookupParameter<DoubleValue> QualityParameter {
|
---|
27 | get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
|
---|
28 | }
|
---|
29 | public ILookupParameter<TypeValue> AlgorithmTypeParameter {
|
---|
30 | get { return (ILookupParameter<TypeValue>)Parameters[MetaOptimizationProblem.AlgorithmTypeParameterName]; }
|
---|
31 | }
|
---|
32 | public ILookupParameter<IItemList<IProblem>> ProblemsParameter {
|
---|
33 | get { return (ILookupParameter<IItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
|
---|
34 | }
|
---|
35 | public ILookupParameter<ParameterConfigurationTree> ParameterConfigurationParameter {
|
---|
36 | get { return (ILookupParameter<ParameterConfigurationTree>)Parameters["ParameterConfigurationTree"]; }
|
---|
37 | }
|
---|
38 | public LookupParameter<IntValue> RepetitionsParameter {
|
---|
39 | get { return (LookupParameter<IntValue>)Parameters[MetaOptimizationProblem.RepetitionsParameterName]; }
|
---|
40 | }
|
---|
41 |
|
---|
42 | public LookupParameter<DoubleArray> ProblemQualityReferencesParameter {
|
---|
43 | get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityReferences"]; }
|
---|
44 | }
|
---|
45 | public LookupParameter<IntValue> GenerationsParameter {
|
---|
46 | get { return (LookupParameter<IntValue>)Parameters["Generations"]; }
|
---|
47 | }
|
---|
48 | public LookupParameter<ResultCollection> ResultsParameter {
|
---|
49 | get { return (LookupParameter<ResultCollection>)Parameters["Results"]; }
|
---|
50 | }
|
---|
51 |
|
---|
52 | public IntValue Repetitions {
|
---|
53 | get { return RepetitionsParameter.ActualValue; }
|
---|
54 | }
|
---|
55 |
|
---|
56 | public ParameterConfigurationEvaluator()
|
---|
57 | : base() {
|
---|
58 | Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the ParameterVector."));
|
---|
59 | Parameters.Add(new LookupParameter<TypeValue>(MetaOptimizationProblem.AlgorithmTypeParameterName, "Missing description."));
|
---|
60 | Parameters.Add(new LookupParameter<IItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName, "Missing description."));
|
---|
61 | Parameters.Add(new LookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", "Missing description."));
|
---|
62 | Parameters.Add(new LookupParameter<IntValue>(MetaOptimizationProblem.RepetitionsParameterName, "Number of evaluations on one problem."));
|
---|
63 | Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityReferences", ""));
|
---|
64 | Parameters.Add(new LookupParameter<IntValue>("Generations", ""));
|
---|
65 | Parameters.Add(new LookupParameter<ResultCollection>("Results", ""));
|
---|
66 | }
|
---|
67 |
|
---|
68 | [StorableConstructor]
|
---|
69 | protected ParameterConfigurationEvaluator(bool deserializing) : base(deserializing) { }
|
---|
70 | protected ParameterConfigurationEvaluator(ParameterConfigurationEvaluator original, Cloner cloner)
|
---|
71 | : base(original, cloner) {
|
---|
72 | }
|
---|
73 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
74 | return new ParameterConfigurationEvaluator(this, cloner);
|
---|
75 | }
|
---|
76 |
|
---|
77 | public override IOperation Apply() {
|
---|
78 | ParameterConfigurationTree parameterConfiguration = ParameterConfigurationParameter.ActualValue;
|
---|
79 | IAlgorithm algorithm = (IAlgorithm)Activator.CreateInstance(AlgorithmTypeParameter.ActualValue.Value);
|
---|
80 | IItemList<IProblem> problems = ProblemsParameter.ActualValue;
|
---|
81 | ItemDictionary<StringValue, RunCollection> runsCache = ResultsParameter.ActualValue.ContainsKey("Runs") ? (ItemDictionary<StringValue, RunCollection>)ResultsParameter.ActualValue["Runs"].Value : null;
|
---|
82 | double[] referenceQualities = GetReferenceQualities(problems);
|
---|
83 |
|
---|
84 | RunCollection runs;
|
---|
85 | if (runsCache != null && runsCache.Count(x => x.Key.Value == parameterConfiguration.ParameterInfoString) > 0) {
|
---|
86 | runs = runsCache.Single(x => x.Key.Value == parameterConfiguration.ParameterInfoString).Value;
|
---|
87 | Console.WriteLine("Used Cache for {0}", parameterConfiguration.ParameterInfoString);
|
---|
88 | } else {
|
---|
89 | runs = ExecuteAlgorithm(parameterConfiguration, algorithm, problems);
|
---|
90 | }
|
---|
91 |
|
---|
92 | List<List<double>> qualities = new List<List<double>>();
|
---|
93 | List<List<TimeSpan>> executionTimes = new List<List<TimeSpan>>();
|
---|
94 |
|
---|
95 | for (int i = 0; i < problems.Count; i++) {
|
---|
96 | var problemRuns = runs.Where(x => ((IntValue)x.Results["Meta.ProblemIndex"]).Value == i + 1);
|
---|
97 | qualities.Add(problemRuns.Select(x => ((DoubleValue)x.Results["BestQuality"]).Value).ToList());
|
---|
98 | executionTimes.Add(problemRuns.Select(x => ((TimeSpanValue)x.Results["Execution Time"]).Value).ToList());
|
---|
99 | }
|
---|
100 |
|
---|
101 | parameterConfiguration.AverageExecutionTimes = new ItemList<TimeSpanValue>(executionTimes.Select(t => new TimeSpanValue(TimeSpan.FromMilliseconds(t.Average(ts => ts.TotalMilliseconds)))));
|
---|
102 | parameterConfiguration.Repetitions = (IntValue)Repetitions.Clone();
|
---|
103 | parameterConfiguration.BestQualities = new DoubleArray(qualities.Select(q => q.Min()).ToArray()); // todo: respect Maximization:true/false
|
---|
104 | parameterConfiguration.AverageQualities = new DoubleArray(qualities.Select(q => q.Average()).ToArray());
|
---|
105 | parameterConfiguration.WorstQualities = new DoubleArray(qualities.Select(q => q.Max()).ToArray()); // todo: respect Maximization:true/false
|
---|
106 | parameterConfiguration.QualityVariances = new DoubleArray(qualities.Select(q => q.Variance()).ToArray());
|
---|
107 | parameterConfiguration.QualityStandardDeviations = new DoubleArray(qualities.Select(q => q.StandardDeviation()).ToArray());
|
---|
108 | parameterConfiguration.Runs = (RunCollection)runs.Clone();
|
---|
109 |
|
---|
110 | this.QualityParameter.ActualValue = new DoubleValue(NormalizeQualities(parameterConfiguration, referenceQualities));
|
---|
111 |
|
---|
112 | return base.Apply();
|
---|
113 | }
|
---|
114 |
|
---|
115 | private double[] GetReferenceQualities(IItemList<IProblem> problems) {
|
---|
116 | double[] referenceQualities;
|
---|
117 | if (ProblemQualityReferencesParameter.ActualValue == null) {
|
---|
118 | // this is generation zero. no reference qualities for normalization have been calculated yet. in this special case the ReferenceQualityAnalyzer will do the normalization
|
---|
119 | referenceQualities = new double[problems.Count];
|
---|
120 | for (int i = 0; i < referenceQualities.Length; i++) {
|
---|
121 | referenceQualities[i] = 1;
|
---|
122 | }
|
---|
123 | } else {
|
---|
124 | referenceQualities = ProblemQualityReferencesParameter.ActualValue.ToArray();
|
---|
125 | }
|
---|
126 | return referenceQualities;
|
---|
127 | }
|
---|
128 |
|
---|
129 | private RunCollection ExecuteAlgorithm(ParameterConfigurationTree parameterConfiguration, IAlgorithm algorithm, IItemList<IProblem> problems) {
|
---|
130 | IAlgorithm algorithmClone = (IAlgorithm)algorithm.Clone();
|
---|
131 |
|
---|
132 | // set parameters
|
---|
133 | parameterConfiguration.Parameterize(algorithmClone);
|
---|
134 | algorithmClone.StoreAlgorithmInEachRun = false;
|
---|
135 |
|
---|
136 | if (algorithmClone is EngineAlgorithm) {
|
---|
137 | ((EngineAlgorithm)algorithmClone).Engine = new SequentialEngine.SequentialEngine();
|
---|
138 | }
|
---|
139 | algorithmClone.Prepare(true);
|
---|
140 |
|
---|
141 | foreach (IProblem problem in problems) {
|
---|
142 | algorithmClone.Problem = (IProblem)problem.Clone();
|
---|
143 |
|
---|
144 | for (int i = 0; i < Repetitions.Value; i++) {
|
---|
145 | algorithmClone.Prepare();
|
---|
146 |
|
---|
147 | AlgorithmExecutor executor = new AlgorithmExecutor(algorithmClone);
|
---|
148 | executor.StartSync();
|
---|
149 |
|
---|
150 | if (algorithmClone.ExecutionState == ExecutionState.Paused) {
|
---|
151 | // this parametercombination was bad. set penalty for this solution
|
---|
152 | // TODO!
|
---|
153 | }
|
---|
154 | int problemIndex = problems.IndexOf(problem) + 1;
|
---|
155 | IRun run = algorithmClone.Runs.Last();
|
---|
156 | run.Results.Add("Meta.FromCache", new BoolValue(false));
|
---|
157 | run.Results.Add("Meta.Generation", new IntValue(GenerationsParameter.ActualValue != null ? GenerationsParameter.ActualValue.Value : 0));
|
---|
158 | run.Results.Add("Meta.ProblemIndex", new IntValue(problemIndex));
|
---|
159 | int runCountOfThisProblem = algorithmClone.Runs.Where(x => ((IntValue)x.Results["Meta.ProblemIndex"]).Value == problemIndex).Count();
|
---|
160 | run.Name = string.Format("{0} Problem {1} Run {2}", parameterConfiguration.ParameterInfoString, problemIndex, runCountOfThisProblem);
|
---|
161 | }
|
---|
162 | }
|
---|
163 | algorithmClone.Prepare();
|
---|
164 | return algorithmClone.Runs;
|
---|
165 | }
|
---|
166 |
|
---|
167 | public static double NormalizeQualities(ParameterConfigurationTree parameterConfigurationTree, double[] referenceQualities) {
|
---|
168 | double[] qualitiesNormalized = new double[referenceQualities.Length];
|
---|
169 | for (int i = 0; i < referenceQualities.Length; i++) {
|
---|
170 | qualitiesNormalized[i] = parameterConfigurationTree.AverageQualities[i] / referenceQualities[i];
|
---|
171 | }
|
---|
172 | parameterConfigurationTree.QualitiesNormalized = new DoubleArray(qualitiesNormalized);
|
---|
173 | parameterConfigurationTree.AverageQualityNormalized = new DoubleValue(qualitiesNormalized.Average());
|
---|
174 | return parameterConfigurationTree.AverageQualityNormalized.Value;
|
---|
175 | }
|
---|
176 |
|
---|
177 | public static double Variance(IEnumerable<double> source) {
|
---|
178 | double avg = source.Average();
|
---|
179 | double d = source.Aggregate(0.0, (total, next) => total += Math.Pow(next - avg, 2));
|
---|
180 | return d / (source.Count() - 1);
|
---|
181 | }
|
---|
182 |
|
---|
183 | public static double StandardDeviation(IEnumerable<double> source) {
|
---|
184 | return Math.Sqrt(source.Variance());
|
---|
185 | }
|
---|
186 | }
|
---|
187 | }
|
---|