混合果蝇算法求解分布式异构并行机调度

发布时间：2021-09-04 21:19

　　以工业生产中面临的实际生产问题为背景,提出了分布式异构并行机的调度问题模型,进而针对该问题设计了一种混合果蝇优化算法,用于最小化最大完工时间。在算法中,首先,在初始化阶段加入竞争机制,有效地提高了初始解的质量;其次,在嗅觉搜索阶段引入了自适应搜索半径,实现了对解空间的有效搜索;最后,在更新阶段融入了三阶段局部搜索,使全局搜索和局部搜索达到了较好平衡。仿真实验和算法比较验证了所提混合果蝇优化算法的有效性和鲁棒性。 

【文章来源】：控制工程. 2020,27(02)北大核心CSCD

【文章页数】：10 页

【部分图文】：

工厂一对应的甘特图Fig.1Ganttmapoffactoryone

第2期黄元元等：混合果蝇算法求解分布式异构并行机调度·257·表中‘/’表示该工件不能在该机器上加工。对π=[6,3,2,5,4,1]应用规则ECF[7]，可得1,1T=2，1,2T=1,2,1T=1,2,2T=2,1,11,11,112[,][6,4]TTTπ=ππ=,1,21,21[][5]TTπ=π=,2,12,11[][3]TTπ=π=,2,22,21[,TTπ=π2,22][2,1]Tπ=，工厂一和工厂二对应的甘特图，分别如图1和图2所示。图1工厂一对应的甘特图Fig.1Ganttmapoffactoryone图2工厂二对应的甘特图Fig.2Ganttmapoffactorytwo3混合果蝇优化算法果蝇优化算法是一种基于果蝇觅食行为而提出的群智能优化算法。将果蝇种群的觅食过程模拟为算法寻找优化解的过程，基于果蝇觅食行为中的嗅觉和视觉行为来设计相应的操作，通过不断对果蝇种群中心位置的优化，进而找到食物存在的位置。原始果蝇优化算法的流程如下[15]：步骤1初始化种群中心位置。步骤2嗅觉搜索：根据种群中心位置随机产生NP个邻域解。步骤3评价个体：计算每个个体的评价值。步骤4视觉搜索：选择最优邻域解，替换更新种群中心位置。步骤5判断终止准则是否满足：是，则输出最优解；否则，转至步骤2。HFOA不同于传统的FOA：首先，在初始化种群时引入了竞争机制从而有效的提高了初始解的质量；其次，在视觉和嗅觉搜索过程中加入了自适应搜索半径，实现了对解空间的有效搜索；最后，将基于三阶段的局部搜索融入了算法更新阶段：首先对最优排序进行了扰动操作；其次，添加了对最优排序的领域搜索操作；最后，对最大完成工厂内部排序进行基?

基于swap2的局部搜索是从最优排序中任意挑出两个工件进行交换操作。第一阶段的扰动避免算法在搜索过程中过早陷入局部最优；第二个阶段的局部搜索操作保证了搜索方向的正确性；第三个阶段的搜索操作是在较优排序中找到一个最优的分配方案；多阶段的局部搜索同时应用，有效地提高了局部搜索的能力。3.5HFOA流程图HFOA主要包括3个主要环节：基于竞争机制的初始化、基于自适应搜索半径的嗅觉和视觉搜索阶段、基于三阶段的局部搜索。求解分布式异构并行机的HFOA的流程图，如图3所示。图3HFOA流程图Fig.3HFOAflowchart4仿真实验与分析为验证所提算法解决分布式异构并行机调度问题的有效性，首先，将改进过后的算法与基本的果蝇优化算法进行比较，具体数据，见表3和表4。表3基本果蝇和改进初始化果蝇的比较Tab.3Comparisonofbasicfruitfliesandimprovedinitializationoffruitflies初始化改进的果蝇基本果蝇J_M_F最小值最大值平均值标准差最小值最大值平均值标准差运行时间:50*J20_2_32072302235.848077243254249.052.8191320_3_2233262246.56.06218267302285.111.4188430_2_4236253246.53.91791277296288.25.36283530_3_5131155143.458.065203176183179.651.423940_3_4229247240.155.659284255266260.12.42693

【参考文献】：
期刊论文
[1]果蝇优化算法研究进展[J]. 王凌,郑晓龙.  控制理论与应用. 2017(05)
[2]自适应果蝇算法优化模糊均值聚类算法图像分割[J]. 孙立新,张栩之,邓先瑞,魏萍.  控制工程. 2016(04)
[3]基于果蝇优化算法的冒口优化[J]. 王瞳,周建新,殷亚军,沈旭,周琴.  特种铸造及有色合金. 2016(03)
[4]分布式车间调度优化算法研究综述[J]. 王凌,邓瑾,王圣尧.  控制与决策. 2016(01)
[5]基于免疫果蝇混合优化算法的多配送中心选址问题研究[J]. 刘勇,孙静杰,王萱.  世界科技研究与发展. 2015(01)
[6]基于FOA-ELM的客户基金购买行为预测仿真[J]. 李栋,张文宇.  计算机仿真. 2014(06)
[7]求解一类异构并行机调度问题的分布估计算法[J]. 李作成,钱斌,胡蓉,向凤红,车国霖.  计算机集成制造系统. 2013(09)



本文编号：3384027