基于竞争蛙跳算法的军事训练计划智能优化

刘昊; 董宁宇; 邢岩

doi:10.3969/j.issn.1673-3819.2020.05.022

指挥控制与仿真 >

2020 , Vol. 42 >Issue 5: 112 - 117

DOI: https://doi.org/10.3969/j.issn.1673-3819.2020.05.022

工程实践

基于竞争蛙跳算法的军事训练计划智能优化

刘昊 ¹ ,
董宁宇 ² ,
邢岩 ³

展开

1.国防大学联合作战学院, 河北石家庄 050000
2.军委机关事务管理总局, 北京 100000
3.沈阳航空航天大学电子信息工程学院, 辽宁沈阳 111000

刘昊(1983—),男,辽宁辽阳人,博士研究生,研究方向为作战指挥。

董宁宇(1970—),女,硕士。

Copy editor: 张培培

收稿日期: 2019-10-14

要求修回日期: 2019-11-21

网络出版日期: 2022-05-07

版权

收起

Intelligent Optimization of Remnant Training Plan Based on Competitive Leapfrog Algorithm

LIU Hao ¹ ,
DONG Ning-yu ² ,
XING Yan ³

Expand

1. National Defense University Joint Operations College, Shijiazhuang 050000, China
2. General Administration of Military Affairs, Beijing 100000, China
3. School of Electronics and Information Engineering, Shenyang Aerospace University, Shenyang 111000, China

Received date: 2019-10-14

Request revised date: 2019-11-21

Online published: 2022-05-07

Copyright

Fold

摘要

针对军事训练中补差训练计划拟制和优化困难的问题,提出一种基于蛙跳算法的补差训练计划智能优化算法。该算法以标准蛙跳算法为基础,通过引入遗传算法“超级个体剔除”和“自然选择”的优胜劣汰竞争机制,实现算法自主删除冗余个体并有效进化的方法提升算法的全局寻优能力和收敛效率,并定义和构建了符合补差训练计划工程特点的评估指标数学模型,实现了基于熵权理想点法的补差训练计划综合评分,最终通过竞争蛙跳算法的多代推演获取全局最优解。仿真结果表明:竞争蛙跳算法较标准蛙跳算法具有更强的全局寻优能力和更快的收敛效率,能够有效解决补差训练计划的智能优化问题。

关键词： 补差训练计划; 熵权理想点法; 遗传算法; 蛙跳算法; 智能优化

本文引用格式

刘昊 , 董宁宇 , 邢岩 . 基于竞争蛙跳算法的军事训练计划智能优化[J]. 指挥控制与仿真, 2020 , 42(5) : 112 -117 . DOI: 10.3969/j.issn.1673-3819.2020.05.022

Abstract

Aiming at the difficulty in the formulation and optimization of the compensatory training program in military training, an intelligent optimization algorithm based on the leapfrog algorithm is proposed. Based on the standard leapfrog algorithm, the algorithm uses the "end-of-life" and "survival of the fittest" competition mechanism in genetic algorithm to improve the global optimization ability and convergence efficiency of the algorithm by detecting and deleting redundant individuals, and defines and constructs. The mathematical model of the evaluation index that meets the characteristics of the replenishment training program is built, realizes the comprehensive scoring of the replenishment training plan based on the entropy weight ideal point method, and finally obtains the global optimal solution through multi-generation deduction of the competitive leapfrog algorithm. The simulation results show that the competitive leapfrog algorithm has stronger global optimization ability and faster convergence efficiency than the standard leapfrog algorithm, and it can effectively solve the intelligent optimization problem of the replenishment training program.

Key words： replenishment training plan; entropy weight ideal point method; genetic algorithm; leapfrog algorithm; intelligent optimization

