速解魔方机器人(下)

接上篇
5.4.2   粒子群优化算法(PSO)
训练BP神经网络常常采用误差反向传播算法，这种算 法容易陷入局部极值点，并且随着层数增多，内层权重梯 度过低，学习速度慢。而PSO算法是一种基于群体的优化方 法，算法中种群称作粒子群，个体称为粒子。它的基本概念 源于对海鸥等海鸟捕食方式的模拟。一群海鸟随机地搜寻食 物，它们不知道食物在哪里，但知道当前离食物最近的位 置，从而选择搜寻目前离食物最近的鸟的周围区域，以尽快 地找到食物。这种算法有训练速度快，不易陷入局部极值点 的优点。
1.问题的描述
采 用 P S O 训 练 神 经 网 络 时 ， 首 先 应 将 特 定 结 构 中 所 有 神 经 元 间 的连 接 权 值 编 码 成 实 数 码 串 表 示 的 个 体 。 假 设 网 络 中 包 含 M 个 优 化 权 值 ( 包 括 阈 值 在 内 ) ， 则 每 个 个 体 将 由 M 个 权 值 参 数 组 成 的 一 个
M 维 向 量 来 表 示 。   例 如 ： 给 定 如 下 结 构 的 神 经 网 络 ， 其 中 包 括 一 个 阈 值 ， 一 维 输 入 ， 两 个 隐 层 单 元 ， 一 维 输 出 ， 从 图 中 可 知 其 中 包括 6 个 连 接 权 ， 分 别 是
， 令则 微 粒 群 中 的 个 体 可 用 一 个 6 维 向 量 来 表 示 ， 即

此时， 个体结构中的每一个 元素，即代表神经网络中的一个权值。

2.初始化微粒群

图19　CCD摄像头    

图20　舵机实物
根据微粒群规模，按照上述个体结构随机产生一定数目的个体(微粒)组成种群，其中不同的个体代表神经网络的 一组不同权值。同时初始化群体最优位置gbest，个体最优位 置lbest。

3.神经网络的训练及微粒

将微粒群中每一个体的分量映射为网络中的权值，从而构成一个神经网络。对每一个体对应的神经网络，输入训 练样本进行训练。网络权值的优化过程是一个反复迭代的过 程。为了保证所训练的神经网络具有较强的泛化能力，在网 络的训练过程中，往往将给定的样本空间分为两部分，一部 分用作训练样本，称为训练集，一部分作为测试样本，称为 测试集。而在权值优化过程中，每进行一次训练，都要对给 定的样本集进行分类，以保证每次训练时采用的训练集均不 相同。计算每一个网络在训练集上产生的均方误差，并以此 作为目标函数，并构造如下的适应度函数，用来计算个体的适应度。

其中，tk,p指训练样本P在K输出端的给定输出，则适应度函数定义如下：

4.PSO模型计算
评价微粒群中的所有个体( 每一个体视为可飞行的微 粒)，从中找到最佳个体用来判断是否需要更新微粒的Gbest 与Lbest。之后，按照PSO模型更新每一个体不同分量上的飞 行速度，并以此产生新的个体微粒。

5.算法终止条件

当目标函数值(即均方误差)小于给定的    时，算法终止。 用PSO训练神经网络算法的具体流程如下图21。
5.5  Linux系统下通过地址映射访问物理内存
设计基于ARM的linux应用程序控制FPGA端PIO控制器 pio_led，pio_led连接到HPS/ARM lightweight axi bridge从而获 得在HPS/ARM总线上的物理地址空间。linux应用程序通过 linux内核内存映射设备驱动访问PIO控制器pio_led的寄存器 物理地址进而控制pio_led执行相应的动作。
Linux系统下通过地址映射访问物理内存的原理如下

图22　算法终止条件
/dev/mem: 物理内存的全镜像。可以用来访问物理内存。
调试嵌入式Linux内核时，可能需要查看某个内核变量 的值。/dev/kmem提供了访问内核虚拟内存的途径。现在 的内核大都默认禁用了/dev/kmem，打开的方法是在 make menuconfig中选中  device drivers --> Character devices -->/dev/
kmem virtual device support.用 cat /proc/kallsyms | grep  *** 找到要查看的变量的地 址， 这个地址作为本程序的输入参数。/dev/mem 用来访问物理IO设备， 比如X用来访问显 卡的物理内存， 或访问嵌入式板中的G P I O 。 用法一般是 open，mmap，然后使用map之后的地址访问物理内存。这 是实现用户空间驱动的一种方法。
比如，标准VGA 16色模式的实模式地址是A000:0000， 而线性地址则是A0000。设定显 存大小为0x10000，则可以 如下操作mem_fd  = open( "/dev/mem", O_RDWR );
vga_mem = mmap( 0, 0x10000, PROT_READ  | PROT_ WRITE, MAP_SHARED,
mem_fd, 0xA0000 ); close( mem_fd );
然后便可以对vga_mem进行访问。当然，如果是操作 VGA显卡，还要获得I/O 端口的访问权限，以便进行直接的 I/O操作，用来设置模式/调色板/选择位面等等。在工控领 域中还有一种常用的方法，用来在内核和应用程序之间高效 传递数据。

