Evolutionary Design Of Combinational Circuits Based On Improved Genetic Programming

Evovable Hardware(EHW), which combines evolutionary algorithms and programmable devices, is a new reaearch field of hardware design. EHW can reconfigurate its own structure self-adaptively by using the evolutionary technique so to satisfy the design requirement. EHW is in the ascendant and will provide a new circuits design approach when the traditional design methods can't solve the practical design problems.Genetic Programming(GP) is a branch of evolutionary algorithms. GP is based on survival of the fittest theory of Darwinianism. GP starts from a population of programs which describe the solutions of a problem and the solutions are evolved by simulating the process of natural evolution generation by generation until the best solution is finded. The applictions of GP are very extensive, especially the circuits design. A part of study results has shown its great development potential.This paper introduced genetic programming and the method of electronic circuits evolutionary design. A new design method of combinational circuits based on genetic programming is presented. The individuals of GP are represented by multi sub-tree groups in order to match the circuits'structures. According to the individual representation, corresponding genetic operations are established, including improved crossover and mutation operators. In addition, the paper introduces a random individual set in order to improve the quality of a population. Finally the ability of this improved algorithm for finding optimal solution and its covergence speed are improved much. Final evolutionary results are structures of electronic circuits which are easily understandable. The paper introduces a method of fitness evaluation based on true tables. The fitness value of an individual can be gotten through comparing the true table of the individual with the standard true table, which reflects the function of the required circuit. The evolutionary circuits in this paper are combinational circuits. By introducing the module design method, the paper designed an embryo circuits which combines all evolvable functional modules together. Each evolvable module is evolved separately which is the core of the embryo circuit and the whole circuit is designed after the modules evolutionary design finishes. The evolutionary results are inputted into MaxplusII10.2 to simulate their functions. In the experiments, a 1 bit adder and two 2 bits ALU are designed, their simulation resluts shows the method is practicable and the designed circuits are independent on priori knowledge and their functions are satisfying. The comparison experiments proved the presented improved GP speeded up the convergence and improved the ability of GP for finding optimal solution.