Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14663


Ignore:
Timestamp:
02/11/17 00:53:52 (8 years ago)
Author:
abeham
Message:

#2666: Updated linear linkage encoding

  • Renamed folder from 3.3 to 3.4
  • Added a new static move API for non-swap moves
  • Added conversion to and from LLE-b (back-links)
  • Added tests for moves, conversions and added some missing license headers
Location:
trunk/sources
Files:
8 added
8 edited
1 moved

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab 3.3.sln

    r14475 r14663  
    420420Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4", "HeuristicLab.Algorithms.CMAEvolutionStrategy\3.4\HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4.csproj", "{291010E4-2F4E-4D29-A795-753CFF293FDB}"
    421421EndProject
    422 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.4", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj", "{BE698769-975A-429E-828C-72BB2B6182C8}"
     422Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.4", "HeuristicLab.Encodings.LinearLinkageEncoding\3.4\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj", "{BE698769-975A-429E-828C-72BB2B6182C8}"
    423423EndProject
    424424Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Orienteering-3.3", "HeuristicLab.Problems.Orienteering\3.3\HeuristicLab.Problems.Orienteering-3.3.csproj", "{D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}"

  • trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj

    r14660 r14663  
    177177    <Compile Include="Manipulators\MergeGroupManipulator.cs" />
    178178    <Compile Include="Manipulators\MultiLLEManipulator.cs" />
     179    <Compile Include="Moves\ExtractMove.cs" />
     180    <Compile Include="Moves\MergeMove.cs" />
     181    <Compile Include="Moves\Move.cs" />
     182    <Compile Include="Moves\ShiftMove.cs" />
     183    <Compile Include="Moves\SplitMove.cs" />
     184    <Compile Include="Moves\StaticAPI\MoveGenerator.cs" />
    179185    <Compile Include="Moves\Swap\ExhaustiveSwap2MoveGenerator.cs" />
    180186    <Compile Include="Moves\Swap\StochasticSwap2MultiMoveGenerator.cs" />

  • trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding/3.4/LinearLinkage.cs

    r14475 r14663  
    5959    /// and throws an ArgumentException otherwise.
    6060    /// </remarks>
     61    /// <exception cref="ArgumentException">If <paramref name="lle"/> does not represent a valid LLE array.</exception>
    6162    /// <param name="lle">The LLE representation</param>
     63    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    6264    public static LinearLinkage FromForwardLinks(int[] lle) {
    63       if (!Validate(lle)) {
     65      if (!Validate(lle))
    6466        throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements");
    65       }
    6667      return new LinearLinkage(lle);
     68    }
     69
     70    /// <summary>
     71    /// Create a new LinearLinkage object by parsing a LLE-b representation
     72    /// and modifing the underlying array so that it is in LLE representation.
     73    /// </summary>
     74    /// <remarks>
     75    /// This operation runs in O(n) time, the parameter <paramref name="lleb"/> is not modified.
     76    /// </remarks>
     77    /// <exception cref="ArgumentException">If <paramref name="lleb"/> does not represent a valid LLE-b array.</exception>
     78    /// <param name="lleb">The LLE-b representation (LLE with back-links)</param>
     79    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
     80    public static LinearLinkage FromBackLinks(int[] lleb) {
     81      var result = new LinearLinkage(lleb.Length);
     82      for (var i = lleb.Length - 1; i > 0; i--) {
     83        if (lleb[i] == i) {
     84          if (result[i] == 0) result[i] = i;
     85          continue;
     86        }
     87        result[lleb[i]] = i;
     88        if (result[i] == 0) result[i] = i;
     89      }
     90      if (!Validate(result.array))
     91        throw new ArgumentException("Array is malformed and does not represent a valid LLE-b encoding (with back-links).", "lleb");
     92      return result;
    6793    }
    6894
    … …  
    76102    /// </remarks>
    77103    /// <param name="llee">The LLE-e representation</param>
    78     /// <returns>LinearLinkage</returns>
     104    /// <returns>The linear linkage encoding in LLE format (with forward-links).</returns>
    79105    public static LinearLinkage FromEndLinks(int[] llee) {
    80106      var result = new LinearLinkage(llee.Length);
    … …  
    111137    /// array.
    112138    /// </remarks>
     139    /// <exception cref="InvalidOperationException">If this object is not vaild LLE.</exception>
    113140    /// <returns>An enumeration of all groups.</returns>
    114141    public IEnumerable<List<int>> GetGroups() {
    … …  
    126153          group.Add(curr);
    127154        }
    128         if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
     155        if (curr != next) throw new InvalidOperationException("Array is malformed and does not represent a valid LLE forward encoding.");
    129156        used[curr] = true;
    130157        yield return group;
    131158      }
    132       /*
    133       var len = array.Length;
    134       var used = new bool[len];
    135       // iterate from lowest to highest index
    136       for (var i = 0; i < len; i++) {
    137         if (used[i]) continue;
    138         var group = new List<int> { i };
    139         used[i] = true;
    140         var next = array[i];
    141         if (next < i || next >= len) {
    142           throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    143         }
    144         while (next != array[next]) {
    145           if (next < 0 || next >= len || used[next]) {
    146             throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    147           }
    148           group.Add(next);
    149           used[next] = true;
    150           next = array[next];
    151         }
    152         yield return group;
    153       }*/
    154159    }
    155160
    … …  
    227232    /// <param name="grouping">The grouping of the elements, each element must
    228233    /// be part of exactly one group.</param>
     234    /// <exception cref="ArgumentException">If <paramref name="grouping"/> cannot be converted
     235    /// to a valid LLE representation. For instance, because elements are too big or too small,
     236    /// or they're contained in multiple groups, or there are elements not assigned to any group.
     237    /// </exception>
    229238    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    230239      var len = array.Length;
    … …  
    271280          next = array[next];
    272281        }
    273         if (curr!=next) return false;
     282        if (curr != next) return false;
    274283        used[curr] = true;
    275284      }
    … …  
    281290    /// These tree structures may be created by e.g. merging two groups by
    282291    /// linking one end node to the end node of another.
    283     /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
    284     /// This results in the following tree structure for group 8:
    285     ///      8
     292    /// Consider following array: 5, 5, 6, 4, 4, 7, 7, 7, 8.
     293    /// This results in the following tree structure for group 7:
     294    ///      7
    286295    ///    /   \
    287     ///   6     7
     296    ///   5     6
    288297    ///  / \    |
    289     /// 1   2   3
    290     /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
    291     /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
     298    /// 0   1   2
     299    /// After this operation the array will be 1, 2, 5, 4, 4, 6, 7, 7, 8.
     300    /// Representing a tree with one branch: 0 -> 1 -> 2 -> 5 -> 6 -> 7.
    292301    /// </summary>
    293302    /// <remarks>
    294303    /// The method first converts the array to LLE-e format and then
    295304    /// linearizes the links. This requires two passes of the whole array
    296     /// as well as a dictionary to hold the smallest index of each group.
     305    /// as well as another copy of the underlying array.
    297306    /// The runtime complexity is O(n).
    298307    ///
    … …  
    312321    /// LLE-e is a special format where each element points to the
    313322    /// ending item of a group.
    314     /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become
    315     /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
     323    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7 would become
     324    /// 4, 4, 4, 7, 4, 7, 7, 7 in LLE-e.
    316325    ///
    317326    /// This operation runs in O(n) time.
    318327    /// </remarks>
     328    /// <exception cref="ArgumentException">In case, this object does not
     329    /// represent a valid LLE encoding.
     330    /// </exception>
    319331    /// <returns>An integer array in LLE-e representation</returns>
    320332    public int[] ToEndLinks() {
    … …  
    345357    /// </remarks>
    346358    /// <param name="llee">The LLE-e representation</param>
     359    /// <exception cref="ArgumentException">
     360    /// If <paramref name="llee"/> does not contain a valid LLE-e representation or
     361    /// has a different length to the given instance.
     362    /// </exception>
    347363    public void SetEndLinks(int[] llee) {
    348364      var length = array.Length;
    … …  
    360376          lookup[end] = i;
    361377        } else {
    362           throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee");
    363         }
    364       }
     378          throw new ArgumentException("Array is malformed and does not represent a valid LLE-e end encoding.", "llee");
     379        }
     380      }
     381    }
     382
     383    /// <summary>
     384    /// Creates a copy of the underlying array and turns it into LLE-b.
     385    /// </summary>
     386    /// <remarks>
     387    /// LLE-b is a special format where each element points to the
     388    /// predecessor instead of the successor.
     389    /// The LLE representation 1, 2, 4, 5, 4, 6, 7, 7
     390    /// would become           0, 0, 1, 3, 2, 3, 5, 6 in LLE-b.
     391    ///
     392    /// This operation runs in O(n) time.
     393    /// </remarks>
     394    /// <returns>An integer array in LLE-b representation</returns>
     395    public int[] ToBackLinks() {
     396      var result = new int[array.Length];
     397      var zeroLink = array[0];
     398      for (var i = 0; i < array.Length; i++) {
     399        if (array[i] == i) {
     400          if (result[i] == 0 && i != zeroLink) result[i] = i;
     401          continue;
     402        }
     403        result[array[i]] = i;
     404        if (result[i] == 0 && i != zeroLink) result[i] = i;
     405      }
     406      return result;
    365407    }
    366408  }

  • trunk/sources/HeuristicLab.Problems.Programmable/3.3/HeuristicLab.Problems.Programmable-3.3.csproj

    r14475 r14663  
    149149      <Name>HeuristicLab.Encodings.IntegerVectorEncoding-3.3</Name>
    150150    </ProjectReference>
    151     <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
     151    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.4\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj">
    152152      <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project>
    153153      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name>

  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.LinearLinkageEncoding-3.4/Auxiliary.cs

    r14475 r14663  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.

  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.LinearLinkageEncoding-3.4/ConversionsTest.cs

    r14475 r14663  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2017 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 HeuristicLab.Random;
    225using Microsoft.VisualStudio.TestTools.UnitTesting;
    326
    … …  
    95118      }
    96119    }
     120
     121    [TestMethod]
     122    [TestCategory("Encodings.LinearLinkage")]
     123    [TestProperty("Time", "short")]
     124    public void ConvertFromLLEtoLLEe() {
     125      var random = new MersenneTwister(42);
     126      var lle = MaxGroupsLinearLinkageCreator.Apply(random, 32, 8);
     127      Assert.IsTrue(lle.SequenceEqual(LinearLinkage.FromEndLinks(lle.ToEndLinks())));
     128    }
     129
     130    [TestMethod]
     131    [TestCategory("Encodings.LinearLinkage")]
     132    [TestProperty("Time", "short")]
     133    public void ConvertFromLLEtoLLEb() {
     134      var random = new MersenneTwister(42);
     135      var lle = MaxGroupsLinearLinkageCreator.Apply(random, 32, 8);
     136      Assert.IsTrue(lle.SequenceEqual(LinearLinkage.FromBackLinks(lle.ToBackLinks())));
     137    }
    97138  }
    98139}

  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.LinearLinkageEncoding-3.4/GroupCrossoverTest.cs

    r14475 r14663  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2017 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
    222using HeuristicLab.Random;
    323using HeuristicLab.Tests;

  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r14662 r14663  
    512512    <Compile Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.4\ConversionsTest.cs" />
    513513    <Compile Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.4\GroupCrossoverTest.cs" />
     514    <Compile Include="HeuristicLab.Encodings.LinearLinkageEncoding-3.4\MoveTests.cs" />
    514515    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\Auxiliary.cs" />
    515516    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\CosaCrossoverTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.