局部搜索算法

摘要： Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明,WWP+WalkSAT算法有较好的性能。

摘要： 针对当前局部搜索算法在求解大规模、高密度的分布式约束优化问题(DCOP)时,求解困难且难以跳出局部最优取得进一步优化等问题,提出一种基于局部并行搜索的分布式约束优化算法框架(LPOS),算法中agent通过自身的取值并行地搜索局部所有邻居取值来进一步扩大对解空间的搜索,从而避免算法过早陷入局部最优。为了保证算法的收敛性与稳定性,设计了一种自适应平衡因子K来平衡算法对解的开发和继承能力,并在理论层面证明了并行搜索优化算法可以扩大对解空间的搜索,自适应平衡因子K可以实现平衡目的。综合实验结果表明,基于该算法框架的算法在求解低密度和高密度DCOP时性能都优于目前最新的算法。特别是在求解高密度DCOP中有显著的提升。

摘要： 局部搜索算法是求解非对称分布式约束优化问题(asymmetric distributed constraint optimization problems,ADCOPs)的热点,然而此系列算法都未利用历史局部代价这一关键信息。提出了一种新的历史局部代价的算法(historical local cost,HLC),利用局部代价历史记录求解ADCOPs。HLC使用指数加权移动平均(exponential weighted moving average,EWMA)对局部代价进行模拟更新,并引入了种群机制对其充分模拟和搜索更广的解空间,从模拟局部代价的有效性和种群作用的优越性进行了理论分析。实验结果表明:HLC比最先进的ADCOPs非完备算法有更高质量的解。

摘要： 闭环布局问题(CLLP)是一种NP-困难的混合优化问题,它在大小可调的矩形环上寻找设施最佳放置次序,目标是最小化设施之间物料流的运输成本.现有方法均采用元启发式算法来寻找最优的设施放置次序,并且通过枚举方法来获得最优的矩形环大小,而枚举方法的计算效率不高.为了解决这个问题,提出了求解CLLP的混合群体增量学习(HPBIL)算法,分别使用离散群体增量学习(DPBIL)算子和连续PBIL(CPBIL)算子同时对设施放置次序和矩形环大小进行优化,提高了搜索效率;同时还设计了一个局部搜索算法来优化每代中的部分优质解,以提高算法的求精能力.在13个CLLP测试实例上进行实验,结果表明HPBIL算法在9个测试实例上找到了新的最优布局,它对CLLP的寻优能力明显优于对比算法.

摘要： 已有针对虚拟机映射问题的研究,主要以提高服务器资源及能耗效率为目标.综合考虑虚拟机映射过程中对服务器及网络设备能耗的影响,在对物理服务器、虚拟机资源及状态,虚拟机映射、网络通信矩阵等概念定义的基础上,对协同能耗优化及网络优化的虚拟机映射问题进行了建模.将问题抽象为多资源约束下的装箱问题与二次分配QAP问题,并设计了基于蚁群算法ACO与局部搜索算法2-exchange结合的虚拟机映射算法CSNEO来进行问题的求解.通过与MDBP-ACO、vector-VM等四种算法的对比实验结果表明:CSNEO算法一方面在满足多维资源约束的前提下,实现了更高的虚拟机映射效率;另一方面,相比只考虑网络优化的虚拟机放置算法,CSNEO在实现网络优化的同时具有更好的能耗效率.

摘要： 合理的资源配置是提高项目调度鲁棒性一种有效的方法.本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性.本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响.为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案.最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法.

摘要： 车辆路径问题是物流配送过程中的关键环节,车辆路径优化问题是一个典型的有约束的组合优化问题,属于强NP问题。本文在建立车辆路径模型的基础上,运用分区算法,把大量的数据区域划分成几个不同的较小的数据区域,利用局部搜索算法和遗传算法结合的新的混合遗传算法来确定具体的快递车辆的配送路径。仿真实验证明,该混合遗传算法在寻找最优解上具有可行性,而且在运算效率方面有相应的提升。

