Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/20/17 15:41:27 (7 years ago)
Author:
abeham
Message:

#1614:

  • Implementing basic algorithm according to paper (rechecking all operators)
  • Checking implementation with paper
  • Improved speed of move generator
  • Improved speed of randomized solution creator
File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

    r15512 r15553  
    9494    }
    9595
    96     /// <summary>
    97     /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
    98     /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
    99     /// the maxItr parameter defined by Mateus et al.
    100     /// </summary>
    101     /// <param name="random">The random number generator to use.</param>
    102     /// <param name="assignment">The equipment-location assignment vector.</param>
    103     /// <param name="quality">The solution quality.</param>
    104     /// <param name="evaluation">The evaluation result of the solution.</param>
    105     /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
    106     /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
    107     /// <param name="problemInstance">The problem instance that contains the data.</param>
    108     /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
    109     /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
    110     public static void Apply(IRandom random, IntegerVector assignment,
    111       DoubleValue quality, ref Evaluation evaluation, IntValue maxCLS, IntValue maximumIterations,
    112       GQAPInstance problemInstance, IntValue evaluatedSolutions, PercentValue oneMoveProbability) {
     96    public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
     97      double oneMoveProbability, int maximumIterations,
     98      GQAPInstance problemInstance, out int evaluatedSolutions) {
     99      var fit = problemInstance.ToSingleObjective(sol.Evaluation);
     100      var eval = sol.Evaluation;
     101      Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
     102        out evaluatedSolutions);
     103      sol.Evaluation = eval;
     104    }
     105
     106      /// <summary>
     107      /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
     108      /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
     109      /// the maxItr parameter defined by Mateus et al.
     110      /// </summary>
     111      /// <param name="random">The random number generator to use.</param>
     112      /// <param name="assignment">The equipment-location assignment vector.</param>
     113      /// <param name="quality">The solution quality.</param>
     114      /// <param name="evaluation">The evaluation result of the solution.</param>
     115      /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
     116      /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
     117      /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
     118      /// <param name="problemInstance">The problem instance that contains the data.</param>
     119      /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
     120      public static void Apply(IRandom random, IntegerVector assignment,
     121      ref double quality, ref Evaluation evaluation, int maxCLS,
     122      double oneMoveProbability, int maximumIterations,
     123      GQAPInstance problemInstance, out int evaluatedSolutions) {
     124      evaluatedSolutions = 0;
    113125      var capacities = problemInstance.Capacities;
    114126      var demands = problemInstance.Demands;
    … …  
    121133        do {
    122134          NMove move;
    123           if (random.NextDouble() < oneMoveProbability.Value)
    124             move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 1, capacities);
    125           else move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 2, capacities);
     135          if (random.NextDouble() < oneMoveProbability)
     136            move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(random, assignment, capacities);
     137          else move = StochasticNMoveSingleMoveGenerator.GenerateTwoMove(random, assignment, capacities);
    126138         
    127139          var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
    … …  
    129141          double moveQuality = problemInstance.ToSingleObjective(moveEval);
    130142
    131           if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality.Value) {
     143          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) {
    132144            CLS.Add(Tuple.Create(move, moveQuality, moveEval));
    133145            sum += 1.0 / moveQuality;
    134146          }
    135147          count++;
    136         } while (CLS.Count < maxCLS.Value && count < maximumIterations.Value);
     148        } while (CLS.Count < maxCLS && count < maximumIterations);
    137149
    138150        if (CLS.Count == 0) {
    139           evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
     151          evaluatedSolutions += (int)Math.Ceiling(evaluations);
    140152          return; // END
    141153        } else {
    … …  
    150162          }
    151163          NMoveMaker.Apply(assignment, selected.Item1);
    152           quality.Value = selected.Item2;
     164          quality = selected.Item2;
    153165          evaluation = selected.Item3;
    154166        }
    … …  
    158170    public override IOperation Apply() {
    159171      var evaluation = EvaluationParameter.ActualValue;
     172      var quality = QualityParameter.ActualValue;
     173      var fit = quality.Value;
     174      var evaluatedSolutions = 0;
     175
    160176      Apply(RandomParameter.ActualValue,
    161177        AssignmentParameter.ActualValue,
    162         QualityParameter.ActualValue,
     178        ref fit,
    163179        ref evaluation,
    164         MaximumCandidateListSizeParameter.ActualValue,
    165         MaximumIterationsParameter.ActualValue,
     180        MaximumCandidateListSizeParameter.ActualValue.Value,
     181        OneMoveProbabilityParameter.ActualValue.Value,
     182        MaximumIterationsParameter.ActualValue.Value,
    166183        ProblemInstanceParameter.ActualValue,
    167         EvaluatedSolutionsParameter.ActualValue,
    168         OneMoveProbabilityParameter.ActualValue);
     184        out evaluatedSolutions);
     185
    169186      EvaluationParameter.ActualValue = evaluation;
     187      quality.Value = fit;
     188      EvaluatedSolutionsParameter.ActualValue.Value += evaluatedSolutions;
    170189      return base.Apply();
    171190    }
Note: See TracChangeset for help on using the changeset viewer.