Research On Estimation Of Distribution Algorithm And Its Application In HW/SW Partition

Embedded system has been widely applied into all aspects of people’s work and life. Some functions can be realized by either hardware or software, the two ways have different characteristics. Therefore, how to get the best system performance with the minimum price has become an attractive topic, this is also the problem that hardware/software partitioning need to solve.However, the current inefficient software/hardware partitioning algorithm hampered the wider application of the embedded system. One of popular algorithms is genetic algorithm, which has the building block damage problem in evolutionary process, it made its application greatly restricted. Estimation of distribution algorithm is a new branch of the field of evolutionary computation, it is proposed to solve the problems of building block damage in genetic algorithm, which made up for the inadequacy of genetic algorithm and provides a new effective tool for solving software/hardware partitioning problem.This thesis aims at the hardware/software partitioning of the embedded system, and focuses on the research of the estimation distributed algorithm and its application. The main research work and contributions are as follows:1. In order to resolve the diversity loss problem of estimation distributed algorithm, this paper combined dynamically the estimation of distribution algorithm and genetic algorithm. In each iteration of the proposed algorithm, the population is generated by the two algorithms jointly, the number of individuals of two algorithms change dynamically, the fast convergence of EDA and population diversity of GA is combined. The proposed algorithm is tested and validated by 0/1 knapsack problem, the simulation results show that the algorithm is efficient in optimal value, run time and convergence speed.2. The wrong treatment for some information is an important reason to hinder the performance of estimation of distribution algorithm. The information of previous generation of probability model and inferior solutions were usually discarded in univariate marginal distribution algorithm, but the discarded contents may carries useful information. In order to adress this problem, we proposed a estimation of distribution algorithm using variety of information, the former probability information and the inferior solution information are utilized respectively, added the former probability information when building the probabilistic model, and the inferior solutions is used to construct inferior probability model, which is used to filter the sampled solutions to avoid generating inferior solution. The algorithm is tested by knapsack problem, simulation results show that the former probability information can help improve diversity loss problem effectively, the information of inferior solutions is beneficial to search and improve the convergence reliability.3. We proposed elite clone estimation of distribution algorithm to enhance the local search ability, considering the estimation of distribution algorithm is poor in local search ability. The proposed algorithm made cloning, T transform and the substitution operation for the elite solutions to strengthen the local search ability, the probability model is modified to improve the population diversity loss problem. The algorithm is tested by multi-demension knapsack problem, The results demonstrated that the algorithm can improve local search ability effectively, and maintain the diversity of the population, which is suitable for obtaining the optimal solution or near optimal solution.4. In order to improve the accuracy of probability model and the diversity of solution, we proposed an information recombination multi-objective estimation of distribution algorithm. The selected population is composed of two parts: one consists of good solutions selected by fitness, this part guided algorithm convergence to the pareto optimal front; the other part consist of solutions with the most distant from the inferior solutions, this part ensure the diversity. Then cluster the selected populations and construct probability model of each cluster respectively. And the information entropy is used to guide construct new probability vector from each cluster probability vector, thus get abundant information of parent and protect problem structure. The algorithm is verified by the multi-objective knapsack problem, and the simulation results verify the effectiveness of the algorithm.5. The proposed algorithms were applied to solve different hardware/software partitioning problems. Established mathematical model for single objective single constrained hardware/software partitioning problem, and transfer it into a 0/1 knapsack problem through mathematical transform. Furthermore, we established mathematical model for multi-constrained hardware/software partitioning problem and optimized it by proposed elite clone estimate distribution algorithm, the simulation results were compared with the previous algorithm, which showed that the proposed algorithm can obtain better optimization results under 36 kinds of constraints. For multi-objective partitioning problem, taking JPEG encoder as object, we established mathematical model and solved it by proposed information recombination multi-objective estimation of distribution algorithm, the results showed the proposed algorithm can achieve better results compared to genetic algorithm in previous literatures.This paper is only a preliminary attempt to use estimation of distribution in the hardware /software partitioning problem, there is still a lot of research work in the field. Therefore, we plan to continue to deepen the research on this problem in future work, to make greater achievements.