摘要： CT系统除需要设备支持外,参数标定精度和成像模型对扫描效果具有显著影响.本文巧妙地利用模板与探测器的关系,寻找最佳标定位置,精确地对CT扫描系统进行参数标定,在此基础上,建立含有插值、滤波、局部搜索算法的CT介质成像优化模型,并列举实例进行图像重构模拟分析,最后利用逐差法设计更加精确的标定模板.

摘要： 本文以民用建筑结构为研究对象,讨论了现有求解可靠度指标β的比较成熟的方法及需进一步完善的地方,然后从可靠度指标β的几何意义出发,建立了基于最优化理论的求解结构可靠度指标的模型,利用现在应用比较广泛的最优化方法——遗传算法——来求解可靠度指标,并且针对基本遗传算法"早熟"的缺点提出了把基本遗传算法和局部搜索算法相结合的思想:先用遗传算法对问题进行初步搜索,由于遗传算法的全局搜索特性,往往通过进化较少的代数就可以搜索到包括最优解的比较小的区域,然后把遗传算法的最终搜索结果作为局部搜索算法的初始值再进行局部搜索.算例表明,这种方法是一种十分有效的方法.

摘要： 针对每个划分子集要求至少满足一定数量点的k-means问题，本文给出了该问题的一个局部搜索随机算法。首先证明了如果七个中心点选自k个最优子聚类中的点，解的近似性能比的期望值至多为2。给出一个样本子集，证明了该样本子集至少以1/2的概率包含每个最优子集中至少一个点。利用取样技术，给出了一个改进的k-means局部搜索算法，算法的时间复杂度为O(nk3 dlog(n)log(k)/α)，理论与实验表明，此算法在运算时间上对现有算法进行了较大改进。

摘要： 本文提出了一个基于动态子句定权的SAT问题的局部搜索算法RCSAT.通过引入子句相关系数的概念,将算法中子句权重分为两个部分,静态部分为该子句的相关系数,在求解过程中保持不变;而动态部分为通常意义上的子句权重,反映着求解时该子句可满足的难易程度.随着求解的进行,动态权重需要不断更新以引导系统脱离局部最优.本文也给出了动态权重的更新算法.对一些SAT基准问题的求解实验表明,与现有算法相比,这个算法能够有效地减少求解某些问题的翻转次数,获得较好的求解性能.

摘要： 利用改进的协同免疫算法(ICIA)求解Flow Shop调度问题。算法中的疫苗取自迭代N次的局部最优解，并随着每代最优值的变化不断更新。为了克服协同免疫算法初期收敛速度慢的问题，加入了局部搜索算法；针对算法后期求解目标函数值差的问题，提出了一种新的种群选择机制“80/20法则”。通过与遗传算法(GA)和未改进的协同免疫算法(CIA)比较，仿真实验结果验证了ICIA解决Flow Shop问题的有效性。

摘要： 本文提出一种新的蚁群算法来求解移动通信中的频率分配问题.该算法在基本蚁群的基础上引入了精英策略,并实现了蚁群算法和局部搜索算法的结合.仿真结果证明,算法具有较强的全局搜索能力和较快的收敛速度,而且可以提高最优解的质量.

摘要： k-means聚类是聚类划分中应用最广泛的一种方案,但是现在许多关于此问题的研究并没有给出近似比为常数的算法.给出了一个随机算法,该算法通过以不同概率选取初始k个点,保证了以一定概率分别属于不同最优聚类簇的k个点.以这k个点作为初始中心点对输入点集进行交换分别执行局部搜索算法,证明了可得到近似比至多为2的解.实验结果表明该算法能够取得较优的近似解结果.

摘要： 在先行研究工作--利用局部搜索算法提高BP小波神经网络收敛速度的基础上,为了进一步增强小波神经网络的全局性搜索能力,讨论了小波神经网络BP局部搜索算法与全局性搜索算法--遗传算法相结合的方法,从而增强了小波神经网络的全局性搜索能力.最后,讨论了遗传-BP算法在小波神经网络压缩一维数据中的应用.

