用于拆卸线平衡问题的离散蝙蝠优化器

    研究背景

    随着科技的快速发展，人类消费需求变得更加多样化，导致产品的生命周期变得更短。此外，一些被丢弃的产品对环境造成了巨大的危害。然而，对于部分废旧产品（EOL），我们可以拆解其中的有用部件并加以重复利用，以减少环境污染。这不仅节省资源、保护环境，还促进经济发展。在拆解过程中，拆解线平衡问题是其中最重要的问题之一。目前，对工作站空间区域的考虑相对较少，而更大程度地利用工作站的区域也能更好地降低成本。针对U形拆解线平衡问题，建立了一个带有区域约束的单目标优化数学模型，其目标是最大化利润。为了解决这个问题，我们参考自适应遗传算法（AGA）并改进其交叉和变异操作符。我们采用精英策略来避免过早收敛，并提高全局搜索能力。通过与CPLEX的优化结果进行比较，证明了其有效性。实验结果还验证了所提出模型的可行性以及在解决大规模实例时改进的自适应遗传算法相对于其他算法的优越性。同时，实验结果还通过与随机搜索（RS）算法比较，验证了改进的自适应遗传算法算法（IAGA）的优越性和有效性。

    本文基于空间区域的约束解决工作站的单目标DLBP，提出了单产品U形拆解线平衡问题（SUDP）。并在自适应算法基础上，进行改进以解决考虑空间区域约束问题。其目标是最大化拆卸利润。

    成果介绍

    研究成果发表于Journal of Cyber-Physical-Social Intelligence。

    DOI: 10.61702/ZLAS2069

    首先，为使任务分配方案更加合理，并更清晰地描述每个组件之间的关系，本文采用AND/OR图来表示每个组件之间的优先关系。  

    在拆卸的过程中，工作站执行任务不同，其地面空间面积也会有相应的改变。

            其次，本文围绕问题构建模型，在自适应遗传算法的基础之上，对其进行改进：根据每个个体的适应值调整交叉概率和变异概率。当大多数个体停留在局部最优位置时，需要增加交叉和变异概率以提高算法的优化能力。相反，当种群中的个体分散在解空间中时，需要降低交叉和变异的概率，以提高算法的收敛能力。   

    最后，使用手电筒、圆珠笔、洗衣机和锤钻作为测试案例。分别使用IAGA算法和CPLEX来比较四种情况下的利润和运行时间。同时，为了证明IAGA算法的优越性，我们选择了RS算法进行比较。

    从表1、2可知：从最大利润的角度来看，无论是小情况还是大情况，CPLEX始终是最优解，数值与IAGA相似；但从运行时间来看，IACA比CPLEX快，CPLEX运行速度较慢。从表3、4可以更明确地看到IAGA算法的可行性和优越性。

    综上，针对单件产品U型拆卸线平衡问题，IAGA算法与CPLEX所求得的拆卸序列是一样的。IAGA算法与CPLEX的运行时间相比，案例信息越大，IAGA的运行时间越小，优越性越好。且通过与其他算法的比较，验证了IAGA算法的准确性和优越性。

    作者及团队    

    王加存，1991 年获中国南京理工大学计算机工程博士学位。他于2004年加入美国蒙莫斯大学，目前是软件工程专业教授。他在2009年至2015年期间担任计算机科学和软件工程系主任。自2016年以来，他一直担任该系的研究生项目主任。他的研究兴趣包括机器学习、形式化方法、离散事件系统、软件工程、和实时分布式系统。出版著作四部，论文200余篇。著作《实时嵌入式系统》已被翻译成中文，由中国机械工业出版社出版。他目前是IEEE Transactions on Systems， Man， and Cybernetics：Systems， IEEE/CAA Journal of Automatica Sinica， IEEE SMC Magazine和International Journal of Network Dynamics and Intelligence的副主编。他曾在多个国际会议上担任大会主席或程序委员会主席。

    郭希旺，2006 年从沈阳工程学院获得了计算机科学与技术专业的学士学位，2009 年于沈阳航空航天大学获得航空航天制造工程专业的硕士学位，2015 年于东北大学获得了系统工程专业的博士学位。现任辽宁石油化工大学信息与控制工程学院的副教授。从 2016 年到 2018 年，他作为访问学者在新泽西理工学院电气与计算机工程系工作。他在期刊和会议论文集中发表了 60 多篇技术论文，包括《IEEE Transactions on Cybernetics》、《IEEE Transactions on System, Man and Cybernetics: Systems》、《IEEE Transactions on Intelligent Transportation Systems》和《IEEE/CAA Journal of Automatica Sinica》。他的研究方向为 Petri 网、再制造、汽车回收和再利用、智能优化算法。   

    秦术晋，2008 年获得天津工业大学信息与计算科学学士学位，2011 年获得辽宁科技大学运筹学与控制论硕士学位，2019 年获得东北大学系统工程博士学位。他于 2019 年加入商丘师范大学，现任物流管理讲师。主要研究方向为大规模整数规划、切割问题、车辆路径问题、智能优化算法。

    齐亮，分别于2009年和2012年在山东科技大学获得信息与计算科学学士学位和计算机软件与理论硕士学位，并于2017年在同济大学获得计算机软件与理论博士学位。现任山东科技大学计算机科学与技术学院讲师。2015年至2017 年，他在美国新泽西州纽瓦克市新泽西理工学院电气与计算机工程系做访问学者。他在期刊和会议论文集上撰写了 50 多篇技术论文，包括 《IEEE Transactions on System, Manand Cybernetics：Systems》、《IEEE Transactions on Intelligent TransportationSystems》和《IEEE/CAA Journal of Automatica Sinica》等期刊和会议论文集上发表过 50 篇技术论文。他曾获得第 15 届 IEEE 网络、传感与控制国际会议（ICNSC'2018）最佳学生论文奖-入围奖。他目前的研究方向包括 Petri网、离散事件系统和优化算法。  

    张琦，分别于 2012 年和 2015 年获得沈阳师范大学应用数学学士学位和硕士学位;2022 年获得东北大学系统工程博士学位。现任沈阳化工大学信息工程学院讲师。主要研究方向为装箱问题、钢铁生产调度与计划、数学规划、智能优化算法。

    徐斌，于2021年获得河南师范大学学士学位，目前是沈阳化工大学控制工程专业研究生。研究方向是智能优化算法。

    白伟双，分于2020年和2023年在辽宁石油化工大学获得学士学位和硕士学位。