在军队日常训练阶段划分中,入伍训练和专业训练阶段之间通常由补差训练牵引衔接,为提升军队整体作战能力,针对性复训和补训成为弥补战斗力生成短板的有效手段,而补差训练计划的生成和优化就是制约军队战斗力生成的枢纽和瓶颈。补差训练计划拟制的难点在于对参训人员的科学合理分配,以达成训练场地、训练器材资源、组训者的综合利用率最优化,以确保在单位时间内最大限度提升单科目整体训练水平。补差训练计划的拟制和优化问题对算法的实现要求较高,传统基于规则的拟制方法存在生成计划占用资源较多、受训和指挥人员匹配难度大、补差科目选择不合理等诸多问题,如何选择合适的组训科目、如何匹配组训指挥员和受训人员、如何最优化训练资源等系列优化问题均可归结为经典的课表优化问题,而课表优化问题是典型的NP完全问题^[1],很难在给定时限内找到问题的全局最优解,因此,专家学者倾向于使用兴起于20世纪90年代的各种智能优化算法解决此类问题,为军事训练的补差训练计划拟制提供算法支撑。

补差训练计划中的仿真类智能优化算法在特定范围内的使用效果参差不齐,有必要分析各类智能优化算法的优缺点。当前的智能优化算法主要有模拟物理规律的模拟退火算法^[2]、细胞膜优化算法^[3]、量子进化算法^[4]、禁忌搜索算法^[5]等和模拟生物群体行为规则的萤火虫算法^[6]、蛙跳算法^[7] 鱼群算法^[8]、蚁群算法^[9]、蜂群算法^[10]、布谷鸟算法^[11]、粒子群算法^[12]、细菌觅食算法^[13]等,以及模拟物种适应性特征行为的遗传算法^[14]、贪心算法^[15]等。各种智能优化算法从各自仿生思维视角切入NP完全问题,共同点是利用伪随机数创造具有部分随机特征的智能体,通过对综合评分的比较控制个体的游走或演化方向,通过量化累加形成优化质变,以局部最优解趋近全局最优解。然而,上述算法也存在易陷入局部最优陷阱和收敛代数不可控的问题,基于此,国内外学者给出了诸多改进型智能优化算法,尝试解决上述问题。本文以蛙跳算法为参考标准,借鉴了遗传算法中的适者生存思想,在算法中设计“超级个体剔除”机制和“自然选择”机制,以此为基础设计竞争蛙跳算法,并引入补差训练计划优化实践项目中,取得了较好的优化效果。

1 问题描述

补差训练计划智能优化问题可描述为:如何在给定的训练科目、组训者和训练时间段限制条件下,为每个训练科目分配参训人员,以实现同等训练科目下对最薄弱人员的最佳针对性训练。为了满足计划的可操作性,还应设计硬约束条件:一是同一科目内不能有重复人员;二是训练时间段有重叠的科目内不能有重复人员;三是训练时间段有重叠的科目内不能有重复组训者。为了描述参训人员的各方面评估水平,定义评估指标如下:

1)平均分指标:反映补差训练计划中的参训人员在此前1个月内的该科目平均成绩水平,指标项分值越低,说明参与训练人员对应的训练科目越薄弱。

2)参训率指标:反映补差训练计划中的参训人员在此前1个月内的该科目参训次数占比水平,指标项分值越低,说明参与训练的人员对应训练科目参训次数越少。

3)优秀率指标:反映补差训练计划中的参训人员在此前1个月内的该科目考核优秀数占比水平,指标项分值越低,说明参与训练的人员对应训练科目优秀成绩次数越少。

4)同班率指标:反映补差训练计划中的参训人员来自同一单位所占比例水平,指标项分值越高,说明参与训练的人员来自同一单位的概率越高,人员分布越规整,训练组织难度越小。

5)疲劳度指标:反映补差训练计划中的参训人员参加训练结束后的疲劳程度,指标项分值越低,说明参与训练的人员执行补差训练后的参训次数越少,人员分配越合理。

基于上述定义,设组训者限定的训练科目集合为K,训练时间段集合为T,每组补差训练计划的参训人员分配集合为R;其中,第i个补差训练计划在向量空间位置为r_i,训练科目为k_i,训练时间段为t_i;p_i表示该计划的平均分指标,c_i表示该计划参训率指标,y_i表示优秀率指标,b_i表示同班率指标,d_i表示疲劳度指标。则第i个补差训练计划的综合评分f_i数学模型为

