基于复数编码遗传算法的竞争性协进化策略

谭冠政, 刘良敏

(中南大学 信息科学与工程学院, 湖南 长沙, 410083)

摘要: 将基于复数编码的遗传算法引入竞争性协进化的理论研究中, 提出一种竞争性协进化的新策略, 即: 在仿真实验中, 采用2个基于神经网络结构控制的移动机器人, 并将它们投入到一个陌生的环境中。 其中, 一个机器人扮演猎手, 另一个扮演猎物, 猎手对猎物进行捕捉, 最终得到每一代的最好猎手机器人和最好猎物机器人以及它们的适应度曲线。 在这个竞争性协进化系统中, 基于复数编码的遗传算法主要用于对机器人控制系统的神经网络进行进化。 计算机仿真结果表明, 与基本遗传算法相比, 基于复数编码的遗传算法具有更强的进化能力。
关键词: 进化机器人; 竞争性协进化; 遗传算法; 神经网络; 连接权
中图分类号:TP242.6; TP18 文献标识码:A 文章编号: 1672-7207(2005)03-0475-06

Competitive co-evolution strategy based on genetic
algorithm with complex-valued encoding

TAN Guan-zheng, LIU Liang-min

(School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: The genetic algorithm with complex-valued encoding was introduced to the research of competitive co-evolution theory, and a new strategy for competitive co-evolution was proposed. In the simulation experiments, two mobile robots with neural networks control structure were put into an unknown simulation environment. One of them played the part of hunter and the other played the prey; the hunter always tried to catch the prey. The best hunter and the best prey of every generation were obtained from the experiment, including the fitness curves of them. The genetic algorithm with complex-valued encoding was mainly used to evolve the neural networks of controller of robots. The experiment results show that the genetic algorithm with complex-valued encoding has stronger evolutionary capacity compared with the general genetic algorithm.
Key words: evolutionary robot; competitive co-evolution; genetic algorithm; neural networks; synaptic weights 

在进化机器人中, 达尔文的物种进化思想被引入机器人控制系统的设计中^[1]。 近十年来, 欧洲和日本对进化机器人的研究较多, 我国还处于起步阶段。 竞争性协进化模仿动物之间“优胜劣汰”的生存法则, 是进化机器人的一种重要进化方式^[2]。 生态上密切相关的物种, 它们之间相互关联的进化叫做协进化。 可见, 每一群体中各个体的适应度评价都与其他群体相关^[3]。 目前, 协进化方法有: 基于自然界中共生现象衍生出来的合作型协进化^[4]; 基于“捕食者-猎物”问题得到的竞争性协进化^[5]; 基于自然界中个体的生存期适应度评估产生的协进化遗传算法^[6,7]。 在本研究中, 所使用的进化机器人其控制结构采用神经网络, 生物学背景与进化机器人的研究目标很契合, 有利于适应性行为的产生^[8]。 用遗传算法优化神经网络, 可以使神经网络具有自进化、 自适应能力, 从而构造出进化的神经网络^[9-12]。 采用基于复数编码的遗传算法对进化机器人神经网络的连接权进行进化和优化, 为竞争性协进化提供了一种新的策略。 采用VC++6.0语言编写仿真软件, 在计算机上进行动态仿真实验, 以展示一个移动机器人对另一个移动机器人的捕捉过程。

1 复数编码遗传算法的基本原理

1.1 算法的基本思想

遗传算法可以使机器人学习如何提高它自身有限的性能^[13-15]。 在传统的遗传算法中, 染色体大都采用二进制编码, 也就是分别用二进制数或实数码串来表达每个个体。 基于复数编码的遗传算法是将复数编码的思想应用于遗传算法中, 并引入双倍体来代表算法中的个体^[16]。 复数的实部和虚部分别称为实基因与虚基因。 个体由2条等长度的基因链组成, 每个基因位有2个等位基因, 分别对应复数的实部和虚部。 由于复数表示形式及运算本身的多样性, 使得复数编码的遗传算法可以采用非常灵活的遗传操作方式, 为遗传算法在进化机器人研究中的应用提供了新的途径。
1.2 算法的主要操作
1.2.1 编码

对于一个有m个自变量的问题, 设有m个复数: z_k=x_k+iy_k(其中, k=1,2,…,m), 将它们表示成染色体双链结构: {(x₁,x₂,…,x_m), (y₁,y₂,…,y_m)}。 若记: r=(x₁,x₂,…,x_m) , d=(y₁, y₂,…,y_m) , 则称r为实基因串, d为虚基因串。
1.2.2 初始群体的产生

根据所研究的问题中每一个自变量的定义区间[a_k, b_k],(其中,k=1,2,…,m), 随机产生m个复数模: ρ_k∈[0,(b_k-a_k)/2], 同时随机产生m个幅角θ_k∈[0,2π], 这样便构成了m个复数:

x_k+iy_k=ρ_k(cosθ_k+isinθ_k)。(1)

用这种方法形成所需要的实基因串(x₁,x₂,…,x_m)与虚基因串(y₁,y₂,…,y_m), 从而形成一个个体: {(x₁,x₂,…,x_m), (y₁,y₂,…,y_m)}。

按照类似方法, 再产生若干个个体, 形成初始群体。
1.2.3 选择操作

采用适应度比例的选择方法, 即把群体中适应度最高的一部分个体不进行配对交叉而直接复制到下一代中, 其余的个体按适应度比例方法选择产生。 其公式如下:

其中: p_si为第i个个体被选择复制的概率; f_i为第i个个体的适应度; N为个体的数量。
1.2.4 交叉操作

利用类似实数编码中的算术交叉方法分别对2个父代个体中的实基因串和虚基因串进行交叉操作。 为叙述方便, 设2个父代复基因串r₁和r₂分别为:

r₁=(x⁽¹⁾₁+iy⁽¹⁾₁,…,x⁽¹⁾_m+iy⁽¹⁾_m);(3)
r₂=(x⁽²⁾₁+iy⁽²⁾₁,…,x⁽²⁾_m+iy⁽²⁾_m)。(4)

并设交叉后的2个后代复基因串z₁和z₂分别为:

z₁=(u⁽¹⁾₁+iv⁽¹⁾₁,…,u⁽¹⁾_m+iv⁽¹⁾_m);(5)
z₂=(u⁽²⁾₁+iv⁽²⁾₁,…,u⁽²⁾_m+iv⁽²⁾_m)。(6)

在[0,1]区间内产生m个随机数α₁,α₂,…,α_m, 则

交叉后的模仍属于[0, (b_k-α_k)/2]。 其中: k=1,2,…,m。
1.2.5 变异操作

设(ρ₁, ρ₂, …, ρ_m)是一个复数串个体的模分量,选ρ_k进行变异, 其定义区间是[0, (b_k-α_k)/2], 则变异后的模分量为(ρ₁,…,ρ_k-1, ρ_k,…,ρ_m)。 其中^[16]:

R为[0,1]的1个随机数。 函数Δ(T,y)=y*(1-r^Tλ), r为[0,1]的1个随机数; λ∈[2, 5]; T为变异温度, 定义为^[16]:

T=1-f(z)/f_max。(9)

这里: f(z)为个体的适应度, f_max为f(z)的上限值。
2 基于神经网络的控制结构

2.1 控制结构

这里主要研究机器人的竞争性协进化问题, 机器人的控制系统采用基于神经网络的控制结构。

神经网络各神经元之间的连接并不只是一个单纯的信号传送通道, 在每对神经元之间的连接上有一个加权系数, 这个加权系数称为权值。 权值的大小决定上一个神经元的输出对下一个神经元的刺激强度。 在神经网络中, 修改权值的规则称为学习算法^[17,18]。
2.2 优化神经网络连接权的过程

采用基于复数编码的遗传算法来优化神经网络的连接权。 其过程为:

a. 随机产生一组网络权值分布, 采用复数编码方案对该组权值分布中的各权值进行编码, 进而构造出一个码串。 一个码串代表网络的一种权值分布, 因而也表示了一个权值按此分布的一个神经网络。

b. 对所产生的神经网络计算其适应度(对具体问题可以具体定义适应度计算公式)。

c. 选择若干适应度最大的个体, 直接遗传给下一代。

d. 利用交叉和变异等算子对当前一代群体进行遗传操作, 产生下一代群体。

e. 重复步骤b., c.和d.,使初始确定的一组权值分布不断进化, 直到训练目标符合要求为止。
2.3 编码方案

下面通过一个例子说明基于复数编码的遗传算法对神经网络的连接权进行编码的过程。 图1所示为神经网络的一种简单的权值分布, 各线段旁边的数字代表该线段所连神经元之间的权值。神经网络的权值及其对应的复数编码如表1所示。

图 1   一种简单的权值分布
Fig. 1   A simple distribution of weight values

 表 1   复数编码方案
Table 1   Complex-valued encoding scheme

按照以上所述的编码方法, 每一个权值对应于一个复数, 复数的模等于权值, 复数幅角在[0, 2π]内随机产生, 这样就形成了一个染色体结构: {(9.00, -6.50, 20.00, 4.50, 0, 17.32), (15.59, 11.26, 0, 7.79, -10.00, -10.00)}, 然后按照复数编码遗传算法进行遗传操作。

3 机器人竞争性协进化仿真

3.1 实验环境

本实验以2个Motorola MC68331移动机器人为参照建立模型。 该机器人的控制系统采用基于神经网络的控制结构。 2个机器人中, 一个扮演猎手的角色, 另一个扮演猎物的角色, 猎手对猎物进行跟踪及捕捉。 2个机器人都装有8个红外线传感器, 均匀地分布于机器人的四周。 猎手机器人装有摄像机, 摄像机的摄像范围在0~36°以内, 摄像距离为5~50 cm; 而猎物机器人的最大速度是猎手机器人最大速度的2倍, 所以, 两者各有优势。 实验环境如图2所示, 机器人处在一个面积为47 cm×47 cm、 封闭的正方形环境内, 四周是白色的围墙。 该环境称为竞技场。

图 2   实验环境示意图
Fig. 2   Experiment environment

3.2 控制系统的构成

控制系统构成如图3所示。 2个机器人都采用神经网络控制结构, 遗传算法于控制系统的CPU中运行。 每一次新的权值被编码后, 神经网络权值分布通过数据线下载到机器人的微处理器上。 在起始时刻, 2个机器人都把自己的内部时钟(一种循环计数器)设置到零, 并开始移动。 当猎手机器人碰到猎物机器人时, 2个机器人之间的竞赛结束; 或者在500个单位时间内(50 s), 若猎手没有追到猎物, 竞赛也结束。 结束时, 猎物机器人把内部时钟的数值送回控制系统, 该数值被用于构造2个机器人的适应度, 其值越大, 说明猎物机器人的适应度越高, 而猎手机器人的适应度越低。

图 3   控制系统构成
Fig. 3   Control system architecture  

猎物机器人个体的适应度f_p和猎手机器人个体的适应度f_h分别定义为:

f_p=t/500;(10)
f_h=1-f_p。(11)

其中: t为猎手机器人追捕到猎物机器人所需的时间。 因为机器人的行为与其采用的神经网络直接相关, 所以, 将所得机器人的适应度作为神经网络的适应度, 从而进行编码控制。
3.3 算法实现步骤

将基于复数编码的遗传算法应用于机器人竞争性协进化问题时, 具体实现步骤可归纳如下。

Step 1: 设定群体数n_npop, 进化代数n_gensize, 以及每个群体所含个体的数量N。

Step 2: 根据式 (1) 产生初始种群。

Step 3: 置演化代数n_gen=1。

Step 4: 个体数P=1。

Step 5: 执行追踪过程。

Step 6: 按照式 (10) 和 (11) 分别计算猎手机器人个体的适应度f_h和猎物机器人个体的适应度f_p。

Step 7: 若P〈N, 则P=P+1, 并转到Step 5; 否则, 继续往下执行。

Step 8: 按照式 (2) 进行选择操作。

Step 9: 进行交叉操作。

Step 10: 进行变异操作。

Step 11: 分别记录猎手机器人和猎物机器人最优个体的适应度。

Step 12: n_gen=n_gen+1, 若n_gen≤n_gensize, 则转到Step 4, 否则结束循环。

Step 13: 分别绘出猎手机器人和猎物机器人的最优个体适应度变化曲线。

4 仿真结果及分析

仿真参数设置如下: 群体数n_npop=2, 进化代数n_gensize=100, 每个群体所含个体的数量N=20, 交叉率设定为0.6, 变异率设定为0.001。

图4所示为进化过程中第8代的动态运动仿真曲线。 可见, 在进化过程的初始阶段, 无论是猎手机器人还是猎物机器人, 它们的行为都非常简单。 但是不管怎样, 猎物机器人得分都很高。 从两者的运动轨迹上分析, 猎手机器人还没有足够的能力抓到猎物机器人。 很明显, 猎物机器人尽管行为很简单, 但速度较快,而猎手机器人远远被猎物机器人甩开。 随着进化过程的继续进行, 2个互相竞争的机器人的得分都提高, 但猎手机器人的得分明显提高, 它抓到猎物机器人的机会也越来越大。 图5所示为进化过程中第72代的捕捉仿真图, 其中, 虚线代表猎物机器人的运动轨迹, 实线代表猎手机器人的运动轨迹。 可以看出, 两者的运动轨迹变得很复杂, 都具有突然转弯的特性, 这表明两者的进化程度明显提高。

但是无论进化到多少代, 也看不到某一方占绝对优势。 这一点可通过两者的适应度变化看出(如图6所示), 这也印证了协进化的核心思想: 互相竞争, 互相促进。 在通常环境下, 物种之间的竞争能力保持着一种动态平衡。 任何一个物种的任何一次进化改变, 都会引起与其相关物种的“反应”, 最后又回到平衡。

在猎手机器人身上采用基于实数编码的基本遗传算法作为神经网络控制器的进化方法, 而在猎物机器人身上采用基于复数编码的遗传算法, 再让他[CM(22] 们互相竞争、 进化, 可通过分析适应度的变化来比较这2种遗传算法在竞争性协进化应用中的效果; 若猎手机器人和猎物机器人都采用基于复数编码的遗传算法作为其神经网络控制器的进化方法, 则两者最优个体的适应度变化如图6所示。 可见, 猎手和猎物的适应度维持着一种动态平衡, 在某一个时间段猎手占优势, 在另一个时间段猎物占优势。

●—猎手机器人; ○—猎物机器人
图 4   第8代捕捉仿真图
Fig. 4   Dynamic pursuit simulation of generation 8

●—猎手机器人; ○—猎物机器人
图 5   第72代捕捉仿真图
Fig. 5   Dynamic pursuit simulation of
generation 72

当猎手机器人采用基于实数编码的遗传算法, 而猎物机器人采用基于复数编码的遗传算法时, 适应度变化结果如图7所示。 可见,与猎手机器人最优个体的适应度变化曲线相比, 在整个进化过程中,猎物机器人适应度高于猎手机器人的适应度。 这表明, 在竞争性协进化应用中, 基于复数编码的遗传算法其进化程度比基于实数编码的遗传算法的进化程度要高得多; 在竞争性协进化应用中, 基于复数编码遗传算法比基本遗传算法优越, 从而证明了基于复数编码遗传算法的竞争性协进化策略的正确性。

实线—猎手机器人; 虚线—猎物机器人
图 6   采用复数编码遗传算法适应度与进化代数的关系
Fig. 6   Fitness curves of two robots with
complex-valued encoding genetic algorithm

 实线—猎手机器人; 虚线—猎物机器人
图 7   采用2种不同遗传算法的适应度与
进化代数的关系
Fig. 7   Fitness curves of two robots with two
different genetic algorithms

5 结 论

a. 以基于复数编码的遗传算法为基础, 提出了竞争性协进化的新策略。

b. 优化智能机器人神经网络权值是提高机器人性能的一种有效方法。

c. 与基本遗传算法相比, 基于复数编码的遗传算法在竞争性协进化方面的应用具有更好的效果, 这样进化的机器人个体行为复杂,对环境具有高度适应性。

d. 竞争性协进化的进化方式使得每个个体和其竞争对手都在进化, 减少了进化过程所需的资源。

参考文献:

[1]Cliff D, Havey I, Husbands P. Explorations in evolutionary robotics[J]. Adaptive Behavior, 1993, 2(1): 73-110.
[2]刘娟, 蔡自兴. 进化机器人研究进展[J]. 控制理论与应用, 2002, 19(4): 493-499.
LIU Juan, CAI Zi-xin. Survey on evolutionary robotics[J]. Control Theory and Applications, 2002, 19(4): 493-499.
[3]Nicholas R. Commitments and Conventions: The foundation of coordination in multi-agent systems[J]. The Knowledge Engineering Review, 1993, 8(3): 223-250.
[4]Paredis J. Coevolutionary computation[J]. Artificial Life, 1995, 2(4): 355-375.
[5]Gary B, Parker J. Co-evolving model parameters for anytime learning in evolutionary robotics[J]. Robotics and Autonomous Systems, 2000, 33:13-30.
[6]Paredis J. Coevolutionary computation[J]. Artificial Life, 1995, 2(4): 355-375.
[7]Salichs M A, Moreno L. Navigation of mobile robots: open questions[J]. Robotica, 2000, 18: 227-234.
[8]Floreano D, Urzelai J. Evolutionary robots with on-line self-organization and behavioral fitness[J]. Neural Networks, 2000,13: 431-443.
[9]Floreano D, Mondada F. Evolutionary neurocontrollers for autonomous mobile robots[J]. Neural Networks, 1998, 11: 1461-1478.
[10]Miyashita K, Sooyol O. Evolutionary generation of human-like bipedal locomotion[J]. Mechatronics, 2003, 13: 791-807.
[11]Nordin P, Banzhaf W. Evolution of a world model for a miniature robot using genetic programming[J]. Robotics and Autonomous Systems, 1998, 25:105-116.
[12]Bonarini A, Bonacina C. An approach to the design of reinforcement functions in real world, agent-based applications[J]. IEEE Tramsactions on Systems, Man, and Cybernetics-part B, 2001, 31:288-302.
[13]Miglino O, Lund H, Nolfi S. Evolving mobile robots in simulated and real environments[J]. Artificial Life, 1996, 2: 417-434.
[14]Floreano D, Urzelai J. Evolutionary robots with on-line self-organization and behavioral fitness[J]. Neural Networks, 2000, 13: 431-443.
[15]Schultz W A C, Agah A. Evolving control for distributed micro air vehicles[J]. Robotics and Automation, 1999,21:174-179.
[16]ZHENG Zhang-qiu. Genetic algorithm based on complex-valued encoding[J]. Control Theory & Applications, 2003, 20(1): 97-100.
[17]胡守仁.神经网络导论[M].长沙:国防科技大学出版社, 1993: 23-25.
HU Shou-ren. Guide of neural networks[M]. Changsha: National University of Defense Technology Press, 1993: 23-25.
[18]陈国良,王东生.遗传算法及其应用[M].北京:人民邮电出版社, 1996: 242-245.
CHEN Guo-liang, WANG Dong-sheng. Genetic algorithm and application[M]. Beijing: Posts Telecom Press, 1996: 242-245.

收稿日期:2004 -08 -08

基金项目:国家自然科学基金资助项目(50275150);中国科学院机器人学开放研究实验室基金资助项目(RL200002)

作者简介: 谭冠政(1962-),男,湖南湘潭人,博士,教授,博士生导师,从事智能机器人系统与控制,人工智能及其应用,先进控制理论与先进算法的研究

论文联系人: 谭冠政,男, 博士,教授,博士生导师; 电话:0731-8716259(O); E-mail:tgz@mail.csu.edu.cn