控制理论与应用杂志

控制理论与应用杂志2024年第6期

• Seru系统调度优化的知识引导协同进化算法

  王凌,吴玉婷,陈靖方,潘子肖

  作为一种新型的生产模式, Seru系统能够兼顾柔性和效率且快速响应市场, 已在装配企业得到广泛应用.为了实现实际生产过程生产效率和劳动效率的协同优化, 本文研究以最小化最大完工时间和工人总劳动时间为目标的Seru系统多目标调度问题, 提出一种知识引导的协同进化算法. 首先, 将问题分解为Seru构造和Seru调度, 构造两个种群分别优化子问题. 同时, 设计种群规模的调整策略, 通过为有潜力的种群分配更多个体来提高协同搜索的效率. 进而, 通过分析问题的性质, 提炼规则性知识用于设计有效的搜索算子和重生成规则, 指导精英个体执行知识驱动的增强搜索, 从而进一步提升算法的局部开发能力. 通过数值仿真和统计性能对比, 验证了算法各设计环节的有效性, 并取得了显著优于现有最新算法的多目标调度优化性能.

• 基于模糊需求和模糊运输时间的多式联运路径优化

  杨喆,邓立宝,狄原竹,李春磊

  考虑不确定性的模糊多式联运路径优化研究, 可以在满足运输方案经济环保双重要求的同时, 增强运输方案的鲁棒性, 提高企业的抗风险能力. 本文建立了模糊需求和模糊运输时间下低碳低成本多式联运路径优化模型,针对连续型元启发式算法无法直接求解离散型组合优化模型的问题, 设计了基于优先级的通用编码方式. 在此基础上, 为进一步提高算法的求解质量, 提出了带启发式因子的特殊解码方式, 并且提出了一种带邻域搜索策略的自适应差分进化算法. 结果表明, 改进算法获得的最终方案在蒙特卡罗采样的大多数场景下满足约束, 方案稳定性强,目标值最低.

• 带负载均衡的混合算法求解分布式异构作业车间调度问题

  方子丞,李新宇,高亮

  针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(DHJSP), 本文提出了一种新的混合遗传禁忌搜索算法. 首先, 综合考虑工厂的工件总负载与最大机器负载, 提出了一种新的工厂负载表达方式. 其次, 针对DHJSP总工序数不定的特性, 提出以最小化最大工厂负载为目标快速确定初始工件分配方案, 并验证了方法的高效性. 然后, 新设计了两种考虑负载均衡的单工件转移邻域结构, 根据工序调度的结果对工件分配方案进行局部搜索. 最后, 因DHJSP缺少标准算例和相关算法, 在分布式同构作业车间调度问题(DJSP)上与现有算法进行对比, 所提算法在TA算例的480个问题上更新了420个问题的最优解, 其余60个问题取得了同等最优解. 在随机生成的3个不同规模的异构算例中, 所提算法也均取得了较好解, 验证了所提方法的优越性.

• 基于深度强化学习的舰船导弹目标分配方法

  肖友刚,金升成,毛晓,伍国华,陆志沣

  针对对抗环境下的海上舰船防空反导导弹目标分配问题, 本文提出了一种融合注意力机制的深度强化学习算法. 首先, 构建了舰船多类型导弹目标分配模型, 并结合目标多波次拦截特点将问题建模为马尔可夫决策过程.接着, 基于编码器–解码器框架搭建强化学习策略网络, 融合多头注意力机制对目标进行编码, 并在解码中结合整体目标和单个目标编码信息实现舰船可靠的导弹目标分配. 最后, 对导弹目标分配收益、分配时效以及策略网络训练过程进行了仿真实验. 实验结果表明, 本文方法能生成高收益的导弹目标分配方案, 相较于对比算法的大规模决策计算速度提高10%～94%, 同时其策略网络能够快速稳定收敛.

