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