K最短路徑問題的研究與應用.pdf

1、k最短路徑問題是最短路徑算法的重要分支，也是圖論和網(wǎng)絡優(yōu)化研究的主要問題之一。在不同的情況下，我們除了要考慮最短路徑問題外，還有可能需要考慮次短路，次次短路...，即尋求網(wǎng)絡中起點到終點之間的多個備選優(yōu)化路徑，所以研究k最短路徑算法問題不僅具有理論價值，而且也具有很大的實用價值。
　　本文對傳統(tǒng)的群智能進行改進來求解k最短路問題，主要內容如下：
　　1.通過研究蛙跳算法，針對其種群分割方式不合理會影響收斂速度的問題，提出一種

2、新的種群分割方式，同時結合Yen算法的偏離路徑思想提出一種新的學習策略，使得該算法可以用于求解k最短路經(jīng)問題。仿真結果表明提出的新算法是可行的，在尋優(yōu)精確度、時間效率的比較上均優(yōu)于標準遺傳算法。
　　2.提出了一種基于遺傳算法k最短路徑問題的混合遺傳算法，該算法思想是重新定義一種染色體編碼方式，交叉率和變異率采用同時采用自適應規(guī)則提出k最短路徑問題的混合遺傳算法。通過重新構造的交叉率和變異率的公式，加快了算法收斂速度，同時結合模擬