邻域搜索

摘要： 针对矩形件排样问题,给出精确的数学优化模型,提出一种改进邻域搜索算法的求解方法.为了克服一般邻域搜索算法易陷入局部最优解和搜索效率低的缺点,挖掘矩形件排样的问题特征,提出反悔算子、距离受限邻域算子、以“满足容忍度”接受劣解等3种新的改进策略.以矩形件排放顺序为编码,利用“最下左填充算法”进行解码,优化矩形件排样方案.对文献中的12个经典案例进行计算,通过对不同算法的计算结果进行比较和分析,改进邻域搜索算法具有明显优势,平均板材利用率能达到98.1%,表明了所提算法的有效性.

摘要： 高速铁路列车正晚点分布模型是研究正晚点预测和能力利用的基础,具有重要的理论与现实意义。提出一种邻域核密度估计模型(KDE-ND),针对采集的京沪高速铁路沿线车站列车运行实绩数据,进行列车到达的正晚点分析。该模型以高斯核为核函数,利用邻域搜索算法求得最优带宽值。为全面评价分布模型的拟合效果,基于决定系数等4项拟合优度指标,提出一种新的综合评价指标,并将包括KDE-ND模型在内的3种KDE模型与其他参数化模型进行综合评价指标的对比。实验结果表明,KDE-ND模型具有更优的拟合效果,可以更加准确地刻画高速铁路列车正晚点的分布规律,为高速铁路运输组织和仿真分析提供借鉴。

摘要： 文章主要研究多目标柔性作业车间的调度问题,以完工时间、机器总负载、生产成本为优化目标,建立多目标柔性作业车间调度模型。针对传统的非支配排序遗传算法(non-dominated sorting genetic algorithm II,NSGA2)在求解多目标柔性作业车间调度中出现的过早收敛或局部收敛问题,提出了改进的NSGA2算法。将传统算法精英保留过程中直接选取前N个最优个体作为新一代种群改为先选取前N×α个个体,然后在次优前沿面上随机选择剩余个体,避免了种群多样性降低导致的算法陷入局部收敛,同时加入了邻域搜索,弥补了传统算法在局部搜索上的不足。通过实验仿真验证了算法的有效性。

摘要： 连续体结构拓扑优化过程中往往存在着棋盘格和网格依赖性等数值不稳定现象,过滤算法是解决此类问题的有效手段,其实质是对单元灵敏度进行光滑处理。灵敏度过滤算法是将中心单元灵敏度用其过滤半径内单元灵敏度的加权平均值替代。在面向复杂工程结构时,由于结构网格量规模庞大,如何准确且快速确定单元的邻域是影响计算效率的关键一环。现广泛使用的是通过枚举计算单元形心间的距离,这种方法易于实现但需要消耗大量计算用时,且无法反映单元之间的连通关系,不能适应结构当中存在孔洞等非设计域的情况。为避免上述情况产生,基于双向渐近结构优化法,提出一种准确快速搜索单元邻域的新策略,通过构建的节点与单元的关联信息,建立从中心单元—从属单元—邻域单元的逐层搜寻模式。这种搜索策略可以极大节省前处理运算耗时,也能够适用于任意非规则网格以及三维模型。最后引入了存在非设计域孔洞的算例,发现使用此过滤策略能够得到性能更优的结果,得到的柔度值比使用枚举的方法低4%,同时能够有效消除“孤岛”现象。

摘要： 针对多无人机同时执行多个截止时间不一致的数据摆渡任务时,无人机与任务“一一对应”的分配方式会导致部分任务完成效果差及无人机能耗效率低等问题,提出了一种基于任务拆解与重组的“交叉执行”任务分配方法。根据任务截止时间对多个任务进行碎片化分解,并为每个碎片设置时间戳,而后执行基于时间戳碎片的任务重组及无人机协同任务分配。将该问题建模为带有时间窗约束的组合优化问题,并以无人机总能耗最小化为目标,采用改进遗传算法求解,通过引入大规模邻域搜索中的“破坏和修复”思想,弥补了传统遗传算法易陷入局部最优解的缺陷。仿真结果表明,与其他算法相比,提出的“交叉执行”任务分配方法能够在满足任务截止时间的前提下,无人机总能耗降低约17.7%~41.9%;同时,与传统遗传算法相比,提出的改进算法也能够使无人机总能耗平均降低约12%。

