基于元胞遺傳算法的避障路徑規(guī)劃

1、學(xué)校代碼：10406分類號：TP301.6 學(xué) 號：080081002007南昌航空大學(xué) 南昌航空大學(xué)碩 士 學(xué) 位 論 文（學(xué)位研究生）基于元胞遺傳算法的避障路徑規(guī)劃 基于元胞遺傳算法的避障路徑規(guī)劃碩士研究生： 李建建導(dǎo) 師： 周之平博士申請學(xué)位級別：碩 士學(xué)科、專業(yè)： 信號與信息處理所在單位： 信息工程學(xué)院答辯日期： 2012 年 5 月授予學(xué)位單位：南昌航空大學(xué)I摘 摘 摘 摘 要 要 要 要路徑規(guī)劃技術(shù)是指在具有障礙物的環(huán)境中，

2、按照某一特定的評價(jià)標(biāo)準(zhǔn)，尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)無碰撞路徑。路徑規(guī)劃技術(shù)已經(jīng)被廣泛應(yīng)用于機(jī)器人，超大規(guī)模集成電路設(shè)計(jì)，地理信息系統(tǒng)和導(dǎo)航系統(tǒng)等領(lǐng)域。迄今為止，在移動(dòng)機(jī)器人路徑規(guī)劃方面國內(nèi)外呈現(xiàn)出大量的研究成果，主要方法有：梯度下降法、動(dòng)態(tài)規(guī)劃算法、A*算法、圖論算法、人工勢場法、模擬退火法、禁忌搜索法、人工神經(jīng)網(wǎng)絡(luò)法和群體智能優(yōu)化算法，如遺傳算法、蟻群算法、粒子群算法等。遺傳算法作為群體智能算法的重要分支之一，以達(dá)爾文的自然選

3、擇學(xué)說為基礎(chǔ)，通過遺傳操作產(chǎn)生子代群體，并按照優(yōu)勝劣汰的原則指導(dǎo)種群進(jìn)化，它具有較強(qiáng)的全局尋優(yōu)能力。將遺傳算法用于求解路徑規(guī)劃問題，近年來引起了國內(nèi)外研究學(xué)者的廣泛關(guān)注，也取得了一定的研究成果。采用傳統(tǒng)遺傳算法進(jìn)行路徑規(guī)劃時(shí)，對間斷無障礙路徑進(jìn)行插入修復(fù)很難保證解的可行性，并且由于選擇壓力的影響，算法易陷入局部最優(yōu)。為此， 本文提出一種基于 Moore 鄰居統(tǒng)計(jì)模型的可行路徑生成算法，并在此基礎(chǔ)上利用元胞遺傳算法進(jìn)行路徑規(guī)劃，以提高算法

4、性能。元胞遺傳算法將元胞空間結(jié)構(gòu)和元胞狀態(tài)轉(zhuǎn)換規(guī)則與遺傳操作相結(jié)合，將遺傳算法種群中的個(gè)體視為一個(gè)獨(dú)立元胞，所有個(gè)體被隨機(jī)映射到同等規(guī)模的二維元胞空間中，通過元胞鄰域內(nèi)的遺傳操作和元胞演化規(guī)則進(jìn)行進(jìn)化，直至滿足終止條件為止。元胞遺傳路徑規(guī)劃算法在局部優(yōu)化的同時(shí)保持了群體的多樣性，進(jìn)而在一定程度上克服了算法的早熟收斂。結(jié)合 Visual C++ 6.0 和 Matlab 7.0 混合編程建立路徑規(guī)劃仿真平臺，在不同障礙物配置環(huán)境下對本文算