(1)

f_i(k_i,t_i,r_i)=F $p i (k i, t i, r i) min c i (k i, t i, r i) min y i (k i, t i, r i) min b i (k i, t i, r i) max d i (k i, t i, r i) min max$

式中,k_i∈K,t_i∈T,r_i∈R,F为综合评分集合,f_i∈F。

2 算法构建

智能优化算法的算法模块具备通用性,主要由参数录入、向量空间建立、综合评分和智能优化等部分组成,各部分之间紧密结合,用以实现具体工程实践问题的优化解决。参数录入模块由组训者在补差训练前手工确定训练科目、组训者和训练时间段等环境限制变量;向量空间建立部分在参训人员和训练科目基础上建立能够区分补差训练计划的空间向量,记为二维数组V(K,R);综合评分部分实现对空间向量中的对应位置v_i(k_i,r_i)综合评分计算,以评估该位置在空间中的重量;智能优化模块使用相关仿真类算法实现空间位置的特征随机游走,通过多方向试探找到特征在空间中的最佳点位。算法流程如图1。

显示原图|下载原图ZIP|生成PPT

图1 智能优化算法通用流程图

2.1 标准蛙跳算法

标准蛙跳算法模拟自然界蛙群的生活规律,蛙群被分割在各自独立的小池塘中,各池塘内的青蛙个体共享塘内资源,最差评分个体可通过蛙跳转移至周边高分位置,如蛙跳范围内无法找到高分位置,则判定青蛙死亡,引入新的青蛙个体;并模拟蛙群繁殖季节的聚集交配行为,定期将蛙群打乱重组,以防陷入局部最优。标准蛙跳算法流程图如图2所示。

显示原图|下载原图ZIP|生成PPT

图2 标准蛙跳算法流程图

设种群最高分个体为X_q,共分m组,第j组的最高分个体为X_b,最低分个体为X_w,s为[-1,1]之间的随机实数。计算X_w跳跃后位置X'_w 的蛙跳操作流程如下:

Step1:计算步长ΔX'_w。

(2)

ΔX'_w=s·(X_b-X_w)

Step2:计算跳跃后的X'_w。

(3)

X'_w=X_w+ΔX'_w

Step3:比较X_w和X'_w 的综合评分。若X_w<X'_w,则用X'_w 替换X_w,退出操作;否则,执行Step4。

Step4:用全局最优个体X_q替换公式(2)的X_b,执行Step12,求出X_w全局跳跃后产生的个体X'_wq。

Step5:比较X_w和X'_wq 的综合评分。若X_w<X'_wq,则用X'_wq 替换X_w,退出操作;否则,生成随机新个体X_s替换X_w。

2.2 竞争蛙跳算法

通过对标准蛙跳算法分析可知,其核心是通过蛙跳操作使低分个体向周边空间的高分位置跳跃,并通过定期拆分合并种群操作防止算法陷入局部最优,通过多代推演使最优个体综合评分逼近全局最优位置。但算法有两个智能优化算法的通用缺陷。一是易陷入局部最优陷阱。由于算法解决的问题属于复杂非线性不连贯问题,导致空间中的点位分布不连续,对于偶然出现的局部最优点位,算法会促使周边个体向该位置跳跃,进而陷入局部最优陷阱。二是迭代效率低问题。由于组内的蛙跳操作只针对最低分个体X_w执行,若X_w已经陷入低分区域而未达到删除程度,算法会对X_w频繁执行蛙跳操作,造成系统资源的浪费。基于此,本文设计了竞争蛙跳算法,其思想是将遗传算法中的超级个体剔除机制和自然选择机制引入标准蛙跳算法,为种群中的个体赋予自然寿命和淘汰系数,通过自然寿命实现超级个体剔除,以防超级个体破坏算法的全局寻优环境;通过合并种群后的淘汰系数判定,剔除对全局寻优毫无意义的冗余个体。如图3所示。寿命项存储青蛙经历过合并种群的次数;淘汰系数以个体在生命期内蛙跳操作次数为上限;个体位置的空间向量用二维整数数组存储。