摘要： 针对传统的加工与装配分阶段独立调度中资源利用率不高的问题,将加工与装配联合同时进行调度。在考虑工件批量和批次的前提下提出一种改进遗传算法求解该问题,以最小化最大完工时间为优化目标建立数学模型,根据问题特性提出一种工件末工序前移的邻域结构,提升了算法的局部搜索能力进而改善整体求解质量。设计了一种基于装配设备负载均衡的混合贪婪解码方法,完成了装配设备选择。考虑到实际车间中机器故障的特点,提出了相应的响应策略和染色体更改规则,解决了动态调度问题。最后通过算例分析验证了所提算法和策略求解该问题的可行性和有效性。

摘要： 电动汽车电池容量有限,出行过程中需要通过快速充电来完成原定行程,由于充电站内配置不同功率类型充电桩,使得充电持续时间不等。通过分析配备正常、快速、超快速三种模式充电桩的快充站来模拟具有时间窗的电动汽车快速充电路径规划问题,提出一种自适应大邻域搜索算法,并结合CPLEX工具有效探索充电路径,实现运行最少数量电动汽车的同时最大限度地降低总的充电成本目的。通过与已有文献测试算法算例对比分析,验证EVRPTW模型具备更好的性能,且快充站可以减少充电成本的和车队规模。

摘要： 在软件定义网络(SDN)中,当流传输路径信息获取受限时,现有的测量节点选择算法只能基于网络拓扑的中心性指标进行测量节点选择,存在测量精度较低、测量负载不均衡、运行时间长等问题。将SDN网络中测量节点选择问题抽象为最小顶点覆盖模型,提出一种基于蚁群优化的测量节点选择算法ACO-NS。利用复杂网络的度分布理论缩减状态转移过程中的候选集规模,同时设计一种信息素局部增强-全局挥发机制,增大可行解的信息素浓度,提高算法的准确度和收敛度,并且缩短搜索时间。通过OpenFlow消息在线计算测量节点的负载,采用邻域搜索策略对过载节点进行筛选和替换,以降低过载处理的时间。实验结果表明,与ACO算法相比,该算法的准确度和收敛度分别提高56.7和28.2个百分点,且单位时间内的过载处理开销降低79.8个百分点,具有较高的测量精度。

摘要： 对于求解带时间窗口车辆路径问题,提出一种融合邻域搜索策略的改进蚁群算法,针对时间窗口特性,将等待时间加入到蚁群算法的状态转移规则之中。为提升算法的局部寻优能力,设计多种节点删除操作和插入操作对得到的路径进行邻域搜索。最后利用Solomon标准算例对改进算法进行测试,与目前已知最优解对比,实验结果表明改进后的蚁群算法对带时间窗口的车辆路径问题有较好的适用性。

摘要： 动车运用所的调车计划编制随着检修任务的增加而变得越来越复杂,调车计划编制的自动化对于增强动车运用所的检修能力具有重要意义。以最小化动车组检修任务完成时的时刻之和为目标,考虑动车运用所的股道占用冲突等约束构建优化模型,设计的贪婪算法结合邻域搜索的启发式算法可以对调车计划编制的自动化问题进行快速求解。最后,设计算例验证本文算法的有效性。研究发现,对于15组动车组规模的5个算例,平均Gap值为0.87%,且有3个算例直接求出了最优解;对于20组动车组规模的5个算例,邻域搜索改进的平均值为1.35%。

