Free cookie consent management tool by TermsFeed Policy Generator

# Changeset 12288

Ignore:
Timestamp:
04/06/15 22:41:24 (8 years ago)
Message:
• Changed encoding to represent linkages in LLE (as opposed to LLE-e)
• Improved performance of some crossovers
Location:
Files:
12 edited
1 copied

### Legend:

Unmodified
Removed

 r12285 using System; using System.Collections.Generic; using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; for (var i = 0; i < length; i++) { if (endNodes.Contains(i)) continue; if (endNodes.Contains(p1[i]) && endNodes.Contains(p2[i])) { var p1End = endNodes.Contains(p1[i]); var p2End = endNodes.Contains(p2[i]); if ((p1End && p2End) || (!p1End && !p2End)) { child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i]; } else if (endNodes.Contains(p1[i])) { } else if (p1End) { child[i] = p1[i]; } else if (endNodes.Contains(p2[i])) { } else { child[i] = p2[i]; } else { var a = p1[i]; var b = p2[i]; while (true) { if (endNodes.Contains(p2[a])) { child[i] = p2[a]; break; } if (endNodes.Contains(p1[b])) { child[i] = p1[b]; break; } var tmp = b; b = p2[a]; a = p1[tmp]; } } } child.LinearizeTreeStructures(); return child; }

 r12285 public static LinearLinkage Apply(IRandom random, ItemArray parents) { var len = parents[0].Length; var p = random.Next(parents.Length); var child = new LinearLinkage(len); var childGroup = new List>(); var currentParent = random.Next(parents.Length); var remaining = new HashSet(Enumerable.Range(0, len)); var remaining = new SortedSet(Enumerable.Range(0, len)); do { var i = remaining.Min(); var group = new HashSet(parents[currentParent].GetGroupForward(i)); group.IntersectWith(remaining); childGroup.Add(group); remaining.ExceptWith(group); currentParent = (currentParent + 1) % parents.Length; var i = remaining.Min; foreach (var g in parents[p].GetGroupForward(i)) { if (!remaining.Contains(g)) continue; child[i] = g; i = g; remaining.Remove(g); } child[i] = i; remaining.Remove(i); p = (p + 1) % parents.Length; } while (remaining.Count > 0); child.SetGroups(childGroup); return child; }

 r12285 var len = parents[0].Length; var child = new LinearLinkage(len); var childGroup = new List>(); var remaining = new HashSet(Enumerable.Range(0, len)); var remaining = new SortedSet(Enumerable.Range(0, len)); do { var i = remaining.Min(); var groups = parents.Select(x => new HashSet(x.GetGroupForward(i))).ToList(); for (var k = 0; k < groups.Count; k++) groups[k].IntersectWith(remaining); var maxGroup = groups.Select((v, idx) => Tuple.Create(idx, v)).MaxItems(x => x.Item2.Count).SampleRandom(random).Item1; childGroup.Add(groups[maxGroup]); remaining.ExceptWith(groups[maxGroup]); var groups = parents.Select(x => x.GetGroupForward(remaining.Min).Where(y => remaining.Contains(y)).ToList()).ToList(); var max = groups.Select((v, idx) => Tuple.Create(idx, v.Count)).MaxItems(x => x.Item2).SampleRandom(random).Item1; var i = groups[max][0]; for (var k = 1; k < groups[max].Count; k++) { child[i] = groups[max][k]; remaining.Remove(i); i = child[i]; } child[i] = i; remaining.Remove(i); } while (remaining.Count > 0); child.SetGroups(childGroup); return child; }

 r12286

 r12285 namespace HeuristicLab.Encodings.LinearLinkageEncoding { [Item("LinearLinkage", "Represents an LLE-e grouping of items.")] [Item("LinearLinkage", "Represents an LLE grouping of items.")] [StorableClass] public sealed class LinearLinkage : IntArray { /// /// This method parses the encoded array and calculates the membership of each element to the groups. /// It starts at the lowest element. /// /// /// Runtime complexity of this method is O(n) where n is the length of the array. /// This method parses the encoded array and calculates the membership of /// each element to the groups. It starts at the lowest element. /// /// /// Runtime complexity of this method is O(n) where n is the length of the /// array. /// /// An enumeration of all groups. public IEnumerable> GetGroups() { var len = array.Length; var dict = new Dictionary>(); for (var i = 0; i < len; i++) { var end = array[i]; if (end < i || end >= len || array[end] != end) throw new ArgumentException("Array is malformed and does not represent a valid LLE-e encoding."); List list; if (!dict.TryGetValue(end, out list)) dict.Add(end, new List() { i }); else list.Add(i); } return dict.Values; /* This code implements group extraction from LLE forward encoding * var len = array.Length; var remaining = new HashSet(Enumerable.Range(0, len)); // iterate from lowest to highest index } yield return group; }*/ } /// /// This method parses the encoded array and gathers all items that belong to the same group as element . } } /// /// This method parses the encoded array and gathers all items that /// belong to the same group as element . /// /// The element whose group should be returned. /// The element at and all other elements in the same group. /// The element at and all other /// elements in the same group. public IEnumerable GetGroup(int index) { yield return index; var gn = array[index]; for (var i = index + 1; i <= gn; i++) { if (array[i] == gn) yield return i; } for (var i = index - 1; i >= 0; i++) { if (array[i] == gn) yield return i; } /* This code implements group extraction from LLE forward encoding // return current element yield return index; next = prev; yield return next; }*/ } /// /// This method parses the encoded array and gathers the item itself as well as subsequent items that belong to the same group as element . /// /// The element from which items in the group should be returned. /// The element at and all subsequent elements in the same group. } } /// /// This method parses the encoded array and gathers the item itself as /// well as subsequent items that belong to the same group as element /// . /// /// The element from which items in the group should /// be returned. /// The element at and all subsequent /// elements in the same group. public IEnumerable GetGroupForward(int index) { yield return index; var gn = array[index]; for (var i = index + 1; i <= gn; i++) { if (array[i] == gn) yield return i; } /* This code implements group extraction from LLE forward encoding yield return index; var next = array[index]; prev = next; next = array[next]; } while (next != prev);*/ } /// /// This method translates an enumeration of groups into the underlying array representation. /// /// /// Throws an ArgumentException when there is an element assigned to multiple groups or elements that /// are not assigned to any group. /// /// The grouping of the elements, each element must be part of exactly one group. } while (next != prev); } /// /// This method translates an enumeration of groups into the underlying /// array representation. /// /// /// Throws an ArgumentException when there is an element assigned to /// multiple groups or elements that  are not assigned to any group. /// /// The grouping of the elements, each element must /// be part of exactly one group. public void SetGroups(IEnumerable> grouping) { var len = array.Length; var remaining = new HashSet(Enumerable.Range(0, len)); foreach (var group in grouping) { var max = -1; foreach (var g in group.OrderByDescending(x => x)) { if (max < 0) max = g; array[g] = max; remaining.Remove(g); } } if (remaining.Count > 0) throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining))); /* This code implements group setting for LLE forward encoding var len = array.Length; var remaining = new HashSet(Enumerable.Range(0, len)); if (remaining.Count > 0) throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining))); */ } /// /// Performs a check whether the array represents a valid LLE-e encoding. /// /// /// The runtime complexity of this method is O(n) where n is the length of the array. } /// /// Performs a check whether the array represents a valid LLE encoding. /// /// /// The runtime complexity of this method is O(n) where n is the length of /// the array. /// /// True if the encoding is valid. public bool Validate() { var len = array.Length; for (var i = 0; i < len; i++) { var end = array[i]; if (end < i || end >= len || array[end] != end) return false; } return true; /* This code implements group setting for LLE forward encoding var len = array.Length; var remaining = new HashSet(Enumerable.Range(0, len)); } while (next != prev); } return remaining.Count == 0;*/ return remaining.Count == 0; } /// /// This method flattens tree structures that may be present in groups. /// These tree structures may be created by e.g. merging two groups by /// linking one end node to the end node of another. /// Consider following example: 6, 6, 7, 5, 5, 8, 8, 8, 9. /// This results in the following tree structure for group 8: ///      8 ///    /   \ ///   6     7 ///  / \ /// 1   2 /// After this operation the array will be 2, 3, 6, 5, 5, 7, 8, 8, 9. /// /// /// The method first converts the array to LLE-e format and then /// linearizes the links. This requires two passes of the whole array /// as well as a dictionary to hold the smallest index of each group. /// /// The method assumes that there are no back links present. /// public void LinearizeTreeStructures() { // Step 1: Convert the array into LLE-e var length = array.Length; var groups = new Dictionary(); for (var i = length - 1; i >= 0; i--) { if (array[i] == i) groups[i] = i; else array[i] = array[array[i]]; } // Step 2: For all groups linearize the links for (var i = length - 1; i >= 0; i--) { if (array[i] == i) continue; var g = array[i]; array[i] = groups[g]; groups[g] = i; } } }

 r12285 namespace HeuristicLab.Encodings.LinearLinkageEncoding { [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE-e).", "3.3.11.$WCREV$")] [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.3.11.$WCREV$")] [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.3.dll", PluginFileType.Assembly)] [PluginDependency("HeuristicLab.Collections", "3.3")]