6  设计特点
6.1  机械手臂设计
利用舵机的旋转带动拉伸杆的拉伸，从而达到像人的 手臂一样灵活伸缩旋转，抓取魔方，转动魔方。
6.2  魔方机器人结构
巧妙地利用舵机与塑料条的配合搭建机器人的机械手 臂，利用方形架构固定四个机械手臂，使机械手臂能灵活快 速地转动以及伸缩。
6.3  基于BP神经网络的颜色识别算法
对颜色进行分类的方式有多种，其中 RGB颜色空间是 最基本、最常用的颜色空间，然而，从颜色感知特性来说， R G B 颜 色 空 间 是 非 均 匀 的 ， 各 颜 色 分 量 之 间 的 相 关 性 较 强， 因而一般用于把目标分为两类的识别模型中。HSI 颜色 空间是另一种比较常用的颜色空间，它基于人的心理感知特 性而建立，属于极坐标空间结构，其优点是能直观地描述颜 色，但是，由于 HSI 颜色空间内存在奇异点，同时，当光线 明暗变化，灯光中的某分量值稍高时，对颜色分类会出现许 多错误。因此也不适合用来实现对颜色的分类和量化。对于 这种复杂多变环境下的颜色的分类，我们最终采用人工神经 网络(ANN)来进行。
6.4.  独立开发的还原魔方算法
算法的核心是基于迭代加深启发式搜索算法(IDA*)的 一种二阶段的搜索算法，过程规则很简单，没有很复杂的状 态判断，只是重复循环：对每个阶段的魔方不断重复尝试不 同的旋转，然后判断是否达到目标状态，如果没有，则根据 一个估价函数，选择估价最低的操作继续尝试。第一个阶 段有18种可能的操作，最多12步，第二阶段有10种可能的操作，最多有18步。可见，如果仅做简单处理，循环的次数会
十分巨大，难以搜索出正确结果。所以，对每个操作进行高 效的代价计算，然后进行剪枝是十分必要的。估价函数是一 张事先生成好的内存查找表。采用该内存查找表进行启发搜 索，有些情况下，得出还原方法速度会非常快，在百毫秒之 内，当然，也存在一定的概率，需要花较长时间得出还原方 法，(算法运行到现在，未出现超过3秒的情况)在一台intel i5@2.50Ghz的个人电脑，得出方法平均仅需一秒钟的时间。
6.5  采用SoC设计
利用FPGA端丰富的外设做数据采集，将采集到的图像 数据进行处理，在ARM端做算法，对任意一个打乱的魔方 进行还原的求解步骤，充分发挥DE1-SoC的SoC特点。

7 总结
经过三个月的奋战，我们的作品基本达到预期目标， CCD摄像头识别、VGA显示以及机械部分的搭建等都已实 现，唯一不足的是在VGA显示部分画面不够绚丽，写好的
3D魔方程序由于移植出现问题，没有出现在显示屏上。在 团队的分工上，硬件软件分工明确，很大地提高了作品完成 效率。
在这次比赛中，我们学会了Altera公司许多开发工具， 例如Quartus ，Qsys以及ARM公司的DS-5等，为我们的硬件 开发和测试提供了很大的便利。
从入门FPGA开发板，到现在基本完成预期作品，通过 这次比赛和这三个月的努力，我们团队的每个人都学到了很 多，我们都总结了许多解决问题的方法，并养成了良好的文 档习惯。在比赛过程中，我们采用多种途径解决技术难题， 例如网络、DE1-SoC的配套书籍、官方论坛以及开发板的用 户手册和自带例程,攻破设计难点。我们针对各个模块制定 了多套方案，合理分析了设计的可行性，保证在实现基本功 能的基础上再进行优化。在每一次实验中，我们将自己的收 获写进文档，然后与队友进行交流，分享心得，共同进步。 当然，我们必须感谢湖北大学—Altera公司EDA/SOPC联合 实验室提供的丰富的硬件、软件资源，同时还要感谢感谢 Altera和TERASIC公司为本课题提供的设计工具，包括大学 计划所提供的学习资源、FPGA、软件、开发板、文档支持 和参考设计。