Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/12/16 14:14:11 (7 years ago)
Author:
abeham
Message:

#2701:

  • Added TryGetBy(First|Second) method to BidirectionalDictionary
  • Updated linear linkage encoding
    • Added move generator and moves for shift, merge, split, and extract moves
    • Added unit test (Apply/Undo)
  • Updated MemPR (linear linkage)
    • Added basic tabu walk
  • Fixed bug in MemPR (permutation)
  • Updated Tests project
File:
1 edited

Legend:

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

    r14471 r14477  
    2626using HeuristicLab.Algorithms.MemPR.Interfaces;
    2727using HeuristicLab.Algorithms.MemPR.Util;
     28using HeuristicLab.Collections;
    2829using HeuristicLab.Common;
    2930using HeuristicLab.Core;
     
    9293    }
    9394
    94     protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) {
    95       return 0;
    96       /*Func<Encodings.LinearLinkageEncoding.LinearLinkage, IRandom, double> eval = new EvaluationWrapper<Encodings.LinearLinkageEncoding.LinearLinkage>(Context.Problem, scope).Evaluate;
     95    protected override int TabuWalk(
     96        ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope,
     97        int maxEvals, CancellationToken token,
     98        ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> sub_space = null) {
     99      var maximization = Context.Problem.Maximization;
     100      var subspace = sub_space is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)sub_space).Subspace : null;
     101      var evaluations = 0;
    97102      var quality = scope.Fitness;
    98       var lle = scope.Solution;
    99       var random = Context.Random;
    100       var evaluations = 0;
    101       var maximization = Context.Problem.Maximization;
     103      var bestQuality = quality;
    102104      if (double.IsNaN(quality)) {
    103         quality = eval(lle, random);
     105        Evaluate(scope, token);
     106        quality = scope.Fitness;
    104107        evaluations++;
    105       }
    106       Encodings.LinearLinkageEncoding.LinearLinkage bestOfTheWalk = null;
    107       double bestOfTheWalkF = double.NaN;
    108       var current = (Encodings.LinearLinkageEncoding.LinearLinkage)lle.Clone();
    109       var currentF = quality;
    110       var overallImprovement = false;
     108        if (evaluations >= maxEvals) return evaluations;
     109      }
     110      var currentScope = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)scope.Clone();
     111      var current = currentScope.Solution;
     112
    111113      var tabu = new double[current.Length, current.Length];
    112114      for (var i = 0; i < current.Length; i++) {
    113115        for (var j = i; j < current.Length; j++) {
    114           tabu[i, j] = tabu[j, i] = double.MaxValue;
    115         }
    116         tabu[i, current[i]] = currentF;
    117       }
    118 
    119       var steps = 0;
    120       var stepsUntilBestOfWalk = 0;
     116          tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;
     117        }
     118        tabu[i, current[i]] = quality;
     119      }
     120     
     121      // this dictionary holds the last relevant links
     122      var links = new BidirectionalDictionary<int, int>();
     123      bool allMoveTabu;
    121124      for (var iter = 0; iter < int.MaxValue; iter++) {
    122         var allTabu = true;
    123         var bestOfTheRestF = double.NaN;
    124         object bestOfTheRest = null;
    125         var improved = false;
    126         foreach () {
    127           if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
     125        allMoveTabu = true;
     126        // clear the dictionary before a new pass through the array is made
     127        links.Clear();
     128        for (var i = 0; i < current.Length; i++) {
     129          if (subspace != null && !subspace[i]) {
     130            links.RemoveBySecond(i);
     131            links.Add(i, current[i]);
    128132            continue;
    129 
    130 
    131           var q = eval(current, random);
    132           evaluations++;
    133           if (FitnessComparer.IsBetter(maximization, q, quality)) {
    134             overallImprovement = true;
    135             quality = q;
    136             for (var i = 0; i < current.Length; i++) lle[i] = current[i];
    137           }
    138           // check if it would not be an improvement to swap these into their positions
    139           var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index1, current[swap.Index1]])
    140                     && !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index2, current[swap.Index2]]);
    141           if (!isTabu) allTabu = false;
    142           if (FitnessComparer.IsBetter(maximization, q, currentF) && !isTabu) {
    143             if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
    144               bestOfTheWalk = (Encodings.LinearLinkageEncoding.LinearLinkage)current.Clone();
    145               bestOfTheWalkF = q;
    146               stepsUntilBestOfWalk = steps;
    147             }
    148             steps++;
    149             improved = true;
    150             // perform the move
    151             currentF = q;
    152             // mark that to move them to their previous position requires to make an improvement
    153             tabu[swap.Index1, current[swap.Index2]] = maximization ? Math.Max(q, tabu[swap.Index1, current[swap.Index2]])
    154                                                                    : Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
    155             tabu[swap.Index2, current[swap.Index1]] = maximization ? Math.Max(q, tabu[swap.Index2, current[swap.Index1]])
    156                                                                    : Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
    157           } else { // undo the move
    158             if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
    159               bestOfTheRest = swap;
    160               bestOfTheRestF = q;
    161             }
    162             current[swap.Index2] = current[swap.Index1];
    163             current[swap.Index1] = h;
    164           }
     133          }
     134
     135          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) {
     149              if (maximization) {
     150                tabu[i, next] = Math.Max(tabu[i, next], moveF);
     151                tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);
     152              } else {
     153                tabu[i, next] = Math.Min(tabu[i, next], moveF);
     154                tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);
     155              }
     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;
     163          }
     164          links.RemoveBySecond(i);
     165          links.Add(i, current[i]);
    165166          if (evaluations >= maxEvals) break;
    166         }
    167         if (!allTabu && !improved && bestOfTheRest != null) {
    168           tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]])
    169                                                                                    : Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
    170           tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]])
    171                                                                                    : Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
    172 
    173           var h = current[bestOfTheRest.Index1];
    174           current[bestOfTheRest.Index1] = current[bestOfTheRest.Index2];
    175           current[bestOfTheRest.Index2] = h;
    176 
    177           currentF = bestOfTheRestF;
    178           steps++;
    179         } else if (allTabu) break;
     167          if (token.IsCancellationRequested) break;
     168        }
     169        if (allMoveTabu) break;
    180170        if (evaluations >= maxEvals) break;
    181       }
    182       Context.IncrementEvaluatedSolutions(evaluations);
    183       if (!overallImprovement && bestOfTheWalk != null) {
    184         quality = bestOfTheWalkF;
    185         for (var i = 0; i < current.Length; i++) lle[i] = bestOfTheWalk[i];
    186       }
    187       return stepsUntilBestOfWalk;*/
     171        if (token.IsCancellationRequested) break;
     172      }
     173      return evaluations;
    188174    }
    189175
Note: See TracChangeset for help on using the changeset viewer.