求解工件车间调度问题的一种新的邻域搜索算法

该文提出了一种新的求解工件车间调度(job shop scheduling)问题的邻域搜索算法．问题的目标是：在满足约束条件的前提下使得调度的makespan尽可能地小．定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向．计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法．其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解．这些实例是当前文献中报导的所有规模为10工件10机器的实例．     

基于邻域等价类的同构子图搜索算法

节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于Turbo_(ISO)算法中的邻域等价类(NEC)概念,提出同构子图搜索算法NEC-COMB。该算法包含预处理、节点顺序确定、子图同构匹配和子图提取4个部分,在子图同构匹配时对NEC中的节点使用组合策略,避免等价节点重复匹配。实验结果表明,与经典算法VF2,GraphQL,Turbo_(ISO)相比,NEC-COMB可有效提高搜索效率,优化去重效果。     

基于邻域感知图神经网络的会话推荐

在基于会话的推荐中,图神经网络及其改进模型将会话内复杂的交互关系建模为图结构并从中捕获项目特征,是现有推荐模型中性能较好的一类方法。然而大多数模型都忽略了不同会话之间可能存在的有效信息,仅对当前会话建模难以利用其他会话,也无法发挥邻域信息的辅助作用。因此提出基于邻域感知图神经网络的会话推荐（NA-GNN）。该模型构建会话层和全局邻域层的图结构捕获项目表示,结合注意力机制聚合两种项目表征,将会话序列之间的互信息最大化地结合到网络训练中。在真实的数据集Yoochoose和Diginetica上进行实验,与性能最优的基准模型相比,模型P@20在Yoochoose上提高了1.85%,在Diginetica上提升了7.19%;MRR@20分别提升了0.48%和8.36%,证明模型的有效性和合理性。     

一种SAT邻域的快速搜索算法

用局部搜索算法求解SAT问题．通常都需要在较大的邻域中。寻找合适的邻解。如果对邻域中的每个邻解。都通过重新判断每个子句是否为可满足来得到其可满足的子句个数．则时间耗费较多。已经有一些经典的处理方法．例如通过修改邻域结构．来减小搜索空间。从另外一个角度来考虑搜索过程．根据当前解和邻解的内在关系．介绍一种SAT邻域的快速搜索算法。该算法能在不影响解质量的前提下．快速寻找合适的邻解．从而进一步提高局部搜索算法的求解速度。另外．该算法还提供用于提高解质量的信息。有助于研究新的局部搜索算法。     

最大弧覆盖问题的一种邻域搜索算法

研究应急救援中心的选址问题,通过合理设置各中心的位置,使相应的专业应急小组及时到达事故点进行应急救援,最大限度地减少事故损失.上述问题可描述为网络的最大弧覆盖问题.针对建立最大弧覆盖的数学模型,提出了一种邻域搜索算法:首先将最大弧覆盖问题近似看作p-median问题,利用顶点替代算法给出初始解,再通过邻域搜索,对初始解进行改进.通过实例仿真表明,邻域搜索算法收敛速度快,求解精度接近最优解.     

面向动态车辆路径的改进变邻域搜索算法

为了切实求解带时间窗的车辆动态路径问题,提出一种改进变邻域搜索算法,并建立了相应数学模型。算法运用聚类方法完成客户分配和路线规划的初始解构建。插入一交换混合算子实现抖动过程,提出后优化过程改进解空间,并采用最佳改进策略实现算法在求解质量和运行时间上的最佳平衡,引入模拟退火思想控制新解接受、地理位置分布等,并对路径选择进行了分析。通过与其他算法的实验结果比较表明该算法的可行性和高效性。     

求解护士排班问题的变邻域搜索算法

