智能优化算法：探路者优化算法

@[toc]
摘要：探路者算法(Pathfinder Algorithm, PFA)是 2019年由 Yapici 提出的一种新的元启发式算法。该算法受群体动物的狩猎行为启发，将种群中的个体分为探路者（领导者）和跟随者；算法的寻优过程模拟了种群寻找食物的探索过程，通过探路者、跟随者二种不同种群角色间的交流来实现优化，同时在进化过程中也加强了种群三代间优良信息的保留；PFA 具有容易理解、实现简单、优化性能较好等优点。

1.算法原理

在探路者算法中，种群中的个体分为探路者(pathfinder)和跟随者(follower members)，它们共同组成种群团队。探路者个体是团队的领导者，指引算法的全局搜索方向，而种群中的跟随者沿着探路者的方向进行移动。种群中个体的移动使其位置向量发生变化，其对应的工件排列也随之改变，即种群的更新。

在种群的更新过程中，探路者是该种群运动方向的探索者，先于跟随者移动，其更新方式如式（1），（2）：
$X_p^{K+1}=X_p^{K}+2r_1(X_p^K-X_p^{K-1})+A \tag{1}$

$A = u_1e^{-2K/K_{max}}\tag{2}$

式中， $K$ 表示算法当前的迭代代数， $K_{max}$ 为算法的
最大迭代数； $X_p^K$ 表示当代探路者的位置， $X_p^{K-1}$ 表示上一代探路者的位置，则 $X_p^{K+1}$ 表示探路者更新后的位置； $r_1$ 为探路者移动的步长因子，在范围[0,1]内服从均匀分布； $A$ 表示探路者移动的多向性和随机性：多向性由 $u_1$ 的取值决定， $u_1$ 为[-1,1]范围内的随机数；步长大小的随机性由 $-2K/K_{max}$ 决定，即与算法迭代的次数有关。

此外，由于探索过程存在多向性和随机性，探路者探索到的位置可能不如原位置。因此，在探路者完成更新后加入保优操作，即更新后位置不如原位置，则探路者回到原位置。

探路者更新完成后，种群中跟随者根据探路者位置进行更新：
$X_i^{K+1} = X_i^K+R_1(X_j^K-X_i^K)+R_2(X_p^K-X_i^K+\varepsilon),i\geq2 \tag{3}$

$R_1=\alpha r_2\tag{4}$

$R_2=\beta r_3\tag{5}$

$\varepsilon=(1-K/K_{max})u_2D_{ij}\tag{6}$

$D_{ij}=||X_i-X_j||\tag{7}$

式中， $K$ 表示算法当前的迭代代数， $X_i^K$ 表示跟随者的当前位置,则 $X_i^{K+1}$ 表示其更新后的位置；跟随者的移动不仅与探路者 $X_p^K$ 有关,而且受到其他跟随者 $X_j^K$ 的影响, $\alpha$ 表示跟随者之间的相互作用系数， $\beta$ 表示探路者对跟随者的吸引系数,均在 [1,2]服从均匀分布； $r_2,r_3$ 分别为与其他跟随者和探路者移动的步长因子均为[0,1]范围内的随机数;同理，与探路者一样， $\varepsilon$ 表示跟随者移动的随机性， $u_2,D_{ij}$ 决定随机运动的方向和步长, $D_{ij}$ 为当前跟
随者与其他跟随者之间的距离。由上述可知，无论是探路者还是跟随者，其随机步长的大小都与算法迭代的次数有关，且代数越大步长越小。这是由于算法搜索初期需要在庞大的解空间中探索优质解区域，而在后期对优质解区域进行更细致的搜索，该操作有效地平衡了 PFA 全局搜索与局部搜索的关系。