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 A9, A15, A27, A45, A81 and A243 with reasonable times for a microcomputer implementation. Other tests with classical set covering problems confirm the good results for an additional class of instances.