基于捕食搜索策略的模拟退火优化算法

针对传统模拟退火算法初始温度和降温函数难以确定以及接收劣质解同时容易遗失当前最优解等缺陷,将禁忌搜索算法的禁忌表功能引入SA算法,避免遗失最优解和对某个解进行多次重复地搜索;根据函数的复杂程度确定初始温度,并定义新的降温函数,提高算法的搜索效率和精度;引入捕食搜索策略,平衡算法搜索能力和开发能力,避免陷入局部最优。通过对5个典型的基准测试函数的仿真表明,改进算法具有较强的全局搜索能力,同时寻优精度和收敛速度比原算法也有较大的提高。     

模糊Job Shop调度中的混合搜索策略的研究

采用并行遗传算法作为全局搜索算法，提出一种混合搜索策略，用于求解模糊Job Shop调度问题．根据模糊Job Shop调度问题解的特征，提出基于关键工序的邻域选择方法，并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法，加强了遗传算法局部搜索能力．针对13个困难benchmark问题的实验结果表明，在较短的时间内，混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%，比TSAB算法提高5.76%．采用的禁忌搜索算法改善了遗传算法的局部搜索能力，说明提出的混合搜索策略是有效的．     

融合粒子群和局部邻域搜索的优化算法

为解决采用单一搜索策略的算法很难兼顾全局搜索和局部搜索,且易陷入局部优化的问题,提出一种融合粒子群优化和局部邻域搜索思想的新算法(Ne-PSO).采用混合搜索策略,通过对全局最优粒子信息的交互和反馈,并行进行全局搜索和局部搜素.同时,新算法引入禁忌策略,通过设置禁忌邻域来限制粒子的搜索区域,有效规避了局部优化.通过4个经典函数的测试,验证了该算法在寻优速度、精度和成功率方面的优异性能.     

基于Powell局部搜索策略的全局优化布谷鸟算法

为了解决布谷鸟搜索算法后期收敛速度慢、求解精度不高、易陷入局部最优等缺陷,提出了一种基于Powell局部搜索策略的全局优化布谷鸟搜索算法.算法将布谷鸟全局搜索能力与Powell方法的局部寻优性能有机地结合,并根据适应度值逐步构建精英种群候选解池在迭代后期牵引Powell搜索的局部优化,在保证求解速度、尽可能找到全局极值点的同时提高算法的求解精度.对52个典型测试函数实验结果表明,该算法相比于传统的布谷鸟搜索算法不仅寻优精度和寻优率有所提高,并且适应能力强、鲁棒性好,与最新提出的其他改进算法相比也具有一定的竞争优势.     

解决图着色问题的一种新禁忌搜索算法

为了解决典型的组合优化问题——图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS)。该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解。计算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性。     

一种求解动态优化问题的免疫文化基因算法

针对传统免疫网络动态优化算法局部寻优能力弱、寻优精度低及易早熟收敛的缺点,提出一种求解动态优化问题的免疫文化基因算法。基于文化基因算法基本框架,将人工免疫网络算法作为全局搜索算法,采用禁忌搜索算法作为局部搜索算子;同时引入柯西变异加强算法的全局搜索能力,并有效防止早熟收敛。通过对经典动态优化函数测试集在相同条件下的实验表明,该免疫文化基因算法相较于其他同类算法具有较好的搜索精度和收敛速度。     

MAX-SAT问题一种改进的局部搜索算法

局部搜索算法是求解大规模SAT问题的高效算法。经典的局部搜索算法有GSAT、WSAT、TSAT、NSAT等,但这些算法的初始解都是随机产生的。本文提出了用单纯形法产生“初始概率”（每个变量取1的概率）,用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束,使在局部搜索的开始阶段,满足的子句数大大增加,加快了收敛的速度。通过对不同规模的随机STA问题实例的实验表明,这些改进有效地提高了局部搜索算法求解SAT问题的效率。     

改进多样性和局部优化能力的引力搜索算法

针对引力搜索算法局部搜索能力较弱,搜索过程容易出现早熟的现象,提出一种基于多样性和局部优化能力协同优化的引力搜索算法。将粒子群算法中局部最优解和细菌趋化中排斥操作的概念引入到引力搜索算法中,通过帮助粒子接近最优位置和逃离最差位置,改进了搜索算法中粒子的局部优化能力及种群多样性,并使用标准函数进行测试。结果表明,该算法能够实现全局搜索与局部搜索的平衡,最大程度地保持种群多样性,提高算法搜索能力。     

基于离散粒子群和禁忌搜索的网格资源调度算法

提出一种基于智能的网格资源分配和任务调度算法,由于网格资源调度是个离散问题,所以采用基于惯性权重的离散粒子群算法,针对离散粒子群算法在后期容易陷入局部最优的缺陷,将其与禁忌搜索算法相结合,在算法的前期采用离散粒子群算法进行搜索,在后期采用禁忌搜索算法进行局部搜索。并利用网格模拟工具Gridsim Toolkit开发一个网格模拟系统进行实验。实验结果表明,该算法具有较高的寻优能力。     

