2.2　启发式算法

启发式算法是相对最优化算法提出的，是指受到大自然的运行规律或人类解决具体问题时积累的工作经验等的启发而产生的算法。它可以在混流装配线生产计划的有限搜索空间内给出组合优化问题的一个可行解，故在混流装配线的生产计划优化问题中可以大大减少尝试的数量，加快求解速度。适用于混流装配线生产计划优化问题的常用启发式算法有粒子群算法、模拟退火算法、遗传算法、禁忌搜索算法和蚁群算法等。以下针对常见启发式算法在混流装配线中的应用进行具体描述。

2.2.1　粒子群算法

粒子群（Particle Swarm Optimization，PSO）算法是对鸟类群体觅食行为进行模拟的一种智能优化算法，适用于大规模、复杂环境的混流装配线优化问题。混流装配线优化问题的解空间可以看作粒子群算法的可行域，而群体中的每个个体可以视为混流装配线优化目标的潜在可行解，通过赋给每个粒子一定的速度（忽略粒子的大小和质量）使其能在可行域内飞行，并根据个体和群体的寻找经验影响粒子接下来的飞行方向和速度，实现对混流装配线生产计划优化问题中最优解的确定。但是，由于混流装配线生产计划优化问题规模庞大、环境复杂，运用粒子群算法处理类似混流装配线生产计划优化问题这样的多约束目标优化问题还需要进一步深入研究。

1. 基本思想

粒子群算法也称为粒子群优化算法或鸟群觅食算法，是由J. Kennedy和R. C. Eberhart等开发的一种新的进化算法（Evolutionary Algorithm，EA）。粒子群算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，以及通过适应度来评价解的品质，但它比遗传算法规则简单，它没有遗传算法的“交叉”（Crossover）和“变异”（Mutation）操作，通过追随当前搜索到的最优值来寻找全局最优解。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法，目前已广泛应用于函数优化、神经网络训练、模糊系统控制及其他遗传算法的应用领域。

近年来，一些学者将粒子群（PSO）算法推广到约束优化问题，其关键在于如何处理好约束，即解的可行性。如果约束处理得不好，其优化的结果往往会出现不能收敛和结果是空集的状况。基于粒子群算法的约束优化工作主要分为以下两类。

（1）罚函数法。罚函数的目的是将约束优化问题转化为无约束优化问题。

（2）将粒子群的搜索范围都限制在条件约束簇内，即在可行解范围内寻优。

根据文献介绍，有研究学者采用罚函数法，利用非固定多段映射函数对约束优化问题进行转化，再利用粒子群算法求解转化后的问题。仿真结果显示粒子群算法相对遗传算法更具有优越性，但其罚函数的设计过于复杂，不利于求解；也有学者采用可行解保留政策处理约束，即一方面更新存储所有粒子时仅保留可行解，另一方面在初始化阶段所有粒子均从可行解空间取值，然而初始可行解空间对于许多问题是很难确定的。此外，有专家学者提出了具有多层信息共享策略的粒子群原理来处理约束，根据约束矩阵采用多层Pareto排序机制来产生优良粒子，进而用一些优良粒子来决定其余个体的搜索方向。

2. 标准粒子群算法的流程

（1）初始化一群微粒（群体规模为m），包括随机位置和速度。

（2）评价每个微粒的适应度。

（3）对于每个微粒，将其适应值与其经过的最好位置pbest进行比较，若较好，则将其作为当前的最好位置pbest。

（4）对于每个微粒，将其适应值与其经过的最好位置gbest进行比较，若较好，则将其作为当前的最好位置gbest。

（5）根据优化函数式调整微粒的速度和位置。

（6）未达到结束条件则转（2）。

标准粒子群算法的流程图如图2-3所示。

简而言之，粒子群算法是模拟群体智能所建立起来的一种优化算法，粒子群算法可以用鸟类在一个空间内随机觅食为例，所有的鸟都不知道食物具体在哪里，但是它们知道大概距离多远，最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。所以，粒子群算法就是将鸟看成一个个粒子，并且它们拥有位置和速度这两个属性，然后根据自身已经找到的离食物最近的解和参考整个共享于整个集群中找到的最近的解去改变自己的飞行方向，最终会发现，整个集群大致向同一个地方聚集，而这个地方是离食物最近的区域，在适当条件下鸟类即可找到食物。

2.2.2　模拟退火算法

模拟退火（Simulated Annealing，SA）算法是一种在搜索过程中引入随机因素的贪心算法，在混流装配线生产计划优化问题中，它能够以一定概率来接受一个比当前解要差的解，由此可能跳出优化问题的局部最优解，并在优化全局域内寻找到符合要求的最优解。因此，模拟退火算法在混流装配线生产计划优化问题中主要用于寻找到优化解空间中的全局最优解；但其缺点是在寻找优化解空间中最优解的运算效率会比较低。

1. 基本思想

模拟退火算法最早的思想是由N. Metropolis等于1953年提出的，之后有学者将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能，目前已在工程中得到了广泛应用，如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其慢慢冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而慢慢冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e(-∆E/(kT))，其中E为温度T时的内能，∆E为其改变量，k为Boltzmann常数。使用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数初值t，即得到解组合优化问题的模拟退火算法。由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于Monte-Carlo迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数初值t及其衰减因子∆t、每个t值时的迭代次数L和停止条件S。

2. 算法流程

模拟退火算法可以分解为解空间、目标函数和初始解三部分。其基本思路流程如下。

