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(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
|
---|
64 | return new PermutationEqualityComparer().Equals(a.Solution, b.Solution);
|
---|
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 <= Context.LocalSearchEvaluations; evaluations++) {
|
---|
401 | var c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution);
|
---|
402 | if (cache.Contains(c)) {
|
---|
403 | cacheHits++;
|
---|
404 | if (cacheHits > 10) break;
|
---|
405 | continue;
|
---|
406 | }
|
---|
407 | var probe = ToScope(c);
|
---|
408 | Evaluate(probe, token);
|
---|
409 | cache.Add(c);
|
---|
410 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
411 | offspring = probe;
|
---|
412 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
413 | break;
|
---|
414 | }
|
---|
415 | }
|
---|
416 | Context.IncrementEvaluatedSolutions(evaluations-1);
|
---|
417 | return offspring;
|
---|
418 | }
|
---|
419 |
|
---|
420 | private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
|
---|
421 | var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
|
---|
422 | var cacheHits = 0;
|
---|
423 | var evaluations = 1;
|
---|
424 | ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
|
---|
425 | for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
|
---|
426 | var c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
|
---|
427 | if (cache.Contains(c)) {
|
---|
428 | cacheHits++;
|
---|
429 | if (cacheHits > 10) break;
|
---|
430 | continue;
|
---|
431 | }
|
---|
432 | var probe = ToScope(c);
|
---|
433 | Evaluate(probe, token);
|
---|
434 | cache.Add(c);
|
---|
435 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
436 | offspring = probe;
|
---|
437 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
438 | break;
|
---|
439 | }
|
---|
440 | }
|
---|
441 | Context.IncrementEvaluatedSolutions(evaluations-1);
|
---|
442 | return offspring;
|
---|
443 | }
|
---|
444 |
|
---|
445 | private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
|
---|
446 | var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
|
---|
447 | var cacheHits = 0;
|
---|
448 | var evaluations = 1;
|
---|
449 | ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
|
---|
450 | for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
|
---|
451 | var c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
|
---|
452 | if (cache.Contains(c)) {
|
---|
453 | cacheHits++;
|
---|
454 | if (cacheHits > 10) break;
|
---|
455 | continue;
|
---|
456 | }
|
---|
457 | var probe = ToScope(c);
|
---|
458 | Evaluate(probe, token);
|
---|
459 | cache.Add(c);
|
---|
460 | if (offspring == null || Context.IsBetter(probe, offspring)) {
|
---|
461 | offspring = probe;
|
---|
462 | if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
|
---|
463 | break;
|
---|
464 | }
|
---|
465 | }
|
---|
466 | Context.IncrementEvaluatedSolutions(evaluations-1);
|
---|
467 | return offspring;
|
---|
468 | }
|
---|
469 |
|
---|
470 | protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
|
---|
471 | if (double.IsNaN(a.Fitness)) Evaluate(a, token);
|
---|
472 | if (double.IsNaN(b.Fitness)) Evaluate(b, token);
|
---|
473 | if (Context.Random.NextDouble() < 0.5)
|
---|
474 | return Context.IsBetter(a, b) ? Relink(a, b, token) : Relink(b, a, token);
|
---|
475 | else return Context.IsBetter(a, b) ? Relink(b, a, token) : Relink(a, b, token);
|
---|
476 | }
|
---|
477 |
|
---|
478 | protected virtual ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> betterScope, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> worseScope, CancellationToken token) {
|
---|
479 | var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope);
|
---|
480 | double quality;
|
---|
481 | return ToScope(Relink(Context.Random, betterScope.Solution, worseScope.Solution, wrapper.Evaluate, out quality));
|
---|
482 | }
|
---|
483 |
|
---|
484 | public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
|
---|
485 | if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
|
---|
486 | switch (p1.PermutationType) {
|
---|
487 | case PermutationTypes.Absolute:
|
---|
488 | return RelinkSwap(random, p1, p2, eval, out best);
|
---|
489 | case PermutationTypes.RelativeDirected:
|
---|
490 | return RelinkShift(random, p1, p2, eval, out best);
|
---|
491 | case PermutationTypes.RelativeUndirected:
|
---|
492 | return RelinkOpt(random, p1, p2, eval, out best);
|
---|
493 | default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
|
---|
494 | }
|
---|
495 | }
|
---|
496 |
|
---|
497 | 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) {
|
---|
498 | var maximization = Context.Problem.Maximization;
|
---|
499 | var evaluations = 0;
|
---|
500 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
501 |
|
---|
502 | best = double.NaN;
|
---|
503 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
504 |
|
---|
505 | var options = Enumerable.Range(0, child.Length).Where(x => child[x] != p2[x]).ToList();
|
---|
506 | var invChild = new int[child.Length];
|
---|
507 | for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
|
---|
508 |
|
---|
509 | //Log(string.Join(", ", child));
|
---|
510 | while (options.Count > 0) {
|
---|
511 | int bestOption = -1;
|
---|
512 | var bestChange = double.NaN;
|
---|
513 | for (var j = 0; j < options.Count; j++) {
|
---|
514 | var idx = options[j];
|
---|
515 | if (child[idx] == p2[idx]) {
|
---|
516 | options.RemoveAt(j);
|
---|
517 | j--;
|
---|
518 | continue;
|
---|
519 | }
|
---|
520 | Swap(child, invChild[p2[idx]], idx);
|
---|
521 | var moveF = eval(child, random);
|
---|
522 | evaluations++;
|
---|
523 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
524 | bestChange = moveF;
|
---|
525 | bestOption = j;
|
---|
526 | }
|
---|
527 | // undo
|
---|
528 | Swap(child, invChild[p2[idx]], idx);
|
---|
529 | }
|
---|
530 | if (!double.IsNaN(bestChange)) {
|
---|
531 | var idx1 = options[bestOption];
|
---|
532 | var idx2 = invChild[p2[idx1]];
|
---|
533 | Swap(child, idx1, idx2);
|
---|
534 | invChild[child[idx1]] = idx1;
|
---|
535 | invChild[child[idx2]] = idx2;
|
---|
536 | //Log(string.Join(", ", child));
|
---|
537 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
538 | if (Dist(child, p2) > 0) {
|
---|
539 | best = bestChange;
|
---|
540 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
541 | }
|
---|
542 | }
|
---|
543 | options.RemoveAt(bestOption);
|
---|
544 | }
|
---|
545 | }
|
---|
546 | if (bestChild == null) {
|
---|
547 | best = eval(child, random);
|
---|
548 | evaluations++;
|
---|
549 | }
|
---|
550 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
551 |
|
---|
552 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
553 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
554 |
|
---|
555 | return bestChild ?? child;
|
---|
556 | }
|
---|
557 |
|
---|
558 | public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
|
---|
559 | var maximization = Context.Problem.Maximization;
|
---|
560 | var evaluations = 0;
|
---|
561 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
562 |
|
---|
563 | best = double.NaN;
|
---|
564 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
565 |
|
---|
566 | var invChild = new int[child.Length];
|
---|
567 | for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
|
---|
568 |
|
---|
569 | var bestChange = double.NaN;
|
---|
570 | do {
|
---|
571 | int bestFrom = -1, bestTo = -1;
|
---|
572 | bestChange = double.NaN;
|
---|
573 | for (var j = 0; j < child.Length; j++) {
|
---|
574 | var c = invChild[p2[j]];
|
---|
575 | var n = invChild[p2.GetCircular(j + 1)];
|
---|
576 | if (n - c == 1 || c == child.Length - 1 && n == 0) continue;
|
---|
577 |
|
---|
578 | if (c < n) Shift(child, from: n, to: c + 1);
|
---|
579 | else Shift(child, from: c, to: n);
|
---|
580 | var moveF = eval(child, random);
|
---|
581 | evaluations++;
|
---|
582 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
583 | bestChange = moveF;
|
---|
584 | bestFrom = c < n ? n : c;
|
---|
585 | bestTo = c < n ? c + 1 : n;
|
---|
586 | }
|
---|
587 | // undo
|
---|
588 | if (c < n) Shift(child, from: c + 1, to: n);
|
---|
589 | else Shift(child, from: n, to: c);
|
---|
590 | }
|
---|
591 | if (!double.IsNaN(bestChange)) {
|
---|
592 | Shift(child, bestFrom, bestTo);
|
---|
593 | for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
|
---|
594 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
595 | best = bestChange;
|
---|
596 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
597 | }
|
---|
598 | }
|
---|
599 | } while (!double.IsNaN(bestChange));
|
---|
600 |
|
---|
601 | if (bestChild == null) {
|
---|
602 | best = eval(child, random);
|
---|
603 | evaluations++;
|
---|
604 | }
|
---|
605 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
606 |
|
---|
607 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
608 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
609 |
|
---|
610 | return bestChild ?? child;
|
---|
611 | }
|
---|
612 |
|
---|
613 | public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
|
---|
614 | var maximization = Context.Problem.Maximization;
|
---|
615 | var evaluations = 0;
|
---|
616 | var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
|
---|
617 |
|
---|
618 | best = double.NaN;
|
---|
619 | Encodings.PermutationEncoding.Permutation bestChild = null;
|
---|
620 |
|
---|
621 | var invChild = new int[child.Length];
|
---|
622 | var invP2 = new int[child.Length];
|
---|
623 | for (var i = 0; i < child.Length; i++) {
|
---|
624 | invChild[child[i]] = i;
|
---|
625 | invP2[p2[i]] = i;
|
---|
626 | }
|
---|
627 |
|
---|
628 | var bestChange = double.NaN;
|
---|
629 | var moveQueue = new Queue<Tuple<int, int>>();
|
---|
630 | var undoStack = new Stack<Tuple<int, int>>();
|
---|
631 | do {
|
---|
632 | Queue<Tuple<int, int>> bestQueue = null;
|
---|
633 | bestChange = double.NaN;
|
---|
634 | for (var j = 0; j < p2.Length; j++) {
|
---|
635 | if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
|
---|
636 |
|
---|
637 | var a = invChild[p2[j]];
|
---|
638 | var b = invChild[p2.GetCircular(j + 1)];
|
---|
639 | if (a > b) { var h = a; a = b; b = h; }
|
---|
640 | var aprev = a - 1;
|
---|
641 | var bprev = b - 1;
|
---|
642 | while (IsUndirectedEdge(invP2, child.GetCircular(aprev), child.GetCircular(aprev + 1))) {
|
---|
643 | aprev--;
|
---|
644 | }
|
---|
645 | while (IsUndirectedEdge(invP2, child.GetCircular(bprev), child.GetCircular(bprev + 1))) {
|
---|
646 | bprev--;
|
---|
647 | }
|
---|
648 | var bnext = b + 1;
|
---|
649 | var anext = a + 1;
|
---|
650 | while (IsUndirectedEdge(invP2, child.GetCircular(bnext - 1), child.GetCircular(bnext))) {
|
---|
651 | bnext++;
|
---|
652 | }
|
---|
653 | while (IsUndirectedEdge(invP2, child.GetCircular(anext - 1), child.GetCircular(anext))) {
|
---|
654 | anext++;
|
---|
655 | }
|
---|
656 | aprev++; bprev++; anext--; bnext--;
|
---|
657 |
|
---|
658 | if (aprev < a && bnext > b) {
|
---|
659 | if (aprev < 0) {
|
---|
660 | moveQueue.Enqueue(Tuple.Create(a + 1, bnext));
|
---|
661 | moveQueue.Enqueue(Tuple.Create(a + 1, a + 1 + (bnext - b)));
|
---|
662 | } else {
|
---|
663 | moveQueue.Enqueue(Tuple.Create(aprev, b - 1));
|
---|
664 | moveQueue.Enqueue(Tuple.Create(b - 1 - (a - aprev), b - 1));
|
---|
665 | }
|
---|
666 | } else if (aprev < a && bnext == b && bprev == b) {
|
---|
667 | moveQueue.Enqueue(Tuple.Create(a + 1, b));
|
---|
668 | } else if (aprev < a && bprev < b) {
|
---|
669 | moveQueue.Enqueue(Tuple.Create(a + 1, b));
|
---|
670 | } else if (aprev == a && anext == a && bnext > b) {
|
---|
671 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
672 | } else if (aprev == a && anext == a && bnext == b && bprev == b) {
|
---|
673 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
674 | } else if (aprev == a && anext == a && bprev < b) {
|
---|
675 | moveQueue.Enqueue(Tuple.Create(a + 1, b));
|
---|
676 | } else if (anext > a && bnext > b) {
|
---|
677 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
678 | } else if (anext > a && bnext == b && bprev == b) {
|
---|
679 | moveQueue.Enqueue(Tuple.Create(a, b - 1));
|
---|
680 | } else /*if (anext > a && bprev < b)*/ {
|
---|
681 | moveQueue.Enqueue(Tuple.Create(a, bprev - 1));
|
---|
682 | moveQueue.Enqueue(Tuple.Create(bprev, b));
|
---|
683 | }
|
---|
684 |
|
---|
685 | while (moveQueue.Count > 0) {
|
---|
686 | var m = moveQueue.Dequeue();
|
---|
687 | Opt(child, m.Item1, m.Item2);
|
---|
688 | undoStack.Push(m);
|
---|
689 | }
|
---|
690 | var moveF = eval(child, random);
|
---|
691 | evaluations++;
|
---|
692 | if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
|
---|
693 | bestChange = moveF;
|
---|
694 | bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
|
---|
695 | }
|
---|
696 | // undo
|
---|
697 | while (undoStack.Count > 0) {
|
---|
698 | var m = undoStack.Pop();
|
---|
699 | Opt(child, m.Item1, m.Item2);
|
---|
700 | }
|
---|
701 | }
|
---|
702 | if (!double.IsNaN(bestChange)) {
|
---|
703 | while (bestQueue.Count > 0) {
|
---|
704 | var m = bestQueue.Dequeue();
|
---|
705 | Opt(child, m.Item1, m.Item2);
|
---|
706 | }
|
---|
707 | for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
|
---|
708 | if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
|
---|
709 | best = bestChange;
|
---|
710 | bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
|
---|
711 | }
|
---|
712 | }
|
---|
713 | } while (!double.IsNaN(bestChange));
|
---|
714 |
|
---|
715 | if (bestChild == null) {
|
---|
716 | best = eval(child, random);
|
---|
717 | evaluations++;
|
---|
718 | }
|
---|
719 | Context.IncrementEvaluatedSolutions(evaluations);
|
---|
720 |
|
---|
721 | if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
|
---|
722 | if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
|
---|
723 | return bestChild ?? child;
|
---|
724 | }
|
---|
725 |
|
---|
726 | private static bool IsUndirectedEdge(int[] invP, int a, int b) {
|
---|
727 | var d = Math.Abs(invP[a] - invP[b]);
|
---|
728 | return d == 1 || d == invP.Length - 1;
|
---|
729 | }
|
---|
730 |
|
---|
731 | private static void Swap(Encodings.PermutationEncoding.Permutation child, int from, int to) {
|
---|
732 | Swap2Manipulator.Apply(child, from, to);
|
---|
733 | }
|
---|
734 |
|
---|
735 | private static void Shift(Encodings.PermutationEncoding.Permutation child, int from, int to) {
|
---|
736 | TranslocationManipulator.Apply(child, from, from, to);
|
---|
737 | }
|
---|
738 |
|
---|
739 | private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
|
---|
740 | if (from > to) {
|
---|
741 | var h = from;
|
---|
742 | from = to;
|
---|
743 | to = h;
|
---|
744 | }
|
---|
745 | InversionManipulator.Apply(child, from, to);
|
---|
746 | }
|
---|
747 | }
|
---|
748 | }
|
---|