View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Analyzing the Performance of the Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm on Tree Decomposition Mk Landscapes using Local Optima Networks

        Thumbnail
        View/Open
        Thesis_Master (6) (1).pdf (3.535Mb)
        Publication date
        2023
        Author
        Hoogen, Erik van den
        Metadata
        Show full item record
        Summary
        Abstract This thesis analyses the performance of Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm (LT-GOMEA) on Tree Decomposition Mk Landscapes for problems generated by the benchmark function CliqueTreeMk introduced by Thierens et al. [16]. To understand the challenges faced by LT-GOMEA on these landscapes, the search process is visualized using Local Optima Networks (LONs) introduced by Ochoa et al. [13]. Problems are generated in both a random and deceptive-trap codomain, and the input parameters for CliqueTreeMk are varied to create problems with different characteristics. The main parameter being varied is the overlap between subfunctions, and the number of subfunctions increases as well to maintain a constant problem length. Two implementations of LT-GOMEA are tested: the standard population-based version and a non-population-based version in which the building blocks are learned from a hill-climbed population. For population-based LT-GOMEA, the performance for both codomains increased prior to decreasing with an increase in overlap, but the deceptive-trap codomain performed better at higher overlap. This is thought to be due to a lower number of local optima (than for the random codomain) and decreased deceptiveness with an increase in overlap. The non-population based LT-GOMEA had similar results for the deceptivetrap codomain, but performed poorly on the random codomain with overlap higher than 0, suggesting that an evolving population is necessary to utilize the linkage learning of LT-GOMEA. We also discovered that the intended deceptiveness of the deceptive-trap codomain decreases with overlap, and this could also contribute to the increase in global optima for the deceptive-trap neutral codomain. The findings about the challenges faced by LT-GOMEA are supported by analyzing the search process through the use of LONs. The LONs reveal that problems generated with the same input parameters can vary significantly in difficulty, and gaining a deeper understanding of the reasons behind this variance could improve the effectiveness of CliqueTreeMk as a benchmark function, by being able to more precisely estimate the difficulty of the generated problems.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/43550
        Collections
        • Theses
        Utrecht university logo