Add LinearLinkageEncoding (LLE)

[abeham]

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).

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.

Item#	1	2	3	4	5	6	7	8	9
Link	2	4	6	9	7	6	8	8	9

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.

The above example identifies the following three groups:

1. { 1, 2, 4, 9 }
2. { 3, 6 }
3. { 5, 7, 8 }

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.

There are different variants:

• LLE is the variant described above
• LLE-b is the same, but with backward links instead of forward links
• LLE-e uses the number of the highest element in the group as group number

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.

References:

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. (​PDF).
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. (​Link).
3. Korkmaz, E.E. 2010. Multi-objective Genetic Algorithms for grouping problems. Applied Intelligence, 33, pp. 179-192. Springer Berlin Heidelberg. (​Link).

[abeham]

r12285: Added branch for linear linkage encoding (LLE-e)