禁忌搜索算法解决零空闲流水线调度问题

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值.     

车辆路径问题的禁忌搜索算法研究

简要回顾了车辆路径问题的禁忌搜索算法的发展现状,提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间,提高了最优解的效果;是一种将问题进行空间分解的并行算法,可采用多台计算机同时运算以减少整体运行时间。     

改进的粒子群算法在VRP中的应用

将粒子群算法和禁忌搜索算法相结合构造禁忌搜索粒子群算法.提出一种对粒子群算法中全局最优解进行禁忌搜索的混合算法,扩展了粒子群算法进化方式.将其用于车辆路径优化问题求解.与基本粒子群算法相比较,结合禁忌搜索算法的粒子群算法明显提高了算法收敛速度和优化性能.     

求解Job-Shop调度问题的禁忌搜索算法的研究

本文针对最小完工时间的Job-Shop调度问题提出了一种禁忌搜索算法，该算法使用插入算法构造尽可能好的初始解，然后用禁忌搜索算法改进当前解，在算法中对未被选中的候选解信息进行记忆，合理平衡了集中搜索与分散搜索。最后用基准实例进行仿真，实验结果表明该算法是可行的和有效的。     

一种改进的禁忌-粒子群算法及应用

针对粒子群优化算法(PSO)的局部搜索能力差和存在早熟收敛的问题,将禁忌搜索(TS)思想融入到粒子群算法中,提出一种新的禁忌搜索的粒子群优化算法.新算法结合了PSO和TS各自的优点,在寻优前期利用粒子群算法得到较好的初始值,同时将个体极值pbest放人禁忌表,在寻优后期,当粒子的搜索能力减弱时,利用禁忌搜索算法中禁忌表的短期记忆功能,使其跳出局部最优解,并且在搜索过程中允许接受劣解.将改进的算法应用于函数的优化,仿真结果表明,改进算法具有计算精度高、稳定性强的特点,是一种非常有效的计算智能方法.     

求解可重入并行机调度的混合禁忌搜索算法

为解决带有一台远程服务设备的可重入并行机调度问题,设计了一种混合禁忌搜索算法。针对传统禁忌搜索算法只从单起始点搜索、容易陷入局部最优等缺点,混合禁忌搜索算法设计了一种Restart策略。当传统禁忌搜索算法陷入局部最优时,用Restart策略重新产生初始解以进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。数值实验中将混合禁忌搜索算法与启发式算法CS相比,结果表明该算法具有较高的求解质量,且其计算时间是可接受的。     

有车辆数限制的开放式车辆调度问题研究

有车辆数限制的开放式车辆调度问题(m-OVRP)是车辆调度类问题(VRP)的一个新的分支.本文通过多初始解选优、平滑动态的禁忌长度等改进手段,基于遗传算法中变异的思想,设计了改进的禁忌搜索算法来解决m-OVRP问题.实验结果表明,本文提出的算法不仅能很好地解决m-OVRP问题,对OVRP问题也能得到稳定的结果.本算法核心包括:提出一种全新的构造初始解的贪心算法,在禁忌搜索初始解的选取中采用多初始解选优的策略;提出在禁忌搜索中采用平滑动态的禁忌长度.本算法可以很方便地应用到其他的一些启发式搜索问题的求解中.     

MAX-SAT问题的一种改进的禁忌搜索算法

求解SAT问题的经典禁忌搜索算法TSSAT初始解是随机产生的,本文在传统的禁忌搜索算法的基础上提出了一种改进初始解的方法.通过对不同规模的随机SAT问题实例的测试表明,这种改进可以有效地提高禁忌搜索过程中求解SAT问题的效率.     

混合流水车间调度的变邻域禁忌搜索算法

针对混合流水车间系统的最小化Makespan调度问题,提出一种基于关键路径理论的变邻域禁忌搜索算法,讨论其关键技术。在该算法中,提出基于关键路径的毗邻域概念,防止搜索算法陷入局部最优解,采用变邻域搜索策略,在无法改进解时,实现对移动毗邻域的搜索。仿真结果表明,该算法获得的调度结果优于简化禁忌搜索和启发式算法。     

IT外包进度风险控制的自适应禁忌搜索算法

针对委托代理模式下的IT外包项目的进度风险控制问题构建了双层结构的优化模型.设计了自适应禁忌搜索算法对模型进行求解，该算法将多样化搜索机制与禁忌搜索相结合，在算法运行过程中，根据适应值的反馈自动调整禁忌搜索强度与多样化搜索力度；同时，应用贪婪策略构造初始解，循环交替应用两种邻域结构提高算法寻优能力.实验结果表明，进度风险控制显著地降低了IT外包项目的拖期风险，同时使委托方和代理商双方实现收益最大化.将自适应禁忌搜索算法的实验结果分别与遗传算法、模拟退火算法、禁忌搜索算法、自适应遗传算法和自适应模拟退火算法的实验结果进行了比较：在收敛程度和稳定性方面自适应禁忌搜索算法优于其它算法，并且随着问题规模的增加，该算法的优势更为明显.     

