基于性别猫群的主动式路径确定算法

林 涛，王鹏程，赵鹏飞

(河北工业大学 人工智能与数据科学学院, 天津 300401)

风能作为绿色可再生的新型清洁能源，是国家和社会能源结构中重要的组成部分.在2016年累积装机容量已经达到16873万千瓦时.由图1可以看出，风电场基本坐落于西北和华北地区，这些地区相对而言地广人稀非常适合风力发电，同时这里一般是山区、沿海等环境恶劣的地区.因此风电机组非常容易发生故障，这就对维修工作埋下了隐患.不仅维修成本高，技术难度也高，安全风险更高.

图1 2012～2016中国风能建设分布图Fig.1 2010～2016 China wind energy distribution figure

风力发电机组上各个组件的稳定运行是风机能够正常发电的前提条件[1].由图2可知各组件均有很高的几率发生故障.因此有必要研究新的方法去完善故障维修机制，以保证风场的正常运行以及控制成本.

图2 风电机组主要组件故障率分布图Fig.2 The failure rate distribution figure of wind turbine major components

1 研究现状

风力发电在电力供应方面有着不可忽略的贡献，风机巡检的研究对于其稳定运行有十分重要的意义.文献[2]以巡检时间最短为目标,提出基于整数规划的巡检策略.文献[3]提出不同种猫群优化算法并应用于分布式发电机组的配置和调整方面，取得了良好的效果.文献[4]使用无人机近距离巡检去替代传统的巡检，以避免观测精度低等缺点.文献[5]和文献[6]以粒子群算法为目标函数，对风电机组的状态健康进行监测和优化系统节点数目，提出3种节点部署方案并对所提出的方案进行了理论分析和实验仿真比较；结果表明部署方案均有效延长了监测系统的使用寿命，更加适用于海上风电机组的状态监测.文献[7]为了解决风电机组状态监测过程中因节点失效而产生的路由可靠性降低问题，提出了基于父节点及兄弟节点替代的节点路由修复算法.通过仿真分析可知：算法可显著提高风电机组状态监测的数据传输成功率.文献[8]针对已有风力发电机组在线监测系统布线复杂、工程成本高的问题，通过设计发电机组齿轮箱在线状态监测系统和应用无线传感网络ZigBee技术,实现对风力发电机组齿轮箱温度、加速度的在线采集和数据传送，从而省去传感器与上位机之间的大量布线，大大减少工程成本,为风力发电机组在线监测的广泛应用奠定技术基础.文献[9]针对海上气候环境恶劣、风电机组维护困难、故障率高等问题.分类并总结现有海上风电机组状态监控技术的相关研究, 探讨亟待解决的问题,指出今后的发展方向.文献[10]提出一种求解非线性优化调度问题算法，通过多通道动态规划优化粒子群算法并用于解决风力发电机组的巡径相关效率问题.文献[11]提出一种方法来优化基于状态的风机组件巡检策略，策略根据损坏的严重程度对组件进行降级；结果表明新的巡检策略保证了低故障时间，便于基于状态的巡检.文献[12]使用马尔可夫决策过程，建立了一个最佳的经济高效的风机维修策略.文献[13]将优化的猫群算法应用于车载自组织网络.为交通系统带来重大改进、增加了道路安全、减少了交通拥堵.文献[14]通过定性与定量方式结合优化猫群算法,最后验证猫群算法在进化过程中能够同时进行全局及局部搜索,且搜索速度具有很好的收敛性.文献[15]提出一种新的多目标猫群优化算法.该算法将一部分个体应用于搜索模式，将另一部分个体非随机地应用于跟踪模式；使得个体可以在最终的迭代过程中避免陷入局部最优，从而有效地提高算法的搜索能力.

上述文献中对猫群算法的应用和风机巡检策略进行了研究，有一定的积极意义，但是在研究过程中未对风机维修网络模型进行深入探讨；因此，本文对风电机组网络模型中的主动式维修网络模型进行详细分析，并提出一种优化算法用于解决这类模型.

2 主动式维修路径问题

2.1 主动式维修路径问题分析

主动式维修路径问题是指维修人员有多条维修路径可选.主动式模型按照交点数量可以细分为主动式多路不交叉模型、主动式多路不定点交叉模型.主动式多路不交叉模型如图3所示.在M区域中，有A、B两个风场，总中心准备单独安排维修人员分别维修，维修任务相互独立，互不干扰.该模型十分简单，这里不再赘述.其中A、B为两个风场，ai∈A，bi∈B,i∈{1，2，···，n}.

