针对粒子群算法易早熟的缺点, 提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态, 在发现粒子出现停滞或者粒子群出现早熟后, 及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异, 变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束, 增加粒子的多样性, 从而克服粒子群的早熟现象。同时, 为了使算法能更快找到或逼近最优解, 采用了循环迭代策略, 在阶段优化结果的基础上, 周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题, 并在问题求解时与几个具有代表性的算法进行了比较。结果表明, 提出的算法能够克服粒子群早熟, 在求解质量方面优于其他算法。
2030· 计算机应用研究 第29卷 的增加,在对P。利用I算法进行变异后,得到的新解优于原最住相对误差,即算法运行得到的最佳值Cmx与问题理论最优 来解的概率降低。为此,本文在对P进行变异之前,首先对其解的相对误差,最相对误差为(Cm-C*)C×100%。由 进行局部搜索,然后利用G算法对其进行变异。对变异后的表1可以看出,对于问题规模较小的Car类问题,所有算法均 P。同样按照模拟退火思想进行概率接收。 能计算得到最优解;在所选择的Rec类问题的14个实例中,除 2.3交叉操作 了在Rec37问题上, PSO-EDA_PI算法优于木文算法外,对于求 本文采用部分交又策略,即在第二个串中随机选择一个交解的其他实例,本文算法明显优于其他算法,且在Re13 叉区域,将串2中的交叉区域加到串1中对应的位置,删除串c19、Hce29间题实例上,其他算法都未能计算得到最优解 1中已在串2的交义区域出现过的作业 而本文算法获得了最优解。从算法的求解质量上看,本文算法 2.4混合粒子群算法求解PFSP问题步骤 要远优于其他算法。 表1相关算法所得结果比较 木文提出的混合粒子群算法在解决PFSP时的流程如下 )设置参数。设置的参数包括算法迭代次数gmmm、种群个数。 nN 文献7]文献[14] PSOMA PSO-FDA_P本文算法 b冫种群初始化。利用rand()%n隨机产生粒子的位置和速度。 7038 0 0 e)更新个体最优和仝局最优。 47100 P4=x:(0),Pg=P1(0)&&Cax(P:(0))=min=1(Cm(P(0)) Car3 7312 0000 whle(循坏次数A<预设伯CYC)do 0 Cars 7720 while(迭代次数< genus)do 8,985050 d)根据式(8)(9)更新粒子的位置和速度 000 0000000 0 6590 0 e)更新粒子的P和P。若Cmx(X(k))<Cm(P1),P:=x(k) 8355 0 将记录粒了停滞代数的计数器 count清零;否则 count加1。若cont达 刭规定值,则利用IG算法对x(k)实施毁坏和构造换作,得到新的工 Ree1320,1519300.2070.1000.2590.104 件加工序列,依照2.2节方法a)接收新的个体极值。所有粒子的个体 20.15 0 极值更新后,若ming=1(Cm(P2(h))<CmP,则更新Pg,PB= 30,102093 .430.287 0 Pi(h)&&Cma(pi (k))=mini(Cmax(P (h))) 0.74 f)若P(h)=P(h-1),则使记录粒子群全局极值停滞代数的计 30,1020110.1490.1490.5960.398 效器CPes加1,否则将CPss清零。若CPs达到预定的值则按照 0.875 2.2节方法b)对Pk实施IG算法的毁坏和构造操作;同时,为了增加种 0.159 群多样性,选出粒子群中最差的1/3个体,对其实胞IG算法的毁坏和 Rec2730,1523730.33 0.420 1.348 0.969 0.253 构造操作,并利用模拟退火思想概率接收得到的新个体。 22871.8360.5201 g)迭代次数k=k+1。若k< genus,则进入下一次迭代继续执 Rc3150,1030450.3281.8391.510.263 0.263 行;香则迭代结束,根据当前P计算完⊥时间,输出本次循环最优解。 Re350,1031140.2890.220 0 end while(迭代次数k< gennum) 50 n)判断种群是否早熟。若本次循环中P与上次循环中得到的P Ree3775,2 4951 2.444 l.838 相等,则计数器num加1,否则num置为0。如果num运到预设的值 75,2050871.376 1.5530.924 则说明算法已经停滞很难再找到更的解,为此,需要重浙增加种群多 样性。方法为:对本次循环得到的P采用逆转策略进行变异,即在P4结束语 1,…,逆序插入到原来,1+1,…,氵的位置,其余不变。经过一次 变异后得到新的粒了,重复执行n次,这样得到新的粒了和群。 本文针对置换流水车间调度中求解最小化最大完工吋间 )λ=λ+1,若λ<CYC,则转c)继续执行;否则,程序结束,输出问题进行了研究,并结合1G算法,提出了一种混合SO算法 CYC循环中得到的问题最优解。 通过与文献[7,14]所提出的算法以及 PSOMA算法、 PSO-EDA end while(循环次数A<预设宜CYC P算汰等具有代表性的算法进行比较,验证了该算法在求解 2.5算法复杂度分析 质量上的优越性。但是,由于增加了粒子的多样性,粒子的收 依据上述算法描述,算法中关键步骤的复杂度分别是 敛速度较慢,得到问题最优解时迭代次数和循环次数较大,在 a)lG算法的构造操作,其复杂度为O(n)。 算法执行时间上比其他算法高。因此,减小算法的执行时间 b)设算法中粒子群大小为P,迭代次数为G,粒子群算法提高算法寻优效率将是进一步研究的内容。 的复杂度为O(P×G×n)。 参考文献: 忽略次要步骤的影响,本文提出的混合粒子群算法的时间 1 GAREY M R, JOIINSON DS, SETIII R. The complexity of flow 复杂度为O( n xGa)+O( PxGxnxn),其中λ为循环次数。 shop and job shop scheduling[ J]. Mathematics of Operations Re- search,1976,1(2):117-129 3算法测试 [2 EBERHART R C, KENNEDY J. A new optimizer using partiele 算法基于VC++6.0实现,在处理器为 Pentium1.6GH, swarm theory[ C]//Proc of the 6th International Symposium on Micro 内存为1.5GB的PC机下运行。设置的关键参数为:粒子群 Machine and Human Science. 1995: 39-43 「3高尚,杨静宇.求解流水作业调度冋题的混合粒子优化算法 大小取为50,迭代次数 gennum=500,循环次数CYC=200。 []/中国控制与决策学术年会论文集.2006:1006-1008 为了检验算法的有效性,本文选择由 Earlier12提出的car 「4田野,刘大有.求解流水车间调庋问题的混合粒子群算法「J1.电 类问题和Rves3提出的Re类问题进行测试,并与文献[7] 子学报,2011,39(5):1087-109 所提出的并行粒子群算法与模拟退火算法的混合算法、文献[5]宁正元,林大辉,李丽珊,等,置换流水车间调度问题的离散粒子 [14]所提出的改进微粒群算法、POⅥA算法、 PSO-EDA P 群优化算法[冂].集美大学学报:自然科学版,2008,13(2):97- 算法8进行了对比,比较结果如表1所示。表1中结果指的是 (下转第2034页) 2034 计算机应用研究 第29卷 择概率上的影响参数α=0.5,路径长度对选择概率的影响参 olumns 39 through 76 数β=5,蚂蚁每次更新的信息素数量为1,最高迭代次数为 383736>5152543944135,4243)3334 100次。利用基本蚁群算法仿真的结果如图2和3所示 32→31-30→2928→1948→27→5 13→2-6-7-8-9→10 0.6 lI→12-16-15-14→3-18 555 0 shortestlength =0. 5057 7∴ 0.64 45.76 ∴ 从实例仿真中可以看出,改进的蚁群算法相对于基本蚁群 45.75 算法迭代次数更少,能够以更快的速度收敛到全局最优解;求 45.74 0.54 解方面,改进的蚁群算法找到的最短路径为0.5057,基本蚁群 0.52 45.72 0. 算法找到的最优解为0.5192,其解的质量也有所提高。说明 26.6126.64126.68126.72 0102030405060708090100 图2用基本蚁群算法的 图3用基本蚁群算法求得的每次 改进的蚁群算法跟一般的蚁群算法相比不仅操作简单,而且收 仿真路径 循环平均路径长度和最短路径长度敛效果好、收敛速度快、全局收敛率高。 结果显示,仿真求得的最短路径为 columns 1 through 38 5结束语 62-61→75-63-6059→58→47→57→56-55→54→53-49 本文对基本蚁群算法进行改进,包括参数的改进、信息素 45+46-3940→2930→35-42→43→33→31→32→34-41→28→ 19-48-38-437-50→51-52→36 更新策略的改进、信息素挥发因子的改进等,设计出新的改进 蚁群算法。利用改进的蚁群算法求解ⅤRP,并利用 MATLAB 27s132,678心1on11216,15143,软件进行仿真,以哈尔滨市地图为模型验证了改进蚁群算法的 184-20-21-2326-70-76-736925→22-6-72→1-有效性。仿真结果表明,改进的蚁群算法是可行、有效的。 6724-1766-65-64+74 参考文献 shortest length =0.5192 LⅠ」宋留勇,王锐,周永旺,等,动态堿市交逍网络优化模型硏究及算 冋样的参数设置,利用改进的蚁群算法对哈尔滨市地图上 法设计[J].测绘科学,2011,36(1):134-136 的交通节点进行遍历仿真,得到的仿真结果如图4和5所示。[2]钟石泉,贺国光有时间窗约来车辆调度优化的一种禁忌算法 [J].系统工程理论方法应用,2005,14(6):523-527 0.68 [3 CHAO Yi-ming. A tabu search method for the truck and trailer 0.64 0.62 ting problem.J]. Computer and Operations Research, 2002 45.76 45 0.58 4 CHieN YaD-rong, LIANG Bo, ZllOU Mei-hua Optimization for vehicle scheduling in iron and steel works based on semi-trailer swap transport 4516.6126.6412563126.720.810203050607080900 LJ」.中南大学学报:英文版,2010,17(4):873-879, 图4用改进蚁群算法的图5用改进蚁样算沄求得的每次 [5]唐炉亮,常晓猛,李清泉,等.基于蚁群优化算法与出細车GPS数 仿真路径 循环平均路径长度和最短路径长度 据的公众出行路径优亿[J,中国公路学报,2011,24(2):8-5 结果显示,仿真求得的最短路径为 [6杨中秋,张延华改进蚁群算決在交通系统最短路径问题的研究 lumns 1 through 38 「J1.科学计算与信息处理,2009,32(8):76-78 4→+2021-23→26→70→7673-69252217→24→6717」 DORIGO M, GAMBARDELLA L M. Ant colony system: a coopera 71→7268-66-65-6474-75→62→61→63—60-59-58→47→ tive learning approach to the traveling salesman problem[ J.IEEE 5756-55-46--45-49→53-50→44 Trans on Evolutionary Computations, 1997. 1(1): 67-68 (上接第2030)页 [6」刘志雄,严新平,赵润罕,置换流水乍间凋度粒子群算法与参数设 greedy algorithm for the flowshop scheduling problem with blocking 買分析[冂].武汉理二大学学报:文通科学与工程版,2010,34 [J]. Omega,2011,39(3):293-301 (6):1129-1132 [Il] RUIZ R, STUTZLE T. An iterated greedy heuristic for the sequence [7 SUN Kai, YANG Gen-ke. An effective hybrid optimization algorithm dependent setup times flowshop problem with makespan and weighted for the: flow shop scheduling problen[C]//Prc of IEEE International tardiness objectives[J]. European Journal of Operational Re Conference on Information Acquisition. 2006: 1234-1238 search,2008.187(3):1143-1159 8 LIU Hong-cheng, GAO Liang, PAN Quan-ke. A hybrid particle 12 CARLIER J. Ordonnancements a disjonctives contraintres J. Oper swarm optimization with estimation of distribution algorithm for solving ations Research, 1978, 12(4): 333-351 permutation flowshop scheduling problem. I]. Expert Systems with [13. REEVES C R. A genetic algorithms for flowshop sequencing[ I] Applications,2011,38(4):4348-4360 Computers Operation Research, 1955, 22( 1): 5-13 [9] RIOZ R, STUTZLE T. A simple and effective iterated greedy alg-[14』刘迮风,刘三阳.改进微粒群优化求解置换流水钅间调度问题 rithm for the permutation flowshop scheduling problem[J]. Euro J].计算机集成制造系统,2009,15(10):1968-1972 pean Journal of Operational Research, 2007, 177(3): 2033-[15 LIU B, WANG L, JIN Y. An effective PSo-based memetic algorithm 2049 for flowshop scheduling[ J]. IEEE Trans on Systems, Man, and [10 RIBAS L, COMPANYS R, TORT-MARTORELL. X. An iteralerl Cybernetics, Part B: Cybernetics, 2007, 37(1): 18-27