#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.Collections.Generic;
using System.Linq;
using System.Threading;
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 {
[Item("GreedyRandomizedSolutionCreator", "Creates a solution according to the procedure 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 GreedyRandomizedSolutionCreator : GQAPStochasticSolutionCreator {
public IValueLookupParameter MaximumTriesParameter {
get { return (IValueLookupParameter)Parameters["MaximumTries"]; }
}
public IValueLookupParameter CreateMostFeasibleSolutionParameter {
get { return (IValueLookupParameter)Parameters["CreateMostFeasibleSolution"]; }
}
[StorableConstructor]
protected GreedyRandomizedSolutionCreator(bool deserializing) : base(deserializing) { }
protected GreedyRandomizedSolutionCreator(GreedyRandomizedSolutionCreator original, Cloner cloner)
: base(original, cloner) { }
public GreedyRandomizedSolutionCreator()
: base() {
Parameters.Add(new ValueLookupParameter("MaximumTries", "The maximum number of tries to create a feasible solution after which an exception is thrown. If it is set to 0 or a negative value there will be an infinite number of attempts.", new IntValue(100000)));
Parameters.Add(new ValueLookupParameter("CreateMostFeasibleSolution", "If this is set to true the operator will always succeed, and outputs the solution with the least violation instead of throwing an exception.", new BoolValue(false)));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GreedyRandomizedSolutionCreator(this, cloner);
}
public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance,
int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) {
var demands = problemInstance.Demands;
var capacities = problemInstance.Capacities.ToArray();
var equipments = demands.Length;
var locations = capacities.Length;
int tries = 0;
var assignment = new int[equipments];
var slack = new double[locations];
double minViolation = double.MaxValue;
int[] bestAssignment = null;
var CF = new bool[equipments]; // set of chosen facilities / equipments
var T = new List(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)
var CL_list = new List(locations); // list of chosen locations
var CL_selected = new bool[locations]; // bool decision if location is chosen
var F = new List(equipments); // set of (initially) all facilities / equipments
var L = new List(locations); // set of (initially) all locations
while (maximumTries <= 0 || tries < maximumTries) {
cancelToken.ThrowIfCancellationRequested();
Array.Copy(capacities, slack, locations);
Array.Clear(CF, 0, equipments);
Array.Clear(CL_selected, 0, locations);
CL_list.Clear();
T.Clear();
F.Clear(); F.AddRange(Enumerable.Range(0, equipments));
L.Clear(); L.AddRange(Enumerable.Range(0, locations));
double threshold = 1.0;
do {
if (L.Count > 0 && random.NextDouble() < threshold) {
int l = L.SampleRandom(random);
L.Remove(l);
CL_list.Add(l);
CL_selected[l] = true;
T = new List(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands));
}
if (T.Count > 0) {
var fidx = Enumerable.Range(0, T.Count).SampleRandom(random);
var f = T[fidx];
T.RemoveAt(fidx);
F.Remove(f); // TODO: slow
CF[f] = true;
int l = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).SampleRandom(random);
assignment[f] = l + 1;
slack[l] -= demands[f];
T = new List(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands));
threshold = 1.0 - (double)T.Count / Math.Max(F.Count, 1.0);
}
} while (T.Count > 0 || L.Count > 0);
if (maximumTries > 0) tries++;
if (F.Count == 0) {
bestAssignment = assignment;
break;
} else if (createMostFeasibleSolution) {
// complete the solution and remember the one with least violation
foreach (var l in L.ToArray()) {
CL_list.Add(l);
CL_selected[l] = true;
L.Remove(l);
}
while (F.Count > 0) {
var f = F.Select((v, i) => new { Index = i, Value = v }).MaxItems(x => demands[x.Value]).SampleRandom(random);
var l = CL_list.MaxItems(x => slack[x]).SampleRandom(random);
F.RemoveAt(f.Index);
assignment[f.Value] = l + 1;
slack[l] -= demands[f.Value];
}
double violation = slack.Select(x => x < 0 ? -x : 0).Sum();
if (violation < minViolation) {
bestAssignment = assignment;
assignment = new int[equipments];
minViolation = violation;
}
}
}
if (bestAssignment == null || bestAssignment.Any(x => x == 0))
throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));
return new IntegerVector(bestAssignment.Select(x => x - 1).ToArray());
}
protected override IntegerVector CreateRandomSolution(IRandom random, GQAPInstance problemInstance) {
return CreateSolution(random, problemInstance,
MaximumTriesParameter.ActualValue.Value,
CreateMostFeasibleSolutionParameter.ActualValue.Value,
CancellationToken);
}
private static IEnumerable WhereDemandEqualOrLess(IEnumerable facilities, double maximum, DoubleArray demands) {
foreach (int f in facilities) {
if (demands[f] <= maximum) yield return f;
}
}
private static double GetMaximumSlack(double[] slack, bool[] CL) {
var max = double.MinValue;
for (var i = 0; i < slack.Length; i++) {
if (CL[i] && max < slack[i]) max = slack[i];
}
return max;
}
private static IEnumerable WhereSlackGreaterOrEqual(IEnumerable locations, double minimum, double[] slack) {
foreach (int l in locations) {
if (slack[l] >= minimum) yield return l;
}
}
}
}