Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/Moves/EMSS/ExhaustiveEMSSMoveGenerator.cs @ 15079

Last change on this file since 15079 was 15079, checked in by abeham, 7 years ago

#2666: Added move generators for extract, merge, shift, and split moves and renamed those to EMSS moves, some code cleanup

File size: 3.4 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Optimization;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Encodings.LinearLinkageEncoding {
31  [Item("ExhaustiveEMSSMoveGenerator", "Generates all possible extract, merge, shift, and split (EMSS) moves from a given LLE solution.")]
32  [StorableClass]
33  public class ExhaustiveEMSSMoveGenerator : EMSSMoveGenerator, IExhaustiveMoveGenerator {
34    [StorableConstructor]
35    protected ExhaustiveEMSSMoveGenerator(bool deserializing) : base(deserializing) { }
36    protected ExhaustiveEMSSMoveGenerator(ExhaustiveEMSSMoveGenerator original, Cloner cloner) : base(original, cloner) { }
37    public ExhaustiveEMSSMoveGenerator() : base() { }
38
39    public override IDeepCloneable Clone(Cloner cloner) {
40      return new ExhaustiveEMSSMoveGenerator(this, cloner);
41    }
42
43    protected override EMSSMove[] GenerateMoves(LinearLinkage lle) {
44      int length = lle.Length;
45      if (length == 1) throw new ArgumentException("ExhaustiveEMSSMoveGenerator: There cannot be a move given only one item.", "lle");
46
47      return Generate(lle).ToArray();
48    }
49
50    public static IEnumerable<EMSSMove> GenerateForItem(int i, List<int> groupItems, LinearLinkage lle, int[] lleb) {
51      var pred = lleb[i];
52      var next = lle[i];
53      var isFirst = pred == i;
54      var isLast = next == i;
55
56      // First: shift i into each previous group
57      foreach (var m in groupItems.Where(x => lle[x] != i)) {
58        yield return new ShiftMove(i, pred, m, next, lle[m]);
59      }
60
61      if (!isLast) {
62        // Second: split group at i
63        yield return new SplitMove(i);
64
65        if (isFirst) {
66          // Third: merge with closed groups
67          foreach (var m in groupItems.Where(x => lle[x] == x)) {
68            yield return new MergeMove(i, m);
69          }
70        } else {
71          // Fourth: extract i into group of its own (exclude first and last, because of SplitMove)
72          yield return new ExtractMove(i, pred, next);
73        }
74      }
75    }
76
77    public static IEnumerable<EMSSMove> Generate(LinearLinkage lle) {
78      var groupItems = new List<int>();
79      var lleb = lle.ToBackLinks();
80      for (var i = 0; i < lle.Length; i++) {
81        foreach (var move in GenerateForItem(i, groupItems, lle, lleb))
82          yield return move;
83        if (lleb[i] != i)
84          groupItems.Remove(lleb[i]);
85        groupItems.Add(i);
86      }
87    }
88  }
89}
Note: See TracBrowser for help on using the repository browser.