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

        Comparison between Permutation GOMEA and Biased Random-Key Genetic Algorithm for the Winner Determination Problem in Multi-Combinatorial Auctions

        Thumbnail
        View/Open
        ThesisAndreaScorza.pdf (1.161Mb)
        Publication date
        2021
        Author
        Scorza, A.
        Metadata
        Show full item record
        Summary
        This study presents a comparison between the Gene-pool Optimal Mixing Evolutionary Algorithm for permutation problems (GOMEA) and the Biased RandomKey Genetic Algorithm (BRKGA). The performance of the two algorithms is evaluated on the Winner Determination Problem in Multi-Combinatorial Auctions. The purpose of the study is to understand how well, the linkage tree model on which GOMEA relies, is able to capture and explain the structure of the problem and how well it performs when compared to an algorithm that’s already been proven excellent in solving the aforementioned problem as the BRKGA. To test the algorithms problem instances are generated using the Combinatorial Auction Test Suite (CATS). The test suite is able to generate ad hoc problem instances varying in terms of dimension, hardness, and distribution. Additional FOS models like the Univariate model, for the GOMEA algorithm, are tested and evaluated. GOMEA is also tested with the RKGA and Ordering Messy Genetic Algorithm (OMEGA) on deceptive permutations problems. Results show that GOMEA performs well, especially on harder problem instances when compared to the BRKGA, even though the linkage tree model doesn’t fully represent the problem structure.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/41261
        Collections
        • Theses
        Utrecht university logo