#region License Information
/* HeuristicLab
* Copyright (C) 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.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HEAL.Attic;
namespace HeuristicLab.Problems.QuadraticAssignment {
[Item("QAPExhaustiveInversionLocalImprovement", "Takes a solution and finds the local optimum with respect to the inversion neighborhood by decending along the steepest gradient.")]
[StorableType("7A0F7835-87A6-4C3E-BEE2-E1BA6F67972B")]
public class QAPExhaustiveInversionLocalImprovement : SingleSuccessorOperator, ILocalImprovementOperator, ISingleObjectiveOperator {
public ILookupParameter LocalIterationsParameter {
get { return (ILookupParameter)Parameters["LocalIterations"]; }
}
public IValueLookupParameter MaximumIterationsParameter {
get { return (IValueLookupParameter)Parameters["MaximumIterations"]; }
}
public ILookupParameter EvaluatedSolutionsParameter {
get { return (ILookupParameter)Parameters["EvaluatedSolutions"]; }
}
public ILookupParameter ResultsParameter {
get { return (ILookupParameter)Parameters["Results"]; }
}
public ILookupParameter AssignmentParameter {
get { return (ILookupParameter)Parameters["Assignment"]; }
}
public ILookupParameter QualityParameter {
get { return (ILookupParameter)Parameters["Quality"]; }
}
public ILookupParameter MaximizationParameter {
get { return (ILookupParameter)Parameters["Maximization"]; }
}
public ILookupParameter WeightsParameter {
get { return (ILookupParameter)Parameters["Weights"]; }
}
public ILookupParameter DistancesParameter {
get { return (ILookupParameter)Parameters["Distances"]; }
}
[StorableConstructor]
protected QAPExhaustiveInversionLocalImprovement(StorableConstructorFlag _) : base(_) { }
protected QAPExhaustiveInversionLocalImprovement(QAPExhaustiveInversionLocalImprovement original, Cloner cloner)
: base(original, cloner) {
}
public QAPExhaustiveInversionLocalImprovement()
: base() {
Parameters.Add(new LookupParameter("LocalIterations", "The number of iterations that have already been performed."));
Parameters.Add(new ValueLookupParameter("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached).", new IntValue(10000)));
Parameters.Add(new LookupParameter("EvaluatedSolutions", "The amount of evaluated solutions (here a move is counted only as 4/n evaluated solutions with n being the length of the permutation)."));
Parameters.Add(new LookupParameter("Results", "The collection where to store results."));
Parameters.Add(new LookupParameter("Assignment", "The permutation that is to be locally optimized."));
Parameters.Add(new LookupParameter("Quality", "The quality value of the assignment."));
Parameters.Add(new LookupParameter("Maximization", "True if the problem should be maximized or minimized."));
Parameters.Add(new LookupParameter("Weights", "The weights matrix."));
Parameters.Add(new LookupParameter("Distances", "The distances matrix."));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new QAPExhaustiveInversionLocalImprovement(this, cloner);
}
public static void Improve(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
for (int i = localIterations.Value; i < maxIterations; i++) {
InversionMove bestMove = null;
double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
double evaluations = 0.0;
foreach (var move in ExhaustiveInversionMoveGenerator.Generate(assignment)) {
double moveQuality = QAPInversionMoveEvaluator.Apply(assignment, move, weights, distances);
evaluations += 2 * (move.Index2 - move.Index1 + 1) / (double)assignment.Length;
if (maximization && moveQuality > bestQuality
|| !maximization && moveQuality < bestQuality) {
bestQuality = moveQuality;
bestMove = move;
}
}
evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
if (bestMove == null) break;
InversionManipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
quality.Value += bestQuality;
localIterations.Value++;
cancellation.ThrowIfCancellationRequested();
}
}
public override IOperation Apply() {
var maxIterations = MaximumIterationsParameter.ActualValue.Value;
var assignment = AssignmentParameter.ActualValue;
var maximization = MaximizationParameter.ActualValue.Value;
var weights = WeightsParameter.ActualValue;
var distances = DistancesParameter.ActualValue;
var quality = QualityParameter.ActualValue;
var localIterations = LocalIterationsParameter.ActualValue;
var evaluations = EvaluatedSolutionsParameter.ActualValue;
if (localIterations == null) {
localIterations = new IntValue(0);
LocalIterationsParameter.ActualValue = localIterations;
}
Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
localIterations.Value = 0;
return base.Apply();
}
}
}