Please use this identifier to cite or link to this item:
標題: 優生遺傳演算法應用於解旅行推銷員問題
An Eugenic Genetic Algorithm for the Traveling Salesman Problem
作者: 于正之
Yu, Jenq Jy
關鍵字: Genetic algorithm
Eugenic strategy
Traveling salesman problem
Sequence preserving crossover
Shift mutation
出版社: 應用數學系
摘要: 中 文 摘 要 本論文旨在闡述如何提昇遺傳演算法的搜尋能力,並且 能夠實際應用於旅行推銷員問題。傳統的遺傳演算法是一種強迫式的搜尋 方法,它能改善以往以數學演算法難以解決的問題,透過大量的演化程序 ,使其適用在不同領域裡的複雜搜尋。然而遺傳演算法也有一些長久以來 困擾的限制,當問題的搜尋空間特別巨大時,將使它無法正確地找到所需 要的最佳解。因此我們提出了優生遺傳演算法,使它能靠著優生政策的引 導,往正確的方向快速搜尋好的解答,而又不致陷入陷阱之中。優生政策 能夠使傳統的遺傳演算法提昇效能與效率。 在實際的應用上,我們用 優生遺傳演算法來解決旅行推銷員這個NP-hard 的問題,並且提出了針對 旅行推銷員問題所設計的交配及突變運算元。本論文中,共實驗了四種不 同類型的旅行推銷員問題,比較以往所知的眾多文獻,我們的結果都能得 到較好解答。
Abstract The major goal of this thesis is to discuss how to improve thesearching power of the genetic algorithm. The traditional geneticalgorithms are robust search procedures and can be used to solve complex search problems in a large number of different disciplines.However, it has difficulty in finding the optimal solution on sometypes of problems especially when the solution space is large. Sowe propose the eugenic genetic algorithm which always searches forand retains the better solutions by eugenic strategy, which makesthe searching more effective and efficient. In this thesis, we apply the eugenic genetic algorithm for thetraveling salesman problems, which is an NP-hard problem. We alsopropose some new operators for TSP. The experiment results of fourtypes of TSP instances show that on method can obtain better solutions in comparison with other methods.
Appears in Collections:應用數學系所



Show full item record
TAIR Related Article

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.