Changeset 12396


Ignore:
Timestamp:
05/21/15 16:30:14 (7 years ago)
Author:
abeham
Message:

#2319: Added SinglePointCrossover

Location:
branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj

    r12288 r12396  
    107107    <Compile Include="Crossovers\LowestIndexMaxCrossover.cs" />
    108108    <Compile Include="Crossovers\MultiLLECrossover.cs" />
     109    <Compile Include="Crossovers\SinglePointCrossover.cs" />
    109110    <Compile Include="Interfaces\ILinearLinkageCreator.cs" />
    110111    <Compile Include="LinearLinkage.cs" />
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

    r12288 r12396  
    182182    /// These tree structures may be created by e.g. merging two groups by
    183183    /// linking one end node to the end node of another.
    184     /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9.
     184    /// Consider following 1-based index array: 6, 6, 7, 5, 5, 8, 8, 8, 9.
    185185    /// This results in the following tree structure for group 8:
    186186    ///      8
    187187    ///    /   \
    188188    ///   6     7
    189     ///  / \
    190     /// 1   2
     189    ///  / \    |
     190    /// 1   2   3
    191191    /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9.
     192    /// Representing a tree with one branch: 1 -> 2 -> 3 -> 6 -> 7 -> 8
    192193    /// </summary>
    193194    /// <remarks>
     
    195196    /// linearizes the links. This requires two passes of the whole array
    196197    /// as well as a dictionary to hold the smallest index of each group.
     198    /// The runtime complexity is O(n).
    197199    ///
    198200    /// The method assumes that there are no back links present.
     
    200202    public void LinearizeTreeStructures() {
    201203      // Step 1: Convert the array into LLE-e
     204      ToLLEeInplace(array);
     205      // Step 2: For all groups linearize the links
     206      FromLLEe(array);
     207    }
     208
     209    /// <summary>
     210    /// Creates a copy of the underlying array and turns it into LLE-e.
     211    /// </summary>
     212    /// <remarks>
     213    /// LLE-e is a special format where each element points to the
     214    /// ending item of a group.
     215    /// The LLE representation 2, 3, 5, 6, 5, 7, 8, 8 would become
     216    /// 5, 5, 5, 8, 5, 8, 8, 8 in LLE-e.
     217    ///
     218    /// This operation runs in O(n) time.
     219    /// </remarks>
     220    /// <returns>An integer array in LLE-e representation</returns>
     221    public int[] ToLLEe() {
     222      var result = (int[])array.Clone();
     223      ToLLEeInplace(result);
     224      return result;
     225    }
     226
     227    private void ToLLEeInplace(int[] a) {
     228      var length = a.Length;
     229      for (var i = length - 1; i >= 0; i--) {
     230        if (array[i] == i) a[i] = i;
     231        else a[i] = a[a[i]];
     232      }
     233    }
     234
     235    /// <summary>
     236    /// Parses an LLE-e representation and modifies the underlying array
     237    /// so that it is in LLE representation.
     238    /// </summary>
     239    /// <remarks>
     240    /// This operation runs in O(n) time, but requires additional memory
     241    /// in form of a dictionary.
     242    /// </remarks>
     243    /// <param name="llee">The LLE-e representation</param>
     244    public void FromLLEe(int[] llee) {
    202245      var length = array.Length;
    203246      var groups = new Dictionary<int, int>();
    204247      for (var i = length - 1; i >= 0; i--) {
    205         if (array[i] == i) groups[i] = i;
    206         else array[i] = array[array[i]];
    207       }
    208       // Step 2: For all groups linearize the links
    209       for (var i = length - 1; i >= 0; i--) {
    210         if (array[i] == i) continue;
    211         var g = array[i];
    212         array[i] = groups[g];
    213         groups[g] = i;
     248        if (llee[i] == i) {
     249          array[i] = i;
     250          groups[i] = i;
     251        } else {
     252          var g = llee[i];
     253          array[i] = groups[g];
     254          groups[g] = i;
     255        }
    214256      }
    215257    }
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/GraftManipulator.cs

    r12288 r12396  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
    26 using HeuristicLab.Data;
    27 using HeuristicLab.Parameters;
    2826using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2927
     
    3331  public sealed class GraftManipulator : LinearLinkageManipulator {
    3432
    35     public IValueLookupParameter<IntValue> MaxGroupsParameter {
    36       get { return (IValueLookupParameter<IntValue>)Parameters["MaxGroups"]; }
    37     }
    38 
    3933    [StorableConstructor]
    4034    private GraftManipulator(bool deserializing) : base(deserializing) { }
    4135    private GraftManipulator(GraftManipulator original, Cloner cloner) : base(original, cloner) { }
    42     public GraftManipulator() {
    43       Parameters.Add(new ValueLookupParameter<IntValue>("MaxGroups", "The maximum number of groups. If a value less or equal than 0 is used the number of groups is not limited.", new IntValue(-1)));
    44     }
    45     public GraftManipulator(int maxGroups)
    46       : this() {
    47       MaxGroupsParameter.Value = new IntValue(maxGroups);
    48     }
     36    public GraftManipulator() { }
    4937
    5038    public override IDeepCloneable Clone(Cloner cloner) {
     
    5240    }
    5341
    54     public static void Apply(IRandom random, LinearLinkage lle, int maxGroups) {
     42    public static void Apply(IRandom random, LinearLinkage lle) {
    5543      int tries = lle.Length;
    5644      var index = random.Next(lle.Length);
     
    5947        tries--;
    6048      }
    61       if (lle[index] != index) Apply(random, lle, maxGroups, index);
     49      if (lle[index] != index) Apply(random, lle, index);
    6250    }
    6351
    64     public static void Apply(IRandom random, LinearLinkage lle, int maxGroups, int index) {
     52    public static void Apply(IRandom random, LinearLinkage lle, int index) {
    6553      var groups = lle.Select((val, idx) => Tuple.Create(idx, val))
    6654                      .Where(x => x.Item1 == x.Item2)
     
    8472
    8573    protected override void Manipulate(IRandom random, LinearLinkage lle) {
    86       var maxGroups = MaxGroupsParameter.ActualValue.Value;
    87       Apply(random, lle, maxGroups <= 0 ? int.MaxValue : maxGroups);
     74      Apply(random, lle);
    8875    }
    8976  }
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/MergeGroupManipulator.cs

    r12286 r12396  
    2828
    2929namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    30   [Item("Merge Group Manipulator", "Performs a maximum of N merge operations on the groups. Groups may be merged multiple times.")]
     30  [Item("Merge Group Manipulator", "Performs a maximum of N merge operations on the groups. An already merged group may be merged again.")]
    3131  [StorableClass]
    3232  public sealed class MergeGroupManipulator : LinearLinkageManipulator {
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/MoveItemManipulator.cs

    r12286 r12396  
    2929
    3030namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    31   [Item("Move Item Manipulator", "Performs a maximum of N move operations between groups or to new groups. Items may be moved multiple times.")]
     31  [Item("Move Item Manipulator", "Performs a maximum of N move operations between groups or to new groups. An already moved item may be moved again.")]
    3232  [StorableClass]
    3333  public sealed class MoveItemManipulator : LinearLinkageManipulator {
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SplitGroupManipulator.cs

    r12286 r12396  
    3131
    3232namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    33   [Item("Split Group Manipulator", "Performs a maximum of N split operations on the groups. Groups may be split multiple times.")]
     33  [Item("Split Group Manipulator", "Performs a maximum of N split operations on the groups. An already split group may be split again.")]
    3434  [StorableClass]
    3535  public sealed class SplitGroupManipulator : LinearLinkageManipulator {
  • branches/LinearLinkage/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Manipulators/SwapItemManipulator.cs

    r12286 r12396  
    2828
    2929namespace HeuristicLab.Encodings.LinearLinkageEncoding {
    30   [Item("Swap Item Manipulator", "Swaps items between groups. Items may be swapped multiple times.")]
     30  [Item("Swap Item Manipulator", "Performs N swaps operations of two items each. The same items may be swapped multiple times, at least two groups need to be present.")]
    3131  [StorableClass]
    3232  public sealed class SwapItemManipulator : LinearLinkageManipulator {
Note: See TracChangeset for help on using the changeset viewer.