随机型拆卸线平衡问题的局部邻域遗传算法

发布时间：2022-01-02 00:14

　　针对实际拆卸线存在的不确定性因素导致作业时间具有随机性的特点,采用零件优先关系图定义的拆卸模型,以工作站数目、平衡性指标、稳定性指标为优化目标,考虑工作站等效作业时间满足节拍时间约束,构建了随机型拆卸线平衡问题模型,并提出一种基于Pareto占优的局部邻域遗传算法。在该算法中,设计了一种面向随机作业时间的解码方法,通过两种交叉操作实现种群的全局搜索,并构造了深度邻域和广度邻域相结合的局部搜索策略,以扩大局部搜索的范围并提高局部寻优能力。通过对两个大规模算例的测试与对比,验证了所提算法的优越性和改进策略的有效性。最后,将模型和算法运用至27项任务的电视机为拆卸实例,通过分析该随机型拆卸线平衡优化的具体应用过程与结果,说明了所建模型与算法的实用性。 

【文章来源】：计算机集成制造系统. 2019,25(03)北大核心EICSCD

【文章页数】：12 页

【部分图文】：

图1两点夺贾拯作示素图

第３期张则强等：随机型拆卸线平衡问题的局部邻域遗传算法２．４局部搜索策略遗传算法通过变异操作进行局部搜索，变异操作搜索的范围较小，局部搜索能力有限。本文设计了一种深度邻域和广度邻域相结合的局部搜索策略，扩大局部搜索的范围以提高局部寻优能力。其中邻域解、深度邻域、广度邻域的概念见定义１～定义３，深度邻域与广度邻域的结构示意图如图２所示。定义１邻域解指种群个体周围，与其有邻域结构的解，本文的邻域结构为两两交换方式和插入方式。定义２深度邻域指种群个体通过多次两两交换操作得到一系列的邻域解，该过程中的所有解构成深度邻域关系，变换次数即为深度邻域的搜索深度。定义３广度邻域指种群个体通过多点位插入操作得到一系列的邻域解，该过程中的所有解构成广度邻域关系。局部搜索策略以交叉操作得到的新解为对象，依据变异概率Ｐｍ将局部搜索策略分为深度邻域搜索与广度邻域搜索，通过搜索深度邻域解和广度邻域解扩大了搜索范围，实现了个体的局部寻优。局部搜索策略的具体步骤如下：步骤１输入个体Ｘ（ｘ１，…，ｘｉ，…，ｘｎ），变异概率Ｐｍ。步骤２产生一个均匀随机数ｒ２∈［０，１］。步骤３判断ｒ２＜Ｐｍ，若成立，执行深度邻域搜索步骤４，否则执行广度邻域搜索步骤５。步骤４计算深度邻域搜索的深度Ｌ＝"ｒ２×ｎ#，随机选择个体的某一任务ｘｉ作为邻域出发点，确定ｘｉ的紧前工作和紧后工作之间的可交换任务集Ｖ１，随机选择某一可交换任务ｘｊ∈Ｖ１

第３期张则强等：随机型拆卸线平衡问题的局部邻域遗传算法综合ＬＮＧＡ在｛１００，１６０，０．５，０．５｝参数组合下重复运行１０次的非劣解，ＬＮＧＡ求解Ｐ５２问题的结果见表３，各算法的Ｐａｒｅｔｏ最优前沿如图３所示。由图４可知，ＡＣＯ的求解质量最差，平均闲置率ＦＩｄｌｅ存在两个取值，平滑率ＦＳｍｏｏｔｈ的范围在８５．９４％～９７．４７％，拆卸成本ＦＣｏｓｔ的范围在１５０．５４６～１７３．３８８；ＡＦＳＡ求得８个非劣解，ＦＣｏｓｔ求得３种对比算法的最优值１２９．７５，ＦＳｍｏｏｔｈ求得３种对比算法的最优值９９．７６％；ＧＡＳＡ求得１０个非劣解，所有解均支配ＡＣＯ的非劣解；本文所提ＬＮＧＡ求得１０个非劣解，均开启７个工作站，ＦＳｍｏｏｔｈ的范围在８５．５５％～９９．９９％，ＦＣｏｓｔ的范围在１２７．１４６～１５２．２３２，与ＡＣＯ、ＡＦＳＡ、ＧＡＳＡ３种对比算法相比，ＦＳｍｏｏｔｈ的最优值分别优化了２．５９％、０．２３％、０．２５％，ＦＣｏｓｔ的最优值分别优化了１５．５４％、２．０１％、４．９９％，ＬＮＧＡ将ＡＣＯ、ＡＦＳＡ、ＧＡＳＡ的Ｐａｒｅｔｏ最优前沿向前推进，验证了所提ＬＮＧＡ在求解大规模ＤＬＢＰ的有效性和优越性。表３所提ＬＮＧＡ求解Ｐ５２问题的结果序号拆卸方案ＦＩｄｌｅＦＳｍｏｏｔｈＦＣｏｓｔ１［１８，３６，３３，４７，２１，３］－［２８，１５，２９

【参考文献】：
期刊论文
[1]多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J]. 汪开普,张则强,朱立夏,邹宾森.  计算机集成制造系统. 2017(06)
[2]多目标拆卸线平衡问题的Pareto人工鱼群算法[J]. 汪开普,张则强,毛丽丽,李六柯.  中国机械工程. 2017(02)
[3]基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法[J]. 牟健慧,郭前建,高亮,张伟,牟建彩.  机械工程学报. 2016(22)
[4]作业车间调度的空闲时间邻域搜索遗传算法[J]. 赵诗奎,方水良,顾新建.  计算机集成制造系统. 2014(08)
[5]基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 丁力平,谭建荣,冯毅雄,高一聪.  计算机集成制造系统. 2009(07)



本文编号：3563089