Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/05/17 00:32:43 (7 years ago)
Author:
abeham
Message:

#2701:

  • LLE: Added equality comparer
  • MemPR:
    • Added GPR to learn about heuristic performance
    • Changed Breeding to do more exhaustive search on crossover
    • Added Delinking separately to Relinking
    • Rewrote d/relinking for LLE
    • Reduce usage of local search
    • Renamed TabuWalk to AdaptiveWalk
    • Rewrote adaptive walk for binary problems
    • Renamed LLE namespace to Grouping to avoid namespace clashes
File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

    r14496 r14544  
    3838  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    3939  public class BinaryMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {
    40     private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    41    
    4240    [StorableConstructor]
    4341    protected BinaryMemPR(bool deserializing) : base(deserializing) { }
    … …  
    9189    }
    9290
    93     protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
     91    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    9492      var evaluations = 0;
    9593      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    … …  
    102100      var current = currentScope.Solution;
    103101      var N = current.Length;
    104       var tabu = new Tuple<double, double>[N];
    105       for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
     102
    106103      var subN = subset != null ? subset.Count(x => x) : N;
    107       if (subN == 0) return 0;
     104      if (subN == 0) return;
    108105      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    109106
    110       var steps = 0;
    111       var stepsUntilBestOfWalk = 0;
     107      var max = Context.Population.Max(x => x.Fitness);
     108      var min = Context.Population.Min(x => x.Fitness);
     109      var range = (max - min);
     110      if (range.IsAlmost(0)) range = Math.Abs(max * 0.05);
     111      //else range += range * 0.05;
     112      if (range.IsAlmost(0)) { // because min = max = 0
     113        Context.IncrementEvaluatedSolutions(evaluations);
     114        return;
     115      }
     116
     117      //var upperBound = Problem.Maximization ? min - range : max + range;
     118      //var lowerBound = Problem.Maximization ? max : min;
     119      var temp = 1.0;
    112120      for (var iter = 0; iter < int.MaxValue; iter++) {
    113         var allTabu = true;
    114         var bestOfTheRestF = double.NaN;
    115         int bestOfTheRest = -1;
    116         var improved = false;
     121        var moved = false;
    117122
    118123        for (var i = 0; i < subN; i++) {
    … …  
    124129          var after = currentScope.Fitness;
    125130
    126           if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
     131          if (Context.IsBetter(after, before) && (bestOfTheWalk == null || Context.IsBetter(after, bestOfTheWalk.Fitness))) {
    127132            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
    128             stepsUntilBestOfWalk = steps;
    129           }
    130 
    131           var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1;
    132           var isTabu = !IsBetter(after, qualityToBeat);
    133           if (!isTabu) allTabu = false;
    134 
    135           if (IsBetter(after, before) && !isTabu) {
    136             improved = true;
    137             steps++;
    138             tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
    139           } else { // undo the move
    140             if (!isTabu && IsBetter(after, bestOfTheRestF)) {
    141               bestOfTheRest = idx;
    142               bestOfTheRestF = after;
     133          }
     134          var diff = Problem.Maximization ? after - before : before - after;
     135          if (diff > 0) moved = true;
     136          else {
     137            var prob = Math.Exp(temp * diff / range);
     138            if (Context.Random.NextDouble() >= prob) {
     139              // the move is not good enough -> undo the move
     140              current[idx] = !current[idx];
     141              currentScope.Fitness = before;
    143142            }
    144             current[idx] = !current[idx];
    145             currentScope.Fitness = before;
    146           }
     143          }
     144          temp += 100.0 / maxEvals;
    147145          if (evaluations >= maxEvals) break;
    148146        }
    149         if (!allTabu && !improved) {
    150           var better = currentScope.Fitness;
    151           current[bestOfTheRest] = !current[bestOfTheRest];
    152           tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
    153           currentScope.Fitness = bestOfTheRestF;
    154           steps++;
    155         } else if (allTabu) break;
     147        if (!moved) break;
    156148        if (evaluations >= maxEvals) break;
    157149      }
    … …  
    159151      Context.IncrementEvaluatedSolutions(evaluations);
    160152      scope.Adopt(bestOfTheWalk ?? currentScope);
    161       return stepsUntilBestOfWalk;
    162     }
    163 
    164     protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
    165       var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone();
    166       offspring.Fitness = double.NaN;
    167       var code = offspring.Solution;
    168       var p2Code = p2.Solution;
    169       var bp = 0;
    170       var lastbp = 0;
    171       for (var i = 0; i < code.Length; i++) {
    172         if (bp % 2 == 1) {
    173           code[i] = p2Code[i];
    174         }
    175         if (Context.Random.Next(code.Length) < i - lastbp + 1) {
    176           bp = (bp + 1) % 2;
    177           lastbp = i;
    178         }
    179       }
     153    }
     154
     155    protected override ISingleObjectiveSolutionScope<BinaryVector> Breed(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
     156      var evaluations = 0;
     157      var N = p1.Solution.Length;
     158      if (double.IsNaN(p1.Fitness)) {
     159        Evaluate(p1, token);
     160        evaluations++;
     161      }
     162      if (double.IsNaN(p2.Fitness)) {
     163        Evaluate(p2, token);
     164        evaluations++;
     165      }
     166      var better = Problem.Maximization ? Math.Max(p1.Fitness, p2.Fitness)
     167                                        : Math.Min(p1.Fitness, p2.Fitness);
     168
     169      var offspring = ToScope(null);
     170      var probe = ToScope(new BinaryVector(N));
     171      var order = Enumerable.Range(0, N - 1).Shuffle(Context.Random).ToList();
     172      for (var x = 0; x < N - 1; x++) {
     173        var b = order[x];
     174        if (p1.Solution[b] == p2.Solution[b]) continue;
     175        for (var i = 0; i <= b; i++)
     176          probe.Solution[i] = p1.Solution[i];
     177        for (var i = b + 1; i < probe.Solution.Length; i++)
     178          probe.Solution[i] = p2.Solution[i];
     179
     180        Evaluate(probe, token);
     181        evaluations++;
     182        if (Context.IsBetter(probe, offspring)) {
     183          if (Context.IsBetter(probe.Fitness, better)) {
     184            Context.IncrementEvaluatedSolutions(evaluations);
     185            return probe;
     186          }
     187          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
     188        }
     189      }
     190
     191      while (evaluations < Context.LocalSearchEvaluations) {
     192        probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
     193        Evaluate(probe, token);
     194        evaluations++;
     195        if (Context.IsBetter(probe, offspring)) {
     196          if (Context.IsBetter(probe.Fitness, better)) {
     197            Context.IncrementEvaluatedSolutions(evaluations);
     198            return probe;
     199          }
     200          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
     201        }
     202      }
     203      Context.IncrementEvaluatedSolutions(evaluations);
    180204      return offspring;
    181205    }
    182206
    183     protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    184       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    185       offspring.Fitness = double.NaN;
    186       var code = offspring.Solution;
    187       for (var i = 0; i < code.Length; i++) {
    188         if (subset != null && subset[i]) continue;
    189         if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {
    190           code[i] = !code[i];
    191           if (subset != null) subset[i] = true;
    192         }
    193       }
    194     }
    195 
    196     protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
     207    protected override ISingleObjectiveSolutionScope<BinaryVector> Link(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token, bool delink = false) {
     208      var evaluations = 0;
    197209      if (double.IsNaN(a.Fitness)) {
    198210        Evaluate(a, token);
    199         Context.IncrementEvaluatedSolutions(1);
     211        evaluations++;
    200212      }
    201213      if (double.IsNaN(b.Fitness)) {
    202214        Evaluate(b, token);
    203         Context.IncrementEvaluatedSolutions(1);
    204       }
    205       if (Context.Random.NextDouble() < 0.5)
    206         return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
    207       else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);
    208     }
    209 
    210     protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
    211       var evaluations = 0;
    212       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
     215        evaluations++;
     216      }
     217
     218      var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)a.Clone();
    213219      var child = childScope.Solution;
    214       var better = betterScope.Solution;
    215       var worse = worseScope.Solution;
    216220      ISingleObjectiveSolutionScope<BinaryVector> best = null;
    217       var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness;
     221      var cF = a.Fitness;
    218222      var bF = double.NaN;
    219       var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray();
     223      var order = Enumerable.Range(0, child.Length)
     224        .Where(x => !delink && child[x] != b.Solution[x] || delink && child[x] == b.Solution[x])
     225        .Shuffle(Context.Random).ToList();
     226      if (order.Count == 0) return childScope;
     227
    220228      while (true) {
    221229        var bestS = double.NaN;
    222         var bestIdx = -1;
    223         for (var i = 0; i < child.Length; i++) {
     230        var bestI = -1;
     231        for (var i = 0; i < order.Count; i++) {
    224232          var idx = order[i];
    225           // either move from worse to better or move from better away from worse
    226           if (fromWorseToBetter && child[idx] == better[idx] ||
    227             !fromWorseToBetter && child[idx] != worse[idx]) continue;
    228233          child[idx] = !child[idx]; // move
    229234          Evaluate(childScope, token);
    … …  
    232237          childScope.Fitness = cF;
    233238          child[idx] = !child[idx]; // undo move
    234           if (IsBetter(s, cF)) {
     239          if (Context.IsBetter(s, cF)) {
    235240            bestS = s;
    236             bestIdx = idx;
     241            bestI = i;
    237242            break; // first-improvement
    238243          }
    239           if (double.IsNaN(bestS) || IsBetter(s, bestS)) {
     244          if (Context.IsBetter(s, bestS)) {
    240245            // least-degrading
    241246            bestS = s;
    242             bestIdx = idx;
    243           }
    244         }
    245         if (bestIdx < 0) break;
    246         child[bestIdx] = !child[bestIdx];
     247            bestI = i;
     248          }
     249        }
     250        child[order[bestI]] = !child[order[bestI]];
     251        order.RemoveAt(bestI);
    247252        cF = bestS;
    248253        childScope.Fitness = cF;
    249         if (IsBetter(cF, bF)) {
     254        if (Context.IsBetter(cF, bF)) {
    250255          bF = cF;
    251256          best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
    252257        }
     258        if (order.Count == 0) break;
    253259      }
    254260      Context.IncrementEvaluatedSolutions(evaluations);
Note: See TracChangeset for help on using the changeset viewer.