source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LocalSearch/StaticAPI/ExhaustiveLocalSearch.cs @ 14544

Last change on this file since 14544 was 14544, checked in by abeham, 3 years ago

#2701:

  • LLE: Added equality comparer
  • MemPR:
    • Added GPR to learn about heuristic performance
    • Changed Breeding to do more exhaustive search on crossover
    • Added Delinking separately to Relinking
    • Rewrote d/relinking for LLE
    • Reduce usage of local search
    • Renamed TabuWalk to AdaptiveWalk
    • Rewrote adaptive walk for binary problems
    • Renamed LLE namespace to Grouping to avoid namespace clashes
File size: 8.1 KB
Line 
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
22using System;
23using System.Linq;
24using System.Threading;
25using HeuristicLab.Algorithms.MemPR.Util;
26using HeuristicLab.Collections;
27using HeuristicLab.Core;
28using HeuristicLab.Encodings.LinearLinkageEncoding;
29
30namespace HeuristicLab.Algorithms.MemPR.Grouping.LocalSearch {
31  public static class ExhaustiveLocalSearch {
32    public static Tuple<int, int> Optimize(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token, bool[] subspace = null) {
33      var evaluations = 0;
34      var current = solution;
35      if (double.IsNaN(quality)) {
36        quality = eval(current, random);
37        evaluations++;
38      }
39      var steps = 0;
40      // this dictionary holds the last relevant links
41      var links = new BidirectionalDictionary<int, int>();
42      for (var iter = 0; iter < int.MaxValue; iter++) {
43        var change = false;
44        // clear the dictionary before a new pass through the array is made
45        links.Clear();
46        for (var i = 0; i < current.Length; i++) {
47          if (subspace != null && !subspace[i]) {
48            links.RemoveBySecond(i);
49            links.Add(i, current[i]);
50            continue;
51          }
52          var pred = -1;
53          var isFirst = !links.TryGetBySecond(i, out pred);
54          var keepLink = false;
55          if (!isFirst) {
56            keepLink = subspace != null && !subspace[pred];
57          }
58          var next = current[i];
59          var isLast = next == i;
60
61          if (!keepLink) {
62            // try to insert current into each previous group
63            // first remove i from its group
64            var linksList = links.Where(x => x.Value != i).ToList();
65            if (linksList.Count > 0 && !isFirst) current[pred] = isLast ? pred : next;
66            for (var k = 0; k < linksList.Count; k++) {
67              var l = linksList[k];
68              current[l.Key] = i;
69              current[i] = Math.Max(i, l.Value);
70              var moveF = eval(current, random);
71              evaluations++;
72              if (FitnessComparer.IsBetter(maximization, moveF, quality)) {
73                steps++;
74                quality = moveF;
75                change = true;
76                links.RemoveBySecond(i);
77                links.SetByFirst(l.Key, i); // otherwise the link won't be removed
78                if (!isFirst) links.SetByFirst(pred, isLast ? pred : next);
79                next = current[i];
80                if (next == i) { isLast = true; }
81                pred = l.Key;
82                isFirst = false;
83                break;
84              } else { // undo
85                current[l.Key] = l.Value;
86                if (k == linksList.Count - 1) {
87                  // all attempts unsuccessful
88                  if (!isFirst) current[pred] = i; // undo - readd i to its group
89                  current[i] = next;
90                }
91              }
92            }
93          }
94
95          if (!isLast) {
96            // try to split group at this point
97            // this is safe even if keepLink was true
98            current[i] = i;
99            var moveF = eval(current, random);
100            evaluations++;
101            if (FitnessComparer.IsBetter(maximization, moveF, quality)) {
102              steps++;
103              quality = moveF;
104              change = true;
105              isLast = true;
106              next = i;
107              links.SetBySecond(i, i);
108              continue;
109            } else current[i] = next; // undo
110          }
111
112          if (isFirst && !isLast) {
113            // try merge with all terminated groups
114            foreach (var l in links.Where(x => x.Key == x.Value && (subspace == null || subspace[x.Key]))) {
115              current[l.Key] = i;
116              var moveF = eval(current, random);
117              evaluations++;
118              if (FitnessComparer.IsBetter(maximization, moveF, quality)) {
119                steps++;
120                quality = moveF;
121                change = true;
122                isFirst = false;
123                pred = l.Key;
124                links.SetByFirst(l.Key, i);
125                break;
126              } else {
127                current[l.Key] = l.Value;
128              }
129            }
130          } else if (!isFirst && !keepLink) {
131            // try to extract current into own group
132            current[pred] = isLast ? pred : next;
133            current[i] = i;
134            var moveF = eval(current, random);
135            evaluations++;
136            if (FitnessComparer.IsBetter(maximization, moveF, quality)) {
137              steps++;
138              links.SetByFirst(pred, current[pred]);
139              quality = moveF;
140              change = true;
141            } else { // undo
142              current[pred] = i;
143              current[i] = next;
144            }
145          }
146          links.RemoveBySecond(i);
147          links.Add(i, current[i]);
148          if (token.IsCancellationRequested) break;
149        }
150        if (!change || token.IsCancellationRequested) break;
151      }
152
153      return Tuple.Create(evaluations, steps);
154    }
155
156    public static Tuple<int, int> OptimizeSwapOnly(IRandom random, LinearLinkage solution, ref double quality, bool maximization, Func<LinearLinkage, IRandom, double> eval, CancellationToken token) {
157      var evaluations = 0;
158      var current = solution;
159      if (double.IsNaN(quality)) {
160        quality = eval(current, random);
161        evaluations++;
162      }
163      var groups = current.GetGroups().ToList();
164      var exclude = new bool[groups.Count, groups.Count];
165      var steps = 0;
166      for (var iter = 0; iter < int.MaxValue; iter++) {
167        var change = false;
168        for (var i = 0; i < groups.Count - 1; i++) {
169          for (var j = i + 1; j < groups.Count; j++) {
170            if (exclude[i, j]) continue;
171            var groupsChanged = false;
172            if (groups[i].Count == 1 && groups[j].Count == 1) continue; // groups are anonymous, swap has no effect
173            for (var x = 0; x < groups[i].Count; x++) {
174              for (var y = 0; y < groups[j].Count; y++) {
175                var a = groups[i][x];
176                var b = groups[j][y];
177                groups[i][x] = b;
178                groups[j][y] = a;
179                current.SetGroups(groups);
180                var moveF = eval(current, random);
181                evaluations++;
182                if (FitnessComparer.IsBetter(maximization, moveF, quality)) {
183                  steps++;
184                  quality = moveF;
185                  groupsChanged = true;
186                } else {
187                  // undo
188                  groups[i][x] = a;
189                  groups[j][y] = b;
190                  current.SetGroups(groups);
191                }
192              }
193            }
194            if (!groupsChanged) {
195              exclude[i, j] = true;
196            } else {
197              change = true;
198              for (var k = 0; k < groups.Count; k++) {
199                exclude[k, j] = false;
200                exclude[i, k] = false;
201              }
202            }
203            if (token.IsCancellationRequested) break;
204          }
205          if (token.IsCancellationRequested) break;
206        }
207        if (!change || token.IsCancellationRequested) break;
208      }
209      return Tuple.Create(evaluations, steps);
210    }
211  }
212}
Note: See TracBrowser for help on using the repository browser.