Research On Multi-Objective Evolutionary Algorithm And Its Application On Scheduling Problem

In the real world,there are many optimization problems with two or more objectives.These objectives are conflict with each other generally.The improvement of one objective's performance will cause the performance of other objectives to deteriorate.It is called multi-objective optimization problem(MOP).The multiobjective evolutionary algorithm(MOEA)has the strength,which the traditional methods do not have,when solving the MOP.By maintaining the population,MOEAs can obtain a set of compromise solutions after a single run,thus they are in the good graces of researchers.A number of excellent MOEAs represented by NSGA-II and MOEA/D have been proposed,and many of them have been also applied to solve practical problems in real life.Considering the framework of multi-objective evolutionary algorithm,this paper integrates the population pre-partition steps into the framework and proposes a MOEA based on population pre-partition.In addition,in the environment of artificial intelligence,the continuous expansion of high-performance computer clusters requires an effective resource management system.For this purpose,a planning-based scheduling system based on MOEA is proposed.The main work of this paper is as follows:(1)Evolutionary algorithm in the process of population evolution,if a pair of individuals who are breeding as parents are far away from each other in space,then the offspring they produced cannot effectively help the population to evolve in the right direction.The step of population pre-partition has been added to the MOEA in order to solve this problem.Moreover,a MOEA based on pre-partition has been proposed.So as to provide an effective means for pre-partition the population,this paper proposes a cluster-based pre-partition algorithm for MOEA,which is used to partition the population before producing offspring.This pre-partition algorithm is integrated into the dominance-based MOEA and the decomposition-based MOEA respectively.In order to show the influence of spatial distance between individuals on generating offspring,this paper compares the offspring reproduced by individuals with distant distances and the individuals with close distances,after that,evaluates them according to the dominance criterion.The MOEA based on pre-partition has been tested on 18 widely used benchmark functions to examine the performance,including seven test functions of DTLZ,nine test functions of WFG and two test functions o f UF.(2)So as to provide a feasible scheme for efficient scheduling of high-performance computer clusters,this paper focus on users and computer systems,and follow the principle of providing users with a good experience and reducing cluster idle calculations.A multi-objective optimization problem model is established with biobjectives,which are minimize the average waiting time and maximizing system utilization.According to this model,a new scheduling system for effectively managing large-scale computer clusters is proposed.This scheduling system,which uses a planbased scheduling strategy and adopts MOEA as the optimization engine,is able to specify an execution plan about jobs.In the MOEA optimization engine,a hybrid crossover operator strategy is used.Using the workload trac e of supercomputers in the real world,the simulation experiments about the proposed system are carried out,and the two scheduling systems are compared to verify the effectiveness of the proposed system.