基于多目标粒子群算法的多约束组合优化问题研究

来源: 未知 作者:paper 发布时间: 2020-03-06 14:05
论文地区:中国 论文语言:中文 论文类型:工程管理
摘要 组合优化问题在金融投资、资源分配等领域有着重要的应用,其求解方法一直是人们研 究的重点。实际工程应用中的组合优化问题往往具有多个约束条件且在很多情况下问题规模
摘要
组合优化问题在金融投资、资源分配等领域有着重要的应用,其求解方法一直是人们研 究的重点。实际工程应用中的组合优化问题往往具有多个约束条件且在很多情况下问题规模 较大,传统的优化算法由于需要遍历整个解空间,因此无法在多项式时间内完成求解。元启 发式算法将随机搜索算法与局部搜索算法相结合,同时从目标空间中的多个位置开始搜索, 且目标是尽可能获得更好的解,被认为更适合用来求解具有多个约束的组合优化问题。遗传 算法、粒子群算法、蚁群算法等都是常见的元启发式算法。其中粒子群优化算法通过种群中 个体之间的相互协作使得整个种群逐渐向问题的最优解靠近并最终收敛,其由分散到集中的 寻优方式以及参数设置少、收敛快等特点使得该算法在解决多约束组合优化问题方面得到了 广泛的应用。
在解决多约束组合优化问题的过程中,如何妥善处理约束条件也是一个需要我们重点关 注的问题。根据对己有约束处理方法优缺点的分析,本文釆用约束转目标的方法将多约束优 化问题转化为具有三个以上目标的多目标优化问题,并结合粒子群算法对其进行求解。
为了搜索到质量更高的最优解,本文提出一种改进的多目标粒子群优化算法IMaOPSO, 以违反约束度来维护外部档案,以拥挤度和种群中个体与理想点的距离作为两个指标寻找种 群的全局最优。并且加入扰动变异算子来扩大粒子的搜索区域,使参与变异的粒子个数随算 法迭代次数的增加而减少,在保证算法开发能力的同时避免其陷入局部最优。
此外,针对多约束组合优化问题目标空间复杂、问题规模大的情况,在IMaOPSO算法 的基础上提出了一种基于多种群协同进化的多目标粒子群算法,使用多个种群分别搜索不祠 的区域,并且改进了算法的速度更新机制以及在算法中设计了一个替换算子,以提高算法的 收敛性。最后,以不同规模的多背包问题为算例验证了所提算法的有效性。
目录
1断仑 1
1.1课题研究背景及意义 1
1.2研究现状 2
1.3本文主要研究工作 3
1.4论文主要结构 3
2多约束组合优化问题求解方法概述 5
2.1约束处理方式简介 5
2.2多目标优化 5
2.2. 1多目标优化的基本概念 5
2.2. 2 Pareto占优与非支配解 6
2.2. 3性能评价标准 7
2.3高维多目标优化 8
2.4本章小结 10
3粒子群算法与多目标粒子群算法 11
3.1基本粒子群算法 11
3.11基本粒子群算法原理及算法流程 11
3.12基本粒子群算法参数分析 12
3.2离散粒子群算法 13
3.3多目标粒子群算法 15
3.3. 1多目标粒子群算法 15
3.3.2高维多目标粒子群算法 15
3.4本章小结 16
4多约束组合优化问题的多目标求解方法 17
4.1多约束优化问题的多目标形式 17
4.2改进的多目标粒子群算法 17
4.2.1外部档案维护 17
4.2. 2全局最优的选取 18
4.2. 3个体最优的选取 18
4.2. 4扰动变异算子 19
4. 2. 5頂aOPSO算法流程 20
4. 3支配关系的选择 21
4. 3. 1模糊支配 22
4. 3. 2 a 支配 24
4. 4頂aOPSO算法求解MKP 24
4. 4. 1 MKP的数学模型 24
4.4.2粒子的编码方式 25
4.4.3 MKP的多目标形式 25
4. 4. 4结果展示方式 26
4. 5参数分析 26
4.6算例实验 31
4.7本章小结 36
5求解多约束组合优化问题的多种群BlaOPSO算法 37
1.1课题研究背景及意义
所谓组合优化,是指在满足给定约束条件的基础上对离散事件进行最优分组或编排,最 终求得能够令其目标函数值达到最大(或最小)的一个(或一组)解。组合优化问题通常存 在大量的局部极值点,往往是多维的、不可微的、高度非线性的NP难问题,我们无法精确 的求出其全局最优解。在工程应用中组合优化问题无处不在,例如金融投资、交通线路优化、 通信网络优化等等。而这些实际应用中往往存在不止一个的条件限制,也就是我们所说的约 束条件,大量的条件限制给问题的求解带来了极大的挑战[1,2],这类优化问题,称之为多约 束组合优化问题。多约束组合优化问题从本质上来说还是约束优化问题,只是约束的数量比 较多,理论上来讲,只要遍历所有可能的解的组合就能找到最优解,但随着问题规模的增大, 问题的可行解数量呈指数形式增长,这时使用精确算法求解显然是不可行的。且在约束条件 增多后,问题的可行域变得很小,约束越多可行域越小,这样一来,搜索到可行解的概率也 随之变小,这会导致算法获得的潜在解的质量不高,极大地影响算法的求解效果。所以为了 解决以上问题,我们需要做两方面的工作,一是选择一种合适的约束优化方法,二是选择一 种恰当的求解策略。
根据求解原理的不同,约束优化方法有直接法和间接法两种,直接法只在满足约束条件 的可行域内进行搜索,必须保证每次产生的迭代点都在可行域内,且对于求最小/最大问题, 当前点的目标函数值较前一点是下降/上升的,从而直接求出目标函数的最优解,代表方法 有随机方向搜索法、复合形法、二次规划法等。这种方法虽然简单易行,但在多约束条件下, 很难找到问题的全局最优。间接法的基本思想是通过某种手段将约束优化问题转化为无约束 的优化问题进行求解,常见的方法有罚函数法,修复不可行解法,多目标法等。
元启发式算法结合了随机搜索算法与局部搜索算法,可以从目标空间中的多个点开始搜 索,其优化机理不依赖于问题本身的数学结构,通用性强,已被广泛应用于求解多约束组合 优化问题。其中模拟自然界生物集群行为的群智能优化算法以其鲁棒性强、具有自组织和本 质并行性等特点在解决大规模、高维度的组合优化问题方面脱颖而出,其本质是使具有简单 行为的个体通过群体之间的相互协作来解决复杂问题,算法中的每个个体都可以独立保存关 于优化解的信息,进而通过自学习来不断提高个体对环境的适应性。常见的群智能优化算法 有粒子群优化算法(PSO) [3]、人工蜂群算法(ABC) [4]、蚁群算法(ACO) [5]等等。
Eberhart和Kennedy于1995年提出的粒子群优化算法通过粒子之间的信息共享来搜索 复杂搜索空间中的最优解,概念简单、调参少、通用性好,容易与各种约束处理方法相结合, 适合处理具有多类型约束的组合优化问题,并且受所求问题维数的影响较小,搜索性能出众。 因此本文选择用粒子群算法来解决多约束组合优化问题。
对于多约束组合优化问题,没有一种精确的算法可以在多项式时间内对其进行求解,有 的多项式算法都只能得到其近似解。因此,现有的算法大多侧重于通过引入有效的启发式或 局部搜索算子来提高优化效率。诚然,这样的改进通常是有效的和有意义的。但是多约束组 合优化问题与多个约束相关联这个关键问题仍然没有得到解决。约束边界将可行解空间划分 为许多小块,这使得优化过程中会产生大量的不可行解,从而大大降低了最优解的命中率, 因为最优解首先是一个可行解。因此,如何在保证可靠性的基础上得到尚质量的最优解在多 约束组合优化问题研究中具有重要意义。
1.2研究现状
为了提高求解约束优化问题的效率,近年来,研究者提出了大量将约束条件结合到进化算 法的约束处理方法,其中罚函数法和修复不可行解法是最为常用的两种约束处理方法。针对 罚函数法,文献[6]借鉴模拟退火算法的优点,设计出一种在构造罚函数时引入退火罚因子的 动态罚函数法,克服了传统罚函数法在处理约束优化问题时过早收敛到局部最优的缺点。文 献[7]针对在不确定环境下,使最终财富最大化且投资风险最小化的多周期投资组合选择问题, 采用遗传算法与罚函数法相结合的方法对其求解。并通过算例验证了该模型和方法的有效性 和实用性。针对修复不可行解法,文献[8]提出了一种基于“不可行度”的方法来处理约束优 化问题,其中心思想是利用“不可行度”将进化过程中产生的不可行解分为两种,分别是可 接受解和不可接受解。随着迭代次数的增加,使得可接受的非可行解逐渐向可行域靠近,最 终进化为可行解。文献[9]在求解0-1背包问题的过程中,利用贪心变化算法(GTA)将超出重 量约束条件的个体转化为满足重量条件约束的个体,进而完成对非可行解的修复,得到了质 量更高的最优解和多个次优解。实验结果表明,该算法能够有效地求解组合优化问题。文献 [10]针对电机组组合调度问题,将非可行解依次在旋转备用不足、输出功率过量、最小开机 时间以及最小停机时间四个约束条件下进行修复。实验证明,算法在解决大规模机组组合调 度的问题上效果突出。文献[11]则针对动态经济调度问题,提出了一种基于内存的全局微分 进化算法和约束处理修复技术,并且还采用了一种常用的惩罚函数方法来处理与功率平衡和 禁止操作区域(POZs)相关的可能的违反约束行为。经过实验证明,该算法有效可靠。
然而,使用罚函数法处理约束优化问题时罚因子的设定会极大影响算法的寻优效果,各 种修复不可行解法要根据具体问题来设计,通用性很差。因此,多目标法以其不需要设置任 何参数且易与各种问题相结合的优点在约束处理中脱颖而出。文献[12]提出了约束优化问题 的双种群协同进化(DPDE)方法。将约束优化问题作为一个双目标优化问题,其中第一个目 标是要优化的实际成本或报酬函数,第二个目标考虑约束违反程度。在迭代过程中根据解决 方案的可行性,将整个种群分成两部分,分别对应两个目标,每个子群体只注重优化相应的 目标。结果表明该方法具有较强的竞争力和有效性。文献[13]在多目标优化算法的基础上结 合了违反约束度、与约束边界的距离、拥挤度、支配关系这四个环境信息,提出了基于环境 Pareto支配选择策略的有约束多目标进化算法,实验得到了不错的效果。文献[14]将精确农
业系统(PFS)中任务规划应考虑的几个标准,如预期效益、能源消耗或设备损失分别作为目 标,将任务规划看作是一个多目标优化问题,并利用遗传算法和粒子群算法的优点,提出了 一种改进算法MP-PSOGA。为了验证该方法的可行性,进行了一个名为“精确喷洒农药任 务”的仿真。仿真结果表明了该方法的有效性。文献[15]将多约束组合优化问题转化成双目 标优化问题进行求解,并以多背包问题作为算例。实验结果表明,该方法在处理重量与价值 相差较大的多背包问题上表现优秀,但最终能找到的可行解十分少,算法的可靠性不高。
1.3本文主要研究工作
在查阅和分析大量国内外关于启发式算法的相关文献,对比分析己有算法在解决多约束 组合优化问题方面的优劣之后,确定了以下研究内容:
(1)由于将所有约束转化为两个目标的策略在求解多约束组合优化问题上还存在有一定 缺陷,本文将研究把每个约束分别转化成目标的约束转目标策略,并构建一种适用于此策略 的多目标粒子群优化算法。
(2;)由于(1)中所提策略将导致算法中的目标数量增多,使得原本的多约束优化问题转化 成了一个高维多目标优化问题,而解决高维多目标优化问题和以往解决多目标优化问题的方 法存在着相当大的差异,尤其是在如何评价解的优劣方面。由于支配关系会对算法性能造成 一定的影响,因此,本文分别采用松散Pareto支配的排序方法和非Pareto支配的排序方法结 合粒子群优化算法设计出一种适用于高维多目标优化问题的算法。此外,为了进一步提高算 法的寻优能力,使其适用于各种规模的多约束组合优化问题,我们将多种群机制引入到所提 算法中,提出一种基于多种群的高维多目标粒子群优化算法。
(3)针对组合优化问题的特点,对粒子群算法进行离散化操作,将所提算法应用于求解 多约束组合优化问题。
1.4论文主要结构
本论文共分为六章,具体安排如下:
第一章绪论
第二章介绍了目前多约束组合优化问题中常用的几种约束处理方式,并对其优缺点进 行了分析,为本文所要采用的多目标方法提供了理论基础。对多目标法中针对三个及三个以 下目标和三个以上目标所采用的不同方法做了简单介绍。
第三章简要介绍了粒子群算法以及多目标粒子群算法的基本原理,以及用来求解多约 束组合优化问题的粒子群算法需要有何改进。
第四章将约束转化为目标,从而将多约束组合优化问题转化为高维多目标优化问题进 行求解。针对组合优化问题的特点采用多值编码的方式对粒子进行编码,重新确定全局最优 的选取方式并引入扰动变异算子。并且以多背包问题作为算例,验证所提算法的性能。
第五章在第四章算法的基础上进行改进,提出一种基于多种群协同进化的高维多目标 粒子群算法,对粒子的速度更新机制进行改进并引入替换算子来提高种群的多样性,保证算
法的进化能力。最后,通过多背包问题验证算法性能。 第六章总结与展望
2多约束组合优化问题求解方法概述
2.1约束处理方式简介
随着科学技术的不断进步,现实生活中的问题变得越来越复杂,大部分问题中都存在有 形式各异的约束。约束优化问题的挑战源于对决策变量的各种限制,所涉及的约束,约束之 间的干扰以及约束与目标函数之间的相互关系。在解决约束优化问题时,常用的约束处理方 法有以下几种:
(1)拒绝不可行解法:由于约束增多,非可行解在整个解空间中所占的比例急剧上升,
总是拒绝不可行解会导致算法只能在极少的可行解附近进行寻优,可想而知,寻优效果会变
得很差。
(2)罚函数法:罚函数法是使用最为广泛的约束处理方法,在使用罚函数法时,罚因子 被添加到计算解的适应度值的过程中,其目的是降低不可行解的适应度(求最小问题),从 而有利于可行解的选择和进化。即使这个方法的实现方式非常简单,但在设置罚因子时也需 要十分谨慎,因为对解施加惩罚的力度直接决定了算法的优化效果。罚函数法的基本模型如 下:
cp{x) =/(x)+p(x) (2-1)
其中pO)是扩展后的待优化目标函数,P〇)是惩罚函数。
(3)修复不可行解法:修复法在组合优化问题中比较常用,通常是对算法在每一代产生 的不可行解用各种手段进行修复,使其最终成为满足约束条件的可行解。但这些修复算法往 往是根据具体问题来设计的,通用性很差。
(4)多目标优化法:多目标优化的基本思想是将目标函数和约束均作为目标来处理,可 以避免处理约束所带来的麻烦。这种方法在使用时有两种方案,分别是:(a)将约束优化问题 转化为具有两个目标的多目标问题求解,即原本的目标函数作为一个目标,所有约束的违反 约束度之和作为另一个目标;(b)将约束优化问题转化为具有多个目标的多目标问题求解,即 原本的目标函数作为一个目标,每一个约束的违反约束度分别作为一个目标[16]。
综上所述,我们选择多目标优化方法来解决本文中所要研宄的多约束组合优化问题,而 由于该问题约束数量多的特点,将所有约束的约束违反度相加可能会使得算法的可行域变小, 直接导致所找到的可行解很少,算法可靠性变低。所以本文决定采用将每一个约束的违反约 束度分别作为一个目标的方案。
2.2多目标优化
2.2.1多目标优化的基本概念
多目标优化顾名思义是一种可以使得多个目标同时进行优化的方法。目标之间经常发生
相互作用,这些相互作用被划分为冲突或和谐[17]。当一个目标的表现随着另一个目标的变好 而变差时,这种关系被称为冲突关系;而一个目标的表现随着另一个目标的变好而得到改善 则被描述为和谐的关系。
在多目标优化问题中,目标之间往往是相互冲突的,不存在所有目标都达到最优的情况, 因此我们在解决这类问题时,应该综合考虑所有目标,找出几个在目标之间具有良好权衡的 解决方案,尽可能的使所有目标都在一定程度上被优化。
具有D维决策变量,M个目标的多目标优化的模型可以定义如下:


