基于群体智能和自适应评价的群体编队仿真方法

摘要

本发明公开了一种基于群体智能与自适应评价的群体编队仿真方法；步骤一：在绘图面板中输入待编队的二维图形、图案；步骤二：分析图形或图案，提取边界及内部像素点并保存；步骤三：根据步骤二中保存的像素点，在三维环境中重绘图形；步骤四：根据编队分布密度，对三维图形或图案进行隔行交叉采样，生成图形边界站位点；步骤五：根据群体自适应度函数，人群中的个体自适应的选择目标站位点；步骤六：群体根据人工蜂群算法规划路线，生成到达目标站位点的无碰撞最优路径。本发明利用群体仿真的方式进行自由式编队的组建和控制，该方法不仅提高了编队组建的效率，而且具有较好的智能性和约束性，为动漫创作、团体操编排提供了有效的支撑平台。

说明书

技术领域

本发明涉及一种群体编队仿真方法，尤其涉及一种基于群体智能和自适应评价的群体编 队仿真方法。

背景技术

编队约束及控制广泛存在于群体仿真、计算机动画和机器人协同作业中，如大型团体操 汇演、战役实施对抗模拟等。传统的编队生成方式需要手动设定个体的目标位置，精确性和 可控性有限。在大型团体操汇演，战役实施对抗模拟时，需要有几千人几万人参加，由于受 到场地限制和人员太多不能直接进行编队操作，若要进行现场编队，浪费人力，效率很低。 发明内容

本发明的目的就是为了解决上述问题，提供一种基于群体智能和自适应评价的群体编队 仿真方法，它具有利用可视化系统对编队组建及运动过程进行仿真模拟，为大型团体编排与 设计提供了可视化及支撑工具的优点。

为了实现上述目的，本发明采用如下技术方案：

一种基于群体智能和自适应评价的群体编队方法，具体步骤为：

步骤一：在绘图面板中输入待编队的二维图形、图案；

步骤二：分析图形或图案，提取边界及内部像素点并保存；

步骤三：根据步骤二中保存的像素点，在三维环境中重绘图形；

步骤四：根据编队分布密度，对三维图形或图案进行隔行交叉采样，生成图形边界站位 点；

步骤五：根据群体自适应度函数，人群中的个体自适应的选择目标站位点；

步骤六：群体根据人工蜂群算法规划路线，生成到达目标站位点的无碰撞最优路径。

所述步骤四的具体步骤为：

（4-1）根据编队分布密度，沿Y轴方向进行采样，生成图形边界站位点；

（4-2）根据编队分布密度，沿X轴方向进行采样，生成图形内部站位点；

（4-3）根据公式（1）调整生成的站位点，防止在采样过程中忽略标识图形外观的拐点；

其中，Pos_ij为第i个站位点的第j维坐标，I_kj为第k个拐点的第j维坐标，d为空间维数， ave_distance为空间密度，I_n为拐点个数。

所述步骤五中的自适应度函数为：

${\mathrm{goalpos}}_{\mathrm{ik}}=c_1*\sqrt{\underset{j=1}{\overset{d}{\Sigma }}{({\mathrm{Pos}}_{\mathrm{ij}}-{\mathrm{center}}_j)}^2}+c_2*\sqrt{\underset{j=1}{\overset{d}{\Sigma }}{(x_{\mathrm{ij}}-{\mathrm{Pos}}_{\mathrm{ij}})}^2}+c_3*\mathrm{count}\left[k\right]$

goalpos_i＝mingoalpos_ik，

其中，goalpos_ik为第k个站位点相对于个体i的适应度值，center_j为中心点的第j维坐标， count[k]为第k个站位点所属圆环区域t_k内部被占用的站位点数，goalpos_i为个体i的目标位 置，c₁,c₂,c₃为权重系数。

所述步骤六的具体步骤为：

（6-1）初始化群体规模、迭代次数、解集参数，初始化个体的候选解集 R＝{B,s₁,s₂……s_n,E}，其中B为初始点，E为目标站位点，s_i为个体所经历的路径上的第i个 候选解；

（6-2）根据适应度函数对候选解进行适应度进行评价，

$D=\underset{i=0}{\overset{n}{\Sigma }}\sqrt{{\left(\frac{\left|\mathrm{BE}\right|}{n+1}\right)}^2+{(S_{i,y}-S_{i+1,y})}^2},$

其中s₀＝B,s_n+1＝E，n为自然数，s_i,y指的是第i个个体的第y维坐标，s_i+1,y指的是第i+1 个个体的第y维坐标；

（6-3）按适应度值对候选解进行优劣排序，并选取前50%构造引领矩阵；

（6-4）角色转换，跟随蜂设定跟随目标；

（6-5）候选解根据角色进行位置更新；

（6-6）若满足迭代条件返回步骤2，否则退出算法。

