Gene expression programming for logic circuit design

Abstract

Finding an optimal solution for the logic circuit design problem is challenging and time-consuming especially for complex logic circuits. As the number of logic gates increases the task of designing optimal logic circuits extends beyond human capability. A number of evolutionary algorithms have been invented to tackle a range of optimisation problems, including logic circuit design. This dissertation explores two of these evolutionary algorithms i.e. Gene Expression Programming (GEP) and Multi Expression Programming (MEP) with the aim of integrating their strengths into a new Genetic Programming (GP) algorithm. GEP was invented by Candida Ferreira in 1999 and published in 2001 [8]. The GEP algorithm inherits the advantages of the Genetic Algorithm (GA) and GP, and it uses a simple encoding method to solve complex problems [6, 32]. While GEP emerged as powerful due to its simplicity in implementation and exibility in genetic operations, it is not without weaknesses. Some of these inherent weaknesses are discussed in [1, 6, 21]. Like GEP, MEP is a GP-variant that uses linear chromosomes of xed length [23]. A unique feature of MEP is its ability to store multiple solutions of a problem in a single chromosome. MEP also has an ability to implement code-reuse which is achieved through its representation which allow multiple references to a single sub-structure. This dissertation proposes a new GP algorithm, Improved Gene Expression Programming (IGEP) which im- proves the performance of the traditional GEP by combining the code-reuse capability and simplicity of gene encoding method from MEP and GEP, respectively. The results obtained using the IGEP and the traditional GEP show that the two algorithms are comparable in terms of the success rate when applied on simple problems such as basic logic functions. However, for complex problems such as one-bit Full Adder (FA) and AND-OR Arithmetic Logic Unit (ALU) the IGEP performs better than the traditional GEP due to the code-reuse in IGEP