其中x是决策向量,是决策空间,是目标向量,r是目标空间。
另外多目标优化中有两个十分重要的概念,一是Pareto占优,二是非支配解的定义。
2. 2. 2 Pareto占优与非支配解
由于多目标优化问题需要对不止一个的目标进行优化,而各个目标之间势必会出现冲突 的情况,这样一来我们就无法对算法得到的解进行优劣评判。但在多目标进化算法中为了使 每一代产生的解得到进化,我们必须要选出引领进化的解或者淘汰差的解。因此,学者们借 用由意大利经济学家维弗雷多•帕里托在他关于收入分配和经济效率的研究中提出的Pareto 最优概念(即在不损害任何人利益的情况下,不可能再使某些人获得更多的利益,换句话说 就是在达到Pareto最优后,要使某一个人的情况变好,则最起码会有一个人的情况变差,不 会存在共赢的情况)来判断解的优劣,我们将这种支配关系称为Pareto占优,也可以称之为 Pareto支配,它是多目标优化算法中最常用的支配关系,可以被描述为:
任意两个解&满足:
C\/i E {lf2r-f Ml
by e {1,2,.、M}, /;■(') </〆&) 1 J
即在^的所有目标值都不比差的情况下,^至少有一个目标值比义2好,这时我们称^支 配,也称'Pareto占优;r2。在这种情况下,'就是一个非支配解,;则是被 '支配的 解。图2-1展示了双目标求最小问题中解的支配关系。
此外,如果一个解Pareto占优了其他所有的解,则称这个解为Pareto最优解。在多目标 优化问题中,得到的最优解往往不是一个而是许多个,我们将由这许多个解组成的集合称为 Pareto最优解集。由于在大多数应用中寻找Pareto最优解集是NP难的,因此目前存在的所 有多目标进化算法的重点是找到一个尽可能接近真实帕里托前沿的近似帕里托前沿。











A
图2-1.双目标空间中的支配关系
Fig.2-1 Dominance relation in a bi-objective space
2. 2. 3性能评价标准
对多目标优化算法的性能评价一般有以下四种方法:
(1)以图的形式展示结果
以坐标图的形式直观的展示算法得到的结果,一般我们会根据多目标优化算法得到的非 支配解集来画出Pareto前沿,如果有两个目标则最终结果展示为二维平面图,Pareto前沿应 是一条光滑的曲线。如果有三个目标则最终结果展示为一个三维立体图,Pareto前沿为一光 滑的曲面。从图中我们可以清晰的看出算法的收敛性和多样性情况。
\
、-一   —
>
min
图2-2. Pareto解集的优劣比较情况
Fig.2-2 The comparing of Pareto solution set
如图2-2所示,对于图中的A和B两个Pareto解集,很明显A更加接近真实的Pareto 前沿,也就是说A的收敛性比B好。而B在空间中分布的更加均匀,其分布性要优于A。
(2)收敛性评价
Generational Distance (GD)[18]是衡量多目标优化算法的得到的Pareto解集与真实的Pareto
前沿之间距离的一项指标,由这个距离可以反映出算法收敛性的好坏,GD越小意味着算法

获得的Pareto解集距离真实Pareto前沿越近,即算法收敛性越好。当GD=0时,算法得到的 解全都分布在真实Pareto前沿上。GD的计算公式如下:
GD=^(XUdi2)1/2 (2-5)
其中〃是算法所得的Pareto解集中包含的非支配解的个数,^是解集中第/个非支配解到真 实Pareto前沿的最小欧氏距离。
Maximum Spread (MS)[19]是用来计算多目标优化算法所得的Pareto前沿在真实Pareto前
沿上的覆盖率的一项指标,当MS=1时,非支配解集中的解延伸到整个真实的Pareto前沿的 边界。其计算公式如下:
MS = I maX(F〇-min(F〇) j (2_6)
其中/i是非支配解的第/个目标值,6是真实Pareto前沿上解的第/个目标值。
(3)分布性评价
Spacing (SP)™是一个最早由Deb等人提出的用来衡量多目标优化算法得到的Pareto解 集在空间中分布情况的指标。当SP=0时,算法得到的所有非支配解在真实Pareto前沿上呈 绝对均匀的分布状态。SP的计算公式如下:
mean ~ dtY (2-7)
其中木=I# - //1)乂)= 1, ...,n,w是算法所得的Pareto解集中包含的非支配解 的个数,dmean顾名思义是^的平均值。
(4)对收敛性和分布性的综合评价
Inverted Generational Distance (IGD)[21]不仅能够评价多目标优化算法所得的非支配解集 与真实Pareto前沿的距离,同时还能评价该解集在空间中的分布均匀程度。IGD的值越小, 算法获得的Pareto解集距离真实Pareto前沿越近,算法的综合性能越好。IGD的计算公式如 下:
IGD{P\ P) = ^vep^V,P) (2-8)
其中P*是一组均匀分布在真实Pareto前沿上的解,P是算法得到的非支配解集,v是P*中 的个体而是v到P的最短距离。
2.3高维多目标优化
基于Pareto支配的多目标进化算法(如NSGAII,MOPSO等)在经过Hughes[22]的实验后 被证明在解决具有2个或3个这样较少目标的问题时非常有效。然而,随着科技的不断进步, 工程设计中的约束优化问题往往存在更多的约束条件,这就意味着将其转化为多目标优化问 题后的目标数目将不断增多(增加至4个甚至更多),通常我们把目标数超过三个的多目标 优化称为高维多目标优化[23]。
对于有M个目标的问题来说,其目标空间中会出现一个M-1维的超曲面,为了充分的 表示这个曲面,所需的样本个数是M的指数形式。?1^11〇11^[24]等人指出,随着目标维数的 增加,传统的基于Pareto支配的多目标进化算法的优化效果大大降低。这是由Pareto关系的 定义在目标数超过三个的多目标优化问题中不再那么适用所造成的,原因有以下三点:
⑴比如我们现在有A,B两个解,他们分别有10个目标,如果A仅有1个目标值比B 差,而9个目标值都比B好,那么我们一般都会认为A的质量要比B高,A是这两个解中 的最优解,但是按照式(2-4)中Pareto占优的定义,解A和解B是互为非支配的。
(2)随着目标个数的增多,局部非支配目标向量在有限随机生成样本中的比例变得非常 大。由于支配关系是用来推动搜索不断向真实的Pareto前沿靠近,因此对于高维多目标优化 来说,可能没有足够的选择压力来完成这个过程。虽然可以在算法中设计大量的个体来帮助 解决这个问题,但这在许多工程应用中是不切实际的,因为在这些工程应用中对单个候选解 的评价可能需要经过十分密集的计算,这样会在时间上造成极大的浪费。
(3)随着目标个数的增多,非支配解的数量会呈指数形式增长,甚至有可能出现所有个 体都互相非支配的情况,这也都是由于使用Pareto支配后算法的选择压力过弱引起的。在这 种情况下,算法根本无法在迭代过程中选择出真正优的个体,有可能会导致进化停滞,令算 法失去寻优能力。
因此,解决高维多目标优化问题的难点之一就在于选择怎样一种支配方式来评判各个解 之间的优劣关系才能保证算法的寻优能力。
高维多目标优化针对问题的特点可以分为有冗余问题和无冗余问题两类[25]。对于有冗余 的问题可以直接利用目标缩减技术减少目标数,以确定问题所包含的最小目标数,达到消除 冗余的目的。利用给目标降维的方法,假设Pareto前沿表面的真实结构是低维的,但对于所 有目标都相互冲突的问题中得到的折衷表面来说,降维的潜力是有限的。在大规模目标问题 中,寻找所有的Pareto最优解是一个费时费力的过程,我们可以找到一组加入了决策者偏好 的部分Pareto最优解来代替整个Pareto前沿。Branke等人[26]在中提出了一种基于指导的多 目标进化算法,该算法通过允许定义线性最大和最小权衡函数,将用户的偏好引入到进化算 法中。通过一些测试问题表明所提出的算法能够有效地引导群体不断向决策者感兴趣的区域 靠近,从而达到更快的收敛速度并更好地覆盖Pareto最优前沿所在这个区域。文献[27]将基 于偏好的策略与EMO方法结合起来,演示了如何在决策者感兴趣的区域附近找到一组最优 Pareto解集。Brockhoff和Zitzler提出了一种基于关系的目标缩减方法[28],该方法的目的是 找到众多目标的子集,以便根据目标之间冲突的定义度量来保存整个或大部分优势关系。这 种基于关系的目标缩减方法既可以找到具有最小误差的目标子集,又可以找到符合给定误差 的最小非支配解集。以上方法仅适用于预先知道用户偏好信息或者已知Pareto前沿的真实结 构是低维的即知道冗余目标的情况,不具有普遍性[29]。
我们目前研究的多约束组合优化问题主要是无冗余问题。对于无冗余问题,文献[30]提
出了一种基于L-支配的新算法MDMOEA,不仅考虑了需要优化的目标的数量,同时考虑到 了在所有目标的重要性都相同的情况下需要优化的目标函数的值。仿真结果证明,该算法适 用于处理高维多目标问题。文献[31]设计了一种s支配关系,采用配对比较选择和稳态替换 来代替传统的Pareto排序。为了增强选择压力,文献[29]采用了一种全局排序策略,个体排 序值的计算考虑了在每一个目标上群体中所有个体之间的表现差异。文献[32]提出的平均排 序方法(AR)对每个目标上的所有个体进行比较并对其进行独立的排序。对于特定的解决方案, 每个目标的等级是根据其在总体中所有解之间的目标值的级别来分配的。因此,每个解决方 案都有M个等级(其中M是目标的个数),并且通过对它们求和来获得最终等级以便对个 体进行优劣评判。
总的来说,当前所提出的高维多目标优化算法主要分为以下几类[33]:
(1)仍然采用基于Pareto支配的排序方法,但在算法中结合其他方法以缩小搜索空间或 降低目标维数。
(2)采用松散Pareto支配的排序方法。通过放宽Pareto支配关系,能够实现许多难以 评判优劣的个体之间的比较与选择,如L支配,s支配等概念。
(3)采用非Pareto的排序方法。以全新的评价准则对个体进行比较与排序,如基于评价 指标的方法等。
2. 4本章小结
由于在求解多约束组合优化问题时对约束的处理会直接影响到算法的寻优效果,因此, 本章首先对约束优化问题中常用的几种约束处理方法进行了介绍,通过对各种约束处理方法 优缺点的分析,为本文采用的多目标约束处理技术提供了理论上的支持,然后再对多目标方 法的相关概念进行了简单介绍。最后,介绍了多目标优化方法在高维问题上的扩展,为本文 对多约束组合优化问题的研究提供了方法支持。
3粒子群算法与多目标粒子群算法
粒子群算法中的每个粒子都对目前为止自己找到的最好历史位置以及由同伴所找到的 种群中最好的历史位置有记忆。因此在寻优过程中它表现出的目的性更强,也具有更清晰的 寻优方向。粒子群算法在多目标优化中显得尤为适用,主要是因为该算法在单目标优化中具 有较快的收敛速度[34],又因为粒子群算法易与其他算法相结合,所以选用粒子群算法结合多 目标优化算法对多约束组合优化问题进行求解。
3.1基本粒子群算法
3.1.1基本粒子群算法原理及算法流程
粒子群优化算法(PSO) [3]是一种基于群体的元启发式算法,该算法在寻找最优解的过程 中依靠的是群体中所有个体之间的协作和信息共享。在PSO中,一个特定问题的每个解都 称为粒子,而解的总体称为种群,每个粒子都对自己的飞行经验有记忆,可以进行“自学习”, 即知道自己现在的位置A和到自己目前为止发现的最好位置(pbest)。除此之外,每个粒子 还知道种群中所有粒子到目前为止发现的最好位置Cg&est),这一点可以看作是粒子在进行 “社会学习”。以上两种学习方式共同决定了粒子下一次的飞行。
自1995年PSO被提出后就得到了各领域学者的广泛研究。为了进一步提升算法的寻优 能力,1998年Shi[35]提出了用惯性权重〇)来控制粒子的速度变化,这种引入惯性权重的PSO 被称为标准PSO优化算法,在迭代过程中,粒子的速度和位置由下式确定:


