格雷码混合遗传算法求解0-1背包问题 被引量：5

1

作者 王则林 吴志健 《计算机应用研究》 CSCD 北大核心 2012年第8期2906-2908,共3页

给出0-1背包问题的数学模型,修改传统二进制编码为格雷码混合遗传算法,使用贪心算法来解决约束问题,对每个个体使用价值密度来衡量,提高了算法搜索效率,同时使用精英保留机制来加速算法收敛的速度。最后通过数值实验证明了算法的有效性。

关键词 遗传算法 背包问题 格雷码 贪心算法 精英保留机制

下载PDF 职称材料

基于真实吐露贪婪机制的多Agent单机调度问题 被引量：2

2

作者 姜雪 全雄文 陈秋双 《系统工程学报》 CSCD 北大核心 2016年第3期423-430,共8页

在分布式环境下,从组合拍卖的角度出发研究了多Agent的单机调度问题,设计了一种贪婪机制.该贪婪机制包括贪婪分配算法和贪婪支付算法两部分,首先贪婪分配算法以资源Agent收益最大为目标解决组合拍卖中的竞胜标问题,然后贪婪支付算法以... 在分布式环境下,从组合拍卖的角度出发研究了多Agent的单机调度问题,设计了一种贪婪机制.该贪婪机制包括贪婪分配算法和贪婪支付算法两部分,首先贪婪分配算法以资源Agent收益最大为目标解决组合拍卖中的竞胜标问题,然后贪婪支付算法以第二价格支付的形式确定中标者应该支付的最小费用.本文证明了该贪婪机制的真实吐露性,并通过算例说明设计机制的可行性与有效性.最后进行仿真实验比较该贪婪机制与线性规划方法的求解效果,结果袁明,对大规模问题,该机制能够快速得到使系统总收益近似最优的调度方案. 展开更多

关键词 多Agent单机调度 组合拍卖 真实吐露 贪婪机制

下载PDF 职称材料

自动引导车最优动态调度问题建模与仿真 被引量：2

3

作者 陆天 王嘉珩 +1 位作者 夏裕东 李厚彪 《计算机应用》 CSCD 北大核心 2020年第S01期28-31,共4页

针对自动引导车(RGV)的动态调度问题,建立了相关最优化模型,提出了RGV动态调度的最优策略。首先,基于机理分析法,通过分析RGV和计算机数控机床(CNC)的工作原理,分别给出了它们在单步和多步工序中工作原则的约束条件,并以此为基础建立了... 针对自动引导车(RGV)的动态调度问题,建立了相关最优化模型,提出了RGV动态调度的最优策略。首先,基于机理分析法,通过分析RGV和计算机数控机床(CNC)的工作原理,分别给出了它们在单步和多步工序中工作原则的约束条件,并以此为基础建立了RGV的最优化动态调度模型。最后,利用贪心算法和系统模拟得到了RGV的最优调度策略。仿真结果表明:在单步工序下系统工作效率分别为94.53%、93.81%和94.2%,完成物料的数量分别为384、367和393;多步工序系统工作效率分别为87.87%、67.86%和65.08%,完成物料的数量分别为253、194和228,体现了模型具有较好的可实用性。另外,考虑CNC在工作中故障和检修因素,对模型进行推广,并通过添加故障和检修的约束条件对模型进行求解和检验。实验表明单步工序考虑故障条件下,系统完成物料的数量分别为379、361和371,与普遍情况相近,说明该调度算法能有效处理相关故障问题。 展开更多

关键词 最优化模型 自动引导车动态调度 贪心算法 系统仿真 机理分析

下载PDF 职称材料

一种改进的混合遗传算法求解0_1背包问题 被引量：2

4

作者 白东玲 郭绍永 《电子设计工程》 2013年第14期9-11,共3页

