1.GA（遗传算法）

GA是由美国密西根大学J.Holland教授于20世纪90年代提出来的一种模拟生物进化规律而发展起来的优化方法［2］。GA的主要特点有：较强的隐并行性和全局搜索能力；基于概率化的寻优机制；能自动保留较优解并指导优化的搜索方向，不需要依赖问题的数学特征规则。基于这些优点，GA已被广泛应用于车间调度、图像处理、交通运输、信号处理、金融以及人工智能等领域。

GA有五大核心要素，分别为：编码和解码、种群初始化、适应度函数、遗传算子（包括复制或选择、交叉、变异等），以及遗传参数（种群规模、遗传算子的概率等）设置［3］。GA流程图通常如图3-1所示，具体操作步骤如下。

Step 1：生成初始化种群P（0）；

Step 2：计算种群中每个个体的适应度值；

Step 3：判断是否满足迭代停止条件，如满足则输出当前最优结果；否则转到Step 4；

Step 4：种群更新操作，即对种群进行复制（或选择）、交叉及变异等操作，以产生新一代种群P（gen），gen=gen+1，转到Step 2。

图3-1　GA流程图

2.GWO算法（灰狼优化算法）

GWO算法是由澳大利亚格里菲斯大学学者Mirjalili等人于2014年提出来的一种群智能优化算法［4］。他们受到灰狼捕食猎物活动的启发而开发了这种优化搜索方法，它具有较强的收敛性能，还具有参数少、易实现等特点，近年来受到了学者的广泛关注，已被成功地应用到了车间调度［5，6］、参数优化［7］、图像分类［8］等领域中。灰狼隶属于群居生活的犬科动物，且处于食物链的顶层。灰狼严格遵守着一个社会支配等级关系，如图3-2所示。狼群中的头狼记为α，α狼主要负责对捕食、栖息、作息等活动做出决策。由于其他的狼需要服从α狼的命令，所以α狼也被称为支配狼。有趣的是，α狼不一定是狼群中最强的狼，但就管理能力来说，α狼一定是最优秀的。处于社会等级第二层的是β狼，它服从于α狼，并协助α狼做出决策。在α狼去世或衰老后，β狼将成为α狼的最佳候选者。虽然β狼服从α狼，但β狼可支配其他社会层级上的狼。处于社会等级第三层的是δ狼，它服从α狼、β狼，同时支配剩余层级的狼。δ狼一般由幼狼、哨兵狼、狩猎狼、老年狼及护理狼组成。处于最底层的狼被称为ω狼，它们通常需要服从其他社会层级上的狼。虽然看上去ω狼在狼群中的作用不大，但是如果没有ω狼的存在，狼群会出现内部问题，如自相残杀。GWO算法的优化过程包含了灰狼的社会等级分层、跟踪、包围和攻击猎物等，其具体步骤如下。

图3-2　灰狼社会分层等级（从上到下支配能力依次递减）

1）社会等级分层（social hierarchy）

当设计GWO算法时，首先需构建灰狼社会等级层次模型。计算种群每个个体的适应度，将狼群中适应度最好的三匹灰狼依次标记为α、β、δ，而剩下的灰狼标记为ω。也就是说，灰狼群体中的社会等级从高往低排列依次为：α、β、δ及ω。GWO算法的优化过程主要由每代种群中最好的三个解（即α、β、δ）来指导完成。(www.daowen.com)

2）包围猎物（encircling prey）

灰狼搜索猎物时会逐渐地接近猎物并包围它，该行为的数学模型如下：

式中：t为当前迭代次数；◦表示Hadamard（阿达马）乘积操作；A和C是协同系数向量；Xp表示猎物的位置向量；X（t）表示当前灰狼的位置向量；r1和r2是［0，1］中的随机向量；D表示灰狼与猎物之间的位置向量；a表示在整个迭代过程中［2，0］上的线性下降向量。

3）狩猎（hunting）

灰狼具有识别潜在猎物位置（猎物位置对应最优解）的能力，搜索过程主要靠α、β、δ灰狼的指引来完成。但是很多问题的解空间特征是未知的，灰狼无法确定猎物的精确位置（最优解）。为了模拟灰狼（候选解）的搜索行为，假设α、β及δ具有较强的识别潜在猎物位置的能力，因此，在每次迭代过程中，保留当前种群中适应度最好的三匹灰狼（α、β、δ），然后根据它们的位置信息来更新其他搜索代理（包括ω）的位置。该行为的数学模型可表示如下：

式中：Xα、Xβ、Xδ分别表示当前种群中α、β、δ的位置向量；X表示当前灰狼的位置向量；Dα、Dβ、Dδ分别表示当前候选灰狼与最优三匹狼之间的距离。当时，灰狼尽量分散在各区域并搜寻猎物。当时，灰狼将集中搜索某个或某些区域的猎物。

为了说明其搜索过程，图3-3展示了在二维搜索空间中一个候选解（灰狼）是如何在α、β、δ的引导下逐渐地向猎物靠近的过程。从图3-3中可看出，候选解的位置最终落在被α、β、δ定义的随机圆位置内。总的来说，α、β、δ需首先预测出猎物的大致位置（潜在最优解），然后其他候选狼在当前最优三匹灰狼的指引下在猎物附近随机地更新它们的位置。

图3-3　灰狼更新位置

4）攻击猎物（attacking prey）

构建攻击猎物模型的过程中，根据公式（3-10），a值的减小会引起A的值也随之波动。换句话说，A是一个在区间［-2a，2a］上的随机向量，其中a在迭代过程中呈线性下降。当A在［-1，1］区间上时，则搜索代理（search agent）的下一时刻位置可以在当前灰狼与猎物之间的任何位置上。

5）寻找猎物（search for prey）

灰狼主要依赖α、β、δ的信息来寻找猎物。它们开始分散地去搜索猎物位置信息，然后集中起来攻击猎物。对于分散模型的建立，通过使其搜索代理远离猎物，这种搜索方式使GWO算法能进行全局搜索。GWO算法中的另一个搜索系数是C。从公式（3-11）可知，C是由区间［0，2］上的随机值构成的向量。这有助于GWO算法在优化过程中展示出随机搜索行为，以避免算法陷入局部最优解。值得注意的是，C并不是线性下降的，C在迭代过程中是随机值，该系数有利于算法跳出局部，特别是在算法迭代的后期显得尤为重要。