多目标优化算法与求解策略教学文稿
多目标优化算法与求解策略
2多目标优化综述
2.1多目标优化的基本概念
多目标优化问题(Multi-objective Optimization Problem，MOP)起源于许多实际复杂系统的设计、建模和规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中的决策问题都要在考虑不同的约束的同时处理若干相互冲突的目标，这些问题都涉及多个目标的优化，这些目标并不是独立存在的，它们往往是祸合在一起的互相竞争的目标，每个目标具有不同的物理意义和量纲。它们的竞争性和复杂性使得对其优化变得困难。
多目标最优化是近20多年来迅速发展起来的应用数学的一门新兴学科。它研究向量目标函数满足一定约束条件时在某种意义下的最优化问题。由于现实世界的大量问题，都可归结为含有多个目标的最优化问题，自70年代以来，对于多目标最优化的研究，在国内和国际上都引起了人们极大的关注和重视。特别是近10多年来，理论探索不断深入，应用范围日益广泛，研究队伍迅速壮大，显示出勃勃生机。同时，随着对社会经济和工程设计中大型复杂系统研究的深入，多目标最优化的理论和方法也不断地受到严峻挑战并得到快速发展。近几年来，将遗传算法(Genetic Algorithm，GA)应用于多目标优化问题成为研究热点，这种算法通常称作多目标优化进化算法或多目标优化遗传算法。由于遗传算法的基本特点是多方向和全局搜索，这使得带有潜在解的种群能够一代一代地维持下来。从种群到种群的方法对于搜索Pareto解来说是十分有益的。
一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中
元素称为Pareto最优或非劣最优。所谓Pareto最优就是，不存在比其中至少一个目标好而其它目标不劣的更好的解，也就是不可能通过优化其中部分目标而其它目标不至劣化。Pareto最优解集中的元素就所有目标而言是彼此不可比较的。
下面从严格的数学描述角度介绍多目标优化问题的含义。通常在多目标优化领域中广泛采用并普遍接受的别劝尸问题的数学定义如下：定义1.1(MOP)：一般材MOP由n个决策变量参数、k个目标函数和m个约束条件组成，目标函数、约束条件与决策变量之间是函数关系。最优化目标如下：
Maximize y=f(x)=(f1(x)，f2(x)，…，f k(x))
S.t. e(x)=(e1(x)，e2(x)，…，e m(x))≤0 （2-1）其中x=(x1，x2，…，x n)∈X
Y=(y1，y2，…，y k)∈Y
这里x表示决策向量，y表示目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间，约束条件e(x)≤0确定决策向量的可行的取值范围。
当有多个目标函数存在的时候，“最优解”概念产生了新的变化。因为在解决多目标问题时，实际上是求一组均衡解，而不是单个的全局最优解。这个被普遍采用的最优解的概念是Francis Ysidro Edgeworth早在1881年提出来的。随后著名的法国经济学家和社会学家帕雷托(Vilfredo Pareto)在1896年推广了这个概念，他从经济学的角度将本质上不可比较的多个目标转化成单个指标进行优化求解，这里就涉及到多目标的概念。帕雷托首次提出向量优化的概念，即现在广泛使用的Pareto最优。
MOP的本质在于大多情况下各子目标可能是相互冲突的，某子目标的改善可能引起其它子目标性能的降低，即同时使多个子目标均达到最优一般是不可能的，否则就不属于多目标优化研究的范畴。解决MOP的最终手段只能是在各子目标之间进行协调权衡和折衷处理，使各子目标函数均尽可能达到最优。因此，MOP的最优解与单目标优化问题的最优解有
着本质上的区别，为了正确求解MOP ，必须对其解的概念进行定义。
定义1.2(可行解集)：可行解集
f X 定义为满足式(2-1)中的约束条件e(x)的决策向量x 的集合，即
}0)(|{≤∈=x e X x X f （2-2）
f X 的可行区域所对应的目标空间的表达式为：
)}({)(x f Y x f Y f X x f f ∈== （2-3）
对于式（2-3），表示可行解集f X 中的所有x ，经优化函数映射形成目标空间中的一个子空间，该子空间的决策向量均属于可行解集。 对于极小化问题，可以很容易转化为上述的最大化问题来进行求解。 单目标优化问题的可行解集能够通过它的唯一的目标函数f 来确定方案之间的优劣关系和程度。对于MOP 问题来说，情况则有所不同，因为一般来说，f X 中的决策向量是无法进行全部排序的，而只能对某个指标进行排序，即部分排序。
大多数情况下，类似于单目标优化的最优解在多目标优化问题中是不存在的，只存在Pareto 最优解。多目标优化问题的Pareto 最优解仅仅只是它的一个可以接受的非劣解或满意解，并且通常的多目标优化问题大多具有很多个Pareto 最优解。若一个多目标优化问题存在所谓的最优解，则该最优解必定是Pareto 最优解，并且Pareto 最优解也只由这些最优解组成，再不包含其它解。因此Pareto 最优解是多目标优化问题的合理的解集合。通常多目标优化问题的Pareto 最优解是一个集合。对于实际应用问题，必须根据对问题的了解程度和决策人员的个人偏好，从多目标优化问题的Pareto 最优解中挑选出一个或多个解作为所求多目标优化问题的最优解。因此求解多目标优化问题的首要步骤和关键是求出尽可能多的Pareto 最优解。
2.2传统的多目标优化方法
大多数传统的多目标优化方法将多个目标减少为一个，然后用数学规
划工具求解问题。为了用数学规划工具求解问题，首先需要用数字的形式来表明偏好。数字越大，偏好越强。这种需求促成了各种标量化方法的发展。采用这些方法将多目标优化问题转换为单目标或一系列单目标优化问题，然后可以求解变换后的问题。传统的多目标优化方法有多种，本文选取约束法、加权法、距离函数法、最小最大法这四种多目标优化方法来进行简单的介绍。
2.2.1约束法
在MOP 问题中，从k 个目标函数f 1(x)，f 2(x)，…，f k (x)中，若能够确定一个主要的目标，例如f 1(x)，而对于其他的目标函数f 2(x)，…，f k (x)只要求满足一定的条件即可，例如要求：
k i b x f a i ?=≤≤,3,2,)(
这样我们就可以把其他目标当做约束来处理，则MOP 问题可以转换为求解如下的单目标优化问题：
Maximize )(1x f
..t S 0))(,),(),(()(21≤?=x e x e x e x e m
k i b x f a ,,3,2,)(1?=≤≤
2. 2.2加权法
加权法将为每个目标函数分配权重并将其组合成为一个目标函数，加权法的基本思想是由Zadeh 首先提出，加权方法可以表示如下：
Maximize ∑==k i i i x f x z 1)
()(ω
..t S f X x ∈
i ω称为权重，不失一般性，通常权重可以正则化使得∑==k i 11，求解上述不同权重的优化问题则能够输出一组解。这种方法的最大缺点就是不能在非凸性的均衡曲面上得到所有的Pareto 最优解。
2.2.3距离函数法
距离函数法需要使用理想点，定义理想点如下：
定义1.3(理想点)：理想点用),,,(**2*1*k y y y y ?=来表示，其中
k
i X x x f y f t ,,3,2},|)(sup{1*?=∈=。 点*y 称为理想点（ideal point ）是因为通常该点无法达到。对于每个目
标来说，寻找理想点*y 是可能的。
距离函数法寻找与理想点最近的解，根据理想点*y 的定义，对于目标
空间的每一个元素，我们无法得到比理想解更好的结果。给定Y y ∈，y 与*y 的距离函数来近似：
*
)(y y y r -= 其中*y y -是在某种特定范数意义上从y 到*y 的距离。由于p L 范数比较清晰，因此经常采用，对于一个给定的正数1≥p ，有：
p k j p j j p y y y y p y r /11**
);(??????-=-=∑= p L 范数意义下的最优解就是最小化);(p y r 的点。
距离函数);(p y r 对于每一个*j j y y -的值的重视程度相同。如果具有不
同的重要性，可以指派一个权重向量),,,(21k ωωωω?=来表明不同的重要程度，在这种情况下，有下面的加权
p L 范数： p k j p j j p j p y y y y w p y r /11*,*),;(??????-=-=∑=ωω
2. 2.4分层序列法
分层序列法是把MOP 问题的k 个目标函数，按其重要程度排一个次序。例如，不妨设MOP 问题的k 个目标函数已经排好次序：)(1x f 最重要，)(2x f 次之，)(3x f 再次之，……，最后一个目标为)(x f k 。先求出问题：
Maximize )(1x f
..t S 0))(,),(),(()(21≤?=x e x e x e x e m
的最优解)1(x 及最优值*1f 。即：
)(1*11x f Max f R x ∈=
其中
f X R =1
再求解问题 Maximize )(2x f
..t S 2R x ∈
问题的最优解)2(x 及最优值*2f 。即：
)(2*22x f Max f R x ∈=
其中
})(|{*1112f x f x R R ≥?= 继续求解问题
Maximize )(3x f
..t S 3R x ∈
问题的最优解)3(x 及最优值*3f 。即：
)(3*33x f Max f R x ∈=
其中 }
)(|{*2223f x f x R R ≥?= ……如此继续下去，直到求出第k 个问题
Maximize )(x f k
..t S k R x ∈
问题的最优解)(k x 及最优值*k f 。即：
)(*x f Max f k R x k k ∈=
其中 })(|{*111---≥?=k k k k f x f x R R
这样求得的)(k x 就是MOP 问题在分层序列意义下的最优解，即)(*k x x =，而
))(,),(),((**2*1*x f x f x f F k ?=
为MOP 问题的最优值。
2. 3传统优化方法的局限性
传统方法的优点在于它继承了求解单目标优化问题的一些成熟算法的机理。但是经典方法如加权法求解多目标优化问题时，对Pareto 最优前沿的形状很敏感，不能处理前沿的凹部，并且求解问题所需的与应用背景相关的启发式知识信息获得很少，导致无法正常实施优化或优化效果差，特别对于大规模问题，这些多目标优化方法很少真正能被使用。
前面介绍的传统的多目标优化方法存在一些局限性，主要包括一下几点：
(l)一些古典方法如加权法求解多目标优化问题时，对Pareto 最优前端的形状很敏感，不能处理前端的凹部。
(2)只能得到一个解。然而，在实际决策中决策者通常需要多种可供选择的方案。
(3)传统方法共同存在的一个关键问题就是为了获得Pareto 。最优集须运行多次优化过程，由于各次优化过程相互独立，往往得到的结果很不一致令决策者很难有效地决策，而且要花费巨额时间开销。
(4)多个目标函数之间量纲不同，难以统一。为了避免其中的一个目标函数支配其他目标函数，精确的给出所有目标函数的标量信息，就必须有每一个目标的全局先验知识，计算量巨大，很难实现。
(5)加权值的分配带有较强的主观性。由于是人为规定各个目标函数的权值，因此带有很大的主观性。
最近遗传算法己经作为一种多目标优化方法崭露头角。它的优点在于可处理大规模的搜索空间、在单轮优化期间产生多个均衡解，可有效克服古典方法的局限性，所以本文采用遗传算法对关系模型进行优化。
2.4遗传算法的基本原理和方法
达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。
遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的随机化搜索方法。它是由美国的J.Hofland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，己被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之本章主要介绍遗传算法的基本概念，遗传算法的数学理论基础和遗传算法的基本实现技术。
2.4.1遗传算法概述
模拟生物界中自然选择和群体遗传机制的遗传算法，采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采用种群的方式组织搜索，这使得它可以同时搜索解空间内的多个域，而且用种群组织搜索的方式使得它特别适合大规模并行。因此它能够解决许多常规方法
尚无法处理的复杂优化问题。
2.4.2遗传算法的特点
遗传算法具有如下优点：
(l)对可行解表示的广泛性。遗传算法处理的对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。此编码操作使得遗传算法可以直接对结构对象进行操作。
(2)群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，也使得遗传算法本身易于并行化。
(3)不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。
(4)内在的启发式随机搜索特征。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。
(5)遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。
(6)遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠的解决求解非常困难的问题。
(7)遗传算法具有固有的并行性和并行计算的能力。
(8)遗传算法具有可扩展的能力，易于同别的技术结合起来使用。
同时遗传算法也具有如下不足之处：
(l)编码不规范及编码存在表示的不准确性。
(2)单一的遗传算法编码不能全面的将优化问题的约束表示出来。考虑
约束的一个方法就是对不可行解采用闲值，这样，计算的时间必然增加。
(3)遗传算法通常的效率比其他传统的优化方法低。
(4)遗传算法容易出现过早收敛。
(5)遗传算法对算法的精度、可信度、计算复杂性等方面还没有有效的定量分析方法。
2.4.3遗传算法的运算流程
遗传算法模拟了自然选择和遗传中发生的复制。交叉和变异等现象，从任一初始种群(Population)出发，通过随机选择。交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体(Individuai)，求得问题的最优解。
遗传算法的运算流程包括编码、初始群体生成、适应度值评价检测、选择、交叉、变异六部分，下面分别做简要的介绍。
(l)编码：解空间的解数据x，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。
(2)初始群体的生成：随机生成N个串结构数据，每个串结构数据称为一个个体，N个个体构成一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t=0；设置最大进化代数T；随机生成N个个体作为初始群体尸(0)；
(3)适应度值评价检测：适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数定义的方式不同。根据具体的问题，计算群体p(t)中各个个体的适应度。
(4)选择：将选择算子作用于群体，根据适应度函数值的大小，选取适应度高的个体进行下一步的操作。
(5)交叉：将交叉算子作用于群体，交叉操作以交叉概率此随机选取群体中的个体在随机生成的位置进行交叉。
(6)变异：将变异算子作用于群体，变异操作以变异概率凡随机选取个体中的基于位进行变异，得到新的个体。
根据上述的流程，可以观察得出遗传算法存在初始种群个数N，交叉概率Pc和变异概率Pm这三个关键参数，这三个关键参数有如下的确定规则：
(l)初始群体规模N
群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模N太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模则可减少遗传算法陷入局部最优解的机会，但较大的群体规模意味着计算复杂度高。一般取N从10到160之间。
(2)交叉概率Pc
交叉概率凡控制着交叉操作被使用的频度。较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大；若交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般取只从0.25到1.00之间。
(3)变异概率Pm
变异在遗传算法中属于辅助性的搜索操作，它的主要目的是维持解群体的多样性。一般，低频度的变异可防止群体中重要的、单一基因的可能丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索。通常取变异概率凡为0.001左右。
2.4.4遗传算法的基本操作
遗传算法具有三个基本操作：选择(Selection)，交叉(Crossover)和变异(Mutation)。
(l)选择。选择的目的是为了从当前的群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。根据个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法通过选择运算体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个和多个后代的概率大。这样就体现了达尔文的适者生存原
则。
(2)交叉。交叉操作是遗传算法中最主要的操作。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特征。将群体内的各个个体随机搭配成对，对每一个个体，以交叉概率(crossoverRate)尺交换它们之间的部分染色体。交叉体现了信息交换的思想。
(3)变异。变异操作首先在群体中选择一个个体，对于选中的个体以变异概率凡随机改变串结构数据中某个串的值，即对群体中的每一个个体以变异概率(MutationRate)凡改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样，遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会。
2.4.5标准遗传算法
标准遗传算法(也称为基本遗传算法或简单遗传算法，Simple Genetic Algorithm ，简称SGA)是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本的遗传算子(Genetic Operator)：选择算子(Sdection Operator)，交叉算子(Crossover Operator)和变异算子(Mutation Operator)。其遗传进化操作过程简单，容易理解，是其他遗传算法的基础，它不仅给其他遗传算法提供了一个基本框架，同时也具有一定的应用价值。选择、交叉和变异是遗传算法的3个主要操作算子，他们构成了遗传操作，使遗传算法具有了其他算法没有的特点。
下面描述SGA 的数学模型。
SGA 可表示为：
),,,,,,,(0T N P E C SGA ψΓΦ=
其中：C ——个体的编码方法；
E ——个体适应度评价函数；
0P ——初始种群；
N ——种群大小；
Φ——选择算子；
Γ——交叉算子；
ψ——变异算子；
T ——遗传算法迭代终止条件。
下图为SGA 的流程图：
图2.4-1 SGA 流程图
2.4.6多目标优化及Pareto 最优解
多目标优化问题可以描述如下：
)](,),(),(m in[21x f x f x f m ?
?????≤*=*≤≤b x A beq
x Aeq ub x lb t s ..
其中，)(x f i 为待优化的目标函数；x 为待优化的变量；lb 和ub 分别为变量
x 的下限和上限约束；beq x Aeq =*为变量x 的线性等式约束；b x A ≤*为变量x 的线性不等式约束。
在图所示的优化问题中，目标函数1f 和2f 是相互矛盾的。因为A1
2.4-2多目标优化问题