粒子群算法的边界问题

2024-07-16

粒子群算法的边界问题（精选9篇）

粒子群算法的边界问题第1篇

迷宫问题如图1所示是实验心理学中一个古典问题, 以m*n的长方阵表示迷宫, 0和1分别表示迷宫中的通路和障碍, 给定迷宫的入口和出口。要求求出迷宫入口到出口有无通路, 若有通路则指出其中一条通路和路径。迷宫问题是典型的图搜索问题, 解决方法通常有启发式搜索和A*算法, 鉴于粒子群算法 (Particle Swarm Optimization, PSO) 良好的优化能力, 下文尝试利用粒子群算法求解迷宫问题。

在PSO中, 每个优化问题的解都是搜索空间中的一只鸟, 称之为“粒子”。所有粒子都有一个由被优化的函数决定的适应值, 每个粒子还有一个速度决定它们飞翔的方向和距离, 粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子 (随机解) 。然后通过迭代找到最优解。每次迭代过程通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest, 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。粒子根据式 (1) 和式 (2) 来更新自己速度和新的位置:

其中, Vid是粒子的速度, Pid是当前粒子的位置。c1和c2为学习因子, w为惯性系数。

2 设计思路

2.1 粒子编码

PSO算法一般采用实数编码, 对于图1的迷宫, 从入口到出口的路径共有4个方向可选择:向上、向下、向左、向右。那么用1, 2, 3, 4分别代表, 上、下、左、右4个方向, 假设有随机数P, 若P∈[1, 2], 则选择向上方向运动, 依次类推。那么, 粒子的位置xid代表入口向出口的一条路径 (不一定是通路) , 例如有粒子particle=[3.1, 3.5, 2.4, 3.2, …], 这条路径为向左→向左→向下→向左等。

2.2 适应值的计算

适应值的计算可参考曼哈顿算法, 即当前位置距出口距离的倒数, 具体计算方法为其中Dis=abs (DestinationX-CurrentX) +abs (DestinationY-Currenty) +1 (距离的基数为1) , 由于到达终点时, 距出口的距离为0, 适应度值为最大值1。因此, 在整个搜索过程中, 粒子的搜索目标始终朝着适应度为1的方向搜索。

2.3 种群初始化

粒子的初速度设为0, 每个个体局部极值pBest的初值设为每个粒子自身, 粒子的全局极值gBest初始值为第一代粒子群的最优值。

2.4 粒子更新及参数选择

粒子速度和位置的更新基本按式 (1) 和式 (2) , 为保证粒子位置和速度的合法性, 将式 (2) 取绝对值[1, 4], 同时由于粒子的速度取值在内, 假定:当粒子速度小于1或大于4时, 那么粒子速度就设定为1或4。需要说明的是, 需要预先估计从入口到出口的最大步数, 对于图2的迷宫, 假设从入口到出口最多需要35步, 在这里对应粒子的长度。

3 实现代码

算法实现采取Win32编程, 程序在VC 6.0+WindowsXP环境中调试通过, 程序运行结果如所图2示。

算法实现过程中的核心类主要有:粒子类、算法类和绘图类。

4 结语

一种改进的变异粒子群算法研究第2篇

