一种基于基因编程的集群行为学习方法

摘要

本发明提供了一种基于基因编程的集群行为学习方法，利用基因编程方法，在没有先验知识的情况下，对解空间进行启发式搜索，并最终给出了能很好反映集群真实运动规则的邻居选择机制和行为决策函数，在当前普遍采用正向建模手段的趋势下，另辟蹊径采用反演的方式学习集群个体运动规则。本发明实现无先验知识条件下的集群行为规律学习，能够填补这一领域此类学习方法的空缺，不仅可用于无人集群行为的学习，也可用于对生物集群行为的研究。

说明书

技术领域

本发明涉及反演建模领域，尤其是集群行为反演方法，一种面向集群运动数据的个体行为模型反演任务。

背景技术

集群运动是一种普遍存在的自然现象，无论是鸟群集体飞翔还是鱼群的应激游动，抑或是微生物群落的迁移，都是集群运动的典型代表。当今时代也出现了越来越多的人造集群，比如机器人集群或是无人机群。这些集群的运动都体现出一种集群系统中的“涌现”现象。随着计算机技术，微电子技术等的发展，未来的群体协作必将成为新的趋势，集群系统具有，低成本，可替代，易扩展，效率高等诸多优势。

在无人化，智能化，集群化越来越成为当前主流趋势的前提下，对集群行为模型的学习必将是未来的重要课题。尤其是对非合作集群行为的学习，由于无法进行交流和协商，只能基于简单观测获取的运动数据进行学习，这对传统的正向建模方式是一个很大的挑战，因此数据驱动的反向建模方式是必然的选择。

近年来对于集群运动模型的正向建模方法研究已经取得了不错的成果，但反向的演化建模方法尚未出现什么突破。

发明内容

为了克服现有技术的不足，本发明提供一种基于基因编程的集群行为学习方法。基因编程本质上是一种演化算法，通过模仿自然界中生物种群优胜劣汰自然选择的过程实现对问题的优化求解。演化算法运行过程中会维护一个世代演化的种群，种群中的每个个体即问题的一个解。基因编程与传统的遗传算法的本质区别在于对遗传种群中个体的编码方式。遗传算法中种群个体染色体采用线性编码，而基因编程采用树状结构编码。本发明在不依赖先验知识的前提下，对观测数据进行学习，得出集群行为模型。

本发明解决其技术问题所采用的技术方案的步骤如下：

步骤1：集群运动数据获取；

使用视频处理与目标跟踪技术获取目标集群数据，或基于仿真利用已有集群模型生成集群运动数据，集群运动数据包括集群个体在任意时刻的位置、速度的状态信息；

步骤2：对种群进行编码；

对行为规则进行编码，采用的编码为嵌套结构的双层实数编码(区别于二进制编码)，对应集群个体运动规则的两个维度，两个维度分别为邻居选择和响应策略；一级编码对应个体行为的邻居选择模型，二级编码对应个体行为的邻居信息利用与处理模型，在两个层面上从无到有对集群个体的行为模型进行演化生成；所述邻居选择模型编码为邻居选择半径r，半径r内的个体被视为邻居，邻居的信息构成二级模型的输入；二级模型按树状结构编码，编码的内容经过解码即为集群个体基于感知信息进行响应决策的函数；图1为树状编码的示意图，解码后即为如下具有两个输入x，y的响应函数：

其中x，y根据使用者对其的定义而确定，解码方式只完成输入->输出之间关系的构建。例如确定x为某一邻居与自身相对距离的横坐标值，y为某一邻居与自身相对距离的纵坐标值；

步骤3：生成初始种群；

种群对应进化算法(基因编程)中的个体所组成的群体，而个体的遗传编码所代表的行为决策规则又是所优化的目标；即决策规则对应一群运动智能体的运动方式，运动智能体的集合称为集群；

一级种群的个体编码对应所代表的集群个体的邻居选择半径r，按均匀分布的随机概率进行初始化；一级种群的每个个体对应一个二级种群，二级种群中的个体编码为决策函数，采用随机采样发进行初始化；其中每个节点(节点即种群个体的染色体树状编码中的一个单元，例如图1中的x、+等)的基因从给定的函数集和变量集中选择；

