基于模拟退火遗传算法的全向AGV路径规划的学习与实现
1、路径规划
路径规划的主要目标是根据有障碍物的环境，按照一定的要求规划出可供AGV高效平稳运行的无碰撞路径。
如下图所示，将复杂的环境简化成栅格地图模型。在栅格地图中进行路径规划，其中带有编号的方格为地图的最小单位，白色方格为空白区域，也就是不会影响到小车行进的区域，而黑色方格区域为障碍物与小车碰撞的范围，也就是小车不可行进的区域。路径规划的结果即由多个节点组成的一条由起点到终点的路线。
2、遗传算法
遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
为了更好的理解如何将遗传算法应用到路径规划问题中，我们将自然界遗传过程和路径规划问题进行类比。
自然界中的遗传是,在一定几率的下，父母双方的染色体经由重组，变异等过程形成子代的染色体，染色体中所携带的基因控制了子代的性状表达。并且正常情况下，子代染色体的总数是与父代相同的。
在路径规划问题中，可以将一条可行路径看作一条染色体，而组成路径的每个节点视为组成一条染色体的基因片段。而染色体的重组变异，我们相对的可以对节点进行重组变异操作。
3、模拟退火算法
模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
4、算法的具体结构及其实现
1、栅格图像生成
为了确保算法的普适性以及验证其正确性，算法每次运行所使用的栅格地图中的障碍物由随机生成，并且对每个方格进行编号。并且设定左下角方格为起点，右上角方格为终点。
2、路径初始化
1、确定初始种群大小M。设置起点S、目标点G，并将这两点用直线相连。
2、求出线段SG 的n-2 个垂直平分线L1，L2，…，Ln-2。
3、在虚线Li{i=1,2,…,n-2}上随机产生点Pi，其计算方法如式(4)、(5)所示。若生成的初始点不在自由空间内，则在Pi 的邻域生成一个新的点替换Pi。
x i = x 1 + i − 1 n − 1 ( x n − x 1 ) + m r a n d d grid ( x 1 − x n ) 2 + ( y 1 − y n ) 2 ( y 1 − y n ) x_i=x_1+\frac{i-1}{n-1}\left(x_n-x_1\right)+\frac{m_{r a n d} d_{\text {grid }}}{\sqrt{\left(x_1-x_n\right)^2+\left(y_1-y_n\right)^2}}\left(y_1-y_n\right) xi=x1+n−1i−1(xn−x1)+(x1−xn)2+(y1−yn)2 mranddgrid(y1−yn) (4)
y i = y 1 + i − 1 n − 1 ( y n − y 1 ) + m rand d grid ( x 1 − x n ) 2 + ( y 1 − y n ) 2 ( x n − x 1 ) y_i=y_1+\frac{i-1}{n-1}\left(y_n-y_1\right)+\frac{m_{\text {rand }} d_{\text {grid }}}{\sqrt{\left(x_1-x_n\right)^2+\left(y_1-y_n\right)^2}}\left(x_n-x_1\right) yi=y1+n−1i−1(yn−y1)+(x1−xn)2+(y1−yn)2 mranddgrid(xn−x1)(5)
式中：𝑛是染色体长度，𝑑𝑔𝑟𝑖𝑑是网格尺寸，(𝑥𝑖，𝑦𝑖 )是随机生成点Pi 的坐标，(𝑥1，𝑦1)和(𝑥𝑛，𝑦𝑛)分别是AGV 运动的起点S 和目标点G，𝑚𝑟𝑎𝑛𝑑是{−𝑚, 1 − 𝑚, ⋯ , 𝑚 − 1, 𝑚}中的随机数。
4) 由起始点S 开始，判断相邻两节点之间的连线有无障碍物，若无障碍物则用直线连接，若有障碍物则重复步骤3。若无可用相邻节点，则从起点重新开始初始化。
算法实现重点：
1、为了判断两点连线是否与障碍物区域有相交，先计算两个节点之间的路径所覆盖的区域，然后与障碍物区域取交集，从而判断路径是否可行。
2、结算与轴线相交的坐标精度问题。
下图为（4，1）与（7，13）的直线路径所覆盖的区域示例。
5）判断种群数量与M 的关系，若相等，则结束；若不相等，则重复步骤3~4。
初始化结果示例：
3、建立适应度函数
综合考虑实际应用中AGV 的经济性与平稳性，将所规划路径的长度、转弯次数以及路径角度大小作为评价指标，则得到多约束条件下AGV 的可行路径目标函数表达式为：
𝑓(𝑊∗) = min{𝑓1(𝑊), 𝑓2(𝑊), 𝑓3(𝑊)} (12)
式中：𝑊∗表示符合要求的路径，𝑓1(𝑊)、𝑓2(𝑊)、𝑓3(𝑊)分别由后面等式(13)、(14)、(15)给出。
1、 路径长度
f 1 ( W ) = ∑ i = 1 n − 1 ( x i + 1 − x i ) 2 + ( y i + 1 − y i ) 2 f_1(W)=\sum_{i=1}^{n-1} \sqrt{\left(x_{i+1}-x_i\right)^2+\left(y_{i+1}-y_i\right)^2} f1(W)=∑i=1n−1(xi+1−xi)2+(yi+1−yi)2 (13)
2、路径角度
f 2 ( W ) = ∑ i = 2 n − 1 arccos a ⃗ ⋅ b ⃗ ∣ a ⃗ ∣ ∣ b ⃗ ∣ f_2(W)=\sum_{i=2}^{n-1} \arccos \frac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|} f2(W)=∑i=2n−1arccos∣a ∣∣b ∣a ⋅b (14)
3、 AGV 转弯次数
f 3 ( W ) = ∑ i = 1 n − 2 Φ ( θ i ) f_3(W)=\sum_{i=1}^{n-2} \Phi\left(\theta_i\right) f3(W)=∑i=1n−2Φ(θi)（15）
式中：𝜃𝑖为每个转弯角度，若𝜃𝑖 ≠ 0，则Φ(𝜃𝑖 ) = 1。
由式(12)可知，以Fit 作为适应度函数，规划路径越短，路径转角越小，转弯次数越少时路径最优。所以适应度函数设计为式(16)所示，从中可以看出最优路径将具有最小的适应度函数值。
F i t ( W ) = α 1 ⋅ f 1 ( W ) + α 2 ⋅ f 2 ( W ) 18 0 ∘ ⋅ π + α 3 ∗ f 3 ( W ) F i t(W)=\alpha_1 \cdot f_1(W)+\alpha_2 \cdot \frac{f_2(W)}{180^{\circ}} \cdot \pi+\alpha_3 * f_3(W) Fit(W)=α1⋅f1(W)+α2⋅180∘f2(W)⋅π+α3∗f3(W)（16）
式中：𝛼1、𝛼2、𝛼3为各部分权值，分别取0.5，0.3，0.2。
4、改进选择算子
对于选择操作，大部分文献通常采用轮盘赌法，该方法虽然简单易操作，但可能导致优秀个体流失，使算法过早陷入局部最优解，即出现“早熟”现象。为了避免种群个体过于单一同时防止“早熟”现象出现，借鉴模拟退火思想对选择算子进行改进，使得选择概率趋于合理。与此同时，为了避免影响优良个体，后期需对新生成的种群实施精英保留策略。
在初始种群中任意抽取两个体𝑊1、𝑊2，分别计算各自适应度值𝐹𝑖𝑡(𝑊1)、𝐹𝑖𝑡(𝑊2)；基于模拟退火思想，选择𝑊1、𝑊2两者中的一个进化到子代，若𝐹𝑖𝑡(𝑊1) > 𝐹𝑖𝑡(𝑊2)，直接选择个体𝑊2进化到子代；否则，以概率𝑃𝑘接受个体𝑊2进化到子代；
P k = exp ( − F i t ( W 2 ) − F i t ( W 1 ) T ) , F i t ( W 1 ) ≤ F i t ( W 2 ) P_k=\exp \left(-\frac{F i t\left(W_2\right)-F i t\left(W_1\right)}{T}\right), F i t\left(W_1\right) \leq F i t\left(W_2\right) Pk=exp(−TFit(W2)−Fit(W1)),Fit(W1)≤Fit(W2)
式中，𝐹𝑖𝑡(𝑊1)为个体𝑊1的适应度值，𝐹𝑖𝑡(𝑊2)为𝑊2的适应度值，T 为当前温度，随着进化的进行𝑇要按降温速率衰减。当前温度T 的计算公式为：
T = T 0 × q G E N T=T_0 \times q^{G E N} T=T0×qGEN(18)
式中，𝑇0为初始温度，𝑞为降温速率，GEN 为迭代次数。重复(1)、(2)两步，直到新的子代种群数量达到指定值M。
5、改进交叉算子
随着种群的不断迭代，后面的种群中将包含许多相同的染色体，而相同染色体间的交叉是无效的，因此在交叉之前，基于编辑距离[17]对个体相似度进行筛选。编辑距离小的两个染色体之间不进行交叉操作。经过筛选后，采用单点交叉操作，从种群中随机选出2 个父代染色体，找出相同节点（除过S、G），然后关于该点执行交叉操作，如果不止一个相同点，则随机选取任意一点进行交叉。若2 个父代染色体无相同点，则从这2 个染色体中随机选取2 个点进行交叉；交叉得到的路径不连续时，使用种群初始化方法使其成为一条连续可行路径，删除子代染色体中含有的重复节点。
6、改进变异算子
随机选择两个节点进行变异操作，操作步骤如下：
在需要进行变异的父代个体𝑊𝐹中随机抽取2 个节点𝑃𝑖、𝑃𝑗（不包括S 和G 点）作为变异点，将𝑊𝐹分成三条路径r1、r2 和r3；使用初始种群产生的方法生成两条路径，一条为从起点 S 到节点 𝑃𝑖的路径R1，一条为从节点 𝑃𝑗到目标点 G 的路径R2（要求R2 中不包括r1 和r2 的其它节点）；将R1、r2 和r3，r1、r2 和R2 组成两个新的个体，如果新组成的个体中有重复节点，则删除重复节点中间的路径以及一个重复节点，使新路径变得可行；计算两个新生成个体𝑊𝑁的适应度值，选出其中较优的个体作为子代，变异操作完成。
7、自适应策略
固定的交叉、变异概率将会使得遗传算法收敛速度变慢并且可能陷入局部最优，往往得到的搜索效果不是很好[19]。因此，针对上述问题本文采用一种自适应调整策略[20]，在交叉、变异前对
其概率进行自动调节。具体公式如下：
P c = { P c 1 − ( P c 1 − P c 2 ) ( Fit ′ − F i t a v g ) F a v g − F i t m i n , Fit ≤ Fit avg P c 1 , Fit ′ > Fit avg P_c=\left\{\begin{array}{c}P_{\mathrm{c} 1}-\frac{\left(P_{\mathrm{c} 1}-P_{\mathrm{c} 2}\right)\left(\text { Fit }^{\prime}-F i t_{\mathrm{avg}}\right)}{F_{\mathrm{avg}}-F i t_{\mathrm{min}}}, \quad \text { Fit } \leq \text { Fit }_{\text {avg }} \\ P_{\mathrm{c} 1}, \text { Fit }^{\prime}>\text { Fit }_{\text {avg }}\end{array}\right. Pc={Pc1−Favg−Fitmin(Pc1−Pc2)(Fit′−Fitavg),Fit≤FitavgPc1,Fit′>Fitavg
P m = { P m 1 − ( P m 1 − P m 2 ) ( F i t ∗ − F i t min ) F i t a v g − F i t min , F i t ∗ ≤ F i t avg P m 1 , F i t ∗ > F i t avg P_m=\left\{\begin{array}{c}P_{\mathrm{m} 1}-\frac{\left(P_{\mathrm{m} 1}-P_{\mathrm{m} 2}\right)\left(F i t^*-F i t_{\min }\right)}{F i t_{\mathrm{avg}}-F i t_{\min }}, \quad F i t^* \leq F i t_{\text {avg }} \\ P_{\mathrm{m} 1}, \quad F i t^*>F i t_{\text {avg }}\end{array}\right. Pm={Pm1−Fitavg−Fitmin(Pm1−Pm2)(Fit∗−Fitmin),Fit∗≤FitavgPm1,Fit∗>Fitavg
式中：𝐹𝑖𝑡min为群体中最小的适应度值，𝐹𝑖𝑡avg为每代群体的平均适应度值，𝐹𝑖𝑡’为交叉的两个个体中较小的适应度值，𝐹𝑖𝑡∗为要变异的个体的适应度值。
5、路径规划结果
不同栅格图像在算法迭代50次后的模拟路径
参考文献
1、牛秦玉，李博．基于模拟退火遗传算法的全向AGV路径规划[J/OL]．计算机集成制造系统.
