多目标混合优化论文-盘古文库

多目标混合优化论文

来源：火烈鸟

作者：开心麻花

2025-09-18

多目标混合优化论文（精选12篇）

多目标混合优化论文第1篇

多目标优化问题MOP (multiobjective optimization problem) 是指需要同时优化两个或多个互相冲突目标的优化问题[1]。MOP往往不存在一个解使得所有目标同时取得最优, 只能找出一组解使得目标函数尽可能达到Pareto前端[2], 因此, 寻找能够通过一次计算就可以得到均匀分布在Pareto前端最优解集的多目标优化算法是学者们研究的热点之一[3]。

传统的多目标优化算法将多目标优化问题通过加权方式转化为单目标问题, 在每次求解过程中, 只能得到一个解, 算法效率较低, 而且对权重值和目标给定次序比较敏感[4]。智能优化算法通过种群代与代之间维持潜在解组成的集合实现多目标优化, 近十几年来, 相继提出了不同的多目标优化算法, 如早期的矢量评价遗传算法 (VEGA) 、非劣排序遗传算法 (NSGA) , 随后出现的基于精英保留机制的PAES、SPEA2及经典的NSGA-Ⅱ[5]等算法。将新的机制和策略引入多目标优化算法并对其改进是当前多目标优化的前沿领域, 文献[6]利用多目标优化问题PS分布规则, 提出了一种分布多目标优化问题估计算法RM-MEDA;文献[7]针对多目标粒子群算法 (MOPSO) [8]在优化Pareto前段分段不连续函数时存在收敛效率低、多样性差的缺陷, 提出了一种基于杂草克隆的多目标粒子群算法;文献[9]通过引入克隆选择机制, 提出了一种基于非支配邻域的改进多目标优化算法NNIA-Ⅱ, 实验结果证明了NNIA-Ⅱ具有优秀的求解性能。

混合蛙跳算法SFLA[10]是一种新型的群智能启发式计算技术, 由于SFLA具有实现容易, 收敛速度快等特点, 被广泛使用[11,12], 然而将SFLA应用于多目标优化问题的研究很少。SF-LA较强的寻优能力使其能够快速接近理论Pareto最优解, 但是, 对于多目标优化问题, SFLA存在易于陷入局部最优及需要根据Pareto支配进行多目标函数适应度赋值等问题, 针对这些问题, 本文提出了一种自适应混沌混合蛙跳算法求解多目标优化问题MACSFLA (Adaptive Chaos Shuffled Frog Leaping Algorithm for multiobjective optimization) , 并做了如下改进:

1) 针对SFLA容易陷入局部极值的问题, 使用动态权重因子策略以增强算法跳出局部最优能力和提高算法收敛效率;

2) 引入基于Pareto支配能力的SFLA子族群划分策略, 使得SFLA能够应用于多目标优化问题;

3) 为提高MACSFLA算法的收敛效率, 采用自适应网格密度机制动态维护外部存储器Pareto最优解规模, 并使用自适应混沌优化技术改善Pareto最优解集样本多样性;

4) 利用Pareto最优解选择策略为青蛙种群选择最优更新粒子。

通过对多目标函数实验测试, 结果表明, 与MOPSO和NS-GA-Ⅱ相比, MACSFLA在Pareto最优解集均匀性和多样性上有明显优势。

1多目标优化问题和混合蛙跳算法

1.1多目标优化问题数学描述和基本概念

多目标优化是对多个目标函数同时进行优化, 是优化问题主要的研究领域之一, 不失一般性, 一个决策变量维数为n, 目标变量数目为m的多目标优化问题可以表述为:

其中, x= (x1, x2, …, xn) 为n维决策变量, y= (y1, y2, …, ym) 为目标函数, gi (x) 、hi (x) 分别为不等式约束和等式约束。

定义1 Pareto支配

设有f:Rn→Rm, 对于给定决策变量x1和x2 (x1, x2∈Rn) , 则称与x2相比, x1支配x2, 当且仅当:

定义2 Pareto最优解与Pareto最优解集

决策变量x*称为Pareto最优解, 当且仅当满足条件:

所有Pareto最优解的集合就是Pareto最优解集, 并记为:

定义3 Pareto前端

Pareto最优解集P*中的解对应的y= (y1, y2, …, ym) 组成的集合成为Pareto前端, 并记为:

1.2混合蛙跳算法 (SFLA)

基本SFLA工作原理可以描述为:青蛙种群F包含N只青蛙, 每只青蛙代表n维优化问题的一个解, 设第i只青蛙的位置为Xi={xi1, xi2, …, xin}。青蛙种群将青蛙按照适应度值[13]f (Xk) 降序排列, 并平均分配到M个子族群El (1≤l≤M) 中, 子族群青蛙数为Q, 其中, El按照式 (6) 进行划分。

SFLA对子族群El中适应度最差的个体Xl, w进行更新:

其中, r∈ (0, 1) 为随机数, Xl, b为El适应度最好的个体。如果f[Xl, w (t+1) ]优于f[Xl, w (t) ], 则用新个体替代原个体, 否则用种群内适应度最好的解Xg代替Xl, b重新执行更新策略式 (7) , 如果仍不能优于原个体, 则随机生成青蛙取代原个体。所有子族群执行一定次数的局部迭代搜索后, 青蛙种群重新混合, 然后划分新的子族群, 并重新进行局部搜索, 算法如此往复, 直到满足终止条件。

研究表明, SFLA存在易于陷入局部极值的缺陷, 特别是在算法迭代后期, 当某个青蛙十分接近局部极值时, 算法需要迭代多次才有可能跳出。为了避免SFLA早熟, 对算法更新策略进行改进, 引入动态权重因子策略:

其中, ξ1、ξ2、c1为比例系数, rmin、rmax为权重因子最小值与最大值, Tmax为算法最大迭代次数。从式 (8) 和式 (9) 可以看出, 动态权重因子策略实质为在非线性指数函数递减权重因子的基础上增加了随机扰动, 采用该权重因子策略使得算法在运算初期, r'取值较大, 青蛙能在比较大的空间进行搜索;算法运算后期, 随机扰动让算法能够进一步深度搜索, 提高了算法收敛精度。

对于多目标优化问题, SFLA无法直接根据适应度值进行子族群划分, 因此, 本文提出基于Pareto支配能力的SFLA子族群划分策略:青蛙种群完成一次迭代后, 将所有青蛙进行Pareto支配关系比较, 对于青蛙Xi, 由其支配的青蛙组成的集合为Zi, 即:

设|Zi|为Zi内青蛙个数, 种群根据|Zi|将青蛙降序排序, 如果两只青蛙具有相同的|Zi|, 则随机进行排列。当所有青蛙完成排序后, 根据式 (6) 进行子族群划分。在子族群El内, 对具有最小|Zi|的青蛙按照式 (7) 进行更新, 如果子族群多只青蛙具有相同的|Zi|, 则随机选择一个个体进行更新。如果更新后的个体支配原个体, 则用新个体替代原个体, 否则随机产生新的个体进行替代。

2自适应混沌混合蛙跳算法

2.1自适应网格密度机制

本文将Pareto最优解存储器记为Archive集, MACSFLA每次进化会产生新的Pareto最优解粒子, 称这些粒子为Archive集候选解, 当候选解满足如下条件之一时就可以进入Archive集。

1.Archive集为空集。

2.Archive集为非空集, 且候选解不受Archive集中任一个粒子支配。

3.候选解支配Archive集所有粒子。

4.候选解不受Archive集中至少一个粒子支配, 且候选解所在网格的密度值比该非支配解所在网格的要小。

随着算法迭代不断增加, Archive集规模不断增加, 其计算复杂度为O (t·m·N2) , 如果不控制Archive集规模, 将很大程度地增加计算复杂度, 因此, 本文规定Archive集规模为N, 并采用自适应网格密度机制动态维护Archive集规模。自适应网格密度机制工作原理可以描述为:

Step1 自适应网格划分。将m维目标空间划分为K1×K2×…×Km相同的网格, 网格i维宽度di为:

Step2 Archive集粒子网格定位。设第t代Archive集集合为At={a1, …, aj, …, ah} (h≤N) , 对于aj, 其第i维网格编号wij为:

由式 (13) 可以确定aj在目标空间内的位置aj (w1j, …, wmj) 。

Step3 Archive集网格粒子密度计算。设网格Gk的粒子密度为Dk, 并定义Dk为网格内Pareto最优解的个数, 如果网格内没有粒子, 其Dk为0。

Step4 Archive集粒子淘汰。当候选解加入Archive集后, 可能会使得Archive集规模大于N, 因此需要进行Archive集粒子淘汰:对于网格Gk, 如果其Dk>1, 则根据式 (14) 对其中粒子进行删除。

其中, Gd为网格Gk需要删除的粒子数, 为Archive集加入候选解后的规模。确定Gd后, 根据式 (15) 计算Gk中粒子与理论Pareto前端距离, 并依次删除远离Pareto前端的粒子。

其中, DGk, i为Gk内粒子i与理论Pareto前端最短距离。

2.2自适应混沌优化技术

Archive集中的个体决定了青蛙种群的进化方向, 自适应网格密度机制在一定程度上保证了Archive集中粒子的均匀分布, 但是, 如果某些理论Pareto最优解没有存储在Archive集中, 那么之后会很难再找到该Pareto最优解[4]。为了改善Archive集样本多样性, 引入自适应混沌优化技术, 其思路可以描述为:随机选择Archive集部分粒子进行混沌优化 (限于篇幅, 混沌优化过程不再赘述) , 设粒子i在混沌优化第k-1代、k代和k+1代的位置分别为Ck-1, i、Ck, i和Ck+1, i, Pk-1, i、Pk, i和Pk+1, i分别为Ck-1, i、Ck, i和Ck+1, i的Pareto前端, 则第k-1代、k代和k+1代之间Pareto前端距离Dk, k-1、Dk, k+1分别为:

定义混沌迭代控制系数diffD为Dk, k-1、Dk, k+1的差值, 即:

当diffD>0表示算法处于进化状态, 可以减少混沌优化迭代次数, 以提高算法速度, 当diffD<0表示算法进化能力降低, 需要增加混沌优化迭代次数, 以提高算法精度, 混沌优化迭代次数KCmax自适应策略为:

自适应混沌优化技术在每次混沌优化后, 自适应调整KCmax, 直到新解优于原解或达到设定的最大迭代次数为止。

2.3 Pareto最优解选择策略

MACSFLA根据网格粒子密度值, 在Archive集中为每只青蛙选择一个Pareto最优解进行更新。对于网格Gk, 如果Dk>0, 则其网格适应度值f (Gk) 可以定义为Dk的倒数, 即:

MACSFLA根据网格f (Gk) , 采用轮盘赌的方式为每只青蛙选择一个网格, 并从网格中随机选择一个个体作为最优解进行更新。该Pareto最优解选择策略使得Archive集中Dk越小的网格被选择的概率越大, 确保了Pareto最优解多样性。

2.4自适应混沌混合蛙跳算法实现流程

MACSFLA算法流程可以描述为:

3性能验证

3.1评价指标和测试函数

本文采用文献[14]中的世代距离指标GD和多样性指标Δ进行算法性能评价, 并分别采用文献[1]和文献[4]中的KUR、ZDT1、ZDT2、ZDT3和ZDT6多目标函数进行实验仿真, 其中, KUR函数的n=3, 决策变量取值范围为 (-5, 5) , 其他4个函数的n=30, 决策变量取值范围为[0, 1]。

MACSFLA参数设置如下:N=200, Q=20, Kmax=10, Tmax=500, ξ1=0.2, ξ2=0.8, c1=3, rmin=0.35, rmax=0.95。

3.2实验结果及其分析

分别采用MACSFLA算法、NSGA-Ⅱ算法和MOPSO算法对测试函数进行实验, 每种算法独立测试30次, 表1给出了世代距离指标GD对比结果, 表2给出了多样性指标Δ对比结果 (分别取最大值M和平均值AV) , 图1给出了通过MACSFLA优化后测试函数Pareto前端和理论Pareto前端仿真图。

从表1, 表2和图1可以看出, MACSFLA能够有效地获得Pareto前端, MACSFLA得到的Pareto前端更加均匀, 世代距离指标GD和多样性指标Δ要优于其他两种算法, 而且对于Pareto前端两端端点的逼近程度很高, 特别是对于不连续多目标函数ZDT3, MACSFLA得到的Pareto前端粒子均匀分布在理论Pareto前端上。

5结语

提出了一种新的基于自适应混沌混合蛙跳算法的多目标函数优化算法。对混合蛙跳算法权重因子进行了改进, 设计了基于Pareto支配能力的SFLA子族群划分策略, 提出了自适应网格密度机制动和自适应混沌优化技术, 最终实现了多目标优化问题求解。仿真结果表明, 与MOPSO和NSGA-Ⅱ相比, MACSF-LA在Pareto最优解集均匀性和多样性上有明显优势。

摘要：针对多目标优化问题提出一种自适应混沌混合蛙跳算法MACSFLA (Adaptive chaos shuffled frog leaping algorithm for multiobjective optimization) 。使用动态权重因子策略以提高混合蛙跳算法SFLA (Shuffled Frog Leaping Algorithm) 收敛效率, 引入基于Pareto支配能力的SFLA子族群划分策略, 使得SFLA能够应用于多目标优化问题。在此基础上, MACSFLA首先利用SFLA快速寻优能力接近理论Pareto最优解, 然后采用自适应网格密度机制动态维护外部存储器Pareto最优解规模, 并使用自适应混沌优化技术改善Pareto最优解集样本多样性, 最后利用Pareto最优解选择策略为青蛙种群选择最优更新粒子。多目标函数测试实验结果表明, 与MOPSO和NSGA-Ⅱ相比, MACSFLA在Pareto最优解集均匀性和多样性上有明显优势。

多目标混合优化论文第2篇

Pareto基因算法多目标翼型优化设计

