Evolutionary Optimization of Combinatorial Designs


Combinatorial Designs (CD) are a broad class of combinatorial objects whose elements are arranged in order to satisfy certain balancedness properties, and which have applications in several fields such as statistics, coding theory and cryptography. Evolutionary Algorithms (EA) represent an interesting method for constructing CD, for a twofold reason. First, most of the methods published in the literature for designing CD rely on algebraic constructions, which do not offer a great diversity in the generated solutions; on the contrary, since EA ground their exploration only on the definition of a fitness function, they can in principle generate a wide variety of CD. The second reason is that the construction of CD through EA is a rather underdeveloped research thread; indeed, only few works dealing with this topic can be traced in the literature. Therefore, further investigating how EA perform in the search of CD is interesting also from the evolutionary computing perspective, since it could give theoretical insights about the ability of EA in solving a new class of optimization problems. In this talk, we will give a general overview of the works addressing the use of evolutionary techniques to construct several types of combinatorial designs (including orthogonal Latin squares, orthogonal arrays and disjunct matrices), emphasizing the substantial difference in performance between Genetic Algorithms and Genetic Programming in dealing with these optimization problems.

DSSC Seminar
Room 3B, H2bis Building, University of Trieste, Italy