Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/24/12 17:16:49 (12 years ago)
Author:
abeham
Message:

#1904: Added fast evaluation option to exhaustive swap2 local improvement operator

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs

    r8338 r8846  
    8181    public ILookupParameter<DoubleMatrix> DistancesParameter {
    8282      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
     83    }
     84
     85    public IValueLookupParameter<BoolValue> UseFastEvaluationParameter {
     86      get { return (IValueLookupParameter<BoolValue>)Parameters["UseFastEvaluation"]; }
    8387    }
    8488
     
    100104      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
    101105      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
     106      Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(true)));
    102107    }
    103108
     
    112117      if (!Parameters.ContainsKey("LocalIterations"))
    113118        Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
     119      if (!Parameters.ContainsKey("UseFastEvaluation"))
     120        Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(false)));
    114121    }
    115122    #endregion
     
    140147    }
    141148
     149    public static void ImproveFast(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
     150      Swap2Move bestMove = null;
     151      double evaluations = 0.0;
     152      var lastQuality = new double[assignment.Length, assignment.Length];
     153      for (int i = localIterations.Value; i < maxIterations; i++) {
     154        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
     155        var lastMove = bestMove;
     156        bestMove = null;
     157        foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
     158          double moveQuality;
     159          if (lastMove == null) {
     160            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
     161            evaluations += 4.0 / assignment.Length;
     162          } else {
     163            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, lastQuality[move.Index1, move.Index2], weights, distances, lastMove);
     164            if (move.Index1 == lastMove.Index1 || move.Index2 == lastMove.Index1 || move.Index1 == lastMove.Index2 || move.Index2 == lastMove.Index2)
     165              evaluations += 4.0 / assignment.Length;
     166            else evaluations += 2.0 / (assignment.Length * assignment.Length);
     167          }
     168          lastQuality[move.Index1, move.Index2] = moveQuality;
     169          if (maximization && moveQuality > bestQuality
     170            || !maximization && moveQuality < bestQuality) {
     171            bestQuality = moveQuality;
     172            bestMove = move;
     173          }
     174        }
     175        if (bestMove == null) break;
     176        Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
     177        quality.Value += bestQuality;
     178        localIterations.Value++;
     179        if (cancellation.IsCancellationRequested) {
     180          evaluatedSolutions.Value += (int)Math.Round(evaluations);
     181          throw new OperationCanceledException();
     182        }
     183      }
     184      evaluatedSolutions.Value += (int)Math.Round(evaluations);
     185    }
     186
    142187    public override IOperation Apply() {
    143188      var maxIterations = MaximumIterationsParameter.ActualValue.Value;
     
    154199      }
    155200
    156       Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
     201      if (UseFastEvaluationParameter.ActualValue.Value)
     202        ImproveFast(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
     203      else Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
     204
    157205      return base.Apply();
    158206    }
Note: See TracChangeset for help on using the changeset viewer.