[5111] | 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;
|
---|
[5207] | 12 | using HeuristicLab.Algorithms.GeneticAlgorithm;
|
---|
| 13 | using System.Threading.Tasks;
|
---|
| 14 | using System.Diagnostics;
|
---|
| 15 | using System.Reflection;
|
---|
[5111] | 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 {
|
---|
[5207] | 24 | private const double PenaltyQuality = 100000.0; // todo: use something better
|
---|
[5111] | 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 |
|
---|
[5212] | 42 | public LookupParameter<DoubleArray> ProblemQualityMediansParameter {
|
---|
| 43 | get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityMedians"]; }
|
---|
| 44 | }
|
---|
| 45 |
|
---|
[5111] | 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."));
|
---|
[5212] | 57 | Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityMedians", ""));
|
---|
[5111] | 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() {
|
---|
[5207] | 70 | EngineAlgorithm algorithm = (EngineAlgorithm)AlgorithmParameter.ActualValue.Clone();
|
---|
[5111] | 71 | IItemList<ISingleObjectiveProblem> problems = ProblemsParameter.ActualValue;
|
---|
| 72 |
|
---|
[5212] | 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++) {
|
---|
[5231] | 78 | medians[i] = 1;
|
---|
[5212] | 79 | }
|
---|
| 80 | } else {
|
---|
| 81 | medians = ProblemQualityMediansParameter.ActualValue.ToArray();
|
---|
| 82 | }
|
---|
| 83 |
|
---|
[5111] | 84 | // set parameters
|
---|
| 85 | ParameterConfigurationParameter.ActualValue.Parameterize(algorithm);
|
---|
| 86 | algorithm.StoreAlgorithmInEachRun = false;
|
---|
| 87 |
|
---|
[5212] | 88 | List<List<double>> qualities = new List<List<double>>();
|
---|
| 89 | List<List<TimeSpan>> executionTimes = new List<List<TimeSpan>>();
|
---|
[5111] | 90 | algorithm.Engine = new SequentialEngine.SequentialEngine();
|
---|
| 91 | algorithm.Prepare(true);
|
---|
| 92 |
|
---|
| 93 | foreach (ISingleObjectiveProblem problem in problems) {
|
---|
[5207] | 94 | algorithm.Problem = (IProblem)problem.Clone();
|
---|
[5212] | 95 | var problemQualities = new List<double>();
|
---|
| 96 | var problemExecutionTimes = new List<TimeSpan>();
|
---|
[5111] | 97 |
|
---|
| 98 | for (int i = 0; i < Repetitions.Value; i++) {
|
---|
| 99 | algorithm.Prepare();
|
---|
| 100 |
|
---|
[5207] | 101 | AlgorithmExecutor executor = new AlgorithmExecutor(algorithm);
|
---|
| 102 | executor.StartSync();
|
---|
| 103 |
|
---|
| 104 | if (algorithm.ExecutionState == ExecutionState.Paused) {
|
---|
[5184] | 105 | // this parametercombination was bad. set penalty for this solution
|
---|
[5212] | 106 | problemQualities.Add(PenaltyQuality); // todo: respect Maximization; problem: this messes up average value; solution: use currently worst quality*2
|
---|
| 107 | problemExecutionTimes.Add(algorithm.ExecutionTime);
|
---|
[5184] | 108 | } else {
|
---|
[5212] | 109 | problemQualities.Add(((DoubleValue)algorithm.Results["BestQuality"].Value).Value);
|
---|
| 110 | problemExecutionTimes.Add(algorithm.ExecutionTime);
|
---|
[5184] | 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 | }
|
---|
[5111] | 117 | }
|
---|
[5212] | 118 | qualities.Add(problemQualities);
|
---|
| 119 | executionTimes.Add(problemExecutionTimes);
|
---|
[5111] | 120 | }
|
---|
| 121 | algorithm.Prepare();
|
---|
| 122 |
|
---|
[5212] | 123 | ParameterConfigurationParameter.ActualValue.AverageExecutionTimes = new ItemList<TimeSpanValue>(executionTimes.Select(t => new TimeSpanValue(TimeSpan.FromMilliseconds(t.Average(ts => ts.TotalMilliseconds)))));
|
---|
[5184] | 124 | ParameterConfigurationParameter.ActualValue.Repetitions = (IntValue)Repetitions.Clone();
|
---|
[5212] | 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());
|
---|
[5184] | 130 | ParameterConfigurationParameter.ActualValue.Runs = (RunCollection)algorithm.Runs.Clone();
|
---|
[5111] | 131 |
|
---|
[5212] | 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());
|
---|
[5111] | 139 |
|
---|
[5212] | 140 | this.QualityParameter.ActualValue = ParameterConfigurationParameter.ActualValue.AverageQualityNormalized;
|
---|
| 141 |
|
---|
[5111] | 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 | }
|
---|
[5207] | 154 | }
|
---|
[5111] | 155 |
|
---|
[5212] | 156 | /// <summary>
|
---|
| 157 | /// Can execute an algorithm synchronously
|
---|
| 158 | /// </summary>
|
---|
[5207] | 159 | public class AlgorithmExecutor {
|
---|
| 160 | private EngineAlgorithm algorithm;
|
---|
| 161 | private AutoResetEvent waitHandle = new AutoResetEvent(false);
|
---|
[5184] | 162 |
|
---|
[5207] | 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 | }
|
---|
[5111] | 184 | }
|
---|
| 185 | }
|
---|