基于遺傳算法的最短路徑問題研究.pdf

1、最短路徑問題是傳統(tǒng)的組合優(yōu)化問題之一，并且在實際應(yīng)用中較為常見，例如車輛導(dǎo)航問題和網(wǎng)絡(luò)路由問題。最短路徑問題的有很多種類，例如靜態(tài)的最短路徑問題、動態(tài)最短路徑問題、單目標(biāo)最短路徑問題和多目標(biāo)最短路徑問題等。本文研究了動態(tài)最短路徑問題、多目標(biāo)最短路徑問題和動態(tài)環(huán)境下的多目標(biāo)最短路徑問題，并將傳統(tǒng)優(yōu)化方法和演化求解算法結(jié)合，提出了兩者結(jié)合的演化求解算法。本文主要工作如下所示。
　　(1)對于靜態(tài)網(wǎng)絡(luò)中的最短路徑問題，有很多確定性的求解

2、算法。在靜態(tài)的網(wǎng)絡(luò)拓?fù)渲?，這些確定性的算法表現(xiàn)良好。但是當(dāng)環(huán)境動態(tài)變化時，這些算法需要重新執(zhí)行，而環(huán)境通常是局部變化的，因此這些確定性的算法不是很高效。本文提出了一個帶有四個局部路徑替換策略的解決動態(tài)最短路徑問題的遺傳算法。這些局部路徑替換策略是由Dijkstra的最短路徑算法所啟發(fā)，并且在環(huán)境發(fā)生改變的時候進(jìn)行調(diào)用來產(chǎn)生一些局部最短路徑樹。并且在種群進(jìn)化時，這些保存的局部最短路徑樹用來增強個體的性能。實驗表明，所提出的算法可以快速得到

3、適應(yīng)新環(huán)境的解，并產(chǎn)生高質(zhì)量的個體。
　　(2)實際生活中，有些問題是多目標(biāo)的，并且不同的目標(biāo)之間具有一定的沖突性。對于多目標(biāo)的最短路徑問題，每條邊帶有多個目標(biāo)，該問題旨在求解從源點到終點的非支配路徑集。在本文中，采用了將傳統(tǒng)方法和演化算法結(jié)合的思想，算法的主體采用NSGA-Ⅱ，結(jié)合第k短路徑算法，提出了KSPNSGA。該方法使用加權(quán)求和法將每條邊上不同的目標(biāo)值加權(quán)求和得到一個新的目標(biāo)值，并且求解該目標(biāo)值構(gòu)成的新圖中的第k短路徑。