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

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

改进秃鹰搜索和K均值混合迭代的点云简化算法

针对激光雷达的固有特性和复杂环境易造成点云噪声和冗余点云,以及传统点云简化算法忽略了点云固有特征等问题,提出了一种基于改进秃鹰搜索和K均值聚类(KMC)混合迭代的点云简化算法(IBESSA)。首先,通过秃鹰搜索(BES)算法迭代阶段的竞争融合(CFBES),提高其收敛速度和优化精度;其次,通过CFBES和KMC算法的混合迭代,实现了点云数据的聚类;然后,在k近邻(k-NN)实现点云簇密度估计的基础上,结合香农熵实现点云信息量化;最后,删除信息量化值小于阈值的聚类簇,完成点云数据简化。使用UCI国际标准数据集和斯坦福点云数据集分别对CFBES-KMC算法的聚类效果及点云的简化效果进行验证,结果表明:与改进飞蛾扑火的K均值交叉迭代、K-means++、模糊C均值聚类算法的聚类效果相比,CFBES-KMC算法的聚类准确率分别提高了1.02%、12.31%、14.72%;在斯坦福点云数据集上,IBESSA算法在有效滤除冗余点云的基础上保留了原本点云的细节和形状特征,不失为一种高效的点云简化算法。

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

针对标准灰狼算法(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%,证实了在工程应用中的可行性和有效性。

求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法

在经典分布式流水车间调度问题基础上,本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP),以均衡各工厂能耗成本为优化目标,提出了基于群体优化的迭代贪婪算法(PEIG).该算法针对零缓冲区和多工厂生产模式,设计了问题特性的启发式方法;针对迭代贪婪算法(IGA)的优势和不足,提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法,以进一步平衡所提算法的全局探索和局部搜索能力.通过270个测试算例的数值仿真,以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性,能为中大规模的DBFSP SDST提供更优的调度方案.

改进迭代局部搜索算法求解第Ⅰ类混流双边装配线平衡问题

基于第Ⅰ类混流双边装配线平衡具有生产品种多样性和生产过程复杂性的特点,研制了一种改进迭代局部搜索算法进行求解。在工位数量相同时引入新的二级目标,使前面工位承担更多负载,推进解的细微改进;提出基于工位的启发式解码方式,使成对工位内的负载更为均衡。在解码设计中,优先选择空闲时间较多的边作为分配操作的边,对每种产品优先选择不产生空闲时间的操作分配,然后通过最后成对工位调整策略进一步减少工位的数量。同时设计了新的改进启发式初始化和局部搜索方式,并通过参数校验验证改进的合理性。将所提解码方式与3种不同的解码方式进行对比,并将所提算法与7种不同算法进行对比,结果表明,基于工位的启发式解码优于对比解码,所提迭代局部搜索算法优于其他对比算法。

基于K均值的迭代局部搜索聚类算法

K均值聚类算法(KM)是解决聚类问题的一个常用的方法,该方法的主要缺点是其找到的局部极小值与全局最优值的偏差往往较大。论文构造一种基于KM算法的迭代局部搜索算法(称之为IKM)。该算法以KM算法所得到的解作为初始解,从该初始解开始作局部搜索,在搜索过程中接受部分劣解。当解无法改进时,算法对所得到的局部极小解做适当强度的扰动后进行下一次的迭代,以跳出局部极小,从而拓展了搜索的范围。试验结果表明IKM算法得到的聚类结果比KM算法得到的聚类结果有明显的改进,平均改进达100%以上。当数据集越大,簇的个数越多时,改进的效果越是显著,可以达到300%以上。因而,IKM算法是一个确实可行的有效的方法。

一种基于迭代局部搜索的和声搜索算法

为了改进原始和声搜索算法的全局搜索性能,提出了基于迭代局部搜索的和声搜索算法。该算法在充分利用和声记忆库中信息和提高搜索效率的同时,对于不满足停止准则的新和声采用基于改进kick策略移动的迭代局部搜索算法进行寻优,从而使新算法具有较强的"爬山"能力。针对4个benchmark函数对新算法做了测试,并与粒子群优化算法以及已有的几个算法进行了比较,结果表明该算法跳出局部极值点的能力较强、收敛速度更快、寻优精度较高;最后将新算法应用到焊接梁的优化设计问题中,仿真结果验证了该算法在求解焊接梁最小造价问题时优于原始的和声搜索算法、遗传算法等方法。

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋予一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。

改进迭代局部搜索算法求解多AGV柔性作业车间调度问题