背包问题是组合优化中的NP(Non-Deterministic Polynomial)难题之一,论文将贪婪算法与遗传算法相结合提出一种改进的混合遗传算法来求解0_1背包问题。改进的混合遗传算法通过遗传算法的择优,重复执行选择、交叉和变异以及贪婪算法的修... 背包问题是组合优化中的NP(Non-Deterministic Polynomial)难题之一,论文将贪婪算法与遗传算法相结合提出一种改进的混合遗传算法来求解0_1背包问题。改进的混合遗传算法通过遗传算法的择优,重复执行选择、交叉和变异以及贪婪算法的修正这样一个过程,使得所求解在可以接受的时间内越来越接近最优解。同时采用精英保留机制来加快算法的收敛速度。最后通过实证明该改进的算法可以有效地克服遗传算法中早熟的现象,该方法同样也适用其他优化问题。 展开更多

关键词 遗传算法 贪婪算法 背包问题 精英选择

下载PDF 职称材料

软件定义网络中一种快速无循环路径迁移策略

5

作者 燕昺昊 刘勤让 +2 位作者 沈剑良 汤先拓 梁栋 《通信学报》 EI CSCD 北大核心 2022年第5期24-35,共12页

针对软件定义网络中数据平面转发设备的分布式部署及异步操作导致的路径迁移缓慢及故障等问题,提出了一种快速无循环路径迁移策略。首先,提出了一种基于节点排序的快速循环检测算法。该算法通过对比流的新旧路径上相邻节点的位置差异,... 针对软件定义网络中数据平面转发设备的分布式部署及异步操作导致的路径迁移缓慢及故障等问题,提出了一种快速无循环路径迁移策略。首先,提出了一种基于节点排序的快速循环检测算法。该算法通过对比流的新旧路径上相邻节点的位置差异,可快速判定路径迁移过程中是否存在转发循环以及检测循环发生位置。然后,提出了一种基于节点松弛依赖关系的贪婪更新机制。该机制利用快速循环检测算法发掘出新旧路径上公有交换机之间存在的松弛依赖关系,进而保证了迁移过程每轮更新的交换机数量最大化。仿真实验结果表明,相比于现有迁移方案,所提策略在不同网络状态下均可有效避免迁移循环且获得最佳更新时间开销。 展开更多

关键词 软件定义网络 路径迁移 循环避免 松弛依赖 贪婪机制

下载PDF 职称材料

基于深度强化学习与迭代贪婪的流水车间调度优化 被引量：24

6

作者 王凌 潘子肖 《控制与决策》 EI CSCD 北大核心 2021年第11期2609-2617,共9页

流水车间调度是应用背景最为广泛的调度问题,其智能算法研究具有重要的学术意义和应用价值.以最小化最大完工时间为目标,提出求解流水车间调度的一种基于深度强化学习与迭代贪婪算法的框架.首先,设计一种新的编码网络对问题进行建模,解... 流水车间调度是应用背景最为广泛的调度问题,其智能算法研究具有重要的学术意义和应用价值.以最小化最大完工时间为目标,提出求解流水车间调度的一种基于深度强化学习与迭代贪婪算法的框架.首先,设计一种新的编码网络对问题进行建模,解决了传统模型受问题规模影响而难以扩展的缺陷,并利用强化学习训练模型以获取优良输出结果;然后,提出一种带反馈机制的迭代贪婪算法,以网络的输出结果为初始解,协同利用多种局部操作提高搜索能力,并根据性能反馈调节各操作的使用,进而获得最终的调度解.仿真结果和统计对比表明,所提出的深度强化学习与迭代贪婪融合的算法能够取得更好的性能. 展开更多

关键词 流水车间调度 深度强化学习 迭代贪婪算法 反馈协同机制

原文传递

基于快速扩展随机树―贪婪边界搜索的多机器人协同空间探索方法 被引量：11

7

作者 宁宇铭 李团结 +1 位作者 姚聪 邵继升 《机器人》 EI CSCD 北大核心 2022年第6期708-719,共12页

