摘要：给定一个无向图,符号网络划分问题(signed graph partitioning problem,SGPP)是将节点集合划分为K(K≥2)个互不相交的非空分组,旨在最小化所有位于分组内的负符号边权重之和加上位于分组之间的正符号边权重之和,使网络划分结构尽量趋于平衡。SGPP是NP难问题,在计算机视觉、社交网络分析、生物信息学等实际领域中具有重要应用。但大数据时代的到来给求解大规模SGPP带来一定的挑战。因此,设计新颖且高效的学习驱动型扩展变邻域搜索算法(learning driven extended variable neighborhood search,LDEVNS)来求解SGPP。具体来说,该算法设计全新的快速增量更新策略以及高效的扩展变邻域搜索,同时结合强化学习机制来调整算法搜索过程中的前进方向,进一步探索更有希望的解空间区域来找到更高质量的求解方案。实验部分使用15组大规模社交网络图来评估LDEVNS的高性能,实验结果显示,LDEVNS在求解质量和计算时间方面相较于当前表现最佳的算法具有显著优势,同时也验证了强化学习在LDEVNS中的有效性。

摘要：公共交通乘务调度问题是一个将车辆工作切分为一组合法班次的过程,它是NP难问题,许多求解方法的效率都与班次评价密不可分,本文通过裁剪TOPSIS方法(Technique for Order Preference by Similarity to an Ideal Solution)设计了TOPSIS班次评价方法.此外,通过裁剪变邻域搜索算法使之适合求解乘务调度问题,提出了基于变邻域搜索的乘务调度方法(Crew Scheduling Approach Based on Variable Neighbourhood Search,VNS),其中,并入了TOPSIS班次评价方法在调度过程中进行班次评价,设计了两种带概率的复合邻域结构以增加搜索的多样性,帮助跳出局部最优,在VNS中利用模拟退火算法进行局部搜索.利用中国公共交通中的11组实例进行了测试,测试结果表明,VNS优于两种新近提出的乘务调度方法,且其结果关于班次数接近于下界.

摘要：本文提出了一种基于变邻域搜索与人耳掩蔽效应的音乐生成方法,以克服传统的作曲方法门槛过高、可重复性工作较多等缺点,并且相较于现有音乐生成模型具有操作直观、能够挖掘乐谱长时间内的连贯性等优点.训练阶段的输入选择易获得的时域波形文件,通过基于音高显著度的频率提取和基于掩蔽效应的时域分块获得乐谱,经过预先设定的音乐参数进行训练.生成阶段采取变邻域搜索与人工操作相结合的方式,通过对乐谱中音符进行增删、转调等操作按小节生成具有艺术性的乐谱,并根据操作者的偏好对乐谱进行人工修改与锁定.随后,以4小节为单位一次生成音乐片段,并组合成持续时间较长的一段音乐片段.最后在不同时间尺度完善乐谱,输出时域波形文件.整个流程可视化和人机交互的思想贯穿其中,能够充分调动音乐爱好者的积极性.同时本文提出了一种参数化乐音模拟的方法用于修饰乐谱或生成全新的音色,可根据乐器的分类方法或人的发声过程,通过声源激励与共振腔模拟两个部分参数化模拟乐器与人声.

摘要：针对热轧圆钢的批量调度问题,考虑实际生产中工艺规程和交货期对轧制单元连续加工的影响,建立了以最小化设备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化目标的数学模型,并设计了一种嵌入EDD规则的变邻域搜索算法.算法首先结合模型的约束特征,采用约束满足技术生成初始解;根据实际生产需求,将最小化设备调整时间作为主要目标,设计变邻域搜索算法实现目标优化,其中,运用混合算子构造邻域结构和局部搜索,并引入模拟退火接受准则来控制迭代过程中产生的新解;同时,为了最小化拖期惩罚和钢种跳跃惩罚,在求解过程中嵌入了EDD规则以及钢种排序规则.实验结果表明,模型和算法是可行且有效的.

