Genetic algorithms applied to problems of forbidden configurations

R. P. Anstee ; Miguel Raggi

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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 $\mathrm{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}\|=\mathrm{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\mathrm{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.

Détail

DOI : 10.37236/717

Classification : 05D05, 05B20
Mots-clés : trace, forbidden configurations, extremal set theory, (0, 1)-matrices, genetic algorithms