显示原图|下载原图ZIP|生成PPT

图3 竞争蛙跳算法流程图

超级个体:个体的分值处于局部最优位置,且多代跳跃后依旧没有找到更好的位置,对周边的青蛙个体产生吸附效应。

冗余个体:个体所在的位置周边分值相对较低,对于算法的全局寻优无任何影响,其存在只会降低计算效率。

具体算法如下:

Step1:设置初始种群。按照随机算法产生初始个体,并控制变异概率产生数量规模为n的初始种群,其中每个个体均可对应空间向量的具体解。

Step2:寻找最优个体X_q。通过综合评分算法计算所有个体在空间中的综合评分结果,通过比较排序定位最优个体。

Step3:通过拆分操作将种群拆分为m个子群。具体操作为:首先,将所有个体按综合评分排序,然后按评分由高至低依次放入m个分组中,保证各组综合评分之和相差不大。

Step4:定位第j组中的最低评分个体X_w和最高评分个体X_b,X_b寿命+1。

Step5:随机产生最低评分个体X_w的蛙跳操作步长s,并按蛙跳操作更新位置为X'_w。

Step6:重复步骤4、5,直至j=m。

Step7:拆散各组合并为种群,更新综合评分,标记最高评分个体X_q,并输出最高分值。

Step8:计算所有个体的淘汰系数。

Step9:删除淘汰系数超过阈值的个体。

Step10:随机产生新个体补充种群,使种群数量n维持不变。

Step11:重复步骤210,引入结束条件判定:若最优个体X_q综合评分在10代内无提升,则退出。

2.3 综合评分算法

综合评分算法是智能优化算法和补差训练计划优化工程实际结合的建模算法,由于补差训练计划分值不连续、参训人员来源不同等特点,本文引入熵权理想点法作为多指标综合评分算法。

2.3.1 评估指标计算

按照问题描述阶段的定义,评估指标由平均分指标P、参训率指标C、优秀率指标Y、同班率指标B、疲劳度指标D组成。设训练计划数量为n,其中,第i个训练计划中共安排了z个训练科目,第e个考核科目中,受训人数为n_e;其中,第g个人在对应考核科目中的平均分为f_ge,共组织过h_ge次科目考核。则第g个人在科目e中的优秀率y_ge计算公式为

(4)

y_ge= $100 %; (max {f 1 e, f 2 e, … f ge} × 80 % ≥ f ge) 0 %; (max {f 1 e, f 2 e, … f ge} × 80 % < f ge)$

设参训率为c_ge,相应计算公式为

(5)

c_ge= $∑ g = 1 n e min {f ge, 100 %} n e$

设不考虑训练科目,该人的训练疲劳度指标q_g对应计算公式为

(6)

q_g= $∑ e = 1 z e h ge$ -h_ge

通过公式可知,疲劳度指标公式为指数增长指标,若h_ge的数量增大,则q_g对应增幅呈指数级增长,因此,在实际使用中每个人的训练次数不能过高,否则算法无法承受。该补差训练计划的平均分评估指标P计算公式为

(7)

P= $∑ g = 1 n e ∑ e = 1 z f ge g × e$

同班率评估指标B计算公式为

(8)

B= $∑ e = 1 z n e z$

优秀率评估指标Y计算公式为

(9)

Y= $∑ g = 1 n e ∑ e = 1 z y ge g × e$

疲劳度评估指标D计算公式为

(10)

D= $∑ g = 1 n e q g g × e$

参训率评估指标C计算公式为

(11)

C= $∑ g = 1 n e ∑ e = 1 z c ge g × e$

2.3.2 多指标评分算法

熵权重^[16]是热力学概念,若空间中的微粒混乱程度越大,则熵值越大,对应于指标评估中可理解为:样本评估指标间的偏差值越大,则熵权重越大,由此可将熵权重看作衡量评估指标包含信息量的参考标准。理想点法^[17]的计算原理为:将参评样本的评估指标看作空间特征向量,则可将样本对应于空间中的特定点位,取所有评估指标的最优值产生正理想点A⁺,取最差值产生负理想点A^-,各样本计算与A⁺和A^-之间的空间距离d⁺和d^-,由此求出样本i在多维空间中的评分值f_i。设n个补差训练计划参与评分,建立矩阵X_n₅ (1≤i≤n),评估指标数为5(P、B、Y、D、C)。具体算法为:

