An evolutionary algorithm based on Reed-Muller partition tree model

In order to reduce the evolution time in evolutionary design Boolean functions, we encode the Reed-Muller expression as the chromosome and devise a Reed-Muller Partition Tree Model (RMPT) for decomposition. Moreover, we introduce three operators, i.e. layer evaluation, merisis of partition tree and benign mutation, into the genetic algorithm and adopt bisection test to reduce the time overhead of single chromosome evaluation. Layer evaluation operator picks up the speciality individuals during evolution. Merisis of partition tree operator utilises the complementary of speciality individuals. The ultimate solution is catenated by the evolved slices from different chromosomes. These schemes improve the evolution efficiency. Benign mutation operator explores the search space from two directions simultaneously, which further promotes the performance of the proposed algorithm. The experiments are implemented to evolve functions in various dimensions. The experimental results illustrate that the proposed algorithm decreases the evolution time from exponential complexity to approximately linear complexity, which indicates that the proposed approaches have the capability to address the scalability problem of evolving Boolean functions. Copyright © 2015 Inderscience Enterprises Ltd.