多方法混合算法

多方法混合算法（共8篇）

多方法混合算法 篇1

0 引言

利用载波相位测量是全球导航卫星系统实现快速、高精度定位的必要步骤。在接收机进行连续的载波相位测量过程中, 由于卫星失锁、被遮挡等各种原因容易导致载波相位整周计数发生错误, 产生周跳[1~3]。在GPS载波相位测量中, 周跳的探测与修复一直是个重要问题[4], 众多学者对此展开研究并提出了许多周跳探测及修复的方法。

目前常用的方法主要有高次差法、多项式拟合法、相位减伪距法、电离层残差法、宽巷相位减窄巷伪距法、小波变换法、卡曼滤波法等[1~13], 但每个方法都存在不同的问题, 如相位减伪距法只能探测出大的周跳;电离层残差法易受电离层影响, 对特殊周跳不敏感, 具有多值性[6,14];宽巷相位减窄巷伪距法对两个频率上出现的相等周跳无法探测等问题[5,8]。而目前大多数学者主要是针对单一方法进行探索和改进, 对多种方法混合进行周跳探测的研究还较少。本文在研究了相位减伪距法、电离层残差法、宽巷相位减窄巷伪距法三种算法优缺点的基础上, 提出一种多方法混合算法。该算法充分利用了上述三种算法的优势, 可以探测出大于1周的周跳, 并且在探测过程中可以标记出野值。同时改进了周跳的搜索策略, 使其可以唯一地分离出周跳并加以修复。采用实测数据进行实例分析, 结果表明新算法原理简单、易于实现, 具有很强的实用性。

1 相位减伪距法、电离层残差法、宽巷相位减窄巷伪距法原理

1.1 相位减伪距法

接收机k对卫星j的测码伪距观测量的观测方程和载波相位观测量的观测方程分别为:

其中ρ (t) 为测码伪距观测量, R (t) 为卫星与接收机的几何距离, c为光速, δtk为接收机钟差, δtj为卫星钟差, δρtrop (t) 为对流层延迟改正, δρρion (t) 和δρφion (t) 为伪距测量与载波相位测量的电离层改正, λ为载波波长, φ (t) 为载波相位观测量, Nj为整周模糊度。下文若出现以上各变量, 含义与此相同。

由公式 (1) 、 (2) 可以看出测码伪距观测方程不含模糊度, 因此可以认为测码伪距观测值不受周跳的影响。继续比较两式会发现除电离层延迟影响、多路径效应和测量误差外, 其他误差影响相同。于是用式 (2) 减去式 (1) 得:

然后利用式 (3) , 在历元间求差可得如下检测量D1:

其中Δt为采样间隔。

检测量D1消除了站星几何距离影响, 如果信号采样间隔较短, 因电离层残差、多路径效应在时间上相关性较大, 所以历元间求差后, 其对周跳检测量D1的影响较小, 此时周跳检测量D1的精度主要受伪距测量误差的影响[6]。伪距测量的测距精度对于P码约为29cm, 而载波相位相应的波长为λ1=19.03 cm、λ2=24.42 cm。对于式 (4) 运用误差传播定律得, L1∶mD1≈1.8周, L2:mD1≈2.2周。因此在能获得L2的P码观测值的情形下, 以三倍检验量方差为限, D1检验量能探测出大于7~8周的周跳。

1.2 电离层残差法

电离层残差法由Goad提出[2,6]。使用双频载波相位测量值的电离层残差组成电离层残差检测量, 利用电离层残差检测量在历元间的变化来探测是否出现周跳。在双频相位观测方程之间取差, 得

式 (6) 中为电离层残差。

研究公式 (5) 可发现这个组合包含频率间电离层影响之差, 频率间模糊度之差, 频率间多路径之差和接收机噪声, 对于站星几何距离、接收机和卫星钟差都已消除, 电离层延迟的影响被大大减弱。对于式 (5) 在历元间求差, 便可得到电离层残差法的检测量D2:

若L1、L2的周跳分别为ΔN1和ΔN2, 则有

当电离层比较稳定, 采样率较高, 没有周跳时, D2在零附近波动。但当有周跳时, D2值会有跳变。由此可根据历元间的电离层残差检测量来判断是否有周跳。但是不能确定周跳发生在哪个载波上。根据式 (8) , 按照误差传播定律可知,

假设L1和L2的测量误差均为mφ=±0.01周, 则有mD2=±0.023周。按3倍检测量中误差为限差, 可知限差为±0.07周, 也就是当两个载波上的周跳引起的历元间电离层残差检测量D2变化值大于0.07周时, 就能够探测出周跳。

1.3 宽巷相位减窄巷伪距法

宽巷相位观测值减去窄巷伪距观测值可以消除站星几何距离及电离层的影响[14]。在宽巷相位与窄巷伪距的观测方程之间取差, 可简化为下列形式:

从第1个历元至第i个历元所求得的i个ΔN值的均值及其方差σi2可用下列递推公式计算:

根据第i+1个历元的双频观测值求得的公式。如果成立, 则认为i+1处历元有周跳;如果成立, 则认为i+1处历元为野值[1,5,10,14]。

2 算法思想与设计

2.1 多方法混合周跳探测算法

通过对以上三种方法的研究, 相位减伪距法只能探测出大于7~8周的周跳, 对于小周跳无能为力。电离层残差法可以探测出小周跳, 但当历元间电离层影响较大时, 该方法将难以探测出周跳[15], 且若在两个频率上发生了77/60, 9/7等特殊的周跳时, 电离层残差法失效。宽巷相位减窄巷伪距法不受电离层影响以及卫星和接收机钟差的影响, 可以探测出小周跳。但是对于ΔN1等于ΔN2的周跳, 该检测量失效。电离层残差法与宽巷相位减窄巷伪距法都无法单独区分出发生周跳的频率。

本文多方法混合探测的方法是利用上述三种方法的特点, 使其优势互补, 检测出所有的周跳。基本思路是首先利用相位减伪距方法对观测文件进行大周跳探测与修复, 生成新的观测文件。新文件中可能仍然存在周跳, 但存在的周跳都会小于7~8周。然后利用电离层残差法与宽巷相位减窄巷伪距法的混合方法对新观测文件进行探测。具体多方法混合探测算法流程如图1所示。

2.2 周跳搜索与修复

因为电离层残差法与宽巷相位减窄巷伪距法都无法单独的区分出发生周跳的频率, 所以周跳值必须借助于其他的方法加以分离确定。例如Turboedit方法引入了伪距组合方程, 利用解方程的方法进行求解周跳[14]。利用这种思想求解周跳值, 无法避免四舍五入带来的误差, 甚至还会引入伪距观测噪声误差, 使周跳计算存在3~4周的不确定性[10]。但是如果利用最佳周跳搜索方法进行搜索, 则可以避免这些问题[10]。本文算法正是利用周跳搜索的思想确定周跳值。

首先利用相位减伪距法进行周跳探测与修复, 可以把周跳缩小在-8~8周之间。由于在-8~8周之间不会出在9/7比例的周跳值, 就可以用最小电离层残差值来确定最佳周跳值。为了进一步缩小搜索范围, 提高搜索效率, 提出如下方法:

根据公式 (7) 和 (8) , 可以得到电离层残差法公式 (13) :

然后根据宽巷相位减窄巷伪距法对公式 (10) 进行历元间求差, 得公式 (14) :

对式 (13) 、式 (14) 求解方程组, 可以得到ΔN1与ΔN2的浮点值。然后按上文所讲的最佳周跳搜索方法, 对这个浮点值上下相邻的四个整数值进行搜索, 进而分离确定最佳周跳。通过这个简单的计算, 就可以把搜索范围缩小至4个数。这大大提高了搜索效率, 且不会引入舍入误差。经过实例分析表明, 该方法简单有效。

3 实例与分析

为了验证本文方法的有效性, 采用2009年3月27日的观测数据进行实验。数据情况说明如下:采样间隔:1s;观测数据类型:L1, L2, P1, P2;使用G12号卫星的数据进行实验, 共有2390个历元。为了使图像显示得清析明了, 图2~图5只截取了前200个历元, 进行显示。

针对三种方法周跳探测的肓点, 笔者设计了如下实验数据:在第10历元处加周跳 (1, 0) , 在第15历元处加周跳 (0, -1) , 在第50历元处加周跳 (-1, -1) , 在第70历元处加周跳 (1, 1) , 在90周历元处加周跳 (9, 7) , 在110历元处加周跳 (77, 60) 。本文所说在某一历元处加周跳, 指从该时刻起之后的所有历元均加相应值。

从图2、图3可以看出, 对于在第10、15、50、70历元处的1周的小周跳, 相位减伪距检测量变化不明显, 无法检测出小周跳。对于添加的7、9、77、60大周跳, 检测量波形变化明显, 超过阈值。当检测量达到或超过阈值时, 可以认为此处发生了检测量 (取整) 的周跳, 虽然这种方法不严密, 修复后的周跳中可能会残余小周跳, 但小周跳均小于阈值。并且这种方法快速简单, 为后续工作打下了基础。

从图4中可以看出, 对于在第10、15、50、70历元处的1周的小周跳, 检测量有明显的变化, 超过阈值。但是对于在90、110历元处的9/7, 77/60周跳检测量波形没有变化, 不能探测出来。

从图5中可以看出对于在第10、15历元处加的1/0、0/-1周的小周跳和在90、110处加的9/7、77/60大周跳, 检测量有明显变化。但是对于在第50、70历元处-1/-1, 1/1相等周跳, 检测量没有变化, 无法探测。

从图2~图5可以看出, 相位减伪距法、电离层残差法与宽巷相位减窄巷伪距法的优缺点具有互补性。本文正是利用周跳多方法混合探测与修复的思想, 使其优势互补, 实现所有的周跳的探测。然后利用所给的周跳搜索方法, 可以准确地分离出周跳值, 并加以修复。为了检测本文算法的正确性, 计算了数据的LC-PC[10]残差值, 如图6所示。

从图6中未进行周跳修复的LC-PC残差分析图 (未固定模糊度) 可以看出, 在有周跳发生的历元处均有台阶式跳变, 最大跳跃可达到17m。这将对后续的定位精度产生严重影响。

在经过本文算法修复后, LC-PC残差值比较平稳, 在一个固定值上下随机性的波动。可以看出, 本文算法对周跳的探测与修复是十分有效和实用的。

通过实验表明P1和C1对本文算法影响不大, 如果没有P1数据, 可以用C1代替。同时对于其他采样间隔的数据, 笔者也做了相同的实验, 表明1~30s采样间隔对本文算法影响不大。由于篇幅有限, 不再一一列图表示。

4 结论

本文充分利用相位减伪距法、电离层残差法与宽巷相位减窄巷伪距法各自的优势, 进行有机组合, 设计出一个多方法混合周跳探测与修复算法。该算法不需要测站、卫星轨道等信息, 能弥补以上三种方法的不足并发挥其优势, 可以探测出1周以上的周跳。且通过笔者改进的周跳搜索方法可以唯一地分离出不同频率的周跳。方法原理简单, 易于实现, 有广泛的适用性和实用性。

多方法混合算法 篇2