图3 主动式多路不交叉维修路径模型图Fig.3 Active multiple non-crossover maintenance path model diagram

其次是主动式多路不定点交叉模型.山上的风场环境恶劣，当地很少会有维修人员，一旦出现问题，维修人员必然从分中心去各个故障风场进行维修，这时候遇到的维修路径问题便属于该类网络模型.如图4所示：A区域有4台故障风机，B区域有8台故障风机，C区域有3台故障风机，AC之间不可直接到达，且AC区域各有一个维修点.如果维修队伍数目为2，每支队伍维修一台故障风机的平均时间均为T.按照区域划分有两种情况：第一种是将AB一起考虑，C单独考虑；第二种将A单独考虑，BC一起考虑.这两种情况明显是多路不交叉模型.在这两种情况中，任务的维修时间为分别为12T、11T，且在维修任务的后期会有一支维修队伍空闲，这说明任务分配不合适.为了追求更低的时间成本，就需要考虑共同维修B区域，则维修时间不超过7.5T，此时的维修时间明显低于前两种情况且B区域中两条维修路径的交点是不确定的.

图4 主动式多路不定点交叉模型图Fig.4 Active multiple indefinite point intersection model diagram

2.2 主动式多路不定点交叉问题模型

主动式多路不定点交叉问题的数学模型是由多路不交叉模型和多路单点交叉模型相互嵌套而成.数学模型具体如下：

A={aij|0≤i≤N，0≤j≤N}，

(1)

B={bij|0≤i≤C，0≤j≤C}，

(2)

D={dij|0≤i≤N-C，0≤j≤N-C}，

(3)

目标函数：

(4)

(5)

约束条件：aij>0，bij>0，N>C>0，dij>0.

其中distance为一条完整回路的长度，alt为起始点同时也是终止点.distancenew为无交点路径的长度，dlt为起始点同时也是终止点.aij是第i个节点与第j个节点之间的边的权值.N为节点个数.bij是分类后第i个节点与第j个节点之间的边的权值.C为重新分类后新节点个数.

3 增强型猫群算法

3.1 算法原理与工作过程

增强型猫群算法在优化过程中使用了模拟退火算法和粒子群算法.模拟退火算法是一种概率算法，该算法的关键是衰减，退火过程由冷却进度表决定.算法终止时得到的是近似最优解.粒子群算法是一种基于种群的随机优化计数算法，算法主张群体合作，个体学习其他个体和自身的经验，从而改变搜索模式.增强型猫群算法在起始阶段初始化一定数量的猫个体，使其行为属性与聚类中心相适应，自然也包含搜寻模式和跟踪模式；其中猫个体有K维空间，K就是聚类的个数，猫的适应度和模式标记决定了猫个体应处于什么模式之下.其适应度函数如下：

A={a1，a2…an}，

(6)

B={b1，b2…bn}，

(7)

(8)

(9)

新的搜索模式步骤为：

(1) 计算当前位置和适应值.

(2) 改变维度和对应维度上的速度，并随机地选择范围，依照下面的公式更新位置，获得新的位置bnew,计算新的适应值.

f(bnew)和Δf=f(bnew)-f(b)，

(10)

(11)

其中d=1，2，…，k；p任意；rand∈[0，1]，bpd是B在第P维上的第d个元素；SRD是维度的范围.

(3) 如果Δf<0，猫个体的当前位置为bnew，如果Δf>0，猫个体的当前位置为P=exp(-Δf/kT)，其中T是初始温度.

(4) 减小T.

(5) 重复第2步到第4步，重复次数为记忆池的长度.

跟踪模式下，位置更新公式为：

(12)

该算法的具体过程为：

(1) 初始化聚类数量K，迭代次数，种群大小N等基本参数；

(2) 初始化猫群，随机地将数据对象分给聚类，聚类中心依照规则迭代N次；

(3) 根据分组比例MR，将猫群随机地分成搜寻模式和跟踪模式；

(4) 对于每一个数据对象，根据猫个体的位置编码，通过最近邻域法分类；

(5) 更新所有猫个体的r，其中最小的r即为全局最优解；

(6) 如果迭代次数达到算法结束条件，则算法终止，否则跳转(4).

3.2 算法不足之处

