Deriving Smaller Orthogonal Arrays from Bigger Ones with Genetic Algorithm
This is an incremental improvement for researchers in combinatorial design and optimization, focusing on a specific construction method for orthogonal arrays.
The paper tackles the problem of constructing smaller binary orthogonal arrays from larger ones by removing lines, using a genetic algorithm with constant-weight binary chromosomes and balanced operators. The result is a preliminary experimental validation showing the algorithm can find optimal solutions when starting from specially crafted initial arrays.
We consider the optimization problem of constructing a binary orthogonal array (OA) starting from a bigger one, by removing a specified amount of lines. In particular, we develop a genetic algorithm (GA) where the underlying chromosomes are constant-weight binary strings that specify the lines to be cancelled from the starting OA. Such chromosomes are then evolved through balanced crossover and mutation operators to preserve the number of ones in them. The fitness function evaluates the matrices obtained from these chromosomes by measuring their distance from satisfying the constraints of an OA smaller than the starting one. We perform a preliminary experimental validation of the proposed genetic algorithm by crafting the initial OA as a random permutation of several blocks of the basic parity-check array, thereby guaranteeing the existence of an optimal solution.