其中,fc是迭代次数,N为粒子个数,^和6:2分别是粒子的自学习系数和社会学习系数, ^和r2为[0,1]之间的随机数,惯性权重通常取0到1之间的小数。

基本粒子群算法的流程如下:
(1)初始化一个种群,并初始化种群中每个粒子的速度、位置;
(2)对粒子进行适应度值评价;
(3) 将个体最优初始化为粒子当前的位置,将全局最优gfest初始化为当前种群 中最好粒子的位置;
(4)对每一个粒子,按照公式(3-1)、(3-2)更新其速度、位置并重新对粒子进行适应度值
评价;
(5) 更新户心对和滅;
⑹如果算法达到最大迭代次数,算法结束。反之,转到⑼继续执行。
3.1.2基本粒子群算法参数分析
(1)最大/最小速度
最大速度是种群中粒子在目标空间飞行时所允许的速度上限,最小速度—般是 指与最大速度绝对值相等,符号相反的速度值,即粒子向反方向飞行的最大速度。如果粒子 的最大速过大,可能会导致粒子的搜索不够“精细”,错过最优解。而设置的过小 则会使得粒子的移动速度过慢,且不容易跳出局部最优,不利于寻找最优解。一般情况下, 使— Imax —义min,P?nin —尤min — Imax可以令算法获丫守不辛日的效果。
(2)惯性权重〇)
1998年Shi等对粒子群算法进行了具有里程碑意义的改进,提出用惯性权重〇)来对粒 子的速度变化进行控制,的加入很好的控制了粒子的飞行范围,从而使在粒子的运动 过程中没有那么重要。〇)较大的PSO在全局搜索方面的表现较为突出,而则较小的PSO则 在局部搜索方面表现更出色。一般情况下我们都将〇)设定为一个[〇,1]之间的固定小数,但为 了提高算法的效率,越来越的学者在算法中将0)设置为动态的,即会随着算法迭代次数的 改变而发生改变。一般我们都会令60动态递减,这样一来,在算法运行初期,粒子可以大范 围的在空间内进行全局搜索以发现更多的潜在最优解。随着迭代次数的增加,在算法运行的 中后期,越来越小的0)也就使得粒子更加侧重于精细的局部搜索,有利于算法在已找到的潜 在最优解附近开采到质量更高的最优解。
(3)学习因子
粒子群算法的学习因子分为两部分,第一部分是“自我学习”的系数q,第二部分是“社 会学习”的系数c:2。当Cl = 0时,粒子只向全局最优学习,行为完全不受自身的影响,此 时的算法收敛速度较快,但局部搜索能力差,容易发生“过早熟”的情况,使得算法陷入局 部最优。当c:2 = 〇时,粒子完全只借鉴自己的历史经验完成飞行而不和种群中的其他粒子 进行信息互换,相当于一直在进行盲目的随机搜索,这样会导致算法的收敛速度极慢,大概 率情况下无法找到全局最优解。因此,通常情况下我们设q = c2 = —个常数,意味着粒子 向自己学习和向全局最优学习的比重相同。
3.2离散粒子群算法
粒子群算法最初是针对连续问题而设计的,而连续空间中的向量计算并不能很好地反应 离散状态下粒子的运动轨迹[36],所以要解决组合优化问题,粒子群算法必须被离散化。在解 决连续函数问题时,PSO成功的关键在于它跳出了已知的局部最优,探索了粒子之间以及原 本的群体之外的情况。那么在离散空间中,诸如轨迹、速度、间隔和超越等概念的定义成为 了一个值得研究的问题。
在1997年,Kennedy和Eberhart最先针对离散优化问题提出了离散的二进制粒子群算 法(BPSO)[37]。在该算法中,每个粒子用二进制的值0或1来表示其在空间中的位置,粒子 的速度定义为粒子状态变为1的概率。也就是说,在他们的BPSO模型中粒子的位置将用来 决定“是”与“非”的关系,其速度与位置的更新如下:


