Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/22/11 12:03:36 (13 years ago)
Author:
abeham
Message:

#1541

  • Updated code to reflect what Eric Taillard's code does at ​http://mistic.heig-vd.ch/taillard/codes.dir/tabou_qap.cpp which is however not quite what is described in the paper.
  • Updated the swap2 move evaluator to perform move evaluations in O(1) for several cases by memorizing the move quality of the previous iteration
  • Added a unit test to test the new faster evaluation
  • Changed the robust taboo search to use this faster evaluation
  • Renamed some operators (dropping the QAP pre- and postfix)
Location:
branches/QAPAlgorithms
Files:
1 added
1 deleted
4 edited

Legend:

Unmodified
Added
Removed

  • branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.QuadraticAssignment.Algorithms-3.3.csproj

    r6569 r6586  
    107107  </ItemGroup>
    108108  <ItemGroup>
    109     <Compile Include="QAPRobustTabooSeachOperator.cs" />
     109    <Compile Include="RobustTabooSeachOperator.cs" />
    110110    <Compile Include="RobustTabooSearch.cs" />
    111111    <None Include="Plugin.cs.frame" />

  • branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs

    r6351 r6586  
    2626using HeuristicLab.Core;
    2727using HeuristicLab.Data;
    28 using HeuristicLab.Encodings.PermutationEncoding;
    2928using HeuristicLab.Operators;
    3029using HeuristicLab.Optimization;
    … …  
    3534
    3635namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms {
    37   [Item("Robust Taboo Search (QAP)", "The algorithm is described in Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455.")]
     36  [Item("Robust Taboo Search", "The algorithm is described in Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455.")]
    3837  [Creatable("Algorithms")]
    3938  [StorableClass]
    40   public sealed class RobustTabooSearchQAP : HeuristicOptimizationEngineAlgorithm, IStorableContent {
     39  public sealed class RobustTabooSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent {
    4140    public string Filename { get; set; }
    4241
    … …  
    6968    private FixedValueParameter<IntValue> MaximumTabuTenureParameter {
    7069      get { return (FixedValueParameter<IntValue>)Parameters["MaximumTabuTenure"]; }
    71     }
    72     private FixedValueParameter<IntValue> TabuTenureAdaptionIntervalParameter {
    73       get { return (FixedValueParameter<IntValue>)Parameters["TabuTenureAdaptionInterval"]; }
    7470    }
    7571    private FixedValueParameter<BoolValue> UseAlternativeAspirationParameter {
    … …  
    10298      set { MaximumTabuTenureParameter.Value.Value = value; }
    10399    }
    104     public int TabuTenureAdaptionInterval {
    105       get { return TabuTenureAdaptionIntervalParameter.Value.Value; }
    106       set { TabuTenureAdaptionIntervalParameter.Value.Value = value; }
    107     }
    108100    public bool UseAlternativeAspiration {
    109101      get { return UseAlternativeAspirationParameter.Value.Value; }
    … …  
    119111    private SolutionsCreator solutionsCreator;
    120112    [Storable]
    121     private QAPRobustTabooSeachOperator mainOperator;
     113    private RobustTabooSeachOperator mainOperator;
    122114    [Storable]
    123115    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
    124116
    125117    [StorableConstructor]
    126     private RobustTabooSearchQAP(bool deserializing) : base(deserializing) { }
    127     private RobustTabooSearchQAP(RobustTabooSearchQAP original, Cloner cloner)
     118    private RobustTabooSearch(bool deserializing) : base(deserializing) { }
     119    private RobustTabooSearch(RobustTabooSearch original, Cloner cloner)
    128120      : base(original, cloner) {
    129121      solutionsCreator = cloner.Clone(original.solutionsCreator);
    130122      mainOperator = cloner.Clone(original.mainOperator);
    131123      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
    132     }
    133     public RobustTabooSearchQAP() {
     124      RegisterEventHandlers();
     125    }
     126    public RobustTabooSearch() {
    134127      Parameters.Add(new FixedValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", new MultiAnalyzer()));
    135128      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The seed value of the random number generator.", new IntValue(0)));
    … …  
    138131      Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(20)));
    139132      Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(10)));
    140       Parameters.Add(new FixedValueParameter<IntValue>("TabuTenureAdaptionInterval", "The amount of iterations that have to pass before the tabu tenure is adapted.", new IntValue(60)));
    141133      Parameters.Add(new FixedValueParameter<BoolValue>("UseAlternativeAspiration", "True if the alternative aspiration condition should be used that takes moves that have not been made for some time above others.", new BoolValue(false)));
    142134      Parameters.Add(new FixedValueParameter<IntValue>("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition.", new IntValue(10000)));
     135      Parameters.Add(new FixedValueParameter<BoolValue>("TerminateOnOptimalSolution", "True when the algorithm should stop if it reached a quality equal or smaller to the BestKnownQuality.", new BoolValue(true)));
    143136
    144137      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
    … …  
    153146      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
    154147
    155       OperatorGraph.InitialOperator = randomCreator;
    156 
    157148      VariableCreator variableCreator = new VariableCreator();
    158149      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
    159       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("TabuTenure", new IntValue(0)));
    160       randomCreator.Successor = variableCreator;
    161150
    162151      ResultsCollector resultsCollector = new ResultsCollector();
    163152      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The actual iteration."));
    164       resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("TabuTenure", "The actual tabu tenure."));
    165       variableCreator.Successor = resultsCollector;
    166153
    167154      solutionsCreator = new SolutionsCreator();
    168155      solutionsCreator.NumberOfSolutions = new IntValue(1);
    169       resultsCollector.Successor = solutionsCreator;
    170156
    171157      Placeholder analyzer = new Placeholder();
    172158      analyzer.Name = "(Analyzer)";
    173159      analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name;
    174       solutionsCreator.Successor = analyzer;
    175160
    176161      UniformSubScopesProcessor ussp = new UniformSubScopesProcessor();
    177       analyzer.Successor = ussp;
    178 
    179       mainOperator = new QAPRobustTabooSeachOperator();
     162
     163      mainOperator = new RobustTabooSeachOperator();
    180164      mainOperator.AlternativeAspirationTenureParameter.ActualName = AlternativeAspirationTenureParameter.Name;
    181165      mainOperator.BestQualityParameter.ActualName = "BestSoFarQuality";
    182166      mainOperator.IterationsParameter.ActualName = "Iterations";
    183       mainOperator.LongTermMemoryParameter.ActualName = "LongTermMemory";
     167      mainOperator.LastMoveParameter.ActualName = "LastMove";
    184168      mainOperator.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
    185169      mainOperator.MaximumTabuTenureParameter.ActualName = MaximumTabuTenureParameter.Name;
    186170      mainOperator.MinimumTabuTenureParameter.ActualName = MinimumTabuTenureParameter.Name;
     171      mainOperator.MoveQualityMatrixParameter.ActualName = "MoveQualityMatrix";
    187172      mainOperator.RandomParameter.ActualName = "Random";
     173      mainOperator.ResultsParameter.ActualName = "Results";
    188174      mainOperator.ShortTermMemoryParameter.ActualName = "ShortTermMemory";
    189       mainOperator.TabuTenureAdaptionIntervalParameter.ActualName = TabuTenureAdaptionIntervalParameter.Name;
    190       mainOperator.TabuTenureParameter.ActualName = "TabuTenure";
    191175      mainOperator.UseAlternativeAspirationParameter.ActualName = UseAlternativeAspirationParameter.Name;
    192       ussp.Operator = mainOperator;
     176
     177      ConditionalBranch qualityStopBranch = new ConditionalBranch();
     178      qualityStopBranch.Name = "Terminate on optimal quality?";
     179      qualityStopBranch.ConditionParameter.ActualName = "TerminateOnOptimalSolution";
     180
     181      Comparator qualityComparator = new Comparator();
     182      qualityComparator.Comparison = new Comparison(ComparisonType.Greater);
     183      qualityComparator.LeftSideParameter.ActualName = "BestQuality";
     184      qualityComparator.RightSideParameter.ActualName = "BestKnownQuality";
     185      qualityComparator.ResultParameter.ActualName = "ContinueByQuality";
     186
     187      ConditionalBranch continueByQualityBranch = new ConditionalBranch();
     188      continueByQualityBranch.ConditionParameter.ActualName = "ContinueByQuality";
    193189
    194190      IntCounter iterationsCounter = new IntCounter();
    195191      iterationsCounter.ValueParameter.ActualName = "Iterations";
    196192      iterationsCounter.Increment = new IntValue(1);
    197       ussp.Successor = iterationsCounter;
    198193
    199194      Comparator comparator = new Comparator();
    … …  
    203198      comparator.Comparison = new Comparison(ComparisonType.Less);
    204199      comparator.ResultParameter.ActualName = "ContinueByIteration";
     200
     201      ConditionalBranch continueByIterationBranch = new ConditionalBranch();
     202      continueByIterationBranch.ConditionParameter.ActualName = "ContinueByIteration";
     203
     204      OperatorGraph.InitialOperator = randomCreator;
     205      randomCreator.Successor = variableCreator;
     206      variableCreator.Successor = resultsCollector;
     207      resultsCollector.Successor = solutionsCreator;
     208      solutionsCreator.Successor = analyzer;
     209      analyzer.Successor = ussp;
     210      ussp.Operator = mainOperator;
     211      ussp.Successor = qualityStopBranch;
     212      qualityStopBranch.FalseBranch = iterationsCounter;
     213      qualityStopBranch.TrueBranch = qualityComparator;
     214      qualityStopBranch.Successor = null;
     215      qualityComparator.Successor = continueByQualityBranch;
     216      continueByQualityBranch.TrueBranch = iterationsCounter;
     217      continueByQualityBranch.FalseBranch = null;
     218      continueByQualityBranch.Successor = null;
    205219      iterationsCounter.Successor = comparator;
    206 
    207       ConditionalBranch branch = new ConditionalBranch();
    208       branch.ConditionParameter.ActualName = "ContinueByIteration";
    209       branch.TrueBranch = analyzer;
    210       comparator.Successor = branch;
     220      comparator.Successor = continueByIterationBranch;
     221      continueByIterationBranch.TrueBranch = analyzer;
     222      continueByIterationBranch.FalseBranch = null;
     223      continueByIterationBranch.Successor = null;
    211224
    212225      RegisterEventHandlers();
    … …  
    214227
    215228    public override IDeepCloneable Clone(Cloner cloner) {
    216       return new RobustTabooSearchQAP(this, cloner);
     229      return new RobustTabooSearch(this, cloner);
    217230    }
    218231
    … …  
    246259    }
    247260
     261    private void UseAlternativeAspirationParameter_ValueChanged(object sender, EventArgs e) {
     262      UpdateAlternativeAspirationTenure();
     263    }
     264
     265    private void AlternativeAspirationTenureParameter_ValueChanged(object sender, EventArgs e) {
     266      if (AlternativeAspirationTenure < MaximumIterations
     267        && !UseAlternativeAspiration) {
     268        UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
     269        UseAlternativeAspiration = true;
     270        UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
     271      } else if (AlternativeAspirationTenure >= MaximumIterations
     272        && UseAlternativeAspiration) {
     273        UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
     274        UseAlternativeAspiration = false;
     275        UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
     276      }
     277    }
     278
     279    [StorableHook(HookType.AfterDeserialization)]
     280    private void AfterDeserialization() {
     281      RegisterEventHandlers();
     282    }
     283
    248284    private void RegisterEventHandlers() {
    249       if (Problem != null) {
    250         Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    251       }
     285      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
     286      AlternativeAspirationTenureParameter.Value.ValueChanged += new EventHandler(AlternativeAspirationTenureParameter_ValueChanged);
     287    }
     288
     289    protected override void RegisterProblemEvents() {
     290      base.RegisterProblemEvents();
     291      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
     292    }
     293
     294    protected override void DeregisterProblemEvents() {
     295      Problem.Evaluator.QualityParameter.ActualNameChanged -= new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
     296      base.DeregisterProblemEvents();
    252297    }
    253298
    254299    public override void Start() {
    255300      if (ExecutionState == ExecutionState.Prepared) {
    256         DoubleMatrix shortTermMemory = new DoubleMatrix(Problem.Weights.Rows, Problem.Weights.Rows);
    257         DoubleMatrix longTermMemory = new DoubleMatrix(Problem.Weights.Rows, Problem.Weights.Rows);
    258         for (int i = 0; i < shortTermMemory.Rows; i++)
    259           for (int j = 0; j < shortTermMemory.Rows; j++) {
    260             shortTermMemory[i, j] = -1;
    261             longTermMemory[i, j] = -1;
     301        int dim = Problem.Weights.Rows;
     302        IntMatrix shortTermMemory = new IntMatrix(dim, dim);
     303        for (int i = 0; i < dim; i++)
     304          for (int j = 0; j < dim; j++) {
     305            shortTermMemory[i, j] = -(dim * (i + 1) + j + 1);
    262306          }
    263307
    264308        GlobalScope.Variables.Add(new Variable("ShortTermMemory", shortTermMemory));
    265         GlobalScope.Variables.Add(new Variable("LongTermMemory", longTermMemory));
     309        GlobalScope.Variables.Add(new Variable("MoveQualityMatrix", new DoubleMatrix(dim, dim)));
    266310      }
    267311      base.Start();
    … …  
    271315      MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
    272316      MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
    273       TabuTenureAdaptionInterval = 2 * MaximumTabuTenure;
     317      UpdateAlternativeAspirationTenure();
     318    }
     319
     320    private void UpdateAlternativeAspirationTenure() {
     321      if (UseAlternativeAspiration) {
     322        AlternativeAspirationTenure = Problem.Weights.Rows * Problem.Weights.Rows / 2;
     323      } else {
     324        AlternativeAspirationTenure = int.MaxValue;
     325      }
    274326    }
    275327
    … …  
    277329      AnalyzerParameter.Value.Operators.Clear();
    278330      if (Problem != null) {
    279         foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>())
    280           if (!(analyzer is AlleleFrequencyAnalyzer<Permutation>) && !(analyzer is PopulationDiversityAnalyzer<Permutation>))
    281             AnalyzerParameter.Value.Operators.Add(analyzer);
     331        foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>()) {
     332          AnalyzerParameter.Value.Operators.Add(analyzer);
     333          if (!(analyzer is BestQAPSolutionAnalyzer))
     334            AnalyzerParameter.Value.Operators.SetItemCheckedState(analyzer, false);
     335        }
    282336      }
    283337      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer);

  • branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs

    r5933 r6586  
    4949    }
    5050
     51    /// <summary>
     52    /// Calculates the quality of the move <paramref name="move"/> by evaluating the changes.
     53    /// The runtime complexity of this method is O(N) with N being the size of the permutation.
     54    /// </summary>
     55    /// <param name="assignment">The current permutation.</param>
     56    /// <param name="move">The move that is to be evaluated if it was applied to the current permutation.</param>
     57    /// <param name="weights">The weights matrix.</param>
     58    /// <param name="distances">The distances matrix.</param>
     59    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
    5160    public static double Apply(Permutation assignment, Swap2Move move, DoubleMatrix weights, DoubleMatrix distances) {
    5261      if (move.Index1 == move.Index2) return 0;
    … …  
    7382    }
    7483
     84    /// <summary>
     85    /// Is able to compute the move qualities faster O(1) in some cases if it knows the quality of
     86    /// performing the move <paramref name="move"/> previously. In other cases it performs a
     87    /// standard move quality calculation with runtime complexity O(N).
     88    /// </summary>
     89    /// <remarks>
     90    /// The number of cases that the calculation can be performed faster grows with N^2
     91    /// while the number of cases which require a larger recalculation grows linearly with N.
     92    /// Larger problem instances thus benefit from this faster method to a larger degree.
     93    /// </remarks>
     94    /// <param name="assignment">The current permutation.</param>
     95    /// <param name="move">The current move that is to be evaluated.</param>
     96    /// <param name="previousQuality">The quality of that move as evaluated for the previous permutation.</param>
     97    /// <param name="weights">The weigths matrix.</param>
     98    /// <param name="distances">The distances matrix.</param>
     99    /// <param name="lastMove">The move that was applied to transform the permutation from the previous to the current one.</param>
     100    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
     101    public static double Apply(Permutation assignment, Swap2Move move, double previousQuality,
     102      DoubleMatrix weights, DoubleMatrix distances, Swap2Move lastMove) {
     103      bool overlapsLastMove = move.Index1 == lastMove.Index1
     104                           || move.Index2 == lastMove.Index1
     105                           || move.Index1 == lastMove.Index2
     106                           || move.Index2 == lastMove.Index2;
     107
     108      if (!overlapsLastMove) {
     109        int r = lastMove.Index1, u = move.Index1, s = lastMove.Index2, v = move.Index2;
     110        int pR = assignment[lastMove.Index1], pU = assignment[move.Index1], pS = assignment[lastMove.Index2], pV = assignment[move.Index2];
     111
     112        return previousQuality
     113          + (weights[r, u] - weights[r, v] + weights[s, v] - weights[s, u])
     114            * (distances[pS, pU] - distances[pS, pV] + distances[pR, pV] - distances[pR, pU])
     115          + (weights[u, r] - weights[v, r] + weights[v, s] - weights[u, s])
     116            * (distances[pU, pS] - distances[pV, pS] + distances[pV, pR] - distances[pU, pR]);
     117      } else {
     118        return Apply(assignment, move, weights, distances);
     119      }
     120    }
     121
    75122    public override IOperation Apply() {
    76123      Swap2Move move = Swap2MoveParameter.ActualValue;

  • branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs

    r5933 r6586  
    6060      for (int i = 0; i < ProblemSize - 1; i++) {
    6161        for (int j = i + 1; j < ProblemSize; j++) {
    62           symmetricDistances[i, j] = random.Next(ProblemSize);
     62          symmetricDistances[i, j] = random.Next(ProblemSize * 100);
    6363          symmetricDistances[j, i] = symmetricDistances[i, j];
    64           symmetricWeights[i, j] = random.Next(ProblemSize);
     64          symmetricWeights[i, j] = random.Next(ProblemSize * 100);
    6565          symmetricWeights[j, i] = symmetricWeights[i, j];
    66           asymmetricDistances[i, j] = random.Next(ProblemSize);
    67           asymmetricDistances[j, i] = random.Next(ProblemSize);
    68           asymmetricWeights[i, j] = random.Next(ProblemSize);
    69           asymmetricWeights[j, i] = random.Next(ProblemSize);
    70           nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize);
    71           nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize);
    72           nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize);
    73           nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize);
     66          asymmetricDistances[i, j] = random.Next(ProblemSize * 100);
     67          asymmetricDistances[j, i] = random.Next(ProblemSize * 100);
     68          asymmetricWeights[i, j] = random.Next(ProblemSize * 100);
     69          asymmetricWeights[j, i] = random.Next(ProblemSize * 100);
     70          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize * 100);
     71          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize * 100);
     72          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize * 100);
     73          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize * 100);
    7474        }
    75         nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize);
    76         nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize);
     75        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize * 100);
     76        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize * 100);
    7777      }
    7878      int index = random.Next(ProblemSize);
    7979      if (nonZeroDiagonalDistances[index, index] == 0)
    80         nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize);
     80        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize * 100);
    8181      index = random.Next(ProblemSize);
    8282      if (nonZeroDiagonalWeights[index, index] == 0)
    83         nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize);
     83        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize * 100);
    8484      assignment = new Permutation(PermutationTypes.Absolute, ProblemSize, random);
     85    }
     86
     87    [TestMethod]
     88    public void Swap2MoveEvaluatorFastEvaluationTest() {
     89
     90      for (int i = 0; i < 500; i++) {
     91        Swap2Move lastMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
     92        Permutation prevAssignment = (Permutation)assignment.Clone();
     93        Swap2Manipulator.Apply(assignment, lastMove.Index1, lastMove.Index2);
     94        Permutation nextAssignment = (Permutation)assignment.Clone();
     95        Swap2Move currentMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
     96        Swap2Manipulator.Apply(nextAssignment, currentMove.Index1, currentMove.Index2);
     97
     98        double moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, symmetricWeights, symmetricDistances);
     99        double moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
     100                moveBefore, symmetricWeights, symmetricDistances, lastMove);
     101        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
     102        double after = QAPEvaluator.Apply(nextAssignment, symmetricWeights, symmetricDistances);
     103
     104        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on symmetric matrices: " + Environment.NewLine
     105          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
     106
     107        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, asymmetricWeights, asymmetricDistances);
     108        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
     109                moveBefore, asymmetricWeights, asymmetricDistances, lastMove);
     110        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     111        after = QAPEvaluator.Apply(nextAssignment, asymmetricWeights, asymmetricDistances);
     112
     113        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on asymmetric matrices: " + Environment.NewLine
     114          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
     115
     116        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     117        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
     118                moveBefore, nonZeroDiagonalWeights, nonZeroDiagonalDistances, lastMove);
     119        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     120        after = QAPEvaluator.Apply(nextAssignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     121
     122        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on non-zero diagonal matrices: " + Environment.NewLine
     123          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
     124      }
    85125    }
    86126
Note: See TracChangeset for help on using the changeset viewer.