【作者】 周聪；

【导师】 郑金华；

【作者基本信息】 湘潭大学 ， 计算机应用技术， 2010， 硕士

【摘要】 在实际优化过程中,许多优化问题都需要同时考虑多个目标,并且这些目标往往是相互冲突的,因此,多目标优化受到更多的关注。进化算法是模拟生物自然进化的全局智能搜索算法,广泛地应用于求解高度复杂的非线性问题。研究者们针对不同的应用问题,提出了不同的多目标进化算法,比如:NSGA-II、ε-MOEA等,它们都能很好地处理多目标优化问题。但是,许多文献只是考虑两个或者三个目标的低维问题,而在实际中,往往包括的目标数非常大(4维或者更多)。当目标数量超过3维时,分析Pareto面比较困难。甚至有研究表明,基于Pareto优化的MOEA在高维情况下不易找到好的Pareto面,原因之一就是非支配解的比率随目标维数增加迅速增长。这意味着,许多算法在选择过程中都是随机的。目前处理高维问题有两种方法:松驰Pareto支配关系的方法和目标减少算法。本文针对第二种方法作了一些比较研究,主要工作包括以下三个方面。第一、分析比较了目前已经提出的三种目标减少算法。本文首先对三种同类算法作一个简介,然后分析了这些算法的性能,并与本文将提出的新算法进行对比,从另一面验证本文算法的可行性。第二、提出了基于最小二乘法的目标减少算法,并通过实验证明它的可行性。本文将从决策者角度出发提出一个新的目标减少算法,该算法采用最小二乘法将目标空间中每个目标函数拟合为多条直线段,然后两两比较各直线段的斜率,确定最冗余目标对,并将冗余目标从目标集中删除。在算法设计的每一步,本文将详细对它介绍与分析,得出其时间复杂度。另外,通过大量的比较实验证明,本文的算法是一种有效的算法。第三、提出了两种目标减少算法的评价方法。即:(1)在目标减少前后,用支配关系改变的比率来衡量它的优劣; (2)将目标函数拟合为多条直线段,用空间分布相似程度来评价它的好坏。考虑到目标减少算法目前暂时缺少专门的评价方法这个问题,本文提出了上述两种评价方法,评价的数值结果与图的直观反映结合验证评价方法的可行性;并且,本文已将评价方法(1)用于评价各目标减少算法。最后,通过与已有评价方法进行比较,实验结果表明本文提出的两种方法能准确地评价目标减少算法。另外,本文还改进了单目标遗传算法求解一些实际问题:如旅行商问题,数值优化问题等。更多还原

【Abstract】 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.更多还原