碩士學(xué)位論文：機(jī)器人路徑規(guī)劃螞蟻算法

畢業(yè)論文答辯

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

各類蟻群算法的實施與比較TSP問題

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

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

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

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

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

算法分析

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

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