search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
35 stars 16 forks source link

Implementation of MemPR #2701

Open HeuristicLab-Trac-Bot opened 7 years ago

HeuristicLab-Trac-Bot commented 7 years ago

Issue migrated from trac ticket # 2701

milestone: HeuristicLab 3.3.17 | component: Algorithms | priority: medium

2016-11-11 14:24:04: @abeham created the issue

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

HeuristicLab-Trac-Bot commented 7 years ago

2016-11-29 15:51:53: @abeham commented

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

HeuristicLab-Trac-Bot commented 7 years ago

2016-12-03 00:32:22: @abeham commented

r14450: working on MemPR implementation

HeuristicLab-Trac-Bot commented 7 years ago

2016-12-03 00:32:27: @abeham changed status from new to accepted

HeuristicLab-Trac-Bot commented 7 years ago

2016-12-03 00:33:55: @abeham commented

Merge to trunk separately!

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

HeuristicLab-Trac-Bot commented 7 years ago

2016-12-05 12:28:10: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-05 16:06:41: @abeham commented

r14454:

  • Worked on MemPR algorithm for permutations
  • Refactored TSP
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-05 16:09:17: @abeham commented

r14455: fixed bugs in tsp

HeuristicLab-Trac-Bot commented 7 years ago

2016-12-06 15:07:59: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-07 23:46:55: @abeham commented

r14466:

  • Added MemPR for linear linkage (tabu walk still missing)
  • Added graph coloring problem
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-09 15:56:44: @abeham commented

r14471:

  • Updated GraphColoringProblem and Problems.Instances
    • Added new fitness function from literature
    • Added DIMACS benchmark instances
  • Updated LinearLinkageEncoding
    • Added HammingSimilarityCalculator
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-12 14:15:28: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-13 08:04:03: @abeham commented

r14484:

  • Updated tabu walk for mempr (linear linkage)
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-14 10:19:16: @raggy-rs commented

r14487:

  • Merged with trunk to get new version of LinearLinkageEncoding
  • Improved MoveGenerator
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-14 20:46:08: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2016-12-16 17:10:30: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2017-01-05 00:32:52: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2017-01-05 17:50:20: @abeham commented

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)
HeuristicLab-Trac-Bot commented 7 years ago

2017-01-05 17:50:20: @abeham

HeuristicLab-Trac-Bot commented 7 years ago

2017-01-08 22:16:47: @abeham commented

r14551: refactored breeding, removed hillclimbing after breeding

HeuristicLab-Trac-Bot commented 7 years ago

2017-01-09 00:36:28: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2017-01-11 01:54:07: @abeham commented

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
HeuristicLab-Trac-Bot commented 7 years ago

2017-01-11 02:18:28: @abeham commented

r14557: minor tweaks

HeuristicLab-Trac-Bot commented 7 years ago

2017-01-13 12:55:21: @abeham commented

r14562: Updated branch to trunk

HeuristicLab-Trac-Bot commented 7 years ago

2017-01-13 18:18:47: @abeham commented

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)
HeuristicLab-Trac-Bot commented 7 years ago

2017-01-13 18:18:47: @abeham

HeuristicLab-Trac-Bot commented 7 years ago

2017-01-15 09:58:16: @abeham commented

r14573:

  • changed adaptive walk performance model to relative
  • added ConfidenceConstantModel for regression
  • using constant model as fallback to GPR
  • reorganized code
HeuristicLab-Trac-Bot commented 7 years ago

2017-02-17 13:01:05: @abeham commented

r14680: disabled learning

  • updated HeuristicLab.Data to trunk
HeuristicLab-Trac-Bot commented 7 years ago

2017-07-06 01:34:34: @abeham changed milestone from HeuristicLab 3.3.15 to HeuristicLab 3.3.16

HeuristicLab-Trac-Bot commented 6 years ago

2018-08-30 09:53:46: @abeham commented

r16105: renamed branch

HeuristicLab-Trac-Bot commented 5 years ago

2019-04-12 13:53:00: @abeham changed milestone from HeuristicLab 3.3.16 to HeuristicLab 3.3.17

HeuristicLab-Trac-Bot commented 5 years ago

2019-08-07 06:02:54: @abeham changed status from accepted to assigned