Research On Multi-objective Evolutionary Algorithm Based On Decomposition And Its Application In Multiple Sequence Alignment

Multi-objective optimization problems(MOPs) are one of very common optimization problems in real life and practice. The research on multi-objective optimization algorithms has been becoming a hot topic for engineers and scientists. Traditional multi-objective optimization algorithms have strict restrictions in mathematically, such as continuous, differentiable et al., which greatly limit their application scope. With the rise of the evolutionary algorithms at 1990 s, the significant progress has been made in the research of multi-objective optimization algorithms. Multi-objective evolutionary algorithms(MOEAs) are intelligent, have implicit parallelism and adaptability, and low limits for the objective functions. Besides that, MOEAs just need execute only one time to obtain a set of Pareto optimal solutions. MOEA/D(Multi-objective Evolutionary Algorithm based on Decomposition) was recently proposed, which is a decomposition-based multi-objective evolutionary algorithm. Because MOEA/D has simple algorithm framework and outstanding performance, it has been one of most popular multi-objective evolutionary algorithm. Compared with other kinds of MOEAs, MOEA/D has superior performance when confronting with continuous MOPs. However, when solving hard MOPs or MOPs with many objectives, there are still big challenges for MOEA/D.In this dissertation, we focus on the improvement of MOEA/D and how to use MOEA/D to solve MSA. The main attributions of this dissertation are as follows:â‘ In MOEA/D-DRA(MOEA/D with Dynamic Resource Allocation), the utility function may not reasonable dynamic allocate computation resource when solving hard multi-objective optimization problems. In order to overcome this disadvantage, a MOEA/D-DRA with New Utility function(MOEA/D-DRA-NU) is proposed. In the new proposed utility function, two distance measures are computed. The one is the Euclidean distance between origin and the foot of the normal drawn from the individual to the direction vector. Another one is the length of the normal. The decrease of these two distance measures is used to decide to allocate how much computation resource for the sub-problem. The new proposed MOEA/D-DRA-NU is tested on famous UF test suits. Experimental results show that compared with MOEA/D-DRA and MOEA/D-DE, MOEA/D-DRA-NU performs better. Compared with the recent proposed multi-objective evolutionary algorithm MOEA/D-IR, ED/DPP-DRA and MOEA/D-FRRMAB, MOEA/D-DRA-NU costs less time and performs better.â‘¡In real life, decision makers may not need the whole Pareto front, but just a single solution or a few ones. In order to obtain a part of the whole Pareto front to facilitate making decisions, an improved Reference point based Multi-objective Evolutionary Algorithm by Decomposition(RMEAD) is proposed, which is denote IRMEAD for short. This dissertation modifies RMEAD to improve its performance on two aspects: firstly, a novel and simple approach to finding the base weight vectors is developed, the correctness of which is proved mathematically; secondly, a new updating weight vectors method is proposed. Abundant experiments show that IRMEAD can obtain significantly better results than RMEAD on all the test cases in terms of convergence and diversity. Besides, compared with recently proposed preference-based approach MOEA/D-PRE, IRMEAD outperforms it on most of the test instances.â‘¢A novel approach to multiple sequence alignment using multi-objective evolutionary algorithm based on decomposition(MOMSA) is proposed. Firstly, a new MSA model is presented. MSA is viewed as a multi-objective optimization problem. To solve the multi-objective optimization problem, MOEA/D framework is used to be an optimizer. In the MOMSA algorithm, we develop a new population initialization method and a novel mutation operator. We compare the performance of MOMSA with several alignment methods based on evolutionary algorithms, including VDGA, GAPAM, and IMSA, and also with state-of-the-art progressive alignment approaches, such as MSAprobs, Probalign, MAFFT, Procons, Clustal omega, T-Coffee, Kalign2, MUSCLE, FSA, Dialign, PRANK, and CLUSTALW. These alignment algorithms are tested on benchmark datasets BAli BASE 2.0 and BAli BASE 3.0. Experimental results show that MOMSA can obtain the significantly better alignments than VDGA, GAPAM on the most of test cases by statistical analyses, produce better alignments than IMSA in terms of TC scores, and also indicate that MOMSA is comparable with the leading progressive alignment approaches in terms of quality of alignments.