Genetic algorithms applied to computationally difficult set covering problems

The set covering problem is a known NP-hard combinatorial optimisation problem for covering the rows of a matrix by a subset of columns at minimum cost. Genetic algorithms (GA) are a class of iteration procedures that simulate the evolution process of a structured population. The objective of this work is to show that a somewhat classical GA implementation reaches high quality computational results for difficult set covering problems arising in computing the 1-width of incidence matrices of Steiner triple systems. In computational tests all optimal and best known solutions were found for incidence matrices A₉, A₁₅, A₂₇, A₄₅, A₈₁ and A₂₄₃ with reasonable times for a microcomputer implementation. Other tests with classical set covering problems confirm the good results for an additional class of instances.