【摘 要】
：
作为组合优化领域中经典的NP难问题,集合覆盖问题有重要的理论研究意义和工业应用价值。为了求解对时间要求较高的调度问题,如物资运送、机器调度、卫星拍摄,提出了一个带冲突的集合覆盖扩展问题,称为最小最大加权集合覆盖问题（Min Max Weighted Set Covering Problem,MMWSCP）。在该问题中,元素表示需要完成的任务,每个集合具有一个时间段属性,表示该集合中的任务只能在这个
论文部分内容阅读
作为组合优化领域中经典的NP难问题,集合覆盖问题有重要的理论研究意义和工业应用价值。为了求解对时间要求较高的调度问题,如物资运送、机器调度、卫星拍摄,提出了一个带冲突的集合覆盖扩展问题,称为最小最大加权集合覆盖问题（Min Max Weighted Set Covering Problem,MMWSCP）。在该问题中,元素表示需要完成的任务,每个集合具有一个时间段属性,表示该集合中的任务只能在这个时间段内完成。若两个集合的时间段重叠则表示存在冲突。问题的目标是选取一组互不冲突的集合以覆盖所有的任务并且使得最晚完成任务的结束时间最小。当去掉该问题的时间属性和冲突且问题的目标改为使所选集合数量最小时,问题退化为典型的集合覆盖问题。将强化学习中学习自动机的思想和禁忌搜索相结合,提出了一个新的启发式算法以求解该问题。算法首先借鉴了可满足性问题（SAT）求解中的单子句传播思想,设计了单节点传播（Unit Vertex Propagation,UVP）方法。UVP迭代地寻找只能被一个集合覆盖的元素,然后将对应的集合加入候选解中,从而简化了集合和元素的覆盖关系,在一定程度上减小数据规模。随后,算法综合考虑集合所能覆盖的元素和集合的冲突数来贪心地构造初始解。算法利用二分搜索将优化问题转化为判定问题。然后基于该初始解进行禁忌搜索,在搜索过程中根据集合是否在候选解中维护学习自动机的概率向量。在算法陷入局部最优解时,依据该概率向量进行扰动以跳出局部最优解。概率表中集合的概率值反映了该集合的优劣,因此可根据概率值扰动到一个有较大概率能改进当前解的解空间中。由于MMWSCP是一个新问题,目前没有已有的实验算例,也无法用现有的集合覆盖算法进行求解。以一个项目的数据为基础进行设计和改造,生成了20组不同规模的算例并设置了两个对照算法:贪心算法和移除学习自动机的禁忌搜索算法。实验结果表明,所提出的算法可以有效求解该问题。
其他文献
近些年来深度学习迅猛发展,在图像、自然语言处理、图处理等领域取得了良好的效果。但是随着深度学习的模型越来越复杂,可解释性也随之变得更差。深度学习训练出的模型都被视为黑盒子,严重阻碍了深度学习在某些特定领域的应用。在图神经网络领域,很多较新的解释方法可以归纳为求解一个掩码,然后根据掩码去生成最后的解释,常见的掩码方法有边掩码方法和节点掩码方法。现有的节点掩码方法的优点是生成的解释中几乎都是重要的边,
互联网的兴起与定位技术的进步为基于位置的社交网络（Location-Based Social Network,LBSN）的发展提供了数据和技术上的支撑。随着网络规模的扩大,海量的数据内容造成了信息过载的问题,用户检索时间的开销增大,导致信息的利用率下降。因此如何在LBSN中发掘用户的下一个兴趣点（Point-Of-Interest,POI）成为亟需解决的任务。然而现有的下一个POI推荐任务仍存在缺
针对高陡岩质开采创面由于质地不均一、坡度变化较大、稳定性差别较大等造成废弃矿山生态修复效果不理想的问题，以铜陵市义安区桃园硫铁矿废弃矿坑综合治理工程为例，进行了高陡岩质开采创面柔性生态棒生态治理研究。研究结果表明：柔性生态棒修复技术在桃园硫铁矿废弃矿坑综合治理生态修复工程中取得了较好效果，基本消除了视觉污染、减轻了水土流失，并形成了稳定健康的草、灌、乔、藤多层次植物群落，可为类似高陡岩质开采创面较
移动互联网时代,GPS技术的快速发展以及道路网络的日益复杂给导航应用程序带来新的机遇与挑战。目前许多导航应用程序允许以语音作为输入,避免了用户手动输入文字,提高了交通安全性。但是,现有的导航应用程序通常无法理解用户对路径的自然语言描述,仅识别用户以指定模板发出的指令。例如,现有的导航应用程序仅支持用户输入单一的出发地或目的地,不能设置额外的个性化路径搜索要求,无法满足人们日常的出行需求。为扩展现有
近年来,我国出台了多项政策大力推动智能安防产业发展。在智能监控场景下,应用多目标跟踪算法,可以对其中的人物进行实时、准确的跟踪,因而具有很大的研究价值。现有的多目标跟踪算法,存在遮挡情况下容易跟丢目标、跟踪轨迹不连续、跟踪漂移等问题。针对上述问题,提出了相应的解决方法。首先,提出基于注意力的多目标跟踪算法。原有算法重识别（Re-identification,Re ID）分支对目标辨识力强的特征提取
隐蔽通道是用户可以绕过强制访问控制检查进行隐蔽通信的一种机制,标识一个系统中的隐蔽通道是高安全等级系统的开发和测试中必不可少的工作。源码层面使用信息流分析技术搜索隐蔽通道时,现有方法难以确定虚函数调用处的被调用函数。此外,面对大型系统的修改、引用和返回关系表,使用隐蔽流树法搜索隐蔽通道时,会创建大量重复节点致程序占用内存过多而无法给出计算结果。改进现有方法,对提高数据库这样的大型系统的隐蔽通道分析
供水管道是保障日常生产活动正常进行的重要基础设施,在长期使用中受自身寿命或外界破坏性因素的影响会发生破裂造成漏损。及时的泄漏检测对节约水资源、防止二次污染以及可能带来的次生灾害至关重要,目前常用的检测方法通过采集和分析振动信号确定泄漏是否发生。泄漏振动信号十分微弱,采集时受环境噪声影响大,传统的检测方法无法有效地区分环境中存在的非平稳噪声,检测效果不稳定并且依赖检测人员的经验。大量的泄漏检测设备一
纠删码作为一种以条带的形式存储数据的容错技术,广泛应用于当前的大规模存储系统中;相比副本容错技术,纠删码能以更低的存储成本来提供相同容错能力。为了进一步降低存储成本,业界开始研发“大条带纠删码”技术,通过增加条带长度来压缩校验块在每个条带中的比例以节省更多存储空间。然而,现有“直接编码”生成大条带的方式通常因编码速度下降而导致数据生成缓慢。一种可行思路是通过“扩展转换”来生成大条带,即首先将新写数
区块链在金融、能源、医疗、食品等众多关键领域有着极高的应用价值,然而当前区块链的性能严重限制了其在现实场景中的落地。其中最具代表性的以太坊区块链,其区块处理时延严重受限于状态树引入的海量数据库查询。现有的针对性解决方案多会导致显著的负面效应,如内存、网络带宽等硬件成本的急剧上升,因而难以广泛应用。通过深入分析以太坊工作流与负载,观察到状态树单条分支“一热俱热”的访问规律:绝大多数情况下,热点账户及
通信技术与物联网技术的发展导致物联网终端爆发式增长,感知数据和物联网应用呈指数级增长,推动智慧类应用需求高速发展,对计算存储资源提出更高要求。集中式云计算框架受制于网络拓扑、回传带宽和网络延迟等的影响,难以满足智慧应用场景对处理时延和网络开销的需求。边缘计算框架借助靠近物联网终端侧的多接入边缘计算（Multi-access Edge Computing,MEC）设备,卸载全部或部分计算任务,能有效