Step1:矩阵归一化。由于各评估指标的分值大小差异较大,因此,通过归一化将各评估指标简化为小于1的分布概率值,生成归一化矩阵U,其中,元素u_ij计算公式为

(12)

u_ij= $x ij ∑ i = 1 n x ij$

Step2:计算第j个评估指标的熵值q_j。

(13)

q_j=- $∑ i = 1 n u ij ln (u ij) ln (n)$

特殊情况,若u_ij=0,则规定q_j=0。

Step3:计算第j项评估指标的熵权重z_j。

(14)

z_j= $1 - q j 5 - ∑ j = 1 5 q j$

Step4:计算理想点空间向量。

(15)

$u j +$ =max(u₁_j,u₂_j,…u_nj)

(16)

$u j -$ =min(u₁_j,u₂_j,…u_nj)

Step5:计算理想点空间距离。

(17)

d i +

∑ j = 1 5 z j × (u ij - u j +) 2

(18)

d i -

∑ j = 1 5 z j × (u ij - u j -) 2

Step6:计算综合评分。

(19)

f_i= $d i - d i + + d i -$

3 仿真分析

仿真实验依托工程项目“军事训练成绩分析系统”中的相关训练模块检测竞争蛙跳算法应用于补差训练计划优化的有效性,通过将其融入补差训练模块,达成工程实践应用目的,并同标准智能优化算法比较,检查分析算法的优缺点。数据来源为北部战区某部队新兵营训练数据,选取新兵训练3个月11个组训科目的登记成绩录入系统形成初始训练数据;智能优化硬件性能为:Intel酷睿2.4 GHz处理器,4 G运行内存,Win7 32位操作系统,VC6.0编译环境;为了提升训练计划优化体验效果,设置进化代数上限为300代,淘汰系数为5,种群规模数为1000个,个体寿命上限为3代。系统模块的整体界面如图4所示。

显示原图|下载原图ZIP|生成PPT

图4 补差训练智能优化模块整体界面

3.1 算法收敛性分析

本文以熵权理想点法为多指标综合评分算法,设定退出条件为:最优个体综合评分在20代内无提升,以标准蛙跳算法为参照智能优化算法,对比分析两种算法收敛情况如图5所示。

显示原图|下载原图ZIP|生成PPT

图5 算法收敛情况分析

通过对比两种算法的各代最优个体分值统计评分情况,检查算法的收敛性,通过实验可知,两种算法均能在多代后实现缓慢收敛,但竞争蛙跳算法的收敛代数明显小于标准算法,并且收敛分值相对更高,且由于引入超级个体剔除机制,竞争蛙跳算法可自主跳出局部最优陷阱,向周边的位置主动寻优,全局寻优能力较标准蛙跳算法明显增强。

3.2 最优个体评估指标比较

为了判断两种智能优化算法形成最优个体的内部结构差异,取各自形成的最优个体,分析其各项评估指标的性能,比较结果如表1所示。

表1 各智能优化算法收敛代数统计表

算法名称	综合评分	平均分	参训率	优秀率	同班率	疲劳度
标准蛙跳算法	2.594	4.42	0.38	1.83	0.29	6
竞争蛙跳算法	2.707	4.3	0.33	1.72	0.33	6

实验结果表明:评估分值分别优化了2.71%、13.16%、6.01%、13.79%、0%。

3.3 完成收敛代数及耗时比较

两种智能优化算法完成收敛的代数及其耗时统计如表2所示。

表2 各智能优化算法收敛代数统计表

算法名称	达成收敛代数	收敛分值
竞争蛙跳算法	141	2.707
标准蛙跳算法	231	2.594

实验结果表明:竞争蛙跳算法的收敛代数更少,收敛总耗时和也比标准蛙跳算法更低,而且,在单代耗时上,竞争蛙跳算法并没有比标准蛙跳算法耗时更多,因此,竞争蛙跳算法兼具了收敛高效和时间高效双重特性,相比标准蛙跳算法具备更明显的优势。