所述步骤（6-4）中，跟随蜂采用轮盘赌的方式设定跟随目标，跟随概率公式为：

$P_{S_i}=\frac{{\mathrm{fit}}_{S_i}}{\underset{i=1}{\overset{\mathrm{en}}{\Sigma }}{\mathrm{fit}}_{S_i}}$

其中，表示第S_i个粒子被选择的概率；表示第S_i个粒子的适应度值；en表示引领 粒子个数，i∈{1,2,……,en}。

所述步骤（6-5）中引领蜂位置更新公式为：

S_ij＝S_ij+rand(-1,1)*(S_kj-S_ij)，k∈(1,2,3……en)随机生成且k≠i。

基于人工蜂群算法的原理和流程，实现了群体自适应站位点选择及路径规划。编队设计 人员通过系统提供的交互接口进行图形、参数输入，从而实现对目标编队的组建与控制。在 编队设计过程中，三维重绘实现了二维图案到三维场景的转换，交叉采样生成了分布均匀的 站位点，自适应匹配对群体目标设定进行了有效优化，路径规划保证了群体运动的智能性与 精确性。通过上述过程，最终生成符合用户输入的编队方案。

本发明的有益效果：本发明能够对群体编队进行组建和控制，通过可视化的系统仿真界 面对自由式编队过程进行群体仿真，具有较好的交互性、自适应性和智能性。通过本方法， 可以生成分布均匀、站位精准、移动有序的编队模型。

附图说明

图1是本发明编队控制流程图；

图2（a）是待输入的二维字符；

图2（b）是三维重绘后的字符；

图3（a）是对字符交叉采样生成的站位点集；

图3（b）是对采样点进行调整后的站位点集；

图4是用于实现自适应评价的同心圆模型。

图5（a）是编队图案和人群分别在广场中心及入口进行初始化；

图5（b）是人群在编队组建过程中的运动截图；

图5（c）是最终形成的编队方案（前视图）；

图5（d）是最终形成的编队方案（俯视图）；

具体实施方式

下面结合附图与实施例对本发明作进一步说明。

本方法的理论基础取自于生物进化科学、计算机科学及设计方法的交叉学科，其主要 算法借鉴进化计算领域的群体智能算法；其实现依赖于计算机科学的计算模型、可视化及虚 拟现实技术，其最终服务对象是信息时代的编队设计人员。

基于群体智能及自适应评价的群体编队仿真方法主要包括以下几个过程：

过程1：图形（图案）的绘制与导入；

过程2：图形（图案）分析与数据捕捉；

过程3：编队仿真环境的搭建；

过程4：自适应匹配及群体运动；

过程5：数据导出。

通过本方法，借助相应的支撑平台，最终可以生成符合用户输入的编队模型；以下详细介 绍本方法的几个过程；

过程1：图形（图案）的绘制与导入

选择相应的平台，可以绘制二维或三维图形（图案），对绘制的图形（图案）进行移动、旋转、 编辑等；

第一步：在Windows画图程序中绘制二维图形（图案），如图2(a)所示，或在ACIS/HOOPS 环境下绘制三维图形；

第二步：将二维图形（图案）通过绘图面板中的“图片载入”导入本系统中，进行二值化 处理。

过程2：图形（图案）分析与数据捕捉

该过程自动对导入的图形（图案）进行分析，识别图形（图案）中的边界像素及内部像素 点，并对数据进行保存。

过程3：编队仿真环境的搭建

该过程以ACIS/HOOPS环境为平台，搭建基本的编队组建环境；

第一步：对导入的外部二维图形（图案）进行三维重绘，生成待组建的三维编队轮廓，如 图2（a）、图2（b）所示；

第二步：根据用户设定的密度方案对三维图形（图案）进行隔行交叉采样，沿Y轴采样生 成边界站位点，沿X轴采样生成内部站位点，依据公式1对站位点进行调整、拟合，如图3(a)、 图3（b）所示；

${\mathrm{Pos}}_{\mathrm{ij}}=\left(\begin{array}{cc}{I}_{\mathrm{kj}}& \sqrt{\underset{j=1}{\overset{d}{\Sigma }}{({\mathrm{Pos}}_{\mathrm{ij}}-I_{\mathrm{kj}})}^2}\le \frac{\mathrm{ave}\_\mathrm{dis}\tan \mathrm{ce}}{2},0\le k<I_n\\ {\mathrm{Pos}}_{\mathrm{ij}}& \mathrm{otherwise}\end{array}\right)---\left(1\right)$

其中Pos_ij为第i个站位点的第j维坐标，I_kj为第k个拐点的第j维坐标，d为空间维数， ave_distance为空间密度，I_n为拐点个数。

第三步：将生成的站位点数显示出来；

