[發明專利]求解旅行商問題的順序交叉多子代遺傳算法

在審

• 申請號: 201410740661.8
• 申請日: 2014-12-09
• 公開（公告）號: CN104463328A
• 公開（公告）日: 2015-03-25
• 發明（設計）人: 王吉權;田占偉;王福林;何夢瑩
• 申請（專利權）人: 東北農業大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明求解旅行商問題的順序交叉多子代遺傳算法，屬于應用人工智能技術領域。

背景技術

旅行商問題（Travelling?Salesman?Problem，簡稱TSP）是近代組合優化領域、數學領域中的著名問題之一。TSP問題的一般提法是：一個商人要到n個城市去推銷商品，n個城市中任意兩個城市之間的距離是已知的，該旅行商從某一城市出發，尋找一條可經由每個城市一次且僅一次，最后回到原出發城市，并使所走的路程最短的路線。TSP問題已經被證明是一個典型的NP難題。由于TSP問題具有形式簡單、易于理解等優點，在電網規劃、網絡優化、管道鋪設和物流調度等方面有著廣泛的應用。因此，求解TSP問題有著很高的實際應用價值。自1932年K.?Menger提出旅行商問題以來，該問題已經引起多個領域的許多學者的興趣，它是目前優化領域里研究的熱點問題。1985年，Goldberg和Grefenstette首次應用遺傳算法求解TSP問題。此后，許多學者對求解TSP的遺傳算法進行了改進，在一定程度上克服了算法的早熟收斂問題，而且算法的收斂速度也有一定程度的提高。

現有文獻中的遺傳算法每次迭代產生子代數量與父代相同，但在自然界中所有能夠生存和發展的種群，其父代產生子代的數量都遠遠多于父代個體的數量。基于這樣的事實，提出了基于順序交叉的多子代遺傳算法，并用其求解TSP問題。所謂的多子代遺傳算法是指交叉產生的子代個體數量多于父代個體數量的遺傳算法。順序交叉多子代遺傳算法通過順序交叉產生的子代個體數量多于父代個體數量，使得種群內的競爭加劇。在種群內的競爭過程中，優秀的個體具有較強的生命力，容易存活下來，而具有較低生存能力的個體則被淘汰，從而使物種逐漸地向適應于生存環境的方向進化，進而產生更優良的物種。因此，求解TSP問題的順序交叉多子代遺傳算法可提高算法的收斂速度。

發明內容

針對現有運用遺傳算法求解旅行商問題存在的問題，本發明對現有遺傳算法進行改進，提出了一種求解旅行商問題的順序交叉多子代遺傳算法。求解旅行商問題的順序交叉多子代遺傳算法與現有求解旅行商問題的遺傳算法相比，其顯著特征在于：其一，進化策略不同。順序交叉多子代遺傳算法的交叉概率為1。其二，交叉后產生的子代數量不同。順序交叉多子代遺傳算法交叉產生的子代數量明顯多于現有求解旅行商問題的遺傳算法。這種求解旅行商問題的順序交叉多子代遺傳算法產生優秀個體的可能性增加，因而可提高算法的收斂速度。

求解旅行商問題的順序交叉多子代遺傳算法，其特征在于，具體包括以下幾個步驟：

步驟一：順序交叉多子代遺傳算法的理論基礎。

????（1）生物學理論基礎

現有文獻中求解TSP問題的遺傳算法，都是一對父代產生一對子代。而在生物進化的過程中，通常一對父代繁殖的子代個數多于兩個，這樣的物種在進化過程中不但能夠很好的生存下來，而且能夠使物種得到進化，從而得到更優良的物種；而一對父代繁殖的子代個數小于等于兩個的物種實際上是不存在的，即使存在這樣的物種，在進化的過程中，由于疾病、食物等因素的影響，最終也會滅絕。另外，當某一種群內部的子代個體數量多于父代時，種群內個體的數量增加，促使種群內部的競爭加劇，由于種群內部的優秀個體具有較強的生存能力，容易存活下來，而具有較低生存能力的個體則被淘汰，從而使物種逐漸地向適應于生存環境的方向進化，進而產生更優良的物種。因此，自然界中的物種在進化過程中，子代個體的數量應該多于父代個體的數量。

（2）數學生態學理論基礎

為了說明生物滅種的概率，我們假設一個種群開始只有一個個體，在某一時間t其大小將為0的概率是

（1）

式中，i是初始種群數量，是死亡率，λ是生殖率。

如果初始大小為i的種群隨著時間的流逝而滅種，則i個獨立的家系都已經死光，即對于任意的i，這種情況發生的概率是

（2）

要求出種群最終滅種的概率，必須讓t趨于無窮。故對式（2）我們分三種情況討論：

①?當生殖率小于死亡率時，即?時

顯然，在式（2）中指數項隨而變為0，因此可得：

（3）

概率為1，說明生物最終一定會滅種，顯然這種種群不可能無限地延續下去。

②?當生殖率大于死亡率時，即時

則當時，式（2）可化為

（4）