鄰域可視性相關(guān)的路徑規(guī)劃問題研究.pdf

1、基于可視性分析的最優(yōu)路徑問題是一種以地形可視性信息為主要代價的最優(yōu)路徑搜索，屬于空間決策支持范疇，在理論研究和實(shí)際應(yīng)用兩方面都有重要意義。在傳統(tǒng)基于可視性分析的最優(yōu)路徑問題中，影響通行能力的可視性代價信息通常都是互不相關(guān)的0維數(shù)值，而互不相關(guān)的0維代價不能反映三維地形上不同點(diǎn)視域的重疊特征。本文采用二維視域描述三維地形的可視性信息，提出基于柵格鄰域可視性相關(guān)的最優(yōu)路徑問題。路徑總的可視性信息由所有路徑點(diǎn)的視域融合求得，即為路徑可視覆蓋。

2、根據(jù)路徑可視覆蓋最優(yōu)和路徑長度最優(yōu)兩個目標(biāo)將最優(yōu)路徑問題分為：(1)全區(qū)域可視覆蓋最短路徑，(2)可視覆蓋最小最短路徑，(3)平均視距最大可視覆蓋路徑，(4)平均視距最小可視覆蓋路徑等。
　　 本文針對這四類問題進(jìn)行深入研究，通過對各類問題本質(zhì)的分析，以及對當(dāng)前國內(nèi)外進(jìn)化算法領(lǐng)域研究熱點(diǎn)的追蹤，確定了解決各類問題的研究方向和總體思路。在此基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了針對每類問題的新算法。
　　 (1)對于柵格地形上視域覆蓋整個

3、地形的最小可視覆蓋問題，針對現(xiàn)有方法時間復(fù)雜度高以及不能實(shí)現(xiàn)全覆蓋的問題，根據(jù)鄰近地形點(diǎn)視域的重疊特性，提出了一個以累積可視性為啟發(fā)信息的新方法，稱為反向累積可視去冗余法(RVRR)。通過去除冗余地形觀察點(diǎn)，以較低的時間復(fù)雜度得到了覆蓋整個地形的近似最小數(shù)量的觀察點(diǎn)集。與傳統(tǒng)的貪婪算法相比，該方法在解的質(zhì)量與算法效率上都有了明顯提高。
　　 (2)以RVRR方法獲得的覆蓋整個地形的觀察點(diǎn)集為基礎(chǔ)，進(jìn)一步提出了結(jié)合分而治之思想的

4、兩級進(jìn)化算法，獲得近似最優(yōu)的全區(qū)域可視覆蓋路徑。首先把觀察點(diǎn)分為若干簇，每個簇所在的位置稱為子區(qū)，通過第一級遺傳算法得到遍歷子區(qū)的最優(yōu)順序，而后通過第二級多種群進(jìn)化算法分別得到連接每個子區(qū)中觀察點(diǎn)的最短路徑段。根據(jù)子區(qū)遍歷順序，連接各路徑段形成覆蓋整個地形的完整路徑。這種方法不僅能夠高效獲得覆蓋整個地形的最優(yōu)路徑，而且易于擴(kuò)展到多條路徑協(xié)同對地形進(jìn)行可視覆蓋的情況。
　　 (3)詳細(xì)分析了以平均視距最優(yōu)為目標(biāo)的路徑搜索問題，給

5、出了該類問題的兩個基本性質(zhì)并進(jìn)行了證明：平均視距最優(yōu)的路徑搜索是柵格地形上一類存在負(fù)權(quán)弧但沒有負(fù)權(quán)環(huán)的最優(yōu)路徑問題；平均視距最優(yōu)的路徑搜索不滿足最優(yōu)化原理。
　　 (4)通過對混合單目標(biāo)進(jìn)化算法的研究，設(shè)計(jì)了搜索平均視距最大路徑的混合進(jìn)化算法框架。采用變長染色體結(jié)構(gòu)，并對關(guān)鍵點(diǎn)數(shù)的范圍進(jìn)行限定，既節(jié)省了時間與空間，又保證了染色體的靈活多樣。同時通過自適應(yīng)調(diào)整變異算子，使得算法能夠快速搜索到近似最優(yōu)解。算法在保持穩(wěn)定性的同時，在

6、解的質(zhì)量與搜索效率上都比模擬退火算法有較大的改進(jìn)。
　　 (5)分析了可視覆蓋最小最短路徑問題，是一類特殊類型的雙權(quán)最短路徑，屬于多目標(biāo)組合優(yōu)化問題。通過對混合多目標(biāo)進(jìn)化算法的研究，設(shè)計(jì)了解決可視覆蓋最小最短路徑問題的混合多目標(biāo)進(jìn)化算法框架。除變長染色體結(jié)構(gòu)和自適應(yīng)變異算子外，設(shè)計(jì)了多級鄰域結(jié)構(gòu)，采用可變鄰域搜索做為局部搜索器。另外，設(shè)計(jì)了以視域大小為索引的外部archive，保留進(jìn)化過程和局部搜索過程中產(chǎn)生的更優(yōu)的解。算法獲

7、得的解比已知的通用多目標(biāo)算法NSGA-II更接近真實(shí)的Pareto前沿。
　　 (6)采用超體積和archive的種群更新策略，設(shè)計(jì)了基于超體積的多目標(biāo)進(jìn)化算法(HCEA)解決可視覆蓋最小最短路徑問題。另外把所設(shè)計(jì)的進(jìn)化算法基本要件嵌入NSGA-II和SMS-EMOA算法的框架中，使其適于解決可視覆蓋最小最短路徑問題，并且與HCEA方法具有可比性。實(shí)驗(yàn)表明，我們的方法在超體積測度上優(yōu)于其它兩個方法，而且所得的結(jié)果具有更接近于視