NON-EXHAUSTIVE SEARCH METHODS AND THEIR USE IN THE MINIMIZATION OF REED-MULLER CANONICAL EXPANSIONS

A number of non-exhaustive search algorithms are presented. The method s 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 effectiveness of each m ethod. Tabu search and nearest-ascent hill-climbers are found to be pa rticularly appropriate for these problems.