Representation issue in graph coloring

Linear Linkage Encoding (LLE) is a powerful encoding scheme utilized when genetic algorithms (GAs) are applied to grouping problems. It discards the redundancy of other traditional encoding schemes. However, some genetic operators are quite costly in terms of computational time when LLE is utilized....

Full description

Saved in:
Bibliographic Details
Main Authors: Yilmaz, B, Korkmaz, E E
Format: Conference Proceeding
Language:English
Subjects:
Biological cells
Color
Couplings
Encoding
Genetics
graph coloring
Indexes
multi-objective genetic algorithm
Redundancy
representation scheme
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Linear Linkage Encoding (LLE) is a powerful encoding scheme utilized when genetic algorithms (GAs) are applied to grouping problems. It discards the redundancy of other traditional encoding schemes. However, some genetic operators are quite costly in terms of computational time when LLE is utilized. In this study, two supplementary encoding schemes Linear Linkage Encoding with Ending Node Links (LLE-e) and Linear Linkage Encoding with Backward Links (LLE-b) are designed and used together with LLE. When a genetic operator is costly in LLE, the operation is carried out on one of the supplementary encodings and the result is reflected back to LLE. The algorithm is implemented in a Multi Objective Genetic Algorithm (MOGA) framework and various tests are carried out on Graph coloring Problem (GCP) instances obtained from DIMACS Challenge Suite. A performance improvement has been obtained when both supplementary encoding schemes are included in the algorithm.
ISSN:2164-7143
2164-7151
DOI:10.1109/ISDA.2010.5687028