基本信息
- 項目名稱：
- 遺傳算法解決走遍全中國問題
- 小類：
- 數(shù)理
- 大類：
- 自然科學類學術論文
- 簡介：
- 現(xiàn)如今旅游是人們緩解壓力，放松身心的主要途徑之一。本文以走遍全中國34個省會城市為例，通過建立湮滅遺傳算法模型，并經(jīng)過多次實驗，最終得到最優(yōu)的出行路徑，再通過權重計算、最大最小值定理和模糊矩陣，綜合各方面因素（出行費用、時間、舒適度和方便性等），得出目前最佳的旅行路徑和出行方式。為方便人們出行，提供了優(yōu)良的理論依據(jù)。
- 詳細介紹：
- 本文首先通過引入湮滅的思想來改進遺傳算法，建立了湮滅遺傳算法模型。湮滅的本質就是殺死遺傳算法在一定時間和空間內產(chǎn)生的局部最優(yōu)值，從而讓搜索跳出局部極值，讓遠離局部最優(yōu)的個體有充分的進化空間，從而搜索出更多的最優(yōu)解。然后根據(jù)湮滅思想編寫C語言源程序，并用mapgis軟件將全國34城市的經(jīng)緯度轉換為距離坐標，帶入VC++6.0運行求解，最后得到全國34城市TSP問題的近似最優(yōu)路線和總里程長度。 模型2運用C++編程，求得34個城市中每兩個城市之間的距離，再通過費用與里程的已知關系，求得每兩個城市間乘坐飛機、動車和快車臥鋪的實際費用，建立一個線性規(guī)劃模型，從而比較出每個區(qū)間段內的最經(jīng)濟乘坐方式，得到最經(jīng)濟的網(wǎng)上訂票方案。 模型3 中全面了考慮費用、時間、舒適度和方便性對旅途的影響，聯(lián)系題目要求，根據(jù)變量系數(shù)法，求得各個指標的權重。綜合考慮，引進“顧客接受度”這一概念來體現(xiàn)并比較各旅行方式的優(yōu)越性。并通過最大最小值定理和模糊矩陣來簡化計算。同時，本論文還結合我國現(xiàn)階段鐵路、航班未全面覆蓋，個別城市間不滿足評定關系等因素，對于特殊的地區(qū)，額外制定特殊的旅行路線和旅行方式，最終制定出最佳的旅行路線和旅行方式。 對兩城市間各種出行方式用時的定量分析需要大量的數(shù)據(jù)，文中使用的相關數(shù)據(jù)有較好的準確性，而在文中還利用所查數(shù)據(jù)進行了模型檢驗。因此，文中最后確定出的旅行路線標準具有一定的可靠性，對有關部門在制定最短旅行路線和旅客環(huán)游全國時起到一定的參考作用。在模型的修正過程中，引用了輪船這一出行方式，使整個旅程更加方便，快捷。
作品專業(yè)信息
撰寫目的和基本思路
- 走遍全中國是現(xiàn)在許多人的夢想。現(xiàn)如今旅游是人們緩解壓力，放松身心的主要途徑之一。本文以走遍全中國34個省會城市為例，通過建立湮滅遺傳算法模型，并經(jīng)過多次實驗，最終得到最優(yōu)的出行路徑，再通過權重計算、最大最小值定理和模糊矩陣，綜合各方面因素（出行費用、時間、舒適度和方便性等），得出目前最佳的旅行路徑和出行方式。為方便人們出行，提供了優(yōu)良的理論依據(jù)。
科學性、先進性及獨特之處
- 本文合理運用湮滅遺傳算法，對問題進行了科學的分析與鑒定。全面考慮費用、時間、舒適度和方便性對旅游的影響，綜合考慮，引進“顧客接受度”這一概念來體現(xiàn)并比較各旅行方式的優(yōu)越性。同時，本文還結合我國現(xiàn)階段鐵路、航班未全面覆蓋，個別城市間不滿足評定關系等因素，對特殊地區(qū)，額外制定特殊的路線和方式，最終制定出最佳的旅行路線和旅行方式。與部分實際數(shù)據(jù)比較，有良好的依據(jù)和實際應用價值。
應用價值和現(xiàn)實意義
- 本文所涉及的問題實際上是旅行商（traveling salesman problem 即TSP）問題，是一個NP（non-deterministic poly-nominal）難問題，即不能求出問題的最優(yōu)確切解。但本文在已知數(shù)據(jù)的基礎上，的除了最優(yōu)的出行路徑和出行方式。對人們的出行，有良好的指引作用。同時本文也可以應用于一些NP難問題，對許多世界上不能解決的問題，給予最合理的解決方案。
學術論文摘要
- 1、本文首先通過引入湮滅的思想來改進遺傳算法，建立了湮滅遺傳算法模型。湮滅的本質就是殺死遺傳算法在一定時間和空間內產(chǎn)生的局部最優(yōu)值，從而搜索出更多的最優(yōu)解。然后根據(jù)湮滅思想編寫C語言源程序，最后得到全國34城市TSP問題的近似最優(yōu)路線和總里程長度。 2、運用C++編程，求得34個城市中每兩個城市之間的距離，再通過費用與里程的已知關系，求得每兩個城市間乘坐飛機、動車和快車臥鋪的實際費用，建立一個線性規(guī)劃模型，從而比較出每個區(qū)間段內的最經(jīng)濟乘坐方式，得到最經(jīng)濟的網(wǎng)上訂票方案。 3、 中全面了考慮費用、時間、舒適度和方便性對旅途的影響，聯(lián)系題目要求，根據(jù)變量系數(shù)法，求得各個指標的權重。綜合考慮，引進“顧客接受度”這一概念來體現(xiàn)并比較各旅行方式的優(yōu)越性。并通過最大最小值定理和模糊矩陣來簡化計算。同時，本論文還結合我國現(xiàn)階段鐵路、航班未全面覆蓋，個別城市間不滿足評定關系等因素，對于特殊的地區(qū)，額外制定特殊的旅行路線和旅行方式，最終制定出最佳的旅行路線和旅行方式。
獲獎情況
- 2009年于沈陽農(nóng)業(yè)大學，榮獲東三省數(shù)學建模二等獎。 2009年于沈陽農(nóng)業(yè)大學，榮獲沈陽農(nóng)業(yè)大學數(shù)學建模比賽一等獎。
鑒定結果
- 申報類別：自然科學類（數(shù)理） 論文題目：遺傳算法解決走遍全中國問題 鑒定結果：內容真實，分析合理。優(yōu)
參考文獻
- 1. 2009年中國統(tǒng)計年鑒 [J].中國統(tǒng)計出版社 2. 旅客票價旅程區(qū)段 民用資源網(wǎng) 3. 全國主要城市經(jīng)緯度表 新浪網(wǎng) 4. 旅游的快捷性 中國民航網(wǎng) 5.劉青鳳，李 敏?；谶z傳算法的TSP問題優(yōu)化求解，(安陽工學院, 河南安陽455000) 6計算機與現(xiàn)代化雜志，文章編號: 100622475 (2008) 0220043202，2008年第2期 7.劉青鳳，李敏?；谶z傳算法的TSP問題優(yōu)化求解，(安陽工學院, 河南安陽455000)，計算機與現(xiàn)代化雜志，文章編號: 100622475 (2008) 0220043202，2008年第2期 8.遺傳算法_百度百科,百度網(wǎng)站，網(wǎng)址： 9.用遺傳算法解決旅行商問題，簡單代碼的網(wǎng)易博客，網(wǎng)址： 10.中國TSP問題，簡單代碼的網(wǎng)易博客，網(wǎng)址：
同類課題研究水平概述
- 旅行商問題（Traveling Salesman Problem，TSP）長期活躍于數(shù)學規(guī)劃領域，是組合優(yōu)化問題的典型代表。旅行商問題作為NP難問題的典型代表，下哦那個誕生以來一直都是計算機算法理論研究的熱點話題，各種針對該問題的算法層出不窮。理論與應用方面的雙重意義使得人們對它的研究興趣持續(xù)不減。TSP所具有的數(shù)學、計算機科學和運籌學特點使得其求解算法的發(fā)展推動著眾多領域的進步和發(fā)展。迄今為止，TSP的求解以取得了一些突破性的成果，然而作為NP難問題，圍繞著TSP還有很多問題沒有解決，還沒有通過的有效算法，計算規(guī)模也很有限。目前，求解TSP的主要方法包括近似算法、精確算法個針對特殊問題的求解算法。TSP問題是一個典型的組合優(yōu)化問題，一般很難精確地求出其最優(yōu)解，因而尋找出有效的近似求解算法就具有中有的意義。 以往對旅行商問題的解決，基本是單人或多人的旅行商問題，對單人多因素問題的研究先對較少。本文一用的遺傳算法在近年來逐漸引起了研究者的注意，由于隨著在交叉操作中多父輩的引入，降低了一些個體將自身復制到子代中的可能性，這就意味著多父輩交叉有利于提高遺傳算法的性能。 旅行商問題是一個典型的組合優(yōu)化問題，易于描述卻難于求解。對于大規(guī)模TSP問題，目前扔唯有非常有效的方法，如何快速有效的求解TSP問題，有著重要的理論價值和實際意義。
