速解魔方機器人(下)

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

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

2.初始化微粒群

圖19　CCD攝像頭    

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

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

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

其中，tk,p指訓練樣本P在K輸出端的給定輸出，則適應度函數定義如下：

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

5.算法終止條件

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

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

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

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