基于模拟退火和改进遗传算法的无人机风电检测动态路径最优规划模型

林阳芷，董佳琦，秦李朝政

（长沙理工大学，湖南 长沙 410114）

0 引 言

风电产业作为清洁能源的先行者，已经成为推动能源转型发展的中坚力量。由于风电运作需要大风场，因此风电叶片在运转过程中要承受很大的拉应力、风的冲击力及叶片震动带来的剪切应力，在沙漠地区还会不断受到风沙侵袭，-30℃至50 ℃的循环温差，以及强紫外光的老化等。在这些因素影响下，风电叶片很容易受到损坏，如不能及时检测出受损位置并加以维护，将会降低发电机性能、影响机组寿命、造成经济损失，严重甚至将引发安全事故从而会影响整个风电系统的运作。而现行风叶运维仍多以人巡为主，需要大量人工且效率低；无人机风电巡检控制存在诸多不稳定因素，极易发生“撞塔”事故；风电叶片检测系统亟待优化，因此，以无人机为主的高效、安全、智能一体化风电运维方案具有极大现实意义。

但是现行关于风电场无人机系统研究善处于初级阶段，关于风电场系统中无人机动态路径规划相关研究内容少之又少。近年来，在关于无人机路径规划研究中，周永涛、刘唐等以最大吞吐量为目标，计算每个时隙无人机飞行动作，实现单路径规划，但是忽视了多无人机场景下无人机总体最优布局。孙雪莹、易军凯针对传统路径规划算法不足，采用了粒子群混合算法，进一步提高计算速度与求解最短路径质量，但仍适用于单台无人机三维路径规划。现行研究多集中于单无人机场景下路径最优，多无人机场景下路径规划模型少之又少。

本文针对单无人机模型运行场景，首先引入模拟退火算法（Simulated Annealing, SA），定义节点的实对称矩阵D，以检测无人机经过节点的路径长度为目标函数，通过2变换法和代价函数差求解得出最短距离。后通过遗传算法校正分析，优化模型。为了使得模型适配多台无人机场景下检测情况路径最优规划。本文以同时派出四个检测无人机为例进行模型建立，我们引入优化遗传算法（Genetic Algorithm,GA）提出了一种起点可寻优的多旅行商问题模型，设计一种编码方式，在算法过程中对配送中心位置进行寻优，确定目标函数，从而求解得出四个检测无人机的最优充电路径。经仿真测试，本文所用模型方法可以较简单快速适配多无人机检测风电情况。

1 问题描述与假设

风电叶片智能运维对提升风电机组性能、减少风电机组安全事故具有重要意义。风电场系统中包括若干风电机组群（Wind turbine generator system）、一个数据中心（Data Center）、一个或多个具有缺陷检测功能无人机（Unmanned aerial vehicle （UAV）），是一种分布式网络。数据中心和若干风力发电机分布在一个随意设置的二维空间，无人机从数据中心出发，以固定速度依次经过风电机，在每台风电机处停留一段时间并以固定速率进行叶片检测，直到所有风电机叶片完成内外缺陷检测完成之后返回数据中心，所探讨具体问题假设如下：

（1）由于无人机飞行距离远大于无人机的长度、宽度以及风电机和数据中心的体积所造成距离偏差，所以无人机、风电机、数据中心类物理中的质点处理。

（2）假定无人机飞行距离为最小直线距离，忽略由于地形、道路影响所造成的飞行距离偏差。

（3）假定无人机在数据中心已充满足够电量，其电量可供所经过的风电机检测所需。

2 单个无人机最小能量损耗的充电路线

2.1 每台风电机之间的位置

将所给每台风电机的经纬度数据导入到MATLAB中，通过数据分析处理得到每台风电机与数据中心的位置关系图，如图1所示（其中，十字点为数据中心，星号点为风电机位置）。

图1 风电机与数据中心的位置关系图

2.2 每台风电机与数据中心的距离求解

2.2.1 地理坐标的换算

根据所给每台风电机节点的经纬度地理坐标，依据问题假设，将风电机看作质点，因为无人机飞行过程中，多在两点之间直接移动，求解检测路线最优规划时，首先需计算各点之间的最小实际距离。假设两质点为A与B，两者的地理坐标分别为（x，y），（x，y），则A，B两质点之间实际距离即为大圆的劣弧长长度。以地心为坐标O，以赤道平面为XOY平面，以0度经线圈所在的平面为XOZ平面建立三维直角坐标系。则A，B两点的直角坐标分别为

