source: branches/HeuristicLab.MetaOptimization/HeuristicLab.Problems.MetaOptimization/3.3/Evaluators/ParameterConfigurationEvaluator.cs @ 5357

using System;
using System.Linq;
using System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using System.Collections.Generic;
using HeuristicLab.Algorithms.GeneticAlgorithm;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Reflection;

namespace HeuristicLab.Problems.MetaOptimization {
  /// <summary>
  /// A base class for operators which evaluate TSP solutions.
  /// </summary>
  [Item("ParameterConfigurationEvaluator", "A base class for operators which evaluate Meta Optimization solutions.")]
  [StorableClass]
  public class ParameterConfigurationEvaluator : SingleSuccessorOperator, IParameterConfigurationEvaluator, IStochasticOperator {
    public ILookupParameter<IRandom> RandomParameter {
      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    }
    public ILookupParameter<DoubleValue> QualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ILookupParameter<TypeValue> AlgorithmTypeParameter {
      get { return (ILookupParameter<TypeValue>)Parameters[MetaOptimizationProblem.AlgorithmTypeParameterName]; }
    }
    public ILookupParameter<IItemList<IProblem>> ProblemsParameter {
      get { return (ILookupParameter<IItemList<IProblem>>)Parameters[MetaOptimizationProblem.ProblemsParameterName]; }
    }
    public ILookupParameter<ParameterConfigurationTree> ParameterConfigurationParameter {
      get { return (ILookupParameter<ParameterConfigurationTree>)Parameters["ParameterConfigurationTree"]; }
    }
    public LookupParameter<IntValue> RepetitionsParameter {
      get { return (LookupParameter<IntValue>)Parameters[MetaOptimizationProblem.RepetitionsParameterName]; }
    }

    public LookupParameter<DoubleArray> ProblemQualityReferencesParameter {
      get { return (LookupParameter<DoubleArray>)Parameters["ProblemQualityReferences"]; }
    }
    public LookupParameter<IntValue> GenerationsParameter {
      get { return (LookupParameter<IntValue>)Parameters["Generations"]; }
    }
    public LookupParameter<ResultCollection> ResultsParameter {
      get { return (LookupParameter<ResultCollection>)Parameters["Results"]; }
    }
    
    public IntValue Repetitions {
      get { return RepetitionsParameter.ActualValue; }
    }

    public ParameterConfigurationEvaluator()
      : base() {
      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used to initialize the new random permutation."));
      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The evaluated quality of the ParameterVector."));
      Parameters.Add(new LookupParameter<TypeValue>(MetaOptimizationProblem.AlgorithmTypeParameterName, "Missing description."));
      Parameters.Add(new LookupParameter<IItemList<IProblem>>(MetaOptimizationProblem.ProblemsParameterName, "Missing description."));
      Parameters.Add(new LookupParameter<ParameterConfigurationTree>("ParameterConfigurationTree", "Missing description."));
      Parameters.Add(new LookupParameter<IntValue>(MetaOptimizationProblem.RepetitionsParameterName, "Number of evaluations on one problem."));
      Parameters.Add(new LookupParameter<DoubleArray>("ProblemQualityReferences", ""));
      Parameters.Add(new LookupParameter<IntValue>("Generations", ""));
      Parameters.Add(new LookupParameter<ResultCollection>("Results", ""));
    }

    [StorableConstructor]
    protected ParameterConfigurationEvaluator(bool deserializing) : base(deserializing) { }
    protected ParameterConfigurationEvaluator(ParameterConfigurationEvaluator original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new ParameterConfigurationEvaluator(this, cloner);
    }