针对受运输时间和运输资源约束的柔性作业车间调度问题,提出一种融合贪心启发式规则的改进迭代局部搜索算法。以最大完工时间为优化目标,建立多自动导引小车(AGV)柔性作业车间调度问题的数学模型,并采用工序串和机器串双层编码求解问题模型,解码时融入“先到先服务”的启发式规则来对每个运输任务分配最合适的AGV;生成初始解时考虑机器全局的工作负载平衡;设计了3种邻域结构用于随机邻域局部搜索,并采用精英解记忆库策略来指定当前解,有效利用历史搜索信息,保持算法集中性的同时扩大了搜索空间。采用最好解、相对标准差和算法平均运行时间3种性能指标,分别在小规模和大规模标准测试案例上对所提算法的有效性、稳定性和高效性进行测试,结果表明不管是在求解速度上还是求解质量上其表现都优于遗传禁忌搜索算法、带转移瓶颈的遗传禁忌搜索算法和延迟接受爬山算法。

基于多类迭代局部搜索的自动化排课算法

针对局部搜索算法容易陷入局部最优,无法自适应多种约束条件下排课的问题,提出一种基于多类迭代局部搜索的自动化排课算法。首先,通过多类分类器依据排课问题特征对排课问题进行分类,指导迭代局部搜索的邻域选择及参数设置。然后,在迭代局部搜索的过程中,使用基于序列的贪婪算法获得可行解。最后,采用以问题特性为导向的双温控制模拟退火算法在邻域中搜索局部最优解,并通过特定的扰动策略对当前最优解进行扰动后作为新的初始解进行迭代,最终达到全局最优。该算法在两个国际著名的数据集,即第二届国际时间表大赛基于课程的时间表数据集和Lewis 60数据集上进行了测试。实验结果表明,与当前文献中求解该问题的其他性能较优算法相比,所提出的算法具有更高的求解效率和质量。

基于迭代局部搜索和自适应粒子群优化的SVM短期负荷预测

为了能够进一步的提高船舶电力负荷的预测精度,针对SVM模型在负荷预测中存在的参数选取问题,该研究提出了一种新的参数优化算法:基于迭代局部搜索和自适应粒子群优化的组合算法。自适应粒子群算法提高了传统粒子群算法的收敛速度,引入的迭代局部搜索思想,配合新的极值评价标准能够很好的解决粒子群算法容易陷入局部最优的问题。仿真结果表明,利用新的参数优化算法使得SVM预测模型的精度得到了很大的提高。

车辆路径问题的快速多邻域迭代局部搜索算法

对于容量约束的车辆路径问题（ capacitated vehicle routing problem, CVRP）以及容量和最大行驶距离约束的车辆问题（ capacitated and distance constrained vehicle routing problem, CDVRP）,邻域解的评估包含了适应值计算及合法性评估.设计一种可变长编码的可行解表示,提出用于CVRP/CDVRP问题的邻域解合法性快速评估策略.该策略针对交换、插入、2-opt和2-opt？四种常用的局部搜索算子,通过引入前载重、后载重、前向距离和后向距离的概念,实现了邻域解合法性的快速评估.将改进后的局部搜索算子与迭代局部搜索（ iterated local search, ILS）算法相结合,提出用于车辆路径问题的快速多邻域迭代局部搜索（ fast multi-neighborhood ILS, FMNILS）算法.该快速评估策略将评估一个邻域解的时间复杂度由O（ N）降至O（1）,算法仿真结果表明, FMNILS算法运算能力的提高大致与配送路线所服务的客户数成正比；对客户数介于200~500的容量/最大距离约束VRP问题,该算法能在短时间内获得较满意解,平均求解精度1．2%以内,平均耗时约96 s,仅为对比算法的6%或更少.

迭代局部搜索求解双边混流装配线平衡问题

为有效解决双边混流装配线的平衡问题,建立了联合优先关系图,利用加权时间法简化问题,并提出一种简单高效的迭代局部搜索算法。该算法通过启发式初始化保证初始解的质量,将优先关系约束融入到局部搜索,避免了重复的插入操作,最后摄动方法对当前解多次重复插入算子并产生新解,并用产生的新解代替当前解。同时,结合装配线的特点,提出一种基于优先级的编码和解码方法,该方法通过工位选择策略保证工位负载均衡,通过操作选择策略减少工位的空闲时间。该算法与5种启发式算法进行对比,实验结果表明所提出的算法不仅能有效平衡双边混流装配线,并且参数较少便于实现。

基于余弦控制因子和迭代局部搜索的蝙蝠优化算法

