两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

求解恰当可满足性问题的随机局部搜索算法

可满足性问题(SAT)是一种NP完全问题,被广泛运用于人工智能和机器学习等研究。恰当可满足性问题(XSAT)是SAT中一类重要的子问题。目前的大部分关于XSAT的研究主要为理论层面,对高效的求解算法特别是具有高效验证性的随机局部搜索算法研究很少。针对以上问题,分析了基础编码和等价编码两种转化方式的公式的部分性质,提出一种直接求解XSAT的随机局部搜索算法WalkXSAT。首先使用随机局部搜索框架进行基础搜索与条件判定;其次加入变元所属文字的恰当不可满足计分值,优先处理不易恰当满足的变元;然后使用防重复选择翻转变元的启发式策略减小搜索空间;最后,采用多种来源以及多种格式的实例进行对比实验。在直接求解XSAT时,相较于ProbSAT,WalkXSAT的变元翻转次数与求解时间显著减少;在求解基础编码转化后的实例中,当实例变元规模大于100时,ProbSAT已失效,而WalkXSAT依然能够在短时间内求解。实验结果表明,所提WalkXSAT精确性高、稳定性强、收敛快。

基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题

覆盖推销员问题(Covering Salesman Problem,CSP)是著名的旅行商问题的一个变体,是NP难问题。给定一组顶点和每个顶点相关联的预定覆盖半径,CSP的目标是在顶点子集上找到一个最短长度的哈密顿回路,使每个顶点被访问或者在被访问顶点的覆盖范围内。为提升搜索候选顶点集的质量,提出一种基于多顶点替换的搜索策略,并将该策略引入到迭代局部搜索算法解决CSP。所提CSP算法通过扰动过程和改进过程的迭代探索邻域最优解,其中扰动过程将搜索发散到未探索的区域,改进过程提升解的质量。实验结果表明,多顶点替换方法相比“移出-重新插入”过程可以获得更高质量的候选顶点集。所提CSP算法在寻优的正确率上取得了不错的成效,尽管运行速度与其他启发式算法相比有差距,但可以在合理的运行时间内解决CSP。

基于改进后局部搜索算法的猕猴桃预估产量在种植区域的分配性能

为进一步提高猕猴桃(Actinidia chinensis Planch.)预估产量在种植区域的分配性能,通过麻雀搜索算法、可变螺旋因子来改进局部搜索算法,并利用逐维透镜学习策略加快改进后局部搜索算法的收敛速度。结果表明,当猕猴桃预估产量不变时,随着可变螺旋因子数值增加,分配时间逐渐降低;当可变螺旋因子数值不变时,猕猴桃预估产量增加,分配时间也增加。猕猴桃预估产量分别为10、20、30、40、50、60 t,4个种植区域面积分别为500、650、700、850 m^(2)。建议当猕猴桃预估产量为10~60 t时,可变螺旋因子数值设定为4;当预估产量为10~40 t时,种植区域3可以满足最佳种植间隔,当预估产量为50~60 t时,种植区域4可以满足最佳种植间隔,根据不同预估产量及种植区域面积合理进行猕猴桃种植间隔分配,保证猕猴桃获得充足的养分。改进后局部搜索算法的收敛速度较快,在迭代500次时,算法已趋于收敛,深度学习、粒子群算法及灰狼算法的收敛速度均小于改进后局部搜索算法。

引入改进迭代局部搜索的灰狼算法及应用

针对标准灰狼算法(GWO)收敛速度慢,易陷入局部最优等缺点,提出一种引入改进迭代局部搜索的灰狼算法(IGWO)。首先,通过佳点集策略增强初始种群的均匀性与多样性;其次,采用双收敛因子,收敛因子基于种群位置非线性自适应更新,在种群寻优全期平衡全局勘探与局部开发能力;再次,在种群位置更新公式引入欧氏动态权重与莱维飞行策略,提升寻优精度,并帮助种群跳出局部最优值;最后,引入改进迭代局部搜索,使算法的搜索能力更加灵活,帮助算法加速收敛。通过10个基准测试函数的仿真分析及种群寻优平衡性对比,证明了IGWO具有更优的寻优精度、稳定性及收敛速度,随后将IGWO应用于工程优化问题中,相比GWO、GJO、WOA、HSSAHHO、SCHOA、NCPGWO、DSFGWO 7种算法,适应度分别优化了3.25%、27.2%、28.9%、3.15%、3.04%、0.23%、0.07%,证实了在工程应用中的可行性和有效性。

