#region License Information /* HeuristicLab * Copyright (C) 2002-2015 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 HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.PermutationEncoding; using HeuristicLab.Operators; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms { [Item("RobustTabooSearchOperator", "Performs an iteration of the robust taboo search algorithm as descrbied in Taillard 1991.")] [StorableClass] public sealed class RobustTabooSeachOperator : SingleSuccessorOperator, IIterationBasedOperator, IStochasticOperator, ISingleObjectiveOperator { #region Parameter Properties public ILookupParameter IterationsParameter { get { return (ILookupParameter)Parameters["Iterations"]; } } public ILookupParameter RandomParameter { get { return (ILookupParameter)Parameters["Random"]; } } public ILookupParameter PermutationParameter { get { return (ILookupParameter)Parameters["Permutation"]; } } public ILookupParameter WeightsParameter { get { return (ILookupParameter)Parameters["Weights"]; } } public ILookupParameter DistancesParameter { get { return (ILookupParameter)Parameters["Distances"]; } } public ILookupParameter ShortTermMemoryParameter { get { return (ILookupParameter)Parameters["ShortTermMemory"]; } } public ILookupParameter MoveQualityMatrixParameter { get { return (ILookupParameter)Parameters["MoveQualityMatrix"]; } } public ILookupParameter QualityParameter { get { return (ILookupParameter)Parameters["Quality"]; } } public ILookupParameter BestQualityParameter { get { return (ILookupParameter)Parameters["BestQuality"]; } } public ILookupParameter LastMoveParameter { get { return (ILookupParameter)Parameters["LastMove"]; } } public ILookupParameter UseNewTabuTenureAdaptionSchemeParameter { get { return (ILookupParameter)Parameters["UseNewTabuTenureAdaptionScheme"]; } } public ILookupParameter ResultsParameter { get { return (ILookupParameter)Parameters["Results"]; } } public IValueLookupParameter MaximumIterationsParameter { get { return (IValueLookupParameter)Parameters["MaximumIterations"]; } } public IValueLookupParameter MinimumTabuTenureParameter { get { return (IValueLookupParameter)Parameters["MinimumTabuTenure"]; } } public IValueLookupParameter MaximumTabuTenureParameter { get { return (IValueLookupParameter)Parameters["MaximumTabuTenure"]; } } public IValueLookupParameter UseAlternativeAspirationParameter { get { return (IValueLookupParameter)Parameters["UseAlternativeAspiration"]; } } public IValueLookupParameter AlternativeAspirationTenureParameter { get { return (IValueLookupParameter)Parameters["AlternativeAspirationTenure"]; } } private ILookupParameter AllMovesTabuParameter { get { return (ILookupParameter)Parameters["AllMovesTabu"]; } } public ILookupParameter EvaluatedSolutionsParameter { get { return (ILookupParameter)Parameters["EvaluatedSolutions"]; } } public ILookupParameter EvaluatedSolutionEquivalentsParameter { get { return (ILookupParameter)Parameters["EvaluatedSolutionEquivalents"]; } } #endregion [StorableConstructor] private RobustTabooSeachOperator(bool deserializing) : base(deserializing) { } private RobustTabooSeachOperator(RobustTabooSeachOperator original, Cloner cloner) : base(original, cloner) { } public RobustTabooSeachOperator() { Parameters.Add(new LookupParameter("Iterations", "The current iteration.")); Parameters.Add(new LookupParameter("Random", "The random number generator to use.")); Parameters.Add(new LookupParameter("Permutation", "The permutation solution.")); Parameters.Add(new LookupParameter("Weights", "The weights matrix.")); Parameters.Add(new LookupParameter("Distances", "The distances matrix.")); Parameters.Add(new LookupParameter("ShortTermMemory", "The table that stores the iteration at which a certain facility has been assigned to a certain location.")); Parameters.Add(new LookupParameter("MoveQualityMatrix", "The quality of all swap moves as evaluated on the current permutation.")); Parameters.Add(new LookupParameter("Quality", "The quality value.")); Parameters.Add(new LookupParameter("BestQuality", "The best quality value.")); Parameters.Add(new LookupParameter("LastMove", "The last move that was applied.")); Parameters.Add(new LookupParameter("UseNewTabuTenureAdaptionScheme", "True if the new tabu tenure adaption should be used or false otherwise.")); Parameters.Add(new LookupParameter("Results", "Collection that houses the results of the algorithm.")); Parameters.Add(new ValueLookupParameter("MaximumIterations", "The number of iterations that the algorithm should run.")); Parameters.Add(new ValueLookupParameter("MinimumTabuTenure", "The minimum tabu tenure.")); Parameters.Add(new ValueLookupParameter("MaximumTabuTenure", "The maximum tabu tenure.")); Parameters.Add(new ValueLookupParameter("UseAlternativeAspiration", "True if the alternative aspiration condition should be used that takes moves that have not been made for some time above others.")); Parameters.Add(new ValueLookupParameter("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition.")); Parameters.Add(new LookupParameter("AllMovesTabu", "Indicates that all moves are tabu.")); Parameters.Add(new LookupParameter("EvaluatedSolutions", "The number of evaluated solutions.")); Parameters.Add(new LookupParameter("EvaluatedSolutionEquivalents", "The number of evaluated solution equivalents.")); } public override IDeepCloneable Clone(Cloner cloner) { return new RobustTabooSeachOperator(this, cloner); } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { // BackwardsCompatibility3.3 #region Backwards compatible code, remove with 3.4 if (!Parameters.ContainsKey("AllMovesTabu")) { Parameters.Add(new LookupParameter("AllMovesTabu", "Indicates that all moves are tabu.")); } if (!Parameters.ContainsKey("EvaluatedSolutions")) { Parameters.Add(new LookupParameter("EvaluatedSolutions", "The number of evaluated solutions.")); } if (!Parameters.ContainsKey("EvaluatedSolutionEquivalents")) { Parameters.Add(new LookupParameter("EvaluatedSolutionEquivalents", "The number of evaluated solution equivalents.")); } #endregion } public override IOperation Apply() { IRandom random = RandomParameter.ActualValue; int iteration = IterationsParameter.ActualValue.Value; IntMatrix shortTermMemory = ShortTermMemoryParameter.ActualValue; DoubleMatrix weights = WeightsParameter.ActualValue; DoubleMatrix distances = DistancesParameter.ActualValue; DoubleMatrix moveQualityMatrix = MoveQualityMatrixParameter.ActualValue; DoubleValue quality = QualityParameter.ActualValue; DoubleValue bestQuality = BestQualityParameter.ActualValue; if (bestQuality == null) { BestQualityParameter.ActualValue = (DoubleValue)quality.Clone(); bestQuality = BestQualityParameter.ActualValue; } bool allMovesTabu = false; if (AllMovesTabuParameter.ActualValue == null) AllMovesTabuParameter.ActualValue = new BoolValue(false); else allMovesTabu = AllMovesTabuParameter.ActualValue.Value; int minTenure = MinimumTabuTenureParameter.ActualValue.Value; int maxTenure = MaximumTabuTenureParameter.ActualValue.Value; int alternativeAspirationTenure = AlternativeAspirationTenureParameter.ActualValue.Value; bool useAlternativeAspiration = UseAlternativeAspirationParameter.ActualValue.Value; Permutation solution = PermutationParameter.ActualValue; Swap2Move lastMove = LastMoveParameter.ActualValue; double bestMoveQuality = double.MaxValue; Swap2Move bestMove = null; bool already_aspired = false; double evaluations = EvaluatedSolutionsParameter.ActualValue.Value; foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(solution)) { double moveQuality; if (lastMove == null) { moveQuality = QAPSwap2MoveEvaluator.Apply(solution, move, weights, distances); evaluations += 4.0 / solution.Length; } else if (allMovesTabu) moveQuality = moveQualityMatrix[move.Index1, move.Index2]; else { moveQuality = QAPSwap2MoveEvaluator.Apply(solution, move, moveQualityMatrix[move.Index1, move.Index2], weights, distances, lastMove); if (move.Index1 == lastMove.Index1 || move.Index2 == lastMove.Index1 || move.Index1 == lastMove.Index2 || move.Index2 == lastMove.Index2) evaluations += 4.0 / solution.Length; else evaluations += 2.0 / (solution.Length * solution.Length); } moveQualityMatrix[move.Index1, move.Index2] = moveQuality; moveQualityMatrix[move.Index2, move.Index1] = moveQuality; bool autorized = shortTermMemory[move.Index1, solution[move.Index2]] < iteration || shortTermMemory[move.Index2, solution[move.Index1]] < iteration; bool aspired = (shortTermMemory[move.Index1, solution[move.Index2]] < iteration - alternativeAspirationTenure && shortTermMemory[move.Index2, solution[move.Index1]] < iteration - alternativeAspirationTenure) || quality.Value + moveQuality < bestQuality.Value; if ((aspired && !already_aspired) // the first alternative move is aspired || (aspired && already_aspired && moveQuality < bestMoveQuality) // an alternative move was already aspired, but this is better || (autorized && !aspired && !already_aspired && moveQuality < bestMoveQuality)) { // a regular better move is found bestMove = move; bestMoveQuality = moveQuality; if (aspired) already_aspired = true; } } ResultCollection results = ResultsParameter.ActualValue; if (results != null) { IntValue aspiredMoves = null; if (!results.ContainsKey("AspiredMoves")) { aspiredMoves = new IntValue(already_aspired ? 1 : 0); results.Add(new Result("AspiredMoves", "Counts the number of moves that were selected because of the aspiration criteria.", aspiredMoves)); } else if (already_aspired) { aspiredMoves = (IntValue)results["AspiredMoves"].Value; aspiredMoves.Value++; } } EvaluatedSolutionEquivalentsParameter.ActualValue.Value = evaluations; EvaluatedSolutionsParameter.ActualValue.Value = (int)Math.Ceiling(evaluations); allMovesTabu = bestMove == null; if (!allMovesTabu) LastMoveParameter.ActualValue = bestMove; AllMovesTabuParameter.ActualValue.Value = allMovesTabu; if (allMovesTabu) return base.Apply(); bool useNewAdaptionScheme = UseNewTabuTenureAdaptionSchemeParameter.ActualValue.Value; if (useNewAdaptionScheme) { double r = random.NextDouble(); if (r == 0) r = 1; // transform to (0;1] shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = (int)(iteration + r * r * r * maxTenure); r = random.NextDouble(); if (r == 0) r = 1; // transform to (0;1] shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = (int)(iteration + r * r * r * maxTenure); } else { shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = iteration + random.Next(minTenure, maxTenure); shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = iteration + random.Next(minTenure, maxTenure); } Swap2Manipulator.Apply(solution, bestMove.Index1, bestMove.Index2); quality.Value += bestMoveQuality; if (quality.Value < bestQuality.Value) bestQuality.Value = quality.Value; return base.Apply(); } } }