- Timestamp:
- 01/09/17 00:36:20 (8 years ago)
- Location:
- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage
- Files:
-
- 5 edited
-
LinearLinkageMemPR.cs (modified) (8 diffs)
-
LinearLinkageMemPRContext.cs (modified) (3 diffs)
-
LocalSearch/ExhaustiveSubspace.cs (modified) (3 diffs)
-
LocalSearch/StaticAPI/ExhaustiveLocalSearch.cs (modified) (3 diffs)
-
SolutionModel/Univariate/UnbiasedModelTrainer.cs (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs
r14551 r14552 37 37 [StorableClass] 38 38 [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)] 39 public class LinearLinkageMemPR : MemPRAlgorithm< SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {39 public class LinearLinkageMemPR : MemPRAlgorithm<ISingleObjectiveHeuristicOptimizationProblem, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> { 40 40 [StorableConstructor] 41 41 protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { } … … 69 69 } 70 70 71 protected override ISingleObjectiveSolutionScope<LinearLinkage> ToScope(LinearLinkage code, double fitness = double.NaN) {72 var creator = Problem.SolutionCreator as ILinearLinkageCreator;73 if (creator == null) throw new InvalidOperationException("Can only solve linear linkage encoded problems with MemPR (linear linkage)");74 return new SingleObjectiveSolutionScope<LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {75 Parent = Context.Scope76 };77 }78 79 71 protected override ISolutionSubspace<LinearLinkage> CalculateSubspace(IEnumerable<LinearLinkage> solutions, bool inverse = false) { 80 72 var pop = solutions.ToList(); … … 95 87 int maxEvals, CancellationToken token, 96 88 ISolutionSubspace<LinearLinkage> sub_space = null) { 97 var maximization = Context. Problem.Maximization;89 var maximization = Context.Maximization; 98 90 var subspace = sub_space is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)sub_space).Subspace : null; 99 91 var evaluations = 0; 100 92 var quality = scope.Fitness; 101 93 if (double.IsNaN(quality)) { 102 Evaluate(scope, token);94 Context.Evaluate(scope, token); 103 95 quality = scope.Fitness; 104 96 evaluations++; … … 168 160 move.Apply(current); 169 161 var qualityToRestore = tabu[i, current[i]]; // current[i] is new next 170 Evaluate(currentScope, token);162 Context.Evaluate(currentScope, token); 171 163 evaluations++; 172 164 var moveF = currentScope.Fitness; … … 255 247 var cachehits = 0; 256 248 var evaluations = 0; 257 var probe = ToScope((LinearLinkage)p1.Solution.Clone());249 var probe = Context.ToScope((LinearLinkage)p1.Solution.Clone()); 258 250 ISingleObjectiveSolutionScope<LinearLinkage> offspring = null; 259 251 while (evaluations < p1.Solution.Length) { … … 268 260 continue; 269 261 } 270 Evaluate(probe, token);262 Context.Evaluate(probe, token); 271 263 evaluations++; 272 264 cache.Add(c); … … 283 275 protected override ISingleObjectiveSolutionScope<LinearLinkage> Link(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b, CancellationToken token, bool delink = false) { 284 276 var evaluations = 0; 285 if (double.IsNaN(a.Fitness)) {286 Evaluate(a, token);287 evaluations++;288 }289 if (double.IsNaN(b.Fitness)) {290 Evaluate(b, token);291 evaluations++;292 }293 294 277 var probe = (ISingleObjectiveSolutionScope<LinearLinkage>)a.Clone(); 295 278 ISingleObjectiveSolutionScope<LinearLinkage> best = null; … … 306 289 if (delink && distAfter > distBefore || !delink && distAfter < distBefore) { 307 290 var beforeQ = probe.Fitness; 308 Evaluate(probe, token);291 Context.Evaluate(probe, token); 309 292 evaluations++; 310 293 var q = probe.Fitness; -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPRContext.cs
r14544 r14552 20 20 #endregion 21 21 22 using System; 23 using System.Runtime.Remoting.Contexts; 22 24 using HeuristicLab.Algorithms.MemPR.Interfaces; 23 25 using HeuristicLab.Common; … … 31 33 [Item("MemPR Population Context (linear linkage)", "MemPR population context for linear linkage encoded problems.")] 32 34 [StorableClass] 33 public sealed class LinearLinkageMemPRPopulationContext : MemPRPopulationContext< SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {35 public sealed class LinearLinkageMemPRPopulationContext : MemPRPopulationContext<ISingleObjectiveHeuristicOptimizationProblem, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> { 34 36 35 37 [StorableConstructor] … … 47 49 return new LinearLinkageMemPRSolutionContext(this, solution); 48 50 } 51 52 public override ISingleObjectiveSolutionScope<LinearLinkage> ToScope(LinearLinkage code, double fitness = double.NaN) { 53 var creator = Problem.SolutionCreator as ILinearLinkageCreator; 54 if (creator == null) throw new InvalidOperationException("Can only solve linear linkage encoded problems with MemPR (linear linkage)"); 55 return new SingleObjectiveSolutionScope<LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) { 56 Parent = Scope 57 }; 58 } 49 59 } 50 60 51 61 [Item("MemPR Solution Context (linear linkage)", "MemPR solution context for linear linkage encoded problems.")] 52 62 [StorableClass] 53 public sealed class LinearLinkageMemPRSolutionContext : MemPRSolutionContext< SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext>, ILinearLinkageSubspaceContext {63 public sealed class LinearLinkageMemPRSolutionContext : MemPRSolutionContext<ISingleObjectiveHeuristicOptimizationProblem, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext>, ILinearLinkageSubspaceContext { 54 64 55 65 [Storable] -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LocalSearch/ExhaustiveSubspace.cs
r14544 r14552 22 22 using System.Threading; 23 23 using HeuristicLab.Algorithms.MemPR.Interfaces; 24 using HeuristicLab.Algorithms.MemPR.Util;25 24 using HeuristicLab.Common; 26 25 using HeuristicLab.Core; … … 33 32 [StorableClass] 34 33 public class ExhaustiveSubspace<TContext> : NamedItem, ILocalSearch<TContext> 35 where TContext : ISingleSolutionHeuristicAlgorithmContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage>, ILinearLinkageSubspaceContext { 34 where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, LinearLinkage>, 35 ILinearLinkageSubspaceContext, IEvaluationServiceContext<LinearLinkage> { 36 36 37 37 [StorableConstructor] … … 48 48 49 49 public void Optimize(TContext context) { 50 var evalWrapper = new EvaluationWrapper<LinearLinkage>(context.Problem, context.Solution);51 50 var quality = context.Solution.Fitness; 52 51 try { 53 52 var result = ExhaustiveLocalSearch.Optimize(context.Random, context.Solution.Solution, ref quality, 54 context. Problem.Maximization, evalWrapper.Evaluate, CancellationToken.None, context.Subspace.Subspace);53 context.Maximization, context.Evaluate, CancellationToken.None, context.Subspace.Subspace); 55 54 context.IncrementEvaluatedSolutions(result.Item1); 56 55 context.Iterations = result.Item2; -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LocalSearch/StaticAPI/ExhaustiveLocalSearch.cs
r14544 r14552 21 21 22 22 using System; 23 using System.Collections.Generic; 23 24 using System.Linq; 24 25 using System.Threading; 25 26 using HeuristicLab.Algorithms.MemPR.Util; 26 using HeuristicLab.Collections;27 27 using HeuristicLab.Core; 28 28 using HeuristicLab.Encodings.LinearLinkageEncoding; … … 30 30 namespace HeuristicLab.Algorithms.MemPR.Grouping.LocalSearch { 31 31 public static class ExhaustiveLocalSearch { 32 public static Tuple<int, int> Optimize(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token, bool[] subspace = null) {32 public static Tuple<int, int> Optimize(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, CancellationToken, double> eval, CancellationToken token, bool[] subspace = null) { 33 33 var evaluations = 0; 34 var current = solution;35 34 if (double.IsNaN(quality)) { 36 quality = eval( current, random);35 quality = eval(solution, token); 37 36 evaluations++; 38 37 } 39 38 var steps = 0; 40 // this dictionary holds the last relevant links 41 var links = new BidirectionalDictionary<int, int>(); 39 var lleb = solution.ToBackLinks(); 42 40 for (var iter = 0; iter < int.MaxValue; iter++) { 43 41 var change = false; 44 // clear the dictionary before a new pass through the array is made 45 links.Clear(); 46 for (var i = 0; i < current.Length; i++) { 47 if (subspace != null && !subspace[i]) { 48 links.RemoveBySecond(i); 49 links.Add(i, current[i]); 50 continue; 51 } 52 var pred = -1; 53 var isFirst = !links.TryGetBySecond(i, out pred); 54 var keepLink = false; 55 if (!isFirst) { 56 keepLink = subspace != null && !subspace[pred]; 57 } 58 var next = current[i]; 59 var isLast = next == i; 60 61 if (!keepLink) { 62 // try to insert current into each previous group 63 // first remove i from its group 64 var linksList = links.Where(x => x.Value != i).ToList(); 65 if (linksList.Count > 0 && !isFirst) current[pred] = isLast ? pred : next; 66 for (var k = 0; k < linksList.Count; k++) { 67 var l = linksList[k]; 68 current[l.Key] = i; 69 current[i] = Math.Max(i, l.Value); 70 var moveF = eval(current, random); 71 evaluations++; 72 if (FitnessComparer.IsBetter(maximization, moveF, quality)) { 73 steps++; 74 quality = moveF; 75 change = true; 76 links.RemoveBySecond(i); 77 links.SetByFirst(l.Key, i); // otherwise the link won't be removed 78 if (!isFirst) links.SetByFirst(pred, isLast ? pred : next); 79 next = current[i]; 80 if (next == i) { isLast = true; } 81 pred = l.Key; 82 isFirst = false; 83 break; 84 } else { // undo 85 current[l.Key] = l.Value; 86 if (k == linksList.Count - 1) { 87 // all attempts unsuccessful 88 if (!isFirst) current[pred] = i; // undo - readd i to its group 89 current[i] = next; 90 } 91 } 92 } 93 } 94 95 if (!isLast) { 96 // try to split group at this point 97 // this is safe even if keepLink was true 98 current[i] = i; 99 var moveF = eval(current, random); 42 var groupItems = new List<int>(); 43 for (var i = 0; i < solution.Length; i++) { 44 foreach (var move in MoveGenerator.GenerateForItem(i, groupItems, solution, lleb).ToList()) { 45 move.Apply(solution); 46 var moveF = eval(solution, token); 100 47 evaluations++; 101 48 if (FitnessComparer.IsBetter(maximization, moveF, quality)) { 49 move.ApplyToLLEb(lleb); 102 50 steps++; 103 51 quality = moveF; 104 52 change = true; 105 isLast = true;106 next = i;107 links.SetBySecond(i, i);108 continue;109 } else current[i] = next; // undo53 break; 54 } else { 55 move.Undo(solution); 56 } 57 if (token.IsCancellationRequested) break; 110 58 } 111 112 if (isFirst && !isLast) { 113 // try merge with all terminated groups 114 foreach (var l in links.Where(x => x.Key == x.Value && (subspace == null || subspace[x.Key]))) { 115 current[l.Key] = i; 116 var moveF = eval(current, random); 117 evaluations++; 118 if (FitnessComparer.IsBetter(maximization, moveF, quality)) { 119 steps++; 120 quality = moveF; 121 change = true; 122 isFirst = false; 123 pred = l.Key; 124 links.SetByFirst(l.Key, i); 125 break; 126 } else { 127 current[l.Key] = l.Value; 128 } 129 } 130 } else if (!isFirst && !keepLink) { 131 // try to extract current into own group 132 current[pred] = isLast ? pred : next; 133 current[i] = i; 134 var moveF = eval(current, random); 135 evaluations++; 136 if (FitnessComparer.IsBetter(maximization, moveF, quality)) { 137 steps++; 138 links.SetByFirst(pred, current[pred]); 139 quality = moveF; 140 change = true; 141 } else { // undo 142 current[pred] = i; 143 current[i] = next; 144 } 145 } 146 links.RemoveBySecond(i); 147 links.Add(i, current[i]); 59 if (lleb[i] != i) 60 groupItems.Remove(lleb[i]); 61 groupItems.Add(i); 148 62 if (token.IsCancellationRequested) break; 149 63 } … … 154 68 } 155 69 156 public static Tuple<int, int> OptimizeSwap Only(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token) {70 public static Tuple<int, int> OptimizeSwap(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token) { 157 71 var evaluations = 0; 158 72 var current = solution; -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnbiasedModelTrainer.cs
r14544 r14552 32 32 [StorableClass] 33 33 public class UniasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext> 34 where TContext : IPopulationBasedHeuristicAlgorithmContext< SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage>, ISolutionModelContext<LinearLinkage> {34 where TContext : IPopulationBasedHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, LinearLinkage>, ISolutionModelContext<LinearLinkage> { 35 35 36 36 [StorableConstructor]
Note: See TracChangeset
for help on using the changeset viewer.
