Title: An evolutionary algorithm based on Reed-Muller partition tree model

Authors: Jixiang Zhu; Tiefei Zhang

Addresses: College of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, China ' College of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, China

Abstract: 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.

Keywords: evolutionary algorithms; Reed-Muller partition tree; layer evaluation; benign mutation.

DOI: 10.1504/IJWMC.2015.069393

International Journal of Wireless and Mobile Computing, 2015 Vol.8 No.3, pp.301 - 308

Received: 25 Jul 2014
Accepted: 16 Sep 2014

Published online: 14 May 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article