    public override IOperation Apply() {
      IRandom random = RandomParameter.ActualValue;
      ParameterConfigurationTree parameterConfiguration = ParameterConfigurationParameter.ActualValue;
      IAlgorithm algorithm = (IAlgorithm)Activator.CreateInstance(AlgorithmTypeParameter.ActualValue.Value);
      IItemList<IProblem> problems = ProblemsParameter.ActualValue;
      ItemDictionary<StringValue, RunCollection> runsCache = ResultsParameter.ActualValue.ContainsKey("Runs") ? (ItemDictionary<StringValue, RunCollection>)ResultsParameter.ActualValue["Runs"].Value : null;
      double[] referenceQualities = GetReferenceQualities(problems);

      RunCollection runs;
      if (runsCache != null && runsCache.Count(x => x.Key.Value == parameterConfiguration.ParameterInfoString) > 0) {
        runs = runsCache.Single(x => x.Key.Value == parameterConfiguration.ParameterInfoString).Value;
        Console.WriteLine("Used Cache for {0}", parameterConfiguration.ParameterInfoString);
      } else {
        do {
          runs = ExecuteAlgorithm(parameterConfiguration, algorithm, problems, Repetitions.Value, GenerationsParameter.ActualValue != null ? GenerationsParameter.ActualValue.Value : 0);
          if (runs == null) {
            Repair(parameterConfiguration, random);
            parameterConfiguration.Parameterize(algorithm);
          }
        } while (runs == null);
      }

      List<List<double>> qualities = new List<List<double>>();
      List<List<TimeSpan>> executionTimes = new List<List<TimeSpan>>();

      for (int i = 0; i < problems.Count; i++) {
        var problemRuns = runs.Where(x => ((IntValue)x.Results["Meta.ProblemIndex"]).Value == i + 1);
        qualities.Add(problemRuns.Select(x => ((DoubleValue)x.Results["BestQuality"]).Value).ToList());
        executionTimes.Add(problemRuns.Select(x => ((TimeSpanValue)x.Results["Execution Time"]).Value).ToList());
      }

      parameterConfiguration.AverageExecutionTimes = new ItemList<TimeSpanValue>(executionTimes.Select(t => new TimeSpanValue(TimeSpan.FromMilliseconds(t.Average(ts => ts.TotalMilliseconds)))));
      parameterConfiguration.Repetitions = (IntValue)Repetitions.Clone();
      parameterConfiguration.BestQualities = new DoubleArray(qualities.Select(q => q.Min()).ToArray()); // todo: respect Maximization:true/false
      parameterConfiguration.AverageQualities = new DoubleArray(qualities.Select(q => q.Average()).ToArray());
      parameterConfiguration.WorstQualities = new DoubleArray(qualities.Select(q => q.Max()).ToArray()); // todo: respect Maximization:true/false
      parameterConfiguration.QualityVariances = new DoubleArray(qualities.Select(q => q.Variance()).ToArray());
      parameterConfiguration.QualityStandardDeviations = new DoubleArray(qualities.Select(q => q.StandardDeviation()).ToArray());
      parameterConfiguration.Runs = (RunCollection)runs.Clone();

      this.QualityParameter.ActualValue = new DoubleValue(NormalizeQualities(parameterConfiguration, referenceQualities));

      return base.Apply();
    }

    /// <summary>
    /// This method should repair an invalid parameterConfiguration.
    /// The strategy is to just randomize parameter settings. It's not guaranteed to be a vaild setting
    /// </summary>
    private void Repair(ParameterConfigurationTree parameterConfiguration, IRandom random) {
      parameterConfiguration.Randomize(random);
    }

    private double[] GetReferenceQualities(IItemList<IProblem> problems) {
      double[] referenceQualities;
      if (ProblemQualityReferencesParameter.ActualValue == null) {
        // this is generation zero. no reference qualities for normalization have been calculated yet. in this special case the ReferenceQualityAnalyzer will do the normalization
        referenceQualities = new double[problems.Count];
        for (int i = 0; i < referenceQualities.Length; i++) {
          referenceQualities[i] = 1;
        }
      } else {
        referenceQualities = ProblemQualityReferencesParameter.ActualValue.ToArray();
      }
      return referenceQualities;
    }

