Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/18197
標題: 優生遺傳演算法應用於解旅行推銷員問題
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.
URI: http://hdl.handle.net/11455/18197
Appears in Collections:應用數學系所

Show full item record
 

Google ScholarTM

Check


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