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<EngineAlgorithm> AlgorithmParameter {
|
---|
30 | get { return (ILookupParameter<EngineAlgorithm>)Parameters[MetaOptimizationProblem.AlgorithmTypeParameterName]; }
|
---|
31 | }
|
---|
32 | public ILookupParameter<IItemList<ISingleObjectiveProblem>> ProblemsParameter {
|
---|
33 | get { return (ILookupParameter<IItemList<ISingleObjectiveProblem>>)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> ProblemQualityMediansParameter {
|
---|
43 | get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityMedians"]; }
|
---|
44 | }
|
---|
45 |
|
---|
46 | public IntValue Repetitions {
|
---|
47 | get { return RepetitionsParameter.ActualValue; }
|
---|
48 | }
|
---|
49 |
|
---|
50 | public ParameterConfigurationEvaluator()
|
---|
51 | : base() {
|
---|
52 | Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the ParameterVector."));
|
---|
53 | Parameters.Add(new LookupParameter<EngineAlgorithm>(MetaOptimizationProblem.AlgorithmTypeParameterName, "Missing description."));
|
---|
54 | Parameters.Add(new LookupParameter<IItemList<ISingleObjectiveProblem>>(MetaOptimizationProblem.ProblemsParameterName, "Missing description."));
|
---|
55 | Parameters.Add(new LookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", "Missing description."));
|
---|
56 | Parameters.Add(new LookupParameter<IntValue>(MetaOptimizationProblem.RepetitionsParameterName, "Number of evaluations on one problem."));
|
---|
57 | Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityMedians", ""));
|
---|
58 | }
|
---|
59 |
|
---|
60 | [StorableConstructor]
|
---|
61 | protected ParameterConfigurationEvaluator(bool deserializing) : base(deserializing) { }
|
---|
62 | protected ParameterConfigurationEvaluator(ParameterConfigurationEvaluator original, Cloner cloner)
|
---|
63 | : base(original, cloner) {
|
---|
64 | }
|
---|
65 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
66 | return new ParameterConfigurationEvaluator(this, cloner);
|
---|
67 | }
|
---|
68 |
|
---|
69 | public override IOperation Apply() {
|
---|
70 | EngineAlgorithm algorithm = (EngineAlgorithm)AlgorithmParameter.ActualValue.Clone();
|
---|
71 | IItemList<ISingleObjectiveProblem> problems = ProblemsParameter.ActualValue;
|
---|
72 |
|
---|
73 | double[] medians;
|
---|
74 | if (ProblemQualityMediansParameter.ActualValue == null) {
|
---|
75 | // this is generation zero. no reference qualities for scaling have been calculated yet. calculate a random individuum to get reference values
|
---|
76 | medians = new double[problems.Count]; // todo
|
---|
77 | for (int i = 0; i < medians.Length; i++) {
|
---|
78 | medians[i] = 10;
|
---|
79 | }
|
---|
80 | } else {
|
---|
81 | medians = ProblemQualityMediansParameter.ActualValue.ToArray();
|
---|
82 | }
|
---|
83 |
|
---|
84 | // set parameters
|
---|
85 | ParameterConfigurationParameter.ActualValue.Parameterize(algorithm);
|
---|
86 | algorithm.StoreAlgorithmInEachRun = false;
|
---|
87 |
|
---|
88 | List<List<double>> qualities = new List<List<double>>();
|
---|
89 | List<List<TimeSpan>> executionTimes = new List<List<TimeSpan>>();
|
---|
90 | algorithm.Engine = new SequentialEngine.SequentialEngine();
|
---|
91 | algorithm.Prepare(true);
|
---|
92 |
|
---|
93 | foreach (ISingleObjectiveProblem problem in problems) {
|
---|
94 | algorithm.Problem = (IProblem)problem.Clone();
|
---|
95 | var problemQualities = new List<double>();
|
---|
96 | var problemExecutionTimes = new List<TimeSpan>();
|
---|
97 |
|
---|
98 | for (int i = 0; i < Repetitions.Value; i++) {
|
---|
99 | algorithm.Prepare();
|
---|
100 |
|
---|
101 | AlgorithmExecutor executor = new AlgorithmExecutor(algorithm);
|
---|
102 | executor.StartSync();
|
---|
103 |
|
---|
104 | if (algorithm.ExecutionState == ExecutionState.Paused) {
|
---|
105 | // this parametercombination was bad. set penalty for this solution
|
---|
106 | problemQualities.Add(PenaltyQuality); // todo: respect Maximization; problem: this messes up average value; solution: use currently worst quality*2
|
---|
107 | problemExecutionTimes.Add(algorithm.ExecutionTime);
|
---|
108 | } else {
|
---|
109 | problemQualities.Add(((DoubleValue)algorithm.Results["BestQuality"].Value).Value);
|
---|
110 | problemExecutionTimes.Add(algorithm.ExecutionTime);
|
---|
111 |
|
---|
112 | // parameters will be stored in ParameterConfigurationTree anyway. they would be redundant in runs
|
---|
113 | algorithm.Runs.Last().Parameters.Clear();
|
---|
114 | // but keep the problem, since this differs in runs
|
---|
115 | algorithm.Runs.Last().Parameters.Add("Problem", problem);
|
---|
116 | }
|
---|
117 | }
|
---|
118 | qualities.Add(problemQualities);
|
---|
119 | executionTimes.Add(problemExecutionTimes);
|
---|
120 | }
|
---|
121 | algorithm.Prepare();
|
---|
122 |
|
---|
123 | ParameterConfigurationParameter.ActualValue.AverageExecutionTimes = new ItemList<TimeSpanValue>(executionTimes.Select(t => new TimeSpanValue(TimeSpan.FromMilliseconds(t.Average(ts => ts.TotalMilliseconds)))));
|
---|
124 | ParameterConfigurationParameter.ActualValue.Repetitions = (IntValue)Repetitions.Clone();
|
---|
125 | ParameterConfigurationParameter.ActualValue.BestQualities = new DoubleArray(qualities.Select(q => q.Min()).ToArray()); // todo: respect Maximization:true/false
|
---|
126 | ParameterConfigurationParameter.ActualValue.AverageQualities = new DoubleArray(qualities.Select(q => q.Average()).ToArray());
|
---|
127 | ParameterConfigurationParameter.ActualValue.WorstQualities = new DoubleArray(qualities.Select(q => q.Max()).ToArray()); // todo: respect Maximization:true/false
|
---|
128 | ParameterConfigurationParameter.ActualValue.QualityVariances = new DoubleArray(qualities.Select(q => q.Variance()).ToArray());
|
---|
129 | ParameterConfigurationParameter.ActualValue.QualityStandardDeviations = new DoubleArray(qualities.Select(q => q.StandardDeviation()).ToArray());
|
---|
130 | ParameterConfigurationParameter.ActualValue.Runs = (RunCollection)algorithm.Runs.Clone();
|
---|
131 |
|
---|
132 | // normalize qualities
|
---|
133 | double[] qualitiesNormalized = new double[problems.Count];
|
---|
134 | for (int i = 0; i < problems.Count; i++) {
|
---|
135 | qualitiesNormalized[i] = qualities[i].Average() / medians[i];
|
---|
136 | }
|
---|
137 | ParameterConfigurationParameter.ActualValue.QualitiesNormalized = new DoubleArray(qualitiesNormalized);
|
---|
138 | ParameterConfigurationParameter.ActualValue.AverageQualityNormalized = new DoubleValue(qualitiesNormalized.Average());
|
---|
139 |
|
---|
140 | this.QualityParameter.ActualValue = ParameterConfigurationParameter.ActualValue.AverageQualityNormalized;
|
---|
141 |
|
---|
142 | return base.Apply();
|
---|
143 | }
|
---|
144 |
|
---|
145 | public static double Variance(IEnumerable<double> source) {
|
---|
146 | double avg = source.Average();
|
---|
147 | double d = source.Aggregate(0.0, (total, next) => total += Math.Pow(next - avg, 2));
|
---|
148 | return d / (source.Count() - 1);
|
---|
149 | }
|
---|
150 |
|
---|
151 | public static double StandardDeviation(IEnumerable<double> source) {
|
---|
152 | return Math.Sqrt(source.Variance());
|
---|
153 | }
|
---|
154 | }
|
---|
155 |
|
---|
156 | /// <summary>
|
---|
157 | /// Can execute an algorithm synchronously
|
---|
158 | /// </summary>
|
---|
159 | public class AlgorithmExecutor {
|
---|
160 | private EngineAlgorithm algorithm;
|
---|
161 | private AutoResetEvent waitHandle = new AutoResetEvent(false);
|
---|
162 |
|
---|
163 | public AlgorithmExecutor(EngineAlgorithm algorithm) {
|
---|
164 | this.algorithm = algorithm;
|
---|
165 | }
|
---|
166 |
|
---|
167 | public void StartSync() {
|
---|
168 | algorithm.Stopped += new EventHandler(algorithm_Stopped);
|
---|
169 | algorithm.Paused += new EventHandler(algorithm_Paused);
|
---|
170 | algorithm.Start();
|
---|
171 | waitHandle.WaitOne();
|
---|
172 | waitHandle.Dispose();
|
---|
173 | algorithm.Stopped -= new EventHandler(algorithm_Stopped);
|
---|
174 | algorithm.Paused -= new EventHandler(algorithm_Paused);
|
---|
175 | }
|
---|
176 |
|
---|
177 | void algorithm_Paused(object sender, EventArgs e) {
|
---|
178 | waitHandle.Set();
|
---|
179 | }
|
---|
180 |
|
---|
181 | void algorithm_Stopped(object sender, EventArgs e) {
|
---|
182 | waitHandle.Set();
|
---|
183 | }
|
---|
184 | }
|
---|
185 | }
|
---|