多目标优化问题及其算法的研究.doc

多目标优化问题及其算法的研究摘要：多目标优化问题(MOP)由于目标函数有两个或两个以上，其解通常是一组Pareto最优解。传统的优化算法在处理多目标优化问题时不能满足工业实践应用的需要。随着计算机科学与生命信息科学的发展，智能优化算法在处理多目标优化问题时更加满足工程实践的需要。本文首先研究了典型多目标优化问题的数学描述，并且分析了多目标优化问题的Pareto最优解以及解的评价体系。简要介绍了传统优化算法中的加权法、约束法以及线性规划法。并且研究了智能优化算法中进化算法(EA)、粒子群算法(PSO)和蚁群优化算法(ACO)。关键词：多目标优化问题；传统优化算法；进化算法；粒子群算法；蚁群优化算法中图分类号：TP391 文献标识码：AResearch of Multi-objective Optimization Problem and AlgorithmAbstract: The objective function of Multi-objective Optimization Problem is more than two, so the solutions are made of a term called best Pareto result. Traditional Optimization Algorithm cannot meet the need of advancing in the actual industry in the field of the Multi-objective Optimization Problem. With the development in computer technology and life sciences, Intelligent Optimization Algorithm is used to solve the Multi-objective Optimization Problem in the industry. Firstly, the typical mathematic form of the Multi-objective Optimization Problem, and the best Pareto result of Multi-objective Optimization Problem with its evaluate system were showed in this paper. Its take a brief reveal of Traditional Optimization Algorithm, such as weighting method, constraint and linear programming. Intelligent Optimization Algorithm, including Evolutionary Algorithm, Particle Swarm Optimization and Ant Colony Optimization, is researched too. Keyword: Multi-objective Optimization Problem; Traditional Optimization Algorithm; Evolutionary Algorithm; Particle Swarm Optimization; Ant Colony Optimization.1 引言所谓的目标优化问题一般地就是指通过一定的优化算法获得目标函数的最优化解。当优化的目标函数为一个时称之为单目标优化(Single-objective Optimization Problem, SOP)。当优化的目标函数有两个或两个以上时称为多目标优化(Multi-objective Optimization Problem, MOP)。不同于单目标优化的解为有限解，多目标优化的解通常是一组均衡解。显而易见，多目标优化问题比单目标优化问题更接近工程实践，同时更加复杂。很多工程实践中的优化问题最后都可以转化为多目标优化问题。因此，对多目标优化问题的深入研究对于实践应用更具价值。通常，多目标优化问题都是通过一定的算法实现求解的。对多目标优化问题的研究也更多地集中于对各种算法的研究。目前多目标优化算法归结起来有传统优化算法和智能优化算法两大类。传统优化算法包括加权法、约束法和线性规划法等。智能优化算法包括进化算法（Evolutionary Algorithm, 简称EA）、粒子群算法（Particle Swarm Optimization, PSO）、人工免疫系统（Artificial Immune System, AIS）和蚁群优化算法（Ant Colony Optimization, ACO）等。传统优化算法实质上就是将多目标函数转化为单目标函数，通过采用单目标优化的方法达到对多目标函数的求解。这样得到的解往往与最优解相去甚远，远远满足不了工程实践的应用要求。智能优化算法通过对自然现象的模拟，从而抽象出符合一定规律的数学模型。智能优化算法具有自组织、自适应等特征，为解决复杂的工程实践提供了重要的技术方法。2 多目标优化问题多目标优化问题首先由法国经济学家V.Pareto在研究经济平衡时提出，并且引进和推广了Pareto最优解。多目标优化问题中的每个目标称为子目标。由于各个子目标之间的相互影响和作用使得对多目标优化时不仅仅是满足每个子目标的最优化条件，而且要满足子目标间相互关系的约束条件。因为子目标间的关系也就是子目标约束条件往往是复杂的，有时甚至是相互矛盾的，所以多目标优化问题实质上是处理这种不确定的子目标约束条件。2.1 多目标优化问题的数学描述多目标优化问题的数学描述由决策变量、目标函数、约束条件组成。由于多目标优化问题的应用领域不同，其数学描述也不同，包括一般多目标优化、动态多目标优化、确定多目标优化和不确定多目标优化等几种。一般多目标优化数学描述如下：Min(&Max) S. t. (1.1) 其中：x为D维决策变量，y为目标函数，N为优化目标总数；为第n个子目标函数；为K项不等式约束条件，为M项等式约束条件，约束条件构成了可行域；和为向量搜索的上下限。以上方程表示的多目标最优化问题包括最小化问题（min）和最大化问题（max）以及确定多目标优化问题。动态多目标优化问题的数学描述在一般多目标优化问题的基础上增加了时间变量t。其方程表示如下： (1.2)不确定多目标优化问题的数学描述则在一般多目标优化问题的基础上增加了q维不确定量a。其方程表示如下： （1.3）其中：表示的是不确定量a，的区间为到 ；表示的是不等式约束的允许区间；表示的是等式约束的允许区间。2.2多目标优化问题的Pareto最优解求解多目标优化问题的过程就是寻找Pareto最优解的过程。所谓的Pareto最优解也被称为非劣最优解。Pareto最优解是在集合论的基础上提出的一种对多目标解的向量评估方式。因此，所谓的最优解只是一种评价解的优劣的标准。而所谓的优劣性就是指在目标函数的解集中对其中一个或多个子目标函数的进一步优化不会使其它子目标函数的解超出规定的范围，即在多目标优化中对某些子目标的优化不能影响到其它子目标的优化而容许的整个多目标的最优解。在Pareto最优解中引入了支配向量。支配向量的定义如下：对任意的，满足且存在有，则向量支配向量。当与满足以下条件， ，则称支配。的支配关系和x的支配关系一致。 若是决策变量中的一点（适用于集合论时，将决策变量称为搜索空间），当且仅当在搜索空间的可行域内不存在x使得成立时，称为非劣最优解。对于多目标优化问题，当且仅当在搜索空间中的任意x，都有，则称为全局最优解。由所有非优劣最优解组成的集合称为多目标优化的最优解集。所有的Pareto最优解集对应的目标函数值所形成的区域称为Pareto前端。可见，Pareto最优解只是给出了多目标优化问题的解的评价标准，并没有提供切实可行的解的过程，因此，从多目标优化问题提出到Pareto最优解的提出，都未能触及多目标优化问题的实质。多目标优化问题的解决需要提出各种不同的算法来达到最终的求解。目前的多目标优化问题研究就是集中在优化算法的研究以及与具体的工程实践的结合。为了对各种算法进行评价，我们又不得的引入优化算法的性能评价体系。2.3多目标优化算法的性能评价多目标优化算法的评级指标通常有以下几项：逼近性GD(Generational Distance)、均匀性SP(Spacing)、宽广性EX、最优解数目ER(Error Ratio)、收敛性度量值和多样性度量值。逼近性GD用来描述算法所获得的非劣最优解与Pareto前端的距离。，式中表示第个非劣解与Pareto前端的距离。均匀性SP用来描述非劣解在Pareto前端上的分布范围。，式中，表示的是两非劣解间的距离，则为其平均值。宽广性EX用来描述非劣最优解的分布范围。最优解数目ER用来描述在算法获得的非劣最优解中不属于Pareto前端的解所占的比例。收敛性度量值用来衡量一组已知的Pareto最优解集的收敛范围。收敛性度量的评价方法为在多目标优化问题的Pareto前端均匀地取若干点构成Pareto前端基点系，计算由算法获得的Pareto最优解与基点之间的距离的最小值，所有这些最小值的平均值就是收敛性度量值。多样性度量值用来衡量Pareto前端的分布。多样性度量的评价方法将算法获得的所有非劣解按目标函数有序分布在Pareto前端中，然后计算这些非劣解中连续解的距离及，同时计算Pareto前端中极值点的距离和边界点的距离，则多样性指标表示为如下公式：。多样性度量值反映了非劣解是否均匀分布。以上的评价标准从各个方面表征了算法获得的非劣解的在Pareto前端中的分布情况，其中，最常用的评价指标为收敛性度量值和多样性度量值。随之而形成的三类主要的评价方法：第一种评价非劣解的收敛性性能；第二种评价非劣解的多样性性能；第三种评价包括收敛性和多样性的综合性能。3 传统优化算法传统优化算法的总体思路是，将多目标优化问题通过一定的人为的方法将其转化为单目标优化问题，然后求解转化之后的单目标优化问题。常用的方法有，目标加权法、约束法和目标规划法等。3.1 目标加权法目标加权法将多目标优化问题中的各个子目标按照线性组合的方式将多目标优化转化为单个总体目标然后进行优化求解。其表达式如下： （2.1）其中，为总体目标函数，为加权系数，有。加权系数由人为地根据各个子目标函数的重要程度进行分配。可见，这种算法明显地带有主观性，需要在工程实践中不断地进行改进。3.2 约束法约束法的实质是在多目标优化问题中选取其中的一个子目标作为新优化问题的目标函数，将其它子目标转化为约束条件。设选取的子目标为第k个子目标，则其它n-1个子目标转化为约束条件。其表达式如下： （2.2）其中，为人为设定的下界，通过调节搜索Pareto最优解。可见这种方法实现多目标最优化时也存在人为因素，同加权法一样需要技术人员的经验的积累。3.3 目标规划法目标规划法则首先单独求出各子目标函数的最优解，然后进行归一化求和，最终实现多目标优化。其归一化求和表达式如下： （2.3）目标规划法的关键在于求的各个子目标函数的最优解。这种方法虽然可以避免人为因素的影响，但归一化求和后所得的Pareto最优解往往不能满足多目标优化问题的实践要求。可见，传统优化算法存在着诸多缺陷，无法满足现代工程实践的要求，因此，随着科学技术的进步尤其是信息化技术的进步，使得提出更加科学合理的智能优化算法成为可能。4 智能优化算法适用于多目标优化问题的智能优化算法不再单纯地从纯数学的推导演化中寻求Pareto最优解，而是借鉴于生命科学与信息科学的发展而形成的交叉领域中衍生而来。智能优化算法通过模拟生物进化以及群体动物活动等生命特征，运用迭代计算实现对多目标优化问题的求解。4.1 进化算法（EA）进化算法以生物学领域的进化理论为基础，通过模拟生物进化过程与进化机制实现对多目标优化问题的求解。不同于传统优化算法，进化算法不直接处理多目标优化问题的数学描述，而是根据各个子目标进行编码形成初始个体，然后利用遗传操作算子（选择、重组、变异）在进化过程中产生适应度较高个体，通过逐代进化最终搜索到满足多目标优化问题的Pareto最优解。进化算法的流程包括以下几部分：个体编码、设计适应度函数、建立遗传操作算子、设定终止条件。个体编码就是将多目标优化问题中各子目标函数进行编码形成个体，在算法运算时不再处理子目标函数而是处理各个个体。设计适应度函数则是根据决策变量和约束条件等对各个个体达到最优解的程度进行评价而建立相关的适应度函数。在进化的过程中通过计算各个个体的适应度对个体进行评价，这样不需要外部信息的参与即可实现对群体进化的控制。建立遗传操作算子的过程实际上就是进行迭代运算的过程，通过选择、重组、变异操作实现个体的不断优化，当优化后的由个体组成群体满足终止条件时，将群体中的最优个体输出即为求得的Pareto最优解。（如右图所示）进化算法EA根据不同的进化侧重点又可分为遗传算法GA（Genetic Algorithms）、遗传规划GP(Genetic Programming)、进化策略ES（Evolution Strategies）和进化规划EP（Evolution Strategies）四种典型方法。遗传算法的主要进化操作有选择、重组和变异，而进化策略和进化规划主要的进化操作时选择和变异。目前的进化算法主要以遗传算法作为主流，遗传算法的发展也较为迅速，其中非支配排序遗传算法NSGA（Non-dominated Sorting Genetic Algorithms）及带精英策略的非支配排序遗传算法NSGA在处理多目标优化问题时经常被采用。4.2 粒子群算法（PSO）粒子群算法PSO是一种典型的群智能方法。与蚁群算法ACO类似，粒子群算法是利用计算机模拟鸟群的飞行行为和捕食行为，通过研究鸟群在飞行和捕食中个体（称为微粒）之间如何相互配合和协作来实现整个种群的优化。因此粒子群算法有所谓的两个版本，即全局版本和局部版本。二者的侧重点并不相同：全局版本中，微粒跟踪的两个极值为自身最优位置（pbest）和种群最优位置(gbest)；而在局部版本中，微粒跟踪的两个极值为自身最优位置和拓扑领域中所谓微粒的最优位置（nbest）。应用于多目标优化问题的粒子群算法一般以全局版本为主。粒子群算法基于集群人工生命系统的五个重要原则来构建其数学模型。这五个重要原则分别为：邻近原则，即群体应该能够执行简单的空间和时间运算；质量原则，即群体应该能感受到周围环境质量因素的变化并做出响应；反应多样性原则，即群体不应将获取资源的途径限制在狭窄的范围内；稳定性原则，即群体不应随着环境的每一次改变而改变自己的行为模式；适应性原则，即当改变行为模式带来的回报是值得的时候，群体应该改变其行为模式。根据以上原则我们可以对粒子群算法建立数学模型。粒子定义为D维空间中的点,同时赋予粒子的初始速度，这样给每个粒子赋予了初始位置和初始速度作为优化的初始状态。然后要根据多目标优化问题的目标函数和约束条件建立起类似于进化算法的适应度函数。在给定初始条件和适应度函数后，粒子在搜索空间中开始运行。每次迭代过程中粒子同时跟踪其自身最优位置（pbest）和群最优位置(gbest)，其追踪方程如下式： （3.1）其中，和为加速常数，分别调节粒子达到自身最优位置（pbest）和群最优位置(gbest)的最大步长。和是服从0-1均匀分布的随机数，用来模拟自然界中群体行为的轻微扰动。由于通常为时间常数1，位置迭代方程通常直接表示为：。上述（3.1）式就是粒子群算法的基本迭代方程。在实际应用中需要对方程的参数进行设置，其中和在0,4之间取值，同时限定在之间以防止粒子远离搜索空间。为了提高粒子群算法的收敛速度和求解质量，对基本粒子群迭代方程进行改进产生了带惯性权的PSO算法，其迭代方程： （3.2）其中，即为惯性权系数。较大的惯性权能够加强粒子群算法的全局搜索能力，较小的惯性权能够加强粒子群算法的局部搜索能力。通常，惯性权采用由大变小的方式取值，这样，粒子群算法在运行初期能快速定位最优解的大致范围，随着减小，粒子群算法可以实现精细的局部搜索，最终实现求得最优解。此外，也有研究提出在粒子群算法中引入压缩因子以确保粒子群算法的收敛性，其迭代方程： （3.3）其中，称其为压缩因子。压缩因子的引入可以提高粒子群算法的性能。由于个体数目小、迭代收敛速度快、运算简单、易于实现等优点，粒子群算法具有很广的应用范围。但是由于粒子群算法局部优化能力差，不能同时实现Pareto前端最优解，因此粒子群算法在应用于多目标优化问题时还有待进一步提高。目前常采用的方法是粒子群算法与进化算法相结合，利用粒子群算法快速获得部分最优解，然后利用进化算法实现Pareto前端全部最优解。4.3蚁群优化算法（ACO）蚁群优化算法是一种通过模拟蚂蚁的觅食机理逐渐形成的分布式智能模拟算法。不同于进化算法和粒子群算法从群体入手去求解多目标优化问题，蚂蚁算法从个体着手，利用所谓的信息素以及信息素更新机制实现个体与个体间的间接联系最终实现复杂问题的求解。由于蚂蚁算法的分布性及自组织性，使得蚂蚁优化算法易于与其它优化算法相结合。蚁群的觅食行为具有以下特征：蚁群中的每个蚂蚁在经过的路径上会留下可以被其它蚂蚁所感受的信息素；当经过某条路径的蚂蚁增多时，信息素也会增加形成了正反馈，这样其它蚂蚁会优先选择该路径；信息素并不是永久的而是可以挥发的，这就是所谓的信息素挥发机制，这样有利于蚂蚁发现新的食物源；蚁群中的蚂蚁以分布方式寻找食物，这样可以利用蚂蚁寻找到更多的食物源。正是基于以上特征建立的蚁群优化算法也具有相应的特征：其一是蚂蚁群体中体现出的正反馈机制，使蚁群算法可以有效地搜索到最优解；其二是单个蚂蚁表现出的分布式寻优方式，使得蚁群算法可以在全局的多点进行搜索