Using Messy Genetic Algorithms for Solving the Winner Determination Problem

摘要

The paper presents a study on the application of messy genetic algorithms for the winner determination problem in the combinatorial auction realm. Messy genetic algorithms operate explicitly on building blocks in order to obtain good solutions. Since the winner determination is a constrained problem, the Ordering Messy Genetic Algorithm is used in order to preserve the validity of chromosomes. Experiments on instances generated with the CATS system are presented to illustrate and compare the effectiveness of the approach. The approach is compared against a simple genetic algorithm, which is a random-key genetic algorithm. Other well-known algorithms from literature are used in experiments. Conclusions are drawn on the advantages of using a messy genetic algorithm for this problem.