一种基于IP网络的QoS约束组播路由算法

针对时延约束最小代价组播路由问题,结合禁忌搜索算法和模拟退火算法的优点,提出了一种改进的混合遗传路由算法TSSAGMA。通过分析与仿真,证实了该算法在解决时延约束最小代价组播路由的问题上优于传统算法,能够在较小的代价下搜索到较好的解。     

约束满足混合算法求解提前/拖期Job Shop调度问题

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。     

铁路行包基地及配送点选址问题禁忌搜索算法

分析了铁路行包运输物流化发展背景及行包运输物流配送的特点,给出了铁路行包基地及配送点选址的数学模型,应用改进的扫描法构造问题尽可能好的初始解,并通过巧妙地设计罚函数、合理构造邻域及随机选取禁忌长度的一种禁忌搜索算法对初始解优化．计算结果表明,扫描法和禁忌搜索算法结合的两阶段法,不仅可以得到良好的计算结果,而且具有搜索空间小、求解速度快的优点,该方法是有效、可行的．     

改进禁忌搜索算法的贴片机贴装过程优化

以多贴装头拱架式贴片机为研究对象,利用带块变异算子的改进禁忌算法实现实贴片机贴装过程的优化。在基本禁忌算法的基础上,利用块变异因子扩大元器件贴装顺序优化的搜索空间,并在禁忌搜索过程中利用局部迭代搜索实现喂料器的分配优化。为验证算法有效性,以10块实际生产的PCB为实例进行了测试。实验证明,提出的算法能获得更好的贴片机贴装优化解。     

片上网络映射问题的改进禁忌搜索算法

为求解通信时延受约束的低能耗片上网络(NoC)映射问题,提出一种改进禁忌搜索算法.该算法由局部搜索和精英重组2个步骤经过多次迭代完成,局部搜索采用简化的robust tabu search (RoTS),精英重组步骤选用COHX交叉操作.实验结果表明:文中算法与RoTS相比具有优化性能好、搜索空间小的优点,映射结果比分支限界法平均节能16.1%,适于求解大规模NoC映射问题.     

考虑面积成本的双目标环形过道布置建模及改进禁忌搜索优化

针对现代建筑结构的形式多样化和面积成本在总成本中的占比越来越大等问题，建立了考虑面积成本的双目标环形过道布置问题的数学模型，并对考虑面积成本下的双目标环形过道布置问题的总成本进行优化.结合问题和模型特点，提出了一种加入动态禁忌长度和变异操作的改进禁忌搜索算法.所提算法随着迭代次数的增加，动态禁忌长度不断变化，从而缩小了搜索空间，提高了解的集中性，并融合了变异操作使其跳出局部最优，扩大了算法搜索范围.通过对不同规模实例的测试验证了算法的可行性.通过将所提算法与基本禁忌搜索算法进行对比，结果表明了改进算法的有效性和优越性.     

基于协同自适应禁忌的多时窗VRP算法实现

针对多时窗VRP,提出了一种对其进行求解的协同禁忌优化算法。首先定义了多时窗VRP的数学模型,通过C-W算法求初始解,采用四种算子进行邻域搜索,定义目标函数衡量候选解好坏;设计了自适应地修改禁忌长度的方法和多个子禁忌算法进行协同寻优的算法;将协同寻优获得的最好最优解作为主禁忌算法初始解进行全局寻优。仿真实验证明,该方法能有效地解决多时间窗的VRP,且与其他方法相比,以较少的迭代次数获得了全局最优解为386.38,具有较大的优越性。     

一种求解车间作业调度的自适应混合遗传算法

针对遗传算法和禁忌搜索算法在求解车间作业调度问题存在的全局收敛性差、种群早熟化、收敛速度慢等缺陷,提出了一种自适应遗传禁忌搜索算法。算法通过自适应调整遗传算子中的变异概率,改善了遗传算法的收敛速度;通过增加禁忌表来选择杂交产生的个体,避免迂回搜索,以禁忌搜索算法作为变异算子,增加种群的多样性,避免算法陷入局部最优。通过仿真实例,验证了算法的收敛性和抗局部收敛性。     

求解最大割问题的多启动禁忌搜索算法

为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索（MSTS）算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。