速解魔方機(jī)器人(下)

接上篇
5.4.2   粒子群優(yōu)化算法(PSO)
訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)常常采用誤差反向傳播算法，這種算 法容易陷入局部極值點(diǎn)，并且隨著層數(shù)增多，內(nèi)層權(quán)重梯 度過(guò)低，學(xué)習(xí)速度慢。而PSO算法是一種基于群體的優(yōu)化方 法，算法中種群稱作粒子群，個(gè)體稱為粒子。它的基本概念 源于對(duì)海鷗等海鳥捕食方式的模擬。一群海鳥隨機(jī)地搜尋食 物，它們不知道食物在哪里，但知道當(dāng)前離食物最近的位 置，從而選擇搜尋目前離食物最近的鳥的周圍區(qū)域，以盡快 地找到食物。這種算法有訓(xùn)練速度快，不易陷入局部極值點(diǎn) 的優(yōu)點(diǎn)。
1.問(wèn)題的描述
采 用 P S O 訓(xùn) 練 神 經(jīng) 網(wǎng) 絡(luò) 時(shí) ， 首 先 應(yīng) 將 特 定 結(jié) 構(gòu) 中 所 有 神 經(jīng) 元 間 的連 接 權(quán) 值 編 碼 成 實(shí) 數(shù) 碼 串 表 示 的 個(gè) 體 。 假 設(shè) 網(wǎng) 絡(luò) 中 包 含 M 個(gè) 優(yōu) 化 權(quán) 值 ( 包 括 閾 值 在 內(nèi) ) ， 則 每 個(gè) 個(gè) 體 將 由 M 個(gè) 權(quán) 值 參 數(shù) 組 成 的 一 個(gè)
M 維 向 量 來(lái) 表 示 。   例 如 ： 給 定 如 下 結(jié) 構(gòu) 的 神 經(jīng) 網(wǎng) 絡(luò) ， 其 中 包 括 一 個(gè) 閾 值 ， 一 維 輸 入 ， 兩 個(gè) 隱 層 單 元 ， 一 維 輸 出 ， 從 圖 中 可 知 其 中 包括 6 個(gè) 連 接 權(quán) ， 分 別 是
， 令則 微 粒 群 中 的 個(gè) 體 可 用 一 個(gè) 6 維 向 量 來(lái) 表 示 ， 即

此時(shí)， 個(gè)體結(jié)構(gòu)中的每一個(gè) 元素，即代表神經(jīng)網(wǎng)絡(luò)中的一個(gè)權(quán)值。

2.初始化微粒群

圖19　CCD攝像頭    

圖20　舵機(jī)實(shí)物
根據(jù)微粒群規(guī)模，按照上述個(gè)體結(jié)構(gòu)隨機(jī)產(chǎn)生一定數(shù)目的個(gè)體(微粒)組成種群，其中不同的個(gè)體代表神經(jīng)網(wǎng)絡(luò)的 一組不同權(quán)值。同時(shí)初始化群體最優(yōu)位置gbest，個(gè)體最優(yōu)位 置lbest。

3.神經(jīng)網(wǎng)絡(luò)的訓(xùn)練及微粒

將微粒群中每一個(gè)體的分量映射為網(wǎng)絡(luò)中的權(quán)值，從而構(gòu)成一個(gè)神經(jīng)網(wǎng)絡(luò)。對(duì)每一個(gè)體對(duì)應(yīng)的神經(jīng)網(wǎng)絡(luò)，輸入訓(xùn) 練樣本進(jìn)行訓(xùn)練。網(wǎng)絡(luò)權(quán)值的優(yōu)化過(guò)程是一個(gè)反復(fù)迭代的過(guò) 程。為了保證所訓(xùn)練的神經(jīng)網(wǎng)絡(luò)具有較強(qiáng)的泛化能力，在網(wǎng) 絡(luò)的訓(xùn)練過(guò)程中，往往將給定的樣本空間分為兩部分，一部 分用作訓(xùn)練樣本，稱為訓(xùn)練集，一部分作為測(cè)試樣本，稱為 測(cè)試集。而在權(quán)值優(yōu)化過(guò)程中，每進(jìn)行一次訓(xùn)練，都要對(duì)給 定的樣本集進(jìn)行分類，以保證每次訓(xùn)練時(shí)采用的訓(xùn)練集均不 相同。計(jì)算每一個(gè)網(wǎng)絡(luò)在訓(xùn)練集上產(chǎn)生的均方誤差，并以此 作為目標(biāo)函數(shù)，并構(gòu)造如下的適應(yīng)度函數(shù)，用來(lái)計(jì)算個(gè)體的適應(yīng)度。

其中，tk,p指訓(xùn)練樣本P在K輸出端的給定輸出，則適應(yīng)度函數(shù)定義如下：

