Int. J. of Wireless and Mobile Computing   »   2015 Vol.8, No.3

 

 

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

 

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

 

Submission date: 13 Jul 2014
Date of acceptance: 16 Sep 2014
Available online: 13 May 2015

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article