Opened 11 months ago
Last modified 5 weeks 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: |
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 (27)
comment:1 Changed 11 months ago by abeham
comment:2 Changed 11 months ago by abeham
r14450: working on MemPR implementation
comment:3 Changed 11 months ago by abeham
- Status changed from new to accepted
comment:4 Changed 11 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 11 months 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 11 months ago by abeham
- Worked on MemPR algorithm for permutations
- Refactored TSP
comment:7 Changed 11 months ago by abeham
r14455: fixed bugs in tsp
comment:8 Changed 10 months 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 10 months ago by abeham
- Added MemPR for linear linkage (tabu walk still missing)
- Added graph coloring problem
comment:10 Changed 10 months 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 10 months 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 10 months ago by abeham
- Updated tabu walk for mempr (linear linkage)
comment:13 Changed 10 months ago by sraggl
- Merged with trunk to get new version of LinearLinkageEncoding
- Improved MoveGenerator
comment:14 Changed 10 months 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 10 months 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 10 months 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 9 months 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)
comment:18 Changed 9 months ago by abeham
r14551: refactored breeding, removed hillclimbing after breeding
comment:19 Changed 9 months 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 9 months 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 9 months ago by abeham
r14557: minor tweaks
comment:22 Changed 9 months ago by abeham
r14562: Updated branch to trunk
comment:23 Changed 9 months 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)
comment:24 Changed 9 months 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 8 months ago by abeham
r14680: disabled learning
- updated HeuristicLab.Data to trunk
comment:26 Changed 3 months ago by abeham
- Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.16
comment:27 Changed 5 weeks ago by abeham
- Version changed from 3.3.14 to branch
r14429: Made a new branch from ProblemRefactoring and removed ScopedBasicAlgorithm branch (which becomes MemPR branch)