步骤4：评估种群适应度；

首先，依据自身对演化算法的设计，给出个体适应度函数描述，适应度函数描述了使用者对集群个体的期望演化方向，例如期望集群保持聚集，则定义适应度为集群密度。

对每个一级种群中的个体所对应的二级种群进行若干次独立演化计算，取历次演化中的最小适应度作为个体的最终适应度(适应度针对一级个体而言，即包含完整集群个体决策规则的种群个体)；一级种群中的个体适应度评价规则如下：首先依据编码方式对个体进行解码，得到决策函数Γ，进而将指定的输入代入决策函数计算得出估计值，并和原始数据中的真实值对比计算误差作为个体适应度：

其中，θ

步骤5：选择优良个体；

从本代种群中选取m个优良个体；

步骤6：对个体进行交叉变异生成下一代种群；

一级种群中的个体，由于编码中只包含距离信息，故交叉变异操作合二为一，即以事先给定的变异概率p

步骤7：循环步骤4-6，直至触发终止条件，在演化过程中出现的最小适应度个体即为最优个体；

步骤8：对最优个体按照编码规则进行解码，得到对集群中个体运动规则的估计解。

所述选择优良个体的选取方法为：每次随机从种群中抽取k个个体，取其中适应度最小的个体，此为一次完整择优过程，重复此择优过程直到选够m个个体；

步骤6中，所述的交叉为对于A，B两个父个体分别随机选择一交叉点，然后将A个体交叉点之后的部分丢弃替换为B个体交叉点之后的部分，图2为交叉操作示意图。

所述变异为以相同的概率随机在现有的单点变异和子树变异方法之间选择。

所述单点变异为：在个体编码中随机选择变异点，对该点的编码进行随机变异，即将该点的基因编码替换为另一个与之类型相同的符号，具体来说：如果该点为函数，则替换为另一个自变量数与其相同的函数，如果该点为变量，则替换为另一个随机生成的变量。操作与遗传算法中的位翻转操作类似。

所述子树变异为：在个体编码中随机选择变异点，将该点之后的子树替换为随机生成的子树，图3为子树变异示意图。

所述终止条件为循环代数达到最大设定值或模型误差小于设定阈值。

所述p

所述p

所述p

本发明的有益效果在于利用基因编程方法，在没有先验知识的情况下，对解空间进行启发式搜索，并最终给出了能很好反映集群真实运动规则的邻居选择机制和行为决策函数，在当前普遍采用正向建模手段的趋势下，另辟蹊径采用反演的方式学习集群个体运动规则。

本发明为一种面向非合作集群运动数据基于基因编程的集群行为学习技术，可用于对未知集群运动规律的学习和反演，实现无先验知识条件下的集群行为规律学习，能够填补这一领域此类学习方法的空缺，本发明不仅可用于无人集群行为的学习，也可用于对生物集群行为的研究。

附图说明

图1为本发明交叉操作示意图。

图2为本发明单点变异示意图。

图3为本发明子树变异示意图。

图4为本发明某次演化实验的适应度变化曲线。

图5为本发明10次蒙特卡洛实验给出的邻居认定距离变化曲线。

具体实施方式

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

现结合实例、附图对本发明做进一步描述：

步骤1：为说明本发明的有效性，本实施例采用仿真手段生成集群运动数据并在此基础上对该集群运动规则进行反演。首先编写仿真程序，生成用于学习的集群运动原始数据。采用的集群运动模型为Vicsek模型的一种变体，该模型描述的种群中每个个体的运动速度大小恒定为v，个体在运动过程中只改变速度方向。任一个体，记为a

基于以上模型通过仿真程序对初始随机分布于一个500x500的虚拟仿真环境中对100个个体进行仿真。个体邻居判定范围为50，速度大小为3，仿真步长1/30s，噪声为在[-0.01,+0.01]范围内均匀分布的随机噪声。对模型仿真时长为1s，记录个体运动数据。

步骤2：对种群进行编码；

