Changes between Version 2 and Version 3 of Ticket #2319
- Timestamp:
- 04/04/15 17:30:34 (10 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Ticket #2319
- Property Summary changed from Add LinearLinkageEncoding to Add LinearLinkageEncoding (LLE)
-
Ticket #2319 – Description
v2 v3 1 It is a better suited encoding for grouping problems [[http://www.cs.nott.ac.uk/~exo/docs/publications/llePATAT06.pdf|link]].1 LLE is a better suited encoding for grouping problems than a simple IntegerVector (= group number encoding or GNE) or a more complex IntegerVector with items that may appear only once and others that function as separators (= permutation with repetition or PWR). 2 2 3 The idea is that a vector holds references to other items in the vector, e.g.3 The idea of LLE is that the group is defined such that one item references another. LLE can be implemented in the form of a vector where the index denotes the item and the value denotes the item that is referenced, e.g. 4 4 5 5 || Item# || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 6 6 || Link || 2 || 4 || 6 || 9 || 7 || 6 || 8 || 8 || 9 || 7 7 8 This identifies the following three groups: 8 It is further important that an item must only link to an item with higher or equal index. If an item references itself it is called an ending item which is the last in the group. It is also not allowed that two items link to the same item which would create a tree-like structure. An item must only be linked from exactly one other item (or from itself). The consequence is that except for ending items all numbers appear at most once in the vector. 9 10 The above example identifies the following three groups: 9 11 1. { 1, 2, 4, 9 } 10 12 2. { 3, 6 } 11 13 3. { 5, 7, 8 } 12 14 13 The advantage over a numbered encoding of groups (e.g. an integer vector that assigns a group number to each item) is that there are no ambiguities regarding a change in the group numbers. Typically, for anonymous groups, exchanging all items of group 1 to be group 2 and those of group 2 to be group 1 would not create a different solution. But in e.g. a population-based approach these would be considered as different genes. 14 15 To avoid further ambiguities, the link for an item must always be greater than or equal to its index. And with the exception of the ending items (where item# equals link) no number must occur more than once as link. 15 The advantage over GNE or PWR is that the group is an emerging concept of the structure and not directly encoded in the vector. Thus, the ambiguities that are created by GNE and the larger solution space that comes with PWR can be avoided. 16 16 17 17 There are different variants: … … 19 19 * LLE-b is the same, but with backward links instead of forward links 20 20 * LLE-e uses the number of the highest element in the group as group number 21 22 Even though LLE-e may be similar to GNE the difference is that the group number is not directly encoded and given by the largest element in the group. GNE or PWR would still make sense in the case groups have an identity and cannot be considered equal. 23 24 References: 25 1. Ülker, Ö., Özcan, E., and Korkmaz, E.E. 2006. Linear Linkage Encoding in Grouping Problems: Applications on Graph Coloring and Timetabling. In Practice and Theory of Automated Timetabling VI, pp. 347-363. Springer Berlin Heidelberg. ([[http://www.cs.nott.ac.uk/~exo/docs/publications/llePATAT06.pdf|PDF]]). 26 2. Yilmaz, B., and Korkmaz, E.E. 2010. Representation Issue In Graph Coloring. In Proceedings of the 10th International Conference on Intelligent Systems Design and Applications, pp. 1171-1176. IEEE. ([[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=5687028|Link]]). 27 3. Korkmaz, E.E. 2010. Multi-objective Genetic Algorithms for grouping problems. Applied Intelligence, 33, pp. 179-192. Springer Berlin Heidelberg. ([[http://link.springer.com/article/10.1007%2Fs10489-008-0158-3|Link]]).