基于禁忌搜索的人工蜂群算法及其应用

人工蜂群算法(artificial bee colony algorithm,ABC)是一种简单有效的群智能算法,通过蜜蜂之间的相互合作寻找最优解.禁忌搜索算法(tabu search algorithm,TS)是人工智能与局部邻域搜索算法的结合,具有非常好的全局寻优能力.为了提高ABC的搜索效率和全局寻优能力,结合TS,在ABC中增加一个禁忌表,提出了一种基于禁忌搜索的人工蜂群算法(artificial bee colony algorithm based on tabu search,TSABC).通过对10个常用的标准测试函数进行实验,对TSABC算法进行了验证,并将其应用于图像边缘检测中.实验结果表明,TSABC取得了较好的优化效果,提高了寻优精度和收敛速度,边缘检测结果也更理想.     

改进的Tabu Machine网络求解最大割问题

为了提高Tabu Machine网络处理最大割问题时解的质量,改进原有算法的禁忌搜索策略,并且通过结合局部搜索策略和分布估计策略,形成一种新的网络HNNTS-EDA.此网络有较强的局部搜索能力和脱离局部最优值的能力.将HNNTS-EDA网络与多种经典算法在相同测试数据上进行对比测试,实验结果表明HNNTS-EDA网络具...     

Some local search algorithms for no-wait flow-shop problem with makespan criterion

This paper develops and compares different local search algorithms for the no-wait flow-shop problem with makespan criterion (C_max). We present several variants of descending search and tabu search algorithms. In the algorithms the multimoves are used that consist in performing several moves simultaneously in a single iteration of algorithm and allow us to accelerate the convergence to good solutions. Besides, in the tabu search algorithms a dynamic tabu list is proposed that assists additionally to avoid trapped at a local optimum. The proposed algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than existing algorithms. The presented ideas can be applied in any local search procedures.     

Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times

We tackle the job shop scheduling problem with sequence dependent setup times and maximum lateness minimization by means of a tabu search algorithm. We start by defining a disjunctive model for this problem, which allows us to study some properties of the problem. Using these properties we define a new local search neighborhood structure, which is then incorporated into the proposed tabu search algorithm. To assess the performance of this algorithm, we present the results of an extensive experimental study, including an analysis of the tabu search algorithm under different running conditions and a comparison with the state-of-the-art algorithms. The experiments are performed across two sets of conventional benchmarks with 960 and 17 instances respectively. The results demonstrate that the proposed tabu search algorithm is superior to the state-of-the-art methods both in quality and stability. In particular, our algorithm establishes new best solutions for 817 of the 960 instances of the first set and reaches the best known solutions in 16 of the 17 instances of the second set.     

带扰动和变异因子的改进禁忌搜索算法求解贴片机贴装过程优化

以多贴装头拱架式贴片机为研究对象,利用带扰动和变异因子的改进禁忌搜索算法,实现贴片机贴装过程优化.算法在传统禁忌搜索算法的基础上,利用以长期记忆为基础的多元化扰动策略和块变异算子来扩大贴片机贴装顺序优化搜索空间,并结合局部下降搜索策略优化喂料器分配,最终实现贴片机贴装整体优化.仿真实验表明,改进算法能快速有效地获得较好的贴片机贴装优化解.与其他文献中的算法相比,所提出的算法在求解质量和求解速度上有较大的优越性.     

求解作业车间调度问题的禁忌分布估计算法

为优化作业车间调度问题的解,提出一个禁忌和分布估计的混合算法。分布估计算法是一种新的进化模式,通过概率优化模型在连续空间进行求解;通过对已获得的群体进行选择操作生成优势群体,提出的分布估计算法使用单变量边缘分布算法构建概率模型,估计离散空间中的联合概率分布,从概率向量采样生成新群体;采用基于工件编号的编码和解码机制保证解的可行性。为提高局部搜索能力,算法基于禁忌搜索算法设计新的双重移动组合、块禁忌和选择策略,在搜索陷入局部最优时利用遗传算法的变异算子生成新解;算法通过混合分布估计算法和禁忌搜索算法的优点,兼具全局搜索与局部搜索能力,提高了搜索的效率和性能。通过与现有算法在典型实例上的实验结果比较,表明该算法在求解作业车间调度问题上具有可行性和有效性。     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。     

求解柔性作业车间调度问题的新型改进Jaya算法

为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。     

动态搜索和协同进化的鲸鱼优化算法

针对基本鲸鱼优化算法寻优精度低、收敛速度慢及容易陷入局部最优等缺陷,提出了一种动态搜索和协同进化的鲸鱼优化算法。首先,通过等价替换和Faure序列提高初始解的质量;其次,通过对种群进行分工,提高种群多样性并增强算法跳出局部最优解的能力;最后,根据种群进化信息动态调整搜索策略,从而提高算法的收敛速度和寻优精度。仿真实验结果表明,提出的改进算法相比基本鲸鱼优化算法和部分改进算法具有较好的寻优性能。     

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

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