Changeset 14484


Ignore:
Timestamp:
12/13/16 08:02:53 (3 years ago)
Author:
abeham
Message:

#2701:

  • Updated tabu walk for mempr (linear linkage)
File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

    r14477 r14484  
    101101      var evaluations = 0;
    102102      var quality = scope.Fitness;
    103       var bestQuality = quality;
    104103      if (double.IsNaN(quality)) {
    105104        Evaluate(scope, token);
     
    108107        if (evaluations >= maxEvals) return evaluations;
    109108      }
     109      var bestQuality = quality;
    110110      var currentScope = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)scope.Clone();
    111111      var current = currentScope.Solution;
     112      Encodings.LinearLinkageEncoding.LinearLinkage bestOfTheWalk = null;
     113      var bestOfTheWalkF = double.NaN;
    112114
    113115      var tabu = new double[current.Length, current.Length];
     
    121123      // this dictionary holds the last relevant links
    122124      var links = new BidirectionalDictionary<int, int>();
    123       bool allMoveTabu;
     125      Move bestOfTheRest = null;
     126      var bestOfTheRestF = double.NaN;
     127      var lastAppliedMove = -1;
    124128      for (var iter = 0; iter < int.MaxValue; iter++) {
    125         allMoveTabu = true;
    126129        // clear the dictionary before a new pass through the array is made
    127130        links.Clear();
     
    134137
    135138          var next = current[i];
    136           foreach (var move in MoveGenerator.GenerateForItem(i, next, links)) {
    137             // we intend to break link i -> next
    138             var qualityToBreak = tabu[i, next];
    139             move.Apply(current);
    140             var qualityToRestore = tabu[i, current[i]]; // current[i] is new next
    141             Evaluate(currentScope, token);
    142             evaluations++;
    143             var moveF = currentScope.Fitness;
    144             var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak)
    145                          && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore);
    146             if (isNotTabu) allMoveTabu = false;
    147             var isImprovement = FitnessComparer.IsBetter(maximization, moveF, bestQuality);
    148             if (isNotTabu || isImprovement) {
     139
     140          if (lastAppliedMove == i) {
     141            if (bestOfTheRest != null) {
     142              bestOfTheRest.Apply(current);
     143              currentScope.Fitness = bestOfTheRestF;
     144              quality = bestOfTheRestF;
    149145              if (maximization) {
    150                 tabu[i, next] = Math.Max(tabu[i, next], moveF);
    151                 tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);
     146                tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);
     147                tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);
    152148              } else {
    153                 tabu[i, next] = Math.Min(tabu[i, next], moveF);
    154                 tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);
     149                tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);
     150                tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);
    155151              }
    156               quality = moveF;
    157               if (isImprovement) bestQuality = quality;
    158 
    159               move.UpdateLinks(links);
    160               break;
    161             } else move.Undo(current);
    162             if (evaluations >= maxEvals) break;
     152              if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
     153                bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
     154                bestOfTheWalkF = bestOfTheRestF;
     155              }
     156              bestOfTheRest = null;
     157              bestOfTheRestF = double.NaN;
     158              lastAppliedMove = i;
     159            } else {
     160              lastAppliedMove = -1;
     161            }
     162            break;
     163          } else {
     164            foreach (var move in MoveGenerator.GenerateForItem(i, next, links)) {
     165              // we intend to break link i -> next
     166              var qualityToBreak = tabu[i, next];
     167              move.Apply(current);
     168              var qualityToRestore = tabu[i, current[i]]; // current[i] is new next
     169              Evaluate(currentScope, token);
     170              evaluations++;
     171              var moveF = currentScope.Fitness;
     172              var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak)
     173                              && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore);
     174              var isImprovement = FitnessComparer.IsBetter(maximization, moveF, quality);
     175              var isAspired = FitnessComparer.IsBetter(maximization, moveF, bestQuality);
     176              if ((isNotTabu && isImprovement) || isAspired) {
     177                if (maximization) {
     178                  tabu[i, next] = Math.Max(tabu[i, next], moveF);
     179                  tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);
     180                } else {
     181                  tabu[i, next] = Math.Min(tabu[i, next], moveF);
     182                  tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);
     183                }
     184                quality = moveF;
     185                if (isAspired) bestQuality = quality;
     186
     187                move.UpdateLinks(links);
     188
     189                if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) {
     190                  bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
     191                  bestOfTheWalkF = moveF;
     192                }
     193
     194                bestOfTheRest = null;
     195                bestOfTheRestF = double.NaN;
     196                lastAppliedMove = i;
     197                break;
     198              } else {
     199                if (isNotTabu) {
     200                  if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheRestF)) {
     201                    bestOfTheRest = move;
     202                    bestOfTheRestF = moveF;
     203                  }
     204                }
     205                move.Undo(current);
     206                currentScope.Fitness = quality;
     207              }
     208              if (evaluations >= maxEvals) break;
     209            }
    163210          }
    164211          links.RemoveBySecond(i);
     
    167214          if (token.IsCancellationRequested) break;
    168215        }
    169         if (allMoveTabu) break;
     216        if (lastAppliedMove == -1) { // no move has been applied
     217          if (bestOfTheRest != null) {
     218            var i = bestOfTheRest.Item;
     219            var next = current[i];
     220            bestOfTheRest.Apply(current);
     221            currentScope.Fitness = bestOfTheRestF;
     222            quality = bestOfTheRestF;
     223            if (maximization) {
     224              tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);
     225              tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);
     226            } else {
     227              tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);
     228              tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);
     229            }
     230            if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
     231              bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
     232              bestOfTheWalkF = bestOfTheRestF;
     233            }
     234
     235            bestOfTheRest = null;
     236            bestOfTheRestF = double.NaN;
     237          } else break;
     238        }
    170239        if (evaluations >= maxEvals) break;
    171240        if (token.IsCancellationRequested) break;
     241      }
     242      if (bestOfTheWalk != null) {
     243        scope.Solution = bestOfTheWalk;
     244        scope.Fitness = bestOfTheWalkF;
    172245      }
    173246      return evaluations;
Note: See TracChangeset for help on using the changeset viewer.