Many-Objective Optimization Algorithm With Its Applications In Optimal Software Product Selection

Many-objective optimization problems(MaOPs)exist widely in practical applications.In MaOPs,there are usually more than three optimization ob-jectives.Currently,one of the hot yet difficult research topics is how to solve MaOPs effectively.For many-objective optimization,there are some difficulties that should be well addressed.For example,the estimation of the density of individuals may be incorrect;the conflict between convergence and diversity is aggravated;the search directions may be difficult to adapt to the shapes of the Pareto front(PF),and the recombination operators may be ineffective.In this thesis,we propose some simple yet effective many-objective optimization algorithms by dealing with some of the above difficulties.A huge number of test problems are used to verify and compare these new proposals with state-of-the-art algorithms.To promote the practical applications of the proposed many-objective optimization algorithms,we choose the optimal product selec-tion problem from software product lines as a real application scenario.By combing the proposed algorithmic framework with satisfiability(SAT)solver-s,we develop new techniques that are able to quickly and effectively solve the many-objective optimal product selection problems.In the thesis,we first design many-objective optimization algorithms,then conduct simulation ex-periments and finally apply them in practice.In other words,the algorithm design is combined with practical applications.To summary,we obtain the following research results.1.The VaEA algorithm based on angle.In the algorithm,the angle is used to estimate the density of an individual.On the basis of this,the"maximum-angle-first" principle is developed to promote the diversity of the solution set.In addition,the "worse-elimination" principle is in-troduced to keep a balance between convergence and diversity.In this principle,worse solutions in terms of the convergence are allowed to be replaced by other individuals if the distribution of the solutions satis-fies a certain condition.The proposed method is compared with other state-of-the-art many-objective evolutionary algorithms on a number of test problems with up to 15 objectives.The experimental results have shown that VaEA is effective in keeping a good balance between conver-gence and diversity.Furthermore,it was shown by the results on two problems from practice(with irregular PFs)that the VaEA algorithm sig-nificantly outperforms its competitors in terms of the diversity of the final solution sets,strongly demonstrating the effectiveness of using angle to estimate the density of an individual.It is worth mentioning that the new algorithm has the following good properties:it is free from a set of supplied weight vectors;it has less algorithmic parameters;and the time complexity of the algorithm is not high.2.The MaPSO algorithm with leaders selected from historical solutions by using scalar projections.In the design of a multi-/many-objective particle swarm optimizer(PSO),the selection of leaders is a crucial issue.In MaPSO,the leader for each particle is selected from historical solutions by using scalar projections.For each particle,MaPSO maintains a certain number of historical solutions,which record potential search directions in the objective space.The leader is defined as the solution that has the maximum scalar projection in the direction determined by the nadir point and the point constructed by the objective vector of the current particle.This definition ensures that the leader is the historical solution that is closest to the PF along the aforementioned direction.In the environmental selection,MaPSO implicitly divides the whole optimization process into different phases.In the earlier phase,the convergence of solutions is emphasized.As the iteration proceeds,more emphases are gradually put on the diversity.The simulation experiments are performed on a number of test problems.As demonstrated,MaPSO is superior to other state-of-the-art algorithms in most cases.Finally,the effectiveness and efficiency of the new leader selection strategy are also experimentally verified.3.A decomposition-based many-objective artificial bee colony algorith-m MOABC/D.This is a hybrid algorithm of the decomposition-based algorithmic framework(i.e.,MOEA/D)and artificial bee colony(ABC)algorithm.In MOABC/D,a many-objective optimization problem is con-verted into a number of subproblems which are simultaneously optimized by a modified ABC algorithm.Aided by a set of weight vectors,the MOEA/D framework could maintain diversity among solutions,while the ABC algorithm,with a fast convergence speed,is highly effective when solving scalar optimization problems.Therefore,the new algorith-m would be effective in balancing convergence and diversity.Moreover,subproblems in the proposed algorithm are handled unequally,and com-putational resources are dynamically allocated according to the degree of difficulty of subproblems through specially designed onlooker bees and scout bees.The proposed algorithm is compared with five state-of-the-art many-objective evolutionary algorithms on 13 test problems with up to 50 objectives.It is shown by the experimental results that the proposed al-gorithm performs better than or comparably to other algorithms in terms of both the quality of the final solution set and the efficiency of the algo-rithms.Finally,as demonstrated by the experimental results,the onlooker bees and scout bees indeed contribute to performance improvements of the new algorithm.4.The SATVaEA algorithm for the many-objective optimal software prod-uct selection problem.A feature model is a compact representation of the information of all possible products from software product lines.The aim of the optimal product selection is to choose target products that satisfy one or more optimization objectives from all the software prod-ucts.The many-objective optimal product selection problem under study has a large and highly constrained search space.By combining VaEA with two different satisfiability(SAT)solvers,the proposed SATVaEA is an effective new technique for handling many-objective optimal prod-uct selection problems.In SATVaEA,the search of VaEA is enhanced by two SAT solvers:One is a stochastic local search based SAT solver that can quickly repair infeasible software products,while the other is a conflict-driven clause learning SAT solver that is introduced to generate diversified products.We evaluate SATVaEA on 21 feature models with up to 62,482 features,including two models with realistic values for fea-ture attributes.The experimental results are promising,with SATVaEA returning 100%valid products on almost all the feature models.For mod-els with more than 10,000 features,the search in SATVaEA takes only a few minutes to find a large proportion of valid software products.Concern-ing both effectiveness and efficiency,SATVaEA significantly outperforms other state-of-the-art algorithms.5.Further studies on many-objective optimal software product selection.First,we investigate the effect of different SAT solvers on the performance of SATVaEA.In fact,the fast WalkSAT is used in the local search phase of SATVaEA.To make comparisons,we select a probability-based SAT solver(i.e.,ProbSAT)to conduct experiments.As shown by the experimental results,ProbSAT can improve the quality(especially the diversity)of the final solution set,and it also speeds up the convergence of the algorithm to a large ratio of valid software products.Second,an algorithm named PreEA is proposed to solve many-objective optimal software product selection problem by integrating preference information of users with an achievement scalarizing function(ASF).Similar to SATVaEA,PreEA also adopts SAT solvers to enhance the search of the algorithm.In fact,SATVaEA deals with users' preference in a posterior way,i.e.,selection after search.Different from this,PreEA integrates the preference of users into the optimization process,and it returns only one solution that can satisfy the preference as much as possible in each run.As demonstrated by the experimental results,PreEA is effective in handling the preference of users.Besides,the SAT solvers are shown to be the key factors for the high performance of PreEA.To sum up,this thesis focuses on many-objective optimization algorithms and their practical applications.On the one hand,the proposed algorithms in the thesis can enrich the current researches on many-objective optimization.On the other hand,this study provides new ideas and techniques for software engineers to effectively and efficiently configure software product lines.The studies in this thesis have practical significance and referential value for re-search communities from both evolutionary multi-objective optimization and software product line engineering.