摘要： 组合优化问题优化问题可以分为两类:一类是连续变量的问题,另一类是离散变量的问题,后者称为组合优化问题.组合优化问题的任务:从一个有限或可数无限集里,寻找一个使得目标函数最优的对象——典型地包括:一组赋值,一个集合,一个排列.组合优化问题随处可见,具有很强的工程代表性应用.

摘要： 组合优化问题优化问题可以分为两类:一类是连续变量的问题,另一类是离散变量的问题,后者称为组合优化问题.组合优化问题的任务:从一个有限或可数无限集里,寻找一个使得目标函数最优的对象——典型地包括:一组赋值,一个集合,一个排列.组合优化问题随处可见,具有很强的工程代表性应用.

摘要： 组合优化问题优化问题可以分为两类:一类是连续变量的问题,另一类是离散变量的问题,后者称为组合优化问题.组合优化问题的任务:从一个有限或可数无限集里,寻找一个使得目标函数最优的对象——典型地包括:一组赋值,一个集合,一个排列.组合优化问题随处可见,具有很强的工程代表性应用.

摘要： 本发明公开了一种基于随机蛙跳全局搜索算法的局部阴影光伏阵列多峰最大功率跟踪(Maximum Power Point Tracking，MPPT)控制方法，以光伏阵列的输出电流作为算法的粒子，以光伏阵列的功率作为算法的适应度函数，通过随机蛙跳全局搜索算法这种新型快速且全局的搜索技术，高效而准确的找到光伏阵列的全局最大功率点，然后通过PWM占空比控制Boost电路来实现最大功率点跟踪。本算法可解决局部阴影下具有多峰输出特性的光伏阵列MPPT控制容易陷入局部最大功率点的难题，能准确找到全局最大功率点，并且寻优能力强，搜索精度高，易于编程实现。

摘要： 本发明公开了一种针对选择性装配使用的最差优先的局部随机搜索算法，首先从数据库中读取零部件尺寸信息，将尺寸信息存放在一个3维矩阵中，将部件之间的装配信息存入配合矩阵，然后建立装配矩阵，根据装配矩阵与配合矩阵建立模拟装配矩阵后，进入配合方案的搜索程序，生成一个随机的初始选择方案，之后根据初始的选择方案进行有限范围的搜索，得到匹配出的最优结果。本发明采用“最差优先”的匹配方向，并通过局部的随机搜索及多次迭代的方式，近似的得出最佳匹配方案，能够在不额外提高加工精度的前提下，提高装配的合格率，是一种降低生产成本的有效算法。

摘要： 一种基于阈值式局部迭代搜索算法的叶片排序方法，它涉及一种叶片排序方法。本发明为了解决现有局部迭代搜索算法平均迭代到局部最优的步数多，存在叶片排序搜索效率低的问题。本发明的步骤一：对叶片进行编号；步骤二：对步骤一二中的序列H进行初始化：步骤三：对步骤二中的序列H进行局部搜索：步骤四：更新全局最优解Hglobal；步骤五：判断集合Σ1的元素个数是否大于步长step：若是，则跳转到步骤六，否则跳转到步骤七；步骤六：阈值扰动：步骤七：将下降趋势集合Σperturbation中的所有元素依次用于步骤三的初始序列，并重复步骤三和步骤四；步骤八：随机扰动。本发明引入了阈值式扰动的概念，在合理的计算时间内通过对叶片进行排序。本发明用于叶片排序。

摘要： 本发明公开了一种基于阈值法和局部最大值的自动对焦爬山搜索算法,可提高对焦系统的稳定性和减少对焦时间；通过设定阈值Value，可以直接忽略由于噪声、亮度变化等因素导致的局部极值，提高对焦的成功率；判断评价函数处于“上坡”、“下坡”、“平地”区域的判断条件，随着上一幅图像评价函数值Sm的变化而变化，面对不同对比度的图像，能够自适应改变判断条件；通过引入局部评价函数最大值，减少对焦循环和对焦时间；通过设定电机的固定移动步长，并采用|S‑Sm1|Sm1作为对焦结束的条件，解决传统自动对焦爬山搜索算法中“即使步长缩小为零，镜头仍没有走到最佳对焦点”的问题，并提高对焦的精确性。