传统多机协同探索算法存在鲁棒性较差、探索效率较低、环境障碍感知不完全等问题,为此本文提出一种基于快速扩展随机树-贪婪边界搜索(RRT-GFE)的多机器人协同空间探索方法。首先,采用Thiessen多边形对环境进行建模与划分,利用RRT边界探... 传统多机协同探索算法存在鲁棒性较差、探索效率较低、环境障碍感知不完全等问题,为此本文提出一种基于快速扩展随机树-贪婪边界搜索(RRT-GFE)的多机器人协同空间探索方法。首先,采用Thiessen多边形对环境进行建模与划分,利用RRT边界探索算法依次对所有Thiessen多边形进行探索;其次,在RRT边界探索算法的基础上,引入GFE算法进行细化搜索,并提取连续边界域的形心作为探索目标点;再次,利用划分所形成的多边形区域以及所提取出的边界点,采用基于改进市场机制的多机器人任务分配方法对探索目标点进行动态分配,并在探索过程中采用地图融合算法进行局部地图的实时融合;最后,基于机器人操作系统(ROS)搭建仿真/样机测试平台并进行了一系列实验验证。结果表明,无论在仿真还是样机实验中,基于RRT-GFE的多机器人协同探索算法均能取得更加省时高效的探索效果。 展开更多

关键词 协同探索 快速扩展随机树 贪婪边界搜索 Thiessen多边形 市场机制 机器人操作系统(ROS)

原文传递

考虑多技能人力资源的分布式多项目调度问题 被引量：10

8

作者 于懿宁 徐哲 刘东宁 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2020年第11期2921-2933,共13页

在分布式多项目管理中,当考虑共享资源为多技能人力资源时,共享资源的指派涉及到"活动-技能-资源"的匹配关系,进一步考虑人力资源多技能异质的特性,还会导致活动实际执行工期会随着指派方案的不同而变化,因此,考虑共享资源为... 在分布式多项目管理中,当考虑共享资源为多技能人力资源时,共享资源的指派涉及到"活动-技能-资源"的匹配关系,进一步考虑人力资源多技能异质的特性,还会导致活动实际执行工期会随着指派方案的不同而变化,因此,考虑共享资源为多技能人力资源的分布式多项目调度问题是一类具有很强现实背景和理论研究价值的NP-hard问题.基于多Agent系统,建立以单项目完工时间为优化目标的局部调度模型,以及多项目总延期成本为优化目标的全局协调决策模型;考虑人力资源多技能异质的特点,设计基于贪婪指派策略的序贯博弈谈判机制指派共享的人力资源;基于Ran Gen随机生成的多项目算例开展实验研究.研究表明:基于贪婪指派策略的序贯博弈谈判机制对于程度不同的资源冲突和不同规模问题的求解均具有较好的适应性,可有效降低多项目总延期成本,且求解效果优于随机分配策略;设计的优先指派技能水平高、掌握技能数少、工作时间短的全局资源指派策略,可获得较优的人力资源指派方案和多项目调度计划. 展开更多

关键词 分布式多项目调度 多技能人力资源 全局资源 贪婪指派策略 序贯博弈谈判机制

原文传递

考虑全局资源闲置成本的分布式RCMPSPTT 被引量：8

9

作者 赵松 徐哲 刘东宁 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2020年第7期1882-1894,共13页

在考虑资源转移时间的分布式多项目调度问题中,增加考虑资源闲置成本,对于多项目共享资源的协调决策具有重要影响.基于多Agent系统建立以单项目完工时间为优化目标的局部调度模型,并采用遗传算法求解初始局部调度计划;同时考虑项目延期... 在考虑资源转移时间的分布式多项目调度问题中,增加考虑资源闲置成本,对于多项目共享资源的协调决策具有重要影响.基于多Agent系统建立以单项目完工时间为优化目标的局部调度模型,并采用遗传算法求解初始局部调度计划;同时考虑项目延期成本、全局资源转移成本和闲置成本,以多项目总成本为优化目标建立全局协调决策模型,设计基于贪婪转移策略的序贯博弈谈判机制协调全局资源的分配和转移,并根据协调结果调整单项目局部进度计划;以MPSPLIB问题集开展实验研究.研究结果表明:协调时考虑全局资源闲置成本能更好的协调全局资源的分配和转移;与无博弈随机分配和转移的协调机制相比,基于贪婪转移策略的序贯博弈谈判机制可以有效地降低多项目总成本. 展开更多