对行为规则进行编码，本发明采用的编码为嵌套结构的双层实数编码(区别于二进制编码)，对应集群个体运动规则的两个维度，邻居选择以及响应策略。一级编码对应个体行为的邻居选择模型，二级编码对应个体行为的邻居信息利用与处理模型，在两个层面上从无到有对集群个体的行为模型进行演化生成。邻居选择模型编码为邻居选择半径r，此半径内的其他个体被视为邻居，这些邻居的信息构成二级模型的输入。二级模型按树状结构编码，编码的内容经过解码即为集群个体基于感知信息进行响应决策的函数。

步骤3：生成初始种群

一级种群规模为100，进化代数为100。其个体编码为邻居选择半径r，通过均匀分布的随机数r～U(0,500)进行初始化。一级种群的每个个体对应一个二级种群，种群规模为100，进化代数100代。种群中的个体编码为决策函数，其中每个节点的基因从函数集和变量集中进行选择。具体函数集为{+,-,×,÷,sin,cos,tan,cot,sum,count,rand},变量集为{x,rand}其中x为[θ

其中p

步骤4：评估种群适应度

首先，依据自身对演化算法的设计，给出个体适应度函数描述，适应度函数描述了使用者对集群个体的期望演化方向，例如期望集群保持聚集，则定义适应度为集群密度。

对每个一级种群中的个体所对应的二级种群进行5次独立演化计算，取历次演化中的最小适应度作为个体的最终适应度(适应度针对一级个体而言，即包含完整集群个体决策规则的种群个体)。一级种群中的个体适应度评价规则如下：首先依据编码方式对个体进行解码得到决策函数Γ进而将指定的输入代入决策函数计算得出的估计值，并和原始数据中的真实值对比计算误差作为个体适应度

其中，θ

步骤5：选择优良个体

从本代种群中选30个优良个体。具体方法为每次随机从种群中抽取5个个体，取其中适应度最小的个体，此为一次完整择优过程，重复此择优过程直到选够30个个体。

步骤6：对个体进行交叉变异生成下一代种群

一级种群中的个体，由于编码中只包含距离信息，故交叉变异操作合二为一，即以事先给定的变异概率p

交叉：对于A，B两个父个体分别随机选择一交叉点，然后将A个体交叉点之后的部分丢弃替换为B个体交叉点之后的部分，图2为交叉操作示意图。

变异：以相同的概率随机在现有的单点变异和子树变异方法之间选择。

单点变异：在个体编码中随机选择变异点，对该点的编码进行随机变异，即将该点的基因编码替换为另一个与之类型相同的符号，具体来说：如果该点为函数，则替换为另一个自变量数与其相同的函数，如果该点为变量，则替换为另一个随机生成的变量。操作与遗传算法中的位翻转操作类似。

子树变异：在个体编码中随机选择变异点，将该点之后的子树替换为随机生成的子树，图3为子树变异示意图。

步骤7：循环步骤4-6，直至算法触发终止条件，在演化过程中出现的最小适应度个体即为最优个体。终止条件：循环代数达到最大设定值或模型误差小于设定阈值。

步骤8：对最优个体按照编码规则进行解码，得到对集群中个体运动规则的估计解。

在Python环境下使用演化计算工具库DEAP编制程序，实现本发明所提反演方法并仿真。在一台Intel(R)Core(TM)i7-7500U CPU@2.70GHz 2.90GHz,8G内存的计算机上进行10次独立的蒙特卡洛实验，得到最优个体对应解如下：一级模型邻居选择半径为48.9二级模型给出决策函数备选方案：

divide(sum(X),count(X))

sum(divide(X,sum(count(cos(X)))))

divide(mul(X,X),add(X,count(sin(X))))

经过化简计算，以上三个备选解均可划归为目标表达式

图4给出某次演化实验的适应度变化曲线，图5为10次实验给出的一级模型最优解(邻居选择范围)变化曲线。

从图4与图5中可以看出，本发明所提方法，基于原始集群运动数据通过两个模型的共同演化，对输入的实验数据所内涵的原始模型具有良好的学习精度。在当前针对群集的研究普遍采用正向建模方法且逆向建模工作大多依赖先验知识的背景下，本发明提出的基因编程模型反演方法。能够在对原始模型没有先验信息的情况下通过基因编程途径有效反演出集群个体的邻居选择机制和从邻居信息到自身决策变量的映射关系。