Opened 2 years ago

Last modified 6 months ago

#2701 accepted feature request

Implementation of MemPR

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.16
Component: Algorithms Version: branch
Keywords: Cc:


MemPR is short for MEMetic Path Relinking algorithm. It is a hyper-heuristic that combines various heuristics (crossover, mutation, local search, path relinking, sampling, etc.) in a population-based method with diversity handling. It aims to provide good anytime behavior which can achieve good solutions quickly. MemPR is specific to various encodings, but independent of any concrete problem definition.

MemPR will be available for binary-, LLE-, and permutation-based problems (absolute, relativedirected, and relativeundirected).

Change History (28)

comment:1 Changed 2 years ago by abeham

r14429: Made a new branch from ProblemRefactoring and removed ScopedBasicAlgorithm branch (which becomes MemPR branch)

comment:2 Changed 2 years ago by abeham

r14450: working on MemPR implementation

comment:3 Changed 2 years ago by abeham

  • Status changed from new to accepted

comment:4 Changed 2 years ago by abeham

Merge to trunk separately!

r14451: Added Basic QAP problem and option to hide generic type in the ItemAttribute

comment:5 Changed 2 years ago by abeham


  • Worked on MemPR algorithm for permutations
    • Made Evaluate() method mostly thread-safe and moved evaluated solutions counting to caller
  • Removed TSP specific similarity calculator (it is actually not specific to the TSP) and added it to the permutation encoding as HammingSimilarityCalculator
  • Fixed bug in qap basicproblem

comment:6 Changed 2 years ago by abeham


  • Worked on MemPR algorithm for permutations
  • Refactored TSP

comment:7 Changed 2 years ago by abeham

r14455: fixed bugs in tsp

comment:8 Changed 2 years ago by abeham


  • Using evaluated solutions from HC as max evaluations for tabu walking in MemPR
  • Fixed some bugs in MemPR (permutation) regarding subspace calculation (true means okay, false means no)
  • Fixed bug in TSP

comment:9 Changed 2 years ago by abeham


  • Added MemPR for linear linkage (tabu walk still missing)
  • Added graph coloring problem

comment:10 Changed 2 years ago by abeham


  • Updated GraphColoringProblem and Problems.Instances
    • Added new fitness function from literature
    • Added DIMACS benchmark instances
  • Updated LinearLinkageEncoding
    • Added HammingSimilarityCalculator

comment:11 Changed 2 years ago by abeham


  • 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

comment:12 Changed 2 years ago by abeham


  • Updated tabu walk for mempr (linear linkage)

comment:13 Changed 2 years ago by sraggl


  • Merged with trunk to get new version of LinearLinkageEncoding
  • Improved MoveGenerator

comment:14 Changed 2 years ago by abeham


  • Updated LLE encoding
    • Made folder for version 3.4
    • Added conversion from and to LLE-b representation (back-links)
    • Updated moves and movegenerator to replace bidirectionaldictionary with LLE-b representation
  • Updated MemPR (linear linkage)
    • Updated tabu walk
  • Added test for conversion between LLE-e and LLE and LLE-b and LLE
  • Updated test for move apply/undo and added test for applying in sequence

comment:15 Changed 2 years ago by abeham


  • Reusing similiarty calculator in BinaryMemPR
  • Fixing distance calculation for linear linkage and LinearLinkageMemPR
  • Small changes to base algorithm
  • Added biased model trainer for permutation (rank and fitness)
  • Fixing best known quality calculation for GCP

comment:16 Changed 2 years ago by abeham


  • 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

comment:17 Changed 2 years ago by abeham


  • Added BinaryVectorEqualityComparer (identical to the one in the P3 plugin) to binaryvector plugin
  • Added delinking for absolute coded permutations
  • Some tweaks (reintroduced hillclimbing after breeding and relinking in sub-spaces -> very important for permtuation-based problems; always sample at least one solution so that hillclimber can go on it in case no other heuristic achieved a new solution, tuned adaptive walk for binary problems)
Last edited 2 years ago by abeham (previous) (diff)

comment:18 Changed 2 years ago by abeham

r14551: refactored breeding, removed hillclimbing after breeding

comment:19 Changed 2 years ago by abeham


  • Added alternating bits binary test Problem
  • Refactored MemPR to work with programmable problem in current trunk
  • fixed a bug in permutation MemPR when crossover doesn't assign an offspring

comment:20 Changed 2 years ago by abeham


  • fixed bug with breeding
  • fixed permutation sub-space hillclimber
  • improved speed of inversion by calling Array.Reverse(int, int) instead of using a for-loop
  • added delinking for relative-undirected permutations

comment:21 Changed 2 years ago by abeham

r14557: minor tweaks

comment:22 Changed 2 years ago by abeham

r14562: Updated branch to trunk

comment:23 Changed 2 years ago by abeham


  • Tagged unbiased models with property
  • Changed default configuration
  • Added solution distance to breeding, relinking and delinking performance models
  • Changed sampling model to base prediction on average distance in genotype space
  • Changed target for hillclimber and relinking to relative (quality improvement)
  • changed breeding to count cache hits per crossover
  • collect performance data for breeding and relinking before a potential hillclimb (still unsure if this is good)
Last edited 2 years ago by abeham (previous) (diff)

comment:24 Changed 2 years ago by abeham


  • changed adaptive walk performance model to relative
  • added ConfidenceConstantModel for regression
  • using constant model as fallback to GPR
  • reorganized code

comment:25 Changed 2 years ago by abeham

r14680: disabled learning

  • updated HeuristicLab.Data to trunk

comment:26 Changed 20 months ago by abeham

  • Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.16

comment:27 Changed 18 months ago by abeham

  • Version changed from 3.3.14 to branch

comment:28 Changed 6 months ago by abeham

r16105: renamed branch

Note: See TracTickets for help on using tickets.