基于Pareto 最优解的定义,通过构造新型的联赛式选择复制等算子而发展了一种适合于求解多目标优化设计的Pareto基因算法.通过等级法来正确识别每一代中近Pareto波阵面的解,从而消除选择误差达到快速收敛的目的.为提高解的`分布性:采用小生境技术解决了基因材料多样性损失问题;采用常规实数编码方式配合平均交叉算子解决了编码端点效应问题.将所发展的方法应用于多目标翼型优化设计中,获得了理想的Pareto波阵面,为决策者提供了一个可选的有效解数据库.

作者：隋洪涛陈红全黄明恪作者单位：南京航空航天大学,601教研室,江苏,南京,210016刊名：航空学报 ISTIC EI PKU英文刊名：ACTA AERONAUTICA ET ASTRONAUTICA SINICA年，卷(期)：23(2)分类号：V224关键词：基因算法 Pareto最优解多目标优化设计翼型

盾构刀盘多目标优化设计第3篇

关键词：盾构刀盘；优化设计

盾构机是一种地下隧道挖掘专用的大型、成套施工设备，其主要优点有质优、安全、经济效益高、开挖快、有利环境保护、降低劳动强度等，在城市施工、隧道挖掘中得到广泛应用。盾构机在施工过程中可能遇到各种不同的地质环境，从粘土、与你、砂层到软岩、硬岩等。在盾构机使用过程中，其关键部位就是盾构刀盘。盾構刀盘质量好坏直接关系到盾构机的工作效率、使用寿命和工程的成败。因此，盾构刀盘的设计和地质工程有着紧密的关系，不同的地质类型要选择不同的刀盘结构，进而盾构刀盘的设计也应该采取多目标优化设计，提高盾构机的工作效率。

1.盾构机刀盘结构形式

盾构刀盘主要具备稳定掌子面、搅拌渣土、挖掘三大功能。观察刀盘的结构，主要由辐条式和面板是两种，具体使用哪一种应该根据现场的施工条件和地质条件决定。泥水盾构主要使用面板是刀盘，如果是土压平衡盾构则考虑采用辐条式或者面板式，当然，辐条式刀盘明显优于面板式。对于土压平衡盾构来说，使用面板式的盾构刀盘时，当泥土流经刀盘面板的时候，泥土可能进入土仓开口，进而导致盾构机挖掘的过程中舱内土压和挖掘面土压之间产生压力，导致挖掘面不易控制。而辐条式的刀盘结构辐条较少，切削下来的土体可能直接进入到设备土仓当中，没有压力损失，而且在辐条后面设有搅拌的叶片，在搅拌砂土过程中可以流畅工作。所以，辐条式的刀盘比面板式刀盘的适应性强。但是辐条式的刀盘不能安装滚刀，这也是其缺陷之一，在风化后的岩石或者软硬质地不均的地方使用，还是应该选择面板式刀盘。

2.盾构刀盘结构设计

2.1开口率设计

盾构刀盘的开口率是面板式刀盘开口部分的面积和刀盘面积的比率，其实质上指的是刀盘切削下来的碎土要经过刀盘开口槽进入土仓。因此，在进行刀盘开口设计的时候，必须要考虑到盾构机使用的土壤环境、开挖面的稳定性、开挖效率，并以此作为根据选择尺寸、形状及其他条件相符的刀盘。例如对水泥盾构的时候，盾构刀盘的开口率一般设计在10%-30%之间；对土压平衡盾构的刀盘设计，开口率较小；对于粘性土质盾构来说，刀盘的开口率应该加大；对于较容易坍塌的地质结构进行盾构的时候，刀盘的开口率必须慎重选择。此外，盾构刀盘的开口位置要紧靠刀盘的中心，避免工作室切削下来的渣土掉落在中心部位，造成运行不畅。

2.2泡沫管的设计

实施土压平衡盾构主要使用于土质相对粘稠的施工地点，如果施工地点的含沙量超过限度，泥土的可塑性降低，而且土仓内的土会因为凝固而被压得紧密，仓内的土渣就无法排除。此时，可以采用向土仓内注泡沫或水、膨润土的方法进行强制性搅拌，让沙质土软化。使用泡沫可以有效控制土体塑流性，还可以润滑盾构刀盘、刀具、螺旋输送机等，保持盾构机的流畅运行，提高其性能和作用。所以，泡沫管可以有效防止刀盘运转过程中，泥土形成泥饼，通常情况下，泡沫管注入口设置在刀盘的中心部位或者刀盘的背面，通过旋转接头将泡沫引入，刀盘上布置的泡沫管有两种，一种是外置式，一种是内置式，外置式清理相对容易，但是与土壤直接摩擦，比较容易损坏，内置式清理比较麻烦，但是不宜损坏，目前盾构机多使用的是内置式。从盾构刀盘多目标设计的角度来说，做好泡沫管布置同样具有重要作用。

2.3刀盘倒角和变滚刀设计

盾构机刀盘的切削直径最终是由安装在刀盘外周的刀具实现的。所以，在盾构机进入土层的时候，其运行时通过周边的刮刀实现的。在土质坚硬或者岩石地质进行盾构的时候，主要由边滚刀实现，在土质较软的区域进行盾构的时候，主要由周边的刮刀实现。边滚刀的径向和刀盘的面板必须形成一定的角度，刀盘的形状在边缘处要流出一定的倾斜角。刀盘在运转的过程中，滚刀靠近刀盘的边缘，其旋转速度要比中心部位滚到旋转速度快，而且切削岩层的直线距离很长。所以，边滚刀的磨损要远远大于中心滚刀，因此在进行设计的时候，要增加边滚刀数量。

3.刀盘多目标的优化设计

刀盘设计之前，要预先建立相应的数学模型，将选取钢材的厚度作为设计中的主要变量，选择刀盘最大变形和质量作为函数，进行整体优化，其目标就是使刀盘最大变形量和质量实现最小。当然，进行多目标优化分析的时候，目标函数的级别会影响到设计方案的优化，并以此来确定最佳的设计方案。最优的设计方案选择原则在尽量满足优化目标的前提下进行，优化效果最明显的方案就是盾构刀盘需要选择的方案。

盾构刀盘优化设计流程，先将盾构机刀盘模型参数化，并按照典型的工况条件对刀盘进行静力分析，并将静力分析的结果和设计参数作为边界条件，对参数化的模型进行不断优化直至求出最佳解，将优化结果返回模型，变更并确定最终设计方案。通过这个方式进行盾构机刀盘校核，即使失败也可以通过改变设计参数改变刀盘模型的结构尺寸，减少重复建模的工作量。

4.总结

盾构刀盘进行设计的时候，要考虑到刀盘的使用范围和现实的土质情况，全面考虑各种问题之后，全面优化盾构刀盘优化设计。进行设计的时候可以根据相关参数选择获取设计方案，提高设计分析思路，为盾构刀盘设计提供新的方法和思路。

参考文献：

[1]黄德中.超大直径土压平衡盾构施工土体改良试验研究[J].现代隧道技术.2011（04）

[2]蒲毅，刘建琴，郭伟，裴瑞英.土压平衡盾构机刀盘刀具布置方法研究[J].机械工程学报. 2011（15）

[3]王锡军.无水砂卵石地层盾构施工[J].建筑技术.2011（03）

[4]李建峰，王旭，王凯，周喜.盾构刀盘中心区域磨损研究[J].现代隧道技术.2011（01）

[5]何峰，李小岗，孙善辉.北京铁路地下直径线泥水盾构刀盘、刀具适应性分析[J].中国工程科学. 2010（12）

多目标混合优化论文第4篇

柔性作业车间调度问题 (flexible job-shop scheduling problem, FJSP) 广泛存在于机械加工系统中, 它是传统作业车间调度问题 (job-shop scheduling problem, JSP) 的扩展, 更贴近于制造企业实际车间的生产环境。在FJSP中, 一台机器可以加工同一工件的不同工序, 同一个工序也可以在不同的几台机器上加工[1]。由于工件和工序没有资源的唯一性要求, FJSP是比JSP更复杂的NP-hard问题。

在传统作业车间调度问题中, 车间设备的役龄被看作是无穷大, 设备不存在故障, 被看作一直可用。但是在实际情况中, 随着时间的累积, 设备役龄的增加, 设备不可避免地要出现故障, 并且设备运行时间越长, 故障的频率会越高, 甚至会发生设备整体的损坏以至于无法运行的情况。设备的重大故障会导致整个车间生产停滞, 会对企业产品的交货期产生重大影响, 并给企业造成不必要的损失。所以在进行调度的时候, 必须将设备维护的环节考虑进去。

设备的预防性维修 (preventive maintenance, PM) 是根据设备故障的统计规律制定出长远的维修计划, 以期从总体上控制维修成本, 提高设备可靠性。若维修不当, 设备可能出现可靠性下降的情况, 进而导致成本损失[2]。相对于故障后维护, 预防性维护更加合理有效, 可以很大程度上减轻将来可能的故障对整个系统的影响。合理的预防性维修是提高设备利用率, 实现资产效率最大化的有效途径。因此, 在制定调度计划的同时, 根据车间内机器设备的正常损耗和役龄的情况, 把设备的合理维护考虑在车间调度之中具有重要理论意义和实际应用价值。

为了合理解决生产调度和设备维护之间的矛盾冲突, 许多学者对设备维护和生产调度的集成优化问题进行了研究。Moradi等[3]以最小化最大完工时间和降低系统不可用率为优化目标, 将预防性维护安排在柔性作业车间调度中固定的时间段;Li等[4]以最小化最大完工时间、机器总负荷和瓶颈机器总负荷为目标, 运用化学反应算法解决整合柔性作业车间调度和预防维护的问题;Fitouhi等[5]采用了基于运行的预防性维护, 这种维护方法去除了周期性的约束, 降低了更多的生产和维护成本;Lu等[6]将批量生产问题和基于运行的预防性维护结合起来, 并考虑了设备的可靠度约束。

有效的预防性维修和生产调度计划集成必须同时考虑到提高生产效率和降低维修成本。在前人研究的基础之上, 本文在研究集成优化问题时不仅考虑了柔性作业车间生产时机器可靠度的动态约束, 而且兼顾了设备维护的成本。

殖民竞争算法 (imperialist competitive algorithm, ICA) 是Atashpaz等[7]在2007年通过模拟人类社会殖民竞争过程提出的一种新颖的基于群体的元启发式算法, 实验结果显示该算法比遗传算法和粒子群优化算法具有更高的优化效率和鲁棒性, 近年来得到了越来越广泛的应用[8,9]。本文依据实际生产环境, 建立了预防性维修和生产调度集成模型, 以最小化最大完工时间、总生产成本和平均总维修成本为优化目标, 在每一台机器的维修时间段内合理安排设备维护, 设计一种新颖的多目标混合殖民竞争算法求解该问题。

1 设备维护综述

之前的文献显示, 设备的故障一般服从指数分布, 实际应用中, 倾向于采用二参数威布尔分布来描述一般设备的故障规律[2]。服从威布尔分布的设备故障率函数公式为

其中, m>0, η>0。m、η均为与机器设备自身有关的参数, 可以通过对不同设备故障情况的历史数据分析得到, 与时间无关。m是形状参数, 不改变分布函数的形状, 只表示函数曲线在时间坐标轴上的平行移动。形状参数m是三个参数中最重要的一个参数, 不同的m值可以决定不同的曲线形状。η是尺度参数, 只影响曲线横轴和纵轴尺度的放大和缩小, 并不影响曲线的基本形状。

根据文献[6], 设备在运行时刻t的可靠度Rt的计算公式为

式中, Zt为设备的役龄。

假设某台设备的最低可靠度阈值为R′, 则根据式 (2) , 该设备的可靠度达到阈值时的役龄Z′为

在调度的过程中, 任何时刻该设备的役龄Zt均要小于Z′。

在研究设备维护的过程中, 假设经过预防性维护, 设备能恢复到最初的状态或设备的可靠度不会有所增加都是不切实际的, 所以根据文献[10]的研究, 可以运用一种比例的方法来恰当地表示, 即役龄回退因子p (i) , 假设经过预防性维护前, 某设备的实际役龄是Zi, 则第i次预防性维护以后, 设备的实际役龄变为 (1-p (i) ) Zi。经过预防性维护, 设备的累积役龄随时间变化的曲线如图1所示, PM为预防性维修。

制定生产计划时所有设备都需要在可靠度降低到阈值之前进行预防性维护, 两次维护之间的间隔时间以及每台设备的维护总次数则要根据各个设备之前的故障状态数据 (包括维修前役龄、役龄回退因子、维修后工作时间等) 来决定。

2 设备维护与调度集成模型

2.1 问题描述

柔性作业车间调度问题可描述如下:若干个工件在m台机器上加工, 每个工件分为k道工序, 每道工序可以在若干台机器上加工, 并且必须按一些可行的工艺次序进行加工;每台机器可以加工工件的若干工序, 并且在不同的机器上加工的工序集可以不同。此外, 在加工过程中还需满足以下约束条件: (1) 每台机床一次只能加工一个工件; (2) 工序一旦进行不能中断; (3) 假定工件之间具备相同的优先级; (4) 不同工件的工序之间没有先后约束; (5) 同一工件的工序之间有严格的顺序约束。

对于本文研究的集成优化问题, 在生产过程中, 如果要进行设备的维护, 必然要停止生产活动, 这就造成了生产调度和设备维护的冲突。本文在柔性作业车间调度中安排设备维护方法借鉴Li等[4]的研究, 提出一种动态安排设备维护过程, 如图2所示, Oij表示工件i的第j道工序。具体步骤如下:

(1) 先按照单纯柔性作业车间问题进行决策, 决定每道工序的加工顺序以及加工的机器;

(2) 每安排一道工序之前, 计算该工序的加工机器i的实时役龄Zit, 如果安排该工序以后役龄超出了临界值Z′i, 则在该工序之前进行此机器的预防性维护PM;

(3) PM完成之后, 计算该机器回退后的役龄Z′it, 然后重复步骤 (2) , 直到安排在该机器的所有工序完成安排;

(4) 在每台机器上重复步骤 (2) 到步骤 (3) , 直到所有工序和PM都被安排, 然后按照不同的工序、工序和PM的时间约束调整调度安排。

当然, PM以后工件加工顺序如果做某些改变, 有可能会减小最大完工时间。这些会在算法中的帝国内同化环节和模拟退火环节中实现。

2.2 数学模型

本文对设备的预防性维修和生产调度进行有机集成, 将生产成本和多台设备的平均维护成本也作为模型的优化目标。把设备的维护考虑在作业计划之中, 以最小化最大完工时间、总生产成本和平均总维修成本为目标, 根据设备的可靠度要求, 在调度过程中动态地决定每台设备预防性维护的开始时刻, 制定设备维护和各个工序的生产计划。建立的数学模型如下:

(1) 最大完工时间为

(2) 总生产成本为

(3) 平均总维修成本为

该模型的约束条件如下:

式中, j、k、kj分别表示n个工件中第j工件, 某个工件的第k工序, 工件j包含的工序数量;Mjk为工件j的第k个工序可用的机器集合, Mjk⊆{1, 2, …, m};Xijk为工件j的第k个工序是否在机器i上加工;npr, i为机器i上预防性维护的次数;pi为设备i故障导致的生产损失;tijk为工件j的第k工序在机器i上的加工时间, i⊆Mjk;Ci为机器i上单位时间的加工成本;Cs, i为机器i维修固定费用;Cm, i为机器i的故障后维修成本;Cp, i为机器i预防性维护所需成本;Rit为机器i在时刻t的可靠度;Ri′为机器i的可靠度阈值;tbe, jk为工件j的第k工序开始的时间;ten, jk为工件j的k工序完工时间;tp, i为机器i预防性维护所需时间;tmc, i为机器i的维护结束时刻;Ni (Δt) 为Δt时间段内设备i发生故障的次数;L为一个足够大的正数。

式 (7) 和式 (8) 表示每个工件的加工工序的顺序约束;式 (9) 表示机器约束;式 (10) 表示在特定的时刻, 一台机器只能加工一种工件的一种工序;式 (11) 表示在任意时刻t, 设备i的可靠度不能低于可靠度阈值;式 (12) 表示同一台机器上设备预防性维护和工序的加工不能存在冲突。

3 多目标混合殖民竞争算法求解设备维护与柔性作业车间调度集成问题

殖民竞争算法的流程为初始化每个个体为一个“国家”, 根据国家能量的不同将这些国家分为“殖民国家”和“殖民地”, 将殖民地分给不同的殖民国家来形成一个个的“帝国”;然后, 在帝国内进行殖民地同化操作和帝国之间殖民竞争, 帝国同化操作是殖民地受到殖民国家的同化作用, 使得自身解的结构和殖民国家更接近;殖民竞争是找出当前能量最弱帝国内部的最弱殖民地, 将此殖民地设置为自由状态根据各个帝国的总能量和随机数来确定哪个帝国获得该殖民地。殖民地改革是选出所有国家中能量最弱的国家, 将该国家用一个随机产生的新国家替换掉[11]。

殖民竞争算法的操作特点使得算法中的较劣解能够和较优解相互作用, 相比于遗传算法, 殖民竞争算法中的较劣解可以向更优解更快速地移动, 亦或能产生比较优解更优的解。但是殖民竞争算法的特点也可能使算法陷入局部最优解不容易跳出, 模拟退火算法的思想是通过对已有的解运用某种邻域结构进行扰动来进行局部搜索, 试图得到新的解, 可以使得算法跳出局部最优。所以本文对已有的殖民竞争算法加入模拟退火环节, 可以将两种算法的特点结合起来, 使得该算法更加适合于求解本文研究的集成优化问题。这样虽然算法的时间复杂度会有所增加, 但会使得新算法的全局和局部搜索的能力都比较强。

殖民国家内竞争、殖民竞争和殖民地改革等过程参考文献[7], 本文只对帝国初始化和帝国内同化等过程进行设计。

3.1 初始化

对于多目标问题, 初始化时各个解的质量直接影响算法的收敛速度以及最终求解出的Pareto解集中的解的整体质量, 所以必须选择比较好的编码方式, 力求使初始化时产生的解的质量比较高。

柔性作业车间的殖民竞争算法采用两条编码, 一条是基于工序的编码, 用于说明不同工件的不同工序的加工先后顺序;另一条是基于机器的编码, 用来确定具体每个工件的每个工序在哪一台机器上加工。

3.1.1 工序序列的编码

在基于工序的编码中, 每个数字代表一个工件, 数字出现的次数等于该数字对应工序的个数。且第k次出现的一个数字代表该数字对应的工件的第k个工序, 例如编码[1 2 2 1 3 1 2 3], 表明工件1有三个工序, 工件2有三个工序, 工件3有两个工序。本文算法在国家初始化时, 对于基于工序的编码采用随机交换的方法, 将所有工件的工序按照顺序依次排列, 如[1 1 1 2 2 2 3 3], 然后随机交换工序位置, 就产生了该国家内基于工序编码的序列, 如[1 3 1 2 2 1 3 2]。

3.1.2 机器序列的编码

基于机器的工序中, 将各个工件的工序按照顺序排列下来, 然后每个位置上对应的机器就是对应工序所在的机器。如编码[1 3 1 2 2 1 3 2]表明工件1的三个工序分别在机器1、3、1上加工;工件2的三个工序在机器2、2、1加工;工件3的两个工序在机器3、2上加工。

为每个工序分配机器的时候要考虑该工序在不同可加工机器上的加工时间, 最好选择最小值对应的机器来安排, 同时又要兼顾考虑每台机器已经分配的负载情况, 不能使某台机器的负载过大。因此, 本文为了提高初始解的质量, 借鉴了Kacem等[12]提出的利用时间表的分配方法 (approach by locallization, AL) 和Pezzella等[13]的改进分配规则来进行编码, 使得编码的鲁棒性比较强, 进而得到质量比较高的初始解。但是这两篇文献中都没有考虑不同工件以及同一工件的不同工序的加工顺序。

本文在文献[12]的基础上对机器序列的初始化进一步改进, 即将加工时间的表格按照已经确定的工序排序从上到下对每行重新排序, 首先分配排在第一位的工序, 选择加工该工序时间最短的某台机器分配给该工序, 然后将表中该机器对应的加工时间列在该行之后的所有值均增加该工序的加工时间, 表示该机器负载已经增加。接着对剩下的每个工序都按照一样的操作, 最终确定对应该工序编码的机器分配方案, 过程如表1所示, 对于基于工序的序列[1 3 1 2 2 1 3 2], Mi为第i台机器, 首先将工序O11安排到最小加工时间的M3, 将M3剩余可加工的工序时间增加4, 再安排O31, 最终的安排如表1最右边三列所示, 得到的基于机器编码的序列为[3 1 2 3 1 3 2 1]。

由于要保证初始解的多样性, 本文算法中一半初始解的机器编码采用表1的方法, 另一半初始解的机器编码采用在该工序可用机器集合中随机分配机器的编码方法。

由两列编码就可以结合之前描述的动态安排设备预防性维护的方法, 在某台机器上安排某工序后, 若再安排下一道工序的加工就将使得设备可靠度低于阈值水平的时候, 就在该工序之后进行预防性维护。解码后画出相对应的甘特图, 如图3所示, 进行PM的时间均是根据机器可靠度的变化情况来决定的。

3.2 帝国内同化

帝国内同化就是在一个帝国内, 所有的殖民地都要受到殖民国家的同化作用, 使得所有殖民国家都朝比较好的解来转化。本文算法的同化过程采用交叉和变异操作, 各个殖民国家均要和所在帝国的殖民地进行交叉操作来进行同化, 同化之后得到的新解或许会支配原来的解, 这时就将原来的解用新解替换掉;新解也或许会和已有的Pareto解集中的解处于同一Pareto等级, 这时就将新解保留到Pareto解集中。由于要保证交叉变异以后得到的子代都是问题的可行解, 故一个国家内的两条编码所需要的交叉变异方式是不相同的。

3.2.1 交叉操作

针对柔性作业车间调度的复杂性, 殖民竞争算法中一个国家内两条编码的交叉分别进行, 其中第一部分基于工序的编码采用元素分集合的交叉方法, 第二部分基于机器的编码采用一种新型多点交叉的方法。

(1) 基于工序编码的交叉。该条编码交叉的过程是:将所有的工件随机分为两个集合J1、J2, 新国家内的编码先是继承殖民国家中集合J1内的工件对应的元素, 而后将殖民地中集合J2内的工件对应的元素分别填充到新国家内的编码空缺的元素中, 如图4所示, 其中J1={2, 3}。

(2) 基于机器编码的交叉。基于机器的编码采用多点交叉的方法, 具体操作是:先随机产生一条和编码等长的0-1序列, 将殖民国家中与0-1序列中的0位置相同的所有元素复制到新国家中, 殖民地中与0-1序列中的1位置相同的所有元素复制到新国家中, 如图5所示。

3.2.2 变异操作

(1) 基于工序编码的变异。基于工序编码的序列串采用交换与插入变异, 即从编码串中随机选取一个元素, 然后随机插入到编码的其他位置, 如图6所示。

(2) 基于机器编码的变异。不同工件的不同工序可选择的机器各不相同, 所以这部分编码的变异采用随机选取某个工件的某个工序, 将该工序的加工机器随机替换成该工序可选择机器集合中的其他机器, 如图7所示。

3.3 Pareto求解及排序

本文采取一种效率较高的Pareto解集求解和排序方法。设群体的规模大小为NP, 将群体按照支配关系分类排序为m个子集P1, P2, …, Pm, 这些子集中两两之间无交集, 且满足, 即Pk+1中的个体直接受Pk中的个体支配 (k=1, 2, …, m-1) 。经过排序之后, 候选解就会不断集散到最优解集的边界上。传统的排序方法构造非支配集时, 到了后期可能出现所有的或绝大多数个体均为非支配解, 这样一来排序速度就会变得很慢。为了克服排序速度慢的问题, 本文采用一种新型的快速排序方法。将传统的一个比较个体改为两个比较个体, 其中第二个个体与第一个个体不相关或第二个个体支配第一个个体, 这样, 算法具有更高的工作效率, 降低了时间复杂度。算法程序具体如下:

3.4 适应度函数

本文采用Enayatifar等[9]提出的目标组合法来量化每一个国家, 即

其中, Pareto最优解集的名次被设定为1, cn是个体n的适应度, fk (n) 是个体n的第k个目标值, Nrank是指相同层次Pareto解集里面的个体数。rank (n) 是0~1之间的随机数。该公式可以区分不同Pareto层次的个体适应度大小。然后可以根据下式计算各个国家标准化之后的能量:

式中, Cn为第n个殖民国家标准化之后的成本值, 即适应度。

标准化之后的成本Cn代表了殖民国家的能量, 即对于最小化问题来说, 成本越小, 能量越大。然后可以计算第n个殖民国家的殖民地数量:

其中, Ncol是殖民地数量, Nimp是殖民国家的数量。殖民国家成本越高, 其殖民地越多。

3.5 多目标混合殖民竞争算法

为了使殖民竞争算法拥有更好的局部搜索能力, 可以更快地获得优秀的Pareto解, 本文对Enayatifar等[9]提出的多目标殖民竞争算法进行了改进, 提出一种多目标混合殖民竞争算法 (multi-objective hybrid imperialist competitive algorithm, MOHICA) , 在帝国内同化之后, 加入了模拟退火的算法进行局部搜索。模拟退火算法具有优良的局部搜索能力, 即在搜索最优解的过程中, 除了可以接受优化解外, 还可以有限度地接受部分恶化解, 并且可以使接受恶化解的概率逐渐趋向于0, 从而使算法有可能从局部极值区域中跳出, 尽最大可能寻找更优解, 并保证算法的收敛性[14]。本文算法中模拟退火环节的核心是对已有解的扰动, 即根据已有的旧解, 运用特定的局部搜索方法寻找更优的新解。在根据旧解搜索得到新解时, 如果新解j支配旧解i, 则接受新解为当前解;否则根据与一个随机数的比较来确定是否接受新解, 其中f (j) 是国家j的能量, T为模拟退火环节的实时温度, 即转移概率为

本文对已知解中基于工序编码的扰动方式采用赵良辉等[15]提出的2变换邻域搜索。2变换邻域就是将已知解i的编码首尾相接, 从中任取两点, 将两点间的路径反向后形成的新解的集合称为i的2变换邻域, 搜索时从旧解的2变换邻域中随机挑选一个作为新解。由于基于机器编码的可行性要求比较高, 对于已知解中基于机器编码的扰动采用本文提出的机器编码的变异方式来进行。

在本文中, 模拟退火环节的步骤如下:

(1) 帝国同化后, 将所有的国家合并, 计算每个国家的能量值;

(2) 对当前所有国家依次进行扰动产生新的国家, 如果新国家支配旧国家, 则用新国家替换旧国家, 否则按照概率决定是否接受新国家到合并的国家中;

(3) 在温度为T的时候, 对每个国家进行一定次数的扰动;

(4) 使温度以衰减率α缓慢降低, 即Tk+1=Tkα, α∈ (0, 1) ;

(5) 重复步骤 (2) 到步骤 (4) , 直至满足停止条件。

多目标混合殖民竞争算法的步骤如下:

(1) 选择算法各个参数并运用本文的初始化方法生成国家群体;

(2) 用快速排序法得到所有国家的Pareto排序, 计算各个国家的适应度;

(3) 判断是否满足算法终止的条件, 即达到预设的代数或帝国数量是1;

(4) 根据适应度选出殖民国家, 并计算隶属各个殖民国家的殖民地数量, 按照数量将所有殖民地随机分配给殖民国家;

(5) 帝国内同化;

(6) 模拟退火算法对各个国家进行扰动, 寻找更优解;

(7) 将所有国家重新进行Pareto排序, 计算适应度, 进而重新选定殖民国家及隶属各个殖民国家的殖民地;

(8) 殖民竞争;

(9) 殖民地改革;

(10) 删除帝国;

(11) 重复步骤 (3) 到步骤 (9) ;

(12) 输出并保存最终的Pareto解集。

多目标混合殖民竞争算法的流程如图8所示。

3.6 算法的时间复杂度分析

初始化的过程主要与初始国家数量P, 所有工序的数量N和机器数量M有关, 每道工序安排以后, 就要相应地更新工序-机器时间表, 因此初始化过程的时间复杂度是O (PN2M) , 在一次迭代操作中, 帝国内同化, 殖民竞争和殖民地改革的时间复杂度均为O (NeNc) , 其中, Ne和Nc分别代表殖民国家的数量和每个帝国中殖民地的数量, 而模拟退火环节的时间复杂度为O (NMlogCr (Tf/T0) ) , 其中, T0代表初始温度, Tf代表终止温度, Cr代表降温系数;根据快速排序法的计算方法, 该环节的时间复杂度为O ( (NeNc) log2 (NeNc) ) 。本文提出的多目标混合殖民竞争算法总的时间复杂度为O (PN2M) +GO (NM) +GO (PN2M2logCr (Tf/T0) ) , G是算法的迭代次数。可以看出本文提出算法的时间复杂度与种群大小、算法迭代次数、问题规模以及参数的大小有关。

4 算法测试与比较结果分析

为了验证提出的多目标混合殖民竞争算法的有效性, 本文的测试分为两部分, 第一部分是将文献[4]中三个实例作为基准实例进行测试, 三个实例均是整合柔性作业车间调度和预防性维护的问题, 以最小化最大完工时间、机器总负荷和瓶颈机器总负荷为目标, 由于这三个实例模型的目标和本文模型的目标不同, 故将本文算法的目标改为三个实例中的目标;第二部分是本文模型的具体实例测试, 针对考虑维修成本的设备维护与车间调度集成的问题, 把本文提出MOHICA算法与传统多目标殖民竞争算法[7] (multi-objective imperialist competitive algorithm, MOICA) (不考虑模拟退火算法) , 以及文献[1]改进非支配排序遗传算法 (NSGA?Ⅱ) 进行比较。

4.1 基准实例测试

本文提出的多目标混合殖民竞争算法采用C++语言编程, 计算机运行环境为2.5GHz Intel Core i5多核CPU和2GB RAM的个人计算机, 算法的有关参数设置如下:群规模NP=100, 帝国数量为10, 残民地数量为190, G=100;对于模拟退火环节的参数, 本文取初始温度T=1000, 温度衰减率α=0.8, 终止温度Tf=1, 在温度T时, 每个国家进行n=5次的扰动。三个基准实例分别是8×8、10×10和15×10的整合柔性作业车间调度和预防性维护的问题。文献[4]中的几种不同算法 (混合遗传算法 (hGA) 、基于过滤束搜索的算法 (FBS-based) 和 (离散化学反应算法DCRO) 算法) 和本文MOHICA算法分别得到的Pareto解如表2所示, f1、f2和f3分别表示最大完工时间、机器总负荷和瓶颈机器总负荷。由表2可以看出, 本文的MOHICA算法求解基准实例得到的Pareto解集中解的质量不比前三种算法的质量差, 对于前两个基准实例, 部分解的f2目标的值比其他算法得到的所有值更优, 而且可以得到数量更多的Pareto解。

4.2 具体实例的测试

4.2.1 测试数据

在具体测试实例中, 柔性作业车间调度的数据来自文献[1], 是一个10×8的问题, 每台设备的历史维护数据来自现实制造车间数据[10], 并针对测试实例进行调整, 如表3所示。在表3中, ηi和mi分别是设备的形状参数和尺度参数, 此外, 假设每台设备的可靠度阈值为0.85。

假设设备i经过第j次预防性维修之前的役龄为Zij, 并且维修后又运行了Δt的时间, 则根据文献[10], 经过维护以后设备i在时刻t的故障强度λij也会以比例p (i) 降低, 计算公式为

所以第j次预防性维修之后到第j+1次维修之间, 设备故障发生次数平均值Nij (Δt) 计算的公式为

进而可以得到设备在一次预防性维护到下一次维护这段时间内的平均故障后维修费用:

4.2.2 具体实例测试结果

本文算法的参数设置与基准实例测试时的设置相同, 对比的MOICA算法除了没有模拟退火环节, 其余的参数设置与MOHICA相同, 对于比较算法NSGA?Ⅱ, 将初始化编码、交叉和变异的方式改为适合本文算例的方式, 参数设置如下:种群规模NP=100, 改进优先工序交叉概率50%, 多点交叉50%, 两种序列变异操作的变异概率各为2%, 选择概率值r=0.9, 最大进化代数100。采用三种算法求解上述实例得出各自的Pareto解集, 如表4所示, MT、PC和MC分别代表最大完工时间、总生产费用和平均维护费用。

为了比较这三个多目标算法的结果, 将Pareto最优解的平均比率作为一个量化比较对象。让P1和P2分别代表两个算法计算得到的Pareto最优解, P是P1和P2的并集 (P=P1∪P2) , 即P中仅含有非支配解。所以Pi中的Pareto最优解不被P中的解支配的比率RPOS (Pi) 为

比率越大, 证明算法效果越好。本文算法与两个对比算法的比率计算结果如表5所示。

图9和图10分别给出了MOHICA与NSGA?Ⅱ算法和MOICA的对比Pareto前沿图。

从表5可以看出, MOHICA算法的所有比率值都是1, 表明通过本文算法得到的结果均没有受普通MOICA算法和NSGA?Ⅱ算法得到的解支配, 显示MOHICA算法具有较强的搜索能力。从图9、图10可以看出, MOHICA算法得到的Pareto解的曲面在NSGA?Ⅱ算法和MOICA算法得到的Pareto解的曲面下边, 更靠近“原点”, 说明由MOHICA算法得到的解可以支配参考算法得到的解集。由表5和图9、图10可以看出, MOHICA算法能得到质量更优的Pareto解。

4.3 Pareto解集的决策

MOHICA算法获得一组Pareto解集后, 车间调度员还面临如何从这组Pareto解集选出满意方案的问题, 这需要根据决策者主观经验 (如依据决策指标重要性的排序) 或多指标决策技术进行排序或评估。

本文采用张洪等[16]提出的改进加权优劣解距离 (TOPSIS) 法, 对基本的TOPSIS法增加了权重的因素, 使决策过程更加科学。该方法的步骤为:首先将目标值矩阵的各元素取倒数转换为高优指标Xij;然后将每个目标值进行归一化处理, 处理后值为aij, aij计算公式为

通过式 (21) 得到变换后矩阵;再将矩阵每一列目标值中的最优值组合成理想最优解, 最差值组合成最劣解。计算公式为

式 (22) 计算所有待评对象所有目标值与最优和最劣解的距离Di+和Di-, 其中wj是第j个目标的权重值, a′ij是第j个目标值的最优值或最劣值。最后计算各个对象与最优方案的接近程度C′i, C′i=Di-/ (Di++Di-) , 选择Ci最大的方案作为最优解。本文设三个目标的权重分别为0.867、0.039、0.093, 经计算, 本文算法求解出的Pareto解中方案10为最佳解, 其对应设备维护与调度集成的甘特图 (图11) 中, J m为加工工件m, 深色的PM是预防性维护。

5 结语

多目标混合优化论文第5篇

多杆机构可以通过不同杆系的串联组合及对杆系参数的调整实现末端执行机构复杂的运动规律和运动轨迹，从而满足不同机械的结构设计要求，广泛应用于各种机械、仪表和机电一体化产品结构设计中。

多杆机构的传统杆系设计方法主要包括图解法，解析法，图谱法和模型实验法等，尤其是随着数值计算方法的发展，解析法成为各类多杆机构运动设计的一种有效方法。文献针对多杆机构末端执行机构运动存在非线性传递的问题提出了一种基于遗传算法的多杆压力机运动优化方法;文献通过对多杆系统的分级处理，借助杆系设计变量、约束函数和目标函数推导出最终的增广目标函数，从而计算得到系统的主要参数(运动参数和结构参数);文献通过建立了滑块位移，速度，加速度的数学模型，按滑块在工作行程内速度波动最小的原则建立了优化设计数学模型，最终运用复数矢量法对压力机双曲柄多杆机构进行了运动分析;文献以一种平面八连杆机构为例建立了平面多杆机构的运动分析数学模型，并利用MATLAB对其进行了优化设计和仿真分析。上述方法解决多杆机构运动设计问题的核心思想在于依赖建立能够客观反映机构运动学和动力学特性的代数解析方程(组)，借助系统耦合矩阵，实现对全系统状态方程的程式化推导，通过探讨方程(组)解的形式以及方程(组)解的存在条件等方式，实现对特定结构，特定参数变化条件下系统动态性能的定性描述与比较。然而，当多杆机构给定的运动设计要求较多或较复杂，难以用数学语言对其进行模型表达时，上述多杆结构优化设计方法表现出明显的建模周期长，模型可靠性差，模型重用性差等缺点，延长了产品的设计周期，增加了产品的设计成本。

自20世纪80年代以来，诸多学者提出从系统工程角度将计算机辅助设计优化技术应用于复杂产品研发，借助多种计算机辅助设计软件实现了不同领域仿真物理模型自动向数学模型的转化，并通过综合使用数值仿真技术、优化技术、统计技术、计算机和网络技术，最终实现多目标多约束条件下，产品综合性能和整体质量的改进，极大地提高了产品的设计效率，缩短了产品的设计周期。

1多杆机构优化设计问题

具有不等式约束的多杆机构优化设计问题的数学表达模型可以概括为:

min/maxf(x)=f(x1，x2，…，xn)

s.t.Rj(x··)=gj(x1，x2，…，xm)0≤(j=1，2，…，m)

即在满足m个不等式约束gj(x)≤0的限制条件下，求使目标函数f(x)趋于最小或最大的设计变量向量x=[x1，x2，…，xn]T，(x篟n，Rn为设计变量可行域)。其中目标函数f(x)可以是给定的滑块运动要求，也可以是机构整体的动力学输出特性要求。当给定的运动要求较多或杆系较复杂时，针对多杆机构结构优化设计可以归纳为典型的多目标多约束优化问题。

1.1双曲柄滑块机构

以一种由双曲柄机构与曲柄滑块机构串联组成的六连杆机构，即双曲柄滑块机构的优化设计问题为例。双曲柄滑块机构运动原理图，由于双曲柄机构ABCD的存在，双曲柄滑块机构的滑块运动输出特性得到了有效改善。在恒速驱动条件下，2种机构滑块运动输出特性对比。在相同滑块负载条件下，2种机构驱动电机扭矩对比。

在相同驱动条件下，双曲柄滑块机构与传统曲柄滑块机构相比，两者具有相同的工作周期，且在图示工作行程内，双曲柄滑块机构滑块运动速度趋于平稳，而传统曲柄滑块机构则表现出明显的速度波动。当上述机构应用于锻压机械传动系统，尤其是进行拉伸工艺操作时，传统曲柄滑块机构的上述运动特性极易造成拉伸件的拉裂，加剧模具的磨损。

在相同滑块负载条件下，双曲柄滑块机构与传统曲柄滑块机构相比，在图示负载作用周期内，双曲柄滑块机构驱动扭矩最大值明显小于传统曲柄滑块机构。双曲柄滑块机构上述动力学特性使其更适于作为需要实现大增力比的大型机械传动系统。

由于双曲柄滑块机构的上述特性，该机构被广泛应用于不同功能机床的传动系统，最典型的应用包括多连杆压力机的传动机构和插齿机传动机构，前者利用双曲柄滑块机构滑块加工工作行程内速度变化平稳的优点，相对传统锻压机械在相同加工效率的条件下，能够显著提高拉深工件的成形质量，同时降低模具的磨损;后者则利用相同负载条件下，双曲柄机构的加入能够显著降低系统对于驱动电机容量要求的特点，在不影响加工效率的前提下达到显著的增力效果，最大限度地提高相关加工设备的加工能力。

1.2多杆机构多目标多约束问题描述

以上述双曲柄滑块机构为例，作为多连杆压力机传动系统为适应不同加工工艺操作，不同加工材料，不同材料加工厚度对滑块加工运动轨迹的不同要求，往往需要针对特性的滑块运动轨迹对杆系结构参数进行优化设计;而作为插齿机传动机构，由于要综合考虑结构强度，齿刀寿命等因素，也需针对不同的结构增力要求对其结构参数进行优化。

如何针对不同加工应用领域，不同的功能设计要求，对同一多杆机构的尺寸参数进行优化，使其更合理地规划末端执行机构的运动学和动力学输出特性是多杆机构优化设计的核心问题。显然，上述双曲柄滑块机构针对不同加工应用领域，其优化目标侧重点不同，当双曲柄滑块机构应用于多连杆压力机时，其优化目标可以概括为:求使滑块运动输出满足特定曲线要求的连杆参数优化组合，侧重于对滑块运动学特性的优化;当双曲柄滑块机构应用于插齿机时，其优化目标则更侧重于提高双曲柄机构的增力效果，即求能够使机构输出扭矩最大化的杆系参数优化组合。

其中，M代表变量Loa，Lab，Lbc，Loc的可行域，双曲柄机构成立条件可以表述为:取最短杆为机架，且最短构件与最长构件长度之和小于或等于其他两构件长度之和，即:

Loc

Loa+Lab+Lbc-Loc-2max(Loa，Lab，Lbc，Loc)≤0

2基于Isight与ADAMS面向对象的多杆机构优化设计

通过Isight对用户建立的ADAMS参数化仿真模型的仿真分析流程进行集成和管理，借助Isight提供的多种优化搜索策略对多杆机构的多目标多约束优化问题进行求解，从而获得满足设计要求的整体优化结果。

2.1ADAMS参数化模型的建立

取双曲柄滑块机构从动曲柄水平位置为建模参考位置，利用优化参数对模型坐标点进行参数化，从而建立双曲柄滑块机构的仿真参数化模型。最终建立由杆系几何参数约束的ADAMS参数化模型。其中:α=cosLab2+Loa2+Loc2-Lbc22LoaLoa2槡+Loc()2，β=atanLocLoa()。

2.2双曲柄滑块机构优化

Isight具备试验设计方法(designofexperiment)，梯度优化算法(gradientoptimization)，直接搜索方法(directsearch)，全局优化算法(globaloptimization)等多个优化求解模块，考虑到上述双曲柄滑块机构设计参数不多，以梯度优化算法中的NLPQL算法为例，对双曲柄滑块相关目标函数的优化问题进行求解。

NLPQL算法将目标函数以二阶泰勒级数展开，并通过把约束条件线性化的方式二次规划得到下一个设计点，然后根据2个可供选择的优化函数执行一次线性搜索，其中Hessian矩阵由BFGS公式更新，该算法具有运行稳定，数据收敛速度快的特点。

3仿真结果分析

在Isight中设置好设计变量，约束条件和优化目标后调用ADAMS模型进行批处理运算，计算过程中对每个样本点进行迭代，以双曲柄滑块机构增力特性优化流程结果为例。

在NLPQL算法作用下，设计变量在所定义的变化限制范围内逐步收敛得到所限制范围内的局部最优解。，相同负载条件下，优化后的驱动扭矩较优化之前降低了35%，达到了良好的优化效果。

4结语

暖通空调系统的多目标优化模型第6篇

关键词：暖通空调系统；节能；优化；模型

引言：在现代社会，人们一天中几乎有半天甚至更多时间是待在室内的，因此，利用空调维持室内环境的健康是非常重要的。据统计，空调系统在公用建筑中的能耗超过了60%。因此，暖通空调系统的能效问题为学者们关注的重点问题。暖通空调系统的运行是一个多角度的问题，因此脱离室内空气品质的控制，仅仅将能耗减到最小是不可取的。最佳的控制方法策略是将室内热舒适性维持在一个可以接受的范围内的情况下去考虑系统的能耗。本文将在综合考虑经济性和热舒适性的基础上来提出暖通空调系统的性能最优化模型，能够使暖通空调系统在运行上减少能耗、提高效率以及保持居住环境的舒适性，从而暖通空调系统的性能可以大大提高。

一、数据类型

公用建筑中暖通空调系统的总能耗主要由四个部分组成：空气处理系统的能耗，水泵的能耗，供回风系统的能耗，以及末端设备的再热。在这里，由于热水、照明以及家电能耗在优化过程中的变化并不明显，因此不考虑这部分的能耗。暖通空调系统的所有能耗可以由下式1得出：ETotal=EHeat+EFan+EPump+QReheat （1）

空气处理系统、风机和水泵的能耗可以由开始装在系统中的设备进行校准，因此末端设备的再热负荷导致了所有的能耗。通过调节阀门使热水流与舒适区的实际要求相匹配。热负荷可以由下式2计算得出：QReheat=cm（TVAV_EAT-TVAV_BAT）

QReheat=cm（TVAV_EAT-TVAV_BAT）（2）

在此实验中，用于热舒适性的标准估值由室内温度和湿度来确定，基于管理要求，室温应该维持在21℃～22℃之间室内，湿度范围要在30%～60%。而实际上系统有时会运行在这个范围之外，并且会使人不舒适。因此，如果要使室内这种不舒适性不会发生，则要将室内温度和湿度作为限定条件。从而，在本研究中，优化算法中的补偿函数由限制条件来进行确定。

二、优化方法

本研究优化框架如图1所示。

三、暖通空调系统模型

根据以上讨论，建立最优化问题的双向模型，最终的优化可由下式3得出：min（yEnergy （t）） xSAT_Spt，xSASP_Spt

边界条件为：yEnergy （t）=f（XSAT-SPt，XSASP-SPt，XLoad（t），）XLoad（t-1），XCHWC-vlv，XSA-Hund，XSOL-Horz，XOA-Humd，XOA-TEMP

四、结论

本文讨论了一种基于数据处理的暖通空调系统优化方法。首先，研究实验数据并选择一些重要的参数作为输入。然后讨论若干数据挖掘算法，选择适当的算法建立优化模型，将其作为输出。从边界条件入手，建立最优化问题的双向模型，从而在暖通空调系统上得到大量的节能。

参考文献：

[1] W. Huang， M. Zaheeruddin and S. H. Cho。Dynamic simulation of energy management control functions for HVAC systems in buildings[J]，Energy Conversion and Management，2006， 47 （7-8）： 926-943。

多目标混合优化论文第7篇

多目标遗传算法MGA( Multi-objective Genetic Algorithms) 进化过程和编码相对简单,具有良好的群体寻优能力和较强的鲁棒性,并且能够并行地在全局解空间中搜索出问题的解,适用于在总体上把握进化的方向,可以作为有效的工具解决生产车间调度等组合优化问题,但其存在后期搜索效率低和过早收敛的问题［1］。

多目标粒子群算法MPSO( Multi-objective Particle Swarm Op- timization) 具有计算简单、效率高、鲁棒性强和个体数目少等优势,筛选的优良个体可以直接指导下一代粒子的进化方向,非常适合求解车间调度问题,但其自身发展时间尚短,需要进一步改进易早熟和陷入局部最优等缺点［2］。

本文将MGA和MPSO的优点有机结合起来,弥补各自的不足,构建出多目标遗传-粒子群混合算法MGPS( Multi-Objective Genetic Particle Swarm Algorithm) 。该算法结合基于机器与基于工序的方式进行编码,通过2Z维向量来解决位置向量与调度方案之间的映射关系,利用MGA优良的群体寻优能力在总体上把握进化的方向。根据MPSO计算简单和效率高的特点,首先高效地搜索出群体中优良的个体,接下来进行遗传操作,MGA的初始种群由各粒子群中收集到的最优个体组合成,用锦标赛选择与最佳个体保留相结合的方式进行选择操作,利用改进的POX交叉方法进行交叉操作。得有较优解后,用其替换各粒子群中的较劣个体。另外,为了扩大搜索领域,将个体迁移应用于各粒子群之间,如此循环,快速有效地找到目标的最优解。其结构如图1所示。

1混合算法流程

混合算法总流程如图2所示。

1) 算法编码

由HFSP的特点出发,将一种扩展的基于工序的编码应用于算法中,如图3所示,该编码前半部分利用基于工序的编码确定工序的加工顺序; 后半部分采用基于机器的编码给每道工序分配合适的机器,按每个工件工序的顺序进行机器的排列［3］。

MPSO的关键问题是建立调度方案与位置向量的映射关系。粒子的位置向量由两个相互的Z维向量P[Z]和M[Z]组成［4］,每个候选调度方案对应一个粒子,例如对于一个染色体[1,3,2,3,2,1],工件1的第一道工序用第一次出现“1”表示, 工件1的第二道工序用第二次出现的“1”表示,以此类推。 P[Z]上的分量和M[Z]上的每一个分量是相互对应的; P[Z] 上工序的机器号码通过M[Z]对应位置上的每个分量表示,其为不能大于机器总数M,表1列出了某个4台机器、8道工序、3个工件的混合流水车间调度的粒子编码。

2) 参数初始化

通过对大量HFSP研究数据总结表明,变异概率Pm取值范围是[0. 005,0. 1],交叉概率Pc的取值范围是[0. 5,0. 9],种群规模M取值范围是[30,100],具体优化问题决定粒子的维数D,算法进化终止的条件是最大迭代次数,群体经验影响因素c1和个体经验影响因素c2都设置为2,为了使算法快速收敛一致, 权重系数 ω 取值为0. 4 ~ 1. 2,为保证产生粒子的随机性, rand( ) 取介于[0,1]之间的随机数。

3) 初始个体群的产生

在多目标问题中,因为不同的决策者对优化目标的偏好不同,后面的迭代筛选过程常常会受到初始群体选择的影响。本文提出一种改进的初始群体产生流程,防止算法由于早熟而陷入局部最优,具体的操作步骤如下:

( 1) 工序的加工顺序排列被随机地产生一组;

( 2) 接下来随机地在每一道工序的可选机器集中选择两台机器;

( 3) 随机值在0 ~ 1之间产生,如果随机值大于0. 8,选择加工时间长的机器,否则选择加工时间短的机器。

经过改进的机制可以产生pso_n个粒子群,每个种群中包含pso_s个粒子,通过这些粒子建立起初始个体群。

4) 解码粒子个体

工序出现的次序和工件选用的工艺路线通过粒子的位置向量表示,工序调度的优先级通过粒子位置向量字符串中工序出现的顺序表示,调度序列中可能过早地加入优先级高的工序,粒子的位置向量解码为调度就可用上述算法解决［5］。

5) 产生权重,计算适应度

调度的完成时间、机器的总拖期和机器的空闲率经过个体解码后可以得到。按式( 1) 对调度方案的各个指标值进行处理［6］,从而使染色体的适应度通过多个目标函数值集合组成。

式中表示方案中第j个指标的最大值, bij表示第i个方案的第j个指标值, aij表示经过量纲化处理后的第i个方案的第j个指标值表示所有方案中第j个指标的最小值。

处理完成后,粒子个体位置矢量字符串通过x表示,设完成时间、机器的总拖期和机器的空闲率分别由: f1( x) ,f2( x) , f3( x) 表示。通过权重系数变化的方法,配合线性加权法,随机地为各目标值赋予权重［7］,最后通过线性相加计算个体的适应度如式( 2) 所示:

式中D表示足够大的正数, h表示目标个数,,其中h ( i ) 为随机数。

6) 粒子群搜索

在时间t内,全局最佳粒子记为X*g( t) ,最佳位置记为X*i( t) ,D维空间搜索中第i个粒子的速度和位置分别由Vi= ( vi1,vi2,…,vi D) 和Xi= ( xi1,xi2,…,xi D) 表示。按照如式( 3) 、式( 4) 来更新搜索过程中每个粒子的位置和速度［8］:

其中惯性因子用 ω 表示; 1≤d≤D; r1和r2是[0,1]中的随机数; 加速因子通过两个正常数c1和c2表示。

根据各粒子群不同的参数,分别侧重于局部开发或者整体探索,完成pso_n次粒子群搜索。

7) 个体替代与迁移

当每个粒子群搜索完成以后,将遗传算法种群中的较劣个体用粒子群中相应数目的较优解替代。并且将一定数目的个体迁移应用于各粒子群之间,从而可以保证各粒子群的多样性,并且可以扩大搜索领域。迁移操作通过借鉴自然界中个体往返迁移于不同的自然环境的生态学现象设计求解。

8) 遗传算法计算适应度

将目标值转化,接着赋予随机数权重,再通过线性相加得到个体的适应度,从而得到一致的MGA部分用的适应度函数和MPSO中用到的适应度函数。

9) 遗传算法操作

种群的选择、交叉、变异等遗传运算根据之前设定的参数运行计算,通过最佳个体保留与锦标赛选择两种相结合的方式进行选择操作,通过改进POX交叉方法进行交叉操作［9］,交叉操作过程如图4所示。

两个父代染色体分别用C1和C2表示,交叉后生成的子代染色体分别用P1和P2表示。其具体操作如下:

( 1) 集合N1和N2通过所有的工件随机生成;

( 2) 在保留位置不变的情况下,把C1中包含在N1中的基因复制到P1,把C2中包含在N2中的基因复制到P2;

( 3) 在保留位置不变的情况下,把C2中包含在N2中的基因复制到P1,把C1中包含在N1中的基因复制到P2。

算法的局部搜索能力可以通过插入的变异操作来改善,其操作如图5所示。

其具体操作如下:

( 1) 首先在染色体编码部分选择出一个随机的基因;

( 2) 在保持其他所有基因编码不变的情况下,将其随机地插入到另一个基因的前面。

种群中的较劣个体通过筛选出来的较优个体进行代替,种群的多样性通过小生境技术以维持,完成ga_n代遗传操作。

10) 判断是否满足最终条件

如果满足最终条件则输出最优解集,并且根据不同偏好选择解; 否则继续搜索,返回4) 。

2混合算法实例分析

通过完成时间、总拖期、设备利用率的仿真实验,验证算法的有效性和可行性。表2是4个工件6台机器的调度数据,每道工序在不同的机器上加工时间是不同的,并且对应多个可选择加工的机器,每个工件有3道工序,参数设置如表3所示,算法得到的最优解如表4所示,该表列出了4个最优解,图6和图7分表是方案一和方案二的甘特图。

在方案一和方案二中工件具有不同的加工路线,但是两个方案却具有相同的目标值,由此表明,该算法可以实现不同加工路线的灵活调度,对实际生产车间调度的具有现实意义。

Ponnambalam等［10］针对6台机器、6个工件的经典调度问题得到的最优调度结果是: 工件延误时间为31 min,机床闲置时间为259 min,生产周期为76 min。本文算法以生产周期、零件延误时间、机器闲置时间为目标与其结果进行比较。算法运行程序得到结果是: 工件延误时间为28 min,机床闲置时间为134 min,生产周期为55 min,最优调度甘特图如图8所示,可以看出其结果明显优于Ponnambalam。

3结语

本文针对HFSP问题,结合MGA整体寻优能力强和MPSO高效率的特点,设计了一种多目标遗传粒子群混合算法,克服了MGA进化效率低和MPSO易陷入局部最优的缺点。采用该方案不仅不需要考虑工件的加工路线,还可以缩短生产周期和提高设备利用率,更适应于求解实际的HFSP问题,典型的测试实例的计算结果表明,该算法是求解HFSP的有效方法。

参考文献

[1]王刚.高维优化问题的多目标遗传算法研究及其应用[D].湖北:武汉理工大学控制科学与工程学院,2012.

[2]王云,冯毅雄,谭建荣,等.基于多目标粒子群算法的柔性作业车间调度优化方法[J].农业机械学报,2011,42(2):190-196.

[3]张屹,卢超,张虎,等.基于差分元胞多目标遗传算法的车间布局优化[J].计算机集成制造系统,2013,19(4):727-734.

[4]常桂娟.基于微粒群算法的车间调度问题研究[D].青岛:青岛大学,2008.

[5]凌海风,周献中,江勋林,等.改进的约束多目标粒子群算法[J].计算机应用,2012,32(5):1320-1324.

[6]徐鹤鸣.多目标粒子群优化算法的研究[D].上海:上海交通大学,2013.

[7]赵张娜.多目标粒子群优化方法的实验分析[D].北京:中国地质大学,2012.

[8]董旭良,王建华.一种求解多目标优化问题的粒子群算法的研究[J].电子设计工程,2013,21(3):36-39.

[9]王瑞琪,张承慧,李珂.基于改进混沌优化的多目标遗传算法[J].控制与决策,2011,26(9):1391-1397.

冷藏车多车型混合配送调度优化第8篇

另外,冷链配送除了要消耗能源维持车辆运行外,还要耗费能源来维持车厢内货物的低温,难以避免地造成较高的碳排放量,对环境的破坏程度相对较大。虽然因碳排放造成的环境成本是一种外部成本,但在全球倡导低碳发展的大环境下,通过碳税或碳交易将这一外部成本内部化已是必然趋势。因此,环境成本也是冷链配送企业在决策过程中需考虑的一个方面。

目前,国内外对冷链问题的研究比较深入。部分文献考虑了冷链配送过程中质量的变化及相应的货损成本［２－４］:Rong等［２］提出评价生鲜产品质量的方法,并将产品质量水平整合到配送过程的成本中,运用混合整数线性规划模型为设计和运作供应链提供决策支持;Zanoni和Zavanella［３］建立生鲜产品质量下降率和制冷所需能量以及产品温度的关系,研究了温度和库存时间对产品质量、成本和供应链连续性的影响;Yu和Nagurney［４］通过引入弧乘数计算食品的指数衰减量并考虑了整个供应链中废弃产品的成本,模型还允许消费者根据产品质量区分不同产品。Kuo和Chen［５］提出了冷链配送中的多温共同配送系统,通过提高车辆利用率来保证产品质量和运输安全,减少冷链配送中的成本。部分文献运用不同的方法求解冷链配送问题［６－９］:Brito等［６］建立以总时间最短为目标的模糊规划模型,并运用模糊方法和混合GRASP-VNS启发式算法优化配送过程;Shi等［７］通过实时动态地收集冷链配送过程中产品的信息,运用三阶段调度控制决策模型,做出更合理的决策来降低系统的总成本;Zhang等［８］将径向基函数神经网络、模糊控制和数据分析方法结合在一起构建数学模型,通过对四种异常数据的仿真分析验证了模型的有效性;石兆和符卓［９］建立以运输、冷藏、货损和惩罚成本最小为目标的数学模型,在惩罚成本中考虑了路况的实时变化,并采用两阶段混合遗传算法求解算例。杨建华等［１０］考虑了国家的碳税政策,通过调整冷库的数量、布局以及超市向冷库分配的需求量,有效抵消部分碳税成本、大量降低冷链配送过程中的碳排放。

实际上,考虑了冷链特征的冷藏车多车型混合配送调度优化问题的基础是多车型车辆调度优化问题,国内外对该问题的研究比较成熟。Subramanian等［１１］和Penna等［１２］分别运用基于迭代局部搜索的启发式方法与集合划分规划结合的混合算法、迭代局部搜索元启发式方法求解多车型路径问题;Leung等［１３］运用带有局部搜索的模拟退火方法,求解了装载空间有二维约束的多车型路径问题;De等［１４］运用双信息素踪迹蚁群系统和禁忌搜索方法求解并改进带有时间窗的多车型多货种车辆路径问题; Choi和Tcha［１５］运用列生成技术解决了严格整数规划模型中的线性松弛问题,并对传统的车辆路径问题中的动态规划方案进行了改进,以更有效地生成可行列;叶志坚等［１６］构造了大旅程法和禁忌搜索法相结合的混合启发式算法求解多车型路径问题;熊浩和胡列格［１７］设计了遗传算法分别求解路径最短和油耗成本最少为目标的动态车辆调度优化;石洪波和郎茂祥［１８］设计了一种新的解的表示方法,运用禁忌搜索算法求解多车型车辆调度问题;葛显龙等［１９］将车辆使用费用分为固定费用和油耗费用,并设计量子遗传算法求解模型。

综上所述,针对冷链配送调度优化方面的研究集中在改变配送模式或改进求解模型的方法上,关于冷链成本构成因素对冷链配送优化的影响机理分析不够充分,也少有考虑多车型混合冷链配送优化问题。基于冷链配送的特性,本文的多车型配送问题的成本因素包括固定成本、变动成本、货损成本、制冷成本、时间窗外惩罚成本和环境成本,以这六项成本因素总和最小为目标函数,建立数学模型。其中,变动成本分为两部分进行求解,货损成本采用产品腐败的指数函数进行求解,制冷成本则令其与载重量正相关进行求解,更加贴近现实情况。运用三维矩阵编码形象直观地表示配送路径,开发混合模拟退火算法,量化分析不同车型单独配送和多车型混合配送时的成本差异, 以探究多车型在冷链配送中的优势。最后,在客户需求量分别增加10%、20%、30% 的情况下,灵敏度分析研究各车型使用量随着需求量增长的敏感程度,可为需求量变化时的决策提供指导。

1问题描述

1.1问题归结

多车型冷链配送是指不同车型的冷藏车载有冷链产品从配送中心出发,按照一定的路线和顺序,在相应的时间窗内给客户配送满足要求的货物。多车型冷链配送模式见图1。

问题的实质是已知客户的数量、位置、需求量和时间窗,安排不同类型的冷藏车为客户配送货物,在满足所有客户需求量和时间窗的前提下,合理优化不同类型的冷藏车的数量和配送路径,得到总成本最小的调度方案。

1.2冷链配送时间窗外惩罚成本

冷链配送的货物为易腐坏商品,不仅对低温环境的要求极高,对存放时间的长短也相当敏感。本文假设冷藏车到达客户处即开始卸货,不存在等待卸货。若冷藏车过早到达客户处进行卸货作业,会打乱客户的运营计划,此项成本应当由配送商承担;若过晚到达客户,商品的品质比预期低,价值降低且被售出的可能性减小,此项成本也应由配送商承担。本文采用混合时间窗外的惩罚成本来表示这两种情形下配送商应承担的费用。

混合时间窗即采用两个时间窗,包括客户i可接受的时间窗[tｉ１,tｉ２]和客户要求配送车辆到达的时间窗[tｉ３,tｉ４]。冷藏车在tｉ１之前或者tｉ２之后到达,将付出较高的惩罚成本M(M是足够大的正数);在[tｉ３,tｉ４]时间范围内到达,惩罚成本为0;在[tｉ１,tｉ３]时间范围内到达,单位时间的惩罚系数为a;在[tｉ４,tｉ２]时间范围内到达,单位时间的惩罚系数为b.则车型k的车辆u在时刻tｉｋｕ到达客户i所付出的惩罚成本F(tｉｋｕ)函数图像见图2。

惩罚成本的函数解析式见式(1):

2考虑冷链特征的冷藏车多车型混合配送调度优化模型

2.1建模前提

本文数学模型的建立基于以下假设条件:

1单一配送中心,配送中心的货量可以满足所有客户的需求;

2所有的冷藏车均从配送中心出发,最后回到配送中心;

3配送中心拥有多种类型的冷藏车,车辆总数能够完成配送任务,任意车型的载重量都不小于单个客户的需求量;

4不同的冷藏货物可混装;

5客户的数量、地理位置、需求量以及各客户的时间窗已知,任意两个客户之间均可通行;

6每个客户仅由一辆车服务一次。

2.2符号说明

本文的各项符号说明如下:

(1)参数

n:客户总量;

N:客户集合,N={1,2,…,i,…,n};

0,n+1:配送中心;

dij:任意两个客户i,j(i,j∈N)之间的距离;

qi:客i的需求量;

P:货物的平均单价;

Li:客户i的卸货效率;

K:冷藏车类型的总量;

{1,2,…,k,…,K}:冷藏车类型的集合;

Uk:车型k的冷藏车的数量;

{1,2,…,u,…,Uk}:车型k的冷藏车的集合;

Dk:车型k的冷藏车的载重量;

fｋ:车型k的冷藏车的固定成本(包括车辆的折旧费用和驾驶员工资);

vｋ:车型k的冷藏车的行驶速度;

a:冷藏车早于客户要求的时间窗上限(但不早于可接受时间窗上限)到达时,单位时间的惩罚系数;

b:冷藏车晚于客户要求的时间窗下限(但不晚于可接受时间窗下限)到达时,单位时间的惩罚系数。

(2)状态变量

tｉｋｕ:车型k的车辆u到达客户i的时刻;

t0ku:车型k的车辆u从配送中心出发的时刻;

tku(n+1):车型k的车辆u回到配送中心的时刻。

(3)决策变量

xｉｊｋｕ:0-1变量,车型k的车辆u的配送路径中客户i的紧后客户为客户j,其值为1,否则为0;

yｊｋｕ:0-1变量,车型k的车辆u服务客户i,其值为1, 否则为0。

2.3冷链配送成本分析

本文的成本因素除了常规的固定成本、可变成本和惩罚成本之外,还包括货损成本、制冷成本和环境成本。可变成本的处理与常规不同,不再将其视为与距离成线性相关的函数,而是考虑到冷链的特征将可变成本分为两部分进行计算。由于冷链货物的易腐特性和其对低温的严格要求,配送过程中因货物腐败所造成的货损成本、因耗能维持低温所造成的制冷成本都要纳入成本因素中。同时, 冷链配送较一般的配送而言,消耗的能量更多,因而碳排放量也就更大一些,因碳排放对环境造成破坏而引起的环境成本也是本文成本因素中的一个方面。

(1)可变成本

由于冷链货物多为生鲜产品,此类产品密度较大,冷藏车的装载量直接影响能源的消耗量。因此,本文的可变成本不仅与车辆行驶的每段路径的长短dｉｊ相关,还与该段路径上车辆剩余货量相关。

令cｋ１表示车型k的冷藏车空载时,运行单位距离的可变成本(以下称第一部分可变成本);cｋ２表示车型k的冷藏车装载单位货量、运行单位距离的可变成本(以下称第二部分可变成本);Oｌｋｕ表示车型k的车辆u的配送路径中,第l个客户的编号,式(2)表示该路径中客户总数, 式(3)表示该路径中所有客户的需求总量,式(4)表示该路径中前往第l′ 个客户时,车上剩余载货量。令,即与均代表配送中心。

至此,式(5)求出了所有配送路径总的第一部分可变成本,式(6)则求出了所有配送路径总的第二部分可变成本。

(2)货损成本

冷链货物的腐败主营是由微生物的繁殖引起的,随着时间的推移,腐败量的积累使得货物的腐败部分与正常部分的接触面积增大,货物的腐败速度也随之加快。因此, 多数文献中将冷链货物的腐拜速度设为常数是不够准确的。本文利用指数函数来刻画冷链货物的腐败量随时间的变化。

令式(7)表示配送车辆从配送中心出发直到在客户i处卸完货的时间段内,由于货物汞败造成的客户i处的货损成本。其中,α、θ是根据实际经验得到的刻画腐拜量的因子。

(3)制冷成本

冷藏车在整个作业过程中(包括在途运输和在客户处停车卸货),制冷机均要运转以维持低温,即车辆从配送中心出发直到服务完最后一个客户,制冷成本时刻存在。同时,制冷成本的高低也与车厢内剩余货量成正相关。令βｋ表示车型k单位时间、载有单位货量所付出的制冷成本, 则所有配送路径总的制冷成本Z见式(8)。

(4)环境成本

冷藏车在途运输时与到达客户处进行卸货时的碳排放成本略有不同,但差距较小,因此本文用e珋ｋ表示车型k工作单位时间的环境成本。则所有配送路径总的环境成本E见式(9)。

2.4数学模型

考虑了冷链特征的冷藏车多车型混合配送目标函数如下:

约束条件如下:

式(10)为目标函数,表示冷链运营总成本最低;式(11)表示同一个客户只能由同一辆冷藏车服务;式(12)表示每辆冷藏车配送路径的初始节点和结束节点为且仅为配送中心;式(13)表示不能重复服务同一客户;式(14)表示冷藏车所载货物的重量不超过其载重量;式(15)表示每一冷藏车的路线中除初始节点(配送中心)外任何一个节点(客户)有且只有一个紧前作业节点(客户);式(16)表示每一冷藏车的路线中除结束节点(配送中心)外任何一个节点(客户)有且只有一个紧后作业节点(客户);式(17)表示到达连续服务的两个客户时刻的递推关系;式(18)保证冷藏车到达客户i的时刻满足其可接受时间窗,式(19)为避免子回路约束。

3考虑冷链特征的冷藏车多车型混合配送模拟退火算法

针对本文模型及解的结构特点,采用混合模拟退火算法进行求解,理由如下:首先,多车型车辆路径问题的每个可行解都对应一组包含车型信息的配送路径,其编码的数据结构直接影响算法的性能,而模拟退火算法对解的结构要求相对较低,加之本文设计的解变换规则,不会产生不可行解;其次,模拟退火算法依照Metropolis准则以一定概率接受恶化解,可有效避免算法陷入局部最优解。

3.1解的编码方式

本文采用自然数编码,矩阵中的值为客户编号。单一车型配送时,运用二维矩阵表示解,每一行表示一条配送路径,见图3(a)。此时表示运用一种车型服务20个客户,配送路径为5-6-8-16-15;7-9-14-17-18;2-4-10-13-20;1- 3-11-12-19。多车型配送时,运用三维矩阵表示解,矩阵的层数对应车型数,每一层编码表示一种车型配送方案,每一层中的一行表示该车型的一条配送路径,见图3(b)。此时运用两种类型的冷藏车服务40个客户,车型1的配送路径是16-25-34-24-30;32-3-2-9-20;8-23-11-12-7;38- 18-26-22-15, 车型2的配送路径是14-27-28-13-4; 36-19-33-37-31;21-29-10-17-35;40-1-6-39-5。

但是,按照上述编码方式,配送方案中每种车型所使用冷藏车的数量和每条路径服务的客户数是固定的,不利于保证解变换时搜索到全部可行解。为了扩大解的搜索空间,矩阵要留有足够的0行,每一行都要留有足够的0位。0并无实际意义,仅起到扩大解规模的作用。

例如图3(a)中的矩阵,加入0扩大规模后见图4。此时该配送车型的配送路径数量由原来的4条变为[1,8]范围内任一整数值,每条路径服务的客户数也由原来的5个变为[0,20]范围内的整数值,极大提高了可行解的数量。

为满足极限情况,解的每个二维矩阵设为n列。行数设为z,z是一个与冷藏车载重量、客户数量、客户需求量以及客户时间窗相关的经验值。

3.2生成初始解

单车型配送初始解的生成按照以下步骤进行:

Step1:将n个客户按照各自要求的时间窗上限从早到晚编号,形成集合W = {1,2,…,i,…,n};将该车型冷藏车随机编号,形成集合V = {1,2,…,m,…,Uｋ};

Step2:在矩阵的第r(r=1,2,…,z)行,将客户i加入路径,判断是否能满足该车型的载重量要求及客户i自身的时间窗要求;

Step3:若能满足要求,在该路径中加入客户i后,将i从集合W中取出,放入已安排路径的客户集合X中;若不能满足载重量要求,结束该行,令r=r+1,返回Step2;若不能满足时间窗要求,令i=i+1,返回Step2;

Step4:当集合W变为空集之后,将形成的矩阵按照3.1规定的矩阵大小加入0扩大规模,形成初始可行解。

多车型初始解在单车型初始解的基础上,将单车型配送方案中满足其他车型载重量和时间窗限制的路径取出, 放到相应车型的矩阵中形成。

3.3解变换

通过对当前解进行变换,产生新解,即新的配送方案。本文采用产生随机数方法交换矩阵中的两个元素,生成新的配送方案。首先,在解矩阵中随机产生两个位置。这样, 产生的两个随机整数所对应位置的解编码可能会出现三种情形,即0和0、0和非零整数、非零整数和非零整数。若第h个位置被选定,令集合Gｈ存储解中第h个位置的可替换客户。集合Gｈ中元素确定方法如下:令i=1,判断客户i换入第h个位置后是否满足该位置紧前和紧后客户的时间窗要求、是否满足该条路径的载重量限制。若满足,令i∈ Gｈ;否则,iGｈ.令i=i+1,继续判断,直至i=n.

为了提高搜索效率,针对这三种情形本文设计了如下的解变换规则:

情形1:若两个数均为0。即两个位置均无服务客户, 不进行交换;

情形2:若一个数为0,其在解矩阵中的位置为h1,另一个为非零整数s1.若0所在的路径无非零整数,则交换;否则,判断0所在位置h1的可替换客户集合中是否包含s1,若包含,则交换,否则不交换;

情形3:若两个数为非零整数s２和非零整数s３,在解矩阵中的位置分别为h２和h３,则仅当时交换,否则不交换。

3.4算法参数设计

算法的退火过程由参数T控制(即T为当前温度), 初始温度T０与终止温度Tｅｎｄ均取常数。退火策略采用温度下降函数Tω＋１=δTω,ω为当前的外循环次数,δ为温度下降速率,取[0.5,0.99]范围内的经验值。

由于温度较高时,马氏链的收敛步长期望值较小,此时计算量大对提高精度的作用不大,而温度较低时相反。因此,每一温度T下的内循环次数设为自适应值1000- T/2,可以避免不必要的计算冗余。

每进行一次解变换,产生的新解较原有解的目标函数值的改变量为dc,若dc>0,算法以概率e－ｄｃ／Ｔ接受新解; 否则,算法以概率1接受新解。此规则对恶化解并非完全排斥,可避免算法陷入局部最优。

3.5 “两阶段”混合配送算法和“一体化”混合配送算法

针对多车型冷藏车混合配送调度优化问题,本文分别设计了“两阶段”混合配送算法和“一体化”混合配送算法进行求解。

“两阶段”混合配送算法基于“应当优先配载载重量大的配送车辆”的思想［１８］,优先采用单一车型的大车进行配送,求出配送方案。在已有的配送方案中,将客户需求量不超过小车的载重量限制的、改为小车配送后不违反客户时间窗的配送路径改由小车完成,使得每条路径都能“充分利用运力”。若新的配送方案成本更低,则予以采纳,否则保留原有方案。

“一体化”混合配送算法则是从编码阶段即将不同车型同时考虑,运用三维矩阵表示解,见图3(b)。解变换的过程中,交换的矩阵中两个位置的范围覆盖整个三维矩阵,以保证在全局范围内进行优化。加入图5所示的三种情形下的解变换规则,可以有效避免邻域变换时的非可行解,提高搜索效率。“一体化”算法直接整合多车型的优势,从整体降低配送总成本。

4算例分析

本文设计如下算例,验证针对考虑了冷链特征的冷藏车多车型混合配送调度优化问题的模型和算法的有效性。

4.1数值试验

运用matlab软件在50×50的范围内随机生成100个点的坐标,代表100个客户的位置,设配送中心的坐标为(25,25)。其次生成100个客户的要求时间窗,根据固定的时间窗宽度生成可接受时间窗的边界。最后在(0,0. 7]范围内随机生成100个客户的需求量。客户的地理分布情况见图6。

根据各点坐标求出配送中心到各客户、各客户之间的欧氏距离之后,乘以一定系数换算成路网距离。关于货物与客户的参数设置见表1,其中,L珚ｉ表示各客户的平均卸货效率。

本例采用三种车型进行配送,配送车辆从配送中心最早出发时刻为5∶00。三种车型的各项参数见表2。

4.2算法参数

本例中,每个二维矩阵的行数设为n/2,列数设为n, 即每个二维矩阵的规模为50×100。算法的初始温度T０=1000,终止温度Tｅｎｄ=1,降温速率为δ=0.9,内循环次数见3.4节。

4.3结果与分析

通过计算,三种车型单独配送、“两阶段”混合配送和 “一体化”混合配送五种方案下的相应成本见表3。

从五种配送方案的总成本分析,“一体化”混合配送方案最优,比车型1单独配送总成本降低9.1% ,比车型2单独配送总成本降低11.3% ,比车型3单独配送总成本降低15.2% ,比“两阶段”混合配送总成本降低4.7% .

相对而言,大车的各项成本较高,而小车的各项成本相对较低。采用车型1单独配送时,由于装载的冷链货物较多,每条路径持续时间较长,因此,此方案的货损成本和惩罚成本较高;同时,由于单位时间制冷成本高,此方案在制冷成本方面也处于劣势。采用车型3单独配送时,由于客户需求量的差异较大,车型3受自身载重量的限制,安排的车辆数多,每辆车每次仅能服务极少的客户便回到配送中心,固定成本高的同时,造成了极大的不必要旅行距离,变动成本极高。采用车型2单独配送可以利用该车型本身的“折中”效果缓冲上述两种情形下的极端结果,但总成本方面优势不大。

“两阶段”混合配送在一定程度上可以整合三者的优势,降低成本,但只起到了局部优化的作用。而“一体化” 混合配送可以充分整合三者的优势,在全局范围内优化, 将需求量大且时间窗分散的客户分配给大车服务,而需求量小且时间窗相对紧凑的客户分配给小车服务。这样,大车不能满足时间窗的客户或是运力浪费大的路径采用小车服务,小车受运力限制的路径整合起来交由大车服务。上述算例表明,“一体化”混合配送能十分有效地降低配送成本。

另外,本文提出的“一体化”配送方案相比于车型1单独配送、车型2单独配送和“两阶段”混合配送能有效减少碳排放引起的环境成本,其环境成本接近于碳排放最低的车型3的单独配送方案。因此,“一体化”配送方案在降低配送总成本的同时能有效减少碳排放,兼具经济意义和生态意义。

4.4灵敏度分析

在“一体化”混合配送模式下,所有客户需求量分别增加10% 、20% 和30% ,总配送成本及各车型使用量的增长情况见图7。

当客户的需求量增大时,总的配送成本以接近线性的趋势随之增长。车型1的使用量初期保持不变,在需求量增长到一定程度后开始上升;车型2的使用量以稳定的速度随着客户需求量的增长而上升;而随着客户需求量的增长,车型3的使用量相应减少,但初期需求量增加较少时, 减少的幅度大,随着需求量持续增加,其使用量开始回升。

该结果表明,随着客户需求量的增大,中型车使用量迅速上升以满足对运力的需求,其优势较明显且反映较敏感;大车反映相对迟缓,小幅度的需求量上升不会影响其使用量,只有需求量上升到一定程度后才引起其使用量的增加;由于小车载重量小,需求量增长幅度小时,小车的劣势开始显现,使用量减少,但需求量持续增长时,现有大车接近“饱和”,再增加使用量会造成新的资源浪费,进而影响总成本,此时小车的数量有所回升。

5结论与展望

多目标混合优化论文第9篇

关键词：项目进度计划,多项目,多资源约束,关键链,遗传算法,禁忌搜索算法

随着世界经济社会的发展, 项目管理扮演的角色日趋重要; 而项目的进度管理一直是项目管理的重点和难点。在竞争越来越激烈、资源限制日趋明显的今天, 传统的项目计划方法如CPM和PERT在解决资源约束下的网络规划问题时存在一定的局限性。另外, 传统的项目计划制定方法中对人和环境的因素考虑较少。由于人的惰性等心理行为因素会造成项目的延期, 使得成本增加, 对组织效益产生巨大影响。

Goldratt博士将约束理论［1］应用于项目管理为项目管理开创了一种新的方法, 即关键链项目管理 ( CCPM) ［2］。该方法综合考虑了时间、资源以及人的行为等因素, 将分散在各项工作中的安全时间抽取出来, 通过设置汇入缓冲 ( FB) 、资源缓冲 ( RB) 和项目缓冲 ( PB) 的方式将安全时间综合利用起来集中管理, 较好地解决了项目管理中的不确定性问题。多项目多资源背景下的关键链识别是一个NP难问题。许多学者对此问题进行了研究。Leach［3］认为应该找出多个项目共享的关键资源作为约束因素, 从而对不同优先权的项目进行不同的管理。Oyal等［4］综合考虑了项目中资源供应与使用状况和项目的复杂度, 提出了资源紧张度自适应程序和密度自适应程序。Haiying Ren等［5］首次指出了多agent系统在解决资源约束下项目进度计划问题上的优势, 分析了几种有代表性的多agent方法并指出了未来研究方向。Lianghong Wu等［6］研究了资源约束下项目进度计划问题, 以最小化项目持续时间为目标, 设计了一种基于改进差分进化算法进行求解。文献[7—9]研究了多项目多资源进度计划问题, 分别提出了基于蚁群优化算法、混合遗传算法和蚁群神经网络的求解方法。刘士新等［10］建立了多目标资源受限项目优化调度模型, 设计了基于关键链的项目调度方法, 采用基于优先规则的启发式算法进行求解。陈友玲等［11］提出了基于关键链的面向多项目计划编制新方法, 并通过Monte Carol模拟仿真验证了该关键链计划方法的可行性。彭武良等［12］将建立了关键链项目优化调度模型并提出了一种基于优先权的关键链计划生成方案, 设计了一种混合遗传算法的求解方法。

解决这一问题的方法主要可分为两种, 即精确算法和启发式算法［13］。精确算法可以得到最优解, 但随着资源的增多、项目复杂度的加大, 精确算法往往要花费的时间相当长, 在实际项目中就缺少了应用价值。而基于一定启发式规则的启发式算法, 与精确算法不同, 其特点是速度快, 通常可以得到比较理想的解, 但不一定能够得到最优解, 理想解与最优解之间往往存在偏差。

本文采用混合遗传、禁忌搜索算法来解决这个问题, 并通过改进算法缩小理想解与最优解的偏差, 制定科学合理的进度计划。

1 问题描述

多项目多资源项目进度计划问题主要研究在满足资源约束以及工序约束的前提下, 通过合理安排工序的开始和结束时间, 来达到一定的优化目标。而项目工期往往是项目管理者追求的最主要目标, 本文即是在给定项目和资源相关信息条件下, 综合考虑各种约束以及项目的重要度, 以尽可能少的时间完成项目任务。多项目多资源进度计划的数学模型描述如下:

在多项目问题中, 共包含着 α 个项目、β 种资源。P = { P1, P2, …, Pα} 表示项目的集合, R ={ R1, R2, …, Rβ} 表示资源的集合。w = { w1, w2, …, wα} 表示每个项目重要度的集合。N = { N1, N2, …, Nα} 表示每个项目包含的工序数目的集合。M ( ij) 表示第i个项目的第j个工序, STM ( ij) 表示工序M ( ij) 的开始时间, FTM ( ij) 表示工序M ( ij) 的完工时间, DM ( ij) 表示根据历史数据得到的工序M ( ij) 的持续时间, D'M ( ij) 表示以关键链法对工序M ( ij) 持续时间DM ( ij) 的重新估计。E为工序M ( ij) 的紧前工序的集合。At表示在t时刻进行的工序的集合, Bt表示在t时刻等待开始的工序的集合, 工序M ( ij) 的完成需要资源Rk的数量为rM ( ij) ，k, Rkt表示在时刻t资源Rk的可用量。Ti表示项目i的完工截止时间。T0表示多项目的开始时间。则可建立如下模型:

式中, 公式 ( 1) 表示目标函数; 公式 ( 2) 为单个项目工期的计算方法; 公式 ( 3) 表示应用关键链方法, 采用Goldratt提出的50% 法对工序工期进行重新估计; 公式 ( 4) 表示工序开始时间, 结束时间与持续时间三者的关系; 公式 ( 5) 表示项目工序间紧前紧后的约束关系, 本文仅考虑搭接关系为结束到开始且搭接时间为0 的情况; 公式 ( 6) 表示任一时刻所有工序使用的某种资源的总和不能大于该资源的可用量。

2 算法设计

遗传算法 ( GA) 是模拟生物在自然环境中的遗传和进化过程而形成的一种随机搜索方法, 它是一种典型而富有代表性的进化算法［14］。禁忌搜索算法 ( TS) 是对人类智力过程的一种模拟。它通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索, 并通过藐视准则来赦免一些被禁忌的优良状态, 进而保证多样化的有效探索以最终实现全局优化［15］。

遗传算法具有隐含并行性和全局搜索性两大特点, 且易于理解, 对问题的依赖性小。还具有较强的鲁棒性, 因此很适合作为算法的主体框架。充分地将遗传算法的全局搜索能力和禁忌搜索算法的局部搜索能力有机地结合在一起, 做到了优势互补［16］。综上, 这两种算法在关键链的识别与应用方面, 具有较强的优势。本文将采用这两种算法的混合算法来对项目进度计划进行优化。

算法首先以识别多项目关键链为目标, 随机生成初始种群, 以迭代次数为终止条件, 以适应值为评价准则。在满足迭代条件下进行遗传算法的选择、交叉、变异操作以及禁忌搜索操作。考虑算法的效率, 并不是每次迭代都进行禁忌搜索操作, 以常量K为周期, 用变量k记录迭代次数, 若k = K, 则进入禁忌搜索, 并将变量k重新设置为0, 否则不进行禁忌搜索操作。算法迭代终止后, 在多项目中加入缓冲, 最后输出整个多项目的进度计划。算法流程图如图1 所示。

2. 1 编码产生初始种群

根据初始输入项目和工序信息对多项目的所有工序进行编码, 每条染色体个体表示一种进度计划方案, 染色体上的每个基因就代表一个工序, 基因的先后顺序代表了工序开始时间的先后, 并且要求编码产生的任务序列中不含有重复的基因码。此外, 针对项目问题的特点, 工序的紧前紧后有严格的顺序限制, 例如, 打地基必须要完成后才能建筑房子, 而装修更要排在建房子后面。因此编码后, 需要对随机产生的染色体进行检验, 约束便是工序紧前紧后约束, 将不符合要求的染色体舍弃, 重新生成, 但不同项目的工序间可交叉进行安排。而种群的大小populationSize可根据具体问题规模而定。

具体方法为:α个项目共包含个工序, 编码时随机产生[1, N]之间N个整数的随机排列, 且每个整数只出现一次。然后检验生成的染色体是否满足工序约束, 满足则保留, 否则便舍弃并重新生成, 直到产生populationSize组满足要求的染色体为止。

2. 2 适应值评价

适应值是度量染色体对于环境的适应程度, 适应度较高的染色体将获得更多的繁殖机会, 而适应度较低的物种繁殖机会较少, 甚至逐渐灭绝。在本问题中的适应值是评价多项目进度计划优劣的标准, 是有关项目工期的变量, 因此为非负。评价个体适应值的过程分为两个阶段。首先, 将染色体进行解码处理。针对每条染色体进行解码操作, 解码是将抽象编码的工序转换成能用目标函数进行衡量的具体工序关系, 存在的约束有工序紧前紧后约束和资源约束。解码时对任一工序M ( ij) , 需记录工序M ( ij) 的开始时间STM ( ij) , 结束时间FTM ( ij) , 持续时间D'M ( ij) , 所需资源Rk的数量rM ( ij) ，k以及在任一时刻t资源k的可用量Rkt。然后, 计算个体的适应值F。将染色体解码后, 计算每个项目的完工时间Ti, 对应项目的重要度系数wi, 计算目标函数T', 则适应值F∝T'。

2. 3 选择操作

选择是指以一定的概率从种群中选取若干个体的操作。根据上面计算出来的适应值F, 本文采用精英选择和轮盘赌方法来进行选择操作。以一定的比例保留种群中的精英, 再通过随机数以轮盘赌方法选择其它个体。这样既能保留种群中的优秀个体, 又不破坏种群的多样化。

2. 4 交叉操作

将染色体两两配对, 根据交叉率进行随机交叉。交叉算子采用部分映射交叉 ( PMX) 操作［17］。将满足交叉条件的两个染色体个体进行交叉操作, 视为父代染色体, 随机生成两个位置节点, 交换父代个体两个交叉点之间的片段, 对于交叉点外的基因, 若它不与换过来的片断冲突则保留, 若冲突则通过部分映射来确定直到没有冲突的基因, 从而获得后代个体。PMX算子一定程度上满足Holland图式定理的基本性质, 子串能够继承父串的有效模式。

2. 5 变异操作

根据变异率对染色体进行变异操作, 从而产生新的个体。变异算子通常包括替换式或扰动式变异［17］, 根据本问题的特点, 要求设计的变异算子满足: 对任意一个染色体进行变异操作后, 所产生出的新个体应该能够对应一个具有实际意义的安排序列。因此, 采用替换式变异中的交换变异操作, 将染色体中2 个随机选取的基因相互交换, 从而产生出一个新的成像任务调度序列。例如, 对于一个长度为n初始染色体q: [x1x2x3…xn －2xn －1xn], 满足变异条件且变异位置为第2 个基因和第n - 1 个基因, 则变异后得: q': [x1xn －1x3…xn －2x2xn]。

2. 6 禁忌搜索操作

禁忌搜索的基本思想就是在搜索过程中将近期历史上的搜索数据存放在一个按某种存储结构和相应的禁忌准则构成的禁忌表中, 阻止算法重复进入、帮助算法跳出局部最优点, 并通过藐视准则来赦免一些被禁忌的优良状态, 进而保证多样化的有效探索以最终实现全局优化。其具体步骤如下:

2. 6. 1 初始解的选取

将经变异操作后的populationSize组染色体看作禁忌搜索的初始解X1、X2…XpopulationSize, 分别进行禁忌搜索操作。选定一个初始解Xi, Xi∈ { X1, X2, …, XpopulationSize} , 令禁忌表H = Ø。

2. 6. 2 终止条件

以最大迭代次数tsMaxCount为终止条件, 用变量t记录迭代次数, 若t = tsMaxCount则停止禁忌搜索操作, 比较当前解Xnow与禁忌表中最好的解Xbest, 若F ( Xnow) > F ( Xbest) 则输出Xnow, 若F ( Xbest) >F ( Xnow) 则特赦Xbest, 输出Xbest, 否则令t = t + 1, 继续下面操作。

2. 6. 3 邻域选择

用2 - opt实施邻域搜索, 在Xi的邻域N ( Xi) 中选出满足禁忌要求的候选集C - N ( Xi) 。

2. 6. 4 邻域评价

用适应值F为评价准则, 若F ( Xi') > F ( Xi) , Xi'∈ C - N ( Xi) , 则令Xi= Xi', 更新禁忌表, 否则不进行任何操作。

3 应用案例

为了便于证明模型和算法的有效性, 选取一个案例进行验证。该例子是一个典型的多项目多资源的混合项目, 共包括五个项目, 三种资源, 资源总量为 ( R1, R2, R3) = ( 9, 9, 9) 。多项目重要度系数 ( w1, w2, w3, w4, w5) = ( 1. 0, 1. 0, 3. 0, 3. 0, 2. 0) 。多项目信息如表1 所示。

3. 1 模拟结果及分析

采用Visual studio c#语言编程实现, 以为目标进行调度。参数选取如下: 种群规模populationSize = 1 000; 迭代次数iterMaxCount = 1 000;交叉率crossoverRate = 0. 75; 变异率mutationRate =0. 1; 禁忌循环次数tsCount = 50; 禁忌迭代次数tsMaxCount = 200。

3. 1. 1 结果说明

运行结果为: 得到最优目标函数值为0. 042 6。对应的染色体为: 0 -1 -29 -20 -21 - 13 - 14 - 15- 16 - 32 - 17 - 6 - 31 - 18 - 22 - 19 - 25 - 34 - 30- 8 - 33 - 7 - 24 - 35 - 23 - 9 - 2 - 11 - 10 - 12 -27 - 26 - 28 - 4 - 3 - 5。各项目的完成时间为 ( T1, T2, T3, T4, T5) = ( 41, 34, 21, 34, 13) , 多项目总工期为41。进度计划甘特图如图2 所示。

由图2 可知, 关键链为13 -14 -15 -22 -7 -9- 2 - 3 - 5, 关键链时间长为41。关键链方法采取的是一种将缓冲集中的思想, 在关键链识别的基础上, 在项目中加入汇入缓冲 ( FB) 和项目缓冲 ( PB) 进而得到关键链项目进度网络图, 如图3 所示。

而目前对缓冲区大小设置方法主要有两种, 即剪贴法 ( cut and paste) 和根方差法 ( root square er-ror) 。剪贴法的优点是简单易行, 缺点是缓冲区长度随着工作链的长度呈线性增长; 根方差法基于各工作执行时间相互独立的假设, 为关键链工作以及整个项目提供恰当的缓冲区保护。本文采用根方差法对缓冲区大小进行设置, 项目缓冲PB大小为:

多项目总工期为55. 39 d, 即56 d。以FB1为例, 关于汇入缓冲的计算公式为:

多项目缓冲区大小情况如表2 所示。

3. 1. 2 资源利用情况分析

资源R1、R2、R3的利用情况如图4 ~ 图6 所示。

根据多项目进度计划可知, 多项目采取的是项目间并行、工序间交叉进行的方式, 体现了多项目执行过程中综合利用有限资源、实现多项目整体最优的思想。

3. 2 方法对比

本文采用Goldratt博士提出的基于约束理论的关键链方法解决多项目进度计划问题, 这是一种综合考虑资源问题以及人的行为的方法, 是对项目进度进行计划新的诠释。针对本案例, 关键链方法得出的多项目总工期为56 d。根据传统网络图的思想, 针对同样的进度计划方案, 关键路径法得到的多项目总工期:

由上可知, 采用关键链理论对工期的估计明显小于网络图方法, 说明了关键链方法在时间估算上的优越性。此外, 关键路径法未能对人的行为因素以及环境因素进行考虑, 因而在多项目实际执行中, 提前完工的工序并不能促使其紧后工序的提前开始, 但一旦有工序未能按时完工, 就会造成其随后工序的推迟, 造成了进度的拖延。综上, 关键链方法综合考虑了多方因素, 其进度计划在实际操作中是有效可行的。

3. 3 算法对比

为了检验本文提出的混合算法的有效性, 针对此多项目问题, 运用本文提出的混合遗传禁忌算法与传统的遗传算法分别进行调度100 次, 将调度结果进行对比, 如图7 所示。

分析图7 多项目目标函数值分布情况, 将本文提出的混合算法与传统的遗传算法调度结果对比, 本文算法得到的目标函数值明显优于传统遗传算法, 计算效率可靠, 误差较小。综上, 说明了本文提出的算法求得的解更为优秀, 且更具稳定性。

4 结论

浅析多目标优化问题第10篇

1 问题定义

最小化MOPs的一般描述如下:

min F (x) = (f1 (x) , f2 (x) , …, fm (x) )

其中解x= (x1, x2, …, xn) ∈Ω为在决策空间Ω中的n维决策向量, f1 (x) , f2 (x) , …, fm (x) 为m个相互冲突的目标函数。对于解x1, x2∈Ω, x1支配x2 (记作x1酆x2) , 当且仅当坌i∈ (1, 2, …, m) 使得fi (x1) ≤fi (x2) , 且埚i∈{1, 2, …, m}, 使得fi (x1) ≤fi (x2) 。解x*∈Ω为Pareto最优解, 当且仅当不存在解x∈Ω, 使得x酆x*。Pareto最优解的集合称为Pareto最优解集 (记作P*) , P*={x*∈Ω|劭埚x∈Ω:x酆x*}。Pareto最优解集P*在目标空间的映射称为真实Pareto前沿面 (记作PF*) , PF*={F (x*) = (f1 (x*) , f2 (x*) , …, fm (x*) ) |x*∈P*}。若x1酆x2, 则称x2为支配解。解集P'被称为非支配解集, 当且仅当P'中不含支配解。

2 多目标优化算法

目前, 大量算法用于求解MOPs。通常, 可以将求解MOPs的算法分为两类。

第一类算法, 将MOPs转化为单目标优化问题。算法为每个目标设置权值, 通过加权的方式将多目标转化为单目标。经过改变权值大小, 多次求解MOPs可以得到多个最优解, 构成非支配解集[1]。

第二类算法, 直接求解MOPs。这类算法主要依靠进化算法。进化算法这种面向种群的全局搜索法, 对于直接得到非支配解集是非常有效的。基于进化算法的多目标优化算法被称为多目标进化算法。根据其特性, 多目标进化算法可以划分为两代[2]。

(1) 第一代算法:以适应度共享机制为分布性策略, 并利用Pareto支配关系设计适应度函数。代表算法如下。VEGA将种群划分为若干子种群, 每个子种群相对于一个目标进行优化, 最终将子种群合并。MOGA根据解的支配关系, 为每个解分配等级, 算法按照等级为解设置适应度函数。NSGA采用非支配排序的思想为每个解分配虚拟适应度值, 在进化过程中, 算法根据虚拟适应度值采用比例选择法选择下一代。NPGA根据支配关系采用锦标赛选择法, 当解的支配关系相同时, 算法使用小生境技术选择最优的解进入下一代。

(2) 第二代算法:以精英解保留机制为特征, 并提出了多种较好的分布性策略。代表算法如下。NSGA-II降低了非支配排序的复杂度, 并提出了基于拥挤距离的分布性策略。SPEA2提出了新的适应度分配策略和基于环境选择的分布性策略。PESA-II根据网络超格选择个体并使用了基于拥挤系数的分布性策略。

近年来, 在求解MOPs上, 新的算法框架也在不断提出。粒子群算法、分布估计算法、分解算法等已被逐渐用于求解MOPs。

3 评估方法

求解MOPs通常得到一个非支配解集, 而解集的评估相对于单个解的评估更加复杂。目前存在多种方法评估非支配解集的质量。通常, 对非支配解集的评估分为两个方面[3]。一方面, 是收敛性, 即评估非支配解集在目标空间与真实Pareto前沿面的趋近程度。常用方法有错误率、覆盖率、世代距离、高维空间及其比率、基于聚集距离的趋近度评价方法等;另一方面, 是分布性, 即评估非支配解集在目标空间分布的广度和均匀度, 常用方法有空间评价方法、基于个体信息的评价方法、网格分布评价方法、个体空间的分布度评价方法、基于聚类的评价函数等。

4 测试用例

算法性能的评估需要客观的测试用例。Schaffer、Kursawe和Deb分别在1985年、1991年和1999年提出了较简单的两目标优化测试用例SCH、KUR和DEB。Zitzler、Deb和Thiele在2000年提出了6个两目标优化测试用例ZDT1~ZDT6。Deb、Thiele、Laumanns和Zitzler在2002年提出了7个多目标优化测试用例DTLZ1~DTLZ7, DTLZ1~DTLZ7的决策变量和目标数可以扩展到任何数目[4]。上述测试用例均无约束, 其Pareto最优解集和真实Pareto前沿面可在 (http://www.cs cinvestav.mx/~emoobook/) 下载。Liu在2008年为CEC2009提出了23个更加复杂的测试用例CF1~CF10、R2-DTLZ2、R3-DTLZ3、WFG1和CF1~CF10。其中CF1~CF7为7个无约束两目标优化测试用例, CF8~CF10为3个无约束三目标优化测试用例, R2-DTLZ2、R3-DTLZ3、WFG1为3个无约束五目标优化测试用例, CF1~CF7为7个带约束两目标优化测试用例, CF8~CF10为3个带约束三目标优化测试用例。CEC2009的测试用例的问题描述、Pareto最优解集和真实Pareto前沿面可在网站 (http://dces.essex.ac.uk/staff/qzhang/moeacompetition09.htm) 下载。

5 挑战和困难

由于MOPs与现实应用的密切相关性, MOPs面临许多研究课题:

(1) 现有大部分求解MOPs的算法都基于进化算法, 新的算法框架亟待提出。

(2) 对多目标优化算法的评估需要能够客观反映算法优劣的评估方法和一组测试用例。评估方法和测试用例的选择和设计, 是一个研究的关键问题。

(3) 现有多目标优化算法各有其优缺点, 某个算法对求解一个问题是有效的, 而对求解另一个问题可能是无效的。那么如何使各算法的优缺点互补也是一个尚待研究的问题。

6 结论

MOPs在工程实践和科学研究中是非常重要的。本文通过对MOPs的问题定义、多目标优化算法、评估方法、测试用例四个方面对MOPs的相关问题进行阐述, 最后分析了求解MOPs的挑战和困难。

摘要：本文介绍了多目标优化问题的问题定义。通过对多目标优化算法、评估方法和测试用例的研究, 分析了多目标优化问题所面临的挑战和困难。

关键词：多目标优化问题,多目标优化算法,评估方法,测试用例

参考文献

[1]P.Hajela and C.Y.Lin.Genetic search strategies in multicriterion optimal design[J].Structural and Multidisciplinary Optimization, 1992, 4 (2) :99-107.

[2]Coello Coello, C.A.Evolutionary Multi-Objective Optimization:A Historical View of the Field[J].IEEE Computational Intelligence Magazine, 2006, 1 (1) :28-36.

[3]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007.

基于蚁群优化的多目标社区检测算法第11篇

摘要：蚁群优化算法作为单目标优化问题，由于只有一个目标函数，通常会将解限制到特定的范围内。当优化的目标不恰当时，算法可能失效，比如分辨率限制问题。我们将多目标优化的思想与传统的用于社区检测的蚁群优化算法相结合，增加了目标函数个数，即增加了解的评价指标数目。该算法引入多目标策略，提出多目标ACO算法，该算法在一次运行过程中会产生一组Pareto最优解。并在三个真实世界网络证明该算法的有效性和准确性。

关键词：复杂网络；社区检测；蚁群优化算法；多目标优化

中图分类号：TP18文献标识码：A

1引言

1991年意大利学者Dorigo M等人首次提出了蚁群优化算法[1，2]引起了学者的广泛关注与研究。蚁群算法是一种基于种群的启发式仿生进化系统，该算法采用了正反馈分布式并行计算机制，易于与其它方法相结合并且具有较强的鲁棒性。

本文介绍了一种基于蚁群优化的多目标社区检测方法，将蚁群优化算法与多目标策略[3]相结合，是一种优化模块度的社区检测方法。对于多目标优化问题，通常无法得到最优解，若同时考虑多个目标函数则算法将会得到一组优于其它解的最优解集。该集合叫做帕雷托（Pareto）解集或者非支配解集。

2基于蚁群优化的多目标社区检测

蚁群优化算法（ACO），是一种基于蚂蚁觅食行为的启发式方法，用来解决困难的组合优化问题，并且已经成功的应用到了各种棘手的问题，像二次分配问题（QAP），车辆路径问题（VRP）等。在1996年，Gambardella等人提出了一种修正的蚁群优化算法——蚁群系统（Ant System，AS），已经成功地应用在旅行商问题上。在这之后，科学家们也发明了一些改进的算法，比如精英蚁群系统（Elitist Ant System，EAS），最大最小蚁群系统（MaxMin Ant System，MMAS）以及排序蚁群系统（RankBased Ant System，ASrank）。

运用蚁群优化来做社区检测，首先需要指出如何表达一个解，其次就是如何构建一个解，然后就是信息素的初始化以及更新。下面我们将详细描述该算法。

2.1编码方式

社区就是复杂网络的子图，因而检测社区结构就等价于找出能揭示网络最好分割的一组子图。因此，社区检测问题的解可以明确地表示为：一个n个元素的向量表示图，其连通分量相当于社区。向量的元素和索引对应于图G=（V，A）中的节点。例如，向量中第i个元素等于j，即节点Vi和Vj之间有边相连，也就是说这两个节点在同一个连通分量里面，即处于同一个社区。

该编码框架的优点有很多，最重要的是不需要预先知道复杂网络的社区划分数目。解码的过程需要找出所有的连通分量。所有属于同一个连通分量的节点被划分到一个社区，解码过程是有必要的且可以通过广度优先搜索（breadthfirst search，BFS）或者深度优先搜索（depthfirst search，DFS）在线性时间内完成。解码完成后，会得到一个表示每个节点归属的向量。这种基于基因近邻的编码框架已经应用到了多目标聚类领域。该框架在社区检测的应用中有几个主要的优点，最重要的是，不需要预先知道社区的真实划分数目K，因为在解码过程中能够自动地得到K的取值。

3.1真实世界网络

本节将MOACO算法应用在三个真实世界网络上，分别是Zacharys Karate Club、Bottlenose Dolphins、Books about US politics。以上复杂网络是社会网络分析领域中的经典数据集，将这些数据在并与没有加入多目标策略的ACO算法以及GA、GAloacal算法进行了对比。由表2可以看出，三十次独立运行后，在Zacharys Karate Club网络中，ACO和MOACO的平均模块度值均不如GA和GA-local算法的结果好，而MOACO和ACO的平均模块度相差不大；在Dolphin social network网络中，本文提出的MOACO算法的平均NMI值明显好于其它算法。在Dolphin social network网络中，MOACO算法的模块度Q平均值与ACO算法的结果相差不大，而NMI的平均值要好于ACO算法。

为了验证蚁群规模和迭代次数对算法的影响，以Zacharys Karate Club网络为例进行参数分析，参数α、β、T、ρ、ε的值不变化，算法独立运行三十次求平均模块度值Q和平均NMI值，讨论蚁群规模N对算法结果的影响。

由表3可以看出，随着蚁群规模的增加，平均模块度值呈增长趋势，在蚁群规模为80时，达到了最大值。而由于蚁群优化算法中蚂蚁个体选择路径是随机的，因而平均NMI值没有呈现一定的规律，而当蚁群规模为40时，平均NMI值取得最大值。

表4表示参数α、β、N、ρ、ε保持不变，讨论迭代次数T对算法结果的影响，算法独立运行三十次的算法结果如表4所示。

由表4可知，迭代次数对算法的平均模块度值影响不大，而当迭代次数为150次的时候，平均NMI值取得了最大值。

图2表示调节参数过程中，算法取得的最优结果，即每一次运行的模块度值和NMI值，data1表示平均模块度值，data2表示平均NMI值。最优参数为：迭代次数150次，种群规模40。可以看出模块度值非常稳定。

3.2计算机仿真网络

本节使用经典的GN benchmark复杂网络来检测算法的可行性和有效性。GN基准网络是由Newman等提出。对于该基准网络，每个图包含了128个节点，分为4个由32个节点构成的社区。每个节点平均有Zin条边与同社区内节点连接，Zout条边与社区外节点连接。其中Zin+Zout = 16，作为每个节点的期望的度。随着Zout的增大，所产生的随机网络给社区检测算法带来了更大的挑战。特别是当Zout大于8时，意味着每个节点在社区内的边都要小于社区外的边，这时网络的社区结构就会非常模糊。当Zout≤ 8时，节点外度所占的比例小于内度所占的比例，因此算法应该能检测出网络中存在的社区结构，当Zout = 0时，表明节点的外度为0，此时节点仅与自身社区内的节点相连接，社区结构非常明显。分别对Zout从0到2进行了测试，对每种类型的网络产生一个复杂网络，使用NMI来衡量算法检测的结果和真实网络划分之间的相似性。对于每个网络，计算三十次独立运行的平均值。

由表5可以看出，当GN网络的外度为0时，该算法可以准确地检测出网络划分情况；当GN网络的外度为1和2的时候，该算法得到的结果也还都是有效的。

但是，在蚁群优化方法中，其算法复杂度比较高，所需要的搜索时间很长，而且容易出现所有的蚂蚁所对应的解完全相同这种“停滞现象”。导致了当复杂网络的社区数目较大时，算法不能产生有效解。另外，该算法对计算机生成的仿真网络不能得到有效的结果，这是我们进一步研究的内容。

4小结

基于传统的蚁群优化算法（ACO）算法的缺陷，提出了一种用于复杂网络社区检测的多目标蚁群优化算法MOACO，该算法将继续沿用传统的基于模块度优化的策略，加入了多目标的思想，每次迭代过程中，根据两个目标函数的不同折中，最终得到Pareto解集，选取每一代中优先级最高的那一组解。在三个真实世界网络和GN网络中的外度较小的网络上证明了算法的有效性，并将提出算法与ACO算法进行了比较，NMI平均值要优于ACO算法，模块度Q的平均值与ACO算法相当。缺点是不能处理社区划分类别多的复杂网络，对于结构模糊的GN网络，算法的效果不明显。

参考文献

[1]HONGHAO C， ZUREN F， ZHIGANG R. Community detection using ant colony optimization [C] Evolutionary Computation （CEC）， 2013 IEEE Congress on. IEEE， 2013： 3072-3078.

[2]DORIGO M，BIRATTARI M，STUTZLE T. Ant colony optimization[J]. Computational Intelligence Magazine， IEEE， 2006， 1（4）： 28-39.

[3]SOLNON C， Ghédira K. Ant colony optimization for multi-objective optimization problems[J]. Internation Journal on computer science， 2010.

[4]GONG M， CAI Q，CHEN X， et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. Evolutionary Computation， IEEE Transactions on， 2014， 18（1）： 82-97.

多目标混合优化论文第12篇

采购量分配是供应商选择问题中的重要组成部分, 传统市场上选择供应商时, 主要考虑供应商所能提供的最低产品价格, 或者最优折扣等直观条件甚至只凭直觉臆断, 缺乏客观科学的选择方法。然而, 我们往往还需要结合考虑供应商的供货能力、速度、进价、供货次品率、售后服务等多种因素, 并且, 为了使采购方的最终利益达到最大化, 更需要在产品质量、交货可靠性、成本等多个目标之间优化排列组合, 得出最优解。

国内外学者在求解供应商选择问题上进行了大量研究工作, 目前主要有定性方法和定量方法。定性方法较为简单, 主要是招标法和直觉判断法。而定量方法则是目前被研究得比较多的方向, 主要有层次分析法, 线性权重法, 遗传算法以及粒子群算法等。

笔者对选择供应商单产品采购量分配问题, 提出了一种基于Baldwin效应的混合多目标粒子群优化算法 (BM-M O PSO) , 而后使用BM-M O PSO对单产品采购模型进行求解, 求得Pareto最优解, 并将算法与多目标粒子群算法作对比, 验证算法的有效性。

背景知识

1. 单产品多供应商采购模型

从多个供应商处采购同一个产品且只考虑采购阶段是供应商选择中的常见问题, 对单阶段单产品多供应商采购模型, 四个假设前提是:考虑价格折扣因素, 数量折扣类型;采购都是单阶段内进行的;不存在产品无法供应情况;运输费用由供应商支付。

假设采购一种产品时, 可供选择的供应商有6个, 3个目标是最小化采购总成本、总延迟交货数、总次品数。各个供应商供货的次品率、延迟交货率、供货能力、折扣信息等所有数据来自文献《A fuzzy m odelforsupplierselection in quantity discount environm ents》 (W ang, TY&Y ang, Y H, 2009) , 在此不详细罗列, 可得具体模型及其约束式 (1) :

2.基本粒子群算法

早在1995年, K ennedy和Eberhart就初次提出了粒子群算法 (PSO) 。PSO重点模拟的是鸟群的寻食活动, 每一个粒子代表一个可行解, 同时被赋予速度, 进而根据自己的最优位置和整个鸟群的最优位置, 调整自己的飞行方向和速度。设Xi=[xi1, xi2…, xin]代表粒子i现在的位置, Vi=[vi1, vi2…, vin]表示粒子i当前的飞行速度, Pi=[pi1, pi2…, pin]为粒子i曾经过最优的位置。其进化速度和位置见公式 (2) 、 (3) :

其中, 下标j为粒子第j维;i为第i个粒子;t为第t代;、c1、c2是加速常数, 通常取0~2;w为惯性权重;r1~U (0, 1) 、r2~U (0, 1) 是两个互相独立的随机函数;粒子的飞行速度vij∈[-vmax, vmax]。

基于Baldwin效应的混合多目标粒子群优化算法 (B M-M OPSO)

1. 基于Baldwin效应的局部搜索学习策略

“Baldwin效应”理论是由生物进化学家Baldwin提出并命名的, 该理论反驳了现代进化论后天的学习并不能直接改变个体基因, 无法通过获得性遗传直接遗传给后代的观点。Baldwin认为, 后天学习虽然不能改变自身基因, 但是后天学习可以影响其行为, 同时能将学习到的优良性状遗传给后代。经过后天学习, 部分个体更好地适应环境, 那么生存几率就会更大, 能留传下来的后代也会更多, 最终经过一系列的遗传和进化操作, 学习指导下的个体将会往具有这种学习能力的遗传方向发展, 最终影响个体的染色体性状。

当粒子群进行Baldwin效应局部搜索时, 有3种情况:

(1) 在搜索初期, 大部分粒子远离前沿, 容易找到支配解, 此时让粒子向支配解学习, 使粒子群迅速向前沿靠近。

(2) 若flag次局部搜索得到的都是非支配解, 那么粒子群已达到了搜索末期, 此时应转变搜索方向, 引导粒子群在优化方向上作多样化扩散, 此时的非支配方向为:

其中, 表示搜索得到的第i个非支配解。

(3) 当搜索状况在 (1) 与 (2) 之间时, 将xi的个数d与q (即可容忍的非支配解数, q=3) 的关系, 自主选择搜索方向:若d<q, 按照情况 (1) 处理, 若d≥q, 按照 (2) 处理。

2. 基于Baldwin效应的局部搜索学习策略步骤

依据上面的分析, 基于Baldwin效应的局部搜索学习策略步骤为:

(1) Step1:粒子群粒子x0记为初始解y0, 设置迭代次数i=0, d=0。

(2) Step2:在解y0的r领域[y0 (1-r) , y0 (1+r) ] (r表示决策变量范围的百分比) 内, 随机选取一个解y1, i++。

(3) Step3:若, 依据第一种情况, 采用Baldwin学习策略, 并令xnew=y0+k· (y1-y0) (k表示学习程度) , 转Step5;若, 仿照依据第一种情况学习, 并令xnew=y1+k· (y0-y1) , 转Step5;不然转Step4。

(4) Step4:d++, 计算非支配方向d, 参照第二种情况。若d>=q, 采用三点二次插值法计算最优步长s (傅英定等, 2008) , 计算新的解xnew=y0+d·s, 转Step5。不然转Step2。

(5) Step5:若i≤flag转Step2。不然, 输出xnew替换旧的粒子x0。

为了防止粒子群陷入局部最优, 在进化初期利用惯性权重w调整全局搜索能力, 使初始粒子群均匀分布。到了中后期, 则引入Baldwin学习策略加速算法收敛并改善解集分布, 解决粒子群算法解集质量提高难度大, 多样性不足, 收敛缓慢等问题。此时, 外部种群也就是精英粒子相对靠近Pareto前沿, 若进行Baldwin学习, 将更多地朝着非支配方向搜索。因此, 局部搜索对象采用内部种群, 有效地改进算法收敛性和防止种群的退化。

3. 变异策略选择

笔者引入了非均匀变异策略, 非均匀变异是指采用一种在左边领域或者右边领域内取值的方式, 两个领域非对称, 见公式 (5) 。

其中, 为返回0或1的随机数, U B和LB为vk的上界与下界, △ (t, y) 为依据公式 (6) 计算, 返回[0, y]之间的随机值, r为[0, 1]内的随机数, b则反映了代数对值得影响程度 (参考原文中取值为5) 。

4. 惯性权重设置

采用惯性权重从0.9逐代递减至0.4的渐变方式, 见公式 (7) 。使粒子群起初着重全局搜索, 得到均匀分布的领导粒子后逐渐加快收敛速度。

其中, t为当前代数, 为最大迭代次数, w1取0.9, w2取0.4。

5. BM-M O PSO算法流程

(1) Step1算法参数设置。设定flag=5, 初始化粒子速度为0, 个体最优位置和全局最优位置, 当前代数t=1, 并用拥挤距离排序法管理外部种群。

(2) Step2是否进行局部搜索。若当前迭代次数小于总迭代次数的三分之一, 则不进行局部搜索条件转Step3, 否则转Step4。

(3) Step3全局搜索步骤。选择一个全局最优, 依据基本公式更新速度和位置, 转Step5。

(4) Step4局部搜索步骤。粒子以概率Pls进行基于Baldwin效应的局部搜索学习, 转Step5。

(5) Step5非均匀变异。随机输出一个0, 1之间的数, 若小于Pmut, 则使用非均匀变异算子对粒子进行局部变异。

(6) Step6重复Step2~Step5, 直到达到最大迭代次数。若, 输出外部种群;否则, t=t+1, 转Step2。

实验分析

1.实验环境和参数设置

采用BM-M O PSO对上述问题进行求解, 并采用M O PSO求解作对比分析。为便于粒子进行搜索, 首先对速度及位置作简单的整形转换, 将公式 (2) 修整为:

多目标供应商优选及采购量分配模型中的等式约束:

根据ε约束处理机制 (Liang&Suganthan, 2006) , 可转化为公式 (10) :

其中, ε表示等式约束条件的容忍值, 这里取极小正数。

在此基础上, 两种算法分别求解多目标采购量分配模型, 两种算法内部种群大小均为100, 外部种群大小300, 迭代100次。在BM-M O PSO中, 设置局部搜索半径r=0.15, , , flag=5。

2.数据分析

(1) 收敛性方面。根据50次运算结果, 绘制平均收敛曲线, 如下图所示。其中:横坐标上数值表示当前代数, 纵坐标上数值为对应代数时精英种群的G D值。随着运算过程的进行, 多目标粒子群优化算法求得精英解集对应的G D值1.3左右一直降至0.5左右, 而混合多目标粒子群算法所得精英解集对应的G D值则从1.28左右一直减少至0.25左右。两条曲线之间差距在逐渐增大, 且较为明显, 说明粒子群向前沿的收敛速度在加快。这证明了BM-M O PSO算法对粒子群的后期搜索过程具有性积极指导作用。

(2) 多样性方面。对SP指标作统计分析 (结果见表1) 。由表1可知, 由BM-M O PSO得到的解集在最小值、最大值、均值、中值与标准差上都比M O PSO小, 其中均值提高了近4%、中值则提高8%左右, 说明在相同的迭代次数条件下, 采用混合算法进行求解, 所得解集的分布性有了确实的提高, 标准差提高近25%, 说明混合算法的性能也更稳定。

(3) 运算效率方面。对运行时间作统计分析 (结果见表2) 。从表2中可看出, 各个值都得到了大幅度提高, 基本上接近或超过20%, 说明算法的运算效率并没有因为增加局部搜索过程而有所降低。数据文件的分析显示, 是因为引入Baldwin学习策略, 减少了外部种群维护的时间所致。

结论

从收敛性、多样性、运算效率三个方面的实验分析结果说明, BM-M O PSO是多目标优化问题的有效解决手段, 能为决策者提供优质的Pareto解集。性能比较仿真则阐释了BM-M O PSO算法在收敛性、多样性、运算效率方面均优于M O PSO, 说明Baldwin学习策略的引入不仅在粒子群的搜索进化中作正向的引导, 而且没有增加运算负担。

参考文献

[1]Ebrahim, R.M., Rzami, J.&Haleh, H.Scatter search algorithm for supplier selection and order lot sizing under multiple price discount environment[J].Advances in Engineering Software, 2009, 40 (9) :766-776.

[2]Liang, J.J.&Suganthan, P.N.Dynamic Multi-Swarm Particle Swarm Opt imizer with a Novel Constraint-Handling Mechanism[A].Vancouver, CANADA:IEEE Congress on Evolutionary Computation, 2006:9-16.

[3]Whitley D, Gordon V S, Mathias K.Lamarckian evolution, the Baldwin effect and function optimization[M]//Davidor Y, et al. (Eds.) , Parallel Problem Solving from Nature-PPSN III.Berlin, Germany:Springer-Verlag, 1994:6-15.

[4]Wang, L.&Yoon, K.S.Multiple attribute decision making[M].Berlin:Spring-verlag, 1981.

[5]Wang, T.Y.&Yang, Y.H.A fuzzy model for supplier selection in quantity discount environments[J].Expert Systems with Applications, 2009, 36 (10) :12179-12187.

[6]Ken nedy J, Eberhart R.Particle swarm optimiz ation[C]//Proceedings of the 1995 IEEE International Conference on Neural Networks Proceedings:vol.1-6.Piscataway, NJ, USA:IEEE, 1995:1942-1948.

[7]Baldwin J M.A new factor in evolution[J].American Na turalist (S0003-0 1 47) , 1896, 30 (3) :441-451.

[8]Zhang Jia-qi, CHEN Qi-jun.Ho w Learning Affects Evolution:Research and Simulation Validation[J].Journal of System Simulation (S1004-731X) , 2007, 19 (24) :5849-5855.

[9]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007.

[10]王林, 陈璨, 张金隆, 易觉.基于改进粒子群优化方法的供应商优选与订货量分配模型[J].中国管理科学, 2009, (6) :98-103.