[發(fā)明專利]基于改進(jìn)粒子群算法的多路徑規(guī)劃方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410162014.3
• 申請(qǐng)日: 2014-04-21
• 公開（公告）號(hào): CN104063745B
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 張雪潔;嚴(yán)祥光;周文歡;蔣悅達(dá)
• 申請(qǐng)（專利權(quán)）人: 河海大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙)32204
• 代理人: 李玉平

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于改進(jìn)粒子群算法的多路徑規(guī)劃方法。

背景技術(shù)

多路徑規(guī)劃問(wèn)題，即多旅行商問(wèn)題是經(jīng)典旅行商問(wèn)題的一種泛化，加上某些特定的附加條件，則能夠演化成一些較現(xiàn)實(shí)的問(wèn)題，因而具有較高的理論研究和應(yīng)用價(jià)值。在多旅行商問(wèn)題中，一個(gè)任務(wù)由多位旅行商共同完成，其問(wèn)題的求解難度較經(jīng)典旅行商問(wèn)題更大，用于經(jīng)典旅行商問(wèn)題求解的方法或策略不能簡(jiǎn)單地應(yīng)用于多旅行商問(wèn)題的求解，有關(guān)該問(wèn)題的研究成果遠(yuǎn)比經(jīng)典旅行商問(wèn)題少，現(xiàn)有計(jì)算多路徑的方法是通過(guò)增加虛擬城市，將所有城市隔開，轉(zhuǎn)化為單路徑來(lái)計(jì)算。轉(zhuǎn)化之后的單路徑問(wèn)題有許多限制條件，算法復(fù)雜并且效率低下，而且不能解決有多個(gè)出發(fā)城市的多旅行商問(wèn)題，而實(shí)際中的路徑規(guī)劃通常出發(fā)點(diǎn)都不只一個(gè)。

粒子群算法，也稱粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)，是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化算法(Evolutionary Algorithm-EA)，是解決多路徑規(guī)劃問(wèn)題的有效方法之一。PSO算法屬于進(jìn)化算法的一種，從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，它是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)，通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。這種算法具有實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)，但也仍有容易陷入局部最優(yōu)解導(dǎo)致“早熟”的缺點(diǎn)。

發(fā)明內(nèi)容

發(fā)明目的：針對(duì)現(xiàn)有的多路徑規(guī)劃問(wèn)題計(jì)算方法的不足，本發(fā)明提供一種基于改進(jìn)粒子群算法的多路徑規(guī)劃方法，在前人對(duì)粒子群算法做出的改進(jìn)的基礎(chǔ)上做了進(jìn)一步的改進(jìn)，有效的跳出局部最優(yōu)解，避免“早熟”，克服了粒子群算法本身的缺點(diǎn)，用于解決路徑規(guī)劃問(wèn)題取得了良好的效果。

技術(shù)方案：一種基于改進(jìn)粒子群算法的多路徑規(guī)劃方法，首先根據(jù)實(shí)際需求，對(duì)城市數(shù)據(jù)進(jìn)行預(yù)處理。分如下兩種情況：

a對(duì)于只有一個(gè)出發(fā)城市的多路徑問(wèn)題，如果要計(jì)算出首發(fā)相連的N條路徑，這N條路徑除了出發(fā)城市相同外其余經(jīng)過(guò)的城市各不相同，但覆蓋所有城市，則需增加N個(gè)與出發(fā)城市位置相同的虛擬城市。

b對(duì)于出發(fā)城市互不相同的多路徑問(wèn)題，則不需要進(jìn)行預(yù)處理。

然后使用上述求解旅行商問(wèn)題的算法計(jì)算出一條城市序列X＝(x₁,x₂,…,x_i,x_v1,x_j,…,x_k,x_v2,x_l,…,x_n)。(假設(shè)需要計(jì)算兩條路徑，其中x_v1和x_v2代表兩個(gè)虛擬城市或者出發(fā)城市)

最后將算出來(lái)的城市序列看成首尾相連的環(huán)狀。城市序列中只要遇到虛擬城市或者出發(fā)城市就代表回到上一個(gè)出發(fā)城市，這樣將環(huán)分割成多條路徑，X₁＝(x_v1,x_j,…,x_k,x_v1)，X₁＝(x_v2,x_l,…,x_n,x₁,x₂,…,x_i,x_v2)，得到最終需要的多條路徑。

本發(fā)明在前人解決單路徑規(guī)劃中對(duì)粒子群算法做的改進(jìn)的基礎(chǔ)上，融合貪心算法、遺傳算法和模擬退火算法的思想，使用貪心算法初始化粒子群算法，并且加入一種良好的變異算子與模擬退火思想。變異能夠解開計(jì)算出來(lái)的路徑中有交叉的地方，大大增加了算法找到最優(yōu)解的概率；模擬退火增大了搜索最優(yōu)解的范圍，避免陷入局部最優(yōu)解。這些改進(jìn)使得改進(jìn)后的粒子群算法能夠有效的跳出局部最優(yōu)解，避免“早熟”，克服了粒子群算法本身的缺點(diǎn)，用于解決路徑規(guī)劃問(wèn)題取得了良好的效果。

傳統(tǒng)計(jì)算多路徑是通過(guò)增加虛擬城市，將所有城市隔開，轉(zhuǎn)化為單路徑來(lái)計(jì)算。要計(jì)算N條路徑，需要增加N-1個(gè)與出發(fā)城市位置相同的虛擬城市，路徑中只要遇到虛擬城市就代表回到出發(fā)城市，最后一個(gè)城市之后也回到出發(fā)城市，這樣將多路徑問(wèn)題轉(zhuǎn)化為單路徑問(wèn)題計(jì)算。這樣的處理方法有很多邊界情況需要考慮，例如要保證每次迭代算出的路徑中第一個(gè)城市為出發(fā)城市等。并且不能用于計(jì)算出發(fā)城市不相同的多路徑。