摘要： 为节约混载校车路径问题求解过程中邻域解搜索的时间,引入时空距离和时空相关度概念,将邻域搜索空间限定在合理的范围内.该算法首先计算站点间的时空距离,再附加上简单约束的预判断,从而得到时空相关度矩阵.然后对于任意学生乘车站点,将其他可能与之直接相连的站点按照时空相关度排序,形成一个邻接列表.在邻域搜索过程中,通过限定邻接列表长度,仅尝试最终接受概率较大的一部分移动操作,以此缩小邻域搜索空间,从而提高算法效率.在国际标准案例上的测试结果表明,基于时空相关度的搜索策略能在基本不降低求解质量的情况下,平均节省50％以上的求解时间.

摘要： 分析了Γ型匹配网络的结构和参数，提出了VSWR解空间中可能存在两个局部最小值的问题;介绍了邻域搜索算法的基本概念及其迭代步骤，分析了不同邻域结构的特点，指出通过变换邻域结构和搜索步长来跳出局部最小值的调谐方法;最后通过仿真验证了该方法的可行性，为进一步的研究提供了参考。

摘要： 针对常见QAM和PSK调制信号的半正定松弛（SDR）多输入多输出（MIMO）检测模型无法进行软输入迭代检测这一缺陷，提出了一种将先验信息项表示为规划决策变量线性函数的方法。结合基于硬判决的邻域搜索软输出算法，构成了一种通用QAM和PSK信号的软输入软输出半正定松弛MIMO检测器。仿真结果表明，通用QAM和PSK信号的软输入软输出半正定松弛MIMO检测器具有良好的检测性能，并且通过软输入软输出迭代大大提高了检测性能。

摘要： 基于块的纹理合成,通常可以分为两个阶段:1.选取:根据已合成的纹理在样图中搜索到最匹配的块;2.拼接:把选取到的块拼接到已合成的纹理中.本文提出的算法简单快速,对自然纹理和半结构纹理有很好的合成效果.在选取阶段,本文提出了一种基于块的邻域搜索算法,与以往的基于象素的L-邻域不同,该算法构建基于块的L-邻域,在利用L-邻域减少搜索空间的同时,利用块能够保持纹理结构信息的特性来保证合成纹理的结构连续性和完整性.在拼接阶段,采用动态编程方法求出重叠区域上的最小误差边界,并利用羽化进一步光滑边界。

摘要： 本文研究了求解VRP的改进离散型和声搜索算法.鉴于和声搜索算法产生新的和声的过程随机性太大、搜索过程容易陷入局部最优等问题,提出了一种结合多重邻域搜索方式的和声搜索算法.在该算法中,从和声记忆库中随机选取一条和声,对于和声记忆库内,对该条和声的每个音调以一定的概率进行邻域搜索以减小和声记忆库内随机选取分量的随机性;对于和声记忆库外,随机选取音调,以一定的概率替换该和声的某个音调以提高全局搜索能力;以邻域搜索的方式对和声记忆库中已产生和声分量进行扰动,避免陷入局部最优;以一定概率接受迭代过程中的最优解.通过对不同规模的算例进行实验,测试结果验证了改进算法的有效性.

摘要： 本文提出了一种基于二维激光测距仪的提取算法,该算法可以用于自主移动机器人在结构化和半结构化环境中提取道路可行区域。该算法首先基于8邻域搜索法搜索激光数据点,以已测的邻域点为参考点,结合角度和高度差双阈值的方法对数据进行归类并检测道路边界,利用障碍物检测原理获取障碍物,提取出机器人的可行区域,为路径规划提供参考依据。实验结果表明,该方法能够快速有效地提取机器人行驶过程中的道路可行区域。

摘要： 借鉴数据挖掘领域内的离群点探测技术,提出了适合于海量点云数据的、基于切片技术的粗差探测算法,算法将3D点云经过切片降为2D点,有效解决了3D环境下邻域搜索和粗差指标计算效率低下的问题,使算法整体效率和易用性得以显著提高.

摘要： 基于分解的多目标进化算法MOEA/D是最近提出的一种高效率的计算框架，它将一个多目标优化问题分解成一系列单目标优化问题.根据相邻的子问题信息同时优化各个子问题，最终得到一个Pareto最优解集.本文在分析其局限性的基础之上，提出了一种改进的基于分解的多目标进化算法IMOEA/D，通过设定一个阁值，引入非支配解保存机制和邻域搜索，改善了MOEA/D的分布性。仿真结果表明了IMOEA/D的高效性和有效性.

