#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 HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
[Item("ApproximateLocalSearch", "The approximate local search 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 ApproximateLocalSearch : SingleSuccessorOperator, IProblemInstanceAwareGQAPOperator,
IQualityAwareGQAPOperator, IGQAPLocalImprovementOperator, IAssignmentAwareGQAPOperator, IStochasticOperator {
public IProblem Problem { get; set; }
public Type ProblemType {
get { return typeof(GQAP); }
}
public ILookupParameter ProblemInstanceParameter {
get { return (ILookupParameter)Parameters["ProblemInstance"]; }
}
public ILookupParameter AssignmentParameter {
get { return (ILookupParameter)Parameters["Assignment"]; }
}
public ILookupParameter QualityParameter {
get { return (ILookupParameter)Parameters["Quality"]; }
}
public ILookupParameter EvaluationParameter {
get { return (ILookupParameter)Parameters["Evaluation"]; }
}
public IValueLookupParameter MaximumIterationsParameter {
get { return (IValueLookupParameter)Parameters["MaximumIterations"]; }
}
public ILookupParameter EvaluatedSolutionsParameter {
get { return (ILookupParameter)Parameters["EvaluatedSolutions"]; }
}
public ILookupParameter RandomParameter {
get { return (ILookupParameter)Parameters["Random"]; }
}
public IValueLookupParameter MaximumCandidateListSizeParameter {
get { return (IValueLookupParameter)Parameters["MaximumCandidateListSize"]; }
}
public IValueLookupParameter OneMoveProbabilityParameter {
get { return (IValueLookupParameter)Parameters["OneMoveProbability"]; }
}
public ILookupParameter ResultsParameter {
get { return (ILookupParameter)Parameters["Results"]; }
}
[StorableConstructor]
protected ApproximateLocalSearch(bool deserializing) : base(deserializing) { }
protected ApproximateLocalSearch(ApproximateLocalSearch original, Cloner cloner) : base(original, cloner) { }
public ApproximateLocalSearch()
: base() {
Parameters.Add(new LookupParameter("ProblemInstance", GQAP.ProblemInstanceDescription));
Parameters.Add(new LookupParameter("Assignment", GQAPSolutionCreator.AssignmentDescription));
Parameters.Add(new LookupParameter("Quality", ""));
Parameters.Add(new LookupParameter("Evaluation", GQAP.EvaluationDescription));
Parameters.Add(new ValueLookupParameter("MaximumIterations", "The maximum number of iterations that should be performed."));
Parameters.Add(new LookupParameter("EvaluatedSolutions", "The number of evaluated solution equivalents."));
Parameters.Add(new LookupParameter("Random", "The random number generator to use."));
Parameters.Add(new ValueLookupParameter("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
Parameters.Add(new ValueLookupParameter("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
Parameters.Add(new LookupParameter("Results", "The result collection that stores the results."));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new ApproximateLocalSearch(this, cloner);
}
public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
double oneMoveProbability, int maximumIterations,
GQAPInstance problemInstance, out int evaluatedSolutions) {
var fit = problemInstance.ToSingleObjective(sol.Evaluation);
var eval = sol.Evaluation;
Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
out evaluatedSolutions);
sol.Evaluation = eval;
}
///
/// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
/// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
/// the maxItr parameter defined by Mateus et al.
///
/// The random number generator to use.
/// The equipment-location assignment vector.
/// The solution quality.
/// The evaluation result of the solution.
/// The maximum number of candidates that should be found in each step.
/// The probability for performing a 1-move, which is the opposite of performing a 2-move.
/// The maximum number of iterations that should be performed each time the candidate list is generated.
/// The problem instance that contains the data.
/// The number of evaluated solutions.
public static void Apply(IRandom random, IntegerVector assignment,
ref double quality, ref Evaluation evaluation, int maxCLS,
double oneMoveProbability, int maximumIterations,
GQAPInstance problemInstance, out int evaluatedSolutions) {
evaluatedSolutions = 0;
var capacities = problemInstance.Capacities;
var demands = problemInstance.Demands;
var evaluations = 0.0;
var deltaEvaluationFactor = 1.0 / assignment.Length;
while (true) {
int count = 0;
var CLS = new List>();
double sum = 0.0;
do {
NMove move;
if (random.NextDouble() < oneMoveProbability)
move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(random, assignment, capacities);
else move = StochasticNMoveSingleMoveGenerator.GenerateTwoMove(random, assignment, capacities);
var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
evaluations += move.Indices.Count * deltaEvaluationFactor;
double moveQuality = problemInstance.ToSingleObjective(moveEval);
if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) {
CLS.Add(Tuple.Create(move, moveQuality, moveEval));
sum += 1.0 / moveQuality;
}
count++;
} while (CLS.Count < maxCLS && count < maximumIterations);
if (CLS.Count == 0) {
evaluatedSolutions += (int)Math.Ceiling(evaluations);
return; // END
} else {
var ball = random.NextDouble() * sum;
var selected = CLS.Last();
foreach (var candidate in CLS) {
ball -= 1.0 / candidate.Item2;
if (ball <= 0.0) {
selected = candidate;
break;
}
}
NMoveMaker.Apply(assignment, selected.Item1);
quality = selected.Item2;
evaluation = selected.Item3;
}
}
}
public override IOperation Apply() {
var evaluation = EvaluationParameter.ActualValue;
var quality = QualityParameter.ActualValue;
var fit = quality.Value;
var evaluatedSolutions = 0;
Apply(RandomParameter.ActualValue,
AssignmentParameter.ActualValue,
ref fit,
ref evaluation,
MaximumCandidateListSizeParameter.ActualValue.Value,
OneMoveProbabilityParameter.ActualValue.Value,
MaximumIterationsParameter.ActualValue.Value,
ProblemInstanceParameter.ActualValue,
out evaluatedSolutions);
EvaluationParameter.ActualValue = evaluation;
quality.Value = fit;
EvaluatedSolutionsParameter.ActualValue.Value += evaluatedSolutions;
return base.Apply();
}
}
}