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;
|
---|
26 | using HeuristicLab.Algorithms.MemPR.Interfaces;
|
---|
27 | using HeuristicLab.Algorithms.MemPR.Util;
|
---|
28 | using HeuristicLab.Common;
|
---|
29 | using HeuristicLab.Core;
|
---|
30 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
31 | using HeuristicLab.Optimization;
|
---|
32 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
33 | using HeuristicLab.PluginInfrastructure;
|
---|
34 | using HeuristicLab.Random;
|
---|
35 |
|
---|
36 | namespace HeuristicLab.Algorithms.MemPR.Permutation {
|
---|
37 | [Item("MemPR (permutation)", "MemPR implementation for permutations.")]
|
---|
38 | [StorableClass]
|
---|
39 | [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
|
---|
40 | public class PermutationMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
|
---|
41 | #if DEBUG
|
---|
42 | private const bool VALIDATE = true;
|
---|
43 | #else
|
---|
44 | private const bool VALIDATE = false;
|
---|
45 | #endif
|
---|
46 |
|
---|
47 | [StorableConstructor]
|
---|
48 | protected PermutationMemPR(bool deserializing) : base(deserializing) { }
|
---|
49 | protected PermutationMemPR(PermutationMemPR original, Cloner cloner) : base(original, cloner) { }
|
---|
50 | public PermutationMemPR() {
|
---|
51 | foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<PermutationMemPRPopulationContext>>())
|
---|
52 | SolutionModelTrainerParameter.ValidValues.Add(trainer);
|
---|
53 |
|
---|
54 | foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<PermutationMemPRSolutionContext>>()) {
|
---|
55 | LocalSearchParameter.ValidValues.Add(localSearch);
|
---|
56 | }
|
---|
57 | }
|
---|
58 |
|
---|
59 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
60 | return new PermutationMemPR(this, cloner);
|
---|
61 | }
|
---|
62 |
|
---|
63 | protected override bool Eq(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
|
---|
64 | return new PermutationEqualityComparer().Equals(a, b);
|
---|
65 | }
|
---|
66 |
|
---|
67 | protected override double Dist(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
|
---|
68 | return Dist(a.Solution, b.Solution);
|
---|
69 | }
|
---|
70 |
|
---|
71 | private static double Dist(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
|
---|
72 | return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
|
---|
73 | }
|
---|
74 |
|
---|
75 | protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> ToScope(Encodings.PermutationEncoding.Permutation code, double fitness = double.NaN) {
|
---|
76 | var creator = Problem.SolutionCreator as IPermutationCreator;
|
---|
77 | if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
|
---|
78 | return new SingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation>(code, creator.PermutationParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
|
---|
79 | Parent = Context.Scope
|
---|
80 | };
|
---|
81 | }
|
---|
82 |
|
---|
83 | protected override ISolutionSubspace<Encodings.PermutationEncoding.Permutation> CalculateSubspace(IEnumerable<Encodings.PermutationEncoding.Permutation> solutions, bool inverse = false) {
|
---|
84 | var subspace = new bool[Problem.Encoding.Length, Problem.Encoding.PermutationTypeParameter.Value.Value == PermutationTypes.Absolute ? 1 : Problem.Encoding.Length];
|
---|
85 |
|
---|
86 | switch (Problem.Encoding.PermutationTypeParameter.Value.Value) {
|
---|
87 | case PermutationTypes.Absolute: {
|
---|
88 | if (inverse) {
|
---|
89 | for (var i = 0; i < subspace.GetLength(0); i++)
|
---|
90 | subspace[i, 0] = true;
|
---|
91 | }
|
---|
92 | var first = solutions.First();
|
---|
93 | foreach (var s in solutions.Skip(1)) {
|
---|
94 | for (var i = 0; i < s.Length; i++) {
|
---|
95 | if (first[i] != s[i]) subspace[i, 0] = !inverse;
|
---|
96 | }
|
---|
97 | }
|
---|
98 | }
|
---|
99 | break;
|
---|
100 | case PermutationTypes.RelativeDirected: {
|
---|
101 | if (inverse) {
|
---|
102 | for (var i = 0; i < subspace.GetLength(0); i++)
|
---|
103 | for (var j = 0; j < subspace.GetLength(1); j++)
|
---|
104 | subspace[i, j] = true;
|
---|
105 | }
|
---|
106 | var first = solutions.First();
|
---|
107 | var placedFirst = new int[first.Length];
|
---|
108 | for (var i = 0; i < first.Length; i++) {
|
---|
109 | placedFirst[first[i]] = i;
|
---|
110 | }
|
---|
111 | foreach (var s in solutions.Skip(1)) {
|
---|
112 | for (var i = 0; i < s.Length; i++) {
|
---|
113 | if (placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)] != -1)
|
---|
114 | subspace[i, 0] = !inverse;
|
---|
115 | }
|
---|
116 | }
|
---|
117 | }
|
---|
118 | break;
|
---|
119 | case PermutationTypes.RelativeUndirected: {
|
---|
120 | if (inverse) {
|
---|
121 | for (var i = 0; i < subspace.GetLength(0); i++)
|
---|
122 | for (var j = 0; j < subspace.GetLength(1); j++)
|
---|
123 | subspace[i, j] = true;
|
---|
124 | }
|
---|
125 | var first = solutions.First();
|
---|
126 | var placedFirst = new int[first.Length];
|
---|
127 | for (var i = 0; i < first.Length; i++) {
|
---|
128 | placedFirst[first[i]] = i;
|
---|
129 | }
|
---|
130 | foreach (var s in solutions.Skip(1)) {
|
---|
131 | for (var i = 0; i < s.Length; i++) {
|
---|
132 | if (Math.Abs(placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)]) != 1)
|
---|
133 | subspace[i, 0] = !inverse;
|
---|
134 | }
|
---|
135 | }
|
---|
136 | }
|
---|
137 | break;
|
---|
138 | default:
|
---|
139 | throw new ArgumentException(string.Format("Unknown permutation type {0}", Problem.Encoding.PermutationTypeParameter.Value.Value));
|
---|
140 | }
|
---|
141 | return new PermutationSolutionSubspace(subspace);
|
---|
142 | }
|
---|
143 |
|
---|
144 | protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
|
---|
145 | var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
|
---|
146 | var quality = scope.Fitness;
|
---|
147 | try {
|
---|
148 | TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
|
---|
149 | } finally {
|
---|
150 | scope.Fitness = quality;
|
---|
151 | }
|
---|
152 | }
|
---|
153 |
|
---|
154 | public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
|
---|
155 | switch (perm.PermutationType) {
|
---|
156 | case PermutationTypes.Absolute:
|
---|
157 | TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
|
---|
158 | break;
|
---|
159 | case PermutationTypes.RelativeDirected:
|
---|
160 | TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
|
---|
161 | break;
|
---|
162 | case PermutationTypes.RelativeUndirected:
|
---|
163 | TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
|
---|
164 | break;
|
---|
165 | default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
|
---|
166 | }
|
---|
167 | if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
|
---|
168 | }
|
---|
169 |
|
---|
170 | public int TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
|
---|
171 | var evaluations = 0;
|
---|
172 | var maximization = Context.Problem.Maximization;
|
---|
173 | if (double.IsNaN(quality)) {
|
---|
174 | quality = eval(perm, random);
|
---|
175 | evaluations++;
|
---|
176 | }
|
---|
177 | Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
|
---|
178 | double bestOfTheWalkF = double.NaN;
|
---|
179 | var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
|
---|
180 | var currentF = quality;
|
---|
181 | var overallImprovement = false;
|
---|
182 | var tabu = new double[current.Length, current.Length];
|
---|
183 | for (var i = 0; i < current.Length; i++) {
|
---|
184 | for (var j = i; j < current.Length; j++) {
|
---|
185 | tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;
|
---|
186 | }
|
---|
187 | tabu[i, current[i]] = currentF;
|
---|
188 | }
|
---|
189 |
|
---|
190 | var steps = 0;
|
---|
191 | var stepsUntilBestOfWalk = 0;
|
---|
192 | for (var iter = 0; iter < int.MaxValue; iter++) {
|
---|
193 | var allTabu = true;
|
---|
194 | var bestOfTheRestF = double.NaN;
|
---|
195 | Swap2Move bestOfTheRest = null;
|
---|
196 | var improved = false;
|
---|
197 | foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
|
---|
198 | if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
|
---|
199 | continue;
|
---|
200 |
|
---|
201 | var h = current[swap.Index1];
|
---|
202 | current[swap.Index1] = current[swap.Index2];
|
---|
203 | current[swap.Index2] = h;
|
---|
204 | var q = eval(current, random);
|
---|
205 | evaluations++;
|
---|
206 | if (FitnessComparer.IsBetter(maximization, q, quality)) {
|
---|
207 | overallImprovement = true;
|
---|
208 | quality = q;
|
---|
209 | for (var i = 0; i < current.Length; i++) perm[i] = current[i];
|
---|
210 | }
|
---|
211 | // check if it would not be an improvement to swap these into their positions
|
---|
212 | var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index1, current[swap.Index1]])
|
---|
213 | && !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index2, current[swap.Index2]]);
|
---|
214 | if (!isTabu) allTabu = false;
|
---|
215 | if (FitnessComparer.IsBetter(maximization, q, currentF) && !isTabu) {
|
---|
216 | if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
|
---|
217 | bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
|
---|
218 | bestOfTheWalkF = q;
|
---|
219 | stepsUntilBestOfWalk = steps;
|
---|
220 | }
|
---|
221 | steps++;
|
---|
222 | improved = true;
|
---|
223 | // perform the move
|
---|
224 | currentF = q;
|
---|
225 | // mark that to move them to their previous position requires to make an improvement
|
---|
226 | tabu[swap.Index1, current[swap.Index2]] = maximization ? Math.Max(q, tabu[swap.Index1, current[swap.Index2]])
|
---|
227 | : Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
|
---|
228 | tabu[swap.Index2, current[swap.Index1]] = maximization ? Math.Max(q, tabu[swap.Index2, current[swap.Index1]])
|
---|
229 | : Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
|
---|
230 | } else { // undo the move
|
---|
231 | if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
|
---|
232 | bestOfTheRest = swap;
|
---|
233 | bestOfTheRestF = q;
|
---|
234 | }
|
---|
235 | current[swap.Index2] = current[swap.Index1];
|
---|
236 | current[swap.Index1] = h;
|
---|
237 | }
|
---|
238 | if (evaluations >= maxEvals) break;
|
---|
239 | }
|
---|
240 | if (!allTabu && !improved && bestOfTheRest != null) {
|
---|
241 | tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]])
|
---|
242 | : Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
|
---|
243 | tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]])
|
---|
244 | : Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
|
---|
245 |
|
---|
246 | var h = current[bestOfTheRest.Index1];
|
---|
247 | current[bestOfTheRest.Index1] = current[bestOfTheRest.Index2];
|
---|
248 | current[bestOfTheRest.Index2] = h;
|
---|
249 |
|
---|
250 | currentF = bestOfTheRestF;
|
---|
251 | steps++;
|
---|
252 | } else if (allTabu) break;
|
---|
253 | if (evaluations >= maxEvals) break;
|
---|
254 | }
|
---|
255 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
256 | if (!overallImprovement && bestOfTheWalk != null) {
|
---|
257 | quality = bestOfTheWalkF;
|
---|
258 | for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
|
---|
259 | }
|
---|
260 | return stepsUntilBestOfWalk;
|
---|
261 | }
|
---|
262 |
|
---|
263 | public int TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
|
---|
264 | return 0;
|
---|
265 | }
|
---|
266 |
|
---|
267 | public int TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
|
---|
268 | var maximization = Context.Problem.Maximization;
|
---|
269 | var evaluations = 0;
|
---|
270 | if (double.IsNaN(quality)) {
|
---|
271 | quality = eval(perm, random);
|
---|
272 | evaluations++;
|
---|
273 | }
|
---|
274 | Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
|
---|
275 | var bestOfTheWalkF = double.NaN;
|
---|
276 | var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
|
---|
277 | var currentF = quality;
|
---|
278 | var overallImprovement = false;
|
---|
279 | var tabu = new double[current.Length, current.Length];
|
---|
280 | for (var i = 0; i < current.Length; i++) {
|
---|
281 | for (var j = i; j < current.Length; j++) {
|
---|
282 | tabu[i, j] = tabu[j, i] = double.MaxValue;
|
---|
283 | }
|
---|
284 | tabu[current[i], current.GetCircular(i + 1)] = currentF;
|
---|
285 | tabu[current.GetCircular(i + 1), current[i]] = currentF;
|
---|
286 | }
|
---|
287 |
|
---|
288 | var steps = 0;
|
---|
289 | var stepsUntilBestOfWalk = 0;
|
---|
290 | for (var iter = 0; iter < int.MaxValue; iter++) {
|
---|
291 | var allTabu = true;
|
---|
292 | var bestOfTheRestF = double.NaN;
|
---|
293 | InversionMove bestOfTheRest = null;
|
---|
294 | var improved = false;
|
---|
295 |
|
---|
296 | foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random)) {
|
---|
297 | var prev = opt.Index1 - 1;
|
---|
298 | var next = (opt.Index2 + 1) % current.Length;
|
---|
299 | if (prev < 0) prev += current.Length;
|
---|
300 | if (subspace != null && !(subspace[current[prev], current[opt.Index1]] && subspace[current[opt.Index2], current[next]]))
|
---|
301 | continue;
|
---|
302 |
|
---|
303 | InversionManipulator.Apply(current, opt.Index1, opt.Index2);
|
---|
304 |
|
---|
305 | var q = eval(current, random);
|
---|
306 | evaluations++;
|
---|
307 | if (FitnessComparer.IsBetter(maximization, q, quality)) {
|
---|
308 | overallImprovement = true;
|
---|
309 | quality = q;
|
---|
310 | for (var i = 0; i < current.Length; i++) perm[i] = current[i];
|
---|
311 | }
|
---|
312 | // check if it would not be an improvement to opt these into their positions
|
---|
313 | var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[current[prev], current[opt.Index1]])
|
---|
314 | && !FitnessComparer.IsBetter(maximization, q, tabu[current[opt.Index2], current[next]]);
|
---|
315 | if (!isTabu) allTabu = false;
|
---|
316 | if (!isTabu && FitnessComparer.IsBetter(maximization, q, currentF)) {
|
---|
317 | if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
|
---|
318 | bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
|
---|
319 | bestOfTheWalkF = q;
|
---|
320 | stepsUntilBestOfWalk = steps;
|
---|
321 | }
|
---|
322 |
|
---|
323 | steps++;
|
---|
324 | improved = true;
|
---|
325 | // perform the move
|
---|
326 | currentF = q;
|
---|
327 | // mark that to move them to their previous position requires to make an improvement
|
---|
328 | if (maximization) {
|
---|
329 | tabu[current[prev], current[opt.Index2]] = Math.Max(q, tabu[current[prev], current[opt.Index2]]);
|
---|
330 | tabu[current[opt.Index2], current[prev]] = Math.Max(q, tabu[current[opt.Index2], current[prev]]);
|
---|
331 | tabu[current[opt.Index1], current[next]] = Math.Max(q, tabu[current[opt.Index1], current[next]]);
|
---|
332 | tabu[current[next], current[opt.Index1]] = Math.Max(q, tabu[current[next], current[opt.Index1]]);
|
---|
333 | } else {
|
---|
334 | tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
|
---|
335 | tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
|
---|
336 | tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
|
---|
337 | tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
|
---|
338 | }
|
---|
339 | } else { // undo the move
|
---|
340 | if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
|
---|
341 | bestOfTheRest = opt;
|
---|
342 | bestOfTheRestF = q;
|
---|
343 | }
|
---|
344 |
|
---|
345 | InversionManipulator.Apply(current, opt.Index1, opt.Index2);
|
---|
346 | }
|
---|
347 | if (evaluations >= maxEvals) break;
|
---|
348 | }
|
---|
349 | if (!allTabu && !improved && bestOfTheRest != null) {
|
---|
350 | var prev = bestOfTheRest.Index1 - 1;
|
---|
351 | var next = (bestOfTheRest.Index2 + 1) % current.Length;
|
---|
352 | if (prev < 0) prev += current.Length;
|
---|
353 |
|
---|
354 | if (maximization) {
|
---|
355 | tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Max(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
|
---|
356 | tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
|
---|
357 | tabu[current[bestOfTheRest.Index2], current[next]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
|
---|
358 | tabu[current[next], current[bestOfTheRest.Index2]] = Math.Max(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
|
---|
359 | } else {
|
---|
360 | tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
|
---|
361 | tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
|
---|
362 | tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
|
---|
363 | tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
|
---|
364 | }
|
---|
365 | InversionManipulator.Apply(current, bestOfTheRest.Index1, bestOfTheRest.Index2);
|
---|
366 |
|
---|
367 | currentF = bestOfTheRestF;
|
---|
368 | steps++;
|
---|
369 | } else if (allTabu) break;
|
---|
370 | if (evaluations >= maxEvals) break;
|
---|
371 | }
|
---|
372 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
373 | if (!overallImprovement && bestOfTheWalk != null) {
|
---|
374 | quality = bestOfTheWalkF;
|
---|
375 | for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
|
---|
376 | }
|
---|
377 | return stepsUntilBestOfWalk;
|
---|
378 | }
|
---|
379 |
|
---|
380 | protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Breed(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
|
---|
381 | ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> child = null;
|
---|
382 |
|
---|
383 | if (p1.Solution.PermutationType == PermutationTypes.Absolute) {
|
---|
384 | child = CrossAbsolute(p1, p2, token);
|
---|
385 | } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) {
|
---|
386 | child = CrossRelativeDirected(p1, p2, token);
|
---|
387 | } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) {
|
---|
388 | child = CrossRelativeUndirected(p1, p2, token);
|
---|
389 | } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType));
|
---|
390 |
|
---|
391 | if (VALIDATE && !child.Solution.Validate()) throw new ArgumentException("Cross produced invalid child");
|
---|
392 | return child;
|
---|
393 | }
|
---|
394 |
|
---|
395 | private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
|
---|
396 | var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
|
---|
397 | var cacheHits = 0;
|
---|
398 | var evaluations = 1;
|
---|
399 | ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
|
---|
400 | for (; evaluations <= p1.Solution.Length; evaluations++) {
|
---|
401 | Encodings.PermutationEncoding.Permutation c = null;
|
---|
402 | var xochoice = Context.Random.Next(3);
|
---|
403 | switch (xochoice) {
|
---|
404 | case 0: c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
405 | case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
406 | case 2: c = UniformLikeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
407 | }
|
---|
408 | if (cache.Contains(c)) {
|
---|
409 | cacheHits++;
|
---|
410 | if (cacheHits > 10) break;
|
---|
411 | continue;
|
---|
412 | }
|
---|
413 | var probe = ToScope(c);
|
---|
414 | Evaluate(probe, token);
|
---|
415 | cache.Add(c);
|
---|
416 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
417 | offspring = probe;
|
---|
418 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
419 | break;
|
---|
420 | }
|
---|
421 | }
|
---|
422 | Context.IncrementEvaluatedSolutions(evaluations-1);
|
---|
423 | return offspring;
|
---|
424 | }
|
---|
425 |
|
---|
426 | private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
|
---|
427 | var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
|
---|
428 | var cacheHits = 0;
|
---|
429 | var evaluations = 1;
|
---|
430 | ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
|
---|
431 | for (; evaluations <= p1.Solution.Length; evaluations++) {
|
---|
432 | Encodings.PermutationEncoding.Permutation c = null;
|
---|
433 | var xochoice = Context.Random.Next(3);
|
---|
434 | switch (xochoice) {
|
---|
435 | case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
436 | case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
437 | case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
438 | }
|
---|
439 | if (cache.Contains(c)) {
|
---|
440 | cacheHits++;
|
---|
441 | if (cacheHits > 10) break;
|
---|
442 | continue;
|
---|
443 | }
|
---|
444 | var probe = ToScope(c);
|
---|
445 | Evaluate(probe, token);
|
---|
446 | cache.Add(c);
|
---|
447 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
448 | offspring = probe;
|
---|
449 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
450 | break;
|
---|
451 | }
|
---|
452 | }
|
---|
453 | Context.IncrementEvaluatedSolutions(evaluations-1);
|
---|
454 | return offspring;
|
---|
455 | }
|
---|
456 |
|
---|
457 | private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
|
---|
458 | var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
|
---|
459 | var cacheHits = 0;
|
---|
460 | var evaluations = 1;
|
---|
461 | ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
|
---|
462 | for (; evaluations <= p1.Solution.Length; evaluations++) {
|
---|
463 | Encodings.PermutationEncoding.Permutation c = null;
|
---|
464 | var xochoice = Context.Random.Next(3);
|
---|
465 | switch (xochoice) {
|
---|
466 | case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
467 | case 1: c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
468 | case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
|
---|
469 | }
|
---|
470 | if (cache.Contains(c)) {
|
---|
471 | cacheHits++;
|
---|
472 | if (cacheHits > 10) break;
|
---|
473 | continue;
|
---|
474 | }
|
---|
475 | var probe = ToScope(c);
|
---|
476 | Evaluate(probe, token);
|
---|
477 | cache.Add(c);
|
---|
478 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
479 | offspring = probe;
|
---|
480 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
481 | break;
|
---|
482 | }
|
---|
483 | }
|
---|
484 | Context.IncrementEvaluatedSolutions(evaluations-1);
|
---|
485 | return offspring;
|
---|
486 | }
|
---|
487 |
|
---|
488 | protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
|
---|
489 | if (double.IsNaN(a.Fitness)) {
|
---|
490 | Evaluate(a, token);
|
---|
491 | Context.IncrementEvaluatedSolutions(1);
|
---|
492 | }
|
---|
493 | if (double.IsNaN(b.Fitness)) {
|
---|
494 | Evaluate(b, token);
|
---|
495 | Context.IncrementEvaluatedSolutions(1);
|
---|
496 | }
|
---|
497 |
|
---|
498 | var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, ToScope(null));
|
---|
499 | double quality;
|
---|
500 | return ToScope(Relink(Context.Random, a.Solution, b.Solution, wrapper.Evaluate, delink, out quality));
|
---|
501 | }
|
---|
502 |
|
---|
503 | public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
|
---|
504 | if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
|
---|
505 | switch (p1.PermutationType) {
|
---|
506 | case PermutationTypes.Absolute:
|
---|
507 | return delink ? DelinkSwap(random, p1, p2, eval, out best) : RelinkSwap(random, p1, p2, eval, out best);
|
---|
508 | case PermutationTypes.RelativeDirected:
|
---|
509 | return RelinkShift(random, p1, p2, eval, delink, out best);
|
---|
510 | case PermutationTypes.RelativeUndirected:
|
---|
511 | return RelinkOpt(random, p1, p2, eval, delink, out best);
|
---|
512 | default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
|
---|
513 | }
|
---|
514 | }
|
---|
515 |
|
---|
516 | public Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
|
---|
517 | var maximization = Context.Problem.Maximization;
|
---|
518 | var evaluations = 0;
|
---|
519 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
520 |
|
---|
521 | best = double.NaN;
|
---|
522 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
523 |
|
---|
524 | var options = Enumerable.Range(0, child.Length).Where(x => child[x] != p2[x]).ToList();
|
---|
525 | var invChild = new int[child.Length];
|
---|
526 | for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
|
---|
527 |
|
---|
528 | while (options.Count > 0) {
|
---|
529 | int bestOption = -1;
|
---|
530 | var bestChange = double.NaN;
|
---|
531 | for (var j = 0; j < options.Count; j++) {
|
---|
532 | var idx = options[j];
|
---|
533 | if (child[idx] == p2[idx]) {
|
---|
534 | options.RemoveAt(j);
|
---|
535 | j--;
|
---|
536 | continue;
|
---|
537 | }
|
---|
538 | Swap(child, invChild[p2[idx]], idx);
|
---|
539 | var moveF = eval(child, random);
|
---|
540 | evaluations++;
|
---|
541 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
542 | bestChange = moveF;
|
---|
543 | bestOption = j;
|
---|
544 | }
|
---|
545 | // undo
|
---|
546 | Swap(child, invChild[p2[idx]], idx);
|
---|
547 | }
|
---|
548 | if (!double.IsNaN(bestChange)) {
|
---|
549 | var idx1 = options[bestOption];
|
---|
550 | var idx2 = invChild[p2[idx1]];
|
---|
551 | Swap(child, idx1, idx2);
|
---|
552 | invChild[child[idx1]] = idx1;
|
---|
553 | invChild[child[idx2]] = idx2;
|
---|
554 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
555 | if (Dist(child, p2) > 0) {
|
---|
556 | best = bestChange;
|
---|
557 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
558 | }
|
---|
559 | }
|
---|
560 | options.RemoveAt(bestOption);
|
---|
561 | }
|
---|
562 | }
|
---|
563 | if (bestChild == null) {
|
---|
564 | best = eval(child, random);
|
---|
565 | evaluations++;
|
---|
566 | }
|
---|
567 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
568 |
|
---|
569 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
570 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
571 |
|
---|
572 | return bestChild ?? child;
|
---|
573 | }
|
---|
574 |
|
---|
575 | public Encodings.PermutationEncoding.Permutation DelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
|
---|
576 | var maximization = Context.Problem.Maximization;
|
---|
577 | var evaluations = 0;
|
---|
578 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
579 |
|
---|
580 | best = double.NaN;
|
---|
581 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
582 |
|
---|
583 | var options = Enumerable.Range(0, child.Length).Where(x => child[x] == p2[x]).ToList();
|
---|
584 |
|
---|
585 | while (options.Count > 0) {
|
---|
586 | int bestOption = -1;
|
---|
587 | int bestCompanion = -1;
|
---|
588 | var bestChange = double.NaN;
|
---|
589 | for (var j = 0; j < options.Count; j++) {
|
---|
590 | var idx = options[j];
|
---|
591 | if (child[idx] != p2[idx]) {
|
---|
592 | options.RemoveAt(j);
|
---|
593 | j--;
|
---|
594 | continue;
|
---|
595 | }
|
---|
596 | for (var k = 0; k < child.Length; k++) {
|
---|
597 | if (k == idx) continue;
|
---|
598 | Swap(child, k, idx);
|
---|
599 | var moveF = eval(child, random);
|
---|
600 | evaluations++;
|
---|
601 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
602 | bestChange = moveF;
|
---|
603 | bestOption = j;
|
---|
604 | bestCompanion = k;
|
---|
605 | }
|
---|
606 | // undo
|
---|
607 | Swap(child, k, idx);
|
---|
608 | }
|
---|
609 | }
|
---|
610 | if (!double.IsNaN(bestChange)) {
|
---|
611 | var idx1 = options[bestOption];
|
---|
612 | Swap(child, idx1, bestCompanion);
|
---|
613 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
614 | if (!Eq(child, p2)) {
|
---|
615 | best = bestChange;
|
---|
616 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
617 | }
|
---|
618 | }
|
---|
619 | options.RemoveAt(bestOption);
|
---|
620 | }
|
---|
621 | }
|
---|
622 | if (bestChild == null) {
|
---|
623 | best = eval(child, random);
|
---|
624 | evaluations++;
|
---|
625 | }
|
---|
626 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
627 |
|
---|
628 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
629 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
630 |
|
---|
631 | return bestChild ?? child;
|
---|
632 | }
|
---|
633 |
|
---|
634 | public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
|
---|
635 | var maximization = Context.Problem.Maximization;
|
---|
636 | var evaluations = 0;
|
---|
637 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
638 |
|
---|
639 | best = double.NaN;
|
---|
640 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
641 |
|
---|
642 | var invChild = new int[child.Length];
|
---|
643 | for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
|
---|
644 |
|
---|
645 | var bestChange = double.NaN;
|
---|
646 | do {
|
---|
647 | int bestFrom = -1, bestTo = -1;
|
---|
648 | bestChange = double.NaN;
|
---|
649 | for (var j = 0; j < child.Length; j++) {
|
---|
650 | var c = invChild[p2[j]];
|
---|
651 | var n = invChild[p2.GetCircular(j + 1)];
|
---|
652 | if (n - c == 1 || c == child.Length - 1 && n == 0) continue;
|
---|
653 |
|
---|
654 | if (c < n) Shift(child, from: n, to: c + 1);
|
---|
655 | else Shift(child, from: c, to: n);
|
---|
656 | var moveF = eval(child, random);
|
---|
657 | evaluations++;
|
---|
658 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
659 | bestChange = moveF;
|
---|
660 | bestFrom = c < n ? n : c;
|
---|
661 | bestTo = c < n ? c + 1 : n;
|
---|
662 | }
|
---|
663 | // undo
|
---|
664 | if (c < n) Shift(child, from: c + 1, to: n);
|
---|
665 | else Shift(child, from: n, to: c);
|
---|
666 | }
|
---|
667 | if (!double.IsNaN(bestChange)) {
|
---|
668 | Shift(child, bestFrom, bestTo);
|
---|
669 | for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
|
---|
670 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
671 | best = bestChange;
|
---|
672 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
673 | }
|
---|
674 | }
|
---|
675 | } while (!double.IsNaN(bestChange));
|
---|
676 |
|
---|
677 | if (bestChild == null) {
|
---|
678 | best = eval(child, random);
|
---|
679 | evaluations++;
|
---|
680 | }
|
---|
681 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
682 |
|
---|
683 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
684 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
685 |
|
---|
686 | return bestChild ?? child;
|
---|
687 | }
|
---|
688 |
|
---|
689 | public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
|
---|
690 | var maximization = Context.Problem.Maximization;
|
---|
691 | var evaluations = 0;
|
---|
692 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
693 |
|
---|
694 | best = double.NaN;
|
---|
695 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
696 |
|
---|
697 | var invChild = new int[child.Length];
|
---|
698 | var invP2 = new int[child.Length];
|
---|
699 | for (var i = 0; i < child.Length; i++) {
|
---|
700 | invChild[child[i]] = i;
|
---|
701 | invP2[p2[i]] = i;
|
---|
702 | }
|
---|
703 |
|
---|
704 | var bestChange = double.NaN;
|
---|
705 | var moveQueue = new Queue<Tuple<int, int>>();
|
---|
706 | var undoStack = new Stack<Tuple<int, int>>();
|
---|
707 | do {
|
---|
708 | Queue<Tuple<int, int>> bestQueue = null;
|
---|
709 | bestChange = double.NaN;
|
---|
710 | for (var j = 0; j < p2.Length; j++) {
|
---|
711 | if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
|
---|
712 |
|
---|
713 | var a = invChild[p2[j]];
|
---|
714 | var b = invChild[p2.GetCircular(j + 1)];
|
---|
715 | if (a > b) { var h = a; a = b; b = h; }
|
---|
716 | var aprev = a - 1;
|
---|
717 | var bprev = b - 1;
|
---|
718 | while (IsUndirectedEdge(invP2, child.GetCircular(aprev), child.GetCircular(aprev + 1))) {
|
---|
719 | aprev--;
|
---|
720 | }
|
---|
721 | while (IsUndirectedEdge(invP2, child.GetCircular(bprev), child.GetCircular(bprev + 1))) {
|
---|
722 | bprev--;
|
---|
723 | }
|
---|
724 | var bnext = b + 1;
|
---|
725 | var anext = a + 1;
|
---|
726 | while (IsUndirectedEdge(invP2, child.GetCircular(bnext - 1), child.GetCircular(bnext))) {
|
---|
727 | bnext++;
|
---|
728 | }
|
---|
729 | while (IsUndirectedEdge(invP2, child.GetCircular(anext - 1), child.GetCircular(anext))) {
|
---|
730 | anext++;
|
---|
731 | }
|
---|
732 | aprev++; bprev++; anext--; bnext--;
|
---|
733 |
|
---|
734 | if (aprev < a && bnext > b) {
|
---|
735 | if (aprev < 0) {
|
---|
736 | moveQueue.Enqueue(Tuple.Create(a + 1, bnext));
|
---|
737 | moveQueue.Enqueue(Tuple.Create(a + 1, a + 1 + (bnext - b)));
|
---|
738 | } else {
|
---|
739 | moveQueue.Enqueue(Tuple.Create(aprev, b - 1));
|
---|
740 | moveQueue.Enqueue(Tuple.Create(b - 1 - (a - aprev), b - 1));
|
---|
741 | }
|
---|
742 | } else if (aprev < a && bnext == b && bprev == b) {
|
---|
743 | moveQueue.Enqueue(Tuple.Create(a + 1, b));
|
---|
744 | } else if (aprev < a && bprev < b) {
|
---|
745 | moveQueue.Enqueue(Tuple.Create(a + 1, b));
|
---|
746 | } else if (aprev == a && anext == a && bnext > b) {
|
---|
747 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
748 | } else if (aprev == a && anext == a && bnext == b && bprev == b) {
|
---|
749 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
750 | } else if (aprev == a && anext == a && bprev < b) {
|
---|
751 | moveQueue.Enqueue(Tuple.Create(a + 1, b));
|
---|
752 | } else if (anext > a && bnext > b) {
|
---|
753 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
754 | } else if (anext > a && bnext == b && bprev == b) {
|
---|
755 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
756 | } else /*if (anext > a && bprev < b)*/ {
|
---|
757 | moveQueue.Enqueue(Tuple.Create(a, bprev - 1));
|
---|
758 | moveQueue.Enqueue(Tuple.Create(bprev, b));
|
---|
759 | }
|
---|
760 |
|
---|
761 | while (moveQueue.Count > 0) {
|
---|
762 | var m = moveQueue.Dequeue();
|
---|
763 | Opt(child, m.Item1, m.Item2);
|
---|
764 | undoStack.Push(m);
|
---|
765 | }
|
---|
766 | var moveF = eval(child, random);
|
---|
767 | evaluations++;
|
---|
768 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
769 | bestChange = moveF;
|
---|
770 | bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
|
---|
771 | }
|
---|
772 | // undo
|
---|
773 | while (undoStack.Count > 0) {
|
---|
774 | var m = undoStack.Pop();
|
---|
775 | Opt(child, m.Item1, m.Item2);
|
---|
776 | }
|
---|
777 | }
|
---|
778 | if (!double.IsNaN(bestChange)) {
|
---|
779 | while (bestQueue.Count > 0) {
|
---|
780 | var m = bestQueue.Dequeue();
|
---|
781 | Opt(child, m.Item1, m.Item2);
|
---|
782 | }
|
---|
783 | for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
|
---|
784 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
785 | best = bestChange;
|
---|
786 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
787 | }
|
---|
788 | }
|
---|
789 | } while (!double.IsNaN(bestChange));
|
---|
790 |
|
---|
791 | if (bestChild == null) {
|
---|
792 | best = eval(child, random);
|
---|
793 | evaluations++;
|
---|
794 | }
|
---|
795 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
796 |
|
---|
797 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
798 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
799 | return bestChild ?? child;
|
---|
800 | }
|
---|
801 |
|
---|
802 | private static bool IsUndirectedEdge(int[] invP, int a, int b) {
|
---|
803 | var d = Math.Abs(invP[a] - invP[b]);
|
---|
804 | return d == 1 || d == invP.Length - 1;
|
---|
805 | }
|
---|
806 |
|
---|
807 | private static void Swap(Encodings.PermutationEncoding.Permutation child, int from, int to) {
|
---|
808 | Swap2Manipulator.Apply(child, from, to);
|
---|
809 | }
|
---|
810 |
|
---|
811 | private static void Shift(Encodings.PermutationEncoding.Permutation child, int from, int to) {
|
---|
812 | TranslocationManipulator.Apply(child, from, from, to);
|
---|
813 | }
|
---|
814 |
|
---|
815 | private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
|
---|
816 | if (from > to) {
|
---|
817 | var h = from;
|
---|
818 | from = to;
|
---|
819 | to = h;
|
---|
820 | }
|
---|
821 | InversionManipulator.Apply(child, from, to);
|
---|
822 | }
|
---|
823 | }
|
---|
824 | }
|
---|