而后的几十年里,学者们依然在探索其他的方法去处理离散优化问题。目前在离散粒子 群算法研究方面主要有两种方针,一是仍然使用基本粒子群算法的速度和位置更新公式,只 是将粒子的连续位置空间离散化,再通过粒子在连续空间的飞行引发离散状态的变化。文献 [38]提出了一种取整粒子群算法,在计算时将粒子的小数部分舍去,使得种群直接在整数域 进行进化搜索。二是只保留粒子群算法信息交互的基本框架,舍弃粒子的速度更新机制,采 用位置跳变的方式来实现粒子在离散空间的位置变化。文献[39]基于交换原理重新定义了粒
子群的位置更新公式,整个更新过程分为三部分,首先交换粒子位置矢量的第/维和第y维,
/和y是两个不同的随机数,其次根据个体极值Pbest调整粒子的位置,最后再根据全局极值 Gbest调整粒子的位置。由于直接对粒子位置取整的操作会使得下一代粒子受上一代粒子的 影响较大,不利于算法跳出局部最优,文献[40]对最先是由Clerc设计的原理为离散点位置 交换的粒子群算法做了一些改进,提出了一种新的交换粒子群算法,并用多背包问题和车辆 路径问题作为实例验证了该方法在求解组合优化问题的过程中比取整粒子群算法更有优势。
本文将采用一种改进的交换粒子群算法[15]来求解多约束组合优化问题,该方法已被证 明在处理组合优化问题时可以使算法的收敛速度加快,并提升算法的寻优能力。在这个方法 中,基本PSO的速度和位置更新公式改进为式(3-5)和(3-6):
4+1 = ㊉q ㊉c2 (3-5)
4+1=*4 ㊉ 4
(1)位置减操作®
两位置相减表示速度,x减y时,用x直接替换y,表示为
(2)速度加操作㊉
速度相加得到一个新的速度,假设v = a —&w = x —y,则
(3)位置加速度操作㊉
(4)系数乘速度操作 d和系数C均为(0,1)之间的随机数。
再根据向个体最优粒子和全局最优粒子学习的思想,将公式(3.10)更新为如下所示:
吃 代! = 4
Pgd if 0! > rand(0,1) (3-11)
rand else

3.3多目标粒子群算法
3.3. 1多目标粒子群算法
由于多目标问题最终求得的是一组Pareto最优解,而不是像单目标问题那样只有一个最 优解,因此将PSO推广到MOPSO时需要处理两个问题,一是怎样把从算法运行之初到结 束所找到的优解保存下来,而二是如何选取个体最优和全局最优去引导粒子飞行。
由于粒子群优化算法基于群体的特性,在一次运行中产生多个不同的互不支配解这样的 方案是可行的,Codl等人率先在PSO中引入外部档案的概念[41],使用相当于第二个种群的 外部档案来保存算法运行到现在找到的所有互不支配解,这时引导粒子飞行的全局最优个体 就应该从外部档案中产生。那么一个个体要满足怎样的条件才能进入外部档案中呢?第一种 情况是这个个体与目前外部档案中存放的所有个体都互不支配;第二种情况是这个个体支配 了外部档案中的某一个个体,在这种情况下,被支配的个体应从外部档案中移除。而个体最 优应根据上一代个体与现有个体之间的支配关系来选择。
然而这样处理非支配解有一个致命的缺点,外部档案中非支配解的数量会随着算法迭代 次数的增加而急剧增加,因为外部档案在每一代都需要更新,从计算的角度来说,如果其存 储量过大,更新可会变得非常耗时,基于这一点,外部档案必须是有界的[42]。当外部档案存 放满以后,我们需要采用一种特定的规则去维护它。在进化多目标优化中,学者们提出了很 多种维护这种存放所有非支配解的档案集的策略。文献[43]引入聚类过程在不破坏非支配解 集特征的前提下减少外部档案中存放个体的数量。文献[44]提出了一种基于递归分割目标空 间的新的拥挤度策略。当一个解产生后,它的网格位置也就随之确定,然后釆用自适应方法 对网格空间进行递归细分并分配网格位置。这种自适应方法的工作原理是计算档案中当前解 在目标空间中的范围,并调整网格使其覆盖该范围,然后重新计算网格位置,每个网格位置 的使用构成了维护外部档案的重要部分。
3.3.2高维多目标粒子群算法
为了适应目标数超过3个的高维多目标优化问题,近年来也有许多以多目标粒子群算 法为基础的改进算法被提出。文献[45]采用了一种名为控制解的支配区域(control of dominance area of solutions, CDAS)的方法结合粒子群算法提出了 CDAS-SMOPSO算法。该 方法利用一个有用户自定义的参数S来控制支配区域的扩张或收缩程度,在解决高维多目标 优化问题中取得了不错的效果,但其缺点是S的取值与目标个数、搜索空间的大小和问题的 复杂性密切相关。文献[23]提出了一种改进的多目标粒子群算法I-MOPSO (Ideal Point Guided MOPSO)去探讨多目标粒子群算法在处理三个以上目标方面的一些问题,该算法利用一种新 的存档方法获得更好的收敛性,将解引导至帕里托前沿的理想点附近,并将搜索的多样性由 领导者(个体最优Pbest和全局最优Gbest)的选择策略中引入。在文献[46]中作者针对高维 多目标优化问题提出了基于两步搜索的粒子群算法(Two-Step-PSO),第一步将一个种群划分 为许多组,每一组对每个目标函数及其中心进行单目标搜索。第二步通过PSO搜索,在第
一步所得到的解的基础上,以全局最优为目标保证了解的多样性。实验结果表明该算法在收 敛性方面有着不错的优势。文献[47]将粒子群算法与遗传算法相结合,允许外部档案中存储 的各个个体之间进行交换“精英”信息,并提出了一种平衡适应度估计方法,该方法在进化 过程中同时在一定程度上兼顾了算法的收敛性与多样性。
3. 4本章小结
基本粒子群算法是针对连续问题设计的,而组合优化问题的目标空间是离散的,因此在 解决多约束组合优化问题时,我们需要对基本粒子群算法做出改进。本章首先介绍了基本粒 子群算法以及针对组合优化问题而设计的离散粒子群算法。其次,因为粒子群算法是针对单 目标问题设计的,而多目标问题与单目标问题存在本质上的不同,所以我们对多目标粒子群 算法做了简单的介绍。
4多约束组合优化问题的多目标求解方法
4.1多约束优化问题的多目标形式
本文采用多目标优化的方法,将每个约束对应转化为一个目标来求解多约束组合优化问 题,避免了处理约束所带来的麻烦。转换后的多目标形式如下:
Minimize f{x) (4-1)
Minmize ^(^(x)) (4-2)
Minimize h(g2 (x)) (4-3)
Minimize h(gm(x)) (4-4)
厂是原目标函数,/iCg(x))表示违反约束度,定义如下:
h{gi(x)) = (4-5)
Pm(X)代表违反第爪个约束的程度。
转换为多目标形式后的多约束组合优化问题可以总结为式(4-1)、(4-2)、(4-3)以及(4-4), 但是转换后的问题与求解连续函数问题的多目标法求解重点不同。在求解连续函数问题时主 要是要找出在目标空间中均匀分布的Pareto前沿,而针对多约束组合优化问题的多目标方法 则将重心放在如何得到可行解上。那么转化后问题的最优解应该满足/1(仍〇〇)=0 (/=0,l...m;) 且使得原目标函数最小。
4.2改进的多目标粒子群算法
在研究多约束组合优化问题的过程中,需要慎重的选择一个测试问题去验证所提算法的 有效性。首先这个问题应该是便于人们理解且易于设计的,使实验具有可重复性和可验证性, 其次它也应该是一个相当普遍的问题,可以理想的代表现实生活中的某一类问题。而多背包 问题则很符合以上两点要求[43],它的问题描述很简单,但是问题本身较难解决。作为一个经 典的NP难问题,现实生活中有很多实际问题都可以用MKP作为模型,比如车辆调度、投 资决策、资源分配等。因此,我们选用MKP作为算例来验证本文提出的算法在解决多约束 组合优化问题中的效果。
4.2. 1外部档案维护
MOPSO与单目标粒子群算法的最大不同之处在于,它的最优解不是一个个体而是一个 集合,需要根据粒子的支配和非支配关系,将每一代产生的所有非支配解保存在外部集(外 部档案)中,并使其在迭代过程中进行更新,如果新一代种群中有粒子支配了外部档案中的 某个粒子,则用该粒子去替换外部档案中被支配的那个粒子。由于全局最优粒子的选择是通 过外部存档来完成的,因此对该存档进行妥善的管理是至关重要的,对算法性能有着巨大的 影响。外部档案的规模可以由自己设定,小于或等于种群规模均可,一般利用网格法[41]或拥 挤距离[48]来保证外部档案的规模不超出这个限制。如果外部档案中非支配解的个数超出其规 模限制,则删除最拥挤地区的一个或几个粒子。
而在求解组合优化问题时,我们关注更多的是算法的收敛性,且要在满足众多约束条件 即违反约束度十分小的区域内进行求解。因此,我们根据违反约束度来对外部档案进行维护。 在算法的每一次迭代中,如果外部档案的规模超出限制,则删除违反约束度大的个体,促使 种群向违反约束度小的区域聚集。
4. 2. 2全局最优的选取
在多目标优化算法中,为了防止陷入局部最优,全局最优个体一般取外部档案中拥挤度 密度最小的个体,但这种选取方式存在着一定的缺陷,因为处于拥挤度密度最小地区的个体 很有可能远离真实前沿面,如果选择其作为全局最优,可能导致最终得到的解在空间中松散 地分布,但却远离真正的Pareto最优前沿,影响算法的寻优能力。比如在A (0,1,1,100),B (1,2,1,0),C(l,0,2,l),D(2,l,0,l)这四个点中,很明显A的收敛性最差,但多样性却是最好。 因此,本文在全局最优的选择上采用一个新的标准CD,对第Z个个体^有:
CDt = y x Crowding(Xi) — /3 x Distance(xi) (4-6)
其中,CrowdZn〆^)是第/个个体的拥挤密度估计值,本文采用Harmonic平均距离[49] 对种群中的所有个体进行全局密度估计。是第/个个体距离理想点(外部档案 中个体在第m个目标上的最小值组成的点)的欧氏距离,用来表示该个体距离真实前沿的 距离。y和八均为[0,1]之间的小数,且7 + 0 = 1。s为外部档案集中个体的数量,对aM直由 大到小进行排序,在排序后的第1〜SX0.05个非支配个体中随机选取一个作为全局最优。其 中拥挤密度估计算子伪代码如下:
全局最优选择伪代码:
1s=|I| %1为外部档案,s为I中所包含个体的数量
2for each i
I(CrowJz>?g(z))=Harmonic(z)
\{Distance{i))= Euclidean(I, ideal point) % ideal point 为理想点 \{CD{i))= y Xl(Crowding(i))-l3 Xl(Distance(i))
3I=sort (I(C£)(z))) from max to min
4/=random(0, sx〇.〇5)
5Gbest- I(Q
这个操作相当于对个体的收敛性和多样性做了一次综合评估,有利于我们找到真正意义 上的全局最优个体。
4. 2. 3个体最优的选取
多目标粒子群算法以及高维多目标粒子群算法中个体最优的选取不能仅仅依靠比较两 个个体之间适应度值的大小,而是需要比较两个粒子的支配关系,如果个体最优支配新的粒 子,则个体最优值不变,反之,新的粒子成为个体最优。针对组合优化问题,为了提高算法 的收敛性,若个体最优与新的粒子互为非支配,我们选择距离理想点近的那个作为新的个体 最优以引导粒子向更优的解移动。
4. 2. 4扰动变异算子
为了避免种群过早的陷入局部最优,我们在算法中加入了一个扰动变异算子。在算法运 行初期要尽可能的搜索整个目标空间,所以需要较多的粒子参与变异操作,而在后期,为了 避免已搜索到的潜在最优解被变异,就要减少参与变异操作的粒子个数,因此变异率 尸腿_▲由公式(4-7)确定,变异率随着代数的增加从0.9线性减少到0.05。
Pmutation = 0.9 - (0.85 / Maxgen) x t (4-7)
其中为算法迭代的最大次数,〖为算法目前的迭代次数。
对于种群中的每一个粒子,pm是[〇,1]之间的一个随机数,如果pm小于则在 该粒子的m个位置中随机选取一位按照公式(4-8)进行变异,使得粒子随机选择与目前相同 或相反的方向飞行。其中0是一个大于1的数,目的是为了加快粒子的飞行速度,使其能够 跳出局部最优。
x^-(t) = Randoms elect (-1,1) xpmx 6 x (4-8)
如果变异操作使得粒子的位置超出限制,则按图4-1所示将其拉回边界,并使得该粒子 在下一代向相反方向搜索目标空间,速度设定为原来的二分之一,这样一来粒子的速度也有 了限制,不会无限地增大。

The position boundary of a particle
图4-1粒子位置超出边界示意图 Fig.4-1 Particle position beyond the boundary

由于本文采用了交换粒子群的位置更新方式,该方式舍弃了粒子的速度更新部分,但考
虑到变异操作中需要用到粒子的速度,所以仍按照公式(3-1)对粒子的速度进行更新。但是为 了使得算法具有更好的寻优能力,我们采用动态的粒子群算法,将速度更新公式中的三个参 数惯性权重〇)和学习因子Cl、6:2分别设置为动态变化的,他们的值全都只与算法目前的迭代 次数有关。已有研宄证明,在设置惯性权重0时使用凸函数递减法对于情况复杂的多峰函数 的寻优更为适用[5()],比起线性递减和凹函数递减能获得更高的精度和收敛速度。鉴于多约束 组合优化问题的目标空间比较复杂,并且可能存在多个优解,因此本文采用凸函数递减的方 法来处理惯性权重。
如图4-2所示,根据经验,我们令〇)由0.9逐渐递减至0.4, Cl随着〇)的减小而减小,6:2则
随着^的减小逐渐增大,意味着算法从运行初期侧重于全局搜索逐步演变至侧重于局部搜索, 也就是说这一操作可以让粒子在前期尽量进行大范围的搜索,而在搜索到一定程度后将重心 转移至在目前搜索到的优解附近进行细致的搜索,改善解的精度,从而增加发现潜在最优解 的可能。参数的更新方式如下:
t+i
Maxgen Maxgen
cx — 0.5 x 〇)2 + 3 x 〇) c:2 = 4 - q
其中为算法迭代的最大次数,/为算法目前的迭代次数。
图4-2IMaOPSO算法的速度参数变化 Fig. 4-2 Parameters variation of velocity in IMaOPSO

