#region License Information
/* HeuristicLab
* Copyright (C) 2002-2017 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 .
*/
#endregion
using System;
using System.Linq;
using System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {
///
/// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
///
[Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
[Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
[StorableClass]
public sealed class GRASP : StochasticAlgorithm {
public override bool SupportsPause {
get { return true; }
}
public override Type ProblemType {
get { return typeof(GQAP); }
}
public new GQAP Problem {
get { return (GQAP)base.Problem; }
set { base.Problem = value; }
}
[Storable]
private FixedValueParameter eliteSetSizeParameter;
private IFixedValueParameter EliteSetSizeParameter {
get { return eliteSetSizeParameter; }
}
[Storable]
private FixedValueParameter minimiumEliteSetSizeParameter;
public IFixedValueParameter MinimumEliteSetSizeParameter {
get { return minimiumEliteSetSizeParameter; }
}
[Storable]
private FixedValueParameter maximumLocalSearchIterationsParameter;
public IFixedValueParameter MaximumLocalSearchIterationsParameter {
get { return maximumLocalSearchIterationsParameter; }
}
[Storable]
private FixedValueParameter candidateSizeFactorParameter;
public IFixedValueParameter CandidateSizeFactorParameter {
get { return candidateSizeFactorParameter; }
}
[Storable]
private FixedValueParameter maximumCandidateListSizeParameter;
public IFixedValueParameter MaximumCandidateListSizeParameter {
get { return maximumCandidateListSizeParameter; }
}
[Storable]
private FixedValueParameter oneMoveProbabilityParameter;
public IFixedValueParameter OneMoveProbabilityParameter {
get { return oneMoveProbabilityParameter; }
}
[Storable]
private FixedValueParameter minimumDifferenceParameter;
public IFixedValueParameter MinimumDifferenceParameter {
get { return minimumDifferenceParameter; }
}
public int EliteSetSize {
get { return eliteSetSizeParameter.Value.Value; }
set { eliteSetSizeParameter.Value.Value = value; }
}
public int MinimumEliteSetSize {
get { return minimiumEliteSetSizeParameter.Value.Value; }
set { minimiumEliteSetSizeParameter.Value.Value = value; }
}
public int MaximumLocalSearchIterations {
get { return maximumLocalSearchIterationsParameter.Value.Value; }
set { maximumLocalSearchIterationsParameter.Value.Value = value; }
}
public double CandidateSizeFactor {
get { return candidateSizeFactorParameter.Value.Value; }
set { candidateSizeFactorParameter.Value.Value = value; }
}
public int MaximumCandidateListSize {
get { return maximumCandidateListSizeParameter.Value.Value; }
set { maximumCandidateListSizeParameter.Value.Value = value; }
}
public double OneMoveProbability {
get { return oneMoveProbabilityParameter.Value.Value; }
set { oneMoveProbabilityParameter.Value.Value = value; }
}
public int MinimumDifference {
get { return minimumDifferenceParameter.Value.Value; }
set { minimumDifferenceParameter.Value.Value = value; }
}
[StorableConstructor]
private GRASP(bool deserializing) : base(deserializing) { }
private GRASP(GRASP original, Cloner cloner)
: base(original, cloner) {
eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter);
oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
}
public GRASP() {
Parameters.Add(eliteSetSizeParameter = new FixedValueParameter("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
Parameters.Add(minimumDifferenceParameter = new FixedValueParameter("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));
Problem = new GQAP();
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GRASP(this, cloner);
}
protected override void Initialize(CancellationToken cancellationToken) {
base.Initialize(cancellationToken);
Context.Problem = Problem;
Context.BestQuality = double.NaN;
Context.BestSolution = null;
Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
Results.Add(new Result("BestSolution", typeof(GQAPSolution)));
Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
}
protected override void Run(CancellationToken cancellationToken) {
var eq = new IntegerVectorEqualityComparer();
while (!StoppingCriterion()) { // line 2 in Algorithm 1
// next: line 3 in Algorithm 1
var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
if (Context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
GQAPSolution pi_prime;
if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
pi_prime = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)).Solution; // line 6 in Algorithm 1
else {
// This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
Context.EvaluatedSolutions++;
}
ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
var pi_plus = Context.AtPopulation(Context.Random.Next(Context.PopulationCount)); // line 9 in Algorithm 1
pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
// Book-keeping
if (Context.BestQuality > fitness) {
Context.BestQuality = fitness;
Context.BestSolution = (GQAPSolution)pi_prime.Clone();
}
if (Context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
double[] similarities = Context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
var replacement = Context.Population.Select((v, i) => new { V = v, Index = i })
.Where(x => x.V.Fitness >= fit).ToArray();
if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
// next two lines: line 14 in Algorithm 1
replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
Context.ReplaceAtPopulation(replacement.Last().Index, Context.ToScope(pi_prime, fit));
}
}
} else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
Context.AddToPopulation(Context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
}
} else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
&& IsSufficientlyDifferent(pi_prime_vec)) /* cond. 2 of line 21 in Algorithm 1 */ {
var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
Context.EvaluatedSolutions++;
var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
Context.AddToPopulation(Context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
// Book-keeping
if (Context.PopulationCount == 1 || Context.BestQuality > fitness) {
Context.BestQuality = fitness;
Context.BestSolution = (GQAPSolution)pi_prime.Clone();
}
}
IResult result;
if (Results.TryGetValue("Iterations", out result))
((IntValue)result.Value).Value = Context.Iterations;
else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
if (Results.TryGetValue("EvaluatedSolutions", out result))
((IntValue)result.Value).Value = Context.EvaluatedSolutions;
else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
if (Results.TryGetValue("BestQuality", out result))
((DoubleValue)result.Value).Value = Context.BestQuality;
else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));
if (Results.TryGetValue("BestSolution", out result))
result.Value = Context.BestSolution;
else Results.Add(new Result("BestSolution", Context.BestSolution));
Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
Context.Iterations++;
if (cancellationToken.IsCancellationRequested) break;
}
}
private bool IsSufficientlyDifferent(IntegerVector vec) {
return Context.Population.All(x =>
HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
);
}
private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
// Following code represents line 1 of Algorithm 4
IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
if (targetFit < sourceFit) {
var h = source;
source = target;
target = h;
var hh = sourceEval;
sourceEval = targetEval;
targetEval = hh;
}
int evaluatedSolutions;
// lines 2-36 of Algorithm 4 are implemented in the following call
var pi_star = GQAPPathRelinking.Apply(Context.Random, source, sourceEval,
target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
out evaluatedSolutions);
Context.EvaluatedSolutions += evaluatedSolutions;
return pi_star;
}
private void ApproxLocalSearch(GQAPSolution pi_prime) {
var localSearchEvaluations = 0;
ApproximateLocalSearch.Apply(Context.Random, pi_prime, MaximumCandidateListSize,
OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
Context.EvaluatedSolutions += localSearchEvaluations;
}
}
}