Print Email Facebook Twitter Parallelizing the Linkage Tree Genetic Algorithm and Searching for the Optimal Replacement for the Linkage Tree Title Parallelizing the Linkage Tree Genetic Algorithm and Searching for the Optimal Replacement for the Linkage Tree Author De Bokx, R. Contributor Witteveen, C. (mentor) Bosman, P.A.N. (mentor) Faculty Electrical Engineering, Mathematics and Computer Science Department Software Technology Programme Algorithmics Date 2015-08-18 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. Subject paralleloptimizationmodelingLTGALinkage TreeLinkage Tree Genetic Algorithmmodel optimization To reference this document use: http://resolver.tudelft.nl/uuid:6cf6c908-0f5d-4096-b3ad-aa96fd1ff382 Related item http://dl.acm.org/citation.cfm?id=2739482.2764679 Part of collection Student theses Document type master thesis Rights (c) 2015 De Bokx, R. Files PDF thesis.pdf 1.07 MB Close viewer /islandora/object/uuid:6cf6c908-0f5d-4096-b3ad-aa96fd1ff382/datastream/OBJ/view