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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

对于容量约束的车辆路径问题（ 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%或更少.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于迭代局部搜索的区划问题算法研究

区划问题是将特定地理区域划分为若干空间连续的分区,满足分区内差异最小和分区间差异最大这一基本原则,广泛应用于地理、环境、生态、经济、农业、城市等领域。1960s以来,学者尝试建立各种区划问题数学模型,设计了一系列的求解算法,代表性的算法主要有:AZP、ARISEL、SKATER和REDCAP。本文提出了一个基于迭代局部搜索(ILS)的区划问题算法,进一步提升算法性能。该算法主要机制包括:邻域单元移动搜索改进分区质量;参照中心单元快速计算分区方差,提升算法速度;使用扰动机制跳出当前解局部最优状态;更新分区中心点提升分区方案目标值;使用群搜索探索更大的解空间;以及算法各步骤中通过分区空间连续判断和破碎修复保持分区空间连续。55个基准案例测试表明:ILS算法求解质量优于ARISEL和SKATER算法。一个多指标气候分区实验也表明:ILS算法求解质量优于SKATER、REDCAP和ARISEL算法。

WSN中基于迭代局部搜索的Mobile Agent路径规划方法

无线传感器网络中,相对于传统上广泛使用的C/S计算范式,基于Mobile Agent的计算范式展示出强有力的生存优势.因此,Mobile Agent作为一种分布式中间件技术,已经成为无线传感器网络中高效地自主性数据融合和能量均衡研究领域的热点.由于Mobile Agent的访问路径很大程度上影响数据融合的性能和系统能量开销,所以,确定一个有效的Mobile Agent访问路径是一件颇有意义的研究.本文提出一种新的路径规划方法,采用迭代局部搜索的算法获取Mobile Agent对节点区域的访问路径;同时考虑了Mobile Agent迁移时数据负载,中间节点转发数据时实际的能量开销以及对相邻路径节点的利用.通过仿真实验分析表明本文提出的方法在能量消耗、服务时间方面优于现有的一些多路径规划方法.

基于多目标迭代局部优化算法的成本—路径平衡多目标电动车路径问题

电动车凭借低碳、环保的优势越来越多地被企业接受用于物流场景,但续航里程和充电限制仍制约着电动车的应用。以往文献极少在电动车背景下同时考虑运行成本和路径平衡。因此,将总运营成本和路径平衡两个目标纳入问题,构建了数学模型,结合迭代局部搜索算法和变领域搜索算法的特性,采用五种领域算子,设计了多目标优化算法求解问题。研究构造了九组算例,对比了提出的算法与VNS算法、ILS算法的表现。数据实验验证了算法的可行性、有效性和稳定性。