摘要： 邻域粗糙集模型可以直接处理连续型数据.邻域模型的属性约简是其重要研究内容之一.求取邻域的时间是影响提高邻域模型属性约简算法效率的一个瓶颈.本文提出了一种新的快速邻域搜索的策略,减少了样本之间的比较次数,提高了时间效率.实验结果表明提出的算法是有效可行的.

摘要： 针对传统PL（Priority List）方法采用单一排序指标，即平均满负荷费用AFLC（Average Full-Load Cost）不能全面反映机组优先顺序的不足，本文提出一种扩展优先顺序法EPL （Extended Priority List）解决机组组合问题。在分析PL 方法特点的基础上，定义μ-Load Cost 反映机组在不同出力范围内的经济指标，而后定义机组的效用系数UUR（Unit Utilization Ratio）优化机组的优先顺序。此外，引入参数控制机组组合邻域的规模并采取策略对机组组合进行调整使其满足所有约束，从而提高计算效率。最后采用26 机组、38 机组以及45 机组24 时段等3 个系统的测试结果来验证该方法的有效性。

摘要： 一种求解图像分割问题的基于邻域分解的迭代局部搜索方法，先通过图像预处理技术将彩色图像转化为带权无向图，构建归一化割(normalized cut)的图划分模型，然后通过求解归一化割(normalized cut)的图划分问题来实现图像的分割。该算法为启发式搜索算法，算法框架主要分为解的初始化、局部搜索程序和扰动程序三个部分。首先，随机生成初始可行解；然后迭代地使用局部搜索和扰动程序对解进行优化，直至满足终止条件。本发明方法对于图像分割问题的准确度和时间效率进行了优化，从而提高了图像分割的准确度和速度。

摘要： 本发明实施例公开了一种基于变邻域搜索和引力搜索混合算法的调度方法及系统，该方法包括：1设定算法的参数；2初始化算法初始解；3执行基于GSA的局部搜索；4更新初始解；5判断算法执行的终止条件是否满足，若满足则输出算法搜索的全局最优解，否则返回步骤3；本发明能针对基于位置学习效应和线性启动时间的连续批加工调度问题，求得近似最优解，从而使得企业能在最大限度上充分利用其生产资源，降低生产成本，并提高企业服务水平和顾客满意度水平。

摘要： 本发明实施例公开了一种基于变邻域搜索和引力搜索混合算法的调度方法及系统，该方法包括：1设定算法的参数；2初始化算法初始解；3执行基于GSA的局部搜索；4更新初始解；5判断算法执行的终止条件是否满足，若满足则输出算法搜索的全局最优解，否则返回步骤3；本发明能针对基于位置学习效应和线性启动时间的连续批加工调度问题，求得近似最优解，从而使得企业能在最大限度上充分利用其生产资源，降低生产成本，并提高企业服务水平和顾客满意度水平。

摘要： 本发明公开了一种基于大规模变邻域搜索策略的绿色物流车辆调度规划方法及系统。首先分别使用CW节约算法、最邻近插入算法和随机方法生成初始车辆配送序列。多次重复上述过程，构成初始配送序列的种群；对每个配送序列采用自适应遗传算法进行调度搜索，寻找满足条件的可行调度；采用大规模变邻域搜索算法对满足条件的可行调度进行优化调整，获得候选的配送序列；依据经济成本和环境成本最低的原则，从所有候选配送序列里选择总成本最低的序列，输出为车辆调度规划方案。本方法和系统可以在保证绿色物流车辆调度规划方案成本最优的同时提高求解速度，所得出的最优配送计划能够综合考虑经济成本和环境成本，有利于优化经济和环境指标。

