Font Size: a A A

Evolutionary Algorithms Based On Divide-and-Conquer Strategy And Their Applications

Posted on:2018-07-15Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y WangFull Text:PDF
GTID:1368330542493495Subject:Circuits and Systems
Abstract/Summary:PDF Full Text Request
In real world applications,optimization problems can be very difficult for an evolutionary algorithm(EA)due to a number of problem characteristics such as the number of deci-sion variables,the number of objectives,complex landscapes and variable interactions.EAs based on divide-and-conquer strategy convert a given optimization problem into several sim-ple problems.These algorithms are promising for handling complex optimization problems.However,not much effort has been made on these algorithms.This thesis focuses on the divide-and-conquer strategy and study how to use it to design efficient EAs.The major contributions include:1.In order to improve quality of solutions obtained by MOEA/D,local optimum for sub-problem is stored and used.In original MOEA/D,the stored optimal solutions for one subproblem could be updated by optimal solutions from neighbor subproblems,which may make descent direction of the solutions for this subproblem out of predetermined trajectory.And the whole Pareto front could not be found in this case.So in our study,new generated solutions are matched with subproblems by descent direction.The lo-cal optimum stored for one subproblem could only be updated by solutions which have nearest distance to the subproblem.Meanwhile,an quantum inspired reproduc-ing operator is designed to generate new solutions.On some benchmark problems,the proposed QMOEA/D could obtain more complete PF than original MOEA/D.And in the comparisons with some improved MOEA/D,QMOEA/D also has competitive per-formance.2.For dealing with single objective optimization problem,a new framework,optimiza-tion based on non-linear transformation on decision space,is proposed,which is also base on divide-and-conquer strategy.In this framework,several transformed problems are generated by non-linear transformation on decision space and solved respectively.At last,the results from these transformed problems are filtered for obtaining best one for the given problem.From view of original decision space,different transformed problems have different search weights on different parts of the decision space.Thus,calculating resource could be assigned on different area to avoid population falling in-to single local optimal location.From distribution of solutions during search,it could be found that the instance algorithm ONTD-DE could explore several optimal solu-tions at the same time.And on Test problems and Trap problems,ONTD-DE could obtain global optimal solution with higher probability than DE and PSO algorithms.3.Based on ONTD,an adaptive strategy for adjusting high-weight area is proposed.In ONTD,high-weight areas for one transformed problems are generated randomly,which is not so effective for population to explore one local optimal location.Thus,it is necessary to adjust these high-weight areas for transformed problems.In our work,after several generations,all the individuals in current population would be matched with these transformed problems.A transformed problem would obtain an individual if the distance between them is smaller than the distance between the individual to centers of other transformed problems.For one transformed problem,if no individual could be assigned to it,the transformed problem would be released and generate one new transformed problem,for no high-quality solutions appearing in the high-weight area focused by this transformed problem.For transformed problems obtaining indi-viduals,the center and population would be updated based on these individuals.On Test and Trap problems,the proposed AONTD-DE obtained the best results in com-parisons with ONTD-DE,DE and PSO.And on cee13 benchmark problems,AONTD-DE also had good performance.4.For replica placement problem in HDFS,the conflicted relationship of network load balance and storage load balance is revealed in this dissertation.And a bi-objective op-timization model is constructed for this problem.Based on MOMAD,special coding and operators for replica placement problem are designed.With MOMAD,optimal solution set is obtained for this problem.In comparison with default strategy used in HDFS,MOO-based placement strategy provides more diverse candidate solutions.And these solutions could dominate most solutions from the default strategy.5.To make Pareto local search of MOM AD effective on replica placement problem,a new style of input for PLS is proposed.In original MOM AD,new generated non-dominated solutions are used as the input of PLS.But on replica placement problem,pertubation and local search could not provide new non-dominated solutions to PLS at every generation,which makes PLS fail to work and results in bad performance.So solution set constructed by several non-dominated solutions with largest crowding distance is used as input of PLS in our work.In comparisons with MOMAD based strategy and some other strategies on several cases,the improved MOMAD(IMO-MAD)shown competitive performance.
Keywords/Search Tags:optimization, evolutionary algorithm, divide-and-conquer strategy, decomposition, non-linear transformation, multi-objective, HDFS, replica placement
PDF Full Text Request
Related items