禁忌搜索算法教程

图节点着色问题中的禁忌搜索算法09-03-25 作者：编辑：校方人员图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题。

目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。

综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。

本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性。

禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有效的应用于一些典型NP问题，如TSP。

但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。

本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。

最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。

1图节点着色问题图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集，其中(i,j)表示有连接(i,j)的一条边。

若，且V i内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…,V n)为V的一个划分。

图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,V n)为V的一个划分。

通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。

Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。

一、实验背景禁忌搜索算法（Tabu Search，TS）是一种基于局部搜索的优化算法，最早由Glover和Holland于1989年提出。

该算法通过引入禁忌机制，避免陷入局部最优解，从而提高全局搜索能力。

近年来，禁忌搜索算法在蛋白质结构预测、调度问题、神经网络训练等领域得到了广泛应用。

本次实验旨在验证禁忌搜索算法在求解组合优化问题中的性能，通过改进禁忌搜索算法，提高求解效率，并与其他优化算法进行对比。

二、实验目的1. 研究禁忌搜索算法的基本原理及其在组合优化问题中的应用；2. 改进禁忌搜索算法，提高求解效率；3. 将改进后的禁忌搜索算法与其他优化算法进行对比，验证其性能。

三、实验方法1. 算法实现本次实验采用Python编程语言实现禁忌搜索算法。

首先，初始化禁忌表，存储当前最优解；然后，生成新的候选解，判断是否满足禁忌条件；若满足，则更新禁忌表；否则，保留当前解；最后，重复上述步骤，直到满足终止条件。

2. 实验数据本次实验采用TSP（旅行商问题）和VRP（车辆路径问题）两个组合优化问题作为实验数据。

TSP问题要求在给定的城市集合中找到一条最短的路径，使得每个城市恰好访问一次，并返回起点。

VRP问题要求在满足一定条件下，设计合理的配送路径，以最小化配送成本。

3. 对比算法本次实验将改进后的禁忌搜索算法与遗传算法、蚁群算法进行对比。

四、实验结果与分析1. TSP问题实验结果（1）改进禁忌搜索算法（ITS）实验结果表明，改进后的禁忌搜索算法在TSP问题上取得了较好的效果。

在实验中，设置禁忌长度为20，迭代次数为1000。

改进禁忌搜索算法的求解结果如下：- 最短路径长度：335- 迭代次数：1000- 算法运行时间：0.0015秒（2）遗传算法（GA）实验结果表明，遗传算法在TSP问题上的求解效果一般。

在实验中，设置种群规模为100，交叉概率为0.8，变异概率为0.1。

遗传算法的求解结果如下：- 最短路径长度：345- 迭代次数：1000- 算法运行时间：0.003秒（3）蚁群算法（ACO）实验结果表明，蚁群算法在TSP问题上的求解效果较好。

禁忌搜索算法原理及应用随着计算机技术的不断发展，各种算法也应运而生，其中禁忌搜索算法便是一种比较常用的优化算法。

禁忌搜索算法的一大特点就是能够避免搜索过程中出现循环现象，能够有效地提高搜索效率，因此在许多领域都有广泛的应用。

一、禁忌搜索算法的原理禁忌搜索算法是一种基于局部搜索的优化算法。

其基本思想就是在搜索过程中引入禁忌表，通过记录禁忌元素，避免进入不良搜索状态，从而获得更好的解。

禁忌表的作用是记录已经经过的解的信息，防止搜索陷入局部最优解，增加了搜索的广度和深度。

禁忌搜索算法的核心是寻找最优化解。

具体过程包括：初始化，构造邻域解，选择最优解，更新禁忌表，结束搜索。

当搜索过程中发现某个解是当前状态下的最优解时，将这个最优解加入到禁忌表中，以后在搜索过程中就不再去重复对该最优解的操作。

在禁忌搜索算法中，选择邻域解是非常重要的一环。

邻域解是指与当前解相邻的解，也就是在当前解的基础上进行一定的操作得到的解。

邻域解的选择通常根据问题的不同而定，可以是交换位置、插入、反转等。

而选择最优解的原则则是要在禁忌状态下优先选择不在禁忌表中的最优解，如果所有的最优解都处于禁忌状态，那么就选择设定的禁忌期最短的解。

二、禁忌搜索算法在实际应用中的应用禁忌搜索算法作为一种优化算法，在实际应用中有着广泛的应用。

下面我们就通过几个实际案例来了解禁忌搜索算法的应用。