摘要： 本发明公开了一种基于大邻域搜索算法和K‑means的多星多任务规划方法，其特征在于，包括以下步骤：S1、将任务集合表示为有色图理论中需要上色的顶点；S2、基于上一步获得的任务集合进行模型构建，对模型进行优化及价值评估；S3、经过搜索算法对上一步构建的模型进行资源上色，而基于资源上色后进行任务分配；设计一种基于大邻域搜索和K‑means的多星多任务规划算法，本算法提出基于有色图理论的多星多任务多约束分配方法，以K‑means聚类获取同类型设备，其次利用有色图表示任务和资源的映射关系，再以启发式搜索方法为综合效率最优搜索方法，为每个卫星建立元任务序列。

摘要： 本发明公开了一种解决多配送中心两级城市协同配送的大邻域搜索方法，包括以下步骤：S1：根据客户点与网点之间的距离，构造初始可行解；S2：对初始可行解进行大邻域搜索，确定最新第二级配送网络；S3：对最新第二级配送网络进行优化；S4：基于优化后的最新第二级配送网络，对市趟运输线路进行重构，得到可行市趟运输线路；S5：对可行市趟运输线路进行优化，并对由配送中心与网点之间的车辆运输线路构成的一级路径进行优化，得到最新可行解；S6：根据最新可行解确定当前解，并根据模拟退火准则判断是否达到算法终止条件，若是则结束大邻域搜索，否则返回步骤S2。本发明通过整体优化两级配送网络中的市趟运输线路、最后一公里线路以及车辆调度，降低了整体网络成本而不仅是某单一配送中心配送网络成本。

摘要： 本发明提出一种基于领域搜索动态规划算法的双风轮风力机协同保护方法，通过采集双风轮风力机运行的原始数据并进行处理，建立双风轮风力机协同保护动态规划模型，采用内点法对变量松弛的综合目标优化问题进行求解的到连续最优解；采用领域搜索动态规划算法对前后风轮依次进行多轮优化，迭代计算最优控制算法和最优控制规律。本发明的方法可识别分类多种风况，适用范围和运行灵活性更高；采用动态规划算法并引入降载荷函数，兼顾了风力机运行效率和运行的安全性；使用邻域搜索算法，缩小规划算法搜索空间，提升了控制算法的计算速度。

摘要： 本发明公开了一种基于变邻域搜索的多卫星区域观测规划方法，其步骤包括：1、将局部网格嵌套方法与变邻域搜索算法结合起来，通过局部嵌套构造新的条带对当前覆盖方案进行扰动；2、提出了两种邻域构造方式，来构造从不同层次选择的条带寻找当前解的邻域解。本发明能丰富卫星区域观测条带，获得更好的覆盖方案，并提高卫星资源的利用效率。

摘要： 本发明提供一种基于记忆精英种群的灾变自适应大邻域搜索方法及装置，属于人工智能技术领域。所述方法包括：构建任务分配优化模型；该模型包括目标函数和多个约束条件，目标函数用于表征最小化机器人的最大完工时间，多个约束条件包括任务分配约束条件和任务优先级约束条件；初始化搜索种群和精英种群；通过迭代执行以下步骤来求解该模型，直至迭代次数大于终止迭代次数：针对搜索种群中的每个解，采用自适应大邻域搜索算法对当前解进行邻域搜索，并检测当前解是否被更新；若是，则对精英种群进行相应更新；若否，则在满足灾变条件时从当前的精英种群中随机选择一个解对当前解进行更新，可以弥补自适应大邻域搜索过程的无记忆性和提高搜索深度。

摘要： 本发明公开了基于变邻域搜索算法的考虑行人通行的交叉口调度方法，在车路协同系统中，基于通信模块与计算机模块统一的交叉口管理器获取通过自动交叉口区域车辆的运行信息，交叉口管理器根据信息，通过设计出的基于人均最小延迟的通用框架制定出交叉口内网联自动驾驶汽车与行人的通行顺序，同时设计了一种可变邻域搜索算法来进行优化，求得车辆和行人的最优通过方案。本发明以高承载车辆有更高的通行权通过交叉口为特点之一，与传统的驱动交通信号控制相比更能减少车辆的延迟，更加关注自动交叉口的安全性和效率。