Opened 8 months ago

Last modified 4 months ago

#2701 accepted feature request

Implementation of MemPR

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.15
Component: Algorithms Version: 3.3.14
Keywords: Cc:

Description

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 (25)

comment:1 Changed 7 months ago by abeham

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

comment:2 Changed 7 months ago by abeham

r14450: working on MemPR implementation

comment:3 Changed 7 months ago by abeham

  • Status changed from new to accepted

comment:4 Changed 7 months ago by abeham

Merge to trunk separately!

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

comment:5 Changed 7 months ago by 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

comment:6 Changed 7 months ago by abeham

r14454:

  • Worked on MemPR algorithm for permutations
  • Refactored TSP

comment:7 Changed 7 months ago by abeham

r14455: fixed bugs in tsp

comment:8 Changed 7 months ago by 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

comment:9 Changed 7 months ago by abeham

r14466:

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

comment:10 Changed 7 months ago by abeham

r14471:

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

comment:11 Changed 7 months ago by 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

comment:12 Changed 7 months ago by abeham

r14484:

  • Updated tabu walk for mempr (linear linkage)

comment:13 Changed 7 months ago by sraggl

r14487:

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

comment:14 Changed 7 months ago by 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

comment:15 Changed 6 months ago by 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

comment:16 Changed 6 months ago by 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

comment:17 Changed 6 months ago by 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)
Last edited 6 months ago by abeham (previous) (diff)

comment:18 Changed 6 months ago by abeham

r14551: refactored breeding, removed hillclimbing after breeding

comment:19 Changed 6 months ago by 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

comment:20 Changed 6 months ago by 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

comment:21 Changed 6 months ago by abeham

r14557: minor tweaks

comment:22 Changed 6 months ago by abeham

r14562: Updated branch to trunk

comment:23 Changed 6 months ago by 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)
Last edited 6 months ago by abeham (previous) (diff)

comment:24 Changed 5 months ago by abeham

r14573:

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

comment:25 Changed 4 months ago by abeham

r14680: disabled learning

  • updated HeuristicLab.Data to trunk
Note: See TracTickets for help on using tickets.