针对属性权重信息完全未知、属性值为精确数、区间数和三角模糊数的`混合多属性决策问题,给出了逼近理想点法.该方法通过建立两个二次规划模型来确定属性的权重,再根据方案与理想点的相对贴近度的大小来对方案进行排序.最后给出了算例.

作 者：曾三云 龙君 ZENG San-yun LONG Jun 作者单位：曾三云,ZENG San-yun(吉首大学,数学与计算机科学学院,湖南,吉首,416000)

龙君,LONG Jun(吉首大学,民族预科教育学院,湖南,吉首,416000)

多方法混合算法 篇3

多目标进化算法 (Multi-objective Evolutionary Algorithm, MOEA) 是智能计算领域的研究热点之一[1]。由于智能计算具有本质并行性、 毋须求导、 一次运行产生多个解等优点, 因此它是求解多目标优化问题 (MOP) 的有效方法[2]。目前, 比较有代表性的算法有SPEA[10]、SPEA2、NSGA[1]、NSGA2[9]、PAES[7]、MOPSO[8]等。MOP表示为

$\begin{array}{l}\min \overrightarrow{f}(\overrightarrow{x})=[f{}_1(\overrightarrow{x}),f{}_2(\overrightarrow{x}),\cdots ,f{}_k(\overrightarrow{x})]{}^{{\rm T}}\\ \text{s}.\text{t}.g{}_i(\overrightarrow{x})\ge 0,i=1,2,\cdots ,m\end{array}(1)$

其中, 决策向量$\overrightarrow{x}$∈Rn, 目标向量$\overrightarrow{f}$ ($\overrightarrow{x}$) ∈Rk, gi ($\overrightarrow{x}$) 为约束条件。

在多目标优化问题中, 各个目标之间可能是相互冲突的, 不存在唯一解使所有目标函数同时最优, 可能存在这样一组某种折衷或妥协的非劣解集, 求解MOP就是获得该非劣解集。

多目标优化问题常用的基本概念如下:

①Pareto支配:向量$\overrightarrow{u}=[u{}_1,u{}_2,\cdots ,u{}_k]{}^{{\rm T}}$支配$\overrightarrow{v}=[v{}_1,v{}_2,\cdots ,v{}_k]{}^{{\rm T}}$, 满足:∀i∈{1, 2, …, k}, ui≤vi∧∃i∈{1, 2, …, k}:ui<vi, 记为:u≺v.

②Pareto最优解:可行域中一点$\overrightarrow{x}{}^{*}\in \Omega (\Omega$为可行域) 为Pareto最优解, 当且仅当不存在另一个可行解, $\overrightarrow{x}{}^{*}\in \Omega$使得所有不等式fj (x) ≤fj (x*) 成立, 其中j=1, …, q, 且至少存在一个j∈{1, …, q}, 使得严格不等式fj (x) <fj (x*) 成立, 则称x*为多目标优化问题的一个Pareto 最优解。

③Pareto最优解集:多目标优化问题$\overrightarrow{f}$ ($\overrightarrow{x}$) 的Pareto最优解集ΡS由所有Pareto最优解组成, 即${\rm P}{}_S:=\{\overrightarrow{x}\in \Omega |\rightharpoondown \exists {\overrightarrow{x}}^{\prime }\in \Omega ,\overrightarrow{f}({\overrightarrow{x}}^{\prime })\prec \overrightarrow{f}(\overrightarrow{x})\}$。

④Pareto front:给定多目标优化问题$\overrightarrow{f}$ ($\overrightarrow{x}$) 及其Pareto最优解集ΡS, 则$\overrightarrow{f}$ ($\overrightarrow{x}$) 的Pareto front (PF*) 定义为:${\rm P}F{}^{*}:=\{\overrightarrow{u}=\overrightarrow{f}=(f{}_1(x),\cdots ,f{}_k(x))|x\in {\rm P}{}_s\}$。

自由搜索算法 (Free Search Algorithm, FS) [3]是一种性能优良的新的智能计算方法[4,5,6,7]。本文将其拓展到多目标优化领域, 并且在构建新算法时引入变异算子, 提出基于混合策略的多目标自由搜索算法 (Hybird Based Multi-objective Free Search Algorithm, HMOFS) 。最后, 通过数值实验验证了新算法的有效性。

2 基于混合策略的多目标自由搜索算法

2.1 算法描述

基于混合策略的多目标自由搜索算法的具体实现步骤如下:

Step1:参数设定

1.1 设置种群规模POP, 最大迭代次数G, 搜索步数T, 外部档案Archive大小, 最大最小搜索半径Rmin, Rmax等参数

Step2:外部存档控制

2.1 在决策空间随机产生初始种群POP[j];

2.2 计算初始种群的目标向量, 进行非劣比较;

2.3 调用外部存档控制子程序。

Step3:寻优过程

3.1 每个个体在其搜索半径通过寻优方程行走T步;

3.2 释放信息素, 计算灵敏度;

3.3 比较信息素和计算灵敏度, 得到搜索结果;

3.4 调用变异算子, 获得本次结果。

Step4:外部存档控制

4.1 计算种群的目标向量, 进行非劣比较;

4.2 调用外部存档控制子程序。

Step5:终止判断

若迭代次数不大于G, 则g=g+1, 调转至Step3, 否则转至Step6。

Step6:停止迭代, 将Archive内容输出。

2.2 选择机制

(1) 适应值分配

自由搜索算法的寻优方程如式 (2) 所示:

$\{\begin{array}{l}x{}_{tji}=x{}_{0ji}-\Delta x{}_{tji}+2\Delta x{}_{tji}\cdot random{}_{tji}(0,1)\\ \Delta x{}_{tji}=R{}_j\cdot (x{}_{i\text{m}\text{a}\text{x}}-x{}_{i\text{m}\text{i}\text{n}})\cdot random{}_{tji}(0,1)\end{array}(2)$

式中, randomtji (0, 1) 是 (0, 1) 内均匀分布的随机数;ximax和ximin是第i维变量的最大值和最小值;j代表第j只个体 (j=1, 2, …, m) ;Rj是第j只个体在搜索空间邻域搜索半径 (Rj∈[Rmin, Rmax]) ;t是搜索步 (walk) 中的当前小步 (t=1, 2, …, T) ;T是搜索步数。

在HMOFS中, 采用基于Pareto支配关系的适应值分配方法。对于要选择移动方向的个体j在搜索半径Rji内, 比较其各搜索步解的Pareto支配关系, 设个体在搜索半径Rji内的分布如图1所示, 其适应值分配见式 (3) 。

$fit{}_t=\{\begin{array}{l}\tau {}_0,x{}_i\text{为}\text{非}\text{可}\text{行}\text{解}\\ \tau {}_1,x{}_i\text{为}\text{可}\text{行}\text{解}‚\text{但}x{}_j\succ x{}_i\\ \tau {}_2,x{}_i\text{为}\text{可}\text{行}\text{解}‚\text{而}x{}_j\sim x{}_i\\ \tau {}_3,x{}_i\text{为}\text{可}\text{行}\text{解}‚\text{且}x{}_j\prec x{}_i\end{array}(3)$

(2) 基于信息素的选择机制

在HMOFS算法中, 信息素按照多目标适应值分配机制进行定义:

${\rm P}{}_j=\frac{fit{}_t}{\max (fit{}_j)}(4)$

式中, fitt=max (ftj) , ftj=f (xtji) , 而max (fitj) 是所有个体的当前最佳值。

而HMOFS算法中的灵敏度定义和单目标FS算法类似:

$\{\begin{array}{l}S{}_j=S{}_{\min }+\Delta S{}_j\\ \Delta S{}_j=(S{}_{\max }-S{}_{\min })\cdot random{}_j(0,1)\end{array}(5)$

式中, Smin、Smax是灵敏度的最小值和最大值, randomj (0, 1) 是均匀分布的随机数。

信息素的最小值和最大值分别为Pmin、Pmax。规定:Smin=Pmin, Smax=Pmax. 在一轮搜索结束后, 确定下一轮搜索的起始点。

$x^{\prime }{}_{0ji}=\{\begin{array}{l}{x}^{\prime }{}_{0ji},\\ x{}_{ji},\end{array}\begin{array}{l}{\rm P}{}_j<S{}_j\\ {\rm P}{}_j\ge S{}_j\end{array}(6)$

2.3 变异算子

采用多项式变异算子, 如式 (7) 所示:

$pop{}_{aj}=p{}_{aj}+(p{}_j^u-p{}_j^l)\delta {}_j(7)$

式中, puj, plj分别是决策空间第j维的上下边界, δj如式 (8) 计算。

$\delta {}_j=\{\begin{array}{cc}(2\mu ){}^{\frac{1}{\eta +1}}-1,& \mu <0.5\\ 1-[2(1-\mu )]{}^{\frac{1}{\eta +1}},& \mu \ge 0.5\end{array}(8)$

式中, μ为rand (0, 1) 的随机数, η为变异分布系数。

2.4 自适应策略

采用实时调整搜索半径的策略, 寻优过程中搜索半径R为搜索代数g的函数。R (g) 的调整策略见式 (9) :

$R{}_j(g)=R{}_{\min }+(R{}_{\max }-R{}_{\min })\exp (-\frac{g}{\rho })(9)$

2.5 外部存档机制

外部存档控制采用基于自适应网格的多样性保持策略[8], 其伪代码如下:

3 数值实验

为了测试HMOFS算法的有效性, 采用表1所列5个测试函数, 并将实验结果和MOPSO[9]、NSGA-II[10]、SPEA[11]、PAES[6]进行比较。对于每个测试函数, HMOFS算法独立运行10次, 其参数设置为:T=10, R (0) =1, η=20, pm=1/n, G=250。算法MOPSO、NSGA-II、SPEA、PAES的其它参数设置见文献[10]。

3.1 性能指标

采用文献[9]提出的两个指标来评价算法的性能。

(1) 收敛性指标γ

算法所得解与true Pareto-optimal front之间的最小Euclidean距离的平均值, 即为

$\gamma =\frac{1}{|{\rm H}|}{\displaystyle \sum _{h\in {\rm H}}\text{m}}\text{i}\text{n}\{\parallel h-h^{\prime }\parallel \},h^{\prime }\in {{\rm H}}^{\prime }(10)$

具体计算时, 在问题的true Pareto-optimal front上均匀地取一组点H′, 如取H′=500, h′为H′上分布均匀的一组解。H是算法所得的非劣最优目标域, 然后计算由算法获得的解h∈H与这些点h′之间距离的最小值, 所有这些最小值的平均值就是收敛性指标γ.

(2) 多样性指标Δ

$\Delta =\frac{d{}_f+d{}_l+{\displaystyle \sum _{i=1}^{{\rm N}-1}|}d{}_i-\overline{d}|}{d{}_f+d{}_l+({\rm N}-1)\overline{d}}(11)$

式中, di是近似Pareto front相邻两点间的Euclidean距离, $\overline{d}$为di的均值, df、dl分别为算法获得的边界解与true Pareto front边界点的Euclidean距离, N为近似Pareto front点的个数。

3.2 实验结果与讨论

表2、表3给出了本文算法和其它4钟算法收敛性指标和多样性指标的均值和方差 (每种算法的第一行为均值, 第二行为方差) 。从表2可见, HMOFS算法收敛性指标γ的均值优于MOPSO、 NSGA-II、 SPEA、 PAES。但其方差并非最优, 对于ZDT1、ZDT2和ZDT3, HMOFS列第二, MOPSO列第一; 对于ZDT4, HMOFS列第一; 对于ZDT6, SPEA列第一, HMOFS列第二。从表3可见, HMOFS算法多样性指标Δ的均值优于MOPSO、NSGA-II、SPEA、PAES, 而对于Δ指标的方差, HMOFS与其它算法性能相当。总体而言, HMOFS是一种性能优良的多目标进化算法, 这也可以从该算法获得的近似Pareto front得到直观反映, 见图2～图6。

4 结论

本文提出了基于混合策略的多目标自由搜索算法 (HMOFS) 。将HMOFS应用于5个测试函数, 并与算法MOPSO、NSGA-II、SPEA、PAES进行了对比分析。结果表明, HMOFS算法具有很好的收敛性和多样性, 是解决多目标优化问题的有效方法。

参考文献

[1]Kukkonen S, Deb K.Improved pruning of non-dominated solutions based on crowding distance forbi-objective optimization problems[C]//EvolutionaryComputation, 2006.CEC 2006.IEEE Congress on, 2006:1179~1186.

[2]Chen M R, Lu Y Z.A novel elitist multiobjectiveoptimization algorithm:Multiobjecti extremaloptimization[J].European journal of OperationalResearch, 2008, 188:637~651.

[3]Penev K, Littlefair G.Free search-A comparativeanalysis[J].Information Sciences, 2005, 172:173~193.

[4]周晖, 李丹美, 邵世煌.一种新的群集智能算法——自由搜索[J].东华大学学报 (自然科学版) , 2007:579~583.

[5]周晖, 李丹美, 邵世煌.自适应搜索优化算法[J].计算机科学, 2008, 35 (10) :188~191.

[6]周晖, 邵世煌.基于粗细粒交叉的搜索算法[J].控制与决策, 2008, 23 (9) :1068~1072.

[7]王则林, 罗永平, 陆建德.基于最近邻居选择、信息素动态更新和局部启发搜索的蚁群算法[J].南通大学学报 (自然科学版) , 2006, 5 (12) :71~76.

[8]Knowles J D, Corne D.Approximating the non-dominated front using the pareto archived evolutionstrategy[J].Evolutionary Computation, 2000, 8 (2) :149~172.

[9]Coello C A C, Pulido G T, Lechuga M S.Handlingmultiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computa-tion, 2004, 8 (3) :256~279.

[10]Deb K, et al.A fast and elitist multiobjectivegenetic algorithm:NSGA-II[J].IEEE Transac-tions on Evolutionary Computation, 2002, 6:182~197.

多方法混合算法 篇4

基于以上现状,笔者针对更多的机器进行并行多机批调度问题,并提出了改进的粒子群优化算法。很多学者也提出了各种改进粒子群算法来求解调度问题,但大多改进的算法都只是考虑粒子群算法易早熟和易陷入局部最优的问题,忽略了在改善这些问题的同时也应关注算法的局部搜索能力及收敛速度等。如文献[11]将遗传算法中的交叉策略引入到粒子群算法中,只是改善了粒子群易陷入局部最优的缺陷,并没有考虑提高算法的局部寻优能力和收敛速度。文献[12]在基本粒子群算法的基础上,提出了一种二维粒子表示方法,并采用粒子位置向量多次交换的局部搜索方法使粒子有效地跳出局部最优,但这种改进方法对算法本身的收敛速度有一定的削弱影响。因此,针对上述提到的各方面问题,在文献[13,14]的基础上,笔者综合了几种改进的方法, 提出了一种较全面的改进粒子群优化算法。*

1并行多机批调度问题描述

并行多机批调度是研究工件在多台功能相同的机器上的加工过程,每个工件仅需在某一台机器上加工一次。加工时间相同的工件可以组批, 可同时在一台机器上加工。因此,对具有相同到达时间的并行多机批调度问题可描述为: 有n个相互独立的工件,m台完全相同的机器,每个机器的最大容量为B,每个工件都有确定的加工时间ti( i =1,…,n) ,且均可由m台机器中的任一台完成加工任务。Ci表示工件i的完成时间,Cmax表示所有工件的最大完工时间,即Cmax= max{ Ci} ; F表示批调度的优化目标———最小化最大完工时间,即F = min Cmax。需要满足的约束条件为: 每台机器在每一时刻加工的工件个数不能超过B, 一旦工件在机器上加工就不能中断直至其被加工完成。

2改进粒子群算法的设计

针对粒子群算法易产生早熟收敛及局部寻优能力差等缺点,笔者提出了一种基于二阶振荡和自然选择的随机权重混合粒子群算法,用于求解函数优化问题。并采用一种基于批序列的编码方式,将其运用于求解并行多机批调度的优化问题上。

2.1粒子二阶振荡

针对标准粒子群优化算法(PSO)易陷入局部最优,缺少粒子的多样性,将二阶振荡引入粒子的速度公式中,从而提高粒子群体的多样性,改善算法的全局收敛性。其速度公式更新为:

式中c1、c2———粒子个体的加速权重系数和粒子群体的加速权重系数;

r1、r2———两个在[0,1]上均匀分布的随机数;

w———惯性权重因子;

ξ1、ξ2———随机数。

另外,

在算法前期取:

在算法后期取:

从速度公式中可以看出,此时的速度不仅与当前位置相关,还与微粒位置的变化有关。这样, 粒子可更快地向有利的方向运动,增强了全局和局部收敛性,加快了收敛速度。

2. 2权重与速度的变化

多数粒子群算法都是采用线性递减权重的方法,但该方法有时会使算法陷入局部最优,而采用随机分布的w可以克服这种局面。w的计算公式为:

式中N( 0,1) ———标准正态分布的随机数;

rand( 0,1) ———0 ~ 1之间的随机数;

u———随机权重平均值;

umax、umin———随机权重平均值的最大值和最小值;

σ ———随机权重的方差。

为了提高算法的性能,对最大速度进行了线性递减操作,公式如下:

式中max、min———最大速度的最大值和最小值;

M———最大迭代步数;

t———当前迭代步数;

vmax———最大速度。

在对算法进行上述改进的同时,笔者还引入了自然选择的思想来加快算法的收敛速度,即用群体中适应值最好的前1/N粒子的速度和位置替换群体中适应值最差的1/N粒子的速度和位置。N的取值不能过小也不能过大,若过小,无法达到粒子多样性和较好的全局性;若过大,粒子易陷入局部最优。经算法测试表明,N取5效果较好,即算例中只替换10%的粒子。

3粒子编码及算法实现

3. 1基于批序列的编码方法

基于批序列的编码方法有两个过程: 一是将工件分批; 二是将批分配给机。工件分批: 先将相同加工时间的工件放入一个批,再看批中工件数是否超过机器的最大容量Bmax,若没有,这些工件就分一个批,否则,将这些工件分成( Bmax- m + 1) 批( m表示具有相同加工时间的工件数) 。最后将那些没有重复的加工时间的工件单独成为一批,直到所有的工件都分配到各自的批中。批的分配: 将所有的批按加工时间的降序进行排列,整个粒子编码是面向批的,即通过对粒子位置进行排序,从而间接地对批进行重新排序。最后,按照重新排列的批顺序依次将批分配给空闲的机器。 例如对于6个工件,加工时间分别为{ 5,9,2,7,9, 5} ,首先进行分批,可分成{ ( 9,9) ,( 7) ,( 5,5) , ( 2) } 4批,再将这4批按工件序列进行编码,编码过程见表1。

位置按降序排列得: 0. 63、0. 55、0. 28、0. 09, 对应的批次是1、4、3、2。因此,批将按{ 1、4、3、2} 的顺序依次在空闲的机器上进行加工。

3. 2混合粒子群算法的步骤

按上述方法将基本粒子群优化算法进行改进,得到基于批序列编码的二阶振荡和自然选择的随机权重混合粒子群算法( BSNRPSO) ,其具体步骤如下:

a. 按照基于批序列的编码方式对工件进行分批,并按加工时间的降序进行排列,得到n个批数。

b. 设定粒子种群数量和最大迭代次数,对粒子群中的粒子xi和vi进行初始化,并对粒子按照基于批序列的编码方式进行编码,从而得到批的排序。

c. 按照工件次序和机器的空闲状态,将批分配到各机器上,同时计算该粒子的适应值,确定个体最优粒子和全局最优粒子。

d. 根据式( 6) 对粒子更新速度的最大值进行线性递减,以保证收敛。

e. 根据式( 1) 、( 2) 对粒子的速度和位置进行更新,算法前期取式( 3) 的值,后期则取式( 4) 的值。

f. 根据式( 5) 更新权重系数w。

g. 对每个粒子将其适应值与其经历过的最好位置作比较,如果较好,则将其作为当前的最好位置pbest。并比较当前所有pbest和gbest的值,更新gbest。

h. 将整个粒子群按适应值进行排序,用群体中最好的前1/N粒子的速度和位置替换最差的1 / N粒子的速度和位置,保持pbest和gbest不变。

i. 若满足迭代次数,则搜索停止,输出结果; 否则返回步骤d继续搜索。

4仿真计算及分析

笔者采用随机算法来获得算例,算例的规模按机器台数m、工件数目n和加工时间t3个标准来划分。机器台数有m1、m2、m3、m4四类问题,依次对应3、5、7、10台机器; 工件数目有J1、J2、J3、J4四类问题,依次对应20、50、100、150个工件; 工件加工时间有t1、t2两类问题,分别为[1,10]和[1, 20]分布。总共可产生32种不同的算例,每种算例记为mkJktj( k =1,2,3,4; j =1,2) 。例如m1J1t1表示3台机器、20个工件、加工时间服从[1,10] 的离散均匀分布的实例。在所有实例中,每台机器的最大容量Bmax均为5。

笔者对32种算例分别进行了实验,将基于工件序列编码的混合粒子群算法( JSNRPSO) 和基于批序列编码的BSNRPSO算法与传统的遗传算法( GA) 进行了对比。3种算法中,种群规模、最大迭代次数都一致,分别为m = 50、max gen = 100。 JSNRPSO算法与BSNRPSO算法的粒子群参数为: 自身学习因子c1= 2、全局学习因子c2= 2、权重平均最大值为0. 9,权重平均最小值为0. 4,权重方差为0. 2,淘汰概率为0. 1,速度限制在[-4, 4]之间,边界限制在[0,4]之间。每个实例均连续优化30次,仿真结果见表2。

从表2中的数据可以看出,就算法的最优值、 最差值、平均值和标准差进行比较,JSNRPSO算法比GA算法要好,而BSNRPSO算法比JSNRPSO算法的效果更好,尤其表现在并行机少、工件多的算例中。而对于并行机较多,工件较少的算例,3种算法的性能都差不多。因为此时问题的运算量低,传统的GA算法就能在迭代次数内找到最优解。在一些算例中,例如m4J4t2算例,BSNRPSO算法的标准差比JSNRPSO算法的标准差要大,这表明利用BSNRPSO算法得到的数据波动范围大, 但BSNRPSO算法的最优值、最差值、平均值都比JSNRPSO算法的要好很多,这表明BSNRPSO算法在处理多工件时,能更快地跳出局部最优,增加种群的多样性,快速找到更好的解,具有更强的寻优能力。

为了更好地比较3种算法性能的优劣,采用相对改进率这一指标来评价,改进算法U相对GA算法的改进率为:

式( 7) 中U代表JSNRPSO算法和BSNRPSO算法。改进率的结果见表3。为了更直观地比较两种算法的优越性,绘制了对应的算法平均值改进率,如图1所示,横轴代表工件不同的加工情况,纵轴代表机器台数不同情况下对应的相同算例的改进率的平均值。

由图1可知,JSNRPSO算法相对GA算法有一定的改进,但BSNRPSO算法的改进度更大,尤其表现在大规模的算例中,如多工件且加工时间长的情况。这说明BSNRPSO算法更能胜任复杂的生产调度环境。在工件数目少的情况下,如20个工件,运算量比较小,传统的GA算法就能找到较好的解,改进的空间不大。在表3中,m4J3t1算例,BSNRPSO算法的平均值改进率没有JSNRPSO算法的好,但利用BSNRPSO算法找到的最优解还是比JSNRPSO算法找到的最优解要好。

5结束语

针对粒子群算法本身的缺点提出了改进的算法,笔者将这种新的算法运用于求解并行多机批调度的问题中。通过实验验证,这种改进的算法对求解调度问题是有效的。并且在改进的算法中采用基于批序列的编码,这使得进一步改进后的算法更适合求解大规模的并行机批调度问题,对实际的工业调度具有一定的指导意义。

摘要：针对调度目标为最小化最大完工时间的并行多机批调度问题,提出了改进的基于批序列编码的混合粒子群算法。在基本粒子群算法的基础上,引入了学习因子二阶振荡、随机权重、最大速度线性递减及自然选择等方法,改善了算法本身易陷入局部最优及早熟收敛等问题,并解决了因引入新的方法 造成算法收敛速度慢及寻优能力差等问题。由仿真结果可知:改进的算法均优于常规的粒子群算法,且根据批序列编码的改进算法更优于常规基于工件序列编码的改进算法。

多方法混合算法 篇5

多工序订单生产排序计划问题(以下简称订单排序),是一类典型的组合优化问题,描述的是在工厂有限处理能力的前提下,如何安排大量订单的生产顺序,以达到利润最大化的目的。其经典描述如下:

设:一个工厂接收到n个客户订单,对于其中任何订单i,其处理时间Ti、交货期di以及销售ri收益都是已知的。由于生产能力的限制,某些订单可能需要延迟交货,对于延迟交货的订单对应有与延迟时间成正相关的处罚(或者销售价格折扣),而提前完成任务没有任何奖励。决策的目标就是寻找一个订单排序,以最大化企业的收益。

订单排序问题具有NP—HARD计算复杂性[1],混合整数规划[2]被用来解决此类问题。近年来出现的一些启发式算法如:模拟退火算法[3]、遗传算法[4]、神经网络[5]、禁忌搜索算法[6]以及蚁群算法[7]为解决更大规模的此类问题提供了新的途径。蚁群算法是近些年新出现的一种从群体智能演变而来的新算法,在解决大规模组合优化问题上显示了强大的实力。模拟退火算法也在求解此类问题时也有良好的表现。现有的有关订单排序的研究文献中,大多假定订单的处理过程是单工序的[5,6,7],而这与企业的多工序制造是不相符合的。本文将基于多处理工序订单排序模型,应用将蚁群算法(ACA)和模拟退火算法(SA)结合的混合蚁群算法(HACA)进行求解,并对算法的有效性和鲁棒性进行分析。

1 问题描述与数学建模

订单生产有多道工序,所有订单需要在这多道工序顺序处理完毕后才能交付客户。订单数目,每个订单交货期、收益以及在各道工序的处理时间是已知的。订单的加工工序遵循严格的串行顺序,每个工序的设备在同一时刻不能同时完成不同的订单,在同一时刻,同一订单的各个工序不能同时进行。当订单的完工时间晚于交货期时,企业要承担延迟成本。延迟成本和延迟时间正相关,不同的订单有不同的延迟惩罚系数,而工厂要完成所有的订单。

基于上文对多工序订单生产计划的描述,现转换为数学模型,首先对参数和变量进行说明:

n:表示工厂在某时期接到的订单数目;

i:表示订单序号;

m:表示订单处理工序的数目;

j:表示工序序号;

di:表示订单的交货时间;

ri:表示订单i的期望收益;

wi:表示订单i延迟的惩罚系数;

Tij:表示订单i在工序的处理时间;

Xij:表示订单i的在工序完成时间;

S:表示n个订单的可能的一个排列;

S(k):表示在排列S中第k个被处理的订单号;

f:表示企业的利润函数;

cost:表示在S中所有库存持有成本和惩罚成本之和。

该问题的数学模型可描述为:

约束条件:

目标函数式(1)表示企业利润,是期望收益减去延迟交货成本,+表示仅取正数;约束条件式(2)表示在工序处排在订单i前面的订单必须完成;约束条件式(3)表示订单i在进行j工序之前,j-1工序也必须已经完成;约束条件式(4)表示第一个加工的订单第一个工序完成时间要不小于其加工时间。

2 算法介绍

2.1 蚁群算法(ACA)

蚁群算法是20世纪90年代由意大利学者M-Dorigo等人首先提出的一种新型的模拟进化算法,称为蚁群算法(ant colony algorithm,ACA)。蚁群算法的基本原理是:当蚂蚁在搜索食物源的过程当中,会在其所走过的路径上释放一种特殊的分泌物——信息素,一定范围内的蚂蚁在寻找食物的过程中都会受到这种信息素的影响。当某些路径上走过的蚂蚁越来越多,留下的这种信息素也越多,以致后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的吸引强度。利用这种正反馈机制,最终蚂蚁群体能够在食物源与蚁巢之间找到一条最短的最优路径。

蚁群算法的步骤可简要表述为:(1)设置所有参数,信息素初始化;(2)每只蚂蚁根据状态转移方程建立一个完整的解,状态转移方程主要取决于信息素和能见度因子;(3)更新信息素。重复后两个过程直到满足条件为止。

2.2 模拟退火算法(SA)

模拟退火算法思想最早由Metropolis[8]在1953年提出,Kirkpatrick[9]在1983年成功地应用于组合优化问题。模拟退火算法的基本原理是:金属或玻璃加热后逐渐冷却,其物理性质(稳定性)就会发生改变,这其实是分子重新以一定的结构进行了排列。对冷却过程加以控制,从而获得最好的物理特性。

模拟退火算法步骤可简要表述为:(1)随机给一个初始解;(2)按照一定的方式搜寻初始解的相邻解,并按照某一状态转移方程判断此相邻解是否被接受;(3)重复过程(2)直到温度降低到指定的阀值。

2.3 混合蚁群算法(HACA)

研究表明,蚁群算法开始寻优速度很快,随着迭代次数的增加,其发现更好解的速度变慢,最终收敛。虽然有很多学者研究通过对信息素更新等改进来克服这个缺陷,但要付出增加大量迭代次数和运算时间的代价。而模拟退火算法迭代初期寻优速度很慢,随着温度的降低,其发现更好解的速度变快,最终收敛。加快退火速度和降低初始温度能改善初期寻优慢的问题,但要付出搜寻结果变差的代价。混合蚁群算法的思想就是将蚁群算法和模拟退火算法结合起来,充分利用两种算法的优点。

混合蚁群算法的步骤可简要表述为:(1)适当减少蚁群算法的迭代次数,并取得某一最好解;(2)以蚁群算法取得最好解作为模拟退火算法的初始解进行运算,并适当降低初始温度和加快退火速度;(3)满足某一条件,停止运算,输出结果。

3 混合蚁群算法的求解策略

在用于订单排序问题的混合蚁群算法中,每个人工蚂蚁都是具有下述特征的智能体:(1)当它选择执行完订单i再去执行订单b时,它会在连接(i,b)上留下信息素τkib;(2)它以一定的概率Pkib进行状态转移(从订单i转移到订单b),该概率是启发式信息ηib和信息素量τib的函数;(3)在构造一个完整的解时,已经被处理的订单被加以禁忌,如此重复直到所有订单都被处理完毕;(4)重复以上步骤,在蚁群收敛时,输出当前最好解的蚂蚁参数;(5)以最好解蚂蚁的参数,进行模拟退火的运算,以优化次最好解;(6)达到某一条件,输出运算结果。

按照以上步骤,对其中涉及到的一些参数作如下定义:

相应地,能见度因子ηib表示为:

式(5)和式(6)中,μ、λ为正的可调系数μ燮1,λ叟1。

信息素的更新方程定义为:

式(7)、式(8)和式(9)中,ρ为非负可调系数,表示信息素的持久性,且ρ燮1;Δτib表示蚂蚁转移后的信息素的增加。H为含有(i,b)的解的集合,Q为正的可调系数;如果H为空集,那么Δτib=0;这说明只有蚂蚁经过时才会有信息素的增强。

状态转移方程表示为:

式(10)中,α,β为非负的可调系数,分别表示蚂蚁k在从订单i在转移到订单b时的信息素τib的相对重要性和能见度因子ηib的相对重要性。

初始温度的确定:

式(11)中,To为模拟退火初始温度,costmax和costmin分别表示蚁群算法中所输出的最好解和最差解。

解的接受概率:

式(12)、式(13)和式(14)中,γ为可调系数,0<γ<1,T为温度。

于是,伪代码可以写为:

(1)初始化过程。

参数初始化;

读入订单数据,虚拟一个初始订单,除其序号为1外其他参数均为0;

Nc:=1;/迭代次数置为1/

τib:=A;/信息素强度置为某一相等的较小数值/

Δτib=A;/初始信息素增量置为零/

ηib=1/Δdib;/读入能见度因子,参见式(5)和式(6)/

Sk=准;/蚂蚁k的禁忌表初始为空集/

读入虚拟订单,设;l:=;/l为禁忌表中元素索引/

for k:=1 to ant_num do/ant_num表示蚂蚁数目/

(2)重复到禁忌表满为止。

设置;l:=l+1

蚂蚁k以Pkib选择下个订单b;/见式(10)/S(l)=b;/订单j被列入到禁忌表中/

(3)计算每个蚂蚁的各个订单的完工时间,收益和额外成本。

计算完工时间Xij;/约束条件参见式(2)式(3)

计算企业利润f;/计算公式参见式(1)/

计算企业额外成本cost;/计算公式参见式(9)/(4)更新信息素。

(5)记录到目前为止的最优利润及其相应的排序。

if Nc<Nc_max/不满足终止条件/

清空所有禁忌表;

设Nc:=Nc+1;/迭代次数增加1/

Δτib=0;/清空信息素增量/返回步骤(2);/循环/

输出最好解和最差解;(6)参数初始化。

温度阀值,退火速度等/

初始温度To确定;/参见式(11)/T=To;/当前温度置于最高温度/

(7)for i:=1 to num do/num为某一数值/

进行邻域搜索;

判断搜索解是否接受;/判断条件见式(13)/

(8)记录目前解和相应的排序。

if T>Tf/温度没有达到阀值/

Nc:=Nc+1;/迭代次数增加1/

T=T*γ;/温度更新/

返回步骤(6);/循环/

输出最好利润和相应的订单排序。

4 算例比较

取如下几组(n,m)的随机参数订单进行比较:(10,3)、(50,3)、(50,4)、(100,4)。(10,3)表示订单数为10,工序数为3,其他类推。

运行环境为windows XP系统,MATLAB编程环境,CPU主频为1.5GHZ的笔记本电脑,采用三种计算方法进行比较分析,其参数分别为:(1)模拟退火算法γ=0.95,end T=0.01,L=3*n;(2)蚁群算法:ant_num=1.5*n,μ=0.5,λ=2,α=1,β=2,ρ=0.8,Q=15*n,N=50;(3)混合蚁群算法:ant_num=1.5*n,μ=0.5,λ=2,α=1,β=2,ρ=0.8,Q=15*n,N=50,γ=0.8,end T=0.01,L=3*n。都重复10次求解,求解结果表1~表4。

从统计指标来看,混合蚁群算在四次求解过程所有的指标值都是最好的。而且随着订单数目和工序数目的增加,混合蚁群算法相比其他两个算法更占优势,因而该算法具有良好的鲁棒性。由于三种算法在不同的订单与工序的组合中的寻优过程类似,因而只给出三种算法在(50,3)的最好解的进化图,见图1、图2、图3。

模拟退火算法中可接受解在150代开始收敛,蚁群算法在10代开始就陷入局部最优,而混合蚁群算法在30代开始收敛,从此可以看出混合蚁群算法综合了模拟退火算法和蚁群算法的优点。

5 结束语

订单排序是生产管理中常见的决策问题,也得到了广泛的理论研究和实践应用。本文尝试用混合蚁群算法对多工序的订单排序进行了求解,并通过和模拟退火算法、蚁群算法的横向比较,以及不同数目订单和工序组合的纵向比较,证明了混合蚁群算法在求解此类问题的有效性和良好的鲁棒性。其他的启发式算法,例如遗传算法、粒子群算法、禁忌搜索算法等等均可用于此种模型的求解。融合这些算法或者改进设计启发式算法来求解多工序订单排序问题是一个值得进一步研究的问题。

参考文献

[1]Ghosh J B.Job selection in a heavily loaded shop[J].Computers and Operation Research,1997,24(2),141-145.

[2]Simone Zanoni,Lucio Zavanella.Model and analysis of integrated production-inventory system:The case of steel production[J].International Journal of Production Economics,2005,93/94,197-205.

[3]肖依永、常文兵、张人千:《基于模拟退火算法的多节点订单排序模型》[J];《计算机应用研究》2009(2):460-463。

[4]Rubin P A,Ragatz G L.Scheduling in sequence dependent setup environment with genetic search[J].Computers and Operations Research,1995,22,85-99.

[5]Sabuncuoglu Gurgun.A neural network model for scheduling problems[J].European Journal of Operational Research,1996,93,288-299.

[6]Franca P M,Gendreau M,Laporte G,Muller F M.A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent of setup time[J].International Journal of Production Economics,1996,43,79-89.

[7]Gagne C,Price W L,Gravel M.Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence dependent setup time[J].Journal of the Operations Research Society,2002,53,895-906.

[8]Metropolis N,Rosenbluth A.Equation of state calculations by fast computing machines[J].Journal of Chemical Physics,1953,21,1087-1092.

多方法混合算法 篇6

关键词：微电网,优化,α约束支配,进化算法,多属性决策,模型

0引言

随着节能减排的需求逐渐增强,分布式发电DG (Distributed Generation)的利用率也逐渐增加 ,由小容量分布式电源形成的微电网研究也逐渐深入[1,2]微电网将微型燃气轮机、燃料电池、光伏电源和风力发电机等分布式电源通过电力电子接口等方式联合在一起,为负荷端提供电能和热能。 根据微电网与常规配电网的连接与否,将其划分为并网、孤岛2种运行模式[3,4]。

微电网的经济运行与优化调度一直是国内外研究的热点,微电网运行优化问题的研究中,优化目标多种多样,如电能质量等技术目标、运行成本等经济目标、排污成本等环境目标,其中经济目标和环境目标是目前微电网运行所考虑的主要优化指标[5,6,7],鉴于微电网内基于化石燃料的分布式电源运行时会产生一定的碳排放,且排放量与其出力密切相关,同时基于国家“十二五”规划对低碳经济更为重视,本文将以运行成本和CO2排放量最小化为目标构建微电网多目标优化运行模型。

微电网的多目标优化运行是一个复杂的带多种等式约束和不等式约束条件的多目标优化问题,采用多目标优化算法求解其帕累托(Pareto)最优解集是一种常用手段[8]。 然而如何在优化算法中方便快捷地处理这些约束条件一直是各学者所致力研究的难题,常用的约束处理方法有罚函数法及多目标法等[9,10],这些方法都存在不足之处。 罚函数法为个体加入惩罚项,将约束问题简化成无约束问题,但惩罚项的设计多种多样,很难找到一个确切方案;多目标法将个体违反约束条件的程度作为优化指标,增加了优化问题目标函数的个数,计算更加复杂。 随着约束条件数量的增加,传统的约束处理方法复杂度也大幅增加。 因此,本文提出一种新型的 α 约束支配排 序混合进 化算法 α-CDSHEA (α-Constrain Dominant Sorting Hybrid Evolution Algorithm),可显著提高约束处理效率,降低算法的复杂度。 同时,为有效利用种群的宏观分布信息和个体信息,保持种群多样性,提高算法的收敛性和寻优速度,提出一种微分进化算法DEA(Differential Evolution Algorithm以及分布估计算法EDA(Estimation of Distribution Algorithm)相融合的混合进化算法 。 最后,通过分类逼近理 想解的排 序TOPSIS (Technique for Orde Preference by Similarity to an Ideal Solution)方法对算法得到的Pareto最优解集进行多目标决策,以获得最优折中解。

本文将以一个含光伏PV(Photo Voltaic)、风机WT (Wind Turbine)、微型燃气轮机MT(Micro Turbine) 燃料电池FC(Fuel Cell)以及负荷的微电网为算例分别用 α-CDSHEA、采用常规罚函数约束处理方法的非劣 排序微分 进化算法NSDEA (Non-dominate Sorting Differential Evolution Algorithm)和动态加权遗传算法(GA)进行求解,对比各自得到的Pareto最优前沿和运行时间,测试本文提出算法的有效性。

1微电网运行数学模型

1.1分布式电源模型

1.1.1微型燃气轮机模型

微型燃气轮机运行时的耗量特性[11]可描述为:

其中,PMT(t)为微型燃气轮机t时刻的功率 (k W);Δt为微型燃气轮机运行时间(h);ηMT(t)为微型燃气轮机t时刻发电效率;RLHVf为天然气低位热值(k W·h/m3); VMT(t)为 Δt运行时间内微型燃气轮机消耗的天然气量(m3)。

1.1.2燃料电池模型

燃料电池的耗能特性与微型燃气轮机类似[11], 可描述为:

式中各参数的意义参照式(1)。

光伏和风机的功率外特性模型分别参照文献 [12]和文献[13]。

1.2优化运行目标函数

1.2.1运行成本目标函数

运行成本目标函数F1包括投资折旧成本、运行维护成本、燃料成本以及微电网与外网的交互成本[14,15]:

其中,CDP(t)、COM(t)、Cfuel(t)、Cgrid(t) 分别为t时刻各DG的投资折旧成本 、运行维护成本 、燃料成本以及微电网向外网的购电成本;NG为系统DG总数;Caz,i为第i个DG的单位容量安装成本;Pi N为第i个DG的装机容量;r为年利率;ni为第i个DG的使用寿命;KOM,i为第i个DG的单位电量运行维护成本系数;Pi(t)为第i个DG在t时刻的有功输出 ;fi为第i个DG的燃料成本函数;CF为天然气的价格;CE(t)为t时刻微电网向外网购电的实时电价 ;Pgrid(t)为t时刻微电网向外网的购电量。

1.2.2CO2排放量目标函数

CO2排放量目标函数F2为[16]:

其中,ki为第i个DG的CO2排放系数;kgrid为配电网的CO2排放系数。

1.3约束条件

a. 潮流方程约束:

其中,Pfs、Qfs分别为节点f的有功和无功注入量;UfUg分别为节点f和g的电压;Gfg、Bfg、θfg分别为节点f和g之间的电导、电纳和相角差;g  f为与节点f相连的节点。

b. 功率平衡约束:

其中,Pd(t)为实时有功负荷;Ploss(t)为实时有功损耗。

c. 节点电压约束:

其中,Ui,min、Ui,max分别为节点i的最小、最大电压允许值;N为系统节点数。

d. 微电源的有功出力约束:

其中,Pi,min、Pi,max分别为第i个DG有功功率的最小、最大值。

e. 微电网与外网允许交互的传输功率约束 :

其中,Pgrid,max、Qgrid,max分别为微电网与外网允许交互的最大有功和无功功率。

f. CO2排放约束:

其中,Lmax为该地区CO2允许排放的最大限值。

2α-CDSHEA

2.1α约束支配排序

Takahama提出了 α 约束处理方法[17],α 约束方法将种群个体符合约束条件的程度数值化,提出了约束水平度的概念。 用 μ(x)表示个体x的约束水平度,且 μ(x) [0,1]。 μ(x)越大表示个体x属于可行解的概率越大,若 μ(x)=1,则表示个体x属于可行解。 约束水平度 μ(x)的值可由下式计算得出:

其中,hi(x)、gj(x) 分别表示个体的等式约束和不等式约束值;bi、bj分别为种群中不可行解对应的等式约束和不等式约束的平均值。

在得到个体x对应各约束条件的约束水平度之后,定义个体x的总约束水平度为:

从而定义 α 约束水平截集为:

对于个体x,如果xAα,则称之为满足 α 约束的个体。

由此可定义如下的 α 约束支配关系(用fα表示):

式(17)中,若个体x、y均满足 α 约束,即x,y∈Aα, 或者个体x、y的 α 约束水平度相等,即 μ(x)=μ(y),那么目标函数值f(x)、f(y)决定它们之间的支配关系; 否则,α 约束水平度 μ(x)、μ(y)决定它们之间的支配关系。

式(16)中的约束判定量 α 是一个时变量,可表示为 α(T),它随着进化代数T在0~1之间逐渐增加。 其初值 α(0)的大小由优化问题的可行域占全部搜索空间的比例决定,比例越大,α(0)可取的值越大。 α(T)可由下式计算得出:

其中,β 为 α 的控制参数,β [0,1],根据文献[17], 本文取 β=0.03。 由式(18)可以看出,在 β 的控制下, α 的值随着进化代数T增大逐渐增大到1,即 α 约束条件越来越严格,代表解集逐渐向可行域收敛。

将 α 约束支配关系作为主选择排序机制并以传统的非劣排序方法[18]为辅助排序机制引入多目标优化算法。 在算法种群进化过程中,父代和子代种群按以下原则进行选择和种群更新操作。

a. 父代群体P (T) 和子代种群P (T +1) 构成集合Q(T),将Q(T)分成满足 α 约束的子集Qf和不满足 α 约束的子集Qinf。

b. 将Qf中的个体进行 α 约束支配排序分级,同一级别的个体按非劣排序方法进行排序;将Qinf中的个体按 α 约束水平度大小进行排序。

c. 将Qinf中的个体按顺序排在Qf中的个体之后更新集合Q(T),按照种群规模M在Q(T)中选择前M位的个体更新子代种群P(T+1)。

设最优前沿的个体集合为Bbest(Bbest最终输出即为Pareto最优解集),初始Bbest为空集,在产生初始种群并进行种群排序后,将满足 α 约束的个体储存其中。 种群进化过程中,考察Qf中满足 α 约束的全部个体xi与Bbest中的全部个体yj之间的 α 约束支配关系,Bbest的更新操作按以下原则进行:如果xi被yj支配,Bbest集合不变;如果xi支配yj,则从Bbest中删去yj并加入xi,即Bbest= (Bbest- yj)∪xi。

Bbest的规模如果超过预定值,则按非劣排序方法对其中个体进行排序,删去排序靠后的个体以保持其规模恒定。

2.2混合进化算法

文献[18]提出NSDEA,它是一种基于DEA的多目标优化算法。 DEA是一种非常优秀的进化优化算法,具有结构简单、鲁棒性强、收敛性好、易于与其他进化算法混合等特点[19]。 至今为止,DEA已发展出多种进化策略[20]。 本文采用的DE / best / 2 / bi策略简述如下。

a. 变异。

在种群进化到第T代时,通过下式变异产生新个体:

其中,vi,T为变异得到的新个体;xbest,T为全局最优个体;F为缩放因子,F  (0,1);xr1,T、xr2,T、xr3,T、xr4,T为随机抽取的4个个体。

b. 交叉。

进化群体Xi,T+1和变异之后的群体Vi,T+1通过下式进行交叉产生新个体:

其中,uj,i,T+1为交叉位;k为随机整数;rand(0,1)为随机产生的0~1之间的数;δCR为交叉概率。

然而,上述DEA在进化过程中,种群会较快失去个体多样性而导致变异差分项趋于0,使得寻优停滞或陷入局部搜索。 EDA是一种基于统计学原理的新型进化算法[21],不同于传统进化算法采用交叉、变异等进化手段,EDA通过建立概率模型描述解集在搜索空间的分布信息,然后采用随机采样从群体宏观角度进化产生子代,能充分利用群体的智能信 息,具有较强的全局搜索能力。 为此本文拟将EDA基于整个种群统计信息的宏观层面控制种群进化的模式与DEA基于个体变异、交叉的传统进化模式相融合,提出一种混合进化算法,可有效加强算法的种群多样性,提高其收敛速度并防止早熟收敛。 本文采用基于高斯分布建模的连续域EDA,其建模原理简述如下。

用一个概率向量pT(x)来表示第T代种群的概率分布,pT(x)=(pT(x1),pT(x2),…,pT(xM))。 从其中选择m个优势个体,本文取m = M / 2,假设其满足以下高斯分布:

其中,N(xi; μiT; σiT)为关于xi、 μiT、σiT的高斯分布。 各代的均值 μi和方差 σi2估计如下:

其中,xiT,1、xiT,2、…、xiT,m为第T代种群的m个优势个体。

3算法求解步骤

3.1Pareto最优解集

本文提出的 α-CDSHEA流程如图1所示。

综上所述,α-CDSHEA的Pareto最优解求解步骤如下。

a. 种群初始化 。 进化代数T = 0, 最优前沿以一天24 h各时段的微型燃气轮机 、 燃料电池有功出力和微电网向电网的实时购电量为个体变量,随机产生初始种群P(T),计算种群的适应度f和针对各约束条件的约束值[gj(x) hi(x)],然后计算个体的 α 约束水平度进而得到个体的总 α 约束水平度。

b. 排序并选择优势个体。 对种群进行 α 约束支配排序和非劣支配排序,选择前一半个体形成优势种群,并更新最优前沿集合Bbest。

c. 种群进化产生子代 。 根据优势种群建立概率分布模型,分别用DEA和EDA进化产生子代种群P1(T + 1)和P2(T + 1),计算子代种群的适应度f和约束值[gj(x) hi(x)],并计算个体的 α 约束水平度和总 α 约束水平度。

d. 选择和种群更新 。 依据2.1节中的操作原则更新种群P(T+1)和最优前沿集合Bbest。

e. 判断 。 若达到进化代数要求且最优前沿集合Bbest达到预定规模,进入下一步;否则T =T +1,转步骤b。

f. 输出最优前沿集合Bbest中的个体为最终的Pareto最优解。

3.2最优折中解

为挑选最优折中解,决策者需根据偏好对Paret最优解集 进行筛选 排序 。 Hwang和Yoon提出的TOPSIS方法[22]通过计算Pareto最优解集和理想解的距离,使其与理想解距离最近,并且与负理想解距离最远,判断解集的优劣并排序。 以r个目标、l个解为例,其排序流程如下:

a. 对原始决策矩阵X =[xij]l ×r进行向量规范化, 得到规范化决策矩阵Y=[yij]l×r;

b. 构成加权规范化决策矩阵Z = [zij]l×r,其中zij= τjyij,τ=[τ1,τ2,…,τr]T为决策者给定的加权向量;

c. 确定正理想解Z+和负理想解Z-;

d. 计算各个解到正理想点的距离di+和到负理想点的距离di-;

e. 计算各个解的综合评价指数, 进而排序 。

其中的加权向量τ 可采用客观赋权的变异系数法[23]确定 , 其流程如下 : 计算各目标的均值和方差计算各目标的变异系数将变异系数归一化 , 可得各目标的加权系数

4算例分析

4.1微电网结构与参数

本文以一个含光伏发电、风力发电、微型燃气轮机、燃料电池4种微源的微电网系统为例[24],如图2所示,馈线L1为民用负荷(功率因数为0.85),馈线L2、 L3分别为工业负荷和商业负荷(功率因数为0.90)。

本文作如下假设:在单位时间间隔内,各微源的有功和无功出力恒定、负荷需求恒定、微电网与主网间的交互功率恒定且交互电价维持恒定。 本文取单位时间间隔为1 h。

微电网中各线路参数以及各节点最大负荷如表1所示,表中R、X和Smax分别为线路电阻、电抗和末节点最大负荷。 实时的民用负荷、工业负荷、商业负荷占节点最大负荷的百分比如图3所示。 微电网与外网允 许传输的 最大有功 和无功功 率分别设 为75 k W和46.48 kvar(传输线功率因数0.85),实时电价见文献[25],天然气价格为3元 / m3,各DG的运行成本系数、CO2的排放系数以及某地区CO2的排放限值见文献[26],微电网中各DG的参数见表2。

光伏和风机均为不可控的分布式电源,采用最大功率跟踪输出模型,且由于光伏、风机发电成本低和污染物排放率低,本文假设其为零运行成本、零排放。 根据某日的光照和风力强度,假定光伏和风机的预测日小时出力如图4所示。

4.2优化结果

为了证明本文算法在处理复杂约束多目标优化问题上的优越性,分别用 α-CDSHEA、采用常规罚函数约束处理方法的NSDEA以及动态加权遗传算法对本文算例进行求解,得到该日微电网运行成本和CO2排放量的Pareto最优解集。 3种算法的种群规模均设为100,α-CDSHEA和NSDEA的微分进化缩放因子均为0.85,交叉概率为0.5,α-CDSHEA的 α 初值设为0.5。 本文中遗 传算法直 接调用现 成的MATLAB遗传算法工具箱(GAOT)[27],由于该软件包不能直接求解多目标优化的Pareto前沿,为此需对双目标函数进行加权使之转化成单目标函数,鉴于加权值难以确定,可通过在0~1之间均匀取100个动态权值构造动态加权遗传算法,以间接获得Pareto前沿。 本文运行算法硬件环境的CPU为Intel Core i53317 @ 1.70 GHz 1.70 GHz , 仿真环境为MATLAB R2013a。 以上3种算法各自运行100代得到的优化曲线如图5所示,运行时间如表3所示。

图5中曲线对比可以看出,α-CDSHEA比采用常规罚 函数约束 处理方法 的NSDEA最终得到 的Pareto前沿分布更加均匀 、解集更加全面 。 而采用GAOT通过动态加权函数优化得到的解集明显劣于 α-CDSHEA,与真正的Pareto最优解集相差甚远。 另外,由于采用GAOT求解多目标优化问题需要不断动态改变权值进行单目标优化,因此表3中GAOT运行时间远大于 α-CDSHEA和NSDEA。 而 α-CDSHEA所需要的运行求解时间略小于NSDEA,实际上由于 α-CDSHEA是融合了DEA与EDA这2种不同算法机制的混合算法,其理论运行时间应远大于NSDEA,但本文提出的约束处理方法有效降低了算法的复杂度,导致最终运行时间略小。

为进一步 比较 α-CDSHEA和NSDEA在得到Pareto解集时在收敛速度上的优劣 ,取各自运行25代时的优化曲线对比,如图6所示。

由图6可知,运行至25代时,α-CDSHEA已基本收敛,而NSDEA还远未达到收敛,可见 α-CDSHEA的收敛速度要高于NSDEA,说明引进 α 约束处理方式和混合进化算法是有效、可行的。

经过对 α-CDSHEA优化得到的Pareto前沿进行最终多目标决策优选,可得到该日最终运行成本和CO2排放量分别为4 101.2元和68.236 8 kg,对应的该日微型燃气轮机、燃料电池的有功出力及微电网系统与电网的交互购电优化结果如图7所示。

为保证微电网的独立性,当网内DG输出足够满足负荷需求时,不向外网购电,此时相当于孤岛运行;当网内DG输出无法满足负荷需求时,在允许传输限值范围内向外网购电,此时相当于并网运行。 从图7中可以看出,01:00 — 08:00时微型燃气轮机和燃料电池的出力足够满足网内负荷安全有效运行不需要向外网购电;09 : 00 — 14 : 00、16 : 00 — 19 : 00 22 : 00 — 24 : 00,微型燃气轮机和燃料电池的出力满足不了网内负荷需求,故需要向外网购电 ;15:00 19:00 — 21:00, 微型燃气轮机 、 燃料电池的出力配合向外网购电仍然不能满足网内负荷需求,存在有功缺额,此时微型燃气轮机和燃料电池为最大功率输出,向外网所购电量也达到传输上限,此时为保证微电网安全有效运行,应适当切除民用负荷。 微电网的无功负荷也由微型燃气轮机和燃料电池共同负担,并配合少量外网提供的无功出力。

5结论

多方法混合算法 篇7

在全球经济一体化的进程中,越来越多的

企业参与全球化生产网络中,与其他企业建立合作关系,分工合作地进行生产与贸易,实现互利共赢,特别是在BTO生产环境下,大量零组件需要外部协作。实现这种协作性生产的一种委托代理加工方式称为OEM(original equipment manufacturing),在这种协作生产方式中,品牌企业如何合理分配订单给不同的代工企业(OEM供应商)进行生产,即生产任务分配问题,就成为这种生产方式的主要决策。

在此类任务分配问题中,一方面每个订单的交货期和售价各不相同;另一方面,承担这些订单的供应商,其加工成本及加工时间也是各不相同的。针对这些情况,为找到一个最优的订单分配方案,就需要考虑成本收益、服务水平等目标因素,以最终达到整体的订单效益最大化。这种多目标分配问题基本模型形式可描述为

min F(x)=(α1f1(x),α2f2(x),…,αnfn(x)) (1)

s.t. x∈S

其中,fi(x)(i=1,2,…,n)为目标分配所要满足并追求的各维度目标(包括成本、时间等)函数;S为多维可行空间[1]。每个目标函数可根据实际情况按一定权重加权评估,其中αi(i=1,2,…,n)为各权重,且满足∑αi=1。

对于订单/任务分配问题,传统的方法包括层次分析法、模糊综合分析法等,考量的评价目标也各不相同。国内外已有学者进行了研究,如考虑成本最低及长期能力,并基于AHP与目标规划方法对外包商选择和任务分配的探索[2];研究制定最小生产时间为目标的任务优化分配策略[3];此外还有从多代理协商合同设计角度确定任务分配机制的研究[4];文献[5,6]分别利用改进遗传算法、灰色理论求解设计优化的任务分配策略。这些研究主要集中在任务分配目标及评价因素选择、新方法应用研究及信息化支持[7]等方面。

与其他研究方法不同,本文采用混合蚁群算法进行研究。蚁群算法(ant colony algorithm,ACA)首先应用于解决经典的TSP问题[8],随后因其自身的并行性、较好的寻优能力等特性在工程优化、流程规划、机器智能、数据挖掘等领域取得了成功的应用。文献[1]应用基本的蚁群算法初步研究了多目标优化问题,并从Pareto改进及种群多样化等方面对算法进行了改进。文献[9]尝试利用蚁群算法解决与多目标任务分配问题相类似的武器分配问题(WTA),在求解离散整数规划上,蚁群算法因其自身的并行搜索机制而具有良好的寻优能力,但基本的蚁群算法在解决大型的NP难题时,常常存在着局部收敛等早熟现象。针对这种情况,许多学者提出了混合算法的思想。其中一个尝试是将易局部早熟的蚁群算法与收敛较慢的模拟退火算法相结合,利用结合蚁群算法搜索高效性和模拟退火算法全局搜索性的混合算法来解决组合优化问题。文献[10,11]提出了结合模拟退火与蚁群算法的混合优化算法,在思路上均以模拟退火作为算法主体,结合了蚁群算法信息素正反馈机制,大大提高了算法求解的寻优能力,但在解种群多样性上略显不足。

本文在前人研究的基础上,首先建立能力约束的多目标的任务分配问题模型;然后利用模拟退火蚁群算法——即以蚁群算法为主体的思路对模型进行仿真求解,实现订单的最优分配,同时对算法在解空间多样性及信息素更新方面做了进一步的改进;最后用数值分析验证了模型与算法的有效性与合理性。

1 带能力约束的多目标任务分配问题的模型构建

多目标任务分配问题可以描述为存在m个不同的订单需要加工完成,现有n个产能不同的OEM供应商可以承担这些订单,因此加工成本和时间各不相同。从成本收益(表现为总的任务利润最大化)及服务水平(表现为交货延误时间最小化)两个目标出发,可建立任务分配的问题模型如下:

$\begin{array}{l}\max {\rm P}{}_{\text{t}}={\displaystyle \sum _{i=1}^m(}R{}_i-{\displaystyle \sum _{j=1}^{n}X}{}_{ij}c{}_{ji})\\ \min {\rm T}{}_{\text{d}}={\displaystyle \sum _{i=1}^m|}{\displaystyle \sum _{j=1}^{n}X}{}_{ij}t{}_{ji}-{\rm T}{}_i|\\ \text{s}.\text{t}.{\displaystyle \sum _{i=1}^{m}t}{}_{ji}X{}_{ij}\le {\rm K}{}_j,\forall j(2)\end{array}$

$\begin{array}{l}{\displaystyle \sum _{j=1}^{n}X}{}_{ij}=1,\forall i\\ X{}_{ij}=\{0,1\},\forall i,j\end{array}$

式中,目标函数Pt为总的加工利润;Td为交货延误时间,即实际订单完工时间与预定的理想交货期的差异;订单i被供应商j加工时状态变量Xi j为1,否则为0;Ri为各订单的售价;Kj为供应商的加工能力或产能;ci j与ti j分别为各订单的生产成本和加工时间;Ti为理想的订单交货期。

由目标函数的约束形式可知:订单必须满足供应商产能,即加工能力约束(约束1);订单具有不可分割性,即一个订单只能由一个供应商加工(约束2)。

最后,如前所述,为方便目标的量化评估,达到效益的最大化,可根据实际情况对两项目标属性进行加权并标准化为求总的适应度最小值。设加工利润权重为α,交货延误时间权重为β,且满足α+β=1,则总的适应度函数可变形为

min(α(-Pt)+βTd) (3)

据此建立多任务分配问题的数学模型。

2 算法设计

针对上述问题,本文采用模拟退火结合蚁群算法的混合智能算法进行求解。其主要思路是首先用随机算法初始化信息素矩阵,然后以蚁群算法为迭代计算的主体,完成一次迭代后,采用模拟退火算法对当前解进行随机扰动产生不同的领域解,在Metropolis接受准则下允许解在有限范围内分散化,产生更多可行解,最后用当前解与改进解所带的路径信息更新信息素矩阵,不断重复上述过程。

在领域的局部搜索中,对当前找到的迭代路径序列进行随机扰动,并按照模拟退火的思想,当扰动解优于当前解时,则无条件接受扰动解;当扰动解次于当前解时,则在当前温度下按接受规则有条件接受或拒绝该解,不断重复这个退火过程直到找到改进后的解。这种做法增加了对当前解的随机扰动,从而扩大了解样本的多样性,并在一定程度上发挥了退火算法的优势,有利于稳定状态的大范围全局寻优。

2.1 任务分配过程的蚁群网络图

构造蚁群网络图如图1所示,假设有m个不同的订单O1,O2,…,Om,n个不同的OEM供应商S1,S2,…,Sn;每个订单都有n个OEM供应商可供选择交付加工,但是一个订单只能选择一个供应商来加工。在Oi处分别设置ri只蚂蚁,每只蚂蚁从Oi(i=1,2,…,m)处根据转移概率转移到各级节点S1～Sn处,完成周游,从而形成一条行走路径,即不同的蚂蚁形成不同的解。这里的处理相当于生成m维的1～n的序列,分别对应于各订单所分配的加工供应商。

2.2 算法相关参数及规则的确定

本算法在计算过程中主要考虑了如蚂蚁各节点转移概率、信息素更新规则、随机扰动策略、退火算法Metropolis接受准则等。

2.2.1 转移概率

理论上,各订单可选择并分配给各供应商,在t时刻,蚂蚁k从某级供应商节点i转移到下一级供应商节点j的概率为

${\rm P}{}_{ij}^{(k)}(t)=\tau {}_{ij}^{(k)}(t)/{\displaystyle \sum _{j=1}^n\tau }{}_{ij}^{(k)}(t)(4)$

其中,τi j表示各级供应商节点之间的信息素浓度;供应商节点的信息素越大,则此供应商被选取的概率越大。

2.2.2 解的领域随机扰动

为增加解样本的多样性,使搜索空间更全面,当蚁群算法产生本次迭代最优路径之后,便在该路径基础上采取逆转策略[12],亦即随机产生两个不同的数,如t1与t2(t2>t1);对应订单分配的解序列两个位置,在此当前解C0中将订单t1与订单t2之间的供应商分配关系(子路径)以反方向插入,其余不变,此时新解为C1。为进一步增加解的多样性,考虑双向逆转策略的改进,即对分配矩阵行列上均使用逆转策略进行扰动。

2.2.3 Metropolis准则

本文考虑在上一步的解领域随机扰动中加入小规模的退火算法过程,即根据退火算法的统计规律,设定初始温度T0(200～280,退火算法中温度为量纲一的量,仅表示初始状态)和退火速率αk(0.8～0.95),一般按照直线函数反比递减。如前所述,按照一定的概率在当前最优路径上随机产生新解,每次接受新解的概率为

${\rm P}=\{\begin{array}{l}1f{}_{C{}_i}\ge f{}_{C{}_j}\\ \exp (\frac{-\text{Δ}f{}_{ij}}{{\rm T}})f{}_{C{}_i}＜f{}_{C{}_j}\end{array}(5)$

Δfi j=fCj-fCi

式中,fCi为当前最优解Ci的适应度;fCj为扰动后产生的新解Cj的适应度;Δfi j为两个解的适应度之差。

从式(5)可以看出,当通过退火算法随机扰动产生新解后,若此解较优于原当前解,则百分之百接受新产生的扰动解为当前解;否则以一定的随机概率有条件地接受或拒绝新解。继续降温,重复下一次温度下的扰动,直至达到设定的最低温度。这里采用了模拟退火算法的思想,允许目标函数在有限范围内变坏,增加了解抽样的多样性,有效地避免了计算过早地陷入局部最优状况。

2.2.4 信息素更新规则

在融合模拟退火算法Metropolis扰动之后,其更新方程为

τi j(t+1)=ρ τi j(t)+Δτ (6)

$\text{Δ}\tau =\{\begin{array}{l}\frac{Q}{f{}_{\text{C}}}ij\text{为}\text{当}\text{前}\text{解}\text{路}\text{径}\\ 0\text{其}\text{他}\end{array}(7)$

式中,τi j(t)为t时刻路径上的原信息素浓度;ρ为信息素强度的持久性系数(0.5～0.9);Δτ为本次迭代计算的信息素增量;Q为一正的常数;fC为目标函数适应度值。

最后要提及的是,在目标函数的处理上,本文借鉴了大M法的思想,对超出约束的解引入惩罚系数,从而有利于模型在程序实现上的处理。

2.2.5 算法求解步骤

混合算法程序伪代码如下:

(1)初始化

相关参数的设定及任务、供应商信息的读入;

NC=1:NC_max;//NC为迭代计算次数;NC_max为规定的最大循环次数

τ=C;//信息素浓度初始化,C为初始化信息数

Initial(τ);//随机算法初始化信息浓度

Δτ=0;//信息素增量置0;每次更新取C/5左右效果为佳

Tabuk=Φ;//蚂蚁k的分配路径表清零

k=1;Ant_number;//k为蚂蚁编号;Ant_number为蚂蚁个数

(2)蚂蚁重复周游寻解

while NC⇐NC_max do

for k=1:Ant_number do

蚂蚁k以概率P(k)i j为订单i选择下一供应商j;//见式(4)

Tabuk(NC)=j://供应商j写入分配路径表

(3)适应度目标值计算

for k=1:Ant_number do

for i=1:M do

for j=1:N do//M为订单数,N为供应商数

计算总的加工收益Pt与服务水平Td,并加权处理;//见式(3)及模型(2)

(4)退火算法领域搜索

设定退火算法相关参数;

T0=U;//定义初始温度,常数U代表某高温状态

while T>T_acceptionp and Makob=1∶L do;//T_acceptionp为最低温度点,Makob为链长,并判断迭代次数是否到达设定链长

exchange(Ci,Cj);//行列双向的逆转策略与随机扰动

if (E) AcceptNewSolution(Ci,Cj)

else disturbance(Ci,Cj);//以Metropolis规则判断本次迭代两解优劣,并决定取舍

end if

T=T*α;//降温

(5)信息素更新

for k=1:Ant_number do

for j=1∶N do

$\text{Δ}\text{τ}{}_{\text{i}\text{l}}=\frac{\text{c}{}_1}{\text{f}{}_{\text{i}\text{t}\text{e}\text{r}}(\text{n}\text{c})}+\frac{\text{c}{}_2}{\text{f}{}_{\text{g}\text{l}\text{a}\text{b}\text{a}\text{l}}}$;//按式(7),具体可考虑同时更新扰动前后两解的路径信息

τi l(nc+1)←ρ τi l(nc)+Δτi l;//参见式(6)

(6)最终计算结果

if未到达结束条件,返回第(2)步;

else记录并输出最终解

3 算例分析

为了验证本文构建的模型与算法的有效性,本文用两算例(单资源约束与多资源约束)来进行数值模拟分析。

(1)算例一:单一资源约束情况

只考虑加工时间的单资源约束时,假设某品牌制造商接到9个不同顾客的订单(生产任务),每个订单的交货期与售价见表1。

现有5个OEM供应商可以承担这些订单,但是成本及加工时间不同,同时各供应商也有生产能力上的限制,具体见表2。其加工时间及成本信息见表3,例如4/18中4表示加工时间,18代表订单加工成本,依此类推。此外,根据该品牌制造商追求目标的侧重特点,对式(3)中选取加工利润权重系数为α=0.3,交货延误时间权重为β=1-α=0.7。

本文采用MATLAB仿真编程工具,依次利用单纯的模拟退火算法、蚁群算法及混合SA-ACO算法进行订单的分配问题求解,单资源约束仿真实验结果分别如图2～图4所示。

经多次仿真实验,三种算法均能以其自身的寻优性能求解出此简单算例的最好解,求解出的最佳订单分配矩阵见表4。即供应商1负责订单4;供应商2同时负责订单7与8;供应商3负责订单6;供应商4负责订单1、5和9;供应商5负责订单2与3,具体对应的订单分配矩阵结果如表4所示。此时,可由此算出加工利润Pt目标函数值为285万元,交货延误时间Td目标函数值为89d,按照式(3)赋权加总的最小适应度值为-23.2。

(2)算例二:考虑多种资源约束的情况

综合考虑加工时间和关键物料的多资源约束时,其他条件不变,假设各订单的加工关系到某种关键物料的使用,使用情况wi如表2中最后一列数据所示;此时就要考虑OEM供应商在加工这些订单时有关键物料可用量的资源约束Wj,可用量具体如表3所示。亦即在原模型基础上加入如下新约束:

${\displaystyle \sum _{i=1}^{m}w}{}_{i}X{}_{ij}\le W{}_j,\forall j$

据此用同样的仿真实验求解过程,由实验结果可得,混合算法在问题复杂度增大的情况下依然能保持良好的求解效率,求解出的最佳订单分配矩阵如表5所示。同理,加工利润Pt目标函数值为284万元,交货延误时间Td目标函数值为97d,按照式(3)赋权加总的最小适应度值为-17.3。多资源约束情况下混合算法及基本蚁群算法的仿真实验结果如图5、图6所示。

在单一资源约束情况下,从图2可以看出,模拟退火算法具有很好的全局搜索性能;但是由于反馈信息利用不足,收敛速度较慢,直到100多次迭代计算才收敛至最优解,而且求解结果并不稳定,耗时较长;而在加入多资源约束考虑时,相同的计算时间内甚至很少找到最优解。从图5及图6可以看出基本蚁群算法相对快速的搜索能力,在60～70次左右便能找到最优解,有时也容易陷入局部收敛;而加入自适应条件与退火搜索的混合算法无论在收敛速度还是在寻优的稳定性上均优于前两者,基本上结合了两种算法的长处:最好情况下,在20次左右迭代计算便能找到最优解,经笔者多次实验,其最佳寻优次数也平均多于单一算法情况,具有较好的鲁棒性。

本文也利用商业优化软件Lingo11.0对该问题进行了求解,得到与混合算法相同的结果。经笔者多次实验,对每种计算方法都重复10次求解,各方法计算结果(包括多资源约束情况)统计分析与对比见表6。由此可证明各算法的自身求解能力及混合算法的有效性。

注:表中的负值为适应变值(量纲一),其值越小越好。

4 结束语

任务分配问题是当前供应链协作环境下普遍存在的问题。本文建立了多目标的订单分配模型,并尝试通过结合具有全局搜索性的模拟退火算法及有快速寻优性能的蚁群算法,来对此类问题进行求解。希望借以充分利用两算法的优势,克服如退火算法收敛慢、蚁群局部收敛的缺陷,在新解的扰动中加入了退火算法的规则,有效提高了搜索空间的多样性。最终对基本模拟退火算法、基本蚁群算法、混合算法三种方法的同算例求解结果进行了对比,可以证明混合算法在求解速度及质量上都有让人满意的效果。

参考文献

[1]池元成,蔡国飙.基于蚁群算法的多目标优化[J].计算机工程,2009,35(15):168-172.

[2]朱云.目标规划及AHP在企业外包任务分配中的应用[J].吉林省经济管理干部学院学报,2010,24(3):23-26.

[3]何霆,郭世伟,徐汉川.基于最小生产时间的制造任务分配策略[J].黑龙江大学自然科学学报,2009,26(5):591-595.

[4]谢经明,娄平,陈幼平,等.供应链中基于多Agent协商的任务分配机制的研究[J].中国机械工程,2005,16(21):1911-1915.

[5]郭志明,莫蓉,孙惠斌.改进GSA算法在协同制造任务分配中的应用[J].计算机工程与应用,2011,47(14):210-213.

[6]张卫,潘晓弘,田景红,等.基于灰色理论的制造任务分配服务研究[J].中国机械工程,2010,21(14):1694-1703.

[7]朱金达,宋海生,张永弟.网络化制造执行系统任务分配的研究[J].设计与研究,2006,7(33):9-11.

[8]Dorigo M,Ganbardella L.Ant Colony System a Co-operative Learning Approach to the Traveling Sales-man Problem[J].IEEE Trans.on Evolutionary Computing,1997,1(1):53-66.

[9]罗德林,段海滨,吴顺详,等.基于启发式蚁群算法的协同多目标攻击空战决策研究[J].航空学报,2006,27(6):1166-1170.

[10]刘少伟,王洁,杨明,等.防空C3I目标分配问题的ACO-SA混合优化策略研究[J].系统工程与电子技术,2007,29(11):1886-1890.

[11]麻士东,龚光红,韩亮,等.目标分配的蚁群_模拟退火算法及其改进[J].系统工程与电子技术,2011,33(5):1182-1186.

多方法混合算法 篇8

1975年提出的多模型控制技术,没有采用切换方法,而是采用加权平均算法,提高控制器输出的鲁棒性。后来美国Narendra教授及其团队研究的多模型切换技术,采用指标函数选择切换模型,开创了多模型切换技术的先河[1,2,3]。针对非线性系统参数的不确定性,学者Cezayirli等采用多模型切换控制方法提高系统的动态响应[4]。文献[5,6]将多模型切换控制与神经网络学习进行联合,应用到非线性系统中。

多模型切换控制关键技术之一就是建立模型库,模型库中的模型与实际系统匹配程度决定了模型库的优劣。由于被控系统的不确定性,需要大量的模型来匹配关键工作点。模型库模型数量越多匹配性能就越好,但计算量大;模型数量太少又不能很好匹配实际系统,动态响应变差。为保证匹配度、减少计算量,文献[7,8]对模型库进行优化,在相同的模型数量下,提高了匹配度,但模型数量仍然较大。文献[9]提出在线学习的动态模型库优化方法,实时在线优化模型库中的模型,使模型向实际系统趋近,保证匹配度。

近年来,多模型控制技术在BTT导弹系统、汽车温度调节系统、磁悬浮系统、飞行器控制系统等方面得到良好应用[10,11,12,13,14]。PMSM调速系统对调速性能要求苛刻,而电机参数易受温度等因素影响,具有不确定性,因此本文主要研究基于混合多模型及其切换控制技术的永磁同步电机调速控制系统。

1 基于RLSE的多模型控制

1.1 多模型系统建立

为了应对电机参数的变化,采用RLSE在线实时辨识电机参数,得到离散模型的参数向量。因辨识结果易受干扰,若只辨识和保存1组参数向量,可能会偏离真实值。因此需要辨识多组参数向量历史值,保存误差小的参数向量,误差大的参数向量自然剔除,以提高参数辨识的鲁棒性,为控制器模型提供准确的电机参数。

电机初次运行,需要1组离线辨识参数向量作为控制器基本参数。所以多模型系统中的模型由1个固定参数模型和1个可变参数模型库组成,可变参数模型库由基于RLSE辨识得到的多个模型组成。若模型过多计算量大,模型太少鲁棒性会变差,因此限定模型为3个。基于RLSE的多模型控制系统结构如图1所示。

由RLSE优化的模型库如下:

式中:yLSEi(k)为模型i的预测输出;θLSEi为模型i的参数向量。

当前实际输出与预测输出误差为

式中:y(k)为k时刻系统输出的检测值。

模型i在有限时域长度h内预测误差,设模型i的指标函数为

式中:α为当前误差权重,α≥0;β为历史误差权重,β>0;τ为遗忘因子,τ>0;i为模型的标号,i∈{1,2,3}。

由RLSE辨识得到的3个模型采用“劣汰”方法优化,用指标PLSEi(k)最大的模型参数向量θLSEi替换为当前辨识的θLSE(k),即:

式中:θLSEj为模型j的参数向量;θLSE(k)为当前RLSE辨识的参数向量。

固定模型误差函数和指标函数为

4个PMSM离散模型对应4个指标值,分别为PS,PLSE1,PLSE2,PLSE3,选择最小值对应的模型为最优模型,以此模型的参数向量作为控制器参数在线整定依据,称之为“优胜”。

1.2 多模型控制系统仿真

仿真时,对4个模型编号,固定模型编号为1,RLSE模型编号为2,3,4。仿真系统主要参数配置如表1所示。

基于RLSE的多模型控制系统转速仿真结果如图2所示,多模型控制器采用“劣汰”方法在线优化模型参数,采用“优胜”方法挑选最佳匹配模型作为PMSM的PI调节器参数设计依据。图2中Number为挑选出的最佳匹配模型编号,开始时,基于RLSE的辨识过程未稳定,辨识参数处于有效优化阶段,PI调节器参数随之变化。待RLSE辨识稳定后,匹配的参考模型号不再变化,PI调节器参数基本稳定不变,转速很快稳定下来,结果表明基于RLSE辨识的多模型切换可以保证系统的稳定运行。

2 基于MRAS的混合多模型控制

2.1 混合多模型系统建立

在一定误差范围内,基于RLSE辨识速度较快,而基于MRAS辨识较慢,但基于MRAS辨识误差较小。因此提出混合多模型控制,系统中含有2种可变模型库:一个是基于RLSE辨识的模型库;另一个是基于MRAS辨识的模型库,还有一个固定模型,供不同的工作点择优选用。由不同辨识方法获得的参数值构建的模型越接近实际模型越好。考虑到计算量和鲁棒性因素,限定每个模型库中含有3个可变模型,于是系统共有7个模型,结构如图3所示。

2.2 混合多模型的切换策略

多模型切换控制是通过选择一个合适模型来调节控制器参数,改变其结构和性能,达到匹配控制系统的目的。采用“优胜”方法选择模型,用指标P(k)最小的模型中参数向量θ(k)作为调整控制器的依据,将7个模型分别编号为M1~M7,其对应的指标函数为P1(k)~P7(k)。同时引入滞环方法,防止模型频繁切换,切换策略如下:

式中:θ为控制器调整时使用的参数向量;当前控制器采用第j个模型;Δ为滞环宽度,Δ>0。

2.3 混合多模型控制系统仿真

仿真时,对7个模型进行编号,固定模型编号为1,基于RLSE的模型编号为2,3,4,基于MRAS的模型编号为5,6,7。仿真系统的主要配置参数同样如表1所示。

仿真结果如图4所示,多模型控制器采用“劣汰”方法在线优化多模型参数,采用“优胜”方法选择最佳匹配模型作为PMSM的PI调节器参数整定依据,图中Number为挑选出最佳匹配模型编号。开始RLSE辨识的模型和固定模型被选择的概率较大,然后倾向于MRAS辨识的模型,模型参数处于有效优化过程,待RLSE和MRAS辨识稳定后。由于MRAS辨识的稳态精度比RLSE辨识高,所以最终选定的参考模型来自MRAS辨识的模型库。结果表明,基于混合多模型控制的切换模式能够保证系统的稳定运行,综合了RLSE辨识的快速性和MRAS辨识的高稳态精度等特性。

3 PMSM混合多模型控制实验研究

永磁同步电机调速系统采用380 V/50 Hz三相交流电源,利用变频装置驱动电机运行,负载为三相永磁同步发电机。测试平台还有力矩传感器、示波器、PC机、仿真器等辅助调试设备。系统结构如图5所示。

图5中,Emulator为TI公司出品的DSP仿真器,型号为XDS100V2;Torque Transducer为力矩传感器;Encoder为2 500线增量式正交编码器;Load为Y型连接的纯电阻负载;Rectifier,Inverter和DSP Board共同组成变频驱动装置。由供电箱、15 k W变频器、PMSM、力矩传感器、示波器、DSP仿真器和PC机组成的永磁同步电机变频测试平台。

试验电机参数为:额定功率PN=0.4kW,额定转速nN=3 000r/min,额定电流IN=2.8A,额定电压UN=220V,极对数p=4,交轴电感Lq=6mH,直轴电感Ld=6mH,定子相电阻Rs=1.37Ω,转子磁链Ψf=0.0378Wb,转动惯量J=3.221×10-5kg·m2,载波频率fc=10kHz,直流母线电压UDC=580V。

进行调试,变频器硬件电路有2路独立的模拟量输出模块,输出电压范围0~10 V,输出电压控制2路PWM占空比。试验中,将所有信号进行归一化处理,改变PWM占空比,输出电压同步改变,达到监测变量的目的。得到的uα和uβ波形如图6所示,uα和uβ均为正弦波,而且uα相位比uβ超前90°。

在PMSM双闭环控制的基础上,引入多模型切换控制,在线整定PI调节器参数,系统结构如图7所示,PI Para Adjust模块采用基于混合多模型库的PI参数在线调整方法,试验给定转速500 r/min,对应电角度频率33.33 Hz。转子位置和U相电流波形如图8所示,U,V两相电流波形如图9所示。可以看出,位置信号频率33.33 Hz,U,V两相电流波形为正弦波,说明混合多模型控制效果较好。

4 结论

本文以三相PMSM为研究对象,提出混合多模型控制策略,研究了基于混合多模型控制的PMSM驱动系统,提出了由基于RLSE辨识的模型库和固定模型组成的多模型控制系统,以及由基于MRAS辨识的模型库和固定模型组成的多模型控制系统。遵循“优胜、劣汰”原则,综合两者优点,选择由2种在线辨识方法建立的模型库和固定模型组成混合多模型控制系统,提高系统的鲁棒性和稳定性。通过Matlab/Simulink仿真验证该方法的可行性。将所提混合多模型控制方法应用于永磁同步电机调速系统,利用变频装置驱动电机运行,负载为三相永磁同步发电机。采用CCS5.2进行变频算法设计,分别对模块和系统进行实验调试,实现了基于混合多模型控制的三相PMSM双闭环矢量控制功能,获得了良好的动态和稳态性能。

摘要：以面贴式三相永磁同步电机(PMSM)为研究对象,研究基于递推最小二乘法和模型参考自适应法的混合多模型在线辨识方案,通过指标函数实时优化动态模型库。在电机运行过程中,根据“优胜、劣汰”规则匹配调节器模型和参数,提出基于混合多模型控制的永磁同步电机在线控制策略,达到在线整定参数的目的。将混合多模型策略应用于PMSM调速系统测试平台,仿真和试验结果验证了所提方案的可行性和混合多模型控制策略的正确性。