4 结束语

本文借鉴了遗传算法的算法特征,将其融入蛙跳算法中,在算法设计中,自主设计了融入“自然选择”机制和“超级个体剔除”机制的竞争蛙跳算法,并在仿真实验中验证了其有效性。仿真实验验证了算法的有效性和工程实用性,解答了预设的问题描述。在工程实际项目中,引入了智能优化算法并实现了人机结合条件下的智能算法辅助应用,提升了组训者作业效率,降低了工作难度。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	S.Even, A.Itai, A.Shamir. On the Complexity of Timetabling and Multicommodity Flow Problems[J]. SIAM Journal of Computation, 1976(4):691-703.

[2]	何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 33(2):219-225.

[3]	张磊, 方洋旺, 柴栋. 基于改进量子进化算法的巡航导弹航路规划方法[J]. 兵工学报, 2014, 35(11):1280-1287.

[4]	李子杰, 刘湘伟. 基于进化算法的多无人机协同航路规划[J]. 火力与指挥控制, 2015, 40(2):85-89.

[5]	张滢, 杨任农, 左家亮. 改进分解进化算法求解动态火力分配多目标优化模型[J]. 兵工学报, 2015, 36(8):1533-1540.

[6]	YANG X S. Nature-Inspired Metaheuristic Algorithms[M]. Beckington, UK: Luniver Press, 2008: 81-96.

[7]	郭业才, 张苗青. 基于混合蛙跳算法的多模盲均衡算法[J]. 兵工学报, 2015, 36(7):1280-1287.

[8]	李君, 梁昔明. 人工鱼群算法收敛速度改进优化仿真[J]. 计算机仿真, 2018, 35(1):232-238.

[9]	王辉, 王景良, 朱龙彪. 基于改进蚁群算法的泊车系统路径规划[J]. 控制工程, 2018, 25(2):253-258.

[10]	王志刚, 尚旭东, 夏慧明. 多搜索策略协同进化的人工蜂群算法[J]. 控制与决策, 2018, 33(2):235-241.

[11]	YANG X S, Deb S. Cuckoo Search Via Levy Flights[C]. Proceeding of the World Congress on Nature&Biologically Inspired Computing, NaBIC 2009, Washington: IEEE Publications, 2009: 210-214.

[12]	J Kennendy, R C Eberhart. Particle Swarm Optimization[C]. Proceedings of IEEE International Conference on Neural Networks, Pisataway, 1995: 1942-1948.

[13]	Passino K M. Biomimicry of Bacterial Foraging for Distributed Optimization and Control[J]. IEEE Control Systems, 2012, 22(3):52-67. DOI

[14]	陈春良, 齐鸥, 魏兆磊. 基于蒙特卡洛仿真和遗传算法的车辆装备保障运输网络优化[J]. 兵工学报, 2016, 37(1):114-121.

[15]	李金夫, 度先国, 刘勇. 关于整车物流运输车辆路径优化设计的研究[J]. 计算机仿真, 2016, 33(4):184-188.

[16]	陈秀明, 刘业政. 基于熵权的多粒度犹豫模糊语言VIKOR群推荐方法[J]. 控制与决策, 2018, 33(1):111-118.

[17]	代文锋, 齐春泽. 异构多属性群决策的TOPSIS扩展方法[J]. 统计与决策, 2018, 13(4):20-24.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

1 问题描述

2 算法构建

图1 智能优化算法通用流程图

2.1 标准蛙跳算法

图2 标准蛙跳算法流程图

2.2 竞争蛙跳算法

图3 竞争蛙跳算法流程图

2.3 综合评分算法

3 仿真分析

图4 补差训练智能优化模块整体界面

3.1 算法收敛性分析

图5 算法收敛情况分析

3.2 最优个体评估指标比较

表1 各智能优化算法收敛代数统计表

3.3 完成收敛代数及耗时比较

表2 各智能优化算法收敛代数统计表

4 结束语

参考文献