• 面向主动配电网实时优化调度的图强化学习方法

  陈俊斌,余涛,潘振宁

  主动配电网的新能源、储能等能源形式可以有效提高运行的灵活性和可靠性, 同时新能源和负荷也给配电网带来了双重不确定性, 致使主动配电网的实时优化调度决策维度大、建模精度差. 针对这一问题, 本文提出结合图神经网络和强化学习的图强化学习方法, 避免对复杂系统的精准建模. 首先, 将实时优化调度问题表述为马尔可夫决策过程, 并将其表述为动态序贯决策问题. 其次, 提出了基于物理连接关系的图表示方法, 用以表达状态量的隐含相关性. 随后, 提出图强化学习来学习将系统状态图映射到决策输出的最优策略. 最后, 将图强化学习推广到分布式图强化学习. 算例结果表明, 图强化学习在最优性和效率方面都取得了更好的效果.

• LeCMPSO算法求解异构无人机协同多任务重分配问题

  王峰,付青坡,韩孟臣,邢立宁,吴虎胜

  无人机系统在军事领域有着广泛应用, 由于战场环境复杂多变, 无人机遭遇突发状况后需进行任务重分配.异构无人机是指多种类型的无人机, 可完成单一无人机无法完成的多类型复杂任务, 异构无人机协同多任务重分配问题约束条件复杂且包含混合变量, 现有多目标优化算法不能有效处理此类问题. 为高效求解上述问题, 本文构建多约束异构无人机协同多任务重分配问题模型, 提出一种学习引导的协同多目标粒子群优化算法(LeCMPSO), 该算法引入基于先验知识的初始化策略和基于历史信息学习的粒子更新策略, 能有效避免不可行解的产生并提升算法的搜索效率. 通过在4组实例上的仿真实验表明, 与其他典型的协同进化多目标优化算法相比, 所提算法在解集的多样性、收敛性及搜索时间方面均具有较好的性能.

• 学习驱动的分布式异构混合流水车间批量流能效调度优化

  邵炜世,皮德常,邵仲世

  本文研究了分布式异构混合流水车间批量流能效调度问题, 其中每个工厂的加工效率不同, 工件可以分割成若干子批进入加工系统. 以最大完成时间和总能耗为优化目标, 建立了混合整数规划模型. 本文提出了一种学习驱动的多目标进化算法, 包括学习驱动的全局搜索和局部搜索. 引入Q学习作为学习引擎, 以种群和非支配解集的评价作为环境反馈信号, 通过不断的学习来动态指导搜索操作的选择; 基于问题特征, 设计了算法的状态集、动作集和奖励机制. Q学习的引入能够及时感知当前搜索的状态, 减少搜索操作的盲目性, 提高搜索的效率. 通过对仿真数据集的测试, 表明所提出算法能够有效地求解分布式异构混合流水车间批量流能效调度问题.

• 多目标协同正弦优化算法求解分布式流水车间调度问题

  郎峻,顾幸生

  针对最小化最大完工时间(makespan)、总拖期以及平均空闲时间的多目标序列相关准备时间分布式流水车间调度问题, 本文提出一种多目标协同正弦优化算法(MCSOA). 算法主要包括4个核心阶段: 在多邻域搜索阶段,提出了基于关键工厂的搜索策略, 并通过正弦优化算法控制搜索范围; 在破坏重构阶段, 设计了一种迭代搜索策略引导个体的进化方向, 同时使用正弦优化算法平衡全局开发与局部搜索; 在选择阶段, 使用非支配排序与参考点的方法筛选优质解, 外部档案集用于存储所有非支配解; 在协同阶段, 设计种群间共享与竞争机制, 平衡3个目标的优化. 本文通过多目标优化的均匀性、反世代距离和覆盖率3项性能指标验证算法的有效性, 并使用非参数检验证明所提出的算法具有显著性优势.

