遺傳算法求解TSP的研究

周敏

摘 要：遺傳算法通常被認為是自適應的隨機搜索算法，與傳統的優化方法（枚舉，啟發式等）相比較，以生物進化為原型，具有很好的收斂性。文章用遺傳算法求解經典的旅行商問題，最后使用實驗對算法進行了測試，能夠在短時間內找到理想的解。

關鍵詞：遺傳算法；旅行商問題；遺傳；變異

1 意義和目標

文章提出用遺傳算法求解TSP這個古老而有挑戰性的NP問題，利用遺傳算法的原理對個城市進行編碼，從一組隨機產生的初始解開始搜索，種群中的每個染色體是問題的一個解的編碼串，這些染色體在后續迭代中不斷進化，運算過程中計算每個個體的適應度來衡量染色體的好壞。遺傳和變異過程中，根據選擇規則選擇部分后代，同時淘汰部分后代，最后算法收斂于最好的染色體，可能是TSP的最優解。

2 國內外研究現狀

目前對遺傳算法的研究大部分是從算子出發，提出各種雜交算子，但這些算子一般在實際使用中需要花費較大的工作量，比如已有的OX，PMX，SSX，ERX，CSEX和DPX等。還有其他一種變異算子，這種變異算子以顛倒作為基石，它的工作效率比較高，但也有自身的缺點，就是具有一定的隨機性，從而實現不了對團體中的個別的消息進行再次構建。所以，由Michalewicz和郭濤根據以上兩類算子的優缺點進行了結合，得到了一種比較適合的算子，這種算子叫做Inver-Over，這種算子能夠容易獲取，查找領域寬，它的基本思路是：旅行商問題的核心參數是城市之間的邊，卻不是這些城市的具地理位置?！?br>