Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/03/16 00:32:09 (8 years ago)
Author:
abeham
Message:

#2701: working on MemPR implementation

Location:
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation
Files:
16 added
4 copied

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs

    r14429 r14450  
    2424using System.Linq;
    2525using System.Threading;
     26using HeuristicLab.Algorithms.MemPR.Interfaces;
     27using HeuristicLab.Algorithms.MemPR.Util;
    2628using HeuristicLab.Common;
    2729using HeuristicLab.Core;
    28 using HeuristicLab.Encodings.BinaryVectorEncoding;
     30using HeuristicLab.Encodings.PermutationEncoding;
    2931using HeuristicLab.Optimization;
    30 using HeuristicLab.Optimization.LocalSearch;
    31 using HeuristicLab.Optimization.SolutionModel;
    3232using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3333using HeuristicLab.PluginInfrastructure;
    3434using HeuristicLab.Random;
    3535
    36 namespace HeuristicLab.Algorithms.MemPR.Binary {
    37   [Item("MemPR (binary)", "MemPR implementation for binary vectors.")]
     36namespace HeuristicLab.Algorithms.MemPR.Permutation {
     37  [Item("MemPR (permutation)", "MemPR implementation for permutations.")]
    3838  [StorableClass]
    3939  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    40   public class BinaryMemPR : MemPRAlgorithm<BinaryVector, BinaryMemPRContext, BinarySingleSolutionMemPRContext> {
     40  public class PermutationMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
    4141    private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    42    
     42
     43#if DEBUG
     44    private const bool VALIDATE = true;
     45#else
     46    private const bool VALIDATE = false;
     47#endif
     48
    4349    [StorableConstructor]
    44     protected BinaryMemPR(bool deserializing) : base(deserializing) { }
    45     protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }
    46     public BinaryMemPR() {
    47       foreach (var trainer in ApplicationManager.Manager.GetInstances<IBinarySolutionModelTrainer<BinaryMemPRContext>>())
     50    protected PermutationMemPR(bool deserializing) : base(deserializing) { }
     51    protected PermutationMemPR(PermutationMemPR original, Cloner cloner) : base(original, cloner) { }
     52    public PermutationMemPR() {
     53      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<PermutationMemPRPopulationContext>>())
    4854        SolutionModelTrainerParameter.ValidValues.Add(trainer);
    4955     
    50       foreach (var localSearch in ApplicationManager.Manager.GetInstances<IBinaryLocalSearch<BinarySingleSolutionMemPRContext>>()) {
    51         // only use local search operators that can deal with a restricted solution space
    52         var lsType = localSearch.GetType();
    53         var genTypeDef = lsType.GetGenericTypeDefinition();
    54         // TODO: By convention, context type must be put last
    55         // TODO: Fails with non-generic types
    56         if (genTypeDef.GetGenericArguments().Last().GetGenericParameterConstraints().Any(x => typeof(IBinarySolutionSubspaceContext).IsAssignableFrom(x))) {
    57           localSearch.EvaluateFunc = EvaluateFunc;
    58           LocalSearchParameter.ValidValues.Add(localSearch);
    59         }
     56      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<PermutationMemPRSolutionContext>>()) {
     57        LocalSearchParameter.ValidValues.Add(localSearch);
    6058      }
    6159    }
    6260
    6361    public override IDeepCloneable Clone(Cloner cloner) {
    64       return new BinaryMemPR(this, cloner);
    65     }
    66 
    67     protected double EvaluateFunc(BinaryVector solution) {
    68       var scope = ToScope(solution);
    69       Evaluate(scope, CancellationToken.None);
    70       return scope.Fitness;
    71     }
    72 
    73     protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    74       var len = a.Solution.Length;
    75       var acode = a.Solution;
    76       var bcode = b.Solution;
    77       for (var i = 0; i < len; i++)
    78         if (acode[i] != bcode[i]) return false;
    79       return true;
    80     }
    81 
    82     protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    83       var len = a.Solution.Length;
    84       var acode = a.Solution;
    85       var bcode = b.Solution;
    86       var hamming = 0;
    87       for (var i = 0; i < len; i++)
    88         if (acode[i] != bcode[i]) hamming++;
    89       return hamming / (double)len;
    90     }
    91 
    92     protected override ISingleObjectiveSolutionScope<BinaryVector> ToScope(BinaryVector code, double fitness = double.NaN) {
    93       var creator = Problem.SolutionCreator as IBinaryVectorCreator;
     62      return new PermutationMemPR(this, cloner);
     63    }
     64
     65    protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
     66      return new PermutationEqualityComparer().Equals(a.Solution, b.Solution);
     67    }
     68
     69    protected override double Dist(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
     70      return Dist(a.Solution, b.Solution);
     71    }
     72
     73    private static double Dist(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
     74      return 1.0 - PermutationSimilarityCalculator.CalculateSimilarity(a, b);
     75    }
     76
     77    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> ToScope(Encodings.PermutationEncoding.Permutation code, double fitness = double.NaN) {
     78      var creator = Problem.SolutionCreator as IPermutationCreator;
    9479      if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
    95       return new SingleObjectiveSolutionScope<BinaryVector>(code, creator.BinaryVectorParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
     80      return new SingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation>(code, creator.PermutationParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
    9681        Parent = Context.Scope
    9782      };
    9883    }
    9984
    100     protected override ISolutionSubspace CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {
    101       var pop = solutions.ToList();
    102       var N = pop[0].Length;
    103       var subspace = new bool[N];
    104       for (var i = 0; i < N; i++) {
    105         var val = pop[0][i];
    106         if (inverse) subspace[i] = true;
    107         for (var p = 1; p < pop.Count; p++) {
    108           if (pop[p][i] != val) subspace[i] = !inverse;
    109         }
    110       }
    111       return new BinarySolutionSubspace(subspace);
    112     }
    113 
    114     protected override ISingleObjectiveSolutionScope<BinaryVector> Create(CancellationToken token) {
    115       var child = ToScope(null);
    116       RunOperator(Problem.SolutionCreator, child, token);
    117       return child;
    118     }
    119 
    120     protected override void TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int steps, CancellationToken token, ISolutionSubspace subspace = null) {
    121       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    122       if (double.IsNaN(scope.Fitness)) Evaluate(scope, token);
    123       SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
    124       var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
    125       var current = currentScope.Solution;
    126       var N = current.Length;
    127       var tabu = new Tuple<double, double>[N];
    128       for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
    129       var subN = subset != null ? subset.Count(x => x) : N;
    130       if (subN == 0) return;
    131       var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    132 
    133       for (var iter = 0; iter < steps; iter++) {
     85    protected override ISolutionSubspace<Encodings.PermutationEncoding.Permutation> CalculateSubspace(IEnumerable<Encodings.PermutationEncoding.Permutation> solutions, bool inverse = false) {
     86      var subspace = new bool[Problem.Encoding.Length, Problem.Encoding.PermutationTypeParameter.Value.Value == PermutationTypes.Absolute ? 1 : Problem.Encoding.Length];
     87
     88      switch (Problem.Encoding.PermutationTypeParameter.Value.Value) {
     89        case PermutationTypes.Absolute: {
     90            if (inverse) {
     91              for (var i = 0; i < subspace.GetLength(0); i++)
     92                subspace[i, 0] = true;
     93            }
     94            var first = solutions.First();
     95            foreach (var s in solutions.Skip(1)) {
     96              for (var i = 0; i < s.Length; i++) {
     97                if (first[i] != s[i]) subspace[i, 0] = !inverse;
     98              }
     99            }
     100          }
     101          break;
     102        case PermutationTypes.RelativeDirected: {
     103            if (inverse) {
     104              for (var i = 0; i < subspace.GetLength(0); i++)
     105                for (var j = 0; j < subspace.GetLength(1); j++)
     106                  subspace[i, j] = true;
     107            }
     108            var first = solutions.First();
     109            var placedFirst = new int[first.Length];
     110            for (var i = 0; i < first.Length; i++) {
     111              placedFirst[first[i]] = i;
     112            }
     113            foreach (var s in solutions.Skip(1)) {
     114              for (var i = 0; i < s.Length; i++) {
     115                if (placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)] != -1)
     116                  subspace[i, 0] = !inverse;
     117              }
     118            }
     119          }
     120          break;
     121        case PermutationTypes.RelativeUndirected: {
     122            if (inverse) {
     123              for (var i = 0; i < subspace.GetLength(0); i++)
     124                for (var j = 0; j < subspace.GetLength(1); j++)
     125                  subspace[i, j] = true;
     126            }
     127            var first = solutions.First();
     128            var placedFirst = new int[first.Length];
     129            for (var i = 0; i < first.Length; i++) {
     130              placedFirst[first[i]] = i;
     131            }
     132            foreach (var s in solutions.Skip(1)) {
     133              for (var i = 0; i < s.Length; i++) {
     134                if (Math.Abs(placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)]) != 1)
     135                  subspace[i, 0] = !inverse;
     136              }
     137            }
     138          }
     139          break;
     140        default:
     141          throw new ArgumentException(string.Format("Unknown permutation type {0}", Problem.Encoding.PermutationTypeParameter.Value.Value));
     142      }
     143      return new PermutationSolutionSubspace(subspace);
     144    }
     145
     146    protected override void TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int steps, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
     147      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
     148      var quality = scope.Fitness;
     149      try {
     150        TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, Context.HcSteps, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
     151      } finally {
     152        scope.Fitness = quality;
     153      }
     154    }
     155
     156    public static void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
     157      switch (perm.PermutationType) {
     158        case PermutationTypes.Absolute:
     159          TabuWalkSwap(random, perm, eval, ref quality, maxIterations, noTouch);
     160          break;
     161        case PermutationTypes.RelativeDirected:
     162          TabuWalkShift(random, perm, eval, ref quality, maxIterations, noTouch);
     163          break;
     164        case PermutationTypes.RelativeUndirected:
     165          TabuWalkOpt(random, perm, eval, ref quality, maxIterations, noTouch);
     166          break;
     167        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
     168      }
     169      if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
     170    }
     171
     172    public static void TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
     173      if (double.IsNaN(quality)) quality = eval(perm, random);
     174      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
     175      double bestOfTheWalkF = double.NaN;
     176      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
     177      var currentF = quality;
     178      var overallImprovement = false;
     179      //Console.WriteLine("Current    {0}", string.Join(", ", current));
     180      var tabu = new double[current.Length, current.Length];
     181      for (var i = 0; i < current.Length; i++) {
     182        for (var j = i; j < current.Length; j++) {
     183          tabu[i, j] = tabu[j, i] = double.MaxValue;
     184        }
     185        tabu[i, current[i]] = currentF;
     186      }
     187
     188      for (var iter = 0; iter < maxIterations; iter++) {
    134189        var allTabu = true;
    135190        var bestOfTheRestF = double.NaN;
    136         int bestOfTheRest = -1;
     191        Swap2Move bestOfTheRest = null;
    137192        var improved = false;
    138 
    139         for (var i = 0; i < subN; i++) {
    140           var idx = order[i];
    141           var before = currentScope.Fitness;
    142           current[idx] = !current[idx];
    143           Evaluate(currentScope, token);
    144           var after = currentScope.Fitness;
    145 
    146           if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
    147             bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
    148           }
    149 
    150           var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1;
    151           var isTabu = !IsBetter(after, qualityToBeat);
     193        //LogAlways("TabuWalk ({0}/{2}): {1}   ({3})", iter, currentF, maxIterations, string.Join(", ", current));
     194        foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
     195          if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
     196            continue;
     197
     198          var h = current[swap.Index1];
     199          current[swap.Index1] = current[swap.Index2];
     200          current[swap.Index2] = h;
     201          var q = eval(current, random);
     202          if (q < quality) {
     203            overallImprovement = true;
     204            quality = q;
     205            for (var i = 0; i < current.Length; i++) perm[i] = current[i];
     206          }
     207          // check if it would not be an improvement to swap these into their positions
     208          var isTabu = q >= tabu[swap.Index1, current[swap.Index1]] && q >= tabu[swap.Index2, current[swap.Index2]];
    152209          if (!isTabu) allTabu = false;
    153 
    154           if (IsBetter(after, before) && !isTabu) {
     210          if (q < currentF && !isTabu) {
     211            if (double.IsNaN(bestOfTheWalkF) || bestOfTheWalkF > q) {
     212              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
     213              bestOfTheWalkF = q;
     214            }
     215
    155216            improved = true;
    156             tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
     217            // perform the move
     218            currentF = q;
     219            // mark that to move them to their previous position requires to make an improvement
     220            tabu[swap.Index1, current[swap.Index2]] = Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
     221            //LogAlways("Making Tabu [{0},{1}] = {2}", swap.Index1, current[swap.Index2], tabu[swap.Index1, current[swap.Index2]]);
     222            tabu[swap.Index2, current[swap.Index1]] = Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
     223            //LogAlways("Making Tabu [{0},{1}] = {2}", swap.Index2, current[swap.Index1], tabu[swap.Index2, current[swap.Index1]]);
    157224          } else { // undo the move
    158             if (!isTabu && IsBetter(after, bestOfTheRestF)) {
    159               bestOfTheRest = idx;
    160               bestOfTheRestF = after;
    161             }
    162             current[idx] = !current[idx];
    163             currentScope.Fitness = before;
     225            if (!isTabu && (double.IsNaN(bestOfTheRestF) || q < bestOfTheRestF)) {
     226              bestOfTheRest = swap;
     227              bestOfTheRestF = q;
     228            }
     229            current[swap.Index2] = current[swap.Index1];
     230            current[swap.Index1] = h;
    164231          }
    165232        }
    166233        if (!allTabu && !improved) {
    167           var better = currentScope.Fitness;
    168           current[bestOfTheRest] = !current[bestOfTheRest];
    169           tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
    170           currentScope.Fitness = bestOfTheRestF;
     234          tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
     235          //LogAlways("Making Tabu [{0},{1}] = {2}", bestOfTheRest.Index1, current[bestOfTheRest.Index1], tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
     236          tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
     237          //LogAlways("Making Tabu [{0},{1}] = {2}", bestOfTheRest.Index2, current[bestOfTheRest.Index2], tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
     238
     239          var h = current[bestOfTheRest.Index1];
     240          current[bestOfTheRest.Index1] = current[bestOfTheRest.Index2];
     241          current[bestOfTheRest.Index2] = h;
     242
     243          currentF = bestOfTheRestF;
    171244        } else if (allTabu) break;
    172245      }
    173 
    174       scope.Adopt(bestOfTheWalk ?? currentScope);
    175     }
    176 
    177     protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
    178       var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone();
    179       offspring.Fitness = double.NaN;
    180       var code = offspring.Solution;
    181       var p2Code = p2.Solution;
    182       var bp = 0;
    183       var lastbp = 0;
    184       for (var i = 0; i < code.Length; i++) {
    185         if (code[i] == p2Code[i]) continue; // common bit
    186         if (bp % 2 == 1) {
    187           code[i] = p2Code[i];
    188         }
    189         if (Context.Random.Next(code.Length) < i - lastbp) {
    190           bp = (bp + 1) % 2;
    191           lastbp = i;
    192         }
    193       }
    194       return offspring;
    195     }
    196 
    197     protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace subspace = null) {
    198       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    199       offspring.Fitness = double.NaN;
    200       var code = offspring.Solution;
    201       for (var i = 0; i < code.Length; i++) {
    202         if (subset != null && subset[i]) continue;
    203         if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {
    204           code[i] = !code[i];
    205           if (subset != null) subset[i] = true;
    206         }
    207       }
    208     }
    209 
    210     protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
     246      if (!overallImprovement && bestOfTheWalk != null) {
     247        quality = bestOfTheWalkF;
     248        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
     249      }
     250    }
     251
     252    public static void TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
     253      return;
     254    }
     255
     256    public static void TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
     257      if (double.IsNaN(quality)) quality = eval(perm, random);
     258      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
     259      double bestOfTheWalkF = double.NaN;
     260      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
     261      var currentF = quality;
     262      var overallImprovement = false;
     263      //Console.WriteLine("Current    {0}", string.Join(", ", current));
     264      var tabu = new double[current.Length, current.Length];
     265      for (var i = 0; i < current.Length; i++) {
     266        for (var j = i; j < current.Length; j++) {
     267          tabu[i, j] = tabu[j, i] = double.MaxValue;
     268        }
     269        tabu[current[i], current.GetCircular(i + 1)] = currentF;
     270        tabu[current.GetCircular(i + 1), current[i]] = currentF;
     271      }
     272
     273      for (var iter = 0; iter < maxIterations; iter++) {
     274        var allTabu = true;
     275        var bestOfTheRestF = double.NaN;
     276        InversionMove bestOfTheRest = null;
     277        var improved = false;
     278
     279        foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random)) {
     280          var prev = opt.Index1 - 1;
     281          var next = (opt.Index2 + 1) % current.Length;
     282          if (prev < 0) prev += current.Length;
     283          if (noTouch != null && ((noTouch[current[prev], current[opt.Index1]]) || (noTouch[current[opt.Index2], current[next]])))
     284            continue;
     285
     286          InversionManipulator.Apply(current, opt.Index1, opt.Index2);
     287
     288          var q = eval(current, random);
     289          if (q < quality) {
     290            overallImprovement = true;
     291            quality = q;
     292            for (var i = 0; i < current.Length; i++) perm[i] = current[i];
     293          }
     294          // check if it would not be an improvement to opt these into their positions
     295          var isTabu = q >= tabu[current[prev], current[opt.Index1]] && q >= tabu[current[opt.Index2], current[next]];
     296          if (!isTabu) allTabu = false;
     297          if (q < currentF && !isTabu) {
     298            if (double.IsNaN(bestOfTheWalkF) || bestOfTheWalkF > q) {
     299              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
     300              bestOfTheWalkF = q;
     301            }
     302
     303            improved = true;
     304            // perform the move
     305            currentF = q;
     306            // mark that to move them to their previous position requires to make an improvement
     307            tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
     308            tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
     309            tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
     310            tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
     311          } else { // undo the move
     312            if (!isTabu && (double.IsNaN(bestOfTheRestF) || q < bestOfTheRestF)) {
     313              bestOfTheRest = opt;
     314              bestOfTheRestF = q;
     315            }
     316
     317            InversionManipulator.Apply(current, opt.Index1, opt.Index2);
     318          }
     319        }
     320        if (!allTabu && !improved) {
     321          var prev = bestOfTheRest.Index1 - 1;
     322          var next = (bestOfTheRest.Index2 + 1) % current.Length;
     323          if (prev < 0) prev += current.Length;
     324
     325          tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
     326          tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
     327          tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
     328          tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
     329
     330          InversionManipulator.Apply(current, bestOfTheRest.Index1, bestOfTheRest.Index2);
     331
     332          currentF = bestOfTheRestF;
     333        } else if (allTabu) break;
     334      }
     335      if (!overallImprovement && bestOfTheWalk != null) {
     336        quality = bestOfTheWalkF;
     337        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
     338      }
     339    }
     340
     341    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Cross(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
     342      Encodings.PermutationEncoding.Permutation child = null;
     343
     344      if (p1.Solution.PermutationType == PermutationTypes.Absolute) {
     345        child = CyclicCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     346      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) {
     347        child = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     348      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) {
     349        child = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     350      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType));
     351
     352      if (VALIDATE && !child.Validate()) throw new ArgumentException("Cross produced invalid child");
     353      return ToScope(child);
     354    }
     355
     356    protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
     357      Mutate(Context.Random, offspring.Solution, UncommonBitSubsetMutationProbabilityMagicConst, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
     358    }
     359
     360    public static void Mutate(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
     361      switch (perm.PermutationType) {
     362        case PermutationTypes.Absolute:
     363          MutateSwap(random, perm, p, subspace);
     364          break;
     365        case PermutationTypes.RelativeDirected:
     366          MutateShift(random, perm, p, subspace);
     367          break;
     368        case PermutationTypes.RelativeUndirected:
     369          MutateOpt(random, perm, p, subspace);
     370          break;
     371        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
     372      }
     373      if (VALIDATE && !perm.Validate()) throw new ArgumentException("Mutate produced invalid child");
     374    }
     375
     376    public static void MutateSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
     377      //Log("BEFOR: {0}", string.Join(", ", lle));
     378      // The goal of the mutation is to disrupt crossover when it's in an agreeing position
     379      var options = new List<int>(Enumerable.Range(0, perm.Length).Where(x => subspace == null || !subspace[x, 0]));
     380      if (options.Count < 1) return;
     381
     382      for (var i = options.Count - 1; i > 0; i--) {
     383        if (random.NextDouble() < p) {
     384          var j = random.Next(0, i);
     385          var h = perm[options[i]];
     386          perm[options[i]] = perm[options[j]];
     387          perm[options[j]] = h;
     388          if (subspace != null) {
     389            subspace[options[i], 0] = true;
     390            subspace[options[j], 0] = true;
     391          }
     392        }
     393      }
     394    }
     395
     396    public static void MutateShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
     397      //Log("BEFOR: {0}", string.Join(", ", lle));
     398      // The goal of the mutation is to disrupt crossover when it's in an agreeing position
     399      foreach (var shift in ExhaustiveInsertionMoveGenerator.Generate(perm).Shuffle(random)) {
     400        var prev1 = shift.Index1 - 1;
     401        var next1 = (shift.Index1 + 1) % perm.Length;
     402        if (prev1 < 0) prev1 += perm.Length;
     403        var prev3 = shift.Index3 - 1;
     404        var next3 = (shift.Index3 + 1) % perm.Length;
     405        if (prev3 < 0) prev3 += perm.Length;
     406        if (subspace == null || !(subspace[perm[prev1], perm[shift.Index1]] && subspace[perm[shift.Index1], perm[next1]]
     407            && subspace[perm[prev3], perm[shift.Index3]] && subspace[perm[shift.Index3], perm[next3]])) {
     408          if (random.NextDouble() < p) {
     409            if (subspace != null) {
     410              subspace[perm[prev1], perm[shift.Index1]] = true;
     411              subspace[perm[shift.Index1], perm[next1]] = true;
     412              subspace[perm[prev3], perm[shift.Index3]] = true;
     413              subspace[perm[shift.Index3], perm[next3]] = true;
     414            }
     415            TranslocationManipulator.Apply(perm, shift.Index1, shift.Index2, shift.Index3);
     416            return;
     417          }
     418        }
     419      }
     420    }
     421
     422    public static void MutateOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, double p, bool[,] subspace) {
     423      //Log("BEFOR: {0}", string.Join(", ", lle));
     424      // The goal of the mutation is to disrupt crossover when it's in an agreeing position
     425      foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(perm).Shuffle(random)) {
     426        var prev = opt.Index1 - 1;
     427        var next = (opt.Index2 + 1) % perm.Length;
     428        if (prev < 0) prev += perm.Length;
     429        if (subspace == null || !(subspace[perm[prev], perm[opt.Index1]] && subspace[perm[opt.Index2], perm[next]])) {
     430          if (random.NextDouble() < p) {
     431            if (subspace != null) {
     432              subspace[perm[prev], perm[opt.Index1]] = true;
     433              subspace[perm[opt.Index1], perm[prev]] = true;
     434              subspace[perm[opt.Index2], perm[next]] = true;
     435              subspace[perm[next], perm[opt.Index2]] = true;
     436            }
     437            InversionManipulator.Apply(perm, opt.Index1, opt.Index2);
     438            return;
     439          }
     440        }
     441      }
     442    }
     443
     444    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token) {
    211445      if (double.IsNaN(a.Fitness)) Evaluate(a, token);
    212446      if (double.IsNaN(b.Fitness)) Evaluate(b, token);
    … …  
    216450    }
    217451
    218     protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
    219       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
    220       var child = childScope.Solution;
    221       var better = betterScope.Solution;
    222       var worse = worseScope.Solution;
    223       ISingleObjectiveSolutionScope<BinaryVector> best = null;
    224       var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness;
    225       var bF = double.NaN;
    226       var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray();
    227       while (true) {
    228         var bestS = double.NaN;
    229         var bestIdx = -1;
    230         for (var i = 0; i < child.Length; i++) {
    231           var idx = order[i];
    232           // either move from worse to better or move from better away from worse
    233           if (fromWorseToBetter && child[idx] == better[idx] ||
    234             !fromWorseToBetter && child[idx] != worse[idx]) continue;
    235           child[idx] = !child[idx]; // move
    236           Evaluate(childScope, token);
    237           var s = childScope.Fitness;
    238           childScope.Fitness = cF;
    239           child[idx] = !child[idx]; // undo move
    240           if (IsBetter(s, cF)) {
    241             bestS = s;
    242             bestIdx = idx;
    243             break; // first-improvement
    244           }
    245           if (double.IsNaN(bestS) || IsBetter(s, bestS)) {
    246             // least-degrading
    247             bestS = s;
    248             bestIdx = idx;
    249           }
    250         }
    251         if (bestIdx < 0) break;
    252         child[bestIdx] = !child[bestIdx];
    253         cF = bestS;
    254         childScope.Fitness = cF;
    255         if (IsBetter(cF, bF)) {
    256           bF = cF;
    257           best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
    258         }
    259       }
    260       return best ?? childScope;
     452    protected virtual ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> betterScope, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> worseScope, CancellationToken token, bool fromWorseToBetter) {
     453      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope);
     454      double quality;
     455      return ToScope(Relink(Context.Random, betterScope.Solution, worseScope.Solution, wrapper.Evaluate, out quality));
     456    }
     457
     458    public static Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     459      if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
     460      switch (p1.PermutationType) {
     461        case PermutationTypes.Absolute:
     462          return RelinkSwap(random, p1, p2, eval, out best);
     463        case PermutationTypes.RelativeDirected:
     464          return RelinkShift(random, p1, p2, eval, out best);
     465        case PermutationTypes.RelativeUndirected:
     466          return RelinkOpt(random, p1, p2, eval, out best);
     467        default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
     468      }
     469    }
     470
     471    public static Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     472      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
     473
     474      best = double.NaN;
     475      Encodings.PermutationEncoding.Permutation bestChild = null;
     476
     477      var options = Enumerable.Range(0, child.Length).Where(x => child[x] != p2[x]).ToList();
     478      var invChild = new int[child.Length];
     479      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
     480
     481      //Log(string.Join(", ", child));
     482      while (options.Count > 0) {
     483        int bestOption = -1;
     484        var bestChange = double.NaN;
     485        for (var j = 0; j < options.Count; j++) {
     486          var idx = options[j];
     487          if (child[idx] == p2[idx]) {
     488            options.RemoveAt(j);
     489            j--;
     490            continue;
     491          }
     492          Swap(child, invChild[p2[idx]], idx);
     493          var moveF = eval(child, random);
     494          if (double.IsNaN(bestChange) || moveF < bestChange) {
     495            bestChange = moveF;
     496            bestOption = j;
     497          }
     498          // undo
     499          Swap(child, invChild[p2[idx]], idx);
     500        }
     501        if (!double.IsNaN(bestChange)) {
     502          var idx1 = options[bestOption];
     503          var idx2 = invChild[p2[idx1]];
     504          Swap(child, idx1, idx2);
     505          invChild[child[idx1]] = idx1;
     506          invChild[child[idx2]] = idx2;
     507          //Log(string.Join(", ", child));
     508          if (double.IsNaN(best) || bestChange < best) {
     509            if (Dist(child, p2) > 0) {
     510              best = bestChange;
     511              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
     512            }
     513          }
     514          options.RemoveAt(bestOption);
     515        }
     516      }
     517      //Log(string.Join(", ", p2));
     518
     519      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
     520      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
     521
     522      if (bestChild == null) best = eval(child, random);
     523      return bestChild ?? child;
     524    }
     525
     526    public static Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     527      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
     528
     529      best = double.NaN;
     530      Encodings.PermutationEncoding.Permutation bestChild = null;
     531
     532      var invChild = new int[child.Length];
     533      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
     534
     535      var bestChange = double.NaN;
     536      do {
     537        int bestFrom = -1, bestTo = -1;
     538        bestChange = double.NaN;
     539        for (var j = 0; j < child.Length; j++) {
     540          var c = invChild[p2[j]];
     541          var n = invChild[p2.GetCircular(j + 1)];
     542          if (n - c == 1 || c == child.Length - 1 && n == 0) continue;
     543
     544          if (c < n) Shift(child, from: n, to: c + 1);
     545          else Shift(child, from: c, to: n);
     546          var moveF = eval(child, random);
     547          if (double.IsNaN(bestChange) || moveF < bestChange) {
     548            bestChange = moveF;
     549            bestFrom = c < n ? n : c;
     550            bestTo = c < n ? c + 1 : n;
     551          }
     552          // undo
     553          if (c < n) Shift(child, from: c + 1, to: n);
     554          else Shift(child, from: n, to: c);
     555        }
     556        if (!double.IsNaN(bestChange)) {
     557          Shift(child, bestFrom, bestTo);
     558          for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
     559          if (double.IsNaN(best) || bestChange < best) {
     560            best = bestChange;
     561            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
     562          }
     563        }
     564      } while (!double.IsNaN(bestChange));
     565
     566      if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
     567      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
     568      return bestChild;
     569    }
     570
     571    public static Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
     572      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
     573
     574      best = double.NaN;
     575      Encodings.PermutationEncoding.Permutation bestChild = null;
     576
     577      var invChild = new int[child.Length];
     578      var invP2 = new int[child.Length];
     579      for (var i = 0; i < child.Length; i++) {
     580        invChild[child[i]] = i;
     581        invP2[p2[i]] = i;
     582      }
     583
     584      var bestChange = double.NaN;
     585      var moveQueue = new Queue<Tuple<int, int>>();
     586      var undoStack = new Stack<Tuple<int, int>>();
     587      do {
     588        Queue<Tuple<int, int>> bestQueue = null;
     589        bestChange = double.NaN;
     590        //Log("{0}", string.Join(" ", child));
     591        for (var j = 0; j < p2.Length; j++) {
     592          if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
     593
     594          var a = invChild[p2[j]];
     595          var b = invChild[p2.GetCircular(j + 1)];
     596          if (a > b) { var h = a; a = b; b = h; }
     597          var aprev = a - 1;
     598          var bprev = b - 1;
     599          while (IsUndirectedEdge(invP2, child.GetCircular(aprev), child.GetCircular(aprev + 1))) {
     600            aprev--;
     601          }
     602          while (IsUndirectedEdge(invP2, child.GetCircular(bprev), child.GetCircular(bprev + 1))) {
     603            bprev--;
     604          }
     605          var bnext = b + 1;
     606          var anext = a + 1;
     607          while (IsUndirectedEdge(invP2, child.GetCircular(bnext - 1), child.GetCircular(bnext))) {
     608            bnext++;
     609          }
     610          while (IsUndirectedEdge(invP2, child.GetCircular(anext - 1), child.GetCircular(anext))) {
     611            anext++;
     612          }
     613          aprev++; bprev++; anext--; bnext--;
     614
     615          if (aprev < a && bnext > b) {
     616            if (aprev < 0) {
     617              moveQueue.Enqueue(Tuple.Create(a + 1, bnext));
     618              moveQueue.Enqueue(Tuple.Create(a + 1, a + 1 + (bnext - b)));
     619            } else {
     620              moveQueue.Enqueue(Tuple.Create(aprev, b - 1));
     621              moveQueue.Enqueue(Tuple.Create(b - 1 - (a - aprev), b - 1));
     622            }
     623          } else if (aprev < a && bnext == b && bprev == b) {
     624            moveQueue.Enqueue(Tuple.Create(a + 1, b));
     625          } else if (aprev < a && bprev < b) {
     626            moveQueue.Enqueue(Tuple.Create(a + 1, b));
     627          } else if (aprev == a && anext == a && bnext > b) {
     628            moveQueue.Enqueue(Tuple.Create(a, b - 1));
     629          } else if (aprev == a && anext == a && bnext == b && bprev == b) {
     630            moveQueue.Enqueue(Tuple.Create(a, b - 1));
     631          } else if (aprev == a && anext == a && bprev < b) {
     632            moveQueue.Enqueue(Tuple.Create(a + 1, b));
     633          } else if (anext > a && bnext > b) {
     634            moveQueue.Enqueue(Tuple.Create(a, b - 1));
     635          } else if (anext > a && bnext == b && bprev == b) {
     636            moveQueue.Enqueue(Tuple.Create(a, b - 1));
     637          } else /*if (anext > a && bprev < b)*/ {
     638            moveQueue.Enqueue(Tuple.Create(a, bprev - 1));
     639            moveQueue.Enqueue(Tuple.Create(bprev, b));
     640          }
     641
     642          while (moveQueue.Count > 0) {
     643            var m = moveQueue.Dequeue();
     644            Opt(child, m.Item1, m.Item2);
     645            undoStack.Push(m);
     646          }
     647          var moveF = eval(child, random);
     648          if (double.IsNaN(bestChange) || moveF < bestChange) {
     649            bestChange = moveF;
     650            bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
     651          }
     652          // undo
     653          while (undoStack.Count > 0) {
     654            var m = undoStack.Pop();
     655            Opt(child, m.Item1, m.Item2);
     656          }
     657        }
     658        if (!double.IsNaN(bestChange)) {
     659          while (bestQueue.Count > 0) {
     660            var m = bestQueue.Dequeue();
     661            //Log("Applying opt {0} {1}", m.Item1, m.Item2);
     662            //Log("{0}", string.Join(" ", child));
     663            Opt(child, m.Item1, m.Item2);
     664            //Log("{0}", string.Join(" ", child));
     665          }
     666          for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
     667          if (double.IsNaN(best) || bestChange < best) {
     668            best = bestChange;
     669            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
     670          }
     671        }
     672      } while (!double.IsNaN(bestChange));
     673
     674      //Log("{0}", string.Join(" ", p2));
     675      if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
     676      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
     677      return bestChild;
     678    }
     679
     680    private static bool IsUndirectedEdge(int[] invP, int a, int b) {
     681      var d = Math.Abs(invP[a] - invP[b]);
     682      return d == 1 || d == invP.Length - 1;
     683    }
     684
     685    private static void Move(Encodings.PermutationEncoding.Permutation child, int from, int to) {
     686      if (child.PermutationType == PermutationTypes.Absolute) {
     687        // swap
     688        Swap(child, from, to);
     689      } else if (child.PermutationType == PermutationTypes.RelativeDirected) {
     690        // shift
     691        Shift(child, from, to);
     692      } else if (child.PermutationType == PermutationTypes.RelativeUndirected) {
     693        // opt
     694        Opt(child, from, to);
     695      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", child.PermutationType));
     696    }
     697
     698    private static void Move(PermutationTypes type, bool[] arr, int from, int to) {
     699      switch (type) {
     700        case PermutationTypes.Absolute: {
     701            /*var h = arr[from];
     702            arr[from] = arr[to];
     703            arr[to] = h;*/
     704            arr[from] = false;
     705            arr[to] = false;
     706            break;
     707          }
     708        case PermutationTypes.RelativeDirected: {
     709            var original = (bool[])arr.Clone();
     710            var number = original[from];
     711            int i = 0;  // index in new permutation
     712            int j = 0;  // index in old permutation
     713            while (i < original.Length) {
     714              if (j == from) {
     715                j++;
     716              }
     717              if (i == to) {
     718                arr[i] = number;
     719                i++;
     720              }
     721              if ((i < original.Length) && (j < original.Length)) {
     722                arr[i] = original[j];
     723                i++;
     724                j++;
     725              }
     726            }
     727            break;
     728          }
     729        case PermutationTypes.RelativeUndirected: {
     730            if (from > to) {
     731              var hu = from;
     732              from = to;
     733              to = hu;
     734            }
     735            for (int i = 0; i <= (to - from) / 2; i++) {  // invert permutation between breakpoints
     736              var temp = arr[from + i];
     737              arr[from + i] = arr[to - i];
     738              arr[to - i] = temp;
     739            }
     740            break;
     741          }
     742        default:
     743          throw new ArgumentException(string.Format("Unknown permutation type {0}", type));
     744      }
     745    }
     746
     747    private static void Swap(Encodings.PermutationEncoding.Permutation child, int from, int to) {
     748      Swap2Manipulator.Apply(child, from, to);
     749    }
     750
     751    private static void Shift(Encodings.PermutationEncoding.Permutation child, int from, int to) {
     752      TranslocationManipulator.Apply(child, from, from, to);
     753    }
     754
     755    private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
     756      if (from > to) {
     757        var h = from;
     758        from = to;
     759        to = h;
     760      }
     761      InversionManipulator.Apply(child, from, to);
    261762    }
    262763  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPRContext.cs

    r14429 r14450  
    2020#endregion
    2121
     22using HeuristicLab.Algorithms.MemPR.Interfaces;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    24 using HeuristicLab.Encodings.BinaryVectorEncoding;
     25using HeuristicLab.Encodings.PermutationEncoding;
    2526using HeuristicLab.Optimization;
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2829
    29 namespace HeuristicLab.Algorithms.MemPR.Binary {
    30   [Item("BinaryMemPRContext", "MemPR context for binary encoded problems.")]
     30namespace HeuristicLab.Algorithms.MemPR.Permutation {
     31  [Item("MemPR Population Context (permutation)", "MemPR population context for permutation encoded problems.")]
    3132  [StorableClass]
    32   public sealed class BinaryMemPRContext : MemPRContext<BinaryVector, BinaryMemPRContext, BinarySingleSolutionMemPRContext> {
     33  public sealed class PermutationMemPRPopulationContext : MemPRPopulationContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
    3334
    3435    [StorableConstructor]
    35     private BinaryMemPRContext(bool deserializing) : base(deserializing) { }
    36     private BinaryMemPRContext(BinaryMemPRContext original, Cloner cloner)
     36    private PermutationMemPRPopulationContext(bool deserializing) : base(deserializing) { }
     37    private PermutationMemPRPopulationContext(PermutationMemPRPopulationContext original, Cloner cloner)
    3738      : base(original, cloner) { }
    38     public BinaryMemPRContext() : base("BinaryMemPRContext") { }
    39     public BinaryMemPRContext(string name) : base(name) { }
     39    public PermutationMemPRPopulationContext() : base("PermutationMemPRPopulationContext") { }
     40    public PermutationMemPRPopulationContext(string name) : base(name) { }
    4041
    4142    public override IDeepCloneable Clone(Cloner cloner) {
    42       return new BinaryMemPRContext(this, cloner);
     43      return new PermutationMemPRPopulationContext(this, cloner);
    4344    }
    4445
    45     public override BinarySingleSolutionMemPRContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<BinaryVector> solution) {
    46       return new BinarySingleSolutionMemPRContext(this, solution);
     46    public override PermutationMemPRSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> solution) {
     47      return new PermutationMemPRSolutionContext(this, solution);
    4748    }
    4849  }
    4950
    50   [Item("BinarySingleSolutionMemPRContext", "Single solution MemPR context for binary encoded problems.")]
     51  [Item("MemPR Solution Context (permutation)", "MemPR solution context for permutation encoded problems.")]
    5152  [StorableClass]
    52   public sealed class BinarySingleSolutionMemPRContext : SingleSolutionMemPRContext<BinaryVector, BinaryMemPRContext, BinarySingleSolutionMemPRContext>, IBinarySolutionSubspaceContext {
     53  public sealed class PermutationMemPRSolutionContext : MemPRSolutionContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext>, IPermutationSubspaceContext {
    5354
    5455    [Storable]
    55     private IValueParameter<BinarySolutionSubspace> subspace;
    56     public BinarySolutionSubspace Subspace {
     56    private IValueParameter<PermutationSolutionSubspace> subspace;
     57    public PermutationSolutionSubspace Subspace {
    5758      get { return subspace.Value; }
    5859    }
    59     ISolutionSubspace ISolutionSubspaceContext.Subspace {
     60    ISolutionSubspace<Encodings.PermutationEncoding.Permutation> ISolutionSubspaceContext<Encodings.PermutationEncoding.Permutation>.Subspace {
    6061      get { return Subspace; }
    6162    }
    6263
    6364    [StorableConstructor]
    64     private BinarySingleSolutionMemPRContext(bool deserializing) : base(deserializing) { }
    65     private BinarySingleSolutionMemPRContext(BinarySingleSolutionMemPRContext original, Cloner cloner)
     65    private PermutationMemPRSolutionContext(bool deserializing) : base(deserializing) { }
     66    private PermutationMemPRSolutionContext(PermutationMemPRSolutionContext original, Cloner cloner)
    6667      : base(original, cloner) {
    6768
    6869    }
    69     public BinarySingleSolutionMemPRContext(BinaryMemPRContext baseContext, ISingleObjectiveSolutionScope<BinaryVector> solution)
     70    public PermutationMemPRSolutionContext(PermutationMemPRPopulationContext baseContext, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> solution)
    7071      : base(baseContext, solution) {
    7172
    72       Parameters.Add(subspace = new ValueParameter<BinarySolutionSubspace>("Subspace", new BinarySolutionSubspace(null)));
     73      Parameters.Add(subspace = new ValueParameter<PermutationSolutionSubspace>("Subspace", new PermutationSolutionSubspace(null)));
    7374    }
    7475
    7576    public override IDeepCloneable Clone(Cloner cloner) {
    76       return new BinarySingleSolutionMemPRContext(this, cloner);
     77      return new PermutationMemPRSolutionContext(this, cloner);
    7778    }
    7879  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationSolutionSubspace.cs

    r14429 r14450  
    2020#endregion
    2121
     22using HeuristicLab.Algorithms.MemPR.Interfaces;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    24 using HeuristicLab.Optimization;
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2626
    27 namespace HeuristicLab.Algorithms.MemPR.Binary {
    28   [Item("Solution subspace (binary)", "")]
     27namespace HeuristicLab.Algorithms.MemPR.Permutation {
     28  [Item("Solution subspace (Permutation)", "")]
    2929  [StorableClass]
    30   public sealed class BinarySolutionSubspace : Item, ISolutionSubspace {
     30  public sealed class PermutationSolutionSubspace : Item, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> {
    3131
    3232    [Storable]
    33     private bool[] subspace;
    34     public bool[] Subspace { get { return subspace; } }
     33    private bool[,] subspace;
     34    public bool[,] Subspace { get { return subspace; } }
    3535
    3636    [StorableConstructor]
    37     private BinarySolutionSubspace(bool deserializing) : base(deserializing) { }
    38     private BinarySolutionSubspace(BinarySolutionSubspace original, Cloner cloner)
     37    private PermutationSolutionSubspace(bool deserializing) : base(deserializing) { }
     38    private PermutationSolutionSubspace(PermutationSolutionSubspace original, Cloner cloner)
    3939      : base(original, cloner) {
    40       subspace = (bool[])original.subspace.Clone();
     40      subspace = (bool[,])original.subspace.Clone();
    4141    }
    42     public BinarySolutionSubspace(bool[] subspace) {
     42    public PermutationSolutionSubspace(bool[,] subspace) {
    4343      this.subspace = subspace;
    4444    }
    4545
    4646    public override IDeepCloneable Clone(Cloner cloner) {
    47       return new BinarySolutionSubspace(this, cloner);
     47      return new PermutationSolutionSubspace(this, cloner);
    4848    }
    4949  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SolutionModel/Univariate/UnbiasedModelTrainer.cs

    r14429 r14450  
    2121
    2222using System.Linq;
     23using HeuristicLab.Algorithms.MemPR.Interfaces;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
    25 using HeuristicLab.Encodings.BinaryVectorEncoding;
     26using HeuristicLab.Encodings.PermutationEncoding;
    2627using HeuristicLab.Optimization;
    27 using HeuristicLab.Optimization.SolutionModel;
    2828using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2929
    30 namespace HeuristicLab.Encodings.Binary.SolutionModel.Univariate {
    31   [Item("Uniased Univariate Model Trainer (binary)", "")]
     30namespace HeuristicLab.Algorithms.MemPR.Permutation.SolutionModel.Univariate {
     31  [Item("Unbiased Univariate Model Trainer (Permutation)", "", ExcludeGenericTypeInfo = true)]
    3232  [StorableClass]
    33   public class UnbiasedModelTrainer<TContext> : UnbiasedModelTrainerOperator, IBinarySolutionModelTrainer<TContext>
    34     where TContext : ISolutionModelContext<BinaryVector>, IPopulationContext<BinaryVector>, IStochasticContext {
     33  public class UniasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext>
     34    where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation>,
     35    ISolutionModelContext<Encodings.PermutationEncoding.Permutation> {
    3536   
    3637    [StorableConstructor]
    37     protected UnbiasedModelTrainer(bool deserializing) : base(deserializing) { }
    38     protected UnbiasedModelTrainer(UnbiasedModelTrainer<TContext> original, Cloner cloner) : base(original, cloner) { }
    39     public UnbiasedModelTrainer() { }
     38    protected UniasedModelTrainer(bool deserializing) : base(deserializing) { }
     39    protected UniasedModelTrainer(UniasedModelTrainer<TContext> original, Cloner cloner) : base(original, cloner) { }
     40    public UniasedModelTrainer() {
     41      Name = ItemName;
     42      Description = ItemDescription;
     43    }
    4044
    4145    public override IDeepCloneable Clone(Cloner cloner) {
    42       return new UnbiasedModelTrainer<TContext>(this, cloner);
     46      return new UniasedModelTrainer<TContext>(this, cloner);
    4347    }
    4448
    4549    public void TrainModel(TContext context) {
    46       context.Model = UnivariateModel.CreateWithoutBias(context.Random, context.Population.Select(x => x.Solution));
     50      context.Model = Trainer.Train(context.Random, context.Population.Select(x => x.Solution).ToList(), context.Problem.Encoding.Length);
    4751    }
    4852  }
Note: See TracChangeset for help on using the changeset viewer.