Changeset 14466 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs
- Timestamp:
- 12/07/16 23:46:29 (8 years ago)
- Location:
- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage
- Files:
-
- 1 added
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs
r14456 r14466 25 25 using System.Threading; 26 26 using HeuristicLab.Algorithms.MemPR.Interfaces; 27 using HeuristicLab.Algorithms.MemPR.Util; 27 28 using HeuristicLab.Common; 28 29 using HeuristicLab.Core; 29 using HeuristicLab.Encodings. BinaryVectorEncoding;30 using HeuristicLab.Encodings.LinearLinkageEncoding; 30 31 using HeuristicLab.Optimization; 31 32 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; … … 33 34 using HeuristicLab.Random; 34 35 35 namespace HeuristicLab.Algorithms.MemPR. Binary{36 [Item("MemPR ( binary)", "MemPR implementation for binaryvectors.")]36 namespace HeuristicLab.Algorithms.MemPR.LinearLinkage { 37 [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")] 37 38 [StorableClass] 38 39 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)] 39 public class BinaryMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {40 public class LinearLinkageMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> { 40 41 private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05; 41 42 42 43 [StorableConstructor] 43 protected BinaryMemPR(bool deserializing) : base(deserializing) { }44 protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }45 public BinaryMemPR() {46 foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer< BinaryMemPRPopulationContext>>())44 protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { } 45 protected LinearLinkageMemPR(LinearLinkageMemPR original, Cloner cloner) : base(original, cloner) { } 46 public LinearLinkageMemPR() { 47 foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<LinearLinkageMemPRPopulationContext>>()) 47 48 SolutionModelTrainerParameter.ValidValues.Add(trainer); 48 49 49 foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch< BinaryMemPRSolutionContext>>()) {50 foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<LinearLinkageMemPRSolutionContext>>()) { 50 51 LocalSearchParameter.ValidValues.Add(localSearch); 51 52 } … … 53 54 54 55 public override IDeepCloneable Clone(Cloner cloner) { 55 return new BinaryMemPR(this, cloner); 56 } 57 58 protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) { 59 var len = a.Solution.Length; 60 var acode = a.Solution; 61 var bcode = b.Solution; 62 for (var i = 0; i < len; i++) 63 if (acode[i] != bcode[i]) return false; 64 return true; 65 } 66 67 protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) { 68 var len = a.Solution.Length; 69 var acode = a.Solution; 70 var bcode = b.Solution; 71 var hamming = 0; 72 for (var i = 0; i < len; i++) 73 if (acode[i] != bcode[i]) hamming++; 74 return hamming / (double)len; 75 } 76 77 protected override ISingleObjectiveSolutionScope<BinaryVector> ToScope(BinaryVector code, double fitness = double.NaN) { 78 var creator = Problem.SolutionCreator as IBinaryVectorCreator; 79 if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)"); 80 return new SingleObjectiveSolutionScope<BinaryVector>(code, creator.BinaryVectorParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) { 56 return new LinearLinkageMemPR(this, cloner); 57 } 58 59 protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) { 60 return a.Solution.SequenceEqual(b.Solution); 61 } 62 63 protected override double Dist(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) { 64 if (a.Solution.Length != b.Solution.Length) throw new ArgumentException("Comparing encodings of unequal length"); 65 var dist = 0; 66 for (var i = 0; i < a.Solution.Length; i++) { 67 if (a.Solution[i] != b.Solution[i]) dist++; 68 } 69 return dist / (double)a.Solution.Length; 70 } 71 72 protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> ToScope(Encodings.LinearLinkageEncoding.LinearLinkage code, double fitness = double.NaN) { 73 var creator = Problem.SolutionCreator as ILinearLinkageCreator; 74 if (creator == null) throw new InvalidOperationException("Can only solve linear linkage encoded problems with MemPR (linear linkage)"); 75 return new SingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) { 81 76 Parent = Context.Scope 82 77 }; 83 78 } 84 79 85 protected override ISolutionSubspace< BinaryVector> CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {80 protected override ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> CalculateSubspace(IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> solutions, bool inverse = false) { 86 81 var pop = solutions.ToList(); 87 82 var N = pop[0].Length; … … 94 89 } 95 90 } 96 return new BinarySolutionSubspace(subspace); 97 } 98 99 protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) { 100 var evaluations = 0; 101 var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null; 102 if (double.IsNaN(scope.Fitness)) { 103 Evaluate(scope, token); 104 evaluations++; 105 } 106 SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null; 107 var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone(); 108 var current = currentScope.Solution; 109 var N = current.Length; 110 var tabu = new Tuple<double, double>[N]; 111 for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness); 112 var subN = subset != null ? subset.Count(x => x) : N; 113 if (subN == 0) return 0; 114 var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray(); 115 116 var steps = 0; 117 var stepsUntilBestOfWalk = 0; 118 for (var iter = 0; iter < int.MaxValue; iter++) { 119 var allTabu = true; 120 var bestOfTheRestF = double.NaN; 121 int bestOfTheRest = -1; 122 var improved = false; 123 124 for (var i = 0; i < subN; i++) { 125 var idx = order[i]; 126 var before = currentScope.Fitness; 127 current[idx] = !current[idx]; 128 Evaluate(currentScope, token); 129 evaluations++; 130 var after = currentScope.Fitness; 131 132 if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) { 133 bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone(); 134 stepsUntilBestOfWalk = steps; 135 } 136 137 var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1; 138 var isTabu = !IsBetter(after, qualityToBeat); 139 if (!isTabu) allTabu = false; 140 141 if (IsBetter(after, before) && !isTabu) { 142 improved = true; 143 steps++; 144 tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after); 145 } else { // undo the move 146 if (!isTabu && IsBetter(after, bestOfTheRestF)) { 147 bestOfTheRest = idx; 148 bestOfTheRestF = after; 149 } 150 current[idx] = !current[idx]; 151 currentScope.Fitness = before; 152 } 153 if (evaluations >= maxEvals) break; 154 } 155 if (!allTabu && !improved) { 156 var better = currentScope.Fitness; 157 current[bestOfTheRest] = !current[bestOfTheRest]; 158 tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better); 159 currentScope.Fitness = bestOfTheRestF; 160 steps++; 161 } else if (allTabu) break; 162 if (evaluations >= maxEvals) break; 163 } 164 165 Context.IncrementEvaluatedSolutions(evaluations); 166 scope.Adopt(bestOfTheWalk ?? currentScope); 167 return stepsUntilBestOfWalk; 168 } 169 170 protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) { 171 var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone(); 172 offspring.Fitness = double.NaN; 173 var code = offspring.Solution; 174 var p2Code = p2.Solution; 175 var bp = 0; 176 var lastbp = 0; 177 for (var i = 0; i < code.Length; i++) { 178 if (bp % 2 == 1) { 179 code[i] = p2Code[i]; 180 } 181 if (Context.Random.Next(code.Length) < i - lastbp + 1) { 182 bp = (bp + 1) % 2; 183 lastbp = i; 184 } 185 } 186 return offspring; 187 } 188 189 protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) { 190 var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null; 191 offspring.Fitness = double.NaN; 192 var code = offspring.Solution; 193 for (var i = 0; i < code.Length; i++) { 194 if (subset != null && subset[i]) continue; 91 return new LinearLinkageSolutionSubspace(subspace); 92 } 93 94 protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) { 95 return 0; 96 } 97 98 protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Cross(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p2Scope, CancellationToken token) { 99 var p1 = p1Scope.Solution; 100 var p2 = p2Scope.Solution; 101 var transfered = new bool[p1.Length]; 102 var subspace = new bool[p1.Length]; 103 var lleeChild = new int[p1.Length]; 104 var lleep1 = p1.ToLLEe(); 105 var lleep2 = p2.ToLLEe(); 106 for (var i = p1.Length - 1; i >= 0; i--) { 107 // Step 1 108 subspace[i] = p1[i] != p2[i]; 109 var p1IsEnd = p1[i] == i; 110 var p2IsEnd = p2[i] == i; 111 if (p1IsEnd & p2IsEnd) { 112 transfered[i] = true; 113 } else if (p1IsEnd | p2IsEnd) { 114 transfered[i] = Context.Random.NextDouble() < 0.5; 115 } 116 lleeChild[i] = i; 117 118 // Step 2 119 if (transfered[i]) continue; 120 var end1 = lleep1[i]; 121 var end2 = lleep2[i]; 122 var containsEnd1 = transfered[end1]; 123 var containsEnd2 = transfered[end2]; 124 if (containsEnd1 & containsEnd2) { 125 if (Context.Random.NextDouble() < 0.5) { 126 lleeChild[i] = end1; 127 } else { 128 lleeChild[i] = end2; 129 } 130 } else if (containsEnd1) { 131 lleeChild[i] = end1; 132 } else if (containsEnd2) { 133 lleeChild[i] = end2; 134 } else { 135 if (Context.Random.NextDouble() < 0.5) { 136 lleeChild[i] = lleeChild[p1[i]]; 137 } else { 138 lleeChild[i] = lleeChild[p2[i]]; 139 } 140 } 141 } 142 var child = new Encodings.LinearLinkageEncoding.LinearLinkage(lleeChild.Length); 143 child.FromLLEe(lleeChild); 144 145 return ToScope(child); 146 } 147 148 protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> offspring, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) { 149 var lle = offspring.Solution; 150 var subset = subspace is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)subspace).Subspace : null; 151 for (var i = 0; i < lle.Length - 1; i++) { 152 if (subset == null || subset[i]) continue; // mutation works against crossover so aims to mutate noTouch points 195 153 if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) { 196 code[i] = !code[i]; 197 if (subset != null) subset[i] = true; 198 } 199 } 200 } 201 202 protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) { 154 subset[i] = true; 155 var index = Context.Random.Next(i, lle.Length); 156 for (var j = index - 1; j >= i; j--) { 157 if (lle[j] == index) index = j; 158 } 159 lle[i] = index; 160 index = i; 161 var idx2 = i; 162 for (var j = i - 1; j >= 0; j--) { 163 if (lle[j] == lle[index]) { 164 lle[j] = idx2; 165 index = idx2 = j; 166 } else if (lle[j] == idx2) idx2 = j; 167 } 168 } 169 } 170 } 171 172 protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Relink(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b, CancellationToken token) { 173 var maximization = Context.Problem.Maximization; 203 174 if (double.IsNaN(a.Fitness)) { 204 175 Evaluate(a, token); … … 209 180 Context.IncrementEvaluatedSolutions(1); 210 181 } 211 if (Context.Random.NextDouble() < 0.5) 212 return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true); 213 else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false); 214 } 215 216 protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) { 217 var evaluations = 0; 218 var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone(); 219 var child = childScope.Solution; 220 var better = betterScope.Solution; 221 var worse = worseScope.Solution; 222 ISingleObjectiveSolutionScope<BinaryVector> best = null; 223 var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness; 224 var bF = double.NaN; 225 var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray(); 226 while (true) { 227 var bestS = double.NaN; 228 var bestIdx = -1; 229 for (var i = 0; i < child.Length; i++) { 230 var idx = order[i]; 231 // either move from worse to better or move from better away from worse 232 if (fromWorseToBetter && child[idx] == better[idx] || 233 !fromWorseToBetter && child[idx] != worse[idx]) continue; 234 child[idx] = !child[idx]; // move 235 Evaluate(childScope, token); 236 evaluations++; 237 var s = childScope.Fitness; 238 childScope.Fitness = cF; 239 child[idx] = !child[idx]; // undo move 240 if (IsBetter(s, cF)) { 241 bestS = s; 242 bestIdx = idx; 243 break; // first-improvement 244 } 245 if (double.IsNaN(bestS) || IsBetter(s, bestS)) { 246 // least-degrading 247 bestS = s; 248 bestIdx = idx; 249 } 250 } 251 if (bestIdx < 0) break; 252 child[bestIdx] = !child[bestIdx]; 253 cF = bestS; 254 childScope.Fitness = cF; 255 if (IsBetter(cF, bF)) { 256 bF = cF; 257 best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone(); 258 } 259 } 260 Context.IncrementEvaluatedSolutions(evaluations); 261 return best ?? childScope; 182 var child = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)a.Clone(); 183 var cgroups = child.Solution.GetGroups().Select(x => new HashSet<int>(x)).ToList(); 184 var g2 = b.Solution.GetGroups().ToList(); 185 var order = Enumerable.Range(0, g2.Count).Shuffle(Context.Random).ToList(); 186 ISingleObjectiveSolutionScope <Encodings.LinearLinkageEncoding.LinearLinkage> bestChild = null; 187 for (var j = 0; j < g2.Count; j++) { 188 var g = g2[order[j]]; 189 var changed = false; 190 for (var k = j; k < cgroups.Count; k++) { 191 foreach (var f in g) if (cgroups[k].Remove(f)) changed = true; 192 if (cgroups[k].Count == 0) { 193 cgroups.RemoveAt(k); 194 k--; 195 } 196 } 197 cgroups.Insert(0, new HashSet<int>(g)); 198 child.Solution.SetGroups(cgroups); 199 if (changed) { 200 Evaluate(child, token); 201 if (bestChild == null || FitnessComparer.IsBetter(maximization, child.Fitness, bestChild.Fitness)) { 202 bestChild = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)child.Clone(); 203 } 204 } 205 }; 206 return bestChild; 262 207 } 263 208 }
Note: See TracChangeset
for help on using the changeset viewer.