Research On Evolutionary Design Algorithms For Digital Circuits

Evolvable hardware (EHW) is the derivant of crossing merging by biology, electronics and computer science. It does not rely on the prior knowledge and manual intervention. It seeks for the structure of electronic circuits and systems by evolution, which satisfys the predetermined requirements, with the feature of self-adaption, self-organizing and self-repairing as organism. As the important branch of EHW, Evolutionary design of circuits (EDC) is implemented based on programmable device. It can provide novel and optimal topologies of circuits by evolution, and realize the automatic design of complex circuits. EDC can help designer to discover and summarize the innovative generalized design rules, and endow the circuits with the feature of fault-tolerant. Furthermore, it is the prerequisite for adaptive and fault-tolerant systems. The brand-new design method for circuits has important theoretical significance and application value to promote the research and realization for EHW.The core of this thesis is to investigate the evolutionary design algorithms for digital circuits, and the main contributions of the present work can be described as follows:1. Evolutionary design for traditional gate-level circuitsIn order to avoid the loss of the potential solution in the chromosome at the stage of fitness evalution, a fitness evaluation expansion based Cartesian genetic programming (CGP) algorithm is studied. By analyzing the effect of the random selection mechanism for circuit outputs on fitness of candidate circuits in traditional CGP, the optimal outputs of the circuits are obtained by means of global search to find the best output nodes. This algorithm accomplishes the expansion of the fitness evaluation, and ensures that the optiml solution of each generation can be discovered in the evolutionary process. To enhance the performance of the genetic algorithm (GA), a novel evolutionary design algorithm for gate-level circuits is proposed by combining the adaptive strategy of genetic operators and fitness evaluation expansion. The proposed algorithm improves the success probability of the evolutionary design methods and the population quality in the evolutionary process, reduces the evolutionary generation. Aiming at improve the scalability while the effectiveness of the evolutionary design methods for multi-ouput digital circuits decreases as the complexity of evolution increases, an expanding multi-chromosome CGP based evolutionary design algorithm for multi-ouput gate-level circuits is presented. The goal of the presented algorithm is to reduce the complexity of evolution. Thereby the multi-chromosome parallel evolution form based on outputs decomposition is utilized. An operation method for chromosome just like cross function in GA is introduced, subsequently the (1+λ) expanding multi-chromosome evolutionary strategy with fitness evaluation expansion is proposed to match the multi-chromosome approach. Compared with traditional evolutionary design algorithms, the proposed algorithm needs less computational effort, has less effect by problem complexity, and improves the scalability.2. Evolutionary design for polymorphic circuitsAn evolutionary design algorithm for polymorphic circuits based on dynamic evaluation is investigated. Considering the feature that the circuit functions under different modes in evolution of polymorphic circuits are evaluated at the same time, first, the fitness evaluation expansion is utilized to accomplish the selection of the optimal outputs for each mode. Second, the circuit structure with the best fitness among all modes is obtained by comparison and selection method, and then the dynamic evaluation process for candidate polymorphic circuits is conducted. The proposed algorithm has advantages of fewer evolutionary generation, higher success probability and lower resource consumption, enhances the validity of the traditional CGP and provides a new fitness evalution method for polymorphic circuits. Moreover, the experiment results show that the polymorphic gates are more close to the outputs of the circuit comparing with the traditional gates.3. Evolutionary design for polymorphic self-checking circuits in fault-tolerant systemsAccording to the fact that actually there are better partial solutions within the circuit structure whose fitness is lower in evolutionary process, an outputs matching based evolutionary design algorithm for polymorphic self-checking circuits is studied. The concept of outputs matching degree is derived. The feature of the circuit outputs in evolution is analyzed, and then the outputs matching method is used to protect the partial optimal solutions and increase the population diversity. The influence to proposed method performance by the setting of mutation probability and matching fitness value is analyzed through experiments. The proposed algorithm reduces the evolutionary genetation, at the same time the self-checking performance of the circuit is not affected. Considering the scalability problem of evolutionary design methods, an algorithm of inputs decomposition and outputs matching based evolutionary design for polymorphic circuits is proposed combining with the outputs matching method. The evolutionary generation is investigated as the increasing input and output number. Then inputs decomposition is utilized as the main means by decomposing and rewriting the truth table to decrease the number of input-output combinations at fitness evaluation stage. The proposed algorithm reduces the complexity of evolution, improves the scalability and gets higher fault detection probability with single test vector while the obtained adders can check all the faults. In order to solve the problem of losing potential solution at fitness evaluation stage by fixed outputs, an evolutionary design algorithm for polymorphic circuit based on dynamic evaluation is studied. The experiment results show that on the premise of ensuring the self-checking performance, the presented algorithm not only decrease the evolutionary generation, but also obtains more succinct circuit structure.