4.PSO模型計(jì)算
評(píng)價(jià)微粒群中的所有個(gè)體( 每一個(gè)體視為可飛行的微 粒)，從中找到最佳個(gè)體用來(lái)判斷是否需要更新微粒的Gbest 與Lbest。之后，按照PSO模型更新每一個(gè)體不同分量上的飛 行速度，并以此產(chǎn)生新的個(gè)體微粒。

5.算法終止條件

當(dāng)目標(biāo)函數(shù)值(即均方誤差)小于給定的    時(shí)，算法終止。 用PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)算法的具體流程如下圖21。
5.5  Linux系統(tǒng)下通過(guò)地址映射訪問(wèn)物理內(nèi)存
設(shè)計(jì)基于ARM的linux應(yīng)用程序控制FPGA端PIO控制器 pio_led，pio_led連接到HPS/ARM lightweight axi bridge從而獲 得在HPS/ARM總線上的物理地址空間。linux應(yīng)用程序通過(guò) linux內(nèi)核內(nèi)存映射設(shè)備驅(qū)動(dòng)訪問(wèn)PIO控制器pio_led的寄存器 物理地址進(jìn)而控制pio_led執(zhí)行相應(yīng)的動(dòng)作。
Linux系統(tǒng)下通過(guò)地址映射訪問(wèn)物理內(nèi)存的原理如下

圖22　算法終止條件
/dev/mem: 物理內(nèi)存的全鏡像?？梢杂脕?lái)訪問(wèn)物理內(nèi)存。
調(diào)試嵌入式Linux內(nèi)核時(shí)，可能需要查看某個(gè)內(nèi)核變量 的值。/dev/kmem提供了訪問(wèn)內(nèi)核虛擬內(nèi)存的途徑?，F(xiàn)在 的內(nèi)核大都默認(rèn)禁用了/dev/kmem，打開(kāi)的方法是在 make menuconfig中選中  device drivers --> Character devices -->/dev/
kmem virtual device support.用 cat /proc/kallsyms | grep  *** 找到要查看的變量的地 址， 這個(gè)地址作為本程序的輸入?yún)?shù)。/dev/mem 用來(lái)訪問(wèn)物理IO設(shè)備， 比如X用來(lái)訪問(wèn)顯 卡的物理內(nèi)存， 或訪問(wèn)嵌入式板中的G P I O 。 用法一般是 open，mmap，然后使用map之后的地址訪問(wèn)物理內(nèi)存。這 是實(shí)現(xiàn)用戶空間驅(qū)動(dòng)的一種方法。
比如，標(biāo)準(zhǔn)VGA 16色模式的實(shí)模式地址是A000:0000， 而線性地址則是A0000。設(shè)定顯 存大小為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 );
然后便可以對(duì)vga_mem進(jìn)行訪問(wèn)。當(dāng)然，如果是操作 VGA顯卡，還要獲得I/O 端口的訪問(wèn)權(quán)限，以便進(jìn)行直接的 I/O操作，用來(lái)設(shè)置模式/調(diào)色板/選擇位面等等。在工控領(lǐng) 域中還有一種常用的方法，用來(lái)在內(nèi)核和應(yīng)用程序之間高效 傳遞數(shù)據(jù)。

