K最短路徑問(wèn)題的研究與應(yīng)用.pdf

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

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