4. 2.5 IMaOPSO算法流程
本文针对多约束组合优化问题所提出的改进高维多目标粒子群优化算法IMaOPSO的基 本流程如图4-3所示:

4. 3支配关系的选择
在第二章第三小节我们已经阐述了高维多目标优化算法中支配关系的选择对于算法的 寻优能力有着至关重要的作用,以及目前在高维问题上支配关系的选择大致分为哪几类,在 此不做过多赘述。由于支配关系很大程度上会影响算法的寻优效果,为了避免因支配关系的 选择而对算法造成影响,本文选用了两种不同的支配排序方式,一是松散的Pareto排序方式, 二是非Pareto的排序方式来配合前面所提出的改进高维多目标粒子群优化算法(IMaOPSO) 对多约束组合优化问题进行求解。
4. 3. 1模糊支配
2004年,M.Farina等人提出了(l-fcF)模糊支配策略[51],以一个个体比另一个个体目标 值好的数量来衡量个体的支配关系,其优点是使支配关系的复杂程度不受目标数量多少的影 响,但是只考虑一个目标是否优于另一个目标,而不考虑它比另一个目标好多少,这种方法 只能对寻找最优解做出粗略的指导,并且这种支配策略会导致种群中的个体陷入循环支配。 例如:在求最大值的问题中,对于表4-1中的A,B,C三个个体而言,B有2个目标值比A 好1个目标值比A差,所以B支配A; C有2个目标值比B好1个目标值比B差,所以C 支配B;而A又有2个目标值比C好1个目标值比B差,所以A又支配了 C,这样就导致了 图4-4中出现的循环支配。这样会使种群中不存在非支配解,导致算法在Pbest以及Gbest 的选择过程中无法选取到优秀的个体,影响算法的寻优能力。
表4-1个体A,B,C Table.4-1 Individuals A, B, C


因此,本文采用文献[52]中一种改进的模糊支配关系,设置一个能量参数Pw作为整体衡 量该个体目标函数值大小的标准。Pw是一个标量值,具有传递性,可有效防止个体陷入循 环支配。
Pw
式中^ 为参考点。
为了验证该支配关系对离散数据的有效性,我们在每个个体的目标数分别取3、6、9、
12、15、18、21的情况下每次随机生成200个个体作为一个种群。对同一组数据,分别使
22
用Pareto支配和改进的模糊支配进行实验,统计出在各目标取值下非支配个体在整个种群中 所占的比例。如图4-5所示,当目标个数超过9时,传统Pareto支配下的目标空间中非支配 个体的比例己经超过90%,当目标个数超过15后,几乎种群中所有的个体都互为非支配。
20 10 0
图4-5 Pareto支配下非支配个体比例
Fig.4-5 The proportion of non-dominated individuals with Pareto dominance
图4-6展示了在改进的模糊支配下目标空间中非支配个体占种群总个体的比例情况。我 们可以看出,与图4-5相比各个目标数下的非支配个体比例明显下降。当目标个数增至21 个时,非支配个体的比例还未达到10%,并且非支配个体所占的比例并没有随着目标个数的 增加而出现明显的增幅,证明该方法稳定性良好,能够作为高维目标情况下寻找最优解的有 力保障。
图4-6改进的模糊支配下非支配个体比例
Fig.4-6 The proportion of non-dominated individuals with improved fuzzy dominance