针对蝙蝠算法寻优精度低、易陷入局部极值、求解不稳定的问题,提出了一种基于余弦控制因子和迭代局部搜索策略的蝙蝠的算法。首先在蝙蝠速度公式中加入由余弦因子控制的非线性惯性权重,来动态调节算法全局搜索与局部搜索的平衡,提高算法寻优精度和稳定性。其次,在每轮迭代结束时引入迭代局部搜索策略,扰动局部最优解获得中间状态,并重新搜索上述中间状态得到全局最优解,使算法快速跳出局部最优解,找到全局理论最优。最后与其他算法在12个复杂基准函数上进行仿真实验。结果表明,改进后的算法较好地解决了蝙蝠算法寻优精度不高、易陷入局部极值和求解不稳定的问题。

基于逐步迭代和中垂线点搜索的三维射线追踪算法

在对压裂诱发微地震或天然微地震监测领域中,以地震射线追踪为主的正演环节直接影响震源定位质量以及计算效率。针对微地震监测特点,基于逐步迭代和中垂线点搜索法提出了一种新的三维追踪算法。该方法具有独特的灵活性与高效性。

航班恢复问题的迭代局部搜索算法

在恶劣天气和机械故障等原因造成航班不能按照原计划执行时,航空公司需要采取相应的措施对航班进行恢复。本文基于经典的资源指派模型,综合考虑了调整时间、换机、联程拉直、取消航班和调机5种恢复策略,提出一种以最小化加权成本为优化目标的航班恢复模型,并设计一种迭代局部搜索算法。首先用构造-修复启发式方法构造可行解,然后从该初始解出发,在飞机路线对的邻域中进行局部搜索。当陷入局部最优后,对解进行扰动,然后从扰动后的解重新出发进行局部搜索。为了提高搜索效率,同时降低陷入局部最优解的概率,局部搜索过程采用模拟退火算法。实例结果表明,本文提出的模型及算法能够在短时间内对受到影响的大规模航班计划进行恢复。

改进迭代局部搜索算法在MMTVRP中的应用

为了解决运送不相容货物的带时间窗的多行程车辆路径问题,需要制定一个明确的路径规划来服务一组客户,以满足客户运送不相容的大宗货物的需求。车辆在工作日期间允许执行多个行程,目的就是最大限度地减少使用车辆的数量。通过创建巨网结构并采用辅助分割过程和改进的迭代局部搜索算法获得解决方案,在多个相关约束条件限制下,车辆实现了以最少的数量、最短的行程在规定的时间窗内送达货物,并从车队不同规模的角度分别介绍了采用多行程方式送货的优势。最后通过典型的带时间窗的车辆路径问题的实例分析表明,该算法在某些情况下可以使车队规模减半,从而最大程度上减少了运行成本。

神经外科导航系统基于迭代局部最近点法技术的形态学三维数据场的快速配准与融合

目的:拟开发一种全自动快速配准技术,用于临床形态学三维数据场的配准与融合。方法:用本研究提出的基于迭代局部最近点法(ILCP)技术的形态学三维数据场的快速配准技术,用临床实际病例的CT、MRI图像进行配准实验。结果:实验得到了满意的全自动快速配准效果,结果显示ILCP法比普通ICP法快10-30倍,比最大互信息法快8-10倍;耗时可以为临床医生所接受。结论:所提出的方法是切实可行的,为进一步应用于临床打下了坚实的基础。

求解RCPSP问题的迭代局部搜索算法研究

迭代局部搜索(Iterated Local Search)算法是一个简单、高效的元启发式算法。提出一种新的求解资源受限项目调度问题(RCPSP)的迭代局部搜索算法。通过对当前解进行迭代交换实现局部搜索过程,再通过扰动多个任务的方式进行有效的扰动,防止陷入局部最优。迭代过程中通过优先对关键链的任务进行局部搜索进一步缩小解空间,通过双对齐技术提高解的质量。最终通过标准问题库求出各项参数并且验证算法的性能。

基于迭代局部搜索的路径规划蚁群算法

针对蚁群算法易早熟及局部搜索能力欠佳的缺陷,将迭代局部搜索策略引入蚁群算法。新算法的基本思想是:从初始解出发,用蚁群算法进行局部搜索,如陷入局部最优,则产生一个摄动解作为新的初始解再进行局部搜索,根据接受规则决定进入下一步迭代的局部最优解。将改进算法应用于二维路径规划,数值实验表明,改进算法相比基本蚁群算法有更佳的局部收敛性,可获得比基本蚁群算法结果更优路径。