Parallelizing the Linkage Tree Genetic Algorithm and Searching for the Optimal Replacement for the Linkage Tree

Abstract

The recently introduced Linkage Tree Genetic Algorithm (LTGA) has shown to exhibit excellent scalability on a variety of optimization problems. LTGA employs Linkage Trees (LTs) to identify and exploit linkage information between problem variables. In this work we present two parallel implementations of LTGA that enable us to leverage the computational power of a multi-processor architecture. These algorithm extensions for LTGA enable us to solve a problem that previously could not be solved, being the problem of finding high-quality predetermined linkage models that result in a better performance of LTGA for intricate problems by replacing the online-learned LTs. This is done by learning high-quality LTs offline by optimizing LTGAs performance as a function of static LTs. This results in a better performance of LTGA than with online-learned LTs as the problem complexity increases. A parameter-free implementation is used to search optimal subsets of linkage sets in the offline-learned LTs. This pruning of the LT results in a further performance improvement of the LTGA by, on average, removing about 50% of the linkage sets from the offline-learned LTs. This suggests that LTs contain redundancies that may possibly still be exploited to improve the performance of LTGA with online-learned LTs.