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

Abstract

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.