摘要：针对成型机故障和工单交货期提前两类事件,提出一种基于改进变邻域搜索算法的分批重调度方法,基于最小分批原则和非等量分批原则对工单进行批量划分,考虑重调度过程的稳定性与准时性,建立数学模型。设计一种改进的变邻域搜索算法(VNS),通过构建转移邻域和叠加邻域两种邻域结构,提高了搜索的收敛速度和寻优能力。最后以某磁性材料成型车间作为实例进行验证。结果表明,所提重调度方法能够在保证工单准时交付的基础上,提高成型机利用率,为工厂的实际生产决策提供参考。

摘要：针对新工件突然到达干扰下的单机最大延迟时间重调度问题,提出一种融合和声搜索与变邻域搜索技术的混合算法。该算法运用两阶段启发式与排序解随机生成相融合的方法来初始化和声记忆库,在和声搜索迭代框架中嵌入了结合问题特征的变邻域搜索算子。为进一步强化算法的寻优能力,设计了基于占优性质的非最优解排除方法,在变邻域搜索算子的局部搜索环节中实施。通过参数校准实验及其结果分析,得出和声记忆库规模与和声记忆思考率两个参数的建议取值。运用校准后的算法对大量算例进行计算测试,并与单独应用变邻域搜索技术的3种已报道算法展开优化性能比较,结果表明所提算法在解的质量与鲁棒性上均具备比较优势。

摘要：针对预防维护下的装配线平衡问题,提出了一种带有重启策略的多目标变邻域搜索算法,以优化正常工作、设备维护情形下的节拍与工序调整。算法结合启发式与随机方法得到较优初始解;设计并筛选出寻优能力较强且具有互补性的四类邻域算子及其搜索策略,以更好地进行全局探索与局部开发。为促进Pareto前沿推进,提出了一种具有自适应能力的重启算子,以便根据问题规模调整重启代数阈值、参考寻优进程扩大搜索空间。该算法机制简单且无固定参数,实验结果表明该算法能够获得具有竞争性的非支配解集。

摘要：针对多资源、多约束的资源受限舰载机保障作业调度问题,提出了一种求解该问题的基于变邻域搜索的分布估计算法.首先,建立了考虑站位、设备、作业的优先级和安全性等约束的调度模型,该模型以舰载机保障作业的总完成时间和舰载机移动次数的加权和最小化为目标;其次,结合问题特征分析,提出了最早可用设备规则,对偶站位交换规则等两类启发式规则,定义了基于序置换排列的解的编码方式;再次,提出了分布估计算法(EDA)的概率分布更新模型,以及基于工序插入、交换、反转等邻域操作的变邻域搜索策略,设计了基于变邻域搜索的分布估计算法(EDAVNS);最后,基于单波次8架舰载机保障的仿真结果,验证了所提模型对舰载机保障作业调度问题具有较好的实用性.同时,基于5个不同规模的问题集的分析结果表明:与分布估计算法、变邻域搜索、遗传算法、以及只使用插入、交换、反转等单一邻域操作的EDA算法相比,EDAVNS均取得了最优的结果,验证了EDAVNS能有效地求解该问题,并较好地平衡全局探索与局部搜索.

摘要：针对排序依赖转换时间的两机器机器人制造单元调度问题的NP难特性,设计了变邻域搜索算法求解。为了加快算法收敛速度,设计了工件阻塞时间最小化生成初始解;为了搜索到更好解,分析了算法的参数取值。通过随机产生算例测试,提出算法优于模拟退火算法,证实了提出算法的有效性。

摘要：针对运输-装配协同优化问题,建立其整数规划模型,提出一种融合分解策略的学习型变邻域搜索算法(learning variable neighborhood search with decomposition strategy,LVNS_DS)对其求解。为降低问题的求解难度,设计一种分解策略将原问题分解为路径规划问题和装配线平衡问题;应用LVNS算法对2个子问题进行求解;通过合并子问题解可得原问题的完整解。相比常规VNS算法,LVNS算法依据邻域动作概率值来转换邻域结构,依据邻域动作产生的贡献来动态地更新其概率值,LVNS算法能以较大的概率值选择适于当前搜索阶段的邻域动作,从而易于找到子问题的优质解。通过不同规模算例的仿真实验,验证了运输-装配协同优化的有效性和LVNS_DS算法的有效性。