1. 生产排程问题禁忌搜索算法在制造业的排程问题中有着广泛的应用。

在生产排程问题中，需要考虑的因素非常多，如时间、人员、设备、物料等。

禁忌搜索算法通过构建邻域空间，利用禁忌表避免了进入不良解的状态，从而在生产排程问题中，可以为厂家避免很多因时间不足而导致的决策错误。

2. 组合最优化问题禁忌搜索算法在组合最优化问题中有着很好的应用。

比如在公路路径设计中，需要从成千上万的路径中选择最优解。

禁忌搜索算法不仅可以找到全局最优解，还可以避免局部最优解的产生，使得结果更加准确。

无时限单向配送车辆优化调度问题的禁忌搜索算法无时限单向配送车辆优化调度问题，是指在制定配送路线时不考虑客户对货物送到（或取走）时间要求的纯送货（或纯取货）车辆调度问题。

无时限单向配送车辆优化调度问题可以描述为：从某配送中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足一下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。

一、禁忌搜索算法的原理禁忌搜索算法是解决组合优化问题的一种优化方法。

该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。

在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。

为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。

另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。

二、算法要素的设计1.禁忌对象的确定禁忌对象是指禁忌表中被禁的那些变化元素。

由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。

一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。

根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。

举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。

第１３卷㊀第５期Ｖｏｌ．１３Ｎｏ．５㊀㊀智㊀能㊀计㊀算㊀机㊀与㊀应㊀用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ㊀㊀２０２３年５月㊀Ｍａｙ２０２３㊀㊀㊀㊀㊀㊀文章编号：２０９５－２１６３（２０２３）０５－０１７１－０４中图分类号：ＴＰ３０１文献标志码：Ａ混合禁忌搜索的车间调度遗传算法研究管㊀赛，熊禾根（武汉科技大学机械自动化学院，武汉４３００８１）摘㊀要：针对以最小化最大完工时间为目标的作业车间调度问题，提出一种混合禁忌搜索的遗传算法㊂禁忌搜索是一种能有效跳出局部最优解的元启发式算法，在每次迭代过程中通过搜索当前解的邻域来获得一个新解，通过评价新解的优越性来优化求解结果；加入多种交叉方式随机选择来扩大种群多样性；同时加入局部邻域搜索来改善解的质量，加快算法收敛速度㊂将提出的改进算法用于求解若干基准问题，算法具有一定的改良性，能优化求解结果㊂关键词：作业车间调度；遗传算法；禁忌搜索；局部邻域搜索ＡｈｙｂｒｉｄｔａｂｏｏｓｅａｒｃｈｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｓｈｏｐｆｌｏｏｒｓｃｈｅｄｕｌｉｎｇＧＵＡＮＳａｉ，ＸＩＯＮＧＨｅｇｅｎ（ＳｃｈｏｏｌｏｆＭｅｃｈａｎｉｃａｌＡｕｔｏｍａｔｉｏｎ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００８１，Ｃｈｉｎａ）ʌＡｂｓｔｒａｃｔɔＡｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｗｉｔｈｈｙｂｒｉｄｔａｂｏｏｓｅａｒｃｈｉｓｐｒｏｐｏｓｅｄｆｏｒａｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｔｏｍｉｎｉｍｉｚｅｔｈｅｍａｘｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅ．Ｔａｂｏｏｓｅａｒｃｈｉｓａｍｅｔａ－ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｔｈａｔｃａｎｅｆｆｅｃｔｉｖｅｌｙｊｕｍｐｏｕｔｏｆｔｈｅｌｏｃａｌｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ，ａｎｄｏｂｔａｉｎｓａｎｅｗｓｏｌｕｔｉｏｎｂｙｓｅａｒｃｈｉｎｇｔｈｅｎｅｉｇｈｂｏｒｈｏｏｄｏｆｔｈｅｃｕｒｒｅｎｔｓｏｌｕｔｉｏｎｄｕｒｉｎｇｅａｃｈｉｔｅｒａｔｉｏｎ，ａｎｄｏｐｔｉｍｉｚｅｓｔｈｅｓｏｌｕｔｉｏｎｒｅｓｕｌｔｂｙｅｖａｌｕａｔｉｎｇｔｈｅｓｕｐｅｒｉｏｒｉｔｙｏｆｔｈｅｎｅｗｓｏｌｕｔｉｏｎ．Ａｖａｒｉｅｔｙｏｆｃｒｏｓｓｏｖｅｒｍｅｔｈｏｄｓａｒｅａｄｄｅｄｆｏｒｒａｎｄｏｍｓｅｌｅｃｔｉｏｎｔｏｅｘｐａｎｄｔｈｅｐｏｐｕｌａｔｉｏｎｄｉｖｅｒｓｉｔｙ．Ｍｅａｎｗｈｉｌｅ，ｌｏｃａｌｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈｉｓａｄｄｅｄｔｏｉｍｐｒｏｖｅｔｈｅｑｕａｌｉｔｙｏｆｔｈｅｓｏｌｕｔｉｏｎａｎｄｓｐｅｅｄｕｐｔｈｅｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｔｈｅｐｒｏｐｏｓｅｄｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｓｕｓｅｄｔｏｓｏｌｖｅｓｅｖｅｒａｌｂｅｎｃｈｍａｒｋｐｒｏｂｌｅｍｓ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｈａｓｓｏｍｅｉｍｐｒｏｖｅｍｅｎｔｓｔｏｏｐｔｉｍｉｚｅｔｈｅｓｏｌｕｔｉｏｎｒｅｓｕｌｔｓ．ʌＫｅｙｗｏｒｄｓɔｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｔａｂｏｏｓｅａｒｃｈ；ｌｏｃａｌｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈ作者简介：管㊀赛（１９９５－），男，硕士研究生，主要研究方向：作业车间调度及其智能算法；熊禾根（１９６６－），男，博士，教授，博士生导师，主要研究方向：作业车间调度及其智能算法㊂通讯作者：熊禾根㊀㊀Ｅｍａｉｌ：ｘｉｏｎｇｈｅｇｅｎ＠１２６．ｃｏｍ收稿日期：２０２２－０５－３１０㊀引㊀言作业车间调度问题（ＪｏｂＳｈｏｐＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ，ＪＳＰ）是典型的ＮＰ－ｈａｒｄ问题，是目前研究最为广泛的一类调度问题，其存在于制造㊁物流㊁汽车等众多领域的实际生产中，故研究内容具有重要的理论意义和工程价值㊂调度问题的求解方法可分为两类：精确求解方法和近似求解方法㊂精确求解方法包括解析法㊁穷举法㊁分支定界法等；近似求解方法包括基于规则的构造性方法㊁邻域搜索方法以及人工智能方法等㊂其中邻域搜索中的遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＧＡ）结构简单㊁易于实现，且能获得较好的求解结果，所以被作为应用最广的智能优化算法，广泛应用于ＪＳＰ的求解之中㊂但标准遗传算法存在早熟收敛，解的稳定性差等缺点㊂对此何斌等人［１］提出一种改进遗传算法来求解作业车间调度问题，通过采取新的个体适应度计算方法，多种交叉操作随机选择，自适应交叉变异参数调整策略，来提升遗传算法的性能㊂张超勇等人［２］提出一种局部邻域搜索的遗传算法求解ＪＳＰ㊂该算法采用新的ＰＯＸ交叉算子，基于邻域搜索的变异算子，以及基于关键路径邻域的局部搜索，以改善解的质量㊂郑先鹏等人［３］提出的改进遗传算法采用精英保留策略，并结合改进自适应算子对问题进行求解，提升了求解ＪＳＰ的能力㊂王玉芳等人［４］提出了一种改进混合模拟退火算法，该算法采用自适应策略对概率进行动态调整，选择一种基于工序编码新的ＩＰＯＸ交叉算子，同时加入有记忆功能的模拟退火算法，优化了ＪＳＰ的求解结果㊂禁忌搜索是一种全局寻优算法，搜索过程中能跳出局部最优解，同时具有良好的寻求优良解的能力，能有效提升算法的运算效率，实现高效搜索［５］㊂标准遗传算法虽然具有较强的全局搜索能力，但局部搜索能力较弱，在迭代过程中易早熟且陷入局部最优解㊂因此，本文提出一种混合禁忌搜索的改进遗传算法（ＩｍｐｒｏｖｅｄＴａｂｕＳｅａｒｃｈＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＩＴＳＧＡ），在原有的标准遗传算法基础上加入禁忌搜索算法，并改进算法流程，加入多种交叉方式的随机选择来提高种群的多样性以及产生优质解，同时加入局部邻域搜索对解进行微调，改善解的质量，达到寻找全局最优解的目的㊂１㊀ＪＳＰ问题描述ＪＳＰ可描述为：用ｍ台机器加工ｎ个工件，每个工件ｉ都包含一系列工序，给定每道工序Ｏｉｊ的加工机器及加工时间ｐｉｊ㊂约束条件为：（１）同一时刻一台机器只能加工一道工序；（２）工件不能在同一台机器上多次加工；（３）不考虑工件加工优先权且工序加工过程不能中断㊂建立ＪＳＰ数学模型如下：Ｆ＝ｍｉｎ｛ｍａｘ｛Ｃｉ｝｝ｃｉｋ–ｐｉｋ＋Ｍ（１－ａｉｈｋ）ȡｃｉｈ（１）ｃｌｋ–ｃｉｋ＋Ｍ（１－ｘｉｌｋ）ȡｐｌｋ（２）ｃｉｋȡ０（３）ａｉｈｋ＝１㊀若机器ｈ先于机器ｋ加工工件ｉ０㊀非上述情况{（４）ｘｉｌｋ＝１㊀若工件ｉ先于工件ｌ在机器ｋ上加工０㊀非上述情况{（５）㊀㊀其中，目标函数Ｆ为最小化最大完工时间；Ｃｉ为工件ｉ的最大完工时间；式（１） 式（３）表示工艺约束条件决定的工件上各工序先后操作顺序，以及加工各工件的机器先后顺序；Ｃｉｋ㊁ｐｉｋ分别为工件ｉ在机器ｋ上的完工时间和加工时间；Ｍ为一足够大正数；式（４）㊁式（５）中定义决策变量ａｉｈｋ和ｘｉｌｋ，分别确定同一工件在不同机器上的加工先后顺序和同一机器上不同工序的加工先后顺序，２㊀ＩＴＳＧＡＩＴＳＧＡ算法采用基于工序编码的编码方式来表示个体，具有在进行染色体置换操作后总能得到可行解的优点㊂种群初始化方式为随机生成初始种群，以最小化最大完工时间为评价指标，采用轮盘赌选择算子来进行个体选择，同时为了保留优秀个体，加快种群收敛速度，加入精英保留策略㊂在每次选择时，将最优基因直接复制保留下来，以便个体的优良性状能遗传到子代中㊂个体适应度函数定义为ｆ（ｉ）＝ＭＳｍａｘ－ＭＳ（ｇ）（６）㊀㊀其中，ＭＳ（ｇ）表示个体ｇ对应的最大完工时间，ＭＳｍａｘ为种群中的最大值㊂２．１㊀随机选择多种交叉方式交叉操作是遗传算法的核心操作，直接决定迭代过程中解的优劣情况和算法的全局搜索能力㊂本文提出迭代过程中多种交叉方式随机选择，以增加求解结果的多样性㊂以下列出一些在求解ＪＳＰ时用到的交叉操作，随机选择的方式为等概率随机选择㊂ＰＯＸ交叉［６］示意图如图１所示，随机划分工件集｛１，２，３， ，ｎ｝为两个非空子集Ｊ１㊁Ｊ２；将父代Ｐ１㊁Ｐ２中包含Ｊ１的工件复制到子代Ｃ１㊁Ｃ２中，保留原位置；复制父代Ｐ１中包含Ｊ２的工件到子代Ｃ２，复制父代Ｐ２中包含Ｊ２的工件到子代Ｃ１，保留其顺序㊂图１说明了ＰＯＸ算子交叉过程㊂P 1C 1P 2C 2J 1={2}J 2={1，3}图１㊀ＰＯＸ交叉Ｆｉｇ．１㊀ＰＯＸｃｒｏｓｓｏｖｅｒ２．１．１㊀ＯＸ交叉ＯＸ交叉操作的示意如图２所示㊂父代中随机生成两个基因座（假设４和６），以生成子代Ｃ１为例，将父代Ｐ１基因片段３２３继承给子代Ｃ１，以父代Ｐ２第７个基因座作为第一个基因，从右往左生成临时基因编码｛２３２３２１３１１｝，再根据对应位置将基因片段在临时基因编码中一一剔除｛２３２３２１３１１｝ң｛２２１３１１｝，最后再将剔除后剩余的基因片段放入子代Ｃ１中㊂同理，子代Ｃ２的生成过程与上述类似㊂２．１．２㊀ＰＭＸ交叉ＰＭＸ交叉操作的示意如图３所示㊂随机选择两个基因座（假设４和７），得到映射关系３（工件３第一道工序）ѳң１（工件１第三道工序）㊁１（工件１第三道工序）ѳң１（工件１第二道工序），将父代Ｐ１的基因片段３２３１继承给子代Ｃ１并保留原位置，再根据映射关系替换父代Ｐ２中非选中基因片段｛３２１ｘｘｘｘ３２｝ң｛１２１ｘｘｘｘ３２｝，将替换后的片段放入２７１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀子代Ｃ１中，生成子代Ｃ１㊂同理子代Ｃ２的生成过程与上述类似㊂P1C1P2C2图２㊀ＯＸ交叉Ｆｉｇ．２㊀ＯＸｃｒｏｓｓｏｖｅｒP1P2P1片段替换后的P2片段C1图３㊀ＰＭＸ交叉Ｆｉｇ．３㊀ＰＭＸｃｒｏｓｓｏｖｅｒ２．２㊀局部邻域搜索关键路径的变化是改变最大完工时间的关键，本文采取基于关键块的快速邻域搜索方式［７－９］，其流程如下：步骤１㊀确定当前解的关键路径和全部关键块㊂步骤２㊀设计邻域构造为交换关键块中的两个工序㊂３种交换方式为：㊀㊀（１）选择关键块中的首工序与块中任一工序进行交换；（２）选择关键块中任意两个内部工序进行交换；（３）选择关键块中的尾工序与块中任一工序进行交换㊂步骤３㊀通过随机选择来确定关键块中工序的交换方式㊂步骤４㊀将经过局部邻域搜索操作后的解添加到种群中㊂３㊀算法验证为了验证ＩＴＳＧＡ算法在求解作业车间调度问题的有效性，将本文算法与改进粒子群（ＩｍｐｒｏｖｅｄＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＩＰＳＯ）算法［１０］㊁量子鲸鱼优化（ＱｕａｎｔｕｍＷｈａｌｅＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍ，ＱＷＯＡ）算法［１１］㊁改进混合遗传模拟退火（ＩｍｐｒｏｖｅｄＧｅｎｅｔｉｃＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍ，ＩＧＳＡＡ）算法［４］进行对比㊂算法采用ｐｙｔｈｏｎ编程，在２．４０ＧＨｚ处理器的Ｗｉｎｄｏｗｓ１０系统下运行㊂参数设置如下：种群规模Ｐ＝１００，最大迭代次数２００，交叉概率ｐｃ＝０．９，变异概率ｐｍ＝０．１，禁忌表长度为最大迭代次数㊂表１中，Ｃ∗为已知最优解；ｂｅｓｔ为运行１０次得到的最优解；ａｖｇ为连续运行１０次得到的平均值；加粗数据表示已经达到最优解㊂选取ｂｅｎｃｈｍａｒｋ中关于ＪＳＰ的若干算例进行验证㊂㊀㊀从表１中所列数据可以看出，ＩＴＳＧＡ算法对于表格算例中求解的最优值和平均值均优于其它算法㊂对于除ＦＴ２０外的其他算例均已达到最优解，这是其他算法所未能达到的，且本文算法求解ＦＴ１０㊁ＦＴ２０得到的平均值都要明显优与其他算法㊂表１㊀各算法对ｂｅｎｃｈｍａｒｋ问题求解结果比较Ｔａｂ．１㊀Ｃｏｍｐａｒｉｓｏｎｏｆｔｈｅｒｅｓｕｌｔｓｏｆｂｅｎｃｈｍａｒｋｐｒｏｂｌｅｍｂｙｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓ算例规模ｎˑｍＣ∗ＧＡｂｅｓｔａｖｇＩＰＳＯｂｅｓｔａｖｇＱＷＯＡｂｅｓｔａｖｇＩＧＳＡＡｂｅｓｔａｖｇＩＴＳＧＡｂｅｓｔａｖｇＦＴ０６６ˑ６５５５５５５５５５５５５５５．３５５５５５５５５ＦＴ１０１０ˑ１０９３０９９４１０４０．９９７５１０２７９６６１００７．２９５１９８１．４９３０９４７．２ＦＴ２０２０ˑ５１１６５１２６４１３２０．６１２０６１２２２１２０７１２５２．１１１８１１２０７．６１１６８１１９１．２ＬＡ０１１０ˑ５６６６６６６６６７．６６６６６６６６６６６６７．５６６６６６６６６６６６６ＬＡ０６１５ˑ５９２６９２６９２６９２６９２６９２６９２６９２６９２６９２６９２６ＬＡ１１２０ˑ５１２２２１２２２１２２２１２２２１２２２１２２２１２２２１２２２１２２２１２２２１２２２ＬＡ１６１０ˑ１０９４５９７８９９０．３９７３１０１１９４６９９４．３９４５９５３．７９４５９５２．７３７１第５期管赛，等：混合禁忌搜索的车间调度遗传算法研究㊀㊀以求解机器数量较多的ＦＴ１０为例，进一步说明ＩＴＳＧＡ的有效性㊂ＩＴＳＧＡ算法在求解ＦＴ１０得到的最优值和平均值都大大优于算法ＧＡ，更易跳出局部最优解，且在迭代初期就能快速收敛，说明加入的禁忌搜索算法和多种交叉方式随机选择起到了很好的作用㊂同时，精英保留策略也能够使子代更好地继承父代的优良性状；局部邻域搜索则提高了算法达到最优解的可能性㊂图４为运用ＩＴＳＧＡ求解算例ＦＴ１０得到的甘特图，图中Ｏ１，２中１表示工件号，２表示工序号㊂12345678910工件10987654321机器93186279372465558651744837930930时间图４㊀ＩＴＳＧＡ求解ＦＴ１０得到的甘特图Ｆｉｇ．４㊀ＧａｎｔｔｃｈａｒｔｏｂｔａｉｎｅｄｂｙＩＴＳＧＡｓｏｌｖｉｎｇｂｅｎｃｈｍａｒｋＦＴ１０４㊀结束语本文提出的ＩＴＳＧＡ算法通过融合禁忌搜索和局部邻域搜索的改进，增强了求解ＪＳＰ的寻优能力，既有一定的全局寻优能力，能很好地避免陷入局部最优解，提高了算法的求解效率㊂将本文算法应用于求解若干基准问题时得到了较好结果，与传统遗传算法的求解结果相比均有较大的提升，经过与其它改进算法的比较结果，验证了ＩＴＳＧＡ算法的有效性㊂参考文献［１］何斌，张接信，张富强．一种求解作业车间调度问题的改进遗传算法［Ｊ］．制造业自动化，２０１８，４０（８）：１１３－１１７．［２］王佳怡，潘瑞林，秦飞．改进遗传算法求解柔性作业车间调度问题［Ｊ］．制造业自动化，２０２２，４４（１２）：９１－９４，１０６．［３］郑先鹏，王雷．面向作业车间调度问题的遗传算法改进［Ｊ］．河北科技大学学报，２０１９，４０（６）：４９６－５０２．［４］王玉芳，缪昇，马铭阳，等．改进混合遗传算法的作业车间调度研究［Ｊ］．现代制造工程，２０２１（５）：３２－３８．［５］王凌．车间调度及其遗传算法［Ｍ］．北京：清华大学，２００３．［６］张超勇，饶运清，刘向军，等．基于ＰＯＸ交叉的遗传算法求解Ｊｏｂ－Ｓｈｏｐ调度问题［Ｊ］．中国机械工程，２００４（２３）：８３－８７．［７］ＬＡＡＲＨＯＶＥＮＰＪＭＶ，ＡＡＲＴＳＥＨＬ，ＬＥＮＳＴＲＡＪＫ．Ｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｂｙｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇ［ｊ］．ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，１９９２，４０（１）：１．［８］ＮＯＷＩＣＫＩＥ，ＳＭＵＴＮＩＣＫＩＣ．Ａｆａｓｔｔａｂｏｏｓｅａｒｃｈａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｊｏｂｓｈｏｐｐｒｏｂｌｅｍ［Ｊ］．ＭａｎａｇｅｍｅｎｔＳｃｉｅｎｃｅ，１９９６，４２（６）：３．［９］张超勇．基于自然启发式算法的作业车间调度问题理论与应用研究［Ｄ］．武汉：华中科技大学，２００７．［１０］刘洪铭，曾鸿雁，周伟，等．基于改进粒子群算法作业车间调度问题的优化［Ｊ］．山东大学学报（工学版），２０１９，４９（１）：７５－８２．［１１］闫旭，叶春明，姚远远．量子鲸鱼优化算法求解作业车间调度问题［Ｊ］．计算机应用研究，２０１９，３６（４）：９７５－９７９．４７１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀。