Implementation of MemPR

[abeham]

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).

[abeham]

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

[abeham]

r14450: working on MemPR implementation

[abeham]

Merge to trunk separately!

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

[abeham]

r14453:

• 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

[abeham]

r14454:

• Worked on MemPR algorithm for permutations
• Refactored TSP

[abeham]

r14455: fixed bugs in tsp

[abeham]

r14456:

• 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

[abeham]

r14466:

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

[abeham]

r14471:

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

[abeham]

r14477:

• 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

[abeham]

r14484:

• Updated tabu walk for mempr (linear linkage)

[sraggl]

r14487:

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

[abeham]

r14492:

• 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

[abeham]

r14496:

• 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

[abeham]

r14544:

• 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

[abeham]

r14550:

• 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)

[abeham]

r14551: refactored breeding, removed hillclimbing after breeding

[abeham]

r14552:

• 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

[abeham]

r14556:

• 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

[abeham]

r14557: minor tweaks

[abeham]

r14562: Updated branch to trunk

[abeham]

r14563:

• 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)

[abeham]

r14573:

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

[abeham]

r14680: disabled learning

• updated HeuristicLab.Data to trunk

[abeham]

r16105: renamed branch