#region License Information
/* HeuristicLab
* Copyright (C) 2002-2018 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.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;
namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
///
/// 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("GQAPPathRelinking", "Operator that performs path relinking between two solutions. It is 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.")]
[StorableClass]
public class GQAPPathRelinking : GQAPCrossover, IQualitiesAwareGQAPOperator {
public IScopeTreeLookupParameter QualityParameter {
get { return (IScopeTreeLookupParameter)Parameters["Quality"]; }
}
public IScopeTreeLookupParameter EvaluationParameter {
get { return (IScopeTreeLookupParameter)Parameters["Evaluation"]; }
}
public IValueParameter CandidateSizeFactorParameter {
get { return (IValueParameter)Parameters["CandidateSizeFactor"]; }
}
public IValueLookupParameter GreedyParameter {
get { return (IValueLookupParameter)Parameters["Greedy"]; }
}
[StorableConstructor]
protected GQAPPathRelinking(bool deserializing) : base(deserializing) { }
protected GQAPPathRelinking(GQAPPathRelinking original, Cloner cloner) : base(original, cloner) { }
public GQAPPathRelinking()
: base() {
Parameters.Add(new ScopeTreeLookupParameter("Quality", ""));
Parameters.Add(new ScopeTreeLookupParameter("Evaluation", GQAP.EvaluationDescription));
Parameters.Add(new ValueParameter("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(new ValueLookupParameter("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GQAPPathRelinking(this, cloner);
}
public static GQAPSolution Apply(IRandom random,
IntegerVector source, Evaluation sourceEval,
IntegerVector target, Evaluation targetEval,
GQAPInstance problemInstance, double candidateSizeFactor,
out int evaluatedSolutions, bool greedy = true) {
evaluatedSolutions = 0;
var demands = problemInstance.Demands;
var capacities = problemInstance.Capacities;
var cmp = new IntegerVectorEqualityComparer();
var sFit = problemInstance.ToSingleObjective(sourceEval);
var tFit = problemInstance.ToSingleObjective(targetEval);
GQAPSolution pi_star = sFit < tFit
? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone())
: new GQAPSolution((IntegerVector)target.Clone(), (Evaluation)targetEval.Clone()); // line 1 of Algorithm 4
double pi_star_Fit = problemInstance.ToSingleObjective(pi_star.Evaluation); // line 2 of Algorithm 4
var pi_prime = (IntegerVector)source.Clone(); // line 3 of Algorithm 4
//var fix = new bool[demands.Length]; // line 3 of Algorithm 4, note that according to the description it is not necessary to track the fixed equipments
var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
var phi = new List(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
var B = new List((int)Math.Ceiling(phi.Count * candidateSizeFactor));
var B_fit = new List(B.Capacity);
while (phi.Count > 0) { // line 5 of Algorithm 4
B.Clear(); // line 6 of Algorithm 4
B_fit.Clear(); // line 6 of Algorithm 4 (B is split into two synchronized lists)
foreach (var v in phi) { // line 7 of Algorithm 4
int oldLocation = pi_prime[v];
pi_prime[v] = target[v]; // line 8 of Algorithm 4
var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
var pi_dash_eval = problemInstance.Evaluate(pi_dash);
evaluatedSolutions++;
var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
if (B.Any(x => cmp.Equals(x.Assignment, pi_dash))) continue; // cond. 2 of line 12 and cond. 1 of line 16 in Algorithm 4
if (B.Count >= candidateSizeFactor * phi.Count) { // line 11 of Algorithm 4
var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
.Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
.Select(x => new { x.Index, x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
.ToArray();
if (replacement.Length > 0) {
var mostSimilar = replacement.MaxItems(x => x.Similarity).SampleRandom(random).Index;
B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
B_fit[mostSimilar] = pi_dash_fit; // line 13 of Algorithm 4
}
} else { // line 16, condition has been checked above already
B.Add(new GQAPSolution(pi_dash, pi_dash_eval)); // line 17 of Algorithm 4
B_fit.Add(pi_dash_fit); // line 17 of Algorithm 4
}
}
}
if (B.Count > 0) { // line 21 of Algorithm 4
GQAPSolution pi;
// line 22 of Algorithm 4
if (greedy) {
pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).SampleRandom(random).Value;
} else {
pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
}
var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4
var I = phi.Except(diff); // line 24 of Algorithm 4
var i = I.SampleRandom(random); // line 25 of Algorithm 4
//fix[i] = true; // line 26 of Algorithm 4
nonFix.Remove(i); // line 26 of Algorithm 4
pi_prime = pi.Assignment; // line 27 of Algorithm 4
var fit = problemInstance.ToSingleObjective(pi.Evaluation);
if (fit < pi_star_Fit) { // line 28 of Algorithm 4
pi_star_Fit = fit; // line 29 of Algorithm 4
pi_star = pi; // line 30 of Algorithm 4
}
} else return pi_star;
phi = new List(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
}
return pi_star;
}
protected override IntegerVector Cross(IRandom random, ItemArray parents,
GQAPInstance problemInstance) {
var qualities = QualityParameter.ActualValue;
var evaluations = EvaluationParameter.ActualValue;
var betterParent = qualities[0].Value <= qualities[1].Value ? 0 : 1;
var worseParent = 1 - betterParent;
var source = parents[betterParent];
var target = parents[worseParent];
int evaluatedSolution;
return Apply(random, source, evaluations[betterParent],
target, evaluations[worseParent], problemInstance,
CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,
GreedyParameter.ActualValue.Value).Assignment;
}
///
/// Relocates equipments in the same location as to other locations in case the location
/// is overutilized.
///
///
/// This method is performance critical, called very often and should run as fast as possible.
///
/// The random number generator.
/// The current solution.
/// The equipment that was just assigned to a new location.
/// The equipments that have not yet been fixed.
/// The demands for all equipments.
/// The capacities of all locations.
/// The number of tries that should be done in relocating the equipments.
/// A feasible or infeasible solution
private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
int l = pi[equipment];
var slack = ComputeSlack(pi, demands, capacities);
if (slack[l] >= 0) // line 1 of Algorithm 5
return (IntegerVector)pi.Clone(); // line 2 of Algorithm 5
IntegerVector pi_prime = null;
int k = 0; // line 4 of Algorithm 5
var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
var slack_prime = (double[])slack.Clone();
var maxSlack_prime = maxSlack;
// note that FTL can be computed only once for all tries as all tries restart with the same solution
var FTL = nonFix.Where(x => x != equipment && pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
var FTLweight = FTL.Select(x => demands[x]).ToList();
while (k < maximumTries && slack_prime[l] < 0) { // line 5 of Algorithm 5
pi_prime = (IntegerVector)pi.Clone(); // line 6 of Algorithm 5
// set T can only shrink and not grow, thus it is created outside the loop and only updated inside
var T = new List(FTL); // line 8-9 of Algorithm 5
var weightT = new List(FTLweight);
do { // line 7 of Algorithm 5
if (T.Count > 0) { // line 10 of Algorithm 5
var idx = Enumerable.Range(0, T.Count).SampleProportional(random, 1, weightT, false, false).First(); // line 11 of Algorithm 5
int i = T[idx]; // line 11 of Algorithm 5
var j = Enumerable.Range(0, capacities.Length)
.Where(x => slack_prime[x] >= demands[i]) // line 12 of Algorithm 5
.SampleRandom(random); // line 13 of Algorithm 5
pi_prime[i] = j; // line 14 of Algorithm 5
T.RemoveAt(idx);
weightT.RemoveAt(idx);
var recomputeMaxSlack = slack_prime[j] == maxSlack_prime; // efficiency improvement: recompute max slack only if we assign to a location whose slack equals maxSlack
slack_prime[j] -= demands[i]; // line 14 of Algorithm 5
slack_prime[l] += demands[i]; // line 14 of Algorithm 5
if (recomputeMaxSlack) {
maxSlack_prime = slack_prime.Max();
// T needs to be removed of equipments whose demand is higher than maxSlack only if maxSlack changes
for (var h = 0; h < T.Count; h++) {
var f = T[h];
if (demands[f] > maxSlack_prime) {
T.RemoveAt(h);
weightT.RemoveAt(h);
h--;
}
}
}
} else break; // cond. 1 in line 16 of Algorithm 5
} while (slack_prime[l] < 0); // cond. 2 in line 16 of Algorithm 5
k++; // line 17 of Algorithm 5
if (slack_prime[l] < 0) {
// reset
Array.Copy(slack, slack_prime, slack.Length);
maxSlack_prime = maxSlack;
}
}
return pi_prime; // line 19-23 of Algorithm 5
}
private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
var slack = capacities.ToArray();
for (int i = 0; i < assignment.Length; i++) {
slack[assignment[i]] -= demands[i];
}
return slack;
}
}
}