多目标优化问题的研究概述摘要:本文在查阅相关资料的基础上对多目标优化问题进行了一般性描述，详细介绍了实际生活中存在的多目标优化问题以及解决多目标优化题的几种典型算法, 讨论了各个算法存在的优缺点。

关键词:多目标优化; 进化算法; 粒子群算法; 蚁群算法; 模拟退火生活中, 许多问题都是由相互冲突和影响的多个目标组成。

人们会经常遇到使多个目标在给定区域同时尽可能最佳的优化问题, 也就是多目标优化问题。

优化问题存在的优化目标超过一个并需要同时处理, 就成为多目标优化问题(multi-objective optimization-problem, MOP)。

多目标优化问题在工程应用等现实生活中非常普遍并且处于非常重要的地位,这些实际问题通常非常复杂、困难,是主要研究领域之一。

自20世纪60年代早期以来,多目标优化问题吸引了越来越多不同背景研究人员的注意力。

因此,解决多目标优化问题具有非常重要的科研价值和实际意义。

实际中优化问题大多数是多目标优化问题,一般情况下,多目标优化问题的各个子目标之间是矛盾的,一个子目标的改善有可能会引起另一个或者另几个子目标的性能降低, 也就是要同时使多个子目标一起达到最优值是不可能的, 而只能在它们中间进行协调和折中处理, 使各个子目标都尽可能地达到最优化。

其与单目标优化问题的本质区别在于,它的解并非唯一, 而是存在一组由众多Pareto最优解组成的最优解集合, 集合中的各个元素称为Pareto最优解或非劣最优解。

1 多目标优化问题的描述多目标优化问题用文字描述为D个决策变量参数、N个目标函数、m+n个约束条件组成一个优化问题,决策变量与目标函数、约束条件是函数关系。

在非劣解集中决策者只能根据具体问题要求选择令其满意的一个非劣解作为最终解。

多目标优化问题的数学形式可以如下描述:min y=f(x)=[f1(x),f2(x),…,fn(x)]n=1,2,…,Nst g i (x )≤0 i =1,2,…,mℎj (x )=0 j =1,2,…,k x =[x 1,x 2,x d ,…,x D ]x d_min ≤x d ≤x d_max d =1,2,…,D其中: x 为D 维决策向量, y 为目标向量,N 为优化目标总数;g i (x)≤0为第i 个不等式约束,ℎj (x)=0为第j 个等式约束, fn(x)为第n 个目标函数;X 是决策向量形成的决定空间,Y 是目标向量形成的目标空间。

g i (x)≤0和ℎj (x)=0确定了解的可行域, x d_min 和x d_max 为每维向量搜索的上下限。

对于多目标优化问题中最优解或非劣最优解可进行如下定义：定义 1 对任意的d ∈[1,D]满足x d ∗≤x d 且存在d 0∈[1,D]有x d 0∗<x d 0，则向量x ∗=[x 1∗，x 2∗，…，x D ∗]支配向量x =[x 1,x 2,x d ,…,x D ]。

f(x ∗)支配f(x)必须满足一下两个条件：∀n,f n (x ∗)≤f n (x) n =1,2,…,N∃n 0,f n 0(x ∗)<f n 0(x ) 1≤n 0≤Nf(x)的支配关系与x 的支配关系是一致的。

定义2 Pareto 最优解是不被可行解集中的任何解支配的解，若x ∗是搜索空间中的一点，说x ∗为非劣最优解，当且仅当不存在x （在搜索空间可行性域中）使得f n (x)≤f n 0(x ∗)成立，n=1,2，…，N 。

定义3 给定一个多目标优化问题f(x)，f(x ∗)是全局最优化解当且仅当对任意x （在搜索空间中），都有f(x ∗)≤f(x)。

定义 4 由所有非劣最优解组成的集合成为多目标优化问题的最优解集（Pareto optinal set ）,也成为可接受解集或有效解集。

2 不同算法在多目标优化中的应用多目标优化问题不存在唯一的全局最优解,过多的非劣解是无法直接应用的,所以在求解时就是要寻找一个最终解。

求最终解主要有三类方法: a)生成法, 即先求出大量的非劣解,构成非劣解的一个子集,然后按照决策者的意图找出最终解;b)为交互法, 不先求出很多的非劣解,而是通过分析者与决策者对话的方式逐步求出最终解; c)是事先要求决策者提供目标之间的相对重要程度, 算法以此为依据, 将多目标问题转换为单目标问题进行求解。

而这些主要是通过算法来实现的,一直以来很多专家学者采用不同算法解决多目标优化问题,如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。

2.1 多目标进化算法多目标进化算法(MOEA)是一类模拟生物进化机制而形成的全局性概率优化搜索方法,在20世纪90年代中期开始迅速发展, 其发展可以分为两个阶段。

第一阶段主要有两种方法即不基于Pareto优化的方法和基于Pareto优化的方法; 第二个阶段就是在此基础上提出了外部集这个概念,外部集存放的是当前代的所有非支配个体,从而使解集保持较好的分布度。

这个时期提出的多目标进化算法更多地强调算法的效率和有效性。

在这两个阶段中, 比较典型的多目标进化算法有NSGA2、PESA2和SPEA2。

对于这三种算法而言, 其优点较多但是其缺点也比较明显的。

如NSGA2的优点在于运行效率高、解集有良好的分布性, 特别对于低维优化问题具有较好的表现; 其缺点在于在高维问题中解集过程具有缺陷, 解集的多样性不理想。