    /// <summary>
    /// Executes an algorithm 
    /// </summary>
    /// <param name="parameterConfiguration"></param>
    /// <param name="algorithm"></param>
    /// <param name="problems"></param>
    /// <returns></returns>
    private static RunCollection ExecuteAlgorithm(ParameterConfigurationTree parameterConfiguration, IAlgorithm algorithm, IItemList<IProblem> problems, int repetitions, int currentGeneration) {
      IAlgorithm algorithmClone = (IAlgorithm)algorithm.Clone();
      var parameterNames = new List<string>();
      var resultNames = new List<string> { "BestQuality", "Execution Time" };
      parameterConfiguration.CollectOptimizedParameterNames(parameterNames, "");

      // set parameters
      parameterConfiguration.Parameterize(algorithmClone);
      algorithmClone.StoreAlgorithmInEachRun = false;

      if (algorithmClone is EngineAlgorithm) {
        ((EngineAlgorithm)algorithmClone).Engine = new SequentialEngine.SequentialEngine();
      }
      algorithmClone.Prepare(true);

      foreach (IProblem problem in problems) {
        algorithmClone.Problem = (IProblem)problem.Clone();

        for (int i = 0; i < repetitions; i++) {
          algorithmClone.Prepare();

          AlgorithmExecutor executor = new AlgorithmExecutor(algorithmClone);
          executor.StartSync();

          if (algorithmClone.ExecutionState == ExecutionState.Paused) {
            // the parameter settings were invalid. 
            // (1) set penalty for this solution. 
            //     it's difficult to create penalty values for BestQuality and ExecutionTime. Maybe ReferenceQuality * X (but what about ExecutionTime?)
            //     therefore use repair instead.
            
            // (2) repair and retry
            return null;
          }
          int problemIndex = problems.IndexOf(problem) + 1;
          IRun run = algorithmClone.Runs.Last();
          CleanRun(run, resultNames, parameterNames);
          run.Results.Add("Meta.FromCache", new BoolValue(false));
          run.Results.Add("Meta.Generation", new IntValue(currentGeneration));
          run.Results.Add("Meta.ProblemIndex", new IntValue(problemIndex));
          int runCountOfThisProblem = algorithmClone.Runs.Where(x => ((IntValue)x.Results["Meta.ProblemIndex"]).Value == problemIndex).Count();
          run.Name = string.Format("{0} Problem {1} Run {2}", parameterConfiguration.ParameterInfoString, problemIndex, runCountOfThisProblem);
        }
      }
      algorithmClone.Prepare();
      return algorithmClone.Runs;
    }

    /// <summary>
    /// Removes all information from the run which is not needed for lated analysis
    /// only keep the results which are important and the parameters which were optimized
    /// </summary>
    private static void CleanRun(IRun run, IEnumerable<string> resultsToKeep, IEnumerable<string> parametersToKeep) {
      var resultsToRemove = new List<string>();
      var parametersToRemove = new List<string>();
      foreach (var result in run.Results) {
        if (!resultsToKeep.Contains(result.Key))
          resultsToRemove.Add(result.Key);
      }
      foreach (var parameter in run.Parameters) {
        if (!parametersToKeep.Contains(parameter.Key))
          parametersToRemove.Add(parameter.Key);
      }

      foreach (var result in resultsToRemove)
        run.Results.Remove(result);
      foreach (var parameter in parametersToRemove)
        run.Parameters.Remove(parameter);
    }

    public static double NormalizeQualities(ParameterConfigurationTree parameterConfigurationTree, double[] referenceQualities) {
      double[] qualitiesNormalized = new double[referenceQualities.Length];
      for (int i = 0; i < referenceQualities.Length; i++) {
        qualitiesNormalized[i] = parameterConfigurationTree.AverageQualities[i] / referenceQualities[i];
      }
      parameterConfigurationTree.QualitiesNormalized = new DoubleArray(qualitiesNormalized);
      parameterConfigurationTree.AverageQualityNormalized = new DoubleValue(qualitiesNormalized.Average());
      return parameterConfigurationTree.AverageQualityNormalized.Value;
    }

    public static double Variance(IEnumerable<double> source) {
      double avg = source.Average();
      double d = source.Aggregate(0.0, (total, next) => total += Math.Pow(next - avg, 2));
      return d / (source.Count() - 1);
    }

    public static double StandardDeviation(IEnumerable<double> source) {
      return Math.Sqrt(source.Variance());
    }
  }
}