基于ＨＧＡ的較小旅行時間多旅行商問題研究

摘　　　要：為了解決較小化旅行時間的多旅行商一類問題，提出了一種遞階遺傳算法和矩陣解碼方法。該算法根據問題的特點，采用一種遞階編碼方案，此編碼與多旅行商問題一一對應。用遞階遺傳算法優化多旅行商問題不需設計專門的遺傳算子，操作簡單，并且解碼方法適于求解距離矩陣對稱和距離矩陣非對稱的多旅行商問題。計算結果表明，遞階遺傳算法是有效的，能適用于優化較小化完成時間的多旅行商問題。

關　鍵　詞：遞階遺傳算法；多旅行商問題；較小完成時間；解碼方法

引　     言：旅行商問題（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，ＴＳＰ）是一個典型的組合優化難題，它在許多領域都有著廣泛的應用，已被證明屬于ＮＰ問題［１］。有關ＴＳＰ問題的研究在現實問題中有很大的使用價值。諸如：交通運輸、管道鋪設、路線的選擇、計算機網絡的拓撲設計、郵遞員送信等，都可抽象成ＴＳＰ或ＭＴＳＰ問題［２�玻担�。為了有效地解決較小旅行時間、距離矩陣對稱或者非對稱的多旅行商問題，本文提出了一種遞階遺傳算法（ＨｉｅｒａｒｃｈｉｃａｌＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＨＧＡ）和矩陣解碼方法，以便確定每個城市由哪個旅行商經過以及各個旅行商的行走路線，即找到一個較優旅行商分配及行走路線，在各旅行商行走完后，使耗用時間較大的那個旅行商的時間較小。仿真結果證明，本文提出的算法魯棒性好、運行效率高，具有實際應用的價值。

登錄網站后可下載文件

相關閱讀:

• ...2012/03/15 14:37·基于ＨＳ�玻校樱纤惴ǖ模校桑目刂破鲄�數自整定