关键词 分布式多项目调度 转移时间 闲置成本 贪婪转移策略 序贯博弈谈判机制

原文传递

一种基于动态参数调整的强化学习动作选择机制 被引量：6

10

作者 胡晓辉 《计算机工程与应用》 CSCD 北大核心 2008年第28期29-31,48,共4页

强化学习是一种重要的无监督机器学习技术,它能够利用不确定的环境下的奖赏发现最优的行为序列,实现动态环境下的在线学习,被广泛地应用到Agent系统当中。应用强化学习算法的难点之一就是如何平衡强化学习当中探索和利用之间的关系,即... 强化学习是一种重要的无监督机器学习技术,它能够利用不确定的环境下的奖赏发现最优的行为序列,实现动态环境下的在线学习,被广泛地应用到Agent系统当中。应用强化学习算法的难点之一就是如何平衡强化学习当中探索和利用之间的关系,即如何进行动作选择。结合Q学习在ε-greedy策略基础上引入计数器,从而使动作选择时的参数ε能够分阶段进行调整,从而更好地平衡探索和利用间的关系。通过对方格世界的实验仿真,证明了方法的有效性。 展开更多

关键词 强化学习 Q学习 动作选择 ε—greedy机制

下载PDF 职称材料

基于交互式CPHD的多传感器多机动目标跟踪 被引量：5

11

作者 蔡如华 樊向婷 +2 位作者 吴孙勇 王力 伍雯雯 《控制与决策》 EI CSCD 北大核心 2022年第1期47-57,共11页

针对多传感器高速多机动目标的跟踪问题,提出一种多传感器交互式贪婪势概率假设密度(MS-IMMGreedy-CPHD)滤波器.该滤波器在预测阶段,通过交互式多模(IMM)算法对势概率假设密度(CPHD)滤波中目标的状态、势分布和运动模型同时进行预测;在... 针对多传感器高速多机动目标的跟踪问题,提出一种多传感器交互式贪婪势概率假设密度(MS-IMMGreedy-CPHD)滤波器.该滤波器在预测阶段,通过交互式多模(IMM)算法对势概率假设密度(CPHD)滤波中目标的状态、势分布和运动模型同时进行预测;在滤波的更新阶段,利用贪婪(greedy)量测划分机制选取多传感器量测子集和拟分区,并通过拟分区量测子集对不同模型下CPHD预测的目标状态和势分布以及模型进行交互式更新.仿真结果表明,所提出MS-IMM-Greedy-CPHD滤波能够对高机动多目标进行稳定有效的跟踪,相较于多传感器势概率假设密度(MS-CPHD)滤波,跟踪结果的OSPA误差更小且势估计更加准确. 展开更多

关键词 交互式多模型 机动目标 多传感器 势概率假设密度滤波 贪婪量测划分机制

原文传递

无人机自组网中基于邻节点筛选的GPSR协议 被引量：4

12

作者 梁青 上官艺伟 +1 位作者 张文飞 熊伟 《计算机工程》 CAS CSCD 北大核心 2019年第10期96-100,109,共6页

在无人机自组网中,针对贪婪周边无状态路由(GPSR)协议中邻节点位置不准确及数据转发效率低下的问题,提出一种基于邻节点筛选的GPSR(GPSR-NS)协议。GPSR-NS协议采用失效节点筛选机制,预测邻节点当前时刻的位置,剔除已失效的邻节点,降低... 在无人机自组网中,针对贪婪周边无状态路由(GPSR)协议中邻节点位置不准确及数据转发效率低下的问题,提出一种基于邻节点筛选的GPSR(GPSR-NS)协议。GPSR-NS协议采用失效节点筛选机制,预测邻节点当前时刻的位置,剔除已失效的邻节点,降低失效节点的数据转发概率,同时利用空洞节点筛选机制,剔除下一跳可能成为空洞的邻节点,提前避免数据转发到空洞节点处,从而建立更加稳定可靠的通信网络。仿真结果表明,与GPSR协议和MP-GPSR协议相比,GPSR-NS协议的平均端到端时延和路由开销降低了56.79%、21.94%和50.67%、38.81%,网络吞吐量提高了147.86%、102.12%。 展开更多