式中：R=6 370 km为地球半径。

A，B两点的实际距离：

化简可得任意两点距离计算公式为：

2.2.2 建立距离矩阵

假设风电场系统中数据中心为编号1，目标风电机依次编号为2，3，…，30，最后数据中心再重复编号31。距离矩阵D=（d），其中d表示i，j两点的距离，i，j=1，2，…，31，这里D为是对称矩阵。

2.3 模拟退火算法模型建立

根据模拟退火算法原理的阐述，得以模拟退火算法具体求解流程如下：

2.3.1 解空间

设定解空间S可表示为{1，2，…，31}，所有固定起点和终点正如上文建立距离矩阵，依次编号并进行排列集合，初始点循环，即：

其中：每一个循环排列表示检测无人机对29台风电机检测的一个回路，π=j为在第i-1次检测目标风电机j，初始解可选择为（1，2，…，31）。

2.3.2 目标函数

以距离矩阵为自变量，无人机检测所有风电机检测的最小路径规划长度为因变量建立对应目标函数。要求依次迭代，具体由下列三步构成。

2.3.3 新解的产生

设第一步迭代的解为：

进行2变换，任选序号u，v，交换u与v之间的顺序，变成逆序，此时的新路径为：

2.3.4 代价函数差

对于2变换法，路径差可表示为：

2.3.5 接受准则

如式（9）所示，若Δf＜0，则说明所求得新解小于原解，新解为更优路径，则接受新的路径；若Δf＞0，则以概率e极低概率接受新的路径。可理解为通过加入rand函数，系统自动产生一个[0，1]区间上均匀分布的随机数，若所产生rand函数值满足rand≤e不等式，则接受新路径。

2.3.6 降温

利用选定的降温系数α进行降温，取新的温度T为αT，这里的T为上一步迭代的温度，这里选定α=0.999。

2.3.7 结束条件

判断退火过程是否结束，通过选定指定终止温度e进行判断，本文假设e=3。若T＜e，满足所给降温条件，则直接输出当前状态。

2.4 模型求解结果

首先将1个数据中心和29个风电机位置的经纬度坐标数据导入到MATLAB中，利用经纬度距离公式，导出距离矩阵，后代入原先所编写好的模拟退火算法程序。无人机运动路径（path）、运动路径长度（long）、选定终止温度（e）、循环次数（ℒ）、降温系数（α）等参数默认与坐标距离求解程序参数相同，程序循环10 000次，取相对最优解。

MATLAB的运行结果为：

path：

0 -＞ 1 -＞ 2 -＞ 20-＞9-＞ 8 -＞ 12 -＞ 10 -＞ 13-＞ 16-＞ 27-＞15-＞ 14 -＞ 11-＞ 6-＞ 7-＞ 18 -＞ 25 -＞ 26 -＞ 29 -＞ 19 -＞ 17 -＞ 21 -＞23 -＞24-＞ 28 -＞ 22 -＞ 4 -＞ 3-＞5 -＞0 （0表示数据中心，其他数字表示风电机数字）

long：12.2552km

具体如图2所示（其中，十字为数据中心，星号为风电机）。

图2 检测无人机实际距离最优化路程规划图

检测无人机移动的实际最小距离为12.255 2 km，由于正时针走向与逆时针走向总路程不变，因此无人机最小化能量消耗的具体行程有顺逆时针两种走法：

逆时针走法：数据中心→风电机1→风电机2→风电机20→风电机9→风电机8→风电机12→风电机10→风电机13→风电机16→风电机27→风电机15→风电机14→风电机11→风电机6→风电机7→风电机18→风电机25→风电机26→风电机29→风电机19→风电机17→风电机21→风电机23→风电机24→风电机28→风电机22→风电机4→风电机3→风电机5→数据中心（顺时针即为反向）。

2.5 模拟退火模型的改进结果

