Genetic algorithms applied to problems of forbidden configurations (Q665750)

Summary: A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix \(F\) , we say a (0,1)-matrix \(A\) avoids \(F\) (as a configuration) if there is no submatrix of \(A\) which is a row and column permutation of \(F\) . Let \(A\) denote the number of columns of \(A\). We define forb\((m, F ) = \max\{||A|| : A\) is an \(m\)-rowed simple matrix that avoids \(F\}\). Define an extremal matrix as an m-rowed simple matrix \(A\) with that avoids \(F\) and \(A =\) forb\((m, F)\). We describe the use of Local Search Algorithms (in particular a Genetic Algorithm) for finding extremal matrices. We apply this technique to two forbidden configurations in turn, obtaining a guess for the structure of an \(m \times\) forb\((m,F)\) simple matrix avoiding \(F\) and then proving the guess is indeed correct. The Genetic Algorithm was also helpful in finding the proof.