目錄
1 概述
2 旅行商問題
3 遺傳算法
4 限制優化
5 帶有罰方法的遺傳算法的流程圖
6 帶有懲罰函數的遺傳算法在TSP中的應用
7 運作結果
7.1 單旅行商問題
7.2 多旅行商問題
8 參考文獻
9 Matlab代碼實作
1 概述
主要研究用遺傳算法解決帶有限制的TSP的方法。使用貪婪交叉算子、自适應變異算子和帶有精英保留政策的選擇算子相結合對基本遺傳算法進行了改進,針對實際TSP中的限制條件讨論了罰方法在遺傳算法中的應用,提出了自适應的懲罰函數,并将其與改進後的遺傳算法相結合,解決了帶有時間限制的TSP。通過對實驗結果的比較分析,證明了該方法的可行性和有效性。
2 旅行商問題
3 遺傳算法
遺傳算法是1975年由John Holland教授提出。它借用了仿真生物遺傳學和自然選擇機理,通過自然選擇、交叉、變異等機制實作各個個體适應性的提高。遺傳算法在整個進化過程中的遺傳操作是随機的;但是它呈現出來的特性卻并不是完全随機的,它能夠有效地利用曆史資訊使得下一代群體性能有所提高,一代一代不斷進化,最終收斂到一個即使不是最優解,也是離最優解非常接近的解空間上。遺傳算法涉及到編碼方式、初始種群、适應度函數、遺傳算子和控制參數五大要素。
基本遺傳算法雖然具有全局搜尋能力,但是在進化過程中往往容易出現收斂速度緩慢或不收斂,又或陷入局部最優的情況,加快收斂速度又有可能出現早熟現象,過或不及都不能及時準确地獲得最優解。是以,學者們在這些方面進行了大量的研究,希望既能加快收斂速度,又能防止早熟收斂。
4 限制優化
5 帶有罰方法的遺傳算法的流程圖
6 帶有懲罰函數的遺傳算法在TSP中的應用