6  設(shè)計(jì)特點(diǎn)
6.1  機(jī)械手臂設(shè)計(jì)
利用舵機(jī)的旋轉(zhuǎn)帶動(dòng)拉伸桿的拉伸，從而達(dá)到像人的 手臂一樣靈活伸縮旋轉(zhuǎn)，抓取魔方，轉(zhuǎn)動(dòng)魔方。
6.2  魔方機(jī)器人結(jié)構(gòu)
巧妙地利用舵機(jī)與塑料條的配合搭建機(jī)器人的機(jī)械手 臂，利用方形架構(gòu)固定四個(gè)機(jī)械手臂，使機(jī)械手臂能靈活快 速地轉(zhuǎn)動(dòng)以及伸縮。
6.3  基于BP神經(jīng)網(wǎng)絡(luò)的顏色識(shí)別算法
對(duì)顏色進(jìn)行分類的方式有多種，其中 RGB顏色空間是 最基本、最常用的顏色空間，然而，從顏色感知特性來(lái)說(shuō)， R G B 顏 色 空 間 是 非 均 勻 的 ， 各 顏 色 分 量 之 間 的 相 關(guān) 性 較 強(qiáng)， 因而一般用于把目標(biāo)分為兩類的識(shí)別模型中。HSI 顏色 空間是另一種比較常用的顏色空間，它基于人的心理感知特 性而建立，屬于極坐標(biāo)空間結(jié)構(gòu)，其優(yōu)點(diǎn)是能直觀地描述顏 色，但是，由于 HSI 顏色空間內(nèi)存在奇異點(diǎn)，同時(shí)，當(dāng)光線 明暗變化，燈光中的某分量值稍高時(shí)，對(duì)顏色分類會(huì)出現(xiàn)許 多錯(cuò)誤。因此也不適合用來(lái)實(shí)現(xiàn)對(duì)顏色的分類和量化。對(duì)于 這種復(fù)雜多變環(huán)境下的顏色的分類，我們最終采用人工神經(jīng) 網(wǎng)絡(luò)(ANN)來(lái)進(jìn)行。
6.4.  獨(dú)立開(kāi)發(fā)的還原魔方算法
算法的核心是基于迭代加深啟發(fā)式搜索算法(IDA*)的 一種二階段的搜索算法，過(guò)程規(guī)則很簡(jiǎn)單，沒(méi)有很復(fù)雜的狀 態(tài)判斷，只是重復(fù)循環(huán)：對(duì)每個(gè)階段的魔方不斷重復(fù)嘗試不 同的旋轉(zhuǎn)，然后判斷是否達(dá)到目標(biāo)狀態(tài)，如果沒(méi)有，則根據(jù) 一個(gè)估價(jià)函數(shù)，選擇估價(jià)最低的操作繼續(xù)嘗試。第一個(gè)階 段有18種可能的操作，最多12步，第二階段有10種可能的操作，最多有18步。可見(jiàn)，如果僅做簡(jiǎn)單處理，循環(huán)的次數(shù)會(huì)
十分巨大，難以搜索出正確結(jié)果。所以，對(duì)每個(gè)操作進(jìn)行高 效的代價(jià)計(jì)算，然后進(jìn)行剪枝是十分必要的。估價(jià)函數(shù)是一 張事先生成好的內(nèi)存查找表。采用該內(nèi)存查找表進(jìn)行啟發(fā)搜 索，有些情況下，得出還原方法速度會(huì)非?？?，在百毫秒之 內(nèi)，當(dāng)然，也存在一定的概率，需要花較長(zhǎng)時(shí)間得出還原方 法，(算法運(yùn)行到現(xiàn)在，未出現(xiàn)超過(guò)3秒的情況)在一臺(tái)intel i5@2.50Ghz的個(gè)人電腦，得出方法平均僅需一秒鐘的時(shí)間。
6.5  采用SoC設(shè)計(jì)
利用FPGA端豐富的外設(shè)做數(shù)據(jù)采集，將采集到的圖像 數(shù)據(jù)進(jìn)行處理，在ARM端做算法，對(duì)任意一個(gè)打亂的魔方 進(jìn)行還原的求解步驟，充分發(fā)揮DE1-SoC的SoC特點(diǎn)。

7 總結(jié)
經(jīng)過(guò)三個(gè)月的奮戰(zhàn)，我們的作品基本達(dá)到預(yù)期目標(biāo)， CCD攝像頭識(shí)別、VGA顯示以及機(jī)械部分的搭建等都已實(shí) 現(xiàn)，唯一不足的是在VGA顯示部分畫面不夠絢麗，寫好的
3D魔方程序由于移植出現(xiàn)問(wèn)題，沒(méi)有出現(xiàn)在顯示屏上。在 團(tuán)隊(duì)的分工上，硬件軟件分工明確，很大地提高了作品完成 效率。
在這次比賽中，我們學(xué)會(huì)了Altera公司許多開(kāi)發(fā)工具， 例如Quartus ，Qsys以及ARM公司的DS-5等，為我們的硬件 開(kāi)發(fā)和測(cè)試提供了很大的便利。
從入門FPGA開(kāi)發(fā)板，到現(xiàn)在基本完成預(yù)期作品，通過(guò) 這次比賽和這三個(gè)月的努力，我們團(tuán)隊(duì)的每個(gè)人都學(xué)到了很 多，我們都總結(jié)了許多解決問(wèn)題的方法，并養(yǎng)成了良好的文 檔習(xí)慣。在比賽過(guò)程中，我們采用多種途徑解決技術(shù)難題， 例如網(wǎng)絡(luò)、DE1-SoC的配套書籍、官方論壇以及開(kāi)發(fā)板的用 戶手冊(cè)和自帶例程,攻破設(shè)計(jì)難點(diǎn)。我們針對(duì)各個(gè)模塊制定 了多套方案，合理分析了設(shè)計(jì)的可行性，保證在實(shí)現(xiàn)基本功 能的基礎(chǔ)上再進(jìn)行優(yōu)化。在每一次實(shí)驗(yàn)中，我們將自己的收 獲寫進(jìn)文檔，然后與隊(duì)友進(jìn)行交流，分享心得，共同進(jìn)步。 當(dāng)然，我們必須感謝湖北大學(xué)—Altera公司EDA/SOPC聯(lián)合 實(shí)驗(yàn)室提供的豐富的硬件、軟件資源，同時(shí)還要感謝感謝 Altera和TERASIC公司為本課題提供的設(shè)計(jì)工具，包括大學(xué) 計(jì)劃所提供的學(xué)習(xí)資源、FPGA、軟件、開(kāi)發(fā)板、文檔支持 和參考設(shè)計(jì)。