Improved Differential Evolution Algorithm And Its Application In Reversible Logic Synthesis

Evolution algorithms, inspired by biological evolution process in nature, have per-formed well on complex and nonlinear optimization problems. Differential evolution algorithm emerges as a very competitive form of evolution algorithms, which is simple and straightforward to implement, and good at solving global optimization problems. As a result, differential evolution algorithm has become popular. However, its success-ful performance depends on the suitable control parameter settings which may lead to demanding computational costs due to the time-consuming trial-and-error parame-ter tuning process. Besides that, it is slightly bad at solving large scale and complex problems. Well, how to choose suitable control parameter settings and how to improve differential evolution algorithm’s performance on large scale problems are real points to study. Moreover, evolution design has achieved preliminary success in reversible logic synthesis which is a rising field. Therefore, for reducing the constructed redundant designs, it is an urged need to develop a reversible logic synthesis method based on differential evolution algorithm.In this dissertation, the basic principles of evolution algorithms are systematically discussed. Especially, differential evolution algorithm is further studied. Then simple but effective changes are utilized to improve differential evolution algorithm to deliver a more efficient search. The one outcome of this work is a method called differential evolution algorithm with self-adaptive population resizing mechanism (SapsDE). Later, the thesis also extends the SapsDE algorithm with coevolution evolution to solve high dimensional problems. Additionally, for solving reversible logic synthesis, based on SapsDE, a multi-objective coevolutionary differential evolution algorithm (CoMDE) is developed, which, as evolutionary design’s kernel, is utilized to automatically generate reversible circuits. The major contributions in this thesis are as follows.(1)Differential Evolution Algorithm with Self-Adaptive Population Re-sizing Mechanism (SapsDE). Based on the study of differential evolution algorithm, SapsDE is proposed which dynamically chooses one of the two mutation strategies and tunes control parameters in a self-adaptive manner. In detail, firstly, the algo- rithm actives one mutation strategy according to evolution process stage. Secondly, its parameter settings can be determined adaptively according to the previous iteration status. To verify the efficiency of SapsDE, widespread benchmark functions with a wide range of dimensions and diverse complexities are employed. To compare SapsDE with four well-known DE variants, experiment results show that SapsDE is lower time complexity, more effective, efficient and robust one.(2) A coevolution self-adaptive differential evolution algorithm (CoSaDE). In order to solving large scale optimization problems, CoSaDE is proposed to improve SapsDE to solve large scale optimization problem. CoSaDE applies the group adjust-ing scheme which adjusts population scale according evolution process stage in order to balance the exploration and exploitation. Moreover, the optimal collaborator pre-serving scheme is proposed to keep best candidate in the process. The performance of the CoSaDE algorithm is extensively evaluated on a test suite, and it is favorably compared with several state-of-the-art adaptive DE variants and coevolutionary DEs. Even though it is slightly difficult to solve high nonseparable problems, the result shows that CoSaDE has faster convergence speed and more efficient in general.(3)Reversible logic synthesis based on multi-objective differential evo-lution algorithm. Through the study on reversible logic design, reversible logic syn-thesis is modeled as a multi-objective optimization problem. According the characters of the multi-objective problem, a multi-objective coevolutionary differential evolution algorithm (CoMDE) based on SapsDE is proposed. The algorithm employs population updating scheme and fitness evaluation based on Pareto-optimal. The algorithm with network coding strategy and automatic simplification and repair strategies forms a reversible logic synthesis method. The synthesis method is tested on a suite of bench-mark functions in comparison with other synthesis methods. The results show that the proposed synthesis method has a proper improvement on the number of garbage outputs, gate cost and quantum cost.