• 考虑多类型时间依赖资源约束的敏捷卫星调度优化

  李君,邢立宁,彭观胜,徐运保

  随着现代空间科技的迅猛发展, 光学遥感图像数据的应用需求越来越广泛, 大力推动了光学对地观测卫星的发展. 然而, 由于高昂的发射成本的约束, 对地观测卫星的资源是有限的, 远远无法满足各类数据需求. 因此, 提高对地观测卫星的使用效率, 提高其任务执行率, 具有非常重要的应用价值. 本文聚焦于敏捷对地观测卫星的任务调度问题, 即在给定的调度周期内, 对有限的卫星资源制定合理的任务调度方案, 在满足一定星上资源约束下, 最大化观测任务收益. 该问题难点在于星上的资源是非常有限的, 例如存储图像数据的固存资源、用于采集数据和卫星姿态切换的能量资源及执行任务活动耗费的时间资源. 需要注意的是, 能量消耗量和时间消耗量依赖于任务的执行时间, 这是敏捷卫星相对传统的非敏捷卫星独有的特性. 不同任务场景对不同类型资源的需求不同, 多种资源约束互相耦合, 资源约束具有时间依赖特性, 这些难点无疑极大地增加了卫星调度的求解难度. 为高效地求解该问题,本文构建了多类型时间依赖资源约束的敏捷卫星调度整数规划模型, 并针对问题特性提出了一种基于自适应选择因子的迭代局部搜索启发式算法. 自适应选择因子综合考虑了目标收益、资源消耗量、资源约束的松弛量, 采用动态变化的资源重要度, 能快速自适应地根据当前场景下各种类型的资源数据使用量来确定最佳局部搜索方向, 从而在有限时间内找到高质量的解. 实验结果证明, 本文所提出的算法在多种情况下相比当前最好算法求解效果显著更优. 此外, 算法独有的自适应选择因子相比传统的选择因子的求解质量更高, 这是因为所设计的自适应选择因子兼顾了目标收益和资源消耗量之间权衡关系的同时, 采用动态变化的资源重要度准确捕捉了资源需求的迫切程度.

• 深度强化学习算法求解动态流水车间实时调度问题

  杨媛媛,胡 蓉,钱 斌,张长胜,金怀平

  本文针对动态流水车间调度问题(DFSP), 以最小化最大完工时间为优化目标, 提出一种自适应深度强化学习算法(ADRLA)进行求解. 首先, 将DFSP的新工件动态到达过程模拟为泊松过程, 进而采用马尔科夫决策过程(MDP)对DFSP的求解过程进行描述, 将DFSP转化为可由强化学习求解的序贯决策问题. 然后, 根据DFSP的排序模型特点, 设计具有较好状态特征区分度和泛化性的状态特征向量, 并依此提出5种特定动作(即调度规则)来选择当前需加工的工件, 同时构造基于问题特性的奖励函数以获取动作执行效果的评价值(即奖励值), 从而确定ADRLA的3类基本要素. 进而, 以深度双Q网络(DDQN) 作为ADRLA中的智能体, 用于进行调度决策. 该智能体采用由少量小规模DFSP确定的数据集(即3类基本要素在不同问题上的数据)训练后, 可较准确刻画不同规模DFSP的状态特征向量与Q值向量(由各动作的Q值组成)间的非线性关系, 从而能对各种规模DFSP进行自适应实时调度. 最后, 通过在不同测试问题上的仿真实验和与算法比较, 验证了所提ADRLA求解DFSP的有效性和实时性.

• 异构群智感知PPO多目标任务指派方法

  杨潇,郭一楠,吉建娇,刘旭

  现有移动群智感知系统的任务指派主要面向单一类型移动用户展开,对于存在多种类型移动用户的异构群智感知任务指派研究相对缺乏.为此,针对异质移动用户,定义其区域可达性,并给出感知子区域类型划分.进而,兼顾感知任务数量和移动用户规模的时变性,构建了动态异构群智感知系统任务指派的多目标约束优化模型.模型以最大化感知质量和最小化感知成本为目标,综合考虑用户的最大任务执行数量、无人机的受限工作时间等约束.为解决该优化问题,提出一种基于近端策略优化的多目标进化优化算法.采用近端策略优化,根据种群的当前进化状态,选取具有最高奖励值的进化算子,生成子代种群.面向不同异构群智感知实例,与多种算法的对比实验结果表明,所提算法获得的Pareto最优解集具有最佳的收敛性和分布性,进化算子选择策略可以有效提升对时变因素的适应能力,改善算法性能.

