Font Size: a A A

The Research On Diversity Of Solution Set For Multi-Objective Evolutionary Algorithm

Posted on:2009-10-19Degree:MasterType:Thesis
Country:ChinaCandidate:M Q LiFull Text:PDF
GTID:2178360245490777Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Multi-Objective optimization problem (MOP) is one of the most important research areas in optimization method, real-world engineering design problems often involve the satisfaction of multiple criteria, which should be solved simultaneously. Since the solution of a Multi-Objective Optimization Problem can not exist as a single optimal point, which means that usually one solution cannot be said to be better than another. Thus, these MOPs search for an optimal set called the Pareto front. Evolutionary Algorithms (EAs) have proven to be very useful when solving these MOPs. In recent years, many efficient Multi-Objective Evolutionary Algorithms (MOEAs) have been proposed, such as NSGA-II, SPEA2 and PEAS-II. The performance of an MOEA can be measured from three aspects: the convergence to the true Pareto optimal front, the diversity of solutions and the time consuming. A favorable diversity of solutions can give decision makers the opportunities to choose the most adequate solution for the problem from the solution set. This paper focus on the diversity of MOEA, the main work is as follows:First, for existing studies show a good distribution with a large computational load or a comparative bad distribution quickly, this thesis proposes a method maintaining diversity using Spanning Tree. The method defines a density estimation metric– Spanning Tree Crowding Distance (STCD). Moreover, information of degree of solution combined with STCD is employed to truncate population. From an extensive comparative study with three other methods on a number of 2, 3 and 4 objective test problems, the proposed method indicates a good balance among uniformity, extent and execution time.Second, we do research on the measurement for evaluating the diversity of solutions and propose a dynamic neighborhood method. This method constructs dynamic neighborhoods of solutions, and their size change with the density of solution sets. We compute the diversity relation in these neighborhoods, and build a metric. The metric can be used to compare the performance of different multi-objective optimization techniques, in particular, it can adapt to not only uniform test problems, but also non-uniform test problems.Third, the research of maintaining diversity on non-uniform distribution problem has not emerged yet. The chief reasons are that, for non-uniform distribution problem, the regularity of true PF is difficult to grasp, and the methods which try to maintain the uniformity of population may break the'true'distribution of problem. In this paper, we proposed a multi-objective evolutionary algorithm for non-uniformly distributed multi-optimization problems (MOEA/NUDP). We gave a definition of"messy"which reflects the regular degree of distribution. By using potential regularity among different individuals, it is effect to remove individuals which make population clutter. The experimental results show that the MOEA/NUDP can maintain a desired distribution of the problem, and provide a more practical value for decision maker.
Keywords/Search Tags:Multi-objective optimization, Multi-objective evolutionary algorithm, diversity maintenance, non-uniform distribution
PDF Full Text Request
Related items