source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/PopulationReducers/GQAPQualitySimilarityReducer.cs @ 13820

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 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.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
  [Item("GQAPQualitySimilarityReducer", "Reduces two populations two one by using quality and similarity information to obtain a population of high quality, but also diverse solutions.")]
  [StorableClass]
  public class GQAPQualitySimilarityReducer : SingleSuccessorOperator, IAssignmentAwareGQAPOperator, IQualityAwareGQAPOperator, IPopulationReducer {
    public ILookupParameter<IntegerVector> AssignmentParameter {
      get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
    }
    public ILookupParameter<BoolValue> MaximizationParameter {
      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
    }
    public ILookupParameter<DoubleValue> QualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
    }
    public ILookupParameter<DoubleValue> InstallationQualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
    }
    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
    }
    public ILookupParameter<IntValue> MinimumPopulationSizeParameter {
      get { return (ILookupParameter<IntValue>)Parameters["MinimumPopulationSize"]; }
    }
    public ILookupParameter<IntValue> MaximumPopulationSizeParameter {
      get { return (ILookupParameter<IntValue>)Parameters["MaximumPopulationSize"]; }
    }

    [StorableConstructor]
    protected GQAPQualitySimilarityReducer(bool deserializing) : base(deserializing) { }
    protected GQAPQualitySimilarityReducer(GQAPQualitySimilarityReducer original, Cloner cloner) : base(original, cloner) { }
    public GQAPQualitySimilarityReducer()
      : base() {
      Parameters.Add(new LookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
      Parameters.Add(new LookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
      Parameters.Add(new LookupParameter<IntValue>("MinimumPopulationSize", "The size of the population that should not be undershot."));
      Parameters.Add(new LookupParameter<IntValue>("MaximumPopulationSize", "The size of the population that should not be surpassed."));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new GQAPQualitySimilarityReducer(this, cloner);
    }

    public override IOperation Apply() {
      string vectorName = AssignmentParameter.TranslatedName;
      string qualityName = QualityParameter.TranslatedName;
      int populationSize = MaximumPopulationSizeParameter.ActualValue.Value;
      bool maximization = MaximizationParameter.ActualValue.Value;

      IScope remaining = ExecutionContext.Scope.SubScopes[0];
      IScope selected = ExecutionContext.Scope.SubScopes[1];

      List<Individual> population =
        remaining.SubScopes.Select(x => new Individual((IntegerVector)x.Variables[vectorName].Value,
                                                      ((DoubleValue)x.Variables[qualityName].Value).Value,
                                                      x)).ToList();
      HashSet<Individual> candidates = new HashSet<Individual>(
        selected.SubScopes.Select(x => new Individual((IntegerVector)x.Variables[vectorName].Value,
                                                     ((DoubleValue)x.Variables[qualityName].Value).Value,
                                                     x)));

      foreach (var candidate in candidates) {
        double[] similarities = population.Select(x => IntegerVectorEqualityComparer.GetSimilarity(x.Solution, candidate.Solution)).ToArray();
        if (!similarities.Any()) {
          population.Add(candidate);
          break;
        }
        if (similarities.Max() == 1.0) break;
        if (population.Count < populationSize) {
          population.Add(candidate);
        } else {
          var replacement = population.Select((v, i) => new { V = v, Index = i })
                                      .Where(x => (maximization && x.V.Quality < candidate.Quality)
                                               || (!maximization && x.V.Quality > candidate.Quality));
          if (replacement.Any()) {
            replacement.OrderBy(x => similarities[x.Index]).ToArray();
            population.Remove(replacement.Last().V);
            population.Add(candidate);
          }
        }
      }

      ExecutionContext.Scope.SubScopes.Clear();
      ExecutionContext.Scope.SubScopes.AddRange(population.Select(x => x.Scope));

      return base.Apply();
    }

    private class Individual {
      internal IntegerVector Solution { get; set; }
      internal double Quality { get; set; }
      internal IScope Scope { get; set; }

      internal Individual(IntegerVector vector, double quality, IScope scope) {
        Solution = vector;
        Quality = quality;
        Scope = scope;
      }
    }
  }
}