变邻域搜索算法是求解护士排班问题的一个有效算法,其扰动方法对算法性能有显著影响。为提高护士排班问题中护士的满意度,提出一个改进的变邻域搜索(IVNS)算法。该算法使用了三种邻域结构,而且当使用任意的邻域都不能进一步改进当前解时,设计了一个对当前最优解进行扰动的方法,即在排班期间内随机地选择两天,在不违反硬性约束的条件下选出一组值班护士并交换他们在这两天中的班次。在2010年举行的第一次全球护士排班大赛提供的一组公共测试集上与一个混合变邻域搜索(HVNS)算法进行了比较,在Sprint-early、Medium-early和Long-early组算例上的结果表明,IVNS算法的最优值至少不劣于HVNS,而平均值均优于HVNS;IVNS算法的最大方差为0.72,波动范围小,求解性能稳定。IVNS的扰动方案对现有方案的扰动较小,能有效跳出当前局部最优,增强变邻域搜索算法的优化能力,与HVNS算法相比,其求解性能更优。     

基于PCDARTS改进的神经网络架构搜索算法

神经网络架构搜索主要解决人工设计神经网络难度大的问题,针对该算法的研究在自动化机器学习领域有着深远的意义.搜索算法的主要流程包括设计搜索空间、设计搜索策略、网络评估,针对搜索空间,应用通道随机重排技术和上下文信息融合技术进行高效特征提取,同时在搜索策略上,针对联合搜索优化困难且消耗时间长的问题,设计了修正网络的redu...     

基于图神经网络的智能路由机制

现有基于人工智能的路由方案泛化能力较差,难以适应动态的网络拓扑变化。提出基于深度强化学习的智能路由机制SmartRoute。通过实时感知网络中流量分布状态,动态调整路由策略,并结合图神经网络的拓扑信息感知能力和深度强化学习的自我训练能力,提升网络路由策略的智能性。实验结果表明,与DRL-TE、TIDE等方案相比,SmartRoute最多节省9.6%的端到端时延,且具有更好的鲁棒性。     

变邻域搜索算法综述

变邻域搜索算法(Variable Neighborhood Search,VNS)作为一种新的元启发式算法,已初步成功地用于解决优化问题,尤其是对于大规模组合优化问题效果良好。对VNS的扩展研究层出不穷,并将其成功地应用到旅行商问题、车辆路径问题、调度、图着色等问题中。简述了经典的元启发式算法,并依次论述了优化问题,VNS算法起源,VNS算法原理,VNS算法分析,扩展的VNS分析,VNS在初始解构造、邻域结构构造、局部搜索和停止准则几个方面的改进方法,针对不同版本的VNS归纳了其在各种优化问题应用情况。基于对改进的VNS的分类,从算法自身研究角度和实际应用角度提出了未来研究方向。     

基于神经网络架构搜索的肺结节分类算法

肺结节分类是早期肺癌诊断的重要任务。基于深度学习的肺结节分类方法虽然能够取得良好的分类精度,但存在模型复杂和可解释性差的问题。为此,提出了一种基于神经网络架构搜索的肺结节分类算法。首先,将注意力残差卷积cell作为搜索空间的基本单元,并使用偏序剪枝方法作为搜索策略来构建神经网络架构以搜索3D分类网络,从而达到网络性能和搜索速度的平衡。其次,在网络中构建了多尺度通道和空间注意力模块来提高特征描述和类别推理的可解释性。最后,采用堆叠法将搜索到的网络架构进行多模型的融合,从而获取精准的肺结节良恶性分类预测结果。实验结果表明,在肺结节分类常用数据集LIDC-IDRI上,所提算法与最新肺结节分类算法相比具有较好的分类性能和较快的收敛,且所提算法的特异性和精确率分别达到95.37%和93.42%,能够实现良恶性肺结节的准确分类。     

基于知识图注意网络的个性化推荐算法

现有的大多数利用知识图谱的推荐算法在探索用户的潜在偏好时没有有效解决知识图谱中存在的不相关实体的问题,导致推荐结果准确率不高。针对这一问题,提出了基于知识图谱和图注意网络的推荐算法KG-GAT(knowledge graph and graph attention network)。该算法将知识图谱作为辅助信息,在图注意网络中使用分层注意力机制嵌入与实体相关的近邻实体的信息来重新定义实体的嵌入,得到更有效的用户和项目的潜在表示,生成更精确的top-N推荐列表,并带来了可解释性。最后利用两个公开数据集将所提算法和其他算法进行实验对比,得出所提算法KG-GAT能够有效解决沿着知识图谱中的关系探索用户的潜在偏好时存在的不相关实体的问题。     