（1）初始化：初始温度T（充分大），初始解状态S（是算法迭代的起点），每个T值的迭代次数L。

（2）对k=1,…,L做第（3）～（6）步。

（3）产生新解S'。

（4）计算增量∆t'=C(S')-C(S)，其中C(S)为评价函数。

（5）若∆t'≤0，则接受S'作为新的当前解；否则，以概率exp(-∆t'/T)接受S'作为新的当前解。

（6）若满足终止条件，则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受。

（7）T逐渐减少，且T趋于0，然后转第（2）步。

模拟退火算法的流程如图2-4所示。

2.2.3　遗传算法

遗传算法（Genetic Algorithm，GA）是模拟自然界生物进化规律得来的一种随机搜索算法。遗传算法可以将可行域内的混流装配线生产计划优化模型中潜在解视为生物种群中的一条染色体，遵循优胜劣汰的遗传选择规律，借助遗传学的基本操作（遗传、变异、交叉）逐代进化出越来越优的染色体，各条染色体的好坏是依据优化问题拟定一个适应度函数来评价的，遵循适者生存的选择规则，对混流装配线生产计划优化模型解空间中候选种群中的个体进行择优。选择子代种群优于父代种群的个体，经逐步寻优后，最终种群中的最优个体即可认为是混流装配线生产计划优化问题的最优解。由于遗传算法复杂的优化过程、不确定的编码规则，使得其在混流装配线生产计划优化问题中的最优化结果存在一定的不准确性，且算法易过早收敛，在精度、可行度、算法复杂性等方面还需要进一步定量分析，因此将遗传算法应用于大规模、复杂环境的混流装配线生产计划优化问题还需要结合其他辅助优化方法，并进行深入的研究分析。

1. 基本思想

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（Population）开始的，而一个种群则由经过基因（Gene）编码的一定数目的个体（Individual）组成。每个个体实际上是染色体（Chromosome）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（基因型）是某种基因组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始就需要实现从表现型到基因型的映射，即编码工作。由于仿照基因编码的工作很复杂，因此需要进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（Generation）演化产生出越来越好的近似解，在每一代中，根据问题域中个体的适应度（Fitness）的大小选择（Selection）个体，并借助自然遗传学的遗传算子（Genetic Operators）进行组合交叉（Crossover）和变异（Mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应环境，末代种群中的最优个体经过解码（Decoding）可以作为问题近似最优解。

对于一个求函数最大值的优化问题（求函数最小值也类同），一般可以描述为下列数学规划模型。

式中，X为决策变量；max f(X)为目标函数式；X∈R，R⊂U，均为约束条件；U为基本空间；R为U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。而通过遗传算法解决优化问题的主要思想就是通过类似数学规划模型的方法，制定决策变量、设计目标函数、设置约束条件，最后通过迭代过程完成目标值的近似优化求解。

2. 算法流程

（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

（2）个体评价：计算群体P(t)中各个体的适应度。

（3）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

（5）变异运算：将变异算子作用于群体，就是对群体中的个体串的某些基因座上的基因值做变动。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)。

（6）终止条件判断：若t=T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。

遗传算法的流程图如图2-5所示。

遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。

2.2.4　禁忌搜索算法

禁忌搜索（Tabu Search，TS）算法是一种模拟人类思维模式的随机搜索算法。在混流装配线生产计划优化问题中，它通过不断试探获得混流装配线生产计划优化问题中解空间的特定搜索方向，并受此前已记录的搜索方向影响，贪婪地对每个局部区域及其领域进行搜索。为避免陷入找到局部最优解，算法在搜索过程中会有意识地避开当前优化空间的最优解，从而获得更多的搜索区域。同时，在混流装配线生产计划优化问题中为避免出现循环搜索，引入禁忌表停止准则禁止算法移回那些解。其在寻求混流装配线生产计划优化问题中的最优解方面能够取得一定的效果，但该算法的搜索效率取决于初始解的选取，且搜索过程是串行的，而不是并行的，造成搜索速度低，故针对大规模、复杂环境的混流装配线生产计划优化问题，该方法还需要进一步深入探讨。

1. 基本思想

禁忌搜索过程是指标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于太过于对某一局部区域及其邻域的搜索，导致“一叶障目”。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而获得更多的搜索区域。

2. 算法流程

（1）给定一个禁忌表（Tabu List）H=null，并选定一个初始解X_now。

（2）若满足停止规则，则停止计算，输出结果；否则，在X_now的领域中选出满足不受禁忌的候选集N(X_now)。

（3）在N(X_now)中选择一个评价值最佳的解X_next，X_next=X_now。

（4）更新历史记录H，重复步骤（2）。

2.2.5　蚁群算法

蚁群系统（Ant System或Ant Colony System）是由意大利学者Dorigo、Maniezzo等于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如，蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种被称为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高的路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

蚁群算法的流程图如图2-6所示。

将蚁群算法应用于解决优化问题的基本思路是：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁数量也越来越多。最终，整个蚁群会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，开始时两条路上的蚂蚁数量差不多。当蚂蚁到达终点之后会立即返回，距离短的路径的蚂蚁往返一次时间短，重复频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多，会吸引更多蚂蚁过来，留下更多的信息素；而距离长的路径正相反，因此越来越多的蚂蚁聚集到最短路径上来。蚂蚁具有的智能行为得益于其简单行为规则，该规则让其具有多样性和正反馈。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环，是一种创新能力；正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智能行为涌现，如果多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态；如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。