PESA2的优点在于其解的收敛性很好,比较容易接近最优面, 特别是在高维问题情况下; 但其不足之处在于选择操作一次只能选取一个个体, 时间消耗很大, 而且阶级的多样性不佳。

SPEA2的优点在于可以取得一个分布度很好的解集, 特别是在高维问题的求解上, 但是其聚类过程保持多样性耗时较长, 运行效率不高。

多目标进化算法的基本原理描述如下: 多目标进化算法从一组随机生成的种群出发, 通过对种群执行选择、交叉和变异等进化操作, 经过多代进化, 种群中个体的适应度不断提高, 从而逐步逼近多目标优化问题的Pareto最优解集。

与单目标进化算法不同, 多目标进化算法具有特殊的适应度评价机制。

为了充分发挥进化算法的群体搜索优势, 大多数MOEA均采用基于Pareto排序的适应度评价方法。

在实际应用中, 为使算法更好地收敛到多目标优化问题的Pareto最优解, 现有的MOEA通常还采用了精英策略、小生境和设置外部集等关键技术。

MOEA一般框架所描述的算法思想如下:MOEA通过对种群X( t)执行选择、交叉和变异等操作产生下一代种群X( t+ 1)。

在每一代进化过程中,首先将种群X( t)中的所有非劣解个体都复制到外部集A( t)中, 然后运用小生境截断算子剔除A( t)中的劣解和一些距离较近的非劣解个体, 以得到个体分布更为均匀的下一代外部集A( t+1), 并且按照概率pe从A( t+ 1)中选择一定数量的优秀个体进入下代种群。

在进化结束时, 将外部集中的非劣解个体作为最优解输出,如下图所示：图1 MOEA算法的一般框架目前, MOEA研究取得了大量成果, 已被应用于许多领域, 如工程领域、工业领域和科学领域。

其中,工程领域的应用最多, 如电子工程、水利工程、风电工程和控制等。

2.2 多目标模拟退火算法模拟退火( SA)是基于Monte Carlo迭代求解策略的随机寻优算法, 是局部搜索算法的扩展。

其出发点是固体物质的退火过程与一般组合优化问题的相似性, 通过模拟固体退火过程, 从某一初温开始,随着温度的降低,结合概率突跳特性在解空间中搜索最优解,即在局部解时能概率性地跳出并最终趋于全局最优。

它采用了MetropolisHastings接受准则, 并用一组称为冷却进度表的参数控制算法进程模拟退火算法的数学描述为: 在给定邻域结构后,模拟退火过程是从一个状态到另一个状态不断随机游动 ,这个过程可用马尔可夫链来描述。

当温度t 为一定时, 两个状态的移动概率定义如下：A ij不总是等于1，即状态也有不被接受的可能，算法停留在状态i的概率为：式中,p ij是下一步转移概率; |D|表示状态集合(解集合)中状态的个数; θij是从i到j 的产生概率, 表示在状态i时j 状态被选取的概率, 可以理解j是i 的邻域;A ij(t)是接受概率, 表示在状态i产生j 后接受j 的概率,模拟退火过程中其接受概率为其中, f(i)为第j个状态下的目标函数值, ∇f ij=f(j)−f(i)。

模拟退火算法在迭代搜索过程以Metropolis接受准则接受目标, 所以具有跳出局部最优的能力, 通用、灵活性高。

但是模拟退火算法对初始温度和退温系数这两个参数的依赖性较强, 这两个参数选择恰当与否将直接关系到算法性能。

模拟退火算法是一个有效的全局优化算法,这类算法的最大优点是对搜索空间(目标函数的性质)不加任何限制, 可以是不连续的、不可微的, 并且也能求得Pareto边界上多个不同方向的Pareto最优解;但是其需要大量的迭代次数, 因而收敛速度慢、优化效率较低。

在解决多目标问题时仍将其转换为单目标问题, 采用单目标技术求解。

由于单目标问题与多目标问题的不同, 在求解时,往往得不到分布更广的Pareto最优解集, 即将丢失一部分Pareto解。

2.3 多目标蚁群优化算法蚁群算法( ant colony algorithm, ACA)是通过模拟自然界蚂蚁搜索食物的行为提出的仿生优化算法。

仿生学家经过大量细致观察研究发现, 蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。

蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质, 并以此指导自己的运动方向。

因此, 由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多, 则后来的蚂蚁选择该路径的概率就越大。

蚁群算法的基本原理描述如下:基于对自然界真实蚁群的集体觅食行为的研究,模拟真实的蚁群协作过程。

算法由若干个蚂蚁共同构造解路径,通过在解路径上遗留并交换信息素的方法反馈信息提高解的质量, 进而找到最短路径, 达到优化的目的。

蚁群算法是一种本质上并行的算法, 可以看做是一个分布式的多agent系统,它在问题空间的多点同时开始进行独立的解搜索, 不仅增加了算法的可靠性, 也使得算法具有较强的全局搜索能力。

其正反馈的过程不仅能够使得初始值不断地扩大, 同时又可以引导整个系统向最优解的方向进化。

同时, 蚁群算法的求解结果不依赖于初始路线的选择, 而且在搜索过程中不需要进行人工的调整。

但是蚁群算法需要较长的搜索时间, 易于出现早熟停滞现象。

2.4 多目标粒子群算法粒子群优化算法( PSO)是一种源于对鸟群捕食行为的研究而发明的进化计算技术,最先由Barnhart博士和Kennedy博士于1995年提出。