基于局部搜索NSGA2算法的含油污水资源分配

针对目前油田含油污水回收分配存在运营成本较大以及回收作业区资源利用率较低的问题,提出一种基于局部搜索NSGA2算法的含油污水资源分配方法。首先,引入采油厂回收总成本以及回收作业区负载均衡度等指标建立组合评价体系,构建了面向含油污水产生方及回收作业区处理方的双角度多目标分配模型。其次,为了改善NSGA2算法计算过程中种群分布不均匀的情况并提高其收敛速度,提出一种基于混合移民策略的局部搜索机制,使用解的密度来衡量解的稀疏度,在稀疏解和种群领先解周围进行局部搜索,引导算法快速收敛。最后,以某采油厂为例,与多个算法进行比较,结果表明,所提算法所求解的质量均优于其他对比算法,验证了模型的适用性和有效性。

多舱共配绿色车辆路径问题的改进变邻域搜索算法

针对社区团购前置仓配送场景中“多中心、高时效、多品类、高排放”难题,本文提出多车场带时间窗的绿色多舱车车辆路径问题(MDMCG-VRPTW),构建混合整数线性规划模型,并设计改进的变邻域搜索算法(IVNS)实现求解.采用两阶段混合算法构造高质量初始解.提出均衡抖动策略以充分探索解空间,引入粒度机制以提升局部搜索阶段的寻优效率.标准算例测试结果验证了两阶段初始解构造算法和IVNS算法的有效性.仿真实验结果表明,模型与算法能够有效求解MDMCGVRPTW,且改进策略提高了算法的求解效率和全局搜索能力.最后,基于对配送策略和时效性的敏感性分析,为相关配送企业降本增效提供更多决策依据.

基于变邻域局部搜索的篡改图像检测算法

针对复制篡改图像的多个篡改区域检测率较低的问题,提出了一种基于变邻域局部搜索的篡改图像检测算法。提取图像分块后的SIFT特征,通过特征匹配算法判断图像是否经过篡改,合并满足相似性条件的由分块的超像素所得到的疑似区域以及变邻域局部搜索算法所得到的邻域块,采用形态学闭运算填补孔洞,完成篡改区域的检测。改进算法的检测准确率为91.1%,相较于其他两种算法,检测准确率分别提高2.6%和0.6%。仿真结果表明,改进算法对于复制篡改图像的单个篡改区域和多个篡改区域检测效果较好。

基于新混合乌鸦搜索算法的置换流水车间调度

为了更加有效地求解以最大完工时间最小化为目标的置换流水车间调度问题,提出一种新混合乌鸦搜索算法(NHCSA)。首先,对一种基于NEH的启发式算法进行了改进,在此基础上提出新的方法以改善初始种群的质量和多样性;其次,采用SPV(Smallest-Position-Value)规则进行编码,使算法能够处理离散的调度问题;最后,针对迭代贪婪算法,提出了自动调整重插入工件范围的方法、引入了TB机制,并采用改进的迭代贪婪算法对最佳工件排序进行局部搜索,以提升算法收敛的精度。基于典型测试集进行了仿真测试,结果验证了所提算法的寻优能力和稳定性。尤其是在针对Rec19和Rec25算例的比较中,仅NHCSA取得了当前最优解,进一步证明了其优越性。

改进麻雀搜索算法的轮式机器人路径规划

针对传统麻雀搜索算法(sparrow search algorithm,SSA)在轮式机器人路径规划应用中易陷入局部最优使得规划路径较长以及算法后期容易陷入早熟等问题,提出一种改进麻雀搜索算法(improved sparrow search algorithm,ISSA)应用在轮式机器人路径规划中。首先,在算法初期初始化种群时利用Logistic混沌提高初始种群的多样性;其次,将线性动态惯性权重调整方法引入到发现者位置更新中,使得算法的全局搜索能力以及收敛速度得以提升;然后,在跟随者位置更新方法中结合中垂线算法(midperpendicular algorithm,MA)使跟随者快速精准地向种群适应度最高的个体靠拢;最后,在算法后期结合最优爆炸粒子策略与反向学习策略在最优解附近产生扰动,防止算法后期陷入局部最优解。并且在机器人路径规划应用中将全局最优解再次进行局部搜索来提高机器人的路径规划能力。仿真结果表明,ISSA应用在路径规划中,其路径长度、寻优速度以及迭代次数方面均有显著提高。

