畢業(yè)論文答辯

機(jī)器人路徑規(guī)劃蟻群算法姓名：陳俊吉指導(dǎo)老師：朱慶保研究?jī)?nèi)容螞蟻算法的基本原理各類蟻群算法的實(shí)施與比較機(jī)器人路徑規(guī)劃蟻群算法及其編程實(shí)現(xiàn)和仿真實(shí)驗(yàn)研究目標(biāo)及方法目標(biāo)：機(jī)器人在有障礙物的工作環(huán)境中工作時(shí)，通過(guò)兩組螞蟻相向搜索，優(yōu)化尋找出一條從給定起始點(diǎn)到終止點(diǎn)的較優(yōu)的運(yùn)動(dòng)路徑，使機(jī)器人在運(yùn)動(dòng)過(guò)程中能安全、無(wú)碰撞地繞過(guò)所有的障礙物，且所走路徑最短。方法：用兩組螞蟻分別以機(jī)器人出發(fā)點(diǎn)和目標(biāo)點(diǎn)為出發(fā)點(diǎn)，按照一定的概率搜索算法相向搜索。本課題要研究這一概率搜索算法及其編程實(shí)現(xiàn)，并用C語(yǔ)言給出仿真結(jié)果。螞蟻算法的基本原理生物學(xué)的研究表明：雖然單個(gè)螞蟻的能力非常有限，但多個(gè)螞蟻構(gòu)成的群體具有找到蟻穴與食物之間最短路徑的能力。這種能力是靠其在所經(jīng)過(guò)的路徑上留下的一種揮發(fā)性分泌物，即信息素(pheromone)來(lái)實(shí)現(xiàn)的。螞蟻在路徑上前進(jìn)時(shí)會(huì)根據(jù)前邊走過(guò)的螞蟻所留下的信息素選擇其要走的路徑，其選擇一條路徑的概率與該路經(jīng)上分泌物的強(qiáng)度成正比。因此，由大量螞蟻組成的群體的集體行為實(shí)際上構(gòu)成一種學(xué)習(xí)信息的正反饋現(xiàn)象：某一條路徑走過(guò)的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個(gè)體之間通過(guò)這種信息的交流尋求通向食物的最短路徑。

各類蟻群算法的實(shí)施與比較TSP問(wèn)題

即旅行商問(wèn)題，有n個(gè)城市，為旅行商選擇一條經(jīng)過(guò)各城市一次且僅一次的回路，使其路徑長(zhǎng)度最短。

AS算法與ACS改進(jìn)算法

體現(xiàn)在后續(xù)算法中，這里略算法分析

步驟1：在屏幕上畫一個(gè)10*10的柵格，格子的號(hào)碼從1到100。柵格障礙物的號(hào)碼隨機(jī)生成（設(shè)有20個(gè)障礙物），并按照生成的號(hào)碼在圖中用陰影表示。

步驟2：設(shè)定起點(diǎn)和終點(diǎn)的位置：begin=5,end=99。因?yàn)檎系K物是隨機(jī)生成的，所以設(shè)定的起點(diǎn)和終點(diǎn)有可能與障礙物的號(hào)碼沖突。為了避免出現(xiàn)這樣的情況，需用另外的函數(shù)來(lái)檢測(cè)，如果設(shè)定的起點(diǎn)或者終點(diǎn)恰好就是隨機(jī)生成的障礙物時(shí)，就要再重新設(shè)定起點(diǎn)和終點(diǎn)的方格號(hào)碼。為了便于后續(xù)距離的計(jì)算，將終點(diǎn)end轉(zhuǎn)換為橫縱坐標(biāo)：橫坐標(biāo)endx=(end-1)/Y+1；縱坐標(biāo)endy=(end-1)%Y+1。

算法分析

步驟3：初始化。將每?jī)蓚€(gè)方格之間的信息素初始化為一個(gè)很小的常數(shù)值：hormone[i][j]=hormone[j][i]=0.5;起點(diǎn)和終點(diǎn)處均放置一定數(shù)量的螞蟻（本程序中分別放兩只），并將它們固定地分配到起點(diǎn)和終點(diǎn)地四周（一個(gè)方格放一只）。對(duì)于每一只螞蟻，將它們所在的方格號(hào)碼加到禁忌表中。算法分析

步驟4：下一步要走的方格的選擇。每只螞