source: branches/1614_GeneralizedQAP/HeuristicLab.Analysis/3.3/BestNScopesSolutionAnalyzer.cs @ 17505

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Optimization.Operators;
using HeuristicLab.Parameters;

namespace HeuristicLab.Analysis {
  /// <summary>
  /// An operator that extracts (clones) the scope containing the best quality.
  /// </summary>
  [Item("BestNScopesSolutionAnalyzer", "An operator that maintains at most N scopes containing good quality solutions.")]
  [StorableType("730D7F81-57B2-4843-B68D-83D43B1A525E")]
  public class BestNScopesSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer, ISingleObjectiveOperator {

    public virtual bool EnabledByDefault {
      get { return true; }
    }
    public LookupParameter<BoolValue> MaximizationParameter {
      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
    }
    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public IFixedValueParameter<StringValue> BestSolutionsResultNameParameter {
      get { return (IFixedValueParameter<StringValue>)Parameters["BestSolutions ResultName"]; }
    }
    public IValueLookupParameter<ResultCollection> ResultsParameter {
      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
    }
    public IValueParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
      get { return (IValueParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
    }
    private IFixedValueParameter<IntValue> NParameter {
      get { return (IFixedValueParameter<IntValue>)Parameters["N"]; }
    }
    private IFixedValueParameter<DoubleValue> MaximumSimilarityParameter {
      get { return (IFixedValueParameter<DoubleValue>)Parameters["MaximumSimilarity"]; }
    }

    public string BestSolutionsResultName {
      get { return BestSolutionsResultNameParameter.Value.Value; }
      set { BestSolutionsResultNameParameter.Value.Value = value; }
    }

    public int N {
      get { return NParameter.Value.Value; }
      set { NParameter.Value.Value = value; }
    }

    public double MaximumSimilarity {
      get { return MaximumSimilarityParameter.Value.Value; }
      set { MaximumSimilarityParameter.Value.Value = value; }
    }

    #region Storing & Cloning
    [StorableConstructor]
    protected BestNScopesSolutionAnalyzer(StorableConstructorFlag _) : base(_) { }
    protected BestNScopesSolutionAnalyzer(BestNScopesSolutionAnalyzer original, Cloner cloner) : base(original, cloner) { }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new BestNScopesSolutionAnalyzer(this, cloner);
    }
    #endregion
    public BestNScopesSolutionAnalyzer()
      : base() {
      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem."));
      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the solutions."));
      Parameters.Add(new FixedValueParameter<StringValue>("BestSolutions ResultName", "The name of the result for storing the best solution.", new StringValue("Best Solutions")));
      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the solution should be stored."));
      Parameters.Add(new ValueParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The solution similarity calculator that is used to compare two solution scopes.", new QualitySimilarityCalculator()));
      Parameters.Add(new FixedValueParameter<IntValue>("N", "The N best solutions that are kept.", new IntValue(10)));
      Parameters.Add(new FixedValueParameter<DoubleValue>("MaximumSimilarity", "The maximum similarity between two solutions in order to be remembered in the list.", new DoubleValue(0.8)));
    }

    public override IOperation Apply() {
      var results = ResultsParameter.ActualValue;
      if (results.ContainsKey(BestSolutionsResultName) && !typeof(ScopeList).IsAssignableFrom(results[BestSolutionsResultName].DataType)) {
        throw new InvalidOperationException(string.Format("Could not add best solutions result, because there is already a result with the name \"{0}\" present in the result collection.", BestSolutionsResultName));
      }
      ScopeList bestScopes = null;
      if (results.ContainsKey(BestSolutionsResultName)) {
        bestScopes = (ScopeList)results[BestSolutionsResultName].Value;
      } else {
        bestScopes = new ScopeList();
        results.Add(new Result(BestSolutionsResultName, bestScopes));
      }

      var max = MaximizationParameter.ActualValue.Value;
      var simCalc = SimilarityCalculatorParameter.Value;
      var maxSim = MaximumSimilarity;
      var qualityName = QualityParameter.TranslatedName;
      var depth = QualityParameter.Depth;

      IEnumerable<IScope> scopes = new [] { ExecutionContext.Scope };
      for (var j = 0; j < depth; j++)
        scopes = scopes.SelectMany(x => x.SubScopes);

      scopes = max ? scopes.OrderByDescending(x => ((DoubleValue)x.Variables[qualityName].Value).Value)
                   : scopes.OrderBy(x => ((DoubleValue)x.Variables[qualityName].Value).Value);
      
      var newList = new ScopeList(bestScopes.Take(N));
      var cloner = new Cloner();
      // avoid cloning the results collection that the solution is put in
      cloner.RegisterClonedObject(results, new ResultCollection());

      foreach (var s in scopes) {
        bool isDiverse = true, isBetterThanWorst = false, isIdentical = false;
        var worstIdx = -1;
        IScope worst = null;
        var idx = 0;
        foreach (var a in newList) {
          if (IsBetter(s, a, qualityName, max)) {
            isBetterThanWorst = true;
            if (worst == null || IsBetter(worst, a, qualityName, max)) {
              worst = a;
              worstIdx = idx;
            }
          }
          var similarity = simCalc.CalculateSolutionSimilarity(s, a);
          if (similarity.IsAlmost(1.0)) isIdentical = true;
          if (similarity > maxSim) isDiverse = false;
          idx++;

          if (isIdentical || (newList.Count >= N && !isDiverse)) break;
        }
        // to accept a new solution it needs to be
        // A) not identical
        // B) must be less similar than a certain value
        // C) must be better than at least one solution already accepted
        // The exception to B) and C) is when the list is not full yet
        if (isIdentical || (newList.Count >= N && !(isDiverse && isBetterThanWorst))) continue;
        // avoid cloning subscopes of the solution
        cloner.RegisterClonedObject(s.SubScopes, new ScopeList());
        newList.Add(cloner.Clone(s));
        if (newList.Count > N) newList.RemoveAt(worstIdx);
      }

      bestScopes.Replace(newList);

      return base.Apply();
    }

    private static bool IsBetter(IScope a, IScope b, string qualityName, bool max) {
      return max ? ((DoubleValue)a.Variables[qualityName].Value).Value > ((DoubleValue)b.Variables[qualityName].Value).Value
                 : ((DoubleValue)a.Variables[qualityName].Value).Value < ((DoubleValue)b.Variables[qualityName].Value).Value;
    }
  }
}