• 双重信息引导的蚁群算法求解绿色多舱车辆路径问题

  郭宁,申秋义,钱斌,那靖,胡蓉,毛剑琳

  针对当前实际运输中广泛存在的绿色多舱车辆路径问题(GMCVRP), 文章提出一种双重信息引导的蚁群优化算法(DIACO)进行求解. 首先, 在DIACO的全局搜索阶段, 重新构建传统蚁群优化算法(TACO)中的信息素浓度矩阵(PCM), 使其同时包含客户块信息和客户序列信息, 即建立具有双重信息的PCM(DIPCM), 从而更全面学习和累积优质解的信息; 采用3种启发式方法生成较高质量个体, 用于初始化DIPCM, 可快速引导算法朝向解空间中优质区域进行搜索. 其次, 在DIACO的局部搜索阶段, 设计结合自适应策略的多种变邻域操作, 用于对解空间的优质区域执行深入搜索. 再次, 提出信息素浓度平衡机制, 以防止搜索陷入停滞. 最后, 使用不同规模的算例进行仿真测试和算法对比, 结果验证了DIACO是求解GMCVRP的有效算法.

• 工位数固定的U型拆卸线部分拆卸平衡问题

  吴秀丽,张兴宇

  为提高工位数固定的U型拆卸线拆卸效率, 减少有害部件对操作人员的潜在威胁, 针对高价值零部件和有害零部件的拆卸需求, 本文提出了工位数固定的U型拆卸线部分拆卸平衡问题, 建立了以最小化节拍时间、高危工位数目和负载均衡为目标的优化模型, 并设计了改进的变邻域搜索算法进行求解. 在编码过程中提出一种基于零部件释放位置的选择策略, 以减少前继零部件拆卸顺序对编码的影响; 提出最小偏差二分法, 有效减少解码的迭代次数; 提出瓶颈挤压局部搜索策略, 用以优化节拍时间和均衡负载指标. 通过与其他算法对比, 结果表明改进的变邻域搜索算法求解具有优越性, 并且可实现对工位数固定的U型拆卸线部分拆卸平衡问题的高效求解.

• 邻域自适应粒子群算法求解地源热泵区域 能源系统鲁棒优化调度问题

  吴亮红,王维,张红强,贾睿

  针对地源热泵区域能源系统中冷热负荷和机组效能的不确定性, 本文提出了一种考虑双重不确定性的鲁棒优化调度方法. 首先, 基于多面体不确定模型描述调度模型中的鲁棒变量. 然后, 针对建筑冷热负荷不确定性, 采用对偶原理将双层优化模型等价为单层优化模型; 对于机组效能不确定性, 采用场景法进行分析. 最后, 采用多目标优化约束处理方法处理鲁棒优化调度模型中的约束条件. 同时, 为更加高效、准确求解所构建的优化调度模型, 提出了一种邻域自适应粒子群优化算法(NAPSO). 实验结果表明, 在制冷和制热工况下, 与经验运行策略相比, 本文所提方法可分别减少7.22%和5.55%的系统运行成本, 是一种解决地源热泵区域能源系统鲁棒优化调度的有效方法.

• 通勤合乘路径优化模型与算法

  李旺,柳伍生,肖义萍,周清,李薇

  道路车辆的增多导致城市交通和环境问题日益严重, 共享合乘被认为是减少交通拥堵, 降低碳排放的有效方法, 特别是在新冠疫情持续影响下, 通勤者采用互助合乘出行意愿较高. 本文考虑到通勤时间的紧迫性, 通勤者存在通勤压力和合乘不适感, 在没有经济效益驱动的情况下, 限制合乘路径的匹配范围, 并加入惩罚因子以提高合乘配对成功率. 本文提出了一种基于最优时间插值的贪婪启发式算法, 添加了3种扰动算子来提高全局搜索能力, 采用多组不同规模案例测试扰动效果. 结果表明: 设计算法可以在短时间内求解出更优结果, 在解决大规模问题上,相比于精确算法、粒子群算法和遗传算法更具竞争力. 此外, 通过选取位置较远且分布均匀的职员作为接送者, 可以改善合乘效果.

