Sitting guest at a wedding party : experiments on genetic and evolutionary constrained optimization

Abstract

The complex task of giving out tables to guests, according to their preferences, at a wedding party, instantiates a broader class of clustering problems, whose purpose is to group a number of entities into a number of clusters, according to a set of hard constraints, and optimizing an objective function.

In order to study the application of Genetic and Evolutionary Algorithms (GEAs) to these class of problems, some experiments were conducted. These contemplated different approaches to constraint handling, namely the use of penalty functions and decoders. The encoding issue was also studied, being compared direct and indirect representations of the problem's solutions in the chromosomes. The development of hybrid genetic operators, that combine the synergies of the GEAs paradigm with those of problem dependent heuristics, were also taken into account.

The overall result is a study on the performance of several approaches to constrained optimization by GEAs, that can be used to guide the application of the paradigm in real-world problems, in the Combinatorial Optimization arena.