增强型算法在算法过程上与基本算法非常类似，仅对猫群的一些参数和公式进行了改进.一定程度上缓解了猫群算法出现的弊端，但某些弊端依然存在且用于优化的遗传算法和粒子群算法本身也不是完美型算法.所以从某个角度来说：增强型算法拥有更好的性能，但是在其他方面是否更好还有待验证.增强型算法的不足之处主要有：

(1) 编码的规范和存在表示不准确；

(2) 单一的编码不能完全覆盖目标问题的所有约束；

(3) 模式切换过于频繁；

(4) 目前不存在有效的定量分析方法能够对算法的精确程度、计算复杂性、可行性进行评估.

4 基于性别猫群的主动式路径确定算法

4.1 优化算法原理与工作过程

本文提出了一种基于性别猫群的主动式路径确定算法(EGCSO-SEX).该算法主要有四个阶段.第一阶段是算法的起始阶段.主要任务是确定节点的选择方式、步长等，包含非约数原则.第二阶段是单次巡径完成阶段.参照了并行枚举算法，由于枚举算法易于实现，这里不再赘述.第三阶段是是文化交流阶段，也是改进算法的关键阶段，在这一阶段个体之间会相互交流并根据环境原则更新问题的最适应解.该阶段中个体的演变会遵循半数精英原则和环境原则.第四阶段是新个体产生阶段，主要利用了遗传算法的交叉变异原理.

半数精英原则是指在猫群进行一次交流完成后，猫群会自行统计某种文化的认可数量并降序排序，如果该文化的认可排名在一半以上，则增强该文化.环境原则：所有文化的认可度都会随着时间而缓慢下降，直至为0后去除该文化.猫文化的特异性是指由以前同样的猫文化改为能够唯一区分的特异性猫文化，文化变动在某个区间内单独变动，如初始文化为1，则在[0.5，1.5)之间变动.文化认可度公式如下：

cp(t+1)=kcp(t)+cp_e ，

(13)

其中cp(t)为t时刻某个个体文化的认可度，k为认可系数，范围是[0，1]，cp_e为基本文化认可度，一般为0.1.

在第四阶段中，遗传编码为8个比特编码：第零位和第一位表示性别，10和11代表雄性，01和00代表雌性；第二位表示该个体是否可以被继承；第三位和第四位表示该个体的遗传次数；第五位到第七位表示交流阶梯的编号；继承时，性别采用奇校验、偶校验中的一个，且雄雌采用的运算方式相互独立.下一代的性别编码中第零位由雄性决定，第一位由雌性决定.两种运算发生的概率分别为odd，even，两个概率满足以下条件：odd+even=1,0=

改进后的算法流程图如图5所示.

图5 基于性别猫群的主动式路径确定算法流程图Fig.5 The active determinate path algorithm flow chart based on sex cat swarm

4.2 实验结果及其分析

实验运行环境为：Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz，16GBRAM.测试结果如表1所示.

从表1可知：四个数据集的规模逐渐增加，与实际的区域性风场的规模更加接近.另外，在KROA100、GIL262、LIN318、PCB442四个数据集中，改进后算法的最优值都比PSO与ACO要好很多，说明改进后的算法具备处理主动式不定点交叉维修路径问题的能力.

表1 测试结果

PSO，ACO，EGCSO-SEX部分实验对比结果如图6和图7所示.

图6 最优解时间图Fig.6 Optimal solution time figure

从图6可知：改进后的算法在性能上有大幅度地提升，在计算时间上，改进后的算法所需要的时间相对稳定且明显低于PSO和ACO.说明改进后的算法能够用于降低维修路径问题的确定时间，进而提高了风场维修任务的效率.

图7 最优解频率图Fig.7 Optimal solution frequency diagram

从图7可知：在本文的EGCSO-SEX算法和PSO，ACO相比较时，计算出最佳解的频率普遍高于PSO和ACO.这就意味着在实际应用过程中，特定时间内改进的算法能够提供多条较为合适的路径以便维修人员使用.改进后的算法得出最佳解的可能性更大，能够增加风场维修任务的并行度.

5 结语

本文提出一种基于性别猫群的主动式路径确定算法，将问题中的模型切换机制和猫群算法中的模式切换相融合;充分利用猫群算法独有的优势并在多个阶段使用新的原则，进一步地提高猫群算法的搜索广度、收敛性以及计算效率.通过实验对比证明改进的算法有更好地性能去解决主动式多路不交叉模型中的维修路径确定问题.在风场网络的实际应用中取得了很好的表现.