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