Research On Constrained Multi-objective Evolutionary Algorithm And Its Application

Job shop scheduling problem plays a key role in enhancing resource utilization rate, reducing cost and advancing operating efficiency for enterprise. But job shop scheduling problem is a multi-objective optimization problem, and these objectives often conflict with each other. For the classical methods, multi-objective optimization problem is usually transformed into a single objective optimization problem, so each test can only obtains a optimal solution. In order to acquire more feasible suboptimal solutions, experiment needs to be repeated over and over again, it greatly reduces the optimizing efficiency. Therefore, research on an efficient constrained optimization algorithm that can solve multi-objective problem, such as the actual production problem-job shop scheduling, is of great significance both on theory and practice.Differential evolution (DE) algorithm is a very efficient evolutionary algorithm that is used to solve continuous optimization problem. In this paper, how to use DE algorithm to solve multi-objective constrained optimization problem is discussed, which often appears in the current practice engineering. The content of the paper is made of the following two aspects, ons is how to enhance the efficiency of DE algorithm which is used to solve multi-objective constrained optimization problem, the other is research on the application of improved DE algorithm in job shop scheduling problem.The contents of the first section are as follows:(1) How to solve multi-objective constrained optimization problem by DE algorithm is studied in detail. Through analyzing and studying of the standard DE algorithm, which is used to solve the problem of unconstrained optimization and single objective. Based on double populations searching scheme, an improved differential evolution algorithm is proposed for multi-objective constrained optimization problem. two different populations are adopted for handling constraints in optimization process, one is for feasible solutions, and the other is for infeasible solutions. To evaluate evolutionary individual, Pareto-based sorted ranking multi-objective technology is adopted. In addition, in order to improve the algorithm performance, population chaotic initialization, adaptive crossover and mutation are adopted at the same time. Through experiments on three benchmark functions with constraints and multi-objectives, it shows that the proposed algorithm is effective for solving multi-objective constrained optimization problem of low dimension.(2) In order to keep balance between diversity and convergence of differential evolution algorithm in solving multi-objective optimization problem, an improved DE based on adaptive dynamic mutation and second mutation of non-dominance solution was proposed. Through experiments on six benchmark functions with constraints and multi-objectives, it shows that the proposed algorithm is superior to Non-dominated Sorting Genetic Algorithm II and standard DE algorithm in performance.(3) To avoid shortcomings when the standard DE algorithm is used to solve multi -objective optimization problem, such as the number of Non-dominated solution obtained is too small and the algorithm is easily trapped into local optimum, an advanced differential evolution algorithm combing grading second mutation and chaotic theory is presented to solve multi-objective constrained optimization problem. Benchmarks functions are tested, simulation results show this algorithm has better convergence and distribution property.The contents of the second section are as follows:(1) Multi-objective Flow Shop Scheduling Problem (FSSP) based on DE algorithm is studied. The main task is to modify operators of standard DE algorithm and extend its application from continuous optimization problem to discrete optimization problem. Discrete DE algorithm which is suitable for solving multi-objective FSSP is constructed. Experiments on standard testing problem set of classic scheduling model are made, simulation results indicate that the proposed algorithm is effective.(2) How to use DE algorithm to solve more complicated multi-objective Job-shop Scheduling Problem (JSP) is studied. The main work is to modify standard DE algorithm and construct discrete DE algorithm in order to solve multi-objective JSP. Experiments on ten standard testing problem of JSP are made, simulation results demonstrates the effectiveness of the proposed algorithm.Finally, summary of the whole paper is given and the future work is discussed.