Changeset 8338


Ignore:
Timestamp:
07/27/12 01:22:49 (9 years ago)
Author:
abeham
Message:

#1904: Added additional local improvement operators

Location:
trunk/sources
Files:
3 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/ExhaustiveInsertionMoveGenerator.cs

    r7259 r8338  
    2121
    2222using System;
     23using System.Collections.Generic;
     24using System.Linq;
    2325using HeuristicLab.Common;
    2426using HeuristicLab.Core;
     
    3941    }
    4042
    41     public static TranslocationMove[] Apply(Permutation permutation) {
     43    public static IEnumerable<TranslocationMove> Generate(Permutation permutation) {
    4244      int length = permutation.Length;
    4345      if (length == 1) throw new ArgumentException("ExhaustiveInsertionMoveGenerator: There cannot be an insertion move given a permutation of length 1.", "permutation");
    44       TranslocationMove[] moves = null;
    45       int count = 0;
     46
    4647      if (permutation.PermutationType == PermutationTypes.Absolute) {
    47         moves = new TranslocationMove[length * (length - 1)];
    4848        for (int i = 0; i < length; i++) {
    4949          for (int j = 1; j <= length - 1; j++) {
    50             moves[count++] = new TranslocationMove(i, i, (i + j) % length);
     50            yield return new TranslocationMove(i, i, (i + j) % length);
    5151          }
    5252        }
    5353      } else {
    5454        if (length > 2) {
    55           moves = new TranslocationMove[length * (length - 1) - 2];
    5655          for (int i = 0; i < length; i++) {
    5756            for (int j = 1; j <= length - 1; j++) {
    5857              if (i == 0 && j == length - 1
    5958                || i == length - 1 && j == 1) continue;
    60               moves[count++] = new TranslocationMove(i, i, (i + j) % length);
     59              yield return new TranslocationMove(i, i, (i + j) % length);
    6160            }
    6261          }
    6362        } else { // doesn't make sense, but just create a dummy move to not crash the algorithms
    64           moves = new TranslocationMove[1];
    65           moves[0] = new TranslocationMove(0, 0, 1);
     63          yield return new TranslocationMove(0, 0, 1);
    6664        }
    6765      }
    68       System.Diagnostics.Debug.Assert(count == moves.Length);
    69       return moves;
     66    }
     67
     68    public static TranslocationMove[] Apply(Permutation permutation) {
     69      return Generate(permutation).ToArray();
    7070    }
    7171
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/ExhaustiveInversionMoveGenerator.cs

    r7259 r8338  
    2121
    2222using System;
     23using System.Collections.Generic;
     24using System.Linq;
    2325using HeuristicLab.Common;
    2426using HeuristicLab.Core;
     
    4042
    4143    public static InversionMove[] Apply(Permutation permutation) {
     44      return Generate(permutation).ToArray();
     45    }
     46
     47    public static IEnumerable<InversionMove> Generate(Permutation permutation) {
    4248      int length = permutation.Length;
    4349      if (length == 1) throw new ArgumentException("ExhaustiveInversionMoveGenerator: There cannot be an inversion move given a permutation of length 1.", "permutation");
    4450      int totalMoves = (length) * (length - 1) / 2;
    45       InversionMove[] moves = null;
    46       int count = 0;
    4751
    4852      if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
    4953        if (totalMoves - 3 > 0) {
    50           moves = new InversionMove[totalMoves - 3];
    5154          for (int i = 0; i < length - 1; i++) {
    5255            for (int j = i + 1; j < length; j++) {
    5356              // doesn't make sense to inverse the whole permutation or the whole but one in case of relative undirected permutations
    5457              if (j - i >= length - 2) continue;
    55               moves[count++] = new InversionMove(i, j);
     58              yield return new InversionMove(i, j);
    5659            }
    5760          }
    5861        } else { // when length is 3 or less, there's actually no difference, but for the sake of not crashing the algorithm create a dummy move
    59           moves = new InversionMove[1];
    60           moves[0] = new InversionMove(0, 1);
     62          yield return new InversionMove(0, 1);
    6163        }
    6264      } else {
    63         moves = new InversionMove[totalMoves];
    6465        for (int i = 0; i < length - 1; i++)
    6566          for (int j = i + 1; j < length; j++) {
    66             moves[count++] = new InversionMove(i, j);
     67            yield return new InversionMove(i, j);
    6768          }
    6869      }
    69       return moves;
    7070    }
    7171
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

    r7877 r8338  
    125125    <Compile Include="Interfaces\IQAPEvaluator.cs" />
    126126    <Compile Include="Interfaces\IQAPMoveEvaluator.cs" />
     127    <Compile Include="LocalImprovement\QAPExhaustiveInsertionLocalImprovement.cs" />
     128    <Compile Include="LocalImprovement\QAPStochasticScrambleLocalImprovement.cs" />
    127129    <Compile Include="LocalImprovement\QAPExhaustiveSwap2LocalImprovement.cs" />
     130    <Compile Include="LocalImprovement\QAPExhaustiveInversionLocalImprovement.cs" />
    128131    <Compile Include="QAPAssignment.cs" />
    129132    <Compile Include="QAPPermutationProximityCalculator.cs" />
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs

    r7878 r8338  
    2121
    2222using System;
     23using System.Threading;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
     
    4445      get { return problem; }
    4546      set { problem = (QuadraticAssignmentProblem)value; }
     47    }
     48
     49    public ILookupParameter<IntValue> LocalIterationsParameter {
     50      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
    4651    }
    4752
     
    8691    public QAPExhaustiveSwap2LocalImprovement()
    8792      : base() {
    88       Parameters.Add(new ValueLookupParameter<IntValue>("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)));
     93      Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
     94      Parameters.Add(new ValueLookupParameter<IntValue>("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)));
    8995      Parameters.Add(new LookupParameter<IntValue>("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)."));
    9096      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection where to store results."));
     
    100106    }
    101107
    102     public static double Improve(Permutation assignment, double quality, DoubleMatrix weights, DoubleMatrix distances, bool maximization, int maxIterations, out double evaluatedSolutions) {
    103       evaluatedSolutions = 0.0;
     108    // BackwardsCompatibility3.3
     109    #region Backwards compatible code, remove with 3.4
     110    [StorableHook(HookType.AfterDeserialization)]
     111    private void AfterDeserialization() {
     112      if (!Parameters.ContainsKey("LocalIterations"))
     113        Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
     114    }
     115    #endregion
     116
     117    public static void Improve(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
    104118      double evalSolPerMove = 4.0 / assignment.Length;
    105119
    106       for (int i = 0; i < maxIterations; i++) {
     120      for (int i = localIterations.Value; i < maxIterations; i++) {
    107121        Swap2Move bestMove = null;
    108122        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
     123        double evaluations = 0.0;
    109124        foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
    110125          double moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
    111           evaluatedSolutions += evalSolPerMove;
     126          evaluations += evalSolPerMove;
    112127          if (maximization && moveQuality > bestQuality
    113128            || !maximization && moveQuality < bestQuality) {
     
    116131          }
    117132        }
     133        evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
    118134        if (bestMove == null) break;
    119135        Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
    120         quality += bestQuality;
     136        quality.Value += bestQuality;
     137        localIterations.Value++;
     138        cancellation.ThrowIfCancellationRequested();
    121139      }
    122       return quality;
    123140    }
    124141
    125142    public override IOperation Apply() {
    126       int maxIterations = MaximumIterationsParameter.ActualValue.Value;
    127       Permutation assignment = AssignmentParameter.ActualValue;
    128       bool maximization = MaximizationParameter.ActualValue.Value;
    129       DoubleMatrix weights = WeightsParameter.ActualValue;
    130       DoubleMatrix distances = DistancesParameter.ActualValue;
    131       double quality = QualityParameter.ActualValue.Value;
     143      var maxIterations = MaximumIterationsParameter.ActualValue.Value;
     144      var assignment = AssignmentParameter.ActualValue;
     145      var maximization = MaximizationParameter.ActualValue.Value;
     146      var weights = WeightsParameter.ActualValue;
     147      var distances = DistancesParameter.ActualValue;
     148      var quality = QualityParameter.ActualValue;
     149      var localIterations = LocalIterationsParameter.ActualValue;
     150      var evaluations = EvaluatedSolutionsParameter.ActualValue;
     151      if (localIterations == null) {
     152        localIterations = new IntValue(0);
     153        LocalIterationsParameter.ActualValue = localIterations;
     154      }
    132155
    133       double evaluations;
    134       QualityParameter.ActualValue.Value = Improve(assignment, quality, weights, distances, maximization, maxIterations, out evaluations);
    135       EvaluatedSolutionsParameter.ActualValue.Value += (int)Math.Ceiling(evaluations);
     156      Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
    136157      return base.Apply();
    137158    }
Note: See TracChangeset for help on using the changeset viewer.