[14420] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
| 25 | using System.Threading;
|
---|
[14450] | 26 | using HeuristicLab.Algorithms.MemPR.Interfaces;
|
---|
[14466] | 27 | using HeuristicLab.Algorithms.MemPR.Util;
|
---|
[14420] | 28 | using HeuristicLab.Common;
|
---|
| 29 | using HeuristicLab.Core;
|
---|
[14466] | 30 | using HeuristicLab.Encodings.LinearLinkageEncoding;
|
---|
[14420] | 31 | using HeuristicLab.Optimization;
|
---|
| 32 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 33 | using HeuristicLab.PluginInfrastructure;
|
---|
[14563] | 34 | using HeuristicLab.Random;
|
---|
[14420] | 35 |
|
---|
[14544] | 36 | namespace HeuristicLab.Algorithms.MemPR.Grouping {
|
---|
[14466] | 37 | [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")]
|
---|
[14420] | 38 | [StorableClass]
|
---|
| 39 | [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
|
---|
[14552] | 40 | public class LinearLinkageMemPR : MemPRAlgorithm<ISingleObjectiveHeuristicOptimizationProblem, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
|
---|
[14420] | 41 | [StorableConstructor]
|
---|
[14466] | 42 | protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { }
|
---|
| 43 | protected LinearLinkageMemPR(LinearLinkageMemPR original, Cloner cloner) : base(original, cloner) { }
|
---|
| 44 | public LinearLinkageMemPR() {
|
---|
| 45 | foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<LinearLinkageMemPRPopulationContext>>())
|
---|
[14420] | 46 | SolutionModelTrainerParameter.ValidValues.Add(trainer);
|
---|
[14563] | 47 |
|
---|
| 48 | if (SolutionModelTrainerParameter.ValidValues.Count > 0) {
|
---|
| 49 | var unbiased = SolutionModelTrainerParameter.ValidValues.FirstOrDefault(x => !x.Bias);
|
---|
| 50 | if (unbiased != null) SolutionModelTrainerParameter.Value = unbiased;
|
---|
| 51 | }
|
---|
| 52 |
|
---|
[14466] | 53 | foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<LinearLinkageMemPRSolutionContext>>()) {
|
---|
[14450] | 54 | LocalSearchParameter.ValidValues.Add(localSearch);
|
---|
[14420] | 55 | }
|
---|
| 56 | }
|
---|
| 57 |
|
---|
| 58 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
[14466] | 59 | return new LinearLinkageMemPR(this, cloner);
|
---|
[14420] | 60 | }
|
---|
| 61 |
|
---|
[14550] | 62 | protected override bool Eq(LinearLinkage a, LinearLinkage b) {
|
---|
| 63 | if (a.Length != b.Length) return false;
|
---|
| 64 | for (var i = 0; i < a.Length; i++)
|
---|
| 65 | if (a[i] != b[i]) return false;
|
---|
[14471] | 66 | return true;
|
---|
[14420] | 67 | }
|
---|
| 68 |
|
---|
[14544] | 69 | protected override double Dist(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b) {
|
---|
| 70 | return Dist(a.Solution, b.Solution);
|
---|
[14420] | 71 | }
|
---|
| 72 |
|
---|
[14544] | 73 | private double Dist(LinearLinkage a, LinearLinkage b) {
|
---|
| 74 | return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
|
---|
| 75 | }
|
---|
| 76 |
|
---|
| 77 | protected override ISolutionSubspace<LinearLinkage> CalculateSubspace(IEnumerable<LinearLinkage> solutions, bool inverse = false) {
|
---|
[14420] | 78 | var pop = solutions.ToList();
|
---|
| 79 | var N = pop[0].Length;
|
---|
| 80 | var subspace = new bool[N];
|
---|
| 81 | for (var i = 0; i < N; i++) {
|
---|
| 82 | var val = pop[0][i];
|
---|
| 83 | if (inverse) subspace[i] = true;
|
---|
| 84 | for (var p = 1; p < pop.Count; p++) {
|
---|
| 85 | if (pop[p][i] != val) subspace[i] = !inverse;
|
---|
| 86 | }
|
---|
| 87 | }
|
---|
[14466] | 88 | return new LinearLinkageSolutionSubspace(subspace);
|
---|
[14420] | 89 | }
|
---|
| 90 |
|
---|
[14544] | 91 | protected override void AdaptiveWalk(
|
---|
| 92 | ISingleObjectiveSolutionScope<LinearLinkage> scope,
|
---|
[14477] | 93 | int maxEvals, CancellationToken token,
|
---|
[14544] | 94 | ISolutionSubspace<LinearLinkage> sub_space = null) {
|
---|
[14552] | 95 | var maximization = Context.Maximization;
|
---|
[14477] | 96 | var subspace = sub_space is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)sub_space).Subspace : null;
|
---|
| 97 | var evaluations = 0;
|
---|
[14471] | 98 | var quality = scope.Fitness;
|
---|
| 99 | if (double.IsNaN(quality)) {
|
---|
[14552] | 100 | Context.Evaluate(scope, token);
|
---|
[14477] | 101 | quality = scope.Fitness;
|
---|
[14471] | 102 | evaluations++;
|
---|
[14544] | 103 | if (evaluations >= maxEvals) return;
|
---|
[14471] | 104 | }
|
---|
[14484] | 105 | var bestQuality = quality;
|
---|
[14544] | 106 | var currentScope = (ISingleObjectiveSolutionScope<LinearLinkage>)scope.Clone();
|
---|
[14477] | 107 | var current = currentScope.Solution;
|
---|
[14544] | 108 | LinearLinkage bestOfTheWalk = null;
|
---|
[14484] | 109 | var bestOfTheWalkF = double.NaN;
|
---|
[14477] | 110 |
|
---|
[14471] | 111 | var tabu = new double[current.Length, current.Length];
|
---|
| 112 | for (var i = 0; i < current.Length; i++) {
|
---|
| 113 | for (var j = i; j < current.Length; j++) {
|
---|
[14477] | 114 | tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;
|
---|
[14471] | 115 | }
|
---|
[14477] | 116 | tabu[i, current[i]] = quality;
|
---|
[14471] | 117 | }
|
---|
[14492] | 118 |
|
---|
[14477] | 119 | // this dictionary holds the last relevant links
|
---|
[14492] | 120 | var groupItems = new List<int>();
|
---|
| 121 | var lleb = current.ToBackLinks();
|
---|
[15256] | 122 | EMSSMove bestOfTheRest = null;
|
---|
[14484] | 123 | var bestOfTheRestF = double.NaN;
|
---|
| 124 | var lastAppliedMove = -1;
|
---|
[14471] | 125 | for (var iter = 0; iter < int.MaxValue; iter++) {
|
---|
[14477] | 126 | // clear the dictionary before a new pass through the array is made
|
---|
[14492] | 127 | groupItems.Clear();
|
---|
[14477] | 128 | for (var i = 0; i < current.Length; i++) {
|
---|
| 129 | if (subspace != null && !subspace[i]) {
|
---|
[14492] | 130 | if (lleb[i] != i)
|
---|
| 131 | groupItems.Remove(lleb[i]);
|
---|
| 132 | groupItems.Add(i);
|
---|
[14471] | 133 | continue;
|
---|
[14477] | 134 | }
|
---|
[14471] | 135 |
|
---|
[14477] | 136 | var next = current[i];
|
---|
[14484] | 137 |
|
---|
| 138 | if (lastAppliedMove == i) {
|
---|
| 139 | if (bestOfTheRest != null) {
|
---|
| 140 | bestOfTheRest.Apply(current);
|
---|
[14492] | 141 | bestOfTheRest.ApplyToLLEb(lleb);
|
---|
[14484] | 142 | currentScope.Fitness = bestOfTheRestF;
|
---|
| 143 | quality = bestOfTheRestF;
|
---|
[14477] | 144 | if (maximization) {
|
---|
[14484] | 145 | tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);
|
---|
| 146 | tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);
|
---|
[14477] | 147 | } else {
|
---|
[14484] | 148 | tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);
|
---|
| 149 | tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);
|
---|
[14477] | 150 | }
|
---|
[14484] | 151 | if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
|
---|
[14544] | 152 | bestOfTheWalk = (LinearLinkage)current.Clone();
|
---|
[14484] | 153 | bestOfTheWalkF = bestOfTheRestF;
|
---|
| 154 | }
|
---|
| 155 | bestOfTheRest = null;
|
---|
| 156 | bestOfTheRestF = double.NaN;
|
---|
| 157 | lastAppliedMove = i;
|
---|
| 158 | } else {
|
---|
| 159 | lastAppliedMove = -1;
|
---|
| 160 | }
|
---|
| 161 | break;
|
---|
| 162 | } else {
|
---|
[15256] | 163 | foreach (var move in ExhaustiveEMSSMoveGenerator.GenerateForItem(i, groupItems, current, lleb)) {
|
---|
[14484] | 164 | // we intend to break link i -> next
|
---|
| 165 | var qualityToBreak = tabu[i, next];
|
---|
| 166 | move.Apply(current);
|
---|
| 167 | var qualityToRestore = tabu[i, current[i]]; // current[i] is new next
|
---|
[14552] | 168 | Context.Evaluate(currentScope, token);
|
---|
[14484] | 169 | evaluations++;
|
---|
| 170 | var moveF = currentScope.Fitness;
|
---|
| 171 | var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak)
|
---|
| 172 | && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore);
|
---|
| 173 | var isImprovement = FitnessComparer.IsBetter(maximization, moveF, quality);
|
---|
| 174 | var isAspired = FitnessComparer.IsBetter(maximization, moveF, bestQuality);
|
---|
| 175 | if ((isNotTabu && isImprovement) || isAspired) {
|
---|
| 176 | if (maximization) {
|
---|
| 177 | tabu[i, next] = Math.Max(tabu[i, next], moveF);
|
---|
| 178 | tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);
|
---|
| 179 | } else {
|
---|
| 180 | tabu[i, next] = Math.Min(tabu[i, next], moveF);
|
---|
| 181 | tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);
|
---|
| 182 | }
|
---|
| 183 | quality = moveF;
|
---|
| 184 | if (isAspired) bestQuality = quality;
|
---|
[14471] | 185 |
|
---|
[14492] | 186 | move.ApplyToLLEb(lleb);
|
---|
[14484] | 187 |
|
---|
| 188 | if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) {
|
---|
[14544] | 189 | bestOfTheWalk = (LinearLinkage)current.Clone();
|
---|
[14484] | 190 | bestOfTheWalkF = moveF;
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 | bestOfTheRest = null;
|
---|
| 194 | bestOfTheRestF = double.NaN;
|
---|
| 195 | lastAppliedMove = i;
|
---|
| 196 | break;
|
---|
| 197 | } else {
|
---|
| 198 | if (isNotTabu) {
|
---|
| 199 | if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheRestF)) {
|
---|
| 200 | bestOfTheRest = move;
|
---|
| 201 | bestOfTheRestF = moveF;
|
---|
| 202 | }
|
---|
| 203 | }
|
---|
| 204 | move.Undo(current);
|
---|
| 205 | currentScope.Fitness = quality;
|
---|
| 206 | }
|
---|
| 207 | if (evaluations >= maxEvals) break;
|
---|
| 208 | }
|
---|
[14471] | 209 | }
|
---|
[14492] | 210 | if (lleb[i] != i)
|
---|
| 211 | groupItems.Remove(lleb[i]);
|
---|
| 212 | groupItems.Add(i);
|
---|
[14471] | 213 | if (evaluations >= maxEvals) break;
|
---|
[14477] | 214 | if (token.IsCancellationRequested) break;
|
---|
[14471] | 215 | }
|
---|
[14484] | 216 | if (lastAppliedMove == -1) { // no move has been applied
|
---|
| 217 | if (bestOfTheRest != null) {
|
---|
| 218 | var i = bestOfTheRest.Item;
|
---|
| 219 | var next = current[i];
|
---|
| 220 | bestOfTheRest.Apply(current);
|
---|
| 221 | currentScope.Fitness = bestOfTheRestF;
|
---|
| 222 | quality = bestOfTheRestF;
|
---|
| 223 | if (maximization) {
|
---|
| 224 | tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);
|
---|
| 225 | tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);
|
---|
| 226 | } else {
|
---|
| 227 | tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);
|
---|
| 228 | tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);
|
---|
| 229 | }
|
---|
| 230 | if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
|
---|
[14544] | 231 | bestOfTheWalk = (LinearLinkage)current.Clone();
|
---|
[14484] | 232 | bestOfTheWalkF = bestOfTheRestF;
|
---|
| 233 | }
|
---|
| 234 |
|
---|
| 235 | bestOfTheRest = null;
|
---|
| 236 | bestOfTheRestF = double.NaN;
|
---|
| 237 | } else break;
|
---|
| 238 | }
|
---|
[14471] | 239 | if (evaluations >= maxEvals) break;
|
---|
[14477] | 240 | if (token.IsCancellationRequested) break;
|
---|
[14471] | 241 | }
|
---|
[14484] | 242 | if (bestOfTheWalk != null) {
|
---|
| 243 | scope.Solution = bestOfTheWalk;
|
---|
| 244 | scope.Fitness = bestOfTheWalkF;
|
---|
| 245 | }
|
---|
[14466] | 246 | }
|
---|
[14420] | 247 |
|
---|
[14551] | 248 | protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1, ISingleObjectiveSolutionScope<LinearLinkage> p2, CancellationToken token) {
|
---|
[14544] | 249 | var cache = new HashSet<LinearLinkage>(new LinearLinkageEqualityComparer());
|
---|
[14551] | 250 | cache.Add(p1.Solution);
|
---|
| 251 | cache.Add(p2.Solution);
|
---|
| 252 |
|
---|
[14563] | 253 | var cacheHits = new Dictionary<int, int>() { { 0, 0 }, { 1, 0 } };
|
---|
[14551] | 254 | var evaluations = 0;
|
---|
[14695] | 255 | var probe = Context.ToScope(null);
|
---|
[14544] | 256 | ISingleObjectiveSolutionScope<LinearLinkage> offspring = null;
|
---|
[14551] | 257 | while (evaluations < p1.Solution.Length) {
|
---|
| 258 | LinearLinkage c = null;
|
---|
[14563] | 259 | var xochoice = cacheHits.SampleRandom(Context.Random).Key;
|
---|
| 260 | switch (xochoice) {
|
---|
| 261 | case 0: c = GroupCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
| 262 | case 1: c = SinglePointCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
| 263 | }
|
---|
[14551] | 264 | if (cache.Contains(c)) {
|
---|
[14563] | 265 | cacheHits[xochoice]++;
|
---|
| 266 | if (cacheHits[xochoice] > 10) {
|
---|
| 267 | cacheHits.Remove(xochoice);
|
---|
| 268 | if (cacheHits.Count == 0) break;
|
---|
| 269 | }
|
---|
[14544] | 270 | continue;
|
---|
[14420] | 271 | }
|
---|
[14556] | 272 | probe.Solution = c;
|
---|
[14552] | 273 | Context.Evaluate(probe, token);
|
---|
[14551] | 274 | evaluations++;
|
---|
| 275 | cache.Add(c);
|
---|
[14544] | 276 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
| 277 | offspring = probe;
|
---|
[14551] | 278 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
[14544] | 279 | break;
|
---|
| 280 | }
|
---|
[14420] | 281 | }
|
---|
[14551] | 282 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
| 283 | return offspring ?? probe;
|
---|
[14420] | 284 | }
|
---|
| 285 |
|
---|
[14544] | 286 | protected override ISingleObjectiveSolutionScope<LinearLinkage> Link(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b, CancellationToken token, bool delink = false) {
|
---|
| 287 | var evaluations = 0;
|
---|
| 288 | var probe = (ISingleObjectiveSolutionScope<LinearLinkage>)a.Clone();
|
---|
| 289 | ISingleObjectiveSolutionScope<LinearLinkage> best = null;
|
---|
| 290 | while (true) {
|
---|
[15256] | 291 | EMSSMove bestMove = null;
|
---|
[14544] | 292 | var bestMoveQ = double.NaN;
|
---|
| 293 | // this approach may not fully relink the two solutions
|
---|
[15256] | 294 | foreach (var m in ExhaustiveEMSSMoveGenerator.Generate(probe.Solution)) {
|
---|
[14544] | 295 | var distBefore = Dist(probe, b);
|
---|
| 296 | m.Apply(probe.Solution);
|
---|
| 297 | var distAfter = Dist(probe, b);
|
---|
[14550] | 298 | // consider all moves that would increase the distance between probe and b
|
---|
| 299 | // or decrease it depending on whether we do delinking or relinking
|
---|
[14544] | 300 | if (delink && distAfter > distBefore || !delink && distAfter < distBefore) {
|
---|
| 301 | var beforeQ = probe.Fitness;
|
---|
[14552] | 302 | Context.Evaluate(probe, token);
|
---|
[14544] | 303 | evaluations++;
|
---|
| 304 | var q = probe.Fitness;
|
---|
| 305 | m.Undo(probe.Solution);
|
---|
| 306 | probe.Fitness = beforeQ;
|
---|
| 307 |
|
---|
| 308 | if (Context.IsBetter(q, bestMoveQ)) {
|
---|
| 309 | bestMove = m;
|
---|
| 310 | bestMoveQ = q;
|
---|
| 311 | }
|
---|
| 312 | if (Context.IsBetter(q, beforeQ)) break;
|
---|
| 313 | } else m.Undo(probe.Solution);
|
---|
[14466] | 314 | }
|
---|
[14544] | 315 | if (bestMove == null) break;
|
---|
| 316 | bestMove.Apply(probe.Solution);
|
---|
| 317 | probe.Fitness = bestMoveQ;
|
---|
| 318 | if (best == null || Context.IsBetter(probe, best))
|
---|
| 319 | best = (ISingleObjectiveSolutionScope<LinearLinkage>)probe.Clone();
|
---|
| 320 | }
|
---|
| 321 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
| 322 |
|
---|
| 323 | return best ?? probe;
|
---|
[14420] | 324 | }
|
---|
| 325 | }
|
---|
| 326 | }
|
---|