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

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

基于改进迭代局部搜索的多SMT产线多目标优化

针对多PCB订单在多条SMT生产线上的生产调度问题,同时考虑SMT生产线治具约束、生产线停线计划约束,建立以最小化总拖期为主目标和最大完工时间为子目标的数学模型。基于问题特性,提出了一种基于问题邻域知识的多目标迭代局部搜索算法求解问题模型,设计带约束的局部搜索在优化主目标函数时,将子目标函数限制在一定的允许量内,设计4种局部搜索算子局部寻优,扰动产生多个扰动解取Pareto最优解作为下一次的迭代解,增加算法全局搜索能力。在相同的计算资源下,对问题规模大于100×5(PCB订单数×SMT生产线数)的测试集,所提出的算法在主目标总拖期优化上相比传统迭代局部搜索算法提升35%以上,验证了算法的有效性。

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

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

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

覆盖推销员问题(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算法计算过程中种群分布不均匀的情况并提高其收敛速度,提出一种基于混合移民策略的局部搜索机制,使用解的密度来衡量解的稀疏度,在稀疏解和种群领先解周围进行局部搜索,引导算法快速收敛。最后,以某采油厂为例,与多个算法进行比较,结果表明,所提算法所求解的质量均优于其他对比算法,验证了模型的适用性和有效性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

求解蛋白质结构预测问题的局部搜索算法

蛋白质结构预测问题是计算生物学领域的核心问题之一。通过理论计算的方法根据蛋白质氨基酸序列直接预测其空间结构是解决这一问题的有效途径。构造了新的邻域结构,采用了部分随机跳坑策略,对此问题提出了新的局部搜索算法。计算结果表明,该算法计算效率要优于传统的遗传算法和Monte Carlo方法。对于链长为50的算例还找到了文献中所没有的全新的最低能量构形。

多目标遗传局部搜索算法的研究进展

在分析了由演化算法局部搜索能力差造成的多目标演化算法在收敛速度和求解精度上尚不能令人满意的局限性的基础上,详细地论述了融入局部优化方法的多目标混合演化算法能够有效地平衡算法的全局搜索与局部搜索能力、均衡搜索效率与效果,而且已成为求解多目标优化问题的一个非常重要而有前途的研究方向。其次,综述了多目标遗传局部搜索算法的研究进展与分类。最后,简单介绍了一些具有代表性的多目标遗传局部搜索算法,并提出了其有待进一步研究的若干方向和内容。

局部搜索与遗传算法结合的大规模复杂网络社区探测

基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上,给出一种快速、有效的局部搜索变异策略,同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的,采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Genetic algorithm with local search,LGA).在基准网络及大规模复杂网络上对LGA进行测试,并与当前具有代表性的社区探测算法进行比较,实验结果表明了文中算法的有效性与高效性.

基于混沌局部搜索算子的人工蜂群算法

在求解函数优化问题时,为了提升人工蜂群算法局部搜索能力,提出了一种新颖的混沌蜂群算法。新算法设计了一种混沌局部搜索算子,并将其嵌入蜂群算法框架中;该算子不仅能够实现在最优食物源周围局部搜索,还能够随着进化代数增加使搜索范围不断缩小。仿真实验结果表明,与人工蜂群算法相比,新算法在Rosenbrock函数上,求解精度和收敛速度明显占优;此外新算法在多模函数Griewank和Rastrigin上,收敛速度明显占优。