[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 | }
|
---|
[5313] | 29 | public ILookupParameter<TypeValue> AlgorithmTypeParameter {
|
---|
| 30 | get { return (ILookupParameter<TypeValue>)Parameters[MetaOptimizationProblem.AlgorithmTypeParameterName]; }
|
---|
[5111] | 31 | }
|
---|
[5337] | 32 | public ILookupParameter<IItemList<IProblem>> ProblemsParameter {
|
---|
| 33 | get { return (ILookupParameter<IItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
|
---|
[5111] | 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 |
|
---|
[5293] | 42 | public LookupParameter<DoubleArray> ProblemQualityReferencesParameter {
|
---|
| 43 | get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityReferences"]; }
|
---|
[5212] | 44 | }
|
---|
[5303] | 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 |
|
---|
[5111] | 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."));
|
---|
[5313] | 59 | Parameters.Add(new LookupParameter<TypeValue>(MetaOptimizationProblem.AlgorithmTypeParameterName, "Missing description."));
|
---|
[5337] | 60 | Parameters.Add(new LookupParameter<IItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName, "Missing description."));
|
---|
[5111] | 61 | Parameters.Add(new LookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", "Missing description."));
|
---|
| 62 | Parameters.Add(new LookupParameter<IntValue>(MetaOptimizationProblem.RepetitionsParameterName, "Number of evaluations on one problem."));
|
---|
[5293] | 63 | Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityReferences", ""));
|
---|
[5303] | 64 | Parameters.Add(new LookupParameter<IntValue>("Generations", ""));
|
---|
| 65 | Parameters.Add(new LookupParameter<ResultCollection>("Results", ""));
|
---|
[5111] | 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() {
|
---|
[5303] | 78 | ParameterConfigurationTree parameterConfiguration = ParameterConfigurationParameter.ActualValue;
|
---|
[5337] | 79 | IAlgorithm algorithm = (IAlgorithm)Activator.CreateInstance(AlgorithmTypeParameter.ActualValue.Value);
|
---|
| 80 | IItemList<IProblem> problems = ProblemsParameter.ActualValue;
|
---|
[5303] | 81 | ItemDictionary<StringValue, RunCollection> runsCache = ResultsParameter.ActualValue.ContainsKey("Runs") ? (ItemDictionary<StringValue, RunCollection>)ResultsParameter.ActualValue["Runs"].Value : null;
|
---|
| 82 | double[] referenceQualities = GetReferenceQualities(problems);
|
---|
[5111] | 83 |
|
---|
[5303] | 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 |
|
---|
[5337] | 115 | private double[] GetReferenceQualities(IItemList<IProblem> problems) {
|
---|
[5293] | 116 | double[] referenceQualities;
|
---|
| 117 | if (ProblemQualityReferencesParameter.ActualValue == null) {
|
---|
[5303] | 118 | // this is generation zero. no reference qualities for normalization have been calculated yet. in this special case the ReferenceQualityAnalyzer will do the normalization
|
---|
[5293] | 119 | referenceQualities = new double[problems.Count];
|
---|
| 120 | for (int i = 0; i < referenceQualities.Length; i++) {
|
---|
| 121 | referenceQualities[i] = 1;
|
---|
[5212] | 122 | }
|
---|
| 123 | } else {
|
---|
[5293] | 124 | referenceQualities = ProblemQualityReferencesParameter.ActualValue.ToArray();
|
---|
[5212] | 125 | }
|
---|
[5303] | 126 | return referenceQualities;
|
---|
| 127 | }
|
---|
[5212] | 128 |
|
---|
[5337] | 129 | private RunCollection ExecuteAlgorithm(ParameterConfigurationTree parameterConfiguration, IAlgorithm algorithm, IItemList<IProblem> problems) {
|
---|
| 130 | IAlgorithm algorithmClone = (IAlgorithm)algorithm.Clone();
|
---|
[5303] | 131 |
|
---|
[5111] | 132 | // set parameters
|
---|
[5303] | 133 | parameterConfiguration.Parameterize(algorithmClone);
|
---|
| 134 | algorithmClone.StoreAlgorithmInEachRun = false;
|
---|
[5111] | 135 |
|
---|
[5337] | 136 | if (algorithmClone is EngineAlgorithm) {
|
---|
| 137 | ((EngineAlgorithm)algorithmClone).Engine = new SequentialEngine.SequentialEngine();
|
---|
| 138 | }
|
---|
[5303] | 139 | algorithmClone.Prepare(true);
|
---|
[5111] | 140 |
|
---|
[5337] | 141 | foreach (IProblem problem in problems) {
|
---|
[5303] | 142 | algorithmClone.Problem = (IProblem)problem.Clone();
|
---|
[5111] | 143 |
|
---|
| 144 | for (int i = 0; i < Repetitions.Value; i++) {
|
---|
[5303] | 145 | algorithmClone.Prepare();
|
---|
[5111] | 146 |
|
---|
[5303] | 147 | AlgorithmExecutor executor = new AlgorithmExecutor(algorithmClone);
|
---|
[5207] | 148 | executor.StartSync();
|
---|
| 149 |
|
---|
[5303] | 150 | if (algorithmClone.ExecutionState == ExecutionState.Paused) {
|
---|
[5184] | 151 | // this parametercombination was bad. set penalty for this solution
|
---|
[5303] | 152 | // TODO!
|
---|
[5184] | 153 | }
|
---|
[5303] | 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);
|
---|
[5111] | 161 | }
|
---|
| 162 | }
|
---|
[5303] | 163 | algorithmClone.Prepare();
|
---|
| 164 | return algorithmClone.Runs;
|
---|
[5111] | 165 | }
|
---|
| 166 |
|
---|
[5293] | 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];
|
---|
[5281] | 171 | }
|
---|
| 172 | parameterConfigurationTree.QualitiesNormalized = new DoubleArray(qualitiesNormalized);
|
---|
| 173 | parameterConfigurationTree.AverageQualityNormalized = new DoubleValue(qualitiesNormalized.Average());
|
---|
| 174 | return parameterConfigurationTree.AverageQualityNormalized.Value;
|
---|
| 175 | }
|
---|
| 176 |
|
---|
[5111] | 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 | }
|
---|
[5207] | 186 | }
|
---|
[5111] | 187 | }
|
---|