• 策略梯度的超启发算法求解带容量约束车辆路径问题

  张景玲,余孟凡,赵燕伟,孙钰粟,蒋玉勇

  有容量车辆路径问题是组合优化问题中比较热门的问题, 它属于经典的NP-hard问题并且时间复杂度高.本文提出了一种基于策略梯度的超启发算法, 将强化学习中的确定性策略梯度算法引入到超启发算法的高层策略中的底层算法选择策略, 确定性策略梯度算法采用Actor-Critic框架, 另外为了能够在后续计算和神经网络参数更新中引用历史经验数据, 在确定性策略梯度算法中设计了经验池用于存储状态转移数据. 在超启发算法解的接受准则方面, 文中通过实验对比了3种接受准则的效果, 最终选择了自适应接受准则作为高层策略中解的接受准则. 通过对有容量车辆路径问题标准算例的计算, 并将求解结果与其他算法对比, 验证了所提算法在该问题求解上的有效性和稳定性.

• 基于残差图卷积网络与深度强化学习的需求可拆分车辆路径优化算法

  罗佳,李朝锋

  需求可拆分车辆路径问题(SDVRP)出现在广泛的物流配送场景中, 具有重要的研究价值. 高效的SDVRP优化算法能够提高车辆装载率, 降低物流配送成本. 为提高SDVRP的求解效率, 本文提出基于残差图卷积神经网络(RGCN)和多头注意力的深度强化学习算法(REINFORCE), 逐步构建可行解序列. 首先, 从强化学习的角度出发, 文章对SDVRP建立马尔科夫决策模型, 定义序列预测过程的环境状态、智能体动作空间、状态转移函数等. 其次, 建立编–解码模型求解节点选择策略, 其中使用残差图卷积神经网络的编码器重构配送中心和客户节点的特征, 将配送网络中节点间的连接关系与节点特征相互关联, 获得差异性显著的特征嵌入向量; 利用注意力网络解码器在重构后的嵌入向量基础上融合动态变化的车辆剩余装载量和客户需求等信息执行解码任务, 实现每次迭代为单个案例提供多个可行解. 最后, 提出基于平均基准值的REINFORCE算法更新模型参数, 通过求解不同问题规模测试集、标准SDVRP数据集, 以及京东物流实际配送任务, 验证了所提算法的有效性.

• 求解分布式两阶段混合流水车间调度的反馈人工蜂群算法

  王移民,雷德明

  针对考虑工厂适用性和附加资源的分布式两阶段混合流水车间调度问题(DTHFSP), 本文提出了一种反馈人工蜂群算法(FABC), 以最小化最大完成时间和总延迟时间, 该算法利用一种新型反馈机制动态调整搜索策略集.为此, 本文共设计了5 种特点各异的搜索策略, 将其用于初始策略集和备选策略集, 同时, 建立并调整雇佣蜂群和跟随蜂群的共享策略集, 雇佣蜂阶段和跟随蜂阶段在种群划分的基础上采用随机选择和自适应选择方式确定搜索策略, 在侦查蜂阶段完成后, 对搜索策略集进行动态调整. 文章进行了大量的计算实验, 计算结果表明, FABC策略合理有效, 且它对所求解的DTHFSP具有较强的搜索优势.

• 求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法

  韩雪,王玉亭,韩玉艳,李俊青

  在经典分布式流水车间调度问题基础上, 本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP), 以均衡各工厂能耗成本为优化目标, 提出了基于群体优化的迭代贪婪算法 (PEIG). 该算法针对零缓冲区和多工厂生产模式, 设计了问题特性的启发式方法; 针对迭代贪婪算法(IGA)的优势和不足, 提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法, 以进一步平衡所提算法的全局探索和局部搜索能力. 通过270个测试算例的数值仿真, 以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性, 能为中大规模的DBFSP SDST提供更优的调度方案.