A Research Of Multi-Object Based On Objective-space-divided Algorithms And Its Applications

The Evolutionary Algorithm(EA) is a new type of optimal algorithm based on the principle of natural selection as well as on the frame of nature genetics,being with such remarkable characteristics as simplicity, interchangeability, strong robustness and availability for parallel processing.The issue of multiple objectives optimization is an arduous problem which has been highlighted in the field of science and engineering researches,and it has also caught the attention of the general public.As has been proved by the relevant researches, it is quite appropriate to solve the problem of multiple objectives optimization by using the Evolutionary Algorithm.In recent years,many researchers tried to optimize the multiple objectives by adopting the objective-space-divided(OSD)thought,with the aim of avoiding the premature problem of Evolutionary Algorithm and keeping the diversity of solutions group.This thesis, aiming at supplementing the neglected points of the current Evolutionary Algorithms based on the objective-space-divided thought,proposes an improved type of multiple-objective Evolutionary Algorithm based on the objective-space-divided thought (OSD-MOEA).Furthermore, the author solves the scheduling problem in the parallel program of a kind of Grid Task Scheduling.And the major contents of this thesis are as follows:1.This thesis optimizes the multiple objectives by adopting the objective-space-divided thought, and further brings up an improved type of multiple-objective Evolutionary Algorithm based on the objective-space-divided thought (OSD-MOEA).This kind of algorithm consists of the following aspects: through analyzing the characteristics of objective-space-division,it proposes a kind of objective-space-divided algorithm of transforming the Pareto dominating relationship among individuals to the sorting relationship of index values of the divided space; basing on the objective-space-divided algorithm,it designs a simple and efficient algorithm relying on the index values of the divided space.It is no need to compare the dominating relationship of different individuals in this algorithm,and it accomplishes the environment-selecting operation in the multiple-objective Evolutionary Algorithm according to the index values of the divided space for which the individual is currently searching.While dividing the objective space for which the individual is currently searching, however, it is not possible to avoid that multiple individuals coexist in the same divided space;therefore, this thesis designs a kind of individual congestion mechanism which would quickly select the point close to the original point in the divided space.2.As for the OSD-MOEA, this thesis makes a great quantity of simulation experiments,that is,by computing a set of representative test functions,the author compares them with both the NSGA2 which is quite good in performance and the PSFGA basing on the objective-space-division,and analyzes the several aspects of performance of OSD-MOEA.As is shown by the results, the OSD-MOEA has improved the working efficiency of the algorithm and has cut down the time needed in the former algorithms.3.As for the problem of multiple-task-scheduling in the independent grids,this thesis proposes a Grid task-Scheduling Algorithm on the basis of cost & time and objective-space-divided thought(C&T-OSD-GTSA).This C&T-OSD-GTSA adopts the thought of division and sorting of space of the OSD-MOEA,and by making model of the problem of multiple-task-scheduling in the independent grids,the author makes relevant simulation experiments considering the differences in the reliance on cost and time.And the results of the experiments prove that the C&T-OSD-GTSA has got content results in both the convergence of algorithm and the distribution of Pareto solution set.