粒子群优化算法PSO(Particle Swarm Optimization)是一类性能优越的寻优算法.但由于早熟问题,影响了算法性能的发挥.针对这一问题,引入粒子距离的概念,提出一种新的PSO改进方法(称为NA-PSO).通过求解组网雷达的系统偏差,表明了NA-PSO算法的`可行性,与对比方法相比较,能有效配准,且具有更好的收敛精度和更快的进化速度.

作者：王波李瑞涛王灿林朱丹 WANG Bo LI Rui-tao WANG Can-lin ZHU Dan 作者单位：王波,李瑞涛,王灿林,WANG Bo,LI Rui-tao,WANG Can-lin(海军航空工程学院,山东,烟台,624001)

朱丹,ZHU Dan(91550部队,辽宁,大连,116023)

粒子群算法的边界问题第3篇

关键词粒子群算法；水资源优化配置；水稻

中图分类号 S344 文献标识码 A

Optimal Allocation of Rice Water Based on PSO

LUO Yongheng1，ZHANG Mi2，ZHOU Jianhua2

(1. Economic College of Hunan Agricultural University，Changsha，Hunan 410128，China；

2. School of Economics and Management，Changsha University of Science & Technology，Changsha，Hunan 410114，China)

Abstract This article aimed to achieve the optimal allocation of rice water resources. The optimal allocation of rice water not only exists in different types of rice such as early rice, season rice and late rice, but also exists in different growth stages of the same type. Particle swarm optimization has the advantages of high efficiency and precision in the calculation and is relatively easy to operate,so it was applied to the optimal allocation of rice water model solution. The specific example of optimal allocation of rice water in GaoLu village of HengYang verifies the feasibility of the algorithm.

Key words particle swarm optimization;the optimal allocation of water resource; rice

1 引言

作为农业大省的湖南省，其主要农作物是水稻，故水稻用水量十分巨大.虽然湖南省全境地处亚热带季风湿润气候区，降水较为丰沛，但在季节性干旱时节中，全省不少农村地区普遍存在着水稻用水困难问题.

在科学地对水稻进行用水的前提下，有限的灌溉水量既要在早稻、一季稻和晚稻等不同类型的水稻之间进行优化配置，也要在同一类型水稻在不同的生长阶段进行优化配置.为此就要构建一种大系统、多目标的高维非线性优化配置模型.在以往的文献中，在求解模型的方法选择中，一般采用大系统分解协调原理和动态规划相结合的方法.该方法虽然将大系统分解为一个个的子系统并减少了变量个数，便于优化求解，但协调的过程需要多次从低阶模型中返回信息，而且对于每层的寻优求解过程存在难以克服的矛盾，状态变量离散过少会降低计算精度，使计算结果偏差太大；离散过多，则又会大大降低计算效率.因此有学者应用基于粒子群的大系统优化模型来求解.粒子群优化算法具有较强全局寻优能力，应用于水稻用水的优化配置模型的求解.粒子群优化算法一方面提高了计算效率和计算精度，另一方面也比较容易操作.本研究以湖南省衡阳县高炉村的水稻用水优化配置为具体算例.结果表明，本文所用方法运算快速，程序实现简单可行，评价结果准确，没有陷入局部最优解的局限，

2 粒子群优化算法

粒子群优化算法（Particle Swarm Optimization）是由Kennedy和Eberhart于1995年提出的一种新型的群智能进化算法，它可以灵活方便地处理具有大量等式约束、不等式约束和同时包含连续变量、离散变量的混合整数优化问题.因此，对于水稻的用水优化配置间题，采用粒子群优化算法也是一种可行方案，其为水稻用水优化配置提供了一种很有前景和潜力的新型方法［1-7］.

粒子群算法的规则比遗传算法还要简单.粒子群算法从随机解出发，由迭代公式计算最优解，通过适应度来评价解的品质，通过追随当前搜索到的最优值来寻找全局最优.

粒子群优化算法中，其迭代公式是：

vij(t+1)=wvij(t)+c1v1j(t)(pij(t)

－xij(t))+c2v2j(t)(pgj(t)－xij(t))，

xij(t+1)=xij(t)+vij(t+1)，

其中，i表示粒子i，j表示粒子的第j维，t表示第t代，c1,c2为加速常数.w为惯性权重：w(iter)=wmax －(wmax －wmin )/imax ·iter.wmax 为最大惯性权值，imax 为最大进化代数；wmin 为最小惯性权值，iter为代数.r1和r2为两个随机函数，并且相互独立.vij∈［－vmax ,vmax ］， vmax =kvmax ,0.1≤k≤1.0.

3 水稻用水优化配置的模型构建

水稻用水优化配置的出发点和立足点就是，灌溉水稻的用水能够产生最大的经济效益.然而，灌溉水稻的用水量与其带来的经济效益，存在着复杂的非线性关系，较难用函数关系对其进行描述.有时使用动态规划法、线性与非线性规划法等方法，也可以用离散的表格形式表达水稻用水量与其经济效益之间的关系，但前提就是都要把灌溉水稻的用水作为连续变量，为此往往使水稻的用水配置决策与实际的用水情况不相适应.

由一季稻和晚稻打成的大米（简称为一季稻米和晚稻米.同样，由早稻打成的米是早稻米），因为煮熟后米饭较软、黏，得到消费者的偏爱，因而一季稻米和晚稻米其市场价格要比早稻米高出不少.一季稻米由于其生长周期长，加之其米饭口感好，营养比晚稻米丰富，因而其市场售价又比晚稻米贵一些.目前，在我国南方地区，尤其是湖南省的中南部地区，农户在全年当中，有的只是种植一季稻，也有不少农户种植水稻两次，即分别种植早稻和晚稻.这样在每年的3月至10月当中，水稻的存在形式是，既有早稻，也有一季稻和晚稻.除了早稻和晚稻不能同时存在以外，早稻和一季稻、一季稻和晚稻，均有一段交差重叠的时期.本研究因为数据采集的关系，没有考虑大米的市场价格，因而也就没有经济效益的价格因素.而只是把灌溉水稻的用水能够产生最大的经济效益，仅仅等同于水稻的产量.

基于上述情况的考虑，本研究把不同类型的水稻（早稻、一季稻和晚稻）看作一个用水单位，对不同类型的水稻进行用水量最优配置.同类型水稻的用水，分阶段进行用水量最优配置.

3.1 同类型水稻用水优化配置模型

同类型的水稻，处于不同阶段（本研究把水稻的生长期划分为四个生长阶段，具体的阶段划分，见下文），其用水量是不同的.水稻的用水原则是：第一阶段，深水返青；第二阶段，浅水分蘖；第三阶段，有水壮苞；第四阶段，干湿壮籽［8］.

1）第一阶段的深水返青.移栽后的水稻，吸引水分的能力大大减弱，这是由于水稻的根系受到大量损伤，大大减弱了稻根吸收水分的能力.这时候需要对稻田大量灌水，以增加稻根吸收水分的机会.此时田中如果水量不多的话，禾苗的稻根因为吸收水分困难，就会造成禾苗返青期延长.也因为禾苗叶片丧失的水分多，禾苗出现卷叶死苗的现象.因此，水稻禾苗移栽后必须深水返青.不过，深水返青一般以水深3~4 cm为适宜，并不是灌水越深越好.

2）第二阶段的浅水分蘖.分蘖期的水稻，在稻田灌水过深的情况下，往往会由于土壤缺氧闭气，禾苗基部光照弱，禾苗养分分解缓慢，禾苗分蘖困难.但分蘖期也不能没有水层.一般以保持1.5 cm深的浅水层为宜，并要做到“后水不见前水”，以利协调土壤中水、肥、气、热的矛盾.

3）第三阶段的有水壮苞.水稻稻穗形成期间，是水稻生长期中大量耗费水的时期，特别是减数分裂期，对水分的反应更加敏感.这时如果缺水，就会造成颖花退化，穗短、粒少、空壳多等.所以，水稻孕穗到抽穗期间，一定要保持田间有3 cm左右的水层，以保花增粒.

4）第四阶段的干湿壮籽.水稻抽穗扬花以后，叶片停止长大，茎叶不再伸长，颖花发育完成，禾苗需水量减少.为了加强田间透气，减少病害发生，提高根系活力，防止叶片早衰，促进茎秆健壮，应采取“干干湿湿，以湿为主”的用水管理方法，以期达到的以水调气，以气养根，以根保叶，以叶壮籽的目的.

为了理论证明的方便以及建模的需要，本研究把水稻的生长期划分为N个阶段，这N个阶段也就是建模中的粒子群维度.N个阶段形成N维向量的粒子，每个阶段的用水量设为粒子的一维，随机选取5N组N维向量组形成整个粒子群.

设：Si为计划湿润层内可供水稻利用的土壤储水量，Si1、Si2为降雨前后第i个天然土层的土壤含水量，以占干容重的百分数表示.θ为计划湿润层内土壤平均含水率，以占干土重的百分数计.CKi为第i阶段的地下水补给量，θw为土壤含水率下限，约大于凋萎系数，以占干容重的百分数计.θf为田间持水量，以占干土重百分数计.H为计划湿润层深度，Hi从为第i个天然土层的土壤厚度.Pei为第i阶段的有效降雨量，Pi为自然降雨量.α为降雨入渗系数α值与一次降雨量、降雨强度、降雨延续时间、土壤性质、地面覆盖及地形等因素有关。并且一般地，一次降雨量小于5 mm时，α为0；当一次降雨量在5~50 mm时，约为1.0~0.8；当次降雨量大于50 mm时，α=0.70~0.80。.γ为土壤干容重.n为天然土层数.WZi为第i阶段计划湿润层增加而增加的水量.WZi为零时，表明当时段内计划湿润层深度一致.

F(x)=max

(ETa)i=Si－Si+1+mi+pei+CKi－Ki,（2）

式（1）、（2）中，λi为第i个阶段水稻产量对缺水的敏感指数，(ETa)i为第i阶段的实际蒸发蒸腾量/mm，(ETm)i为第i阶段的潜在蒸发蒸腾量/ mm，Pei=αPi，Si=10γH(θi－θω).式（1）和式（2）中的约束条件为∑Ni=1mi=Q以及θw≤θ≤θf.

3.2 不类型水稻用水优化配置模型

不同类型的水稻，其用水优化配置的模型构建如下：

以不同类型水稻的生长期为一个完整的时期（稻谷从播种到收获有 3~5 个月的周期.一般早稻的生长期为 90～120 天，一季稻为 120～150 天，晚稻为 150～170天）.假设有M种水稻（由于稻是人类的主要粮食作物，目前世界上可能超过有14万种的稻，而且科学家还在不停地研发新稻种，因此稻的品种究竟有多少，是很难估算的.尽管农户一般种植早稻、一季稻和晚稻，但也不排除农户种植其他类型的水稻），阶段变量K=1，2，…，M，所有类型水稻的种植面积为已知条件，C0为水稻灌区总的可供水量(m3)，不同类型水稻的可分配水量为Ck(m3），实际分配给每种类型水稻的净灌溉水量为Qk(m3），所有种植面积的水稻全部得到灌溉，则有所有类型水稻之间水量平衡方程

Ck+1=Ck-Qkη, （3）

式（3）中，初始条件Cl=C0.η为水稻用水的有效利用系数，η一般取0.8~0.9.

在不以单个农户为收益单位、而以某个地域（比如某个县、乡，或者某个村）为收益单位，则可以以各种类型水稻所带来的经济效益之和G最大为目标，建立目标函数

G=max ∑Mk=1F(Qk)·AK·YMk·PRk, （4）

式（4）中，G的单位为万元，F(Qk)为由第一层反馈回来的效益指标(最大相对产量)，Ak为第k种水稻的优化种植面积，YMk为第k种水稻的充分供水条件下的产量，PRk为为第k种作物的单价.输入灌区总的可用水量为Q、灌区内水稻种类数量为M，YMk及PRk分别为第K种类型水稻充分供水条件下产量(kg/hm2)及单价(元/kg).式（3）和式（4）中的约束条件为0≤Qk/η≤Ck，0≤Ck≤C0以及0≤∑Qk/η≤C0.

4 衡阳县高炉村的水稻用水优化配置算例

衡阳县地处五岭上升和洞庭湖下陷的过渡地带，“衡阳盆地”北沿.“衡阳盆地”属于南方湿热丘岗地易侵蚀退化脆弱区，是典型的红壤丘陵盆地.衡阳县地貌类型以岗、丘为主，海拔100~500 m之间的土地面积占全县土地总面积46.4%，坡度在15°以上的土地面积比重为52.6%.高炉村地处衡阳县洪罗庙镇南侧，地貌属于南方丘陵区类型.目前，全村人口1 217人，309户，分属于12个村民小组.全村耕地面积1 428亩，其中水田794亩，早地634亩.蒸水河从村的北边流过，池塘水域面积53亩.高炉村的水田，均种植水稻.不过，多数农户同时种植早稻和晚稻，也有不少农户种植一季稻.2009年以前，高炉村在各种水稻用水时，全是采取粗放型管理方法管理用水［9,10］，各种水稻（早稻、一季稻、晚稻）的用水量及产量，见表1.2010年，该村在衡阳县政府有关部门的倡导和大力推动下，采取了精细化的水稻用水管理措施，应用了基于粒子群算法的用水量管理.该算法对衡阳县高炉村782亩水稻田（794亩水田中，有12亩田，因为各种原因，并没有种植水稻）进行了水稻用水优化配置应用研究，见表2和表3.衡阳县高炉村的水稻用水优化配置算例，验证了本文的算法.

通过表2和表3可以发现，本文所使用的粒子群优化算法，在早稻、一季稻和晚稻等不同类型水稻的用水优化配置以及同一类型的水稻在不同的生长阶段用水的优化配置方面，产生了较好的实际效果，表现为水稻产量得到提高.这说明粒子群优化算法寻优能力和优化效率更高，该算法在不同类型的水稻和同一类型水稻的不同生长阶段的用水优化配置，均是可行的.参考文献

［1］刘玉邦，梁川.免疫粒子群优化算法在农业水资源优化配置中的应用［J］.数学的实践与认识, 2011，41（20）：163-171.

［2］陈晓楠，段春青，邱林，等.基于粒子群的大系统优化模型在灌区水资源优化配置中的应用［J］.农业工程学报，2008，24(3):103-106.

［3］崔远来，李远华.作物缺水条件下灌溉供水量最优分配［J］.水利学报，1997,28(3):37-42.

［4］李霆，康绍忠，粟晓玲.农作物优化灌溉制度及水资源分配模型的研究进展［J］.西北农林科技大学学报:自然科学版，2005，33(12):148-152.

［5］贺正楚，翟欢欢.基于DEA三阶段模型的两型农业生产效率——以湖南省为例［J］.农业系统科学与综合研究，2011，27（4）：395-400.

［6］苏里坦，宋郁东，愈双思.大型灌区高产节水灌溉优化配水决策模型研究［J］.水利学报（增刊），2005:369-373.

［7］刘玉邦.农业水资源高效利用理论及其在川中丘陵区的应用［D］.成都：四川大学水利水电学院，2011.

［8］水稻全生育期如何管水［EB/OL］.［2008-01-04］http://data.jinnong.cc/mspx/d9539.shtml.

［9］贺正楚.基于数据包络分析法的湖南省“两型”农业生产效率评价［J］.农业现代化研究，2011，32（3）：344-347.

粒子群算法的边界问题第4篇

校车问题属于车辆运输问题, 同时还受两个因素约束:车辆载重约束和时限约束。这类问题可描述如下:给定有向图G= (V, E) , 其中V为校车往返经过的停靠点的集合, E为边的集合, 是带权边, 且每条边都有一个服务需求量qij≥0 (i, j为两个相邻停靠点, 且) , 如何寻找一条回路, 使该回路所有边的需求量都得到满足且总服务费用最少?关于该问题的解法有精确算法和启发式算法, 精确算法有动态规划、非线性规划[1]等;启发式算法有:SFC法[2], 禁忌搜索法, 遗传算法[3]等。在解决实际的大规模问题时一般采用启发式算法。

1 校车问题的数学模型

数学模型如下:

其中:cij表示有服务时停靠点i到j的平均运输费用;c/ij表示无服务时停靠点i到j的平均运输费用;xijk是服务边决策变量, 当车辆k由停靠点i到停靠点j时取1, 否则取0;F为驾驶员的平均固定年费用;ρi为停靠点i的服务量;Qk为车辆k的最大容量;zi表示是否在停靠点i停靠, 有停靠取1, 否则取0;V为所有停靠点的集合;S为所有车辆的集合。

式 (1) 满足所需服务最小;式 (2) 为运输工具容量的约束条件, 满足在路线上行驶的每台校车都不超过其容量;式 (3) 保证路线连续;式 (4) 保证每个需要停靠的停靠点至少有一个客户;式 (5) 保证车辆行走路线不形成内部闭环;式 (6) 和式 (7) 保证满足取整数约束。

2 改进的量子行为粒子群算法

量子行为粒子群算法是一种启发式算法, 如今在解决网络路由, 非线性方程组[4]等方面得到广泛应用。本文根据校车运行规律, 在传统的量子行为粒子群算法的基础上, 加入回路扫描思想和分解思想, 提出了一种解决校车问题的改进量子行为粒子群算法。具体算法可以表示为:

设定参数, 包括最大迭代次数, 种群大小P (τ) ={a1 (t) , a2 (t) , …, an (τ) }, 其中τ为迭代次数。

(1) 初始化种群P (0) ={a1 (0) , a2 (0) , …, an (0) }及种群中每个粒子的位置向量;

(2) 根据适应值函数计算所有粒子的适应值P (0) ={f (a1 (0) ) , f (a2 (0) ) , …, f (an (0) ) }。适应值函数为:

(3) 根据粒子适应值, 由高到低的顺序排列粒子;

(4) 根据粒子适应值, 把当前所有粒子划分成许多子群, 每个子群中的粒子围绕在本群体中具有最优适应值的粒子周围;

(5) 运用文献[5]提到的回路点扫描法对每个子群进行扫描;

(6) 根据式改变粒子的位置, 其中t为迭代次数, β为收缩扩张系数, 调节它的值可以控制算法的收敛速度, pi其中为个位极值, pg为全局极值, mbest是局部最好位置和平均值。

(7) 转 (2) , 直到条件满足。

本文通过大量的实验仿真确定相应的参数, 图1, 图2和图3 是本算法中三个参数对算法性能的影响曲线, 从图中可以看出选取b=1.3, u=1, 是较合理的选择。

3仿真实例分析

数据来自甘肃民族师范学院所在的合作市, 校车运行网点由甘肃民族师范学院新、老校区出发并最终返回甘肃民族师范学院所行驶的全部网点构成。

校车运行区域为合作市区, 停靠点为16个, 设单位距离运输费用为1元, 车辆载客量为80, 算法最大迭代代数为2000, 图4为最后的计算结果, 图5为本文算法和基本粒子群算法最优解进化的比较, 图6为本算法采用粒子数为10个, 迭代代数为100, 目标值的变化曲线。从上面的仿真数据可知:本文提出的算法求解校车问题是非常有效的。

4 小结

本文提出了基于校车问题的改进量子行为粒子群算法, 该算法保持了种群的多样性, 有效地避免了算法陷入局部最优, 并通过实例验证, 证明了该算法是可行和有效的。

参考文献

[1]汪寿阳、赵秋红、夏国平.集成物流管理系统中定位—运输路线安排问题的研究[J].管理科学学报, 6, 69-75 (2000) .

[2]Chan Y, Carter W B, Burnes M D.随机处理的多车辆的路由问题[J]。计算机与运营研究, 28, 803-826 (1999) .

[3]李敏强, 寇纪淞, 李丹。遗传算法及其应用[M].北京:科学出版社, 1-47 (2002) .

[4]赵佶, 徐文伯, 孙钧。解决非线性方程组的粒子群优化算法[J].计算机应用研究, 24, 56-59 (2007) .

粒子群算法的边界问题第5篇

关键词：项目管理,资源受限项目调度,粒子群算法

资源受限项目调度问题(resource-constrained project scheduling problem,RCPSP)是著名的NP难问题, 精确算法求解问题的规模比较小[1,2]。对于规模比较大的项目网络,一般都采用启发式算法。研究人员开发了一些启发式规则, 并大量采用遗传算法、模拟退火算法、禁忌搜索算法等智能优化算法求解RCPSP问题的次优解。粒子群算法是一种基于群智能的智能优化算法, 它模拟鸟群的觅食行为,其算法模型可以通过显式的数学公式描述,操作和实施简单[3]。该算法本身属于连续空间的优化算法,在连续空间函数优化问题上已经得到了有效的应用。从目前的文献来看, PSO在项目调度等组合优化问题上的应用研究也陆续出现。文献[4]对粒子群算法在RCPSP问题上的应用进行了研究,采用基于优先级的编码方法,设计了一种求解RCPSP问题的元启发式算法,并对粒子群算法和遗传算法的计算效率进行了比较。文献[5]采用类似的方法将PSO算法应用于MRCPSP(multi-modes resource-constrained project scheduling problem)问题。文献[6]、文献[7]对基于优先权和基于排列的粒子表示方法进行了研究,其结论为基于排列编码的粒子群算法性能更好。文献[8]在求解MRCPSP问题时,结合PSO和局部搜索算法,提出一种组合的PSO算法,采用PSO算法为任务选定适合的执行模式,采用局部搜索算法搜索任务的最优调度顺序。

本文在对PSO算法进行研究的基础上,根据RCPSP问题的特点和粒子群算法的计算方式,对应于优先权排列编码的特点,引入向量相似度法建立粒子的速度计算模型,该模型在确定粒子移动速度时,充分考虑了粒子位置与历史最优位置和全局最优位置的相似程度。使用Java语言对本文算法予以实现,并通过实验仿真,验证了该算法的有效性。

1 问题描述

典型的单模式资源受限项目调度问题(SMRCPSP)假定每个任务有单一的执行模式, 任务在执行过程中不间断; 每种类型的资源量均为整数,且每个任务的资源需求是固定的, 需求量为整数; 所有任务时间, 包括开始时间、结束时间和工期均为非负整数;任务之间只存在紧前关系。项目计划采用G=(V,E)描述。任务用从1到n的整数标识, 即i∈V, 1≤i≤n, 其中唯一开始任务1和唯一结束任务n为虚任务,工期为0。(i,j)∈E,表示任务i为任务j的前置任务。对于任务i,其工期为ti,开始时间si, 结束时间fi. 项目所用资源类型数为K, 每种资源的总量为ak(1≤k≤K),rik(1≤i≤n,1≤k≤K)表示任务i对资源类型k的需求量,At为t时刻正在执行的任务集合。SMRCPSP问题的优化调度模型如下[2]:

$\begin{array}{l} \min f_{n} (1) \\ s . t . f_{1} = 0 (2) \\ f_{j} - t_{j} \geq f_{i}, \forall (i, j) \in E (3) \\ \sum_{j \in A_{t}} r_{j k} \leq a_{k}, t = 1, 2, \dots, f_{n}; k = 1, 2, \dots, Κ (4) \end{array}$

2 求解RCPSP问题的PSO算法

基本的粒子群算法可以描述如下:一个由m个粒子组成的群体对n维搜索空间进行搜索,每个粒子在搜索时,考虑到了自己搜索到的历史最好点和群体内(或邻域内)其他粒子的历史最好点,在此基础上进行位置(状态,即解)的变迁。在粒子群移动的某个时刻t (迭代次数),第i个粒子的位置表示为xti=(xti1,xti2,…,xtin),其速度表示为vti=(vti1,vti2,…,vtin),1≤i≤m,它经历过的历史最好点表示为pi=(pi1,pi2,…,pin)。群体所经过的最好点表示为g=(g1,g2,…,gn)。粒子的位置和速度根据如下方程进行变化:

$\begin{array}{l} v_{i}^{t + 1} = w \cdot v_{i}^{t} + c_{1} \cdot r \cdot (p_{i} - x_{i}^{t}) + c_{2} \cdot r \cdot (g_{i} - x_{i}^{t}) (5) \\ x_{i}^{t + 1} = x_{i}^{t} + v_{i}^{t + 1} (6) \end{array}$

式中,w为惯性权重,其大小决定了对粒子当前速度继承多少,合适的选择可以使粒子具有均衡的探索和开发能力。c1和c2称为学习因子。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力,从而向自己的历史最优点以及群体内的历史最优点靠近。r是大于等于0且小于1的随机数。

在采用智能优化算法进行项目调度时,核心内容有两个:一是启发式算法,二是计划生成方案。很多启发式算法借助优先规则来确定任务之间的优先权。本文为了验证算法的有效性,不采用任何优先规则,采用粒子群算法确定任务的优先权。RCPSP问题的计划生成方案包括串行调度生成方案(serial Schedule Generation Scheme,SSGS)和并行调度生成方案(parallel schedule generation scheme,PSGS)两种, Kolisch证明了SSGS生成的是积极计划, PSGS生成的是非延迟计划, 而使用非延迟计划有可能错过最优解[9]。因此本文应用SSGS方法生成项目计划,采用PSO算法查找用于生成最优调度计划的任务优先级排序。

2.1 粒子表示方法

本文采用一种基于优先权列表的编码方案。如图1(a)所示,粒子包含两种信息:位置和值。粒子的每个位置代表一个任务,任务的ID通过任务在粒子中的位置序号描述。每个粒子的优先权值填入在该任务对应的位置上。任务的优先权r是一个1≤r≤n的整数,且不同的任务不能有相同的优先值。这样,在一个任务网络图中,确定了任务之间的优先级排序。采用SSGS进行任务调度时,若发生资源竞争,优先权较高的任务首先获得调度。采用这种编码方式形成的任一优先权排序列表都能通过SSGS调度生成一个积极计划,因此该编码方式保留了基于优先权编码的优点,初始种群的生成和粒子的移动可以独立于计划生成方案。同时由于在这种编码方式中,每个位置的优先权值为互不相同的整数,与基于排列的编码方式相同,算法的搜索空间更小。其原因在于对应于一个积极计划,只对应一种(或少数几种)基于优先权排列的编码,而会对应大量的基于优先权的编码。如图1(b)中,在传统的基于优先权的编码方式中,个体虽然各个位置的值不同,但意义完全相同,会产生相同的积极计划。而基于优先权排序的编码方式则消除了这种数据冗余。

2.2 速度计算模型

在基于优先权的编码方式中, 粒子中每个位置的值都是实数, 因此可以按照经典的速度和位置计算公式进行计算和进化。基于优先权排列的编码方式虽然能够缩小搜索空间,但也带来了计算的复杂性,需要保证粒子的每个位置分量的值是1到n之间互不相同的整数。因为粒子xi中的各个分量不能重复,因此只要有一个xi的分量发生变化,必然会有另外的分量也要发生变化,才能保持任务优先级的唯一性,按照典型的粒子位置计算公式,只要|vik|>0,对应的xik就要发生改变,而多数情况下,vi中的各个分量并不为0,这样会造成每个粒子都以非常快的速度移动,显然这样容易造成粒子无序移动,失去了粒子群算法的智能性。

基于此,在本文的算法中,将限制粒子在进化时需要移动的位置分量,并通过向量相似度计算确定需要移动的位置分量数目。即将每个粒子的位置看作一个空间向量(位置向量),计算粒子位置向量xi与历史最优位置向量pi的相似度m(pi,xi),和xi与全局最优位置向量g的相似度m(g,xi),相似度高的,只需移动少数的位置,相似度低的需要移动多数的位置。由于向量包括大小(向量的模)和方向两个要素,向量的大小通过向量模来确定。在本文所设计的编码方式中,每个粒子的位置xi的向量模都是相同的,即 $∥ x_{i} ∥ = \sqrt{\sum_{k = 1}^{n} x_{i k}^{2}} = \sqrt{\sum_{k = 1}^{n} k^{2}}, i = 1, 2, \dots, n$ . 因此只能通过向量方向的不同来度量向量相似度,可通过计算两个位置向量的夹角余弦来确定相似度。m(pi,xi)的值为粒子位置向量xi与其历史最优位置pi的夹角余弦,通过式(7)计算。m(g,xi)的值为粒子位置向量xi与全局最优位置g的夹角余弦,计算方法与m(pi,xi)的计算方法相同。

$m (p_{i}, x_{i}) = \frac{\sum_{k = 1}^{n} x_{i k} \cdot p_{i k}}{\sqrt{(\sum_{k = 1}^{n} x_{i k}^{2}) (\sum_{k = 1}^{n} p_{i k}^{2})}} (7)$

通过上述方法确定每个粒子在进化时,需要移动几个分量。另外,还需要确定每个位置分量xik的移动速度vik. 可以通过典型粒子群进化策略确定粒子在每个分量上的移动速度。

综上,本文建立粒子移动速度的计算模型如式(8)和式(9)。在该模型中,速度计算包括两个方面,一是向量速度,即粒子位置向量需要移动几个位置分量,通过式(8)计算;一是分量速度,确定粒子位置分量的移动幅度,通过式(9)计算。

$\begin{array}{l} s_{i}^{t + 1} = (r \cdot w) s_{i}^{t} \\ + (1 - r \cdot w) [\frac{1 - m (p_{i}, x_{i}^{t})}{2} + \frac{1 - m (g, x_{i}^{t})}{2}] (8) \\ v_{i}^{t + 1} = w \cdot v_{i}^{t} + c_{1} \cdot r \cdot (p_{i} - x_{i}^{t}) + c_{2} \cdot r \cdot (g - x_{i}^{t}) (9) \end{array}$

式中, r为[0,1]之间的随机数。

2.3 粒子移动算法

在基于优先权排列的编码中,粒子的向量速度和分量速度都必须为整数。因此在位置移动时,应首先将vt+1i和st+1i进行取整,可通过四舍五入的方法进行。所以,在通过(8)和(9)进行速度计算之后,单个粒子需要按以下步骤进行移动:

①首先对速度进行四舍五入取整,vt+1ik=(int)vt+1ik,st+1ik=(int)st+1ik;

②对速度向量vt+1i中,保留位置分量绝对值|vt+1ik|较大的st+1i个分量,其余分量置0;

③在vt+1i中,按照|vt+1ik|值的大小,从小到大依次移动粒子的位置分量xik. 粒子新的位置分量通过式(10)计算:

$x_{i k}^{t + 1} = {\begin{matrix} (x_{i k}^{t} + v_{i k}^{t + 1}) % n, & v_{i k}^{t + 1} \geq 0 \\ (x_{i k}^{t} + v_{i k}^{t + 1}) % n + n, & v_{i k}^{t + 1} < 0 \end{matrix} (10)$

该计算方式能够确保1≤xt+1ik≤n. 同时,为了保证位置分量值不重复,在t时刻位置分量为xt+1ik的分量的值应该修改为xtik,因此粒子分量的位置移动过程实质是分量之间的值交换过程。该步骤的计算过程如图2所示。因为后移动的位置分量有可能会覆盖到先移动的位置分量,因此在移动前,需要比较速度分量|vt+1ik|值的大小,速度分量大的位置分量后移动。

粒子移动到新的位置之后,形成新的xt+1i位置向量,将该向量作为新的优先权排序,通过SSGS算法生成对应计划调度,得到新的目标函数fin. 若fin>pi,则更新历史最优位置pi=fin. 若fin<g,则更新全局最优位置g=fin.

2.4 算法其他参数确定

在应用粒子群算法求解项目调度问题时,还需要确定一些其他的参数,比如惯性权重,学习因子和种群规模。文献[10]对惯性权重进行了研究,其结论为:当最大向量Vmax≤2时,惯性权重最好选择1,当Vmax>3时,惯性权重最好选择0.8。而学习因子对算法的性能影响不大[11],习惯上,人们都设置为1或2。更多的粒子可能提升搜索的成功率,但是在每次迭代时需要更多的计算量,因此在项目调度的研究中,种群大小M通常需要接近非虚活动的数目[11,12]。综上,本文确定w=0.8,学习因子c1=c2=1,种群大小设置为项目的非虚工作数。

3 仿真测试

作者应用Java语言实现了本文所提出的粒子群算法和SSGS计划调度算珐。为了测试算法的计算结果和计算效率,选用标准问题库PSPLIB中的单执行模式工程调度嗡题对算法进行仿真测试。PSPLIB中的单执行项目调度问题分为4组,分别包含32、62、92和122项工作,需要4种可更新资源[12]。其中第1组(J=32)的最优解已经通过精确算法求得,其他几组目前还没能全部给出最优解。在实验中,本文基于第1组问题测试算法蹬有效性,统计算法解距离最优解的平均偏差avdev、最大偏差maxdev、最优解比例optimal和平均CPU运行时间。

在PSO求解RCPSP问题上,目前仅有文献[6]给出了计算结果。作者采用Java语言实现了文献[6]提出的两种编码方法,与本文所提出的算法进行比较。在相同的硬件环境和操作系统上运行,迭代次数为33次,三种算法的计算结果数据如表1。从表中可以看出,针对资源受限项目调度问题,本文所提出的算法能够在平均偏差、最大偏差和最优解比例等指标上全面提升了粒子群算法的性能。因为本文所提出的进化策略计算复杂度略高,因此采用相同的迭代次数,算法速度略有下降。

目前已知的求解RCPSP问题的智能优化算法主要包括遗传算法(GA,genetic algorithm)、模拟退火算法(SA,simulated annealing)、禁忌搜索算法(TS,tabu search)和自适应采样算法(AS,adaptive sampling)。针对PSPLIB的第一组问题进行计算,对比本文算法与上述算法的计算效果。第一组问题非虚任务数为30,为了便于与其它算法比较,在实验中设定种群规模改为25(因为25×40=1000,25×200=500,而种群规模为30时,无法在某一迭代次数上产生1000或5000个计划实例)。如表2。由表中可以看出,与目前比较成熟的优秀算法相比,本文粒子群算法的计算效果也是比较好的。值得说明的是,上述算法在实现时,多利用了各种优先级规则,而本文算法是一种没有采用任何优先级规则的元启发式算法。

4 结论

针对RCPSP问题的特点和粒子群算法的计算方式,提出了一种基于优先权排列的粒子表示方式。该表示方式秉承了优先级列表编码和基于排列编码的优点,缩小了搜索空间,并能够使粒子编码独立于计划的技术资源约束独立进化。建立了基于向量相似度法的粒子群速度计算模型,突出了粒子群算法在求解离散优化问题上的智能性。通过仿真测试,表明与优先级列表编码和基于排列的编码方式相比,本文所提出的编码方法和进化策略能够有效地改进算法的性能。与目前已经相对成熟的其他智能优化算法相比,该算法也有较好的表现。

基于离散粒子群算法的排课问题研究第6篇

粒子群优化 (Particle Swarm Optimization,PSO)[8] 算法是由 Kennedy 和 Eberhart于 1995年提出的一种基于群智能的优化算法。该算法基于仿生学原理,通过模拟鸟群的觅食过程,在搜索过程中记忆个体最优和全局最优,使得种群中的所有粒子快速向最优解移动。由于其操作简单且易于实现,因此一经提出就受到广泛关注,目前已经在函数优化、神经网络训练、模糊系统控制等领域得到了有效的应用。但对粒子群算法的研究目前主要集中在连续问题的优化求解方面,在离散组合优化方面的研究还非常有限。

本文结合排课问题的特点, 对传统PSO 算法进行了改进,构造了一种基于矩阵编码的离散粒子群算法(Discrete Particle Swarm Optimization, DPSO),实验表明这种算法能有效解决高校的排课问题。

1 问题描述

排课问题就是将课程、班级、教师安排在一周内相应的时间和教室内且不发生冲突。可见,在排课问题中涉及五个要素。设:

课程集合(Lesson):L={Li},i=1、2、3……Nl;

班级集合(Class):C={Ci},i=1、2、3……Nc;

教师集合(Professor):P={Pi}, i=1、2、3……Np;

时间集合(Time):T={Tt}, i=1、2、3……Nt;

教室集合(Room):R={Ri}, i=1、2、3……Nr 。

其中Nl,Nc ,Np ,Nt,Nr分别表示课程、上课班级、任课教师、上课时间和可用教室的总数。

五个元素的笛卡尔积L×C×P×T×R就构成了排课问题的解空间,而排课也就是在这个解空间中找到一个满足各种约束的解[5]。教学规模太大,这个解空间的规模也就可想而知了。但根据排课的具体情况,易见,<课程-班级-教师>之间的关系绝不是L×C×P的满映射关系;又因每个教学时间段、每个教室都可以安排课程,所以<时间-教室>可以看成是T×R的满映射。

则排课问题可以表示为映射:f: L->T×R。即为每门课寻找一个合适的时间和教室。其中L是课程实体,它与教师实体和班级实体有关,即每门课程有其对应的任课教师和学习班级(每周两次以上的课看成是不同的课程);T×R表示时间和教室的笛卡尔积:

T×R={(T1,R1), (T1,R2),…, (T1,Rnr), (T2,R1), (T2,R2),…, (T2,Rnr), (Tnp,R1), (Tnp,R2),…, (Tnp,Rnr)}

可知 f(L1)=(Tx,RY)∈T×R,且Tx∈T,RY∈R

排课五要素中,课程是关键要素,其他的要素都与它有关系。排课问题是要求对所有课程找出使给定目标函数最优的分配方案。

2 离散粒子群优化算法

基本粒子群算法[8]及其改进算法[9,10]主要被用来求解连续论域的问题,实验证明它是一个非常有效的工具,具有模型和设计简单、直观、易操作、执行速度快、效率高等优点。但在实际应用中,很多问题被建模在离散空间中,如调度、路径、任务分配等问题。在离散问题面前基本粒子群算法就显得无能为力了。为了解决离散问题,人们对基本粒子群算法进行了改进。

Kennedy等于1997年提出了离散版二进制粒子群优化BPSO(Binary Particle swarm optimization)[11]算法。与连续的PSO算法相比,BPSO算法不仅在编码方式上有所改变,更重要的是算法中的速度向量不再是位置变化率,而是作为粒子位置改变的概率。

Clerc[12]提出了用于求解TSP问题的DPSO算法, 重新定义粒子位置和速度,将离散粒子群算法的运动方程描述为:

Vt+1=c1Vt⊕c2(Pit-Xt)⊕(Pgt-Xt)

Xt+1=Xt+Vt+1

Maurice Clerc针对非对称TSP问题brl7.astp对离散PSO算法的性能作了实验分析,结果表明了算法能够在一定程度上达到优化的目的。

黄岚等[13]针对TSP问题,给出了通过比较粒子与全局最优和该粒子历史最优的差别定义了交换子和交换序的概念,将交换序列作用于该粒子进行进化。并改变原PSO公式为

vid=vid⊕α(pid-xid)⊕β(pgd-xid)

xid=xid⊕vid

其中,α,β (α,β∈[0,1]) 为随机数。α(pid-xid)表示基本交换序(pid-xid)中的所有交换子以概率α保留;同理,β(pgd-xid)表示基本交换序(pgd-xid)中的所有交换子以概率β保留,⊕为两个交换序的合并算子。

文献[14]将离散粒子群算法用于解决无等待流水车间调度问题。作者认为粒子群算法的实质在于粒子根据自己和同伴的飞行经验不断调整位置和速度,从而向最优位置飞行。粒子的新位置是粒子的速度、个体极值和全局极值相互作用的结果,重新给出了粒子位置更新公式,引入了交换操作,基于典型算例的试验,证明了算法的有效性。

还有学者将粒子群算法与蚁群算法、模拟退火等进行结合,提出解决各种离散问题的混合算法。

3 改进的DPSO算法

本文在参考[12,13,14]的基础上设计了用于求解排课问题的DPSO算法,测试结果验证了本算法的可行性和有效性。

3.1 粒子的编码方法

结合排课问题涉及的要素和特点,采用了矩阵编码方式:

设一周有T个时间段可用来安排上课,有R个教室供使用。以R个教室作为行,以T个时间段为列构成一个二维矩阵,记为X[R,T],矩阵中每个元素即为课元编码,由教师、课程、班级三元素构成。这样就以矩阵的方式表示了一种排课方案,也可看成是一个粒子。因为排课方案受到许多约束条件的制约,所以并不是每个粒子都是满足要求的可行解,在初始化粒子时加以调整。

3.2 种群的初始化

粒子群中的每个粒子对应于待解决问题的一个可行解,因此在课程表问题中粒子的表示就是一个可行的解决方案,在数据结构上对应于一个二维数组。为了使初始粒子群具有较好的分散度且减少教室更换的次数,根据各课程的周学时数,随机的选择隔一天安排课程,其次选择隔两天安排课程,依次类推,最后选择相邻天安排课程,且在安排一门课时尽可能安排在同一个教室。在安排时要检查冲突的存在,形成一个可行解。重复构造出规定数量的粒子,形成初始粒子群。

粒子群粒子数量的大小M 对算法的运行效率和效果有一定的影响。当M 取值过大时会降低算法的运行效率;而M 取值过小时,可以提高算法运行速度,但降低了粒子群的多样性,算法易早熟收敛。

3.3 适应度函数

设x为某个可行的课表,X为所有可行课表组成的集合,我们建立如下适应度函数:

undefined

max(f(x)) x∈X

其中,x为某个可行的课表,X为所有可行课表组成的集合,ω1、ω2、ω3为相应的权值,其和为1。f1、f2、f3分别是满足课程分散度、时间利用率和教室利用率的适应度函数。

3.4 粒子位置更新操作

借鉴了交换序的思想,并引入遗传算法的交叉思想重新构造粒子位置更新公式,将粒子当前位置和该粒子的历史最好位置及全局最好位置进行遗传算法中的交叉操作,并对产生的新粒子进行局部交换,具体描述为如下公式:

Xi=c2⊗g(c1⊗g(Xi,Pbesti),gbest) (1)

Xi=ω×fa,b(Xi) (2)

其中,c1、c2、ω∈[0,1],(ω可取大于等于0.6的值);操作g(Xi, Pbesti)的含义是根据两者相同列的适应度值的大小关系以概率c1进行交叉;操作fa,b(Xi)是一个局部交换函数,含义是将Xi中每门课程根据所处的时间段在同一天内做局部调整,若此门课程所在时间段的时间利用率小于没有安排课程的时间段的时间利用率,且教室利用率大于ω,则交换这两个时间段的课程安排。

求解排课问题的离散粒子群算法的流程如下:

(1)初始化M、ω、c1、c2,令计数器k=0;

(2)随机初始化粒子群中粒子的位置,计算初始粒子的适应度值;

(3)令pBki=Xundefined;gBk设置为初始种群中最佳粒子的位置;

(4)判断算法收敛准则是否满足,如满足,则输出gBk,并由gBk得到最佳课表,算法结束;否则执行(5);

(5)对群体中的所有粒子进行如下操作:

①按公式(1)和公式(2)更新粒子位置;

②计算新生成的粒子的适应度值;

③如果粒子适应度值优于pBki,令pBki=Xundefined;

④如果粒子适应度值优于gBk,令gBk=Xundefined;

(6)k=k+1,转(4)。

4 算法性能分析

利用C#语言实现了基于离散粒子群算法的排课系统,并利用学校一学期的数据对算法性能进行了分析。

考虑到系统运行时间及粒子群数量对近似最优解适应度值的影响,本次测试选定粒子群数量为50,运行本排课系统并记录测试结果。表1给出了08-09第一学期部分测试数据及测试结果。

从表1不难看出,对于不同教学资源,本系统都可以得到适应度值较高的排课结果,且近似最优解的适应度值都好于初始粒子适应度值。同时,也可以看出对于教学资源不是太多的学院来讲,排课所需时间非常少。

通过计算传媒学院、商学院、计算机学院三个学院的适应度指标,可以看出人工排出的课表与该系统排出的课表在课程分散度、时间利用率、教室利用率和适应度值存在不同,各指标详见表2。

从表2可以看出,系统课表比人工课表有较高的课程分散度、教室利用率和适应度值,但在时间利用率上不如人工排出的课表高。这主要是由于人工排课在时间上的控制更加灵活,而利用系统进行排课会综合权衡各个不同的指标。

本文已实现了一个基于离散粒子群算法的排课系统,并得到了一些较好的试验结果。后续研究的重点是进一步扩大试验范围以及引入其他智能算法,进一步完善排课系统,真正解决高校的排课难题。

摘要：针对高校排课问题,提出了一种改进的离散粒子群算法。采用基于矩阵的编码方式,对粒子的位置和速度更新方法进行重新定义。利用C#语言实现了一个基于离散粒子群算法的排课系统。并以不同学院一个学期的课程表为依据对系统进行了评估,结果验证了粒子群算法在排课系统中应用的可行性,在一定程度上解决了高校复杂的排课难题,实现了智能化、人性化的排课过程。

基于改进粒子群算法的岸桥调度问题第7篇

岸桥作为集装箱码头前沿装卸集装箱的主要设备,其运作效率将直接关系到整个集装箱港口的运作效率。岸桥调度是给岸桥分配任务作业单元并确定先后顺序,使集装箱船舶能够尽快离开港口。

Daganzo( 1989)[1]提出多船装卸的岸桥调度问题,通过把集装箱船舶划分为多个船区,且要求在任何时刻某一船区最多只有一台岸桥对其作业,其目标为最小化所有集装箱船舶的累计延误成本。Peterkofsky和Daganzo( 1990)[2]利用分支定界法求解上述问题。这两篇文章的目标都是最小化船舶的延迟成本,但都没有考虑岸桥之间会互相干扰。

目前许多研究都是对已有岸桥调度模型进行优化以更加符合实际情况,同时利用不同的方法对模型进行求解,使得所设计算法能在集装箱码头可以容忍的时间范围内得到较优的装卸作业方案。

Kim和Park( 2004)[3]研究了单船的岸桥调度问题,以最小化岸桥最大完工时间以及总完工时间为目标,利用分支定界法以及贪婪随机适应搜索启发式算法进行求解。Moccia等 ( 2005)[4]考虑到岸桥在同一条轨道上运行,在岸桥移动时应注意干扰,由此构建了岸桥调度模型,并利用CPLEX求解小规模问题,利用分支定界法求解大规模问题。孙俊清等 ( 2007)[5]对Kim的模型进行修改,考虑了不同岸桥的装卸能力不同,以所有到港船舶的等候服务时间最短为目标,利用遗传模拟退火算法对其求解。韩笑乐等( 2009)[6]对岸桥作业调度问题的特殊性约束进行考虑,建立了考虑预定义顺序约束, 岸桥碰撞约束的数学模型,并利用启发式算法进行求解。 Legato等( 2012)[7]提出包含各种实际约束的模型,并利用分支定界法以及Petri网进行求解。Chung等( 2012)[8]利用改进的遗传算法对Kim的岸桥调度模型进行求解,利用次序杂交的方式对两部分编码进行交叉操作。Kaveshgar等( 2012)[9]利用遗传算法对Kim的岸桥调度模型进行求解,在初始种群规则中进行改善以提高运行速度,提出一种新的编码方式,使得维数减少且允许岸桥双向移动。范志强等( 2012)[10]考虑到不同岸桥的效率差异,并利用遗传算法对其求解。

2问题描述

集装箱船舶停靠码头后,集装箱码头会安排一定数量的岸桥对船舶进行装卸作业。岸桥调度就是合理安排作业单元的作业顺序使得岸桥的作业时间最短。出于对岸桥调度问题的实际作业考虑,将一个大贝内的作业根据舱盖板划分为集装箱箱组。并且同一个大贝内的作业顺序要符合先卸箱,后装箱的作业原则。岸桥也必须遵守干扰约束原则。

本文的QCSP基于以下几点假设。

1每台岸桥有且仅有一个作业单元为初始作业单元与终了作业单元。

2在任何时刻,一个作业单元只能容纳一台岸桥对其进行作业。

3岸桥一旦开始一个作业单元,就要直到完成该作业单元所有任务后才可执行下一作业单元。

3模型建立

本文以单船的岸桥调度问题为研究对象,为岸桥制定作业计划使得船舶的停靠时间最短,以获得最大的效益。模型符号参数如下所示。

i , j , k作业单元与岸桥序号;

n作业单元数量;

t岸桥相邻两个作业单元间的移动时间;

M一个足够大的正数

li第i个作业单元所在贝位

lck0岸桥k的起始贝位lckT岸桥k的终了贝位

lckT岸桥k的终了贝位

pi第i个作业单元的处理时间

rk岸桥k的最早可用时间

Ω 所有作业单元的集合

ψ 不可以同时进行作业的作业单元集合

φ 具有优先顺序的作业单元集合( 为了满足先卸船后装船,卸船先卸甲板上,装船先装船舱内)

决策变量如下所示,其中xkij为主要决策变量,其他为辅助决策变量。

Yk: 岸桥k的完工时间

Di: 作业单元i的完工时间

基于岸桥实际作业情况,建立如下QCSP模型。

目标函数: minf = max( Yk)( 1)

约束条件:

式( 1) 为目标函数,以最小化岸桥完工时间为目标,式( 2, 3) 表示每台岸桥都有且仅有一个作业单元作为初始与终了作业单元。式( 4) 表示每个作业单元都必须由一台岸桥独立完成。式( 5) 表示同一时刻,一台岸桥只可以为一个作业单元服务。式( 6) 表示对每台岸桥完工时间的约束。式( 7) 表示每台岸桥在对初始作业单元作业之前的最早可用时间约束。式 ( 8) 表示在同一台岸桥上两个相邻作业单元之间的时间约束。式( 9) 对作业单元的前后顺序做出作业时间的约束。式( 10) 表示岸桥在作业过程中不能交叉作业。式( 11) 表示作业单元不能同时进行的作业。式( 12) 表示在优先顺序集合内在作业单元的作业顺序约束。式( 13) 对模型中的0 - 1变量进行约束。式( 14) 表示对于任意作业单元及任何岸桥,作业时间一定大于等于0。

4粒子群算法

粒子群优化算法 ( Particle Swarm Optimization,PSO) 是Kennedy与Eberhart于1995年提出的一种全局优化算法,该算法的基本思想来源于对鸟群行为模拟,它模仿鸟类的觅食行为,将问题的搜索空间比作鸟类的飞行空间。将每只鸟抽象为一个粒子,用以表示问题的一个候选解。每个粒子根据它自身的经验和粒子群的最佳经验,在问题空间中向更好的位置飞行,如此循环搜索直到发现最优解。

在PSO算法中,粒子群在一个D维空间中搜索,粒子总数为n,粒子群的初始位置和速度随机产生,然后按照公式( 15) 和( 16) 进行迭代计算,直到满足终止条件,输出最优解。

其中c1,c2分为粒子的自学习因子与群体学习因子,r1,r2为服从0 ~ 1均匀分布的随机数,w为权重因子,vjt,xjt分为第t次迭代第j个粒子的速度与位置,而pbestjt,gbestjt分为第t次迭代第j个粒子的个体最优与全局最优位置。

由于较大的权重因子w有利于跳出局部最优,以便全局搜索,而较小的权重因子则有利于局部搜索,由于迭代初期最大的权重因子有利于快速寻找到最优解,而在迭代后期较小的权重因子有利于算法局部精确搜索,所以本文采用权重线性递减方法。

其中wmax,wmin分为w的最大值和最小值,通常取0. 9与0. 4,为最大迭代次数,itermax为当前迭代次数。

本文针对粒子群算法的岸桥调度问题进行编码设计,具体如下所示。

如图1所示为编码示意图,表示了六个作业单元的作业顺序以及分配的岸桥情况,其中编码的整数部分表示作业单元所分配的岸桥编号,而小数部分则表示同一台岸桥下的作业顺序,由小到大表示服务顺序的先后。

如图2所示,解码后可得出岸桥1负责作业单元d,e,a, 并且其作业顺序按小数部分由小到大排列。岸桥2负责作业单元b,f,c.

如图3所示为算法的执行步骤。

5算例分析

2台岸桥对一艘具有10个作业单元且分布在10个不同大贝上的船舶进行装卸作业。岸桥在相邻大贝间的移动时间为1min,两台岸桥的安全距离为1个大贝。利用本文提出的改进粒子群算法对算例求解得出如图4所示的收敛曲线以及如表1所示的结果。

由结果可知,本文所提出的粒子群算法对QCSP具有可行性与适用性。并且结果符合岸桥干扰约束以及作业单元优先约束。

6结论

本文针对单船的岸桥调度问题进行研究,建立符合实际作业情况的混合整数规划模型,以船舶的最大完工时间最小化为目标函数,并提出改进粒子群算法进行求解,提出一种新颖的解码方式。本文的研究对今后的岸桥调度问题以及整数编码粒子群算法研究具有一定启发意义,但还需要进一步深入研究,可以加大算例规模使其更有实际应用价值。

摘要：岸桥调度作为集装箱码头生产作业的一个核心环节,其工作效率将直接影响集装箱船舶的船期。合理安排岸桥作业,不仅能减少作业时间,保证船舶船期,更能提高码头装卸效率,提升码头竞争力以及维护船东与货主的利益。文中针对集装箱码头岸桥调度问题进行研究,根据现有文献以及调研结果建立符合实际的混合整数规划模型,考虑到岸桥的干扰约束以及作业单元的作业顺序约束,并利用改进的粒子群算法进行求解。

混合粒子群算法求解单机批调度问题第8篇

单机调度是生产调度问题的一种特殊形式, 半导体芯片的预烧、电路测试、港口货物装卸及金属加工等都属于该类型。在实际生产过程中, 对于大规模的生产活动, 需要进行批量处理, 机器在处理工件时, 可以将多个工件同时进行加工以提高生产效率, 降低生产成本, 这就是所谓的单机批调度问题。文献[2]首先提出了该类问题的单机器模型, 即单机批调度问题, 证明了该类问题的制造跨度问题是强NP问题。文献[3]求解极小化总完工时间的单机批调度问题, 提出了基于工件序列的蚁群算法和基于批序列的蚁群算法。文献[4]研究了单机环境下工件尺寸有差异的批调度问题, 并设计了一种改进蚁群算法对问题的制造跨度进行优化。文献[5]采用模拟退火方法求解最小化最大完工时间的单机批处理调度问题。随着单机批处理调度问题研究的深入, 对于调度问题的约束条件也越来越多, 工件动态到达的单机批调度问题的研究也己逐渐成为一个很有价值的研究方向。但是目前研究工件动态到达的单机批调度的文献很少[6,7], 并且在生产调度问题的优化研究方面, 应用智能优化算法来改进求解的质量仍存在不足。文献[8]利用分批的启发式规则产生初始种群, 然后重新设计了交叉算子和变异算子以优化制造跨度。但遗传算法的求解性能依赖于种群规模, 因此在解决大规模问题时收敛性能较差。文献[9]中微粒群算法在对批调度问题求解时, 主要是使用工件序列对解进行编码, 将改进操作放在成批阶段, 对微粒群算法得到的工件序列釆用动态规划算法进行改进。上述启发式方法不能充分考虑问题的约束条件, 难以找到最优解, 因此, 另外一些学者采用了性能更优的元启发式算法 (meta-heuristic algorithm) 。文献[10]提出了求解最小化最大完工时间的单机批处理调度问题的启发式算法和蚁群算法, 并且考虑了工件尺寸不等和动态工件到达的约束条件。文献[11]利用蚁群聚类算法求解工件具有不同到达时间的单机批调度问题。上述算法虽然能在一定程度上有效求得问题的优化解, 但是随着迭代次数的增加, 算法容易陷入局部最优, 降低算法的收敛速度。因此笔者提出利用混合粒子群算法来求解工件动态到达的单机批调度问题, 并引入自适应策略和惯性权重正弦函数, 防止算法陷入局部最优, 同时也提高了算法的收敛速度。

1 数学模型*

单机批调度问题描述如下:工件到达之后, 在满足机器容量Bmax和工件到达时间的约束下, 可以将多个工件作为一批同时进行加工, 并且只有加工时间相同的工件才可以加入同一批中, 同一批工件具有相同的开始和结束加工时间。从一批开始加工直到该批加工完成, 该过程不允许中断, 也不允许有工件中途退出或加入该批, 因为同一批中的工件由一台机器进行加工, 具有共同速度, 所以批加工时间由批中工件的加工时间最大的工件决定。到达时间、交货期都是已知的。

根据上述描述, 所求问题的数学模型和约束条件为:

优化目标函数为:

其中, Rb、Pb、Sb、Cb分别为批b的释放时间、加工时间、开始加工时间和最大完工时间;di、ri、Ci、Li分别为工件i的交货期、释放时间、最大完工时间和最大拖期时间;Lmax为最大拖期时间;约束条件 (4) 表示批b的开始加工时间要大于批的到达时间, 约束条件 (5) 表示第nb个批工件个数不超过Bmax, 约束条件 (6) 表示批加工时间等于批中工件最大加工时间。

单机批调度问题可以分为两个过程:工件成批和批的加工。工件成批主要是对工件到达时间按升序排列后, 在满足机器批容量的前提下, 已到达工件中加工时间相等的工件加入一批, 否则新建批。分批完成后将工件分配到批处理机进行加工, 得到目标函数。

2 算法设计

2.1 标准粒子群 (PSO) 算法描述

基于微粒群优化算法独特的搜索机制, PSO算法首先在可行解空间和速度空间随机初始化微粒群, 即确定微粒的初始位置和初始速度, 通过评价各微粒的目标函数, 确定t时刻每个微粒所经过的最佳位置pi和群体最佳位置pg, 再按下列公式分别更新各微粒的速度和位置:

式中c1———自身经验学习因子;

c2———社会经验学习因子;

r1、r2———[0, 1]之间的随机数;

w———惯性权重因子。

2.2 混合粒子群算法

由于所求调度问题是离散的, 所以采用基于工件序列的编码方式可以更好地表达问题的解。为了保证编码策略不遗漏问题的全局最优解, 并使优化操作满足状态的可行性和合法性, 设计一种针对随机键编码的基于升序排列 (ranked-ordervalue, ROV) 的操作, 用于实现从微粒的连续位置矢量到工件排序的转换。假定有6个工件的调度问题, 设根据NEH启发式算法和随机方法产生粒子位置[1.9, 1.8, 0.7, 3.5, 2.4, 1.2], 采用ROV规则, 基于升序排列得:4, 3, 1, 6, 5, 2, 所得排列即工件的加工序列。

在式 (8) 中, 由于粒子速度向量vi本身具有随机性和盲目性, 导致算法收敛性较差, 无法快速寻找到新的解区域。在考虑实际优化问题时, 求解最优解的思想就是首先通过全局搜索, 快速收敛于某一新的解空间, 然后采用局部搜索来获得高精度的解。惯性权重因子w是一个控制参数, 不仅控制本次飞行速度对下次飞行速度的影响程度, 还体现着粒子群优化算法对全局搜索与局部搜索的平衡。因此合理地选择有利于更好地平衡算法的全局搜索能力和局部搜索能力, 协调算法的搜索精度和收敛速度。在迭代初期阶段, 希望有较高的搜索能力以探索新的解空间跳出局部极值, 而在后期则重视局部开发以加快收敛并发现精确解, 通过对粒子群算法中惯性权重的分析, 提出了一种惯性权重正弦调整方法来改进粒子群算法中的惯性权重[12], 以改善粒子群算法的收敛速度和全局收敛性。为了防止算法陷入局部最优, 在改进算法的基础上引入自适应变异全局极值的变异操作来开发算法跳出局部最优的能力[13]。

2.2.1 惯性权重正弦调整

首先对由式 (8) 、 (9) 组成的系统进行稳定性分析。为便于表达, 把式 (8) 、 (9) 中的问题简化为一维, 记φ1=c1r1, φ2=c2r2, 则粒子i的运动状态方程为:

根据文献[14]所得结论可知:

对式 (8) ~ (10) 化简, 可知粒子的速度变化过程是一个二阶差分方程:

粒子的位置变化过程也是一个二阶差分方程。将粒子速度变化过程看成是一个时间连续过程, 对时间求导得到一个典型的二阶差分方程:

其中e1、e2为方程λ2+ (φ1+φ2-1-w) λ+w=0的根。根据式 (14) 解的一般形式可知, 当粒子的速度趋向无穷大时, 粒子的运动轨迹是发散的, 导致整个粒子群的运动轨迹是发散的, 粒子速度变化过程的稳定性对整个粒子群行为有着重要影响。假定φ1、φ2为常数, 那么式 (13) z变换后的系统方程则可看成是一个线性系统, 其特征方程为:

对式 (15) 作双线性变换, 将z= (μ+1) / (μ-1) 代入式 (15) 化简得:

特征方程的所有零点均在z平面上一个以原点为圆心的单位圆内, 这是二阶线性系统稳定的必要条件。由罗斯判据可知二阶线性系统稳定的充要条件是特征方程各项系数均为正值, 可得式 (13) 稳定的条件为:

由于φ1、φ2为正实数, 所以在不考虑随机量且个体最优值、全局最优值位置不变的情况下, 单个粒子速度变化过程稳定的条件由式 (17) 的后两个不定式决定, 且两个条件不能同时取等号, 满足条件时单个粒子的速度将趋向于0。用同样的方法对粒子位置变化过程进行分析, 得到粒子位置变化过程稳定的条件:

较大的w值有利于跳出局部最优, 进行全局寻优;较小的w值有利于局部寻优, 加速算法收敛。笔者提出一种正弦调整的粒子群算法惯性权重:

令φ1=[w (k) +1]r1, φ2=[w (k) +1] (2-r1) r2, r1、r2为均匀分布在 (0, 1) 区间的随机数, 式 (17) 、 (18) 所有条件均可得到满足, 从理论上说明了粒子群算法的收敛性能。由正弦变化规律可知w值的变化对算法的影响, 在算法开始时粒子在其自身附近作局部寻优, 在一定时期后粒子的搜索范围逐渐增大, 进行全局寻优, 最后让最优粒子进行局部搜索。

2.2.2 自适应变异全局最优值

如果粒子群优化算法陷入早熟收敛或者达到全局收敛, 粒子群中的粒子就会聚集在搜索空间的一个或几个特定位置, 群体适应度方差σ2等于零。设粒子群的粒子数目为n, fi为第i个粒子的适应度, favg为粒子群目前的平均适应度, 根据适应度函数, 适应度方差定义为:

其中f是归一化定标因子, 其作用是限制σ2的大小。令:

由于粒子在当前全局最优值g Best的作用下可能发现更好的位置, 因此新算法将变异操作设计成一个随机算子, 即对满足变异条件的g Best按一定的概率pm变异。pm的计算公式如下:

其中, k=rand (0.1, 0.3) ;σd2的取值与实际问题有关, 一般远小于σ2的最大值;fd可以设置为理论最优值。

对于g Best的变异操作, 算法中采用增加随机扰动的方法, η是服从Gauss (0, 1) 分布的随机变量, g Best的第k维全局极值变异公式为:

首先判断算法是否满足收敛准则, 如果不满足, 对粒子进行位置和速度的更新, 判断此时粒子适应度值是否满足fi<p Best, gi<g Best, 若满足, 则更新粒子位置。计算群体适应度方差σ2, 并计算全局最优位置的适应度值和pm。如果随机数r<pm, 则按照式 (23) 完成变异操作。

3 实验设计与仿真

为了验证改进算法的性能, 实验中随机产生测试算例, 其中机器容量为3;工件数J[i]分别为20、50、100、150;加工时间服从t1=[0, 20]、t2=[0, 10]均匀分布;设置参数α和β分别用来控制工件的释放时间分布和交货期分布的松紧程度, 其值分别为0.2和3;算法中最大迭代次数和种群规模都为100;w、v和x的取值范围分别为[0.40, 0.91]、[-4, 4]和[0, 4];函数unifrnd (0, a) 取 (0, a) 之间的随机数, ri=unifrnd (0, αCmax) , di=ri+unifrnd (1, β) pi, 这里暂不讨论参数对算法的影响。

笔者将遗传算法 (GA) 与提出HPSO算法进行比较, 运行在Windows XP系统、CPU E66003.06GHz、内存1.96G的台式电脑上。所有算法采用Matlab编程, 每种算例运行30次。笔者对运行结果和运行时间从最差值、最优值、平均值及百分比偏差 (百分比偏差= (L (HPSO) -L (GA) ) /L (GA) ) 等方面进行比较, 比较结果见表1、2。

从表1、2中可以看出, HPSO算法要明显优于GA算法, 随着问题规模的增大, HPSO算法的解与GA算法的差距更为明显, 显示了很好的稳定性。在运行时间上, HPSO算法在所有算例上的求解时间均小于GA算法, 随着问题规模的增大相对GA算法有着更快的收敛速度。为了更直观地看出算法的性能优劣, 分别用折线图和条形图描述了算法均值百分比偏差和标准差的分布情况 (图1、2) 。

由图1可知, HPSO算法相对GA算法有一定的改进, 但对于J1t1算例均值百分比偏差出现不稳定的状态, 对于大部分算例是随着问题规模的增大效果越明显, 而且两种不同加工时间下相比较, 改进比较稳定。对于运行时间的改进则表明, 随着问题规模的增大, 改进效果越明显, 表现在算例中则是收敛速度变大。总体来说HPSO算法更能适应复杂的调度环境。

由图2可以看出, 除了算例J3t1和J3t2的标准差出现波动外, HPSO算法的标准差均比GA算法的小, 表明HPSO算法的寻优能力比GA算法寻优能力强, 能够跳出局部最优区域。标准差表明组内算例间的离散程度, 也就是算例结果偏离平均值的程度, 同时反映数据波动范围大小, 能不能在有限的迭代次数内寻到最优值。由此可知, HPSO算法所得数据波动范围较小, 更适合对此类调度问题分析。

4 结束语

笔者提出了一种基于工件动态到达求解批调度问题最大拖期时间的改进粒子群算法 (HP-SO) 。该算法在标准PSO算法的基础上引入了改进的惯性权重正弦调整, 改善了算法的收敛速度和全局收敛性。为了防止算法陷入局部最优并增强粒子群优化算法跳出局部最优解的能力, 在改进惯性权重算法的基础上引入自适应变异全局极值的变异操作来寻找全局最优解。采取工件序列对应粒子位置的编码方式, 通过实验表明, 在求解基于工件动态到达的单机批调度问题上, 无论从寻优能力还是运行时间方面, HPSO算法的性能要优于GA算法性能。笔者应用改进算法求解的是单机调度问题, 对于应用此算法求解基于工件动态到达的多机批调度问题还有待进一步研究。

摘要：设计了一种混合粒子群算法 (Hybrid Particle Swarm Optimization, HPSO) 以求解基于工件动态到达的最小化最大拖期时间单机批调度问题。该算法在标准粒子群算法的基础上引入了惯性权重正弦调整, 以改善标准粒子群算法的收敛速度和全局收敛性, 然后采用自适应变异全局极值算法增强粒子群优化算法跳出局部最优解的能力, 防止算法陷入局部最优。应用改进的算法对实验设计问题进行求解, 证明了改进算法的有效性。

粒子群算法的边界问题第9篇

随着网络化的发展,越来越多的企业需要联合才能解决复杂的制造问题,于是在制造业中引入了网格技术,这样为制造业提供了一个公共的制造网格平台。制造网格将分散在全球范围内的闲散资源和优势资源封装为网格节点,向用户提供统一的资源访问人口和透明的资源服务,来快速形成资源配置系统,满足企业对资源共享的要求。

基于制造任务协调和共享制造网格环境下的资源,是促进制造网格技术趋于应用必须面对的问题。文献[2]提出了基于层次分析法的制造网格资源调度方法,通过建立多目标、多层次模型来选择满足用户需求的制造资源,但由于层次分析法自身的缺陷导致决策结果与实际情况相差较远,不能很好地解决制造网格中的资源调度问题。文献[3~4],根据制造网格的特点,结合用户对制造任务时间(T)、质量(Q)、成本(C)、服务(s)等的要求,建立了制造网格资源调度数学模型,设计并实现了基于遗传算法的制造网格资源调度过程。

量子计算利用量子世界的叠加态、相干性和纠缠性等特点,使得量子信息系统能突破经典信息系统的极限,目前采用量子计算解决经典计算中的NP完全问题成为研究热点。本文将量子算法与基本微粒群算法结合起来,提出了量子粒子群算法,该算法既利用了量子算法的并行性,又吸取了基本微粒群算法的全局搜索的特点。通过仿真实例验证,表明将量子粒子群算法应用于求解制造网格资源调度这一NP—Hard问题,效果良好。

1 制造网格资源调度问题描述

制造网格中资源调度的目标是通过合理地分配各资源到不同的处理单元上,并且安排好每一处理单元上任务的执行顺序,而使总任务的执行按用户的要求达到最优。根据制造任务类型,将制造任务分解成多个子任务的集合,直至每个子任务都可以由相应的RSF来完成。制造资源调度方案(MRSP)就是由这些制造网格资源服务工厂(RSF)组成的有序序列。该问题的基本数学描述如下:(1)设一个任务需要n种不同的工序,每一项工序由一种特定的机器完成,这台机器又有一系列的不同成本、不同完工时间和不同运输路程的可选资源。(2)这些资源在地理上是分散的。(3)每个类别的资源仅可能在可选资源中选择一个。

在本文中,设定制造网格资源调度的目的就是使整个任务的制造过程在平均时间内所消耗的制造成本最低。实现这一目标,需要尽量保证:总的资源成本最小,总的运费最少,任务完成时间最短,资源在各工序间的传输时间最短。因此,制造网格资源调度过程是一多目标优化问题,其主要的优选目标函数可以表述如下:

(1)总的资源成本最小

(3)总的任务完成时间Ty最短

2 制造网格资源调度问题的量子粒子群算法设计

2.1 量子粒子群算法基本原理

为了改善微粒群算法的缺点我们在原有的微粒群算法的基础上中引入量子算法,提出量子微粒群算法。

量子算法能够通过一个量子比特表征量子的多种状态,一位的量子比特可以体现两种状态的叠加。其中,表示状态|0>,|1>取的概率,因归一化条件的约束,要满足等式。问题的解采用量子比特编码,一个m位的量子比特可以标识各种可行状态,每个状态的形成概率由幅度的乘积来衡量。这就使得算法具备了强大的邻域搜索能力,将量子的这种搜索邻域的功能和微粒群算法通过跟踪极值更新粒子的功能结合,能够改善粒子群算法后期搜索速度慢的问题。

QPSO采用下面的公式对粒子进行操作的。

在QPSO中,首先初始化参数,包括种群数量N,它表示每次迭代运算时都产生N个工件的调度顺序,即N个粒子形成一个种群;迭代次数t,表示粒子的运动次数;加速系数c1和c2,它们代表将每个粒子推向其个体历史最好位置和全局历史最好位置的统计加速项的权值,一般取值为2;惯性权重ω,它表示保留自身速度的权值,一般0.8<ω<1.6。人为设置粒子的初始速度和最大速度,最大速度用以控制粒子在合理区域内运动;设置初始角度θ,一般设置为45°,那么所有粒子的量子比特位都被初始化为,这就意味着所有可能的叠加态以相同的概率出现。根据角度,产生Qt,Qt表示第t代粒子群量子比特对应的概率矩阵。Qt通过随机观察生成,具体操作过程如下:随机产生一个[0,1]之间的随机数,若它大于Qt,则对应的Pt粒子的量子比特位取值为1,否则取值为0。根据生成的Pt产生n个粒子,并计算出该状态下的适应值,然后进行迭代更新,粒子根据个体历史最好位置和全局历史最好位置不断的更新自己的原有的速度,从而改变搜索角度θ,也即更新了Qt和Pt,最终也更新了种群中的粒子的位置,使得粒子向目标值靠拢。

2.2 量子粒子群算法的基本流程设计

量子粒子群算法的基本流程设计如下图所示:

2.3 制造网格资源调度问题的量子粒子群算法设计的关键内容

(1)编码方式。本文采用基于整数的编码方式,每一维表示一个可选的调度资源,这样,每个编码串就可表示一个制造网格资源调度优化方案。

(2)适应度函数的选择。制造网格中资源调度问题是一个多目标优化问题。工程中经常会遇到在多准则或多设计目标下决策的问题,需要找到满足这些目标的最佳设计方案。解决含多目标和多约束的优化问题,通常的做法是根据某效用函数将多目标合成单一目标来进行优化。一般情况下,满足所有目标都是最优的结果是不存在的,只能根据用户对各优化目标不同权重的要求得到相对较优的结果。因此,在用户提交任务详细信息的同时提交用户对y(资源成本)、f(资源加工耗时)、P(资源的地理位置编码)不同重要程度的要求,即目标权重分别记为Qy(资源成本权值)、QA(运费权值),其中Qy+QA=1。适应度函数一般是由目标函数变换而成的。本文采用基于用户目标权重的适应函数,目标函数如下所示:

U(x)表示一项任务在单位时间里所消耗的制造成本。适应度函数f(x)可表示为:

2.4 制造网格资源调度问题的量子粒子群算法具体步骤设计

Step1:首先对种群中粒子进行初始化。根据初始角度,得到粒子群量子比特对应的概率矩阵Qt,随机产生一个[0,1]之间的随机数,后进行判断:若此随机数大于概率矩阵Qt,则对应量子比特位取值为1,否则取0,得到基于0,1编码的矩阵Pt,后根据Pt排序得到基于整数的编码矩阵,即得到一个制造网格资源调度方案;

Step2:随机初始化粒子速度V[n][i];

Step3:计算每种调度方案下的适应函数值。通过对这些适配值的比较得到最大的适配值,作为粒子的全局最优解;

Step4:循环迭代,直到满足终止条件。

Step4.1:对每个粒子,依据公式

Step4.2:根据新的Pt得到新的制造网格资源调度方案,并计算出该方案下的适配值,得到新的粒子最好位置和种群最好位置。

3 算例仿真及性能分析

将本算法在数字制造业中实例化。某数字制造工厂中加工一个零件,需要6道工序(钳工、切削加工、车工、铸工、铣工、数字加工)分别有5、6、4、4、6、5个可选资源,调度的目的是使整个加工任务在单位时间内消费的制造成本最低。可选资源的基本信息如表1所示,位置编号对应的实际城市如表2所示,资源在各城市运输所消耗的时间和费用如表3所示。

对以上算例,分别应用遗传算法、量子粒子群算法进行求解,求解对比情况如下:

结论:通过以上具体实例的仿真模拟,可以看出,在求解制造网格资源调度这类NP-Hard问题时,量子粒子群算法体现出了比遗传算法更好的收敛性能,并得到了比遗传算法更优的调度方案。

4 结束语

针对制造网格资源调度这类问题的特点,本文引入量子粒子群算法这种运算速度高、全局性能好、收敛速度快的优化算法,进行了求解。首先设计出了制造网格资源调度问题的量子粒子群算法的求解步骤,并通过具体的仿真实例,对该算法的可行性和有效性进行了验证,结果表明,在求解制造网格资源调度问题时,量子粒子群算法能获得比遗传算法更好的效果。

摘要：对制造网格资源调度问题进行研究,提出了一种收敛速度快、全局性能好、不易陷入局部最优的智能迭代算法-量子粒子群算法来实现对该问题的求解。该算法采用整数编码方式,将网格资源调度问题转化成准连续优化问题,并采用加权目标组合的方式处理多目标条件。最后通过具体实例,对该算法进行了仿真验证,结果表明,在求解制造网格资源调度这类NP-Hard问题时,量子粒子群算法能获得比遗传算法更优的求解效果。

关键词：量子粒子群算法,制造网格,资源调度,多目标优化

参考文献

[1]张传顺,莫蓉,石胜友,常智勇,陈泽峰.基于遗传算法的制造网格资源调度方法研究[J].中国机械工程.2006,17(18):1916-1919.

[2]刘丽兰,俞涛,施战备.自组织制造网格及其任务调度算法[J].计算机集成制造系统—CIMS.2003,9(6):449-455.

[3]马雪芬,戴旭东,孙树栋.面向网络化制造的制造资源优化配置研究[J].计算机集成制造系统—CIMS.2004,10(5):523-527.

[4]冯蔚东,陈剑,赵纯均.基于遗传算法的动态联盟伙伴选择过程及优化模型[J].清华大学学报.2000,40(10):120-124.

[5]廖莉莉.遗传算法在制造网格资源调度中的应用[J].武汉理工大学学报.2007,29(12):123-125.

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【粒子群算法的边界问题】相关文章：

协同粒子群算法06-07

基于粒子群算法的DBSCAN聚类算法研究12-23

协同粒子群优化算法08-08