第四步：根据站位点数初始化群体规模，根据公式（2）初始化个体位置；

S_ij＝S_i,min+rand(0,1)*(S_i,max-S_i,min)  （2）

其中，S_ij为第i个个体的第j维坐标，S_i,max和S_i,min为群体初始化区间的的上下限，rand(0,1)为 0、1之间的随机浮点数。

过程4：自适应匹配及群体运动

群体自适应的选择目标站位点，通过人工蜂群算法进行路径规划，生成到达目标站位点的 无碰撞最优路径；

第一步：群体依据公式（3）进行目标站位点的选择，如图4所示；

${\mathrm{goalpos}}_{\mathrm{ik}}=c_1*\sqrt{\underset{j=1}{\overset{d}{\Sigma }}{({\mathrm{Pos}}_{\mathrm{ij}}-{\mathrm{center}}_j)}^2}+c_2*\sqrt{\underset{j=1}{\overset{d}{\Sigma }}{(x_{\mathrm{ij}}-{\mathrm{Pos}}_{\mathrm{ij}})}^2}+c_3*\mathrm{count}\left[k\right]---\left(3\right)$

goalpos_i＝mingoalpos_ik

其中goalpos_ik为第k个站位点相对于个体i的适应度值，center_j为中心点的第j维坐标， count[k]为第k个站位点所属圆环区域t_k内部被占用的站位点数，goalpos_i为个体i的目标位 置，c₁,c₂,c₃为权重系数。

在该方法中，借鉴了城市规划中的同心圆模型，基于图形（图案）的中心及密度方案构 建同心圆集合。同心圆圆环内部的个体数反映了当前时间该区域内部的群体拥挤程度，群体 拥挤程度越高，内部站位点的适应度值越低。在设定目标站位点时综合考虑了距离、可达性 以及分布均衡性等因素，使得个体能够在全局范围内选择最优的站位点作为目标，具有较好 的自适应性和智能性。

第二步：群体基于人工蜂群算法进行路径规划，生成到达目标站位点的最优路径；

①初始化路径点集R＝{B,s₁,s₂……s_n,E}，其中B为初始位置，E为目标点，s_i为经历的第i个 位置，B、E和s_i均不处于障碍物覆盖范围。

②为降低路径规划的计算复杂性，对原始坐标系(XOY)进行转换，以BE所在连线为X轴、垂 直于BE向上方向为Y轴建立新的坐标系(X’BY’)。通过公式（4）进行坐标转换；

$\left(\begin{array}{c}x\prime \\ y\prime \end{array}\right)=\left(\begin{array}{cc}\cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)+\left(\begin{array}{c}{x}_B\\ y_B\end{array}\right)---\left(4\right)$

其中(x',y')为新坐标，(x,y)为原始坐标，α为BX’与OX的夹角，(x_B,y_B)为B点的原始坐 标。

③设定路径规划的适应度函数为$D=\underset{i=0}{\overset{n}{\Sigma }}\sqrt{{\left(\frac{\left|\mathrm{BE}\right|}{n+1}\right)}^2+{(S_{i,y}-S_{i+1,y})}^2},$其中s₀＝B,s_n+1＝E。路径规划 最终转化为将D最小化的问题。

④依据③中的适应度值函数对所有个体进行适应度值评价；

⑤按适应度值进行优劣排序，并选择前50%的个体构造引领矩阵；

⑥跟随个体基于轮盘赌的方式设定跟随目标，概率计算公式如公式（5）；

⑦$P_{S_i}=\frac{{\mathrm{fit}}_{S_i}}{\underset{i=1}{\overset{\mathrm{en}}{\Sigma }}{\mathrm{fit}}_{S_i}}---\left(5\right)$

其中表示第S_i个粒子被选择的概率；表示第S_i个粒子的适应度值；en表示引领粒子 个数。

⑧引领个体依据公式（6）进行位置更新；

S_ij＝S_ij+rand(-1,1)*(S_kj-S_ij)  （6）

其中，k∈(1,2,3……en)随机生成且k≠i。位置更新采用贪婪准则，如果计算后的位置适应度 值优于当前值，则进行位置更新，否则重新计算。

通过该过程的反复迭代运行，最终生成到达目标站位点的无碰撞最优路径。路径规划的 过程由设计系统自动完成，不需要设计人员的手动调整，提高了编队组建的效率和数据精度。

过程5：数据导出，导出场景及路径数据，导入Maya等三维动画创作软件中，生成高 质量可视化的群体编队组建方案。

图5（a）是将场景及人群数据导入Maya中所构建的基本场景，在广场中心生成了待编 队的“中国”字样，人群在广场入口进行初始化；图5（b）是人群移动过程中的截图；图5 （c）是最终的编队方案（侧视图）；图5（d）是最终的编队方案（俯视图）。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限 制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付 出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。