模拟退火算法虽然具有局部搜索能力强、运行时间短的优点，但具有全局搜索能力差，容易受到参数的影响的缺点。为了使模型更加准确，采用遗传算法改进现有的模拟退火算法，以此得出检测无人机行驶最小距离最优值，改进结果如图3所示。

图3 检测无人机实际距离最优化路程规划图（遗传算法）

求解得，检测无人机移动的实际最小距离为11.481 5 km，同样由于顺时针走向与逆时针走向总路程不变，因此移动无人机最小化能量消耗的具体行程有顺逆时针两种走法：

顺时针走法：数据中心→风电机2→风电机1→风电机9→风电机7→风电机6→风电机14→风电机11→风电机8→风电机12→风电机15→风电机27→风电机16→风电机13→风电机10→风电机5→风电机3→风电机4→风电机22→风电机28→风电机24→风电机23→风电机21→风电机29→风电机26→风电机25→风电机18→风电机19→风电机20→风电机17→数据中心（逆时针即为反向）。

3 多个移动检测无人机情况下最优路程规划与风电机电池容量最优解（以四个为例）

3.1 遗传算法多旅行商模型建立

用遗传算法研究关于多个移动检测无人机情况下最优路程规划，可看作多旅行商问题模型建立。

本程序需具备的条件有：（1）每台检测无人机均从数据中心出发，最后需返回数据中心，且每台移动检测无人机行驶过程中不重复经过同台风电机节点。（2）除了第一个条件外，每台风电机节点有且只能被一台检测无人机检测一次。

所建立具体模型的参数设定如下：

检测无人机数=4；种群大小M=80；最大代数G=5 000；理想迭代次数（NUMITER）=10 000；交叉率p=1，交叉概率为1能保证种群的充分进化；变异率p=0.1，一般而言，变异发生的可能性较小，

根据所设经纬度数据，计算两个风电机节点距离需经纬度转化坐标可得。因此，根据单位经纬度长度公式得：纬度1°=111.194 km，纬度36°左右时经度1°= 89.469 km。导入所给各风电机节点经纬度数据成为坐标数据，后利用数据中心和29个风电机节点坐标数据，得到各个节点的距离。

3.1.1 编码策略

由于遗传算法主要原理为染色体交汇变异，在一般解空间表示中，大多采用二进制编码形式，但是由于本问题为多旅行商问题，该模型使用二进制编码方式不宜表示相应解，因此本模型所采用的遗传算法需要用特殊的修补算子来修复变化算子所产生的非法路径（即不可行路径）。根据上文所得数据中心与29个风电机编号，相应解用十进制数编码表示更加直观判断无人机最优路径，如上文数据中心编号为1，风电机1编号为2，风电机2编号为3……以此类推，风电机29编号为30。

遗传算法采用十进制编码，随机数列w，…，w作为染色体，其中0≤w≤10（i=2，3，…，30）；每个随机序列都和种群中的个体相对应。例如，目标3的一个染色体为：

[0.82，0.29，0.73，0.38，0.78，0.56，0.87，0.62，0.11]

式中：编码位置i为数据中心或风电机节点，位置i所对应染色体所产生随机数表示目标i在巡回中的顺序，将这些随机数按升序排列得到如下巡回：9-2-4-6-8-3-5-1-7

3.1.2 初始种群

采用经典改良圈算法可求得一个较优质初始种群，对于随机产生的四个初始圈：

交换u与v、w与x、y与z、a与b之间的顺序，此时四个无人机新路径为：

3.1.3 目标函数

函数因变量为4台无人机仅经过一台风电机情况最短路径长度，算法中适应度函数即为目标函数：

3.1.4 交叉操作

为了算法简便化，更快求出所需解，本算法采用单点交叉操作形式。设f和f为C的两个父代个体，其值假设为f=ww…w，f=w′w′…w′，随机地选取第t个基因处为交叉点，经过交叉运算后，所得到新式即为子代个体Z和Z，其中Z的基因由f的前t个基因和f的后31-t个基因构成，Z的基因由f的前t个基因和f的后31-t个基因构成，例如：

若交叉点为第4个基因处，则：

C，C，C的交叉操作同C，在交叉操作过程中，正是子代不断进化的过程，交换选择方式多样，为了能保证子代继承父代的优良特性，变异操作在交叉操作运行过程中也同样有所体现。

3.1.5 变异操作

