旅游線路優(yōu)化設(shè)計開題報告

《旅游線路優(yōu)化設(shè)計開題報告》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、開題報告旅游線路優(yōu)化設(shè)計一、選題的背景、意義隨著科技的不斷發(fā)展和進(jìn)步，現(xiàn)在的計算機(jī)越來越趨向于智能化發(fā)展，未來將會出現(xiàn)許多智能的計算機(jī)，這些智能機(jī)器功能各異，能夠滿足人們對生活和應(yīng)用的需求，一些現(xiàn)實(shí)問題可以在電腦上解決。旅游線路優(yōu)化也叫巡回旅行商問題（TravelingSalesmanProble-m,TSP），也稱為貨郎擔(dān)問題[1-3]。它是一個較古老的問題，最早可以追溯到1759年Euler提出的騎士旅行問題。貨郎擔(dān)問題可以解釋為，一位推銷員從自己所在城市出發(fā)，必須遍訪所有城市且每個城市只能訪問一次之后又返回到原來的

2、城市，求使其旅行費(fèi)用最小（或旅行距離最短）的路徑。1948年，由美國蘭德公司推動，TSP成為近代組合優(yōu)化領(lǐng)域的一個典型難題。它是一個具有廣泛應(yīng)用背景和重要理論價值的組合優(yōu)化問題。TSP的搜索空間隨著城市規(guī)模數(shù)n的增加而增大，這類組合優(yōu)化問題稱之為NP完全問題。在如此龐大的搜索空間中尋求近似最優(yōu)解，對于常規(guī)方法和現(xiàn)有的計算工具而言，存在著諸多的計算困難。因此，借助遺傳演化算法，模仿大自然界生物的繁殖、雜交及其變異的演化過程來解決TSP問題，顯得非常必要?；谝陨显?，本人采用經(jīng)典遺傳算法理論及個體實(shí)數(shù)編碼方法設(shè)計了此算法，

3、試圖進(jìn)一步探索TSP組合優(yōu)化問題的有效解決方案。與其他的算法相比，遺傳算法與之在本質(zhì)上有著不同之處：遺傳算是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。旅游線路優(yōu)化設(shè)計，能讓旅客在遍歷所有景點(diǎn)的情況下，讓旅行的開銷實(shí)現(xiàn)最小化。二、研究的基本內(nèi)容與擬解決的主要問題本課題是設(shè)計現(xiàn)實(shí)旅游線路優(yōu)化。根據(jù)一個區(qū)域內(nèi)全部景點(diǎn)的地理分布，以及各個景點(diǎn)之間的旅行開銷，在實(shí)現(xiàn)所有景點(diǎn)遍歷的前提下，達(dá)到旅行開銷最小化。鑒于傳統(tǒng)搜索方法難以解決復(fù)雜和非線性問題的原因，要求在設(shè)計中運(yùn)用遺傳

4、算法（GA）這一借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。具體來說，本課題要研究的是如何運(yùn)用遺傳算法的相關(guān)知識來對一個區(qū)域的所有景點(diǎn)進(jìn)行排序，使得線路最短。本系統(tǒng)要解決的主要問題：[4,5]（1）初始化種群。（2）選擇。（3）交叉。（4）變異。（5）終止。三、研究的方法與技術(shù)路線、研究難點(diǎn)，預(yù)期達(dá)到的目標(biāo)1.研究方法主要指收集、鑒別、整理文獻(xiàn)，并通過對文獻(xiàn)的研究，形成對事實(shí)科學(xué)認(rèn)識的方法。該方法主要用于系統(tǒng)開發(fā)的前期。首先，通過閱讀大量遺傳算法的文獻(xiàn)和關(guān)于本實(shí)驗(yàn)的一些資料，結(jié)合現(xiàn)實(shí)進(jìn)行對比看哪個比較簡單，總結(jié)個步

5、驟的基本功能及不足。以此確定畢業(yè)設(shè)計的基本方法。然后，根據(jù)相關(guān)文獻(xiàn)，對程序進(jìn)行需求分析和可行性分析，從而確定自己的研究方向和實(shí)現(xiàn)方法。運(yùn)用Java的面向?qū)ο笏枷雽⑾到y(tǒng)實(shí)現(xiàn)。面向?qū)ο蟪绦蛟O(shè)計（OOP）就是使用對象進(jìn)行程序設(shè)計，對象代表現(xiàn)實(shí)世界中可以明確標(biāo)識的一個實(shí)體。在windows操作系統(tǒng)平臺下，運(yùn)用Java的相關(guān)開發(fā)平臺，把系統(tǒng)的功能設(shè)計出來，然后用Java的相關(guān)技術(shù)來實(shí)現(xiàn)。2.技術(shù)路線技術(shù)路線圖如下圖所示。遺傳算法是通過借鑒生物界自然選擇和自然遺傳機(jī)制而產(chǎn)生的一種計算方法I與其他的優(yōu)化算法一樣，遺傳算法也是一種迭代算

6、法，從選定的初始解出發(fā)，通過不斷地迭代，逐步改進(jìn)當(dāng)前解，直到最后搜索到最優(yōu)解或滿意解。其迭代過程是從一組初始解（群體）出發(fā)，采用類似于自然選擇和有性繁殖的方法，在繼承原有優(yōu)良基因的基礎(chǔ)上生成具有更好性能的下一代解的群體，遺傳算法的運(yùn)算過程為：對給定問題，給出變量的編碼方法，定義適應(yīng)度函數(shù)。①初始化。令:t=0，給出交叉概率Pc,及變異概率Pm，隨機(jī)生成M個個體作為初始群體P（0）；②個體評價。計算P（t）中各個體的適應(yīng)度；③選擇。對群體P（t）進(jìn)行選擇操作，得到中間群體；④交叉。把交叉操作作用于中間群體。⑤變異。把變異操

7、作作用于交叉之后所得到的群體，則得到第（t+1）代群體P（t+1）；⑥若沒有到達(dá)終止條件是，則令t=t+1，否則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解，運(yùn)算停止[6-8]。1）初始化群體。在初始化群體之前，需要確定變量的編碼方法及適應(yīng)度函數(shù)。在遺傳算法界有一個共識：旅行的二進(jìn)制表達(dá)對TSP不是最適合的，這里以城市的遍歷次序作為算法編碼，即（i1,i1,i3…in）是{1，2，…n}的全排列。2）個體適應(yīng)度計算，計算個體的適應(yīng)度，即與種群中某一個個體r相對應(yīng)的哈密頓圈長的倒數(shù)。3）比例選擇操作。具體執(zhí)行過程為：

8、①計算種群中所有個體的適應(yīng)度總和；②計算每個個體的相對適應(yīng)度大小，即各個個體咋選擇中的概率；③使用模擬輪盤賭操作，來確定各個個體被選中的次數(shù)，得到中間群體。4）交叉操作。對選擇操作得到的中間群體進(jìn)行以下操作：①隨機(jī)選擇兩個交叉點(diǎn)；②子代保持兩交叉點(diǎn)之間的基因不變；③循環(huán)移動表中元素；④從表中除去父代已有的元素；⑤把表