A Memetic Algorithm for Designing Balanced Incomplete Blocks

The generation of balanced incomplete block designs (BIBD) is a hard constrained combinatorial problem whose applications are manifold. Although the BIBD problem can be easily formulated as a combinatorial optimization problem, its resolution still constitutes a formidable challenge for solving techniques. In this work we devise a memetic algorithm (MA) for tackling the BIBD problem. This MA features a heuristic recombination operator based on greedy procedures and a local search method embedded in the evolutionary cycle. An extensive empirical evaluation is done using 86 different instances of the problem. The results indicate that the two mentioned components of the MA contribute synergistically to the performance of the algorithm, whose results are better than those of other metaheuristics such as genetic algorithms, hill climbing, and tabu search (which was the previous incumbent for the problem).