摘要： 本发明实施例公开了一种基于局部单调图模型的最邻近搜索算法，涉及机器学习算法技术领域。所述最邻近搜索算法的步骤包括：选取图作为搜索数据结构；依据K近邻估计算法将搜索数据结构中每个节点与其最近的K个邻点连接起来；依据K近邻估计算法构建单调搜索网络，并将所述单调搜索网络以二进制文件保存；将搜索数据结构中每个节点的邻点数量设为相同值；从中心节点出发沿着单调搜索网络的单调路径执行搜索任务。本发明能够解决现有最邻近搜索算法技术不适用于大规模数据集，构件搜索数据结构的时间长、精度低的问题。

摘要： 本发明公开一种基于局部搜索算法的室内无线设备部署方法及系统，涉及无线设备部署方法，可在考虑障碍物对信号的影响的前提下，针对指定的目标区域快速地产出设备部署方案，同时可灵活设置每个位置接收到的信号数量要求及其他的约束条件，不仅适用于小区域的求解，还适用于大规模区域的部署。

摘要： 本发明公开一种基于局部搜索算法的室内无线设备部署方法及系统，涉及无线设备部署方法，可在考虑障碍物对信号的影响的前提下，针对指定的目标区域快速地产出设备部署方案，同时可灵活设置每个位置接收到的信号数量要求及其他的约束条件，不仅适用于小区域的求解，还适用于大规模区域的部署。

摘要： 本发明提出了一种优化仓储堆垛机拣选策略的改进多目标局部搜索算法，该算法包括：堆垛机拣选参数初始化，生成堆垛机拣选序列的初始化种群，然后进行优化，获得较高质量的堆垛机拣选序列初始解，然后计算堆垛机拣选路径总距离和收集货物总利润值两个目标值，获得非支配解，存储精英池中，再继续优化精英池中解的质量，若满足终止条件，则结束，否则继续执行增强扰动策略或者一般扰动策略获取候选解，并对候选解进行埃普西隆约束的局部搜索策略，获得最优解更新精英池，跳回迭代搜索。本发明避免大量无效解的产生，综合提高算法的求解效率，较之传统的迭代局部搜索具有更好的性能和稳定性。

摘要： 本发明提出了一种基于局部搜索算法的机械臂自主避障路径生成方法，包括：步骤S1，初始化障碍物相关信息，根据初始化后的信息生成障碍物的边界框；步骤S2，将当前关节角度一个邻域内的关节点离散化；步骤S3，从当前角度出发，依据预测的关节角度变化律获得下一步的搜索路径点，判断从当前关节角度出发能否获得可行路径点，如果能够获得可行路径点，则从可行路径点中筛选最优路径点，进而判断是否到达终点；如果不能获得可行路径点则进行路径回溯，返回前一个路径点重新进入S2向前搜索；步骤S4，如果判断到达终点，则将所有最优路径点平滑连接起来，生成最终的平滑路径，如果判断没有到达终点，则前进一步返回步骤S2，搜索下一个路径点。

摘要： 本发明的一种基于局部搜索算法的医院排课方法，分别获取医院的排课时间数据T、教室数量J、课程数量C、导师数量D和学生数量X，匹配建立教室‑时间、课程‑导师、学生三个数据集合，对教室‑时间、课程‑导师、学生三个数据集合进行随机两两合并，并对合并产生的组合进行条件检测，当符合条件检测时记录该组合，统计所有符合条件检测的组合数量L，当L＝C*X时，停止计算，输出组合集，该组合集为最终结果。与现有技术相比，本发明为了使用各种复杂环境，内置了多种变量，供使用者自行调整。在局部计算中搜索最优值，最大程度确保排课结果的适用性。本算法通过降维、下探等措施，尽可能的减少了迭代次数，大大减少了耗时。