4. 3. 2 a支配
由于在高维多目标优化问题中目标的个数较多,我们无法保证让每一个目标的目标值都 达到最优,这时就必须采用折衷的办法,在保证某几个目标最优的情况下,使得其他几个目 标也不要太差。因此,我们采用a支配[53]来代替传统的Pareto支配。以灸个目标的最小化 问题为例,《支配的定义如下:
对于一个个体的所有目标值/!(x),/2(x),…A(x),XEX,Z为问题的可行域。
gi(xlfx2) = /^Xi) -/^(x2) +2^0: X (/yfe) -/y(x2)) (4-13)
其中,Xp x2 E X。当Vi,仍(x1;x2) < 0,并且3i,使得仍(x1;x2) <0,此时我们称解x:L a支配
解x2。也就是说,如果解;^的一个目标值比x2稍差但其他目标值远好于x2,贝ij还是将;^判断 为比x2好。
图4-7展示了在a支配下目标空间中非支配个体占种群总个体的比例情况。与改进模糊 支配一样,非支配个体所占的比例并没有随着目标个数的增加而出现明显的增幅,证明了该 方法对于高维多目标优化问题有着一定的有效性。
20 10 0
4. 4 IMaOPSO 算法求解 MKP 4.4. 1 MKP的数学模型
多背包问题(MKP)是指有m个背包,每个背包都有自己的最大可承受重量限制 {clfc2f……cm},要将重量和价值分别为{w^ W2,……Wn], {plfp2f……PrjW n个物品分别装 入其中,使其尽可能的装满这些背包,以实现所有背包所装物品的价值总和最大,并且满足 每个背包所装物品的总重量不能超出其最大承重限制的约束条件。其数学模型可以描述为:
Maximize (4-14)

s.t. Yi=i ^i,j ^ Cj M j = 1,2,..., m
Xq E {0,1}, i = 1,2, ■■■, n; j = 1,2, m
i = lf2f...m (4-16)
4. 4. 2粒子的编码方式
(1)二值编码
二值编码是指用计算机语言中的0-1码串来进行编码,将问题可能的解用一个二值矩阵
表不。其中0表不该物体被选中,1则表不:该物体没有被选中。假设我们现在要将6个物品
放入4个背包中,第1件物品放入第3个背包,第2件物品和第6件物品一起放入第2个背
包,第3件物品和第4件物品一起放入第1个背包,第5件物品则放入第4个背包。以上对
物品的处理方式可以用如下矩阵来进行编码:
/0 0 1 1 0 0\
/ 0 1 0 0 0 1 \
1 1 0 0 0 0 0 I
\0 0 0 0 1 0/
在二值编码中矩阵的行数等于背包个数,矩阵的列数等于物品件数。那么如果我们有N 个背包和m件物品,矩阵的大小就是厂x'即有个候选解。随着背包个数和物品数量 的增加,候选解的个数将呈指数形式增长,这会大大影响算法的求解速度,并且在迭代过程 中还可能使矩阵的每一列出现多个1,这表示某一件物品被同时放入了几个不同的背包中, 而这种情况在实际生活当中是不可能出现的。这时如果用修复法强行将1修正为0,会影响 到算法的进化水平,导致算法的寻优能力变弱。
(2)多值编码
多值编码,顾名思义编码的值不只有0和1,而是有多少个背包就有多少个编码,例如 我们要将5件物品放入3个背包中,可行解(1,0,3,2,1)就表示第1和第5件物品放入第1个背 包,第4件物品放入第2个背包,第3个物品放入第3个背包,而第2件物品不放入任何一 个背包。这样一来,在背包个数〃和物品件数m增多时,也只会导致编码的长增加,候选 解的个数为+ 远小于采用二值编码的2nxw。并且不会产生一件物品被放入多个背
包的不合理情况。
通过以上分析比较,我们将采用多值编码的方式对粒子进行编码。
4.4.3 MKP的多目标形式
我们将每一个背包所装物品不超出其最大承重限制分别作为一个目标,这样一来,有m 个背包的MKP就被转化成了具有m+1个目标的超多目标优化问题,具体描述如下:
Minimize F(x) = c//(x) (4-17)
Minimize //(^(x)) = max(〇J<g1(x)) (4-18)

其中,C是一个放大系数,在这里我们取c=l,/(X)是m个背包的总价值,=
1,2,m)表示第灸个背包的违反约束度,pjx)是第灸个背包重量超出其重量限制的部分。
4. 4. 4结果展示方式
与求解连续函数问题的高维多目标粒子群优化算法不同,我们的目的不是要获得一个均 匀分布的Pareto前沿,而是要使所有目标的违反约束程度尽可能的小。由于超多目标问题 的最终结果不易展示,目前最常用的是平行坐标[54]的方式,但对于MKP我们最关心的是最 终得到的非支配解集中解的分布情况,其中的可行解必定有m-1个目标值都是等于0的,许 多非可行解也有多个目标值等于0,使用平行坐标的方式根本不能反映出可行解与非可行解 的分布情况。同时,我们也无法通过第二章第二小节中介绍的几种指标来评价算法的性能。
因此,为了能直观的表示目标空间中可行解与非可行解的分布情况以及最优解在目标空 间中的位置,如图4-8所示,我们令背包总价值F(x)为横坐标,m个背包的违反约束度之和 为纵坐标,从而使得m+1维图形变为二维图形。图中所有红色圆点均表示外 部档案中的非支配解,当时,得到的为可行解,其他的均为不可行解。而 可行解中使F(x)最小的即为最优解。
非可行解 •
H 喻(x)>
i=l
图4-8将超多目标的非支配解集用双目标展示
Fig.4-8 Displaying the non-dominated solutions of MaOP with two objectives
4. 5参数分析
在本文所提出的求解多约束组合优化问题的算法中,有三个参数的设置会对算法结果产 生较大的影响。一是使用a支配排序时折衷比例a值的选择,二是进行全局最优的选择时拥 挤距离与距理想点距离的比值iS/y。三是加入扰动变异算子后扰动系数0的选择。为了分析
这两个参数在算法中的影响,我们随机生成一个m=5,〃=200的背包数据,将不同a值、不 同P/7以及不同0下的算法分别运行10次,每隔500代选出最好的适应度值并对其求10次 的平均值来观察算法能找到的最好适应度值的走向。现在以随机生成的一个多背包算例,分 析这两个参数的取值对算法求解多约束组合优化问题的影响。
(1)折衷比例a
在使用a支配排序时,a值的选择至关重要,它代表着每一个目标值与其余目标值的折 衷比例。已有文献指出,如果a过大,会导致算法的多样性变差,而a值过小又会导致算法 的收敛性变差[53]。因此,本文在[0.1,0.5]区间内每隔0.1选取一个参数,分析a在取多大值 时算法的寻优效果最佳。每次实验除a外,其他参数均相同。图中用A表示a的取值,不 同a下算法的适应度值随迭代次数的变化曲线如图4-9所示。
从图中我们可以看出,当a=〇.l时,寻优曲线的上升高度最低,意味着算法的寻优效果 不佳。当a=0.3时,明显可以看出算法的收敛速度最快,且当别的取值下寻优曲线几乎不再 变化时该取值下的曲线依旧有上升趋势,也就是说a=0.3时算法的持续寻优效果最好。当 a=0.4时算法收敛速度虽然也比较快,但还是比a=0.3时稍差。因此,a应取在[0.3,0.35]之间 较为合适。

(2)全局最优选择参数
在单目标优化问题中,我们可以直接选取适应度值最大的解作为全局最优Gbest,而在 多目标优化问题中,由于最终所得到的最优解不止一个,所以Gbest这一“领导者”的选择 成为了一个问题。Gbest的作用是领导种群中的粒子朝好的方向飞行,本文釆用拥挤距离与 个体距理想点的距离相结合的方式来选取Gbest,然而拥挤距离和个体与理想点的距离各自 所占的比例也是需要我们考虑的。因此,我们选择了 5种情况来进行分析,用proportion表 示拥挤距离所占的比例,1-proportion表示个体与理想点的距离所占的比例。
从图4-10⑻、4-10(b)中可以看出,当proportion=l时,表示Gbest完全根据拥挤距离选 取,这时算法的收敛速度很慢,proportion递减至0.8、0.5后,算法的收敛速度逐渐增加。 而当proportion=0时,意味着Gbest仅依靠个体与理想点之间的距离来选取,此时算法的收 敛性虽好于proportion=l、0.8、0.5的时候,但不及proportion=0.3的时候。实验结果表明, proportion在[G.2,G.3]区间内选择可以使算法的效果达到最优。



1.01  1 1 1 1 1 1
0 2000 4000 6000 8000 10000 12000
迭代次数

(a)改进模糊支配下proportion对适应度值的影响 (a) The influence of proportion with the improved fuzzy dominance on fitness value

0 2000 4000 6000 8000 10000 12000
迭代次数
(b) a支配下proportion对适应度值的影响 (b) The influence of proportion with a dominance on fitness value

图4-10不同proportion取值下的适应度值对比
Fig.4-10 Comparison of fitness values in different proportion
(3)扰动系数0
扰动系数0表示粒子加速飞行的倍数,也就是说在加入扰动变异算子后被选中的粒子会 以原先速度的0倍加速飞行。选择合适的扰动系数可以帮助算法跳出局部最优,扩大粒子的 搜索空间,提高能找到的最优解的质量。本文在[1.5,3.5]区间内每隔0.5选取一个参数,分析 0在取多少时可以使算法性能最优。本次实验除0外,其他参数均相同。
从图4-ll(a)和4-ll(c)中可以看出加入扰动变异算子后,算法的收敛速度有了明显的提 升。为了能够明显的看出0对算法性能的影响,将图4-11⑻中的I部分进行放大,如图4-ll(b) 所示。对比图我们可以看出,0=1.5时算法的收敛速度较慢,寻优能力差,这表明粒 子速度增加的幅度较小,能搜索到的目标空间范围较小,跳出局部最优的能力也较弱。而当 0=3时算法的收敛速度最快且能够找到的最优解比0=1.5,0=2,0=2.5以及0=3.5时算法找 到的最优解都好,也就是说当扰动系数0过大时算法性能也不好,因为粒子飞行的速度过快, 有可能错过很多潜在最优解。综上所述,取0=3。









