Non-exhaustive search methods and their use in the minimization of Reed-Muller canonical expansions

Abstract

Abstract A number of non-exhaustive search algorithms are presented. The methods are a 'classical' genetic algorithm, a tabu search, an evolutionary strategy and stochastically repeated nearest and steepest-ascent hill-climbing algorithms. They are then used to determine optimum and good polarities for Reed-Muller canonical expansions of Boolean functions, and comparisons are drawn between the relative e effectiveness of each method. Tabu search and nearest-ascent hill-climbers are found to be particularly appropriate for these problems.