Font Size: a A A

The Comparison And Research On Many Objective Reduction Algorithms

Posted on:2011-11-14Degree:MasterType:Thesis
Country:ChinaCandidate:C ZhouFull Text:PDF
GTID:2178330332964314Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
In the real world, many optimization problems conside lots of objectives simultaneously, where the objectives are conflict, and so multi-objective optimization are concerned. Evolutionary algorithm is a global intelligent search algorithm simulating natural evolution. For solving highly complex and nonlinear problems, it has been widely used. Researchers put forward their own multi-objective evolutionary algorithm for different applications, for example: NSGA-II,ε-MOEA, and so on, they can deal with a wide range of optimization problems better.Nonetheless, most of the publications consider problems with two or three objectives, in spite of the fact that many real-world problems involve a large number of objectives (4 or more). Besides the difficulty to analyze the Pareto front when there are more than three objectives, recent studies have shown that MOEAs based on Pareto optimality have difficulties to find a good Pareto front approximation in higher dimensions. One of the reasons for this is that the proportion of non-dominated solutions (i.e., equally good solutions) in a population increases rapidly with the number of objectives. This implies that in the presence of many objectives the selection of new solutions is carried out almost at random since a large number of the solutions are equally good in the Pareto sense. Currently, there are mainly two approaches to deal with problems involving many objectives, namely: i) to propose relaxed forms of Pareto optimality ,and ii) to reduce the number of objectives of the problem to ease the decision making or the search processes . This paper focuses on the second method, and its main tasks are the following three aspects:First, analyze and compare three algorithms similar to our approach.At the beginning, this paper introduces those algorithms simpely, and then analyzes their performance. Comparing with our new one, this proves that our algorithm is feasible from another point of view.Second, we propose Objective Reduction based on the Least Square Method,the experiment result with other similar algorithm shows our algorithm is competitive.Our algorithm fits every objective's valus into multi-strip lines, then determines the most redundant objective couples between each two-slope vector, and considers the most redundant objective, then deletes it from the redundant objective set. At every step of the new algorithm, this paper will introduce and analyze detailedly, and educe the time complexity. Othermore, lots of experiments show that our new algorithm is effective. Last, propose two methods for estimating redundant objective reducing algorithms.1) Use the changed dominant relation radio pre and post objective reducing to measure them;2) Fit every function to multi lines and use space similarity radio to survey them.Based on less of metrics on these algorithms, there are two new ways. The numerical value and the figure hang together,which show the two methods are useful. And also, metric (1) was used for estimating all the objective reduction algorithms.Last, compare with existed method, experiment shows that the new method can be used for evaluating non-redundant objective reducing algorithm.In addition, this paper improved single objective genetic algorithm. For example trivial sales problem, and function optimal problems, and so on.
Keywords/Search Tags:Multi-objective optimization, Multi-objective evolutionary algorithm, Many multi-objective optimizations, Objective reduction algorithm
PDF Full Text Request
Related items