融合局部搜索策略求解DCMST的改进稳态遗传算法

针对目前遗传算法求解度约束最小生成树存在的求解质量不稳定、局部搜索不完全的问题,提出一种融合局部搜索策略求解度约束最小生成树(DCMST)的改进稳态遗传算法。提出服从边隶属度值的度约束初始生成树算法,用来提高初始种群的质量;在局部搜索时引入禁忌搜索,防止相似解大量重复搜索;融合自适应变量和点替换的局部搜索方法,提升算法的局部搜索能力。仿真结果表明,提出的算法提高了初始解的质量,加快了算法的收敛速度,加强局部搜索从而提高了算法的求解质量,可获得较好的有效性与稳定性。

融合局部搜索与Pareto支配的多目标任务调度模型

为了解决复杂任务群调度过程中资源利用不均、任务完成时间较长等问题,以最小化资源负载均方差和最小化任务群完成时间为目标构建复杂任务群资源调度模型,提出一种融合局部搜索和Pareto支配的多目标优化算法BRLSN(multi-objective optimization based on boundary range local search and NSGA-Ⅱ,BRLSN)。该算法采用有效的编码方式与交叉变异算子进行迭代寻优,并利用基于边界区域局部搜索的精英保留策略扩大算法搜索范围,保存种群优良个体。实验结果表明,BRLSN相较于其他多目标算法在收敛性和多样性上有显著的提升,同时算法收敛速度更快,种群质量更高,明显优化了最终目标函数的结果值。

改进麻雀搜索算法求解多目标低碳冷链物流车辆路径问题

目的 在传统冷链物流的车辆路径问题模型基础上,考虑服务节点和车辆运输过程中产生的碳排放,并加入客户满意度,在有限资源情况下最小化路径成本和最大化客户满意度。方法 构建多目标低碳冷链物流车辆路径问题模型,将爬山算法局部搜索思想应用到麻雀搜索算法中,形成改进麻雀搜索算法,并用其对上海市某区域内的冷链物流配送路径优化问题算例进行求解。结果 通过与改进前及其他2种智能优化算法运行结果进行对比发现,改进后的麻雀搜索算法具有更快的寻优速度和更好的寻优能力,且改进后的算法对模型的碳排放效用性更高。结论 基于国家的低碳政策,设计出符合当下实情的低碳冷链物流运输模型,通过改进优化算法设计运输方案,验证了爬山算法局部搜索思想对麻雀搜索算法进行改进的有效性及所构建低碳冷链物流车辆路径模型的合理性。

矩形布局优化问题的局部搜索蜂群算法

带平衡约束的矩形布局问题属于组合优化问题,当问题规模增大时求解困难。为提高求解效率,设计了一个蜂群算法,通过分析解的分布,提供了基于贪心策略的群体初始化方案,选择了有效的变异算子,将蜂群算法的搜索空间聚焦于最优解可能的区域。另外设计了一个二次局部搜索算法,对解的质量进行进一步提升。在10个公开的案例上与目前性能最好的算法进行了对照,提出的蜂群算法在其中9个较大规模的案例上超过了现有算法。理论分析和实验结果表明,相对于现有算法,所提蜂群算法能明显提高求解效率。

局部搜索灰狼优化算法求解武器-目标分配问题

武器-目标分配(weapon target assignment,WTA)问题是根据武器对来袭目标毁伤概率的不同,合理确定待打击目标的武器分配方案,以达到用尽可能少的武器对来袭目标毁伤程度最大化的目的,是作战指挥决策领域的重要研究内容。在构建WTA问题模型的基础上,针对传统灰狼优化(grey wolf optimization,GWO)算法局部开发能力不足等问题,采取了一种精英保留及免疫变异局部搜索策略。改进灰狼优化算法(improved grey wolf optimization,IGWO)首先在灰狼种群中选择部分优质精英个体,然后通过随机点变异和受体编辑两种免疫局部搜索策略对精英个体进一步寻优,从而改善传统GWO算法过早收敛和易陷入局部最优的缺点。针对3种不同规模的武器-目标分配问题,将IGWO与交叉熵算法、传统GWO算法进行了对比,计算结果显示IGWO算法所求适应度值的分位数均明显高于对比算法,进而验证了IGWO算法的有效性。

