Free cookie consent management tool by TermsFeed Policy Generator

Changes between Version 2 and Version 3 of Ticket #2319


Ignore:
Timestamp:
04/04/15 17:30:34 (9 years ago)
Author:
abeham
Comment:

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]].
     1LLE 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).
    22
    3 The idea is that a vector holds references to other items in the vector, e.g.
     3The 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.
    44
    55|| Item# || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 ||
    66|| Link  || 2 || 4 || 6 || 9 || 7 || 6 || 8 || 8 || 9 ||
    77
    8 This identifies the following three groups:
     8It 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
     10The above example identifies the following three groups:
    911 1. { 1, 2, 4, 9 }
    1012 2. { 3, 6 }
    1113 3. { 5, 7, 8 }
    1214
    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.
     15The 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.
    1616
    1717There are different variants:
     
    1919 * LLE-b is the same, but with backward links instead of forward links
    2020 * LLE-e uses the number of the highest element in the group as group number
     21
     22Even 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
     24References:
     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]]).