3.1.6 选择操作

最终确定结果，即选择路径数值最小的解。从遗传算法层面来说，即在父代种群和子代种群变异过程中，通过不断筛选目标函数值最小的M个体进化到下一代，以此不断进行，变换与选择过程中同样需保证保存父代的优良特性。

具体流程图如图4所示。

图4 遗传算法多旅行商问题算法具体流程图

3.2 优化遗传算法求解结果

将每个风电机和数据中心节点的地理经纬度坐标代入MATLAB程序中，程序循环10 000次，取相对最优解。

MATLAB的运行结果为：

path：

C1：0 -＞ 1 -＞2-＞ 0

C2：0 -＞ 3 -＞ 28 -＞ 24 -＞23 -＞ 22 -＞ 21 -＞ 4 -＞ 0

C3：0 -＞5 -＞10-＞13-＞16-＞27 -＞ 15 -＞ 12 -＞8 -＞ 11 -＞ 14-＞6-＞7-＞9 -＞ 0

C4：0 -＞ 17 -＞ 19 -＞ 29 -＞ 26 -＞ 25 -＞ 18 -＞ 20 -＞ 0

（0表示数据中心，其他数字表示风电机数字）

Distance：

C1：0.9535 km

C2：3.4981 km

C3：4.7231 km

C4：4.0247 km

long：13.1994km

四台检测无人机移动的实际最小距离总和为13.199 4 km，充电具体路径如图5所示，由于正时针走向与逆时针走向总路程不变，因此检测无人机最小化能量消耗的具体行程有顺逆时针两种走法：

图5 四台检测无人机实际距离最优化路程规划图

逆时针走法：

C1：数据中心→风电机1→风电机2→数据中心；

C2：数据中心→风电机3→风电机28→风电机24→风电机23→风电机22→风电机21→风电机4→数据中心；

C3：数据中心→风电机5→风电机10→风电机13→风电机16→风电机27→风电机15→风电机12→风电机8→风电机11→风电机14→风电机6→风电机7→风电机9→数据中心；

C4：数据中心→风电机17→风电机19→风电机29→风电机26→风电机25→风电机18→风电机20→数据中心（顺时针即为反向）。

3.3 遗传算法模型结果的检验

为了测试得到相对优良的结果，并且考虑到增加局部搜索的能力，子代代数越大，变异的概率也相应有一定的增大。因此，我们对种群规模、迭代次数、交叉概率和突变概率做了相应的一些变化，测试了多组数据，如表1所示。

表1 多种参数条件下的充电路径路程

注：由于每次产生后代都是在随机概率情况下进行交叉和变异，在迭代次数固定情况下，以上最小总路程是经过多次试验后取得的最优解；在迭代饱和的情况下，以上最小总路程是以人为观察随迭代次数增加其不变的取值，最小总距离有一定的误差。

经过多次调整参数进行实验，当种群规模为80，迭代次数为2 000，交叉概率为0.65，突变概率为0.05时，检测路径的总路程最优解为13.199 4 km。

4 结 论

本文构建了基于模拟退火和改进遗传算法无人机风电检测最优路径模型，很好解决了检测无人机最小化路线规划问题，具有一定合理性，模型具体优缺点如下：

（1）建立的模型能与实际紧密联系，结合实际情况对所提出的问题求解，通过修改程序参数，理论上其实可以使用任何正常数量的检测无人机和正常数量的风电机之间的最优路线规划，模型具有通用性，推广性较强。

（2）本文采用了模拟退火算法与遗传算法，选用了机器算法，算法新颖，考虑相对全面，仿真结果合理性较强，模型所得结果可信度高。

（3）该模型对于数据分布及样本量限制小，既可以用于小规模样本，亦可以用于大规模样本，较为灵活、方便。

（4）但该模型运算过程较麻烦，运算时间耗费较长，程序运行时间耗时长。

（5）模型还存在一定的随机性，需要不断尝试最后选取最优解。除此之外，程序在搜索过程中，多采取全局搜索和局部搜索方式，没有进行完整搜索。

（6）现实生活中，需要考虑较为复杂的其他因素（例如：地形、无人机时速限制、运行路径、路障等），该模型较简单，未能对其进行全面考虑，造成与实际有不符之处。