基于SATLike3.0局部搜索求解器的算法改进

部分最大可满足性问题是可满足性问题的重要变体,它可以同时处理硬约束和软约束,因此可以对广泛的现实问题进行建模.局部搜索求解器是为该问题寻找高质量解的主流方法,它依赖于问题实例的初始数据状态.本文针对局部搜索求解器SATLike3.0的初始解生成过程,提出了优先满足硬约束的改进策略,最终得到的算法名为HFCRP-F.该算法作用于构造初始解和初始权重配置阶段,主要包括优先传播尚未满足的硬约束中的未赋值变量,以及根据已找到的解为约束增加初始权重,由此指导后续的局部搜索过程.本文采用MaxSAT Evaluation 2018–2021中的数据集对HFCRP-F和SATLike3.0进行测试,结果表明HFCRP-F处理加权实例的性能明显优于SATLike3.0,同时处理非加权实例的性能与SATLike3.0基本持平.

机械臂工作路径的改进蚁群-顺序局部搜索规划

为了减少机械臂末端路径长度和关节转动角度之和,提出了改进蚁群-顺序局部搜索的路径规划策略。建立了机械臂路径规划问题模型,对机械臂关节空间节点进行了离散化。使用顺序局部搜索方法确定下一节点待选集合,依据蚁群算法原理确定优化意义下的下一路径节点。考虑到传统蚁群算法收敛慢、求解质量不高的问题,构造了局部信息素随蚂蚁聚集度自适应更新方法,进而提出了局部信息素自适应蚁群算法。经实验验证,在无障碍物环境下,与传统蚁群算法相比,自适应蚁群算法规划路径长度减少了15.27%,关节转角和减少了0.78%。在障碍物环境下,与传统蚁群算法相比,自适应蚁群算法规划路径长度减少了3.26%,关节转角和减少了2.21%。在实物机械臂上进行验证,实验结果与仿真结果一致,验证了这里提出的路径规划方法的有效性。

多隔间车辆路径优化问题的局部搜索混合果蝇优化算法求解

为解决智能物流中多隔间车辆的路径优化问题,在标准混合果蝇优化算法的基础上,加入局部搜索以提高算法的搜索能力,通过确定每辆车所访问的客户以及访问的先后顺序形成车辆路径。数值对比实验表明,优化后的方法能显著改善多隔间车辆路径优化问题的求解质量,改善比例优于15%。

改进分散搜索算法求解包装废弃物回收路径规划问题

目的将包装废弃物回收路径规划归纳为一个带回路和时间窗的逆向物流车辆路径问题(RL-VRPBTW),以最小化回收成本、发车成本和时间窗惩罚为联合优化目标进行建模。方法引入“车辆剩余空间回收能力”因素,改进经典节约里程算法,求得较好的初始解;基于分散搜索框架,设计基于初始解改进的分散搜索算法(ISISS),根据问题模型,采用含0的编码方式,通过多样性产生、参考集更新、子集产生、子集合并、解改进等5个步骤实现算法功能。结果在“部分回收点分布较密集”的城市型地理场景下,针对快消企业的低值固废包装,生成回收点数量分别为50、100、200的3种规模算例,并考虑大小两种车型进行仿真实验。将ISISS算法与改进节约里程、遗传和分散搜索3种算法比较后可知,ISISS算法在大规模包装废弃物回收车辆路径问题上具有更优的求解性能。结论仿真实验结果表明,ISISS是一种求解多目标大规模包装废弃物回收路径规划问题的较优算法。

多邻域局部搜索算法在医院多阶段人力资源安排中的应用

医院人力资源管理中医护人员排班问题有助于提升工作效率和质量。研究在提出局部搜索算法的基础上通过多邻域策略进行优化,构建了交换型混合式MNBLS以实现医护人员的排班,同时探讨了随机挑选若干偶数天、随机一天内两种扰动噪声。不同类型的交换型混合式MNBLS均可在较短时间内接近最优解,在不同初始值下求得最优解的类型不同。最终确定的最佳迭代次数为120次,扰动天数和扰动医护人员人数分别为8天和30人,最优目标函数值为0。研究所给出的应用交换型混合式MNBLS实现医护人员值班表安排具有较高的运行效率,同时能满足医护人员排班安排过程中硬条件和软条件。