基于图神经网络的联合实体关系抽取

从非结构化文本中联合提取实体和关系是信息抽取中的一项重要任务。现有方法取得了可观的性能,但仍受到一些固有的限制,如错误传播、预测存在冗余性、无法解决关系重叠问题等。为此,提出一种基于图神经网络的联合实体关系抽取模型BSGB（BiLSTM+SDA-GAT+BiGCN）。BSGB分为两个阶段：第一阶段将语义依存分析扩展到语义依存图,提出融合语义依存图的图注意力网络（SDA-GAT）,通过堆叠BiLSTM和SDA-GAT提取句子序列和局部依赖特征,并进行实体跨度检测和初步的关系预测;第二阶段构建关系加权GCN,进一步建模实体和关系的交互,完成最终的实体关系三元组抽取。在NYT数据集上的实验结果表明,该模型F₁值达到了67.1%,对比在该数据集的基线模型提高了5.2%,对重叠关系的预测也有大幅改善。     

强化学习求解组合最优化问题的研究综述

组合最优化问题(COP)的求解方法已经渗透到人工智能、运筹学等众多领域.随着数据规模的不断增大、问题更新速度的变快,运用传统方法求解COP问题在速度、精度、泛化能力等方面受到很大冲击.近年来,强化学习(RL)在无人驾驶、工业自动化等领域的广泛应用,显示出强大的决策力和学习能力,故而诸多研究者尝试使用RL求解COP问题,...     

基于自适应图卷积注意力神经协同推荐算法

随着互联网的快速发展,推荐系统可以用来处理信息过载的问题。由于传统推荐系统的诸多问题导致其无法处理发掘隐藏信息,提出一种自适应图卷积注意力神经协同推荐算法（ANGCACF）。首先获取用户和项目交互图,通过图卷积神经网络自适应的聚合用户和项目特征信息;其次对用户和项目特征信息添加自适应扩充数据,以解决数据稀疏性,利用注意力机制对用户和项目特征信息及添加的自适应扩充数据重新分配权重;最后将得到的用户和项目特征表示使用基于矩阵分解的协同过滤的算法框架得出最终推荐结果。在MovieLens-1M、MovieLens-100K和 Amazon-baby三个公开数据集上的实验表明,该算法在推荐准确率、召回率、MRR、命中率和 NDCG 五个指标上均优于基线方法。     

改进的自适应邻域的多目标进化算法

提出了一种新的自适应邻域的多目标进化算法,该算法采用自适应邻域的方法维护群体的分布性。探讨了根据当前群体情况进行自适应改变邻域半径,避免了传统邻域策略所引起的邻域半径的取值影响群体分布性的问题。另外,利用自适应邻域半径和拥挤距离进行密度估计,使密度小的个体得到保留。实验结果表明,所讨论的方法是有效的,在保持群体分布性上优于NSGAII和NMOEA。     

基于图染色问题的混合优化算法

为了提高图染色算法的寻优能力和收敛速度,结合禁忌搜索算法和遗传算法的优缺点,提出了一种混合优化算法（GA-HM）。该算法利用遗传算法生成初始解,将染色元素分到不同的色集中,然后通过禁忌算法进行变领域搜索来更新顶点染色。实验结果表明,GA-HM对求解相同的目标解具有更好的全局最优性和收敛性。     

基于知识图谱和图注意力的众包任务推荐算法

为解决目前众包任务推荐存在未考虑任务文本信息和数据稀疏的问题,提出一种基于知识图谱与图注意力的众包任务推荐模型。该模型首先利用自然语言处理技术提取任务文本信息中的关键要素,用于丰富图谱信息和缓解数据稀疏性;通过融合用户—任务交互图中的协同信息来构建协同知识图谱,在协同知识图谱中按协同邻居的类型分别运用图注意力网络;为获取用户准确的偏好,聚合邻居信息时按注意力得分从高到低采样固定数目的邻居;最后通过聚合不同类型的协同信息生成用户和任务的嵌入表示并得到交互概率。在构建的众包数据集上进行实验的结果表明,该模型在AUC、精准率、召回率和NDCG四个指标上均优于基线模型,验证了模型的可行性和有效性。