6000
〇 OOOOOOOOOOOOOOOOOOOO 1—
0 2000 4000 6000 8000 10000 12000
迭代次数
(a)改进模糊支配下0值对适应度值的影响
(a) The influence of 6 with the improved fuzzy dominance on fitness value
xl(T
1.034 1.032 1.03 麵 1.028 ® 1.026
(b)图⑻中I部分的放大
(b) The enlargement of part I in (a)



(c) 0C支配下6/值对适应度值的影响 (c) The influence of 6 with a dominance on fitness value
图4-11不同0取值下的适应度值对比 Fig.4-11 Comparison of fitness values in different 6

4. 6算例实验
为了验证本文提出的IMaOPSO算法的性能,我们将基于两种支配排序方式的IMaOPSO 算法即基于改进模糊支配的IMaOPSO(我们称为IMaOPSO(F))和基于a支配的IMaOPSO(我 们称为(IMaOPSO(a;〇,与离散双目标MOPSO算法(M-IMOPSO)[15]以及第二章提到的几种常
用的求解约束优化问题的约束处理方式进行对比,对比算法分别为基于罚函数法的人工鱼群 算法(P-AFSA)、基于修复法的人工鱼群算法(V-AFSA)以及基于罚函数法的粒子群算法 (P-PSO)进行比较,并选用文献[55]中设计的物品价值与重量相近的一组MKP算例(物品重 量和价值的数值范围分为三组,R =100,R=l〇〇〇,R=10000,其中重量%在[10,R]中随机 生成,而价值仍在[1^-1^/10,1^ + 1^/10]中随机生成)进行实验。在物品的重量与价值相 近的情况下,为了使背包中装入的物品价值尽可能的大,放入的物品重量也会较大,这样一 来就很容易超出背包的重量限制,也就是说问题的可行域变得很小,求解难度变得更高。 实验分为以下两种情况:
(1)5 个背包,200、500 和 1000 件物品(m=5,=200、500、1000)。
(2)50 个背包,200、500 和 1000 件物品(m=50,n=200、500、1000)。
每组中的背包容量数据又分为两种:
(1)相似背包容量(Similarknapsack): C/随机生成,生成范围为
0.6
(2)非相似背包容量(Similarknapsack): cy随机生成,生成范围为[0,0.5(及=11^-
计算机仿真在PC上使用Visual C++ (CPU 2.40GHZ,4GB),并在10个独立运行的实 验中执行。算法参数设置如下:种群规模POPSIZE设为200,外部档案规模为120,最大迭 代次数为10000。
对每一个算例,我们用其在10次独立运行下的最优解平均值作对比,表4-2和表4-3 分别为5个背包和50个背包在物品数为200、500、1000时的实验结果,其中最好的解用黑 色加粗字体标出,表示算法在求解过程中得到的全部是非可行解。由表4-2可以看出, 当背包个数为5时,IMaOPSO算法在对200及500个物品的求解中具有明显的优势,除当 物品数为1000时有2组相似数据的求解结果不如M-IMOPSO外,其余结果均好于P-AFSA 算法、V-AFSA、P-PSO算法以及M-IMOPSO算法。由表4-3可以看出,当背包个数为50 时对1000个物品的数据求解中有4组结果不如P-AFSA算法以及V-AFSA算法。也就是说, 对MKP的36组数据进行求解时,有6组结果不理想,通过以上数据可以看出本文算法在求 解物品数较少的中小规模MKP问题上有着明显的优势,但在处理物品数较多的大规模MKP 问题时还存在一定的缺陷。
虽然IMaOPSO算法对于大规模MKP问题的求解效果不是很理想,但与基于罚函数法 的粒子群算法P-PSO相比,后者在所有类型的数据中几乎都找不到可行解,这说明多目标 法在处理多约束组合优化问题时比起单目标方法有很大的优势。此外,本文算法在对以上 36组数据求解时仅有2组数据求解效果不如基于双目标的M-IMOPSO算法且差距不大,这 一结果充分说明了将每一个约束对应的转化为一个目标的约束处理方法在解决多约束组合 优化问题时是有效的且表现优秀,即本文所提出的约束处理方法与算法是具有借鉴意义的。
表 4-2 m=5,=200,500,1000 的实验结果
Table.4-2 Experiment of m=5 and /?=200, 500, 1000



表 4-3 m=50,=200,500,1000 的实验结果
Table.4-3 Experiment of m=50 and ^=200, 500, 1000


图4-12展示了对于随机生成的MKP算例,本文所提出的IMaOPSO算法与基于约束转 双目标的M-IM0PS0算法最终得到的解集的对比,由于a支配排序方式属于非Pareto排序, 所以得到的图形不能称为Pareto前沿,它只是单纯的展示了算法所得解集在目标空间中的分 布。显然,通过两种支配排序方式的配合,验证了本文算法不仅获得可行解的数量多于 IMOPSO,且得到的可行解更优。

图4-12 IMaOPSO算法与M_IMOPSO算法得到的解集对比 Fig.4-12 Comparison of solution sets obtained by IMaOPSO and M IMOPSO

由于改进模糊支配是一种松散的Pareto支配方式,在这种支配方式下的算法依旧具有完 整的Pareto前沿,我们可以用图4-8所描述的方式将其表现在二维空间。因此,为了能够直 观的表现出IMaOPSO算法的性能,我们选用基于改进模糊支配的算法来观察其迭代过程中 的收敛情况,验证算法的收敛性。
图4-13展示了求解随机生成的MKP算例时IMaOPSO算法的收敛情况。我们可以清楚 地看到,在算法运行初期解都集中在目标空间的右下方,这时背包的总价值很大,但违反约 束的程度也很大。随着代数的增加,目标空间中的解在不断向目标空间的左下方靠近,即所 有背包违反约束度越来越趋向于0,背包价值总和则越来越大,符合我们的预期。运行至 10000代时,得到了我们所需要的满足所有约束条件的最优解。
x1〇-5
1.99
1.98
1.97 1 95
0 200 400 600 800 1000 1200 1400
H(x)
图4-13 IMaOPSO算法收敛情况 Fig.4-13 The convergence of IMaOPSO
4. 7本草小结
本章针对多约束优化问题的特点,将问题的每一个约束分别转化成目标进而将原问题转 化为高维多目标优化问题进行求解。在Pareto支配关系对高维问题无效的情况下,采用松散 的Pareto排序方式以及非Pareto排序的方式与高维多目标粒子群算法相结合,保证算法的选 择压力。针对组合优化的特点,采用个体与理想点之间的距离与拥挤度相结合的方式选取种 群的全局最优Gbest,以兼顾算法的收敛性与多样性。最后选用MKP这一典型的多约束组 合优化问题作为实验算例,对其进行求解。实验结果证明,本文算法在求解多约束组合优化 问题上有着良好的表现。


5求解多约束组合优化问题的多种群IMaOPSO算法
在粒子群算法中,种群中的粒子就像一群集体飞过超维空间寻找潜在最优解的鸟一样, 这些粒子的行为同时受它们从自己过去的飞行经验中学习和它们的同伴调整飞行速度和方 向的成功经验的影响。使用普通粒子群算法时,在进化后期几乎所有粒子都在式(3-11)的引 导下快速接近全局最优粒子,使得进化停滞,导致了普通粒子群算法的搜索能力有限,比较 适用于解决简单问题。而对于目标空间较为复杂的多约束组合优化问题来说,需要采用新的 策略来提高算法的搜索能力。
受人们在解决问题时往往采用分组讨论形式的启发,本文在第四章的基础上引入多个种 群协同进化的思想,提出一种基于多种群的高维多目标粒子群优化算法M_IMaOPSO,使用 多个种群分别搜索不同的区域,可以有效提高算法的搜索性能。另外在原有算法上改进了算 法的更新机制并加入了替换算子,不断向种群中加入“精英个体”,提高算法的收敛性,使 得该算法更适用于多约束组合优化问题。
5. 1更新机制的改进
在多种群机制中,不仅每一个子群都有自己的子群最优Qbest,并且在整个种群中还应 该有一个总体全局最优,我们将其称为总体最优Gbest。按照基本粒子群中的速度更新公式 (3-1),每个子群中粒子的飞行分别受其自身飞行经验和子群最好粒子的影响,这样它们就可 以分别在不同的区域进行搜索。但单个子种群的最优解Qbest只是群内最好的,包含的信息 不够全面,为了进一步提高算法的收敛性,我们在基本的速度更新机制中加入向总体最优学 习的部分,使得子群中的粒子在各自进行搜索的同时也与总体最优进行交流,有助于算法快 速收敛到可行域。改进后的速度更新公式如下:
Vij(k + 1) = 〇)Vij(k) + ^Pbestu(k) - xu(/c)) +
(^(QbestjQk) - + c3r3QGbestj(k) - (5-1)
其中〇),Cl,的设置与第四章相同,r3是在[0,1]区间内的随机数,c3=C2,即粒子受总体 最优的影响与受子群全局最优的影响的比重相同。
5. 2替换算子
受自然界“优胜劣汰”这一自然法则的启发,我们在算法中加入一个替换算子来保存迭 代过程中外部档案里储存的优质非支配解。外部档案所存储的个体本来就是相互非支配的, 可以看作是潜在的最优解,我们利用个体与理想点之间的距离选择出离理想点更近的一部分 非支配解,这里的理想点代表理想中的最优解,离理想点越近也就意味着越接近真正的最优 解。假设有W个子种群,参与替换的非支配个体有M个,将这些非支配解平均分成W份, 用他们去代替种群中距离理想点最远的W/M个个体。
这一操作相当于将整个种群分成了两部分,第一部分是W个子种群,第二部分是用来 保留“精英个体”即存储非支配解的外部档案,由于存放在外部档案中的粒子分别来自不同 的子种群,将他们传送回第一部分相当于为子种群引入了新鲜且优质的个体。这样算法就可 以在已找到的优质非支配解周围进行搜索,即保障了种群的多样性也增加了算法搜索到最优 解的可能。保留算子的基本原理如图5-1所示。

5. 3 MJMaOPSO算法流程
基于多种群的高维多目标粒子群优化算法M_IMaOPSO的基本流程如图5-2所示:

图5-2M_IMaOPSO算法流程图
Fig.5-2 Flowchart of M IMaOPSO algorithm

5. 4参数分析
与第四章一样,本章中所提出的算法性能也受到一些重要参数的影响,除了第四章中提 到的使用《支配排序时6C值的选取,全局最优选取中拥挤距离与个体距理想点的距离所占的 比例以及扰动变异算子中的扰动系数0,子种群的数量以及替换算子中参与替换的非支配解 个数M也会对算法的寻优能力产生影响,他们关系到算法的收敛性与多样性。将不同参数 下的算法分别运行10次,每隔500代选最好的适应度值并对其求10次的平均值来观察算法 能找到的最好适应度值的走向。仍以第四章中随机生成的多背包为算例,分析这四个参数的 取值对算法求解多约束组合优化问题的影响。
(1)子种群数量W
在本文所采用的多种群粒子群算法中,子种群的数量也对算法效果有着一定的影响,从 图5-3(a)、5-3 (b)可以看出当W=2时,算法的收敛速度最慢。这是因为如果子种群数量过少, 则分配去子种群参与替换的精英粒子很有可能来自该种群,会影响算法的多样性,从而使得 算法容易陷入局部最优。而当W=5时,算法的寻优效果虽然比W=2时好,但比起W=3和 W=4还是较差,因为子种群数量过多会导致每个子种群所包含的粒子太少,使得它们对自 己所负责搜索的目标空间搜索不够全面。因此,本文取W=4对算例进行求解。

⑻基于改进模糊支配的M_IMaOPSO (a) M IMaOPSO with the improved fuzzy dominance


x1(T


1.026
f /
4/ -
V! -
/
/
i i i i i
0 2000 4000 6000 8000 10000 12000
迭代次数
(b)基于a支配的M IMaOPSO
(b) M IMaOPSO with a dominance
图5-3不同子种群数量下的适应度值对比
Fig.5-3 Comparison of fitness values in different population quantity
(2)参与替换的非支配解个数
为了验证本文所提出的替换算子的有效性,以及参与替换的非支配解个数M对算法性 能的影响,分别将没有加入替换算子和加入了替换算子但M值不同的算法的运行结果进行 比较。从图5-4(a)、5-4(b)中可以明显地看出,有替换算子加入的算法其收敛速度明显高于 无替换算子的算法,这是因为没有引入“精英个体”,无替换算子的算法仅仅依靠粒子的飞 行搜索潜在最优解,种群的多样性较差,算法容易陷入局部最优。当M=20时,算法的收敛 性相较于无替换算子的算法有了明显的提升,但因为M值较小,用来替换种群中离理想点 较远粒子的“精英个体”数量还不足以保证种群的多样性,当M=40时,算法的收敛速度和 持续寻优能力就有了明显的改善。而当M=60时,由于参与替换的“精英个体”数量过多, 会增加“精英个体”与种群中原本存在的粒子重复的概率,依然会使得种群的多样性变差。 因此,本文取M=40进行算例实验。
(a)基于改进模糊支配的M_IMaOPSO
(a) M IMaOPSO with the improved fuzzy dominance
(b)基于a支配的M IMaOPSO
(b) M IMaOPSO with a dominance
图5-4不同M下的适应度值对比
Fig.5-4 Comparison of fitness values in different M

a支配排序中的a值代表每一个目标值与其余目标值的折衷比例。如果a过大,会导致 算法的多样性变差,而a值过小又会导致算法的收敛性变差。因此,本文在[0.1,0.5]区间内 每隔0.1选取一个参数,分析a在取多大值时算法的寻优效果最佳。
从图5-5中可以看出,当a=0.1时,适应度值曲线的上升高度最低,意味着算法的寻优 效果不佳。当a=0.3时,适应度值曲线的上升高度最大即算法的收敛速度最快,且当别的取 值下适应度值曲线几乎不再变化时该取值下的曲线依旧有上升趋势。随着a值增大至0.4、 0.5,算法的寻优能力逐渐下降,也就是说a=0.3时算法的持续寻优效果最好,因此a应取在 [0.3,0.35]之间较为合适。
(4)全局最优选择参数
从图5-6(a)、5-6(b)中可以看出,当proportion=l时,表示Gbest完全根据拥挤距离选取, 这时算法的收敛速度很慢,proportion递减至0.8、0.5后,算法的收敛速度逐渐增加。而当 proportion=0时,意味着Gbest仅依靠个体与理想点之间的距离来选取,此时算法的收敛性 虽好于proportion=l、0.8、0.5的时候,但不及proportion=0.3的时候。实验结果表明,proportion 在[0.2,0.3]区间内选择可以使算法的效果达到最优。

(a)改进模糊支配下proportion对适应度值的影响 (a) The influence of proportion with the improved fuzzy dominance on fitness value
0 2000 4000 6000 8000 10000 12000
迭代次数
(b) a支配下proportion对适应度值的影响
(b) The influence of proportion with a dominance on fitness value
图5-6不同proportion取值下的适应度值对比
Fig.5-6 Comparison of fitness values in different proportion
(5)扰动系数0
扰动系数0表示粒子加速飞行的倍数,选择合适的扰动系数可以帮助算法跳出局部最优, 扩大粒子的搜索空间,提高能找到的最优解的质量。本文在[1.5,3.5]区间内每隔0.5选取一个 参数,分析0在取多少时可以使算法性能最优。
从图5-7(a)和5-7(b)中可以看出加入扰动变异算子后,算法的收敛速度有了明显的提升。 0=1.5时算法的收敛速度较慢,寻优能力差,这表明粒子速度增加的幅度较小,能搜索到的 目标空间范围较小,跳出局部最优的能力也较弱。而当0=3时算法的收敛速度最快且能够找 到的最优解比0=1.5, 0=2, 0=2.5以及0=3.5时算法找到的最优解都好,也就是说扰动系数0过 大也会对算法性能造成不利的影响,因为粒子飞行的速度过快,有可能错过很多潜在最优解。 因此,0应取3较为合适。
…,x104
(a)改进模糊支配下0值对适应度值的影响
(a) The influence of 6 with the improved fuzzy dominance on fitness value

1.015  1 1 1 1 1 1
0 2000 4000 6000 8000 10000 12000
迭代次数
(b) a支配下0值对适应度值的影响
(b) The influence of 6 with a dominance on fitness value
图5-7不同0取值下的适应度值对比
Fig.5-7 Comparison of fitness values in different 0
5. 5算例实验
为了验证算法的有效性,以MKP算例进行验证。子群数量W=4,参与替换的非支配解 个数M=40,其余参数与第四章设置完全相同。
对每一个算例,我们用其在10次独立运行下的平均值作对比,表5-1和表5-2分别为5 个背包和50个背包在物品数为200、500、1000时的实验结果,其中最好的解用黑色加粗字 体标出表示算法在求解过程中得到的全部是非可行解。


0001 400^ 400^=w J〇 ;u9uiu9dxa i-g-qq^x
00〇r〇0^4〇0^=u^=m 1-9 ^
^#osd〇^i


从表5-1和表5-2中可以看出,对于5背包和50背包的所有算例,除m=5,^=200,R=100 时的非相似数据外,经过改进的M_IMaOPSO算法对其求解的效果较之前的IMaOPSO算法 都有不同程度的提升,尤其对于第四章中使用IMaOPSO算法求解效果不佳的几组数据,使 用M_IMaOPSO算法对他们进行求解,效果明显好于其他所有算法。实验结果表明,无论 是小规模还是大规模MKP,无论是相似背包算例还是非相似背包算例,本文算法均优于其 它算法。
为了进一步验证M_IMaOPSO算法的寻优能力,我们将其与IMaOPSO算法在10次运 行中所找到的最优值对比,最好的解仍旧用黑色加粗字体标出。对比结果如表5-3和5-4所
7K。从表5-3、5-4中我们可以明显看出,除了非相似数据中m=5,w=200,R=100、 m=5,n=200,R=10000 以及相似数据中 m=5,=200,R=10000、m=50,=200,R=100 这 4 组数据外, 在对其余32组数据的求解中,M_IMaOPSO算法所找到的最优解明显好于IMaOPSO算法。 且由表5-1、5-2可知,对于最优解不如IMaOPSO算法的四组数据,M_IMaOPSO算法10
次求得的最优解平均值均好于或等于IMaOPSO算法,充分说明了 M_IMaOPSO算法的寻优 能力不仅好而且稳定。
表 5-3 m=5,=200,500,1000 的最优解 Table.5-3 The best value of m=5 and n=200, 500, 1000





图5-8展示了对于随机生成的大规模MKP算例,本文所提出的M_IMaOPSO算法与基 于约束转双目标的IMOPSO算法最终得到的解集的对比,显然,该算法不仅获得可行解的数 量多于IMOPSO,且得到的可行解更优。


图5-8 M_IMOPSO算法与M_IMaOPSO算法得到的解集对比
Fig.5-8 Comparison of solution sets obtained by M IMOPSO and M IMaOPSO
为了能够直观地表现出IMaOPSO算法的性能,我们同样选用基于改进模糊支配的算法

来观察其迭代过程中的收敛情况,验证算法的收敛性。
图5-9展示了对于随机生成的MKP算例,M_IMaOPSO算法的收敛情况。分别选取了 迭代次数为2000、4000、6000、8000、10000代时的Pareto前沿。可以明显的看出从运行初 期的2000代到运行结束的10000代,随着代数的增加,目标空间中的解在不断向空间下方 靠近,即背包价值总和则越来越大。红色代表算法最终找到的前沿面,其中位于y轴 最下方且违反约束度为0的解即为我们所要找的最优解。
4.85
\JL
4.65 4.6 4.55 4.5
0 500 1000 1500 2000 2500 3000 3500 4000
H(X)
图5-9 M_IMaOPSO算法收敛情况
Fig.5-9 The convergence of M IMaOPSO
5. 6本章小结
由于在第四章中我们采用了粒子位置在一定概率下直接向全局最优Gbest跳变的交换粒 子群方法,使得在迭代过程中粒子快速的向Gbest所在位置聚拢,但这一方法使得种群容易 陷入局部最优,导致了 IMaOPSO算法在大规模MKP的求解上能力不足。因此,在本章我 们釆用多种群的机制配合替换算子来增加种群的多样性,并对粒子的速度更新公式做出了改 进,使各子群在独立进行搜索的同时也和所有种群中的最优粒子相互通信,保证了算法可以 快速收敛到最优解。实验结果证明,该算法是有效的。



6总结与展望
6.1总结
多约束组合优化问题广泛存在于现实生活以及工程应用中,随着问题规模的增大,精确 算法己经无法实现对这类问题的求解。使用传统的启发式算法求解时,多个约束的存在又会 使优化过程中产生大量的不可行解,从而导致算法命中最优解的概率大大降低。因此针对多 约束组合优化问题,研究一种既能有效处理约束条件又能在保证算法可靠性的基础上得到高 质量最优解的优化策略对于解决复杂工程优化问题具有重要意义。本文通过将多个约束分别 转化为多个目标,将多约束组合优化问题转化为高维多目标优化问题,结合改进的多目标粒 子群算法对其进行求解,并以多背包问题为算例,验证了算法的有效性。本文的主要研究如 下:
(1)一般的多目标优化方法都是米用网格法或是拥挤距尚来选取种群的Gbest,他们大多 关心的是Gbest作为种群的“领导者”,如果在目标空间中所处的位置太拥挤会影响算法的 多样性。而对于多约束组合优化问题,我们的最终目的是要求得一个满足所有约束条件的最 优解,也就是说我们对算法收敛性的要求更高。因此,本文采用拥挤密度和个体与理想点之 间的距离作为双重标准对Gbest进行选取,在保证算法多样性的同时提高其收敛性。
(2)由于转化为多目标形式后的组合优化问题要在违反约束度很小的区域内进行求解, 釆用拥挤密度维护外部档案可能会造成非支配解集远离可行域,并且在组合优化问题的求解 中我们并不关心非支配解集是否在目标空间中均匀分布。因此,结合(1)中的Gbest选取方法, 本文提出了一种适用于多约束组合优化问题的改进高维多目标粒子群算法IMaOPSO,采用 违反约束度维护外部档案。并且在种群进化的过程中加入一定的扰动,扩大算法的搜索范围, 有助于算法跳出局部最优。
(3)由于多约束组合优化问题目标空间十分复杂,而普通粒子群算法的搜索能力有限, 因此本文考虑在IMaOPSO算法的基础上,采用多种群协同进化的机制,利用多个种群分别 搜索不同的区域。并对普通粒子群算法的速度更新机制做出改进,使得粒子在运动的过程中 不仅受自身所在子种群中最好粒子的影响,同时也受所有子种群中最好粒子的影响。此外, 在进化过程中不断向子种群中加入新鲜的“精英个体”,使得各个子群之间可以相互通信, 以增强算法的寻优能力。实验结果证明,本文所提算法在解决各种规模的多约束组合优化问 题方面表现优秀。
6.2展望
本文通过将每一个约束转化为一个目标的方法,将多约束优化问题转化高维多目标优化 问题进行求解。对如何将高维多目标优化算法与粒子群算法的结合应用于求解多约束组合优 化问题进行了研究。虽然取得了一定的进展,但仍有很多地方有待进一步的探索与研究。主 要是由于Pareto排序方式对高维多目标优化问题无效,因此我们需要采用新的排序方式结合 所提算法对问题进行求解。而不同的支配排序方式又会影响算法的求解效果,那么如果可以 针对组合优化问题的特点设计一种支配排序方式,将其与本文提出的算法相结合,也许能使 多约束组合优化问题的求解达到更好的效果,这一问题还需要我们进行更深入的研究。