混合遺傳算法解決旅行商問題的研究.pdf

1、旅行商問題是一個經典的NP難問題，一直是學者們研究的熱點，旅行商問題也被叫做“貨郎擔問題”，是指一個周游各地推銷貨品的商人，要找到路過所有計劃之中的城市一次并回到原點的最短路徑。旅行商問題被廣泛的應用在網絡路由、機器人控制、VLSI等問題中。
　　 遺傳算法以其優(yōu)良的性能，較好的健壯性和可移植性，成為了研究組合優(yōu)化問題中常用的算法。
　　 首先研究了旅行商問題的發(fā)展現狀和現行的解決方法，探討了多目標進化算法的分類和機制，

2、并給出了其中最具代表性算法的詳細描述。
　　 其次針對在傳統(tǒng)遺傳算法中所使用的交叉算子并不能很好的處理旅行商問題的個體，容易打亂基因片段順序，失去遺傳信息等問題，本文提出了一種新的交叉算子——基于連通子圖交叉，并且引入小生境操作、移民算法和局部搜索，融合成一種新的混合遺傳算法。通過實驗證明算法的求解效果好，收斂速度較快。
　　 最后著重研究了使用混合遺傳算法解決多目標旅行商問題。本文的混合遺傳算法以NSGA-II為框架，