关键词 无人机自组网 贪婪周边无状态路由协议 路由空洞 失效节点筛选机制 空洞节点筛选机制 邻节点

下载PDF 职称材料

无人机自组网中改进型反应-贪婪-反应路由协议 被引量：3

13

作者 梅家栋 南建国 《空军工程大学学报（自然科学版）》 CSCD 北大核心 2021年第4期22-28,共7页

无人机自组网具有网络拓扑变化剧烈,链路断开频繁等特点。反应-贪婪-反应(reactive-greedy-reactive,RGR)路由协议是针对无人机自组网而提出的改进型协议,在高动态环境下具有较好的网络性能。针对RGR协议具有网络开销大、易出现网络拥... 无人机自组网具有网络拓扑变化剧烈,链路断开频繁等特点。反应-贪婪-反应(reactive-greedy-reactive,RGR)路由协议是针对无人机自组网而提出的改进型协议,在高动态环境下具有较好的网络性能。针对RGR协议具有网络开销大、易出现网络拥塞等问题,提出了一种基于负载均衡和高贪婪地理转发成功概率的改进RGR路由协议。该协议在RGR协议的基础上,提出基于节点负载状态和地理位置信息辅助的受限洪泛机制、GGF模式下高分组成功传输概率的路径选择策略和基于节点负载预测和运动特征的分组转发策略3项关键改进措施。仿真结果表明,相较于AODV和RGR及其改进型协议,该协议提高了分组投递率,降低了网络的控制开销和平均端到端时延,提升了网络应对拓扑高度动态变化的能力,有效改善了网络性能。 展开更多

关键词 无人机自组网 路由协议 贪婪地理转发 受限洪泛机制 负载预测

下载PDF 职称材料

求解多车型校车路径问题的带参数选择机制的GRASP算法 被引量：1

14

作者 侯彦娥 党兰学 +1 位作者 孔云峰 谢毅 《计算机科学》 CSCD 北大核心 2016年第8期233-239,共7页

考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘... 考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘赌法选择阈值参数。完成初始解构造后,使用可变邻域搜索(VNS)进行邻域解改进,并记录所选择的参数和解的目标值。算法迭代过程中,先设置相同阈值参数的选择概率,每隔若干次迭代后,评估每个阈值参数的性能并修改其选择概率,使得算法能够得到更好的平均解。使用基准测试案例进行了测试,比较了基本GRASP算法与设计的GRASP算法的性能,并与现有求解多车型校车路径问题的算法进行对比,实验结果表明所设计的算法是有效的。 展开更多

关键词 校车路径问题 多车型 贪婪随机自适应搜索过程 参数选择机制 可变邻域搜索

下载PDF 职称材料

基于ODMRP的分布式核心稳定路由算法

15

作者 傅伟 周新力 刘军 《计算机系统应用》 2019年第2期219-225,共7页

在无人机网络中,由于节点具有较强的移动性,对于组播路由的建立以及组播组的划分提出更高要求,一般的组播路由协议往往无法满足网络需求.为此,提出了一种基于ODMRP的分布式核心稳定路由算法.该算法结合了改进贪婪机制,根据路由状况对路... 在无人机网络中,由于节点具有较强的移动性,对于组播路由的建立以及组播组的划分提出更高要求,一般的组播路由协议往往无法满足网络需求.为此,提出了一种基于ODMRP的分布式核心稳定路由算法.该算法结合了改进贪婪机制,根据路由状况对路径进行优化,为了降低源节点的数据处理负担,提出了分布式核心节点选择机制,将组播组的信息储存在多个核心节点中,同时释放了转发节点的储存空间.文章通过路由抢修机制,监控路由状态变化,对即将断裂的路由提前修复,保证了路径的有效性.仿真表明,该算法与标准的ODMRP算法及改进算法VCMP算法相比,能够优化传输路径,降低端到端时延,提高分组交付率,提升网络性能. 展开更多

关键词 无人机网络 改进贪婪机制 分布式核心节点 路由抢修

下载PDF 职称材料