【正文】 代代發(fā)生。在每一代，種群的適應(yīng)度被評 估，通過自然選擇和突變產(chǎn)生新的生命種群，隨機從目前的種群選擇多個個體（根據(jù)其自身的適應(yīng)度），這個種群在第一次迭代算法中，生成為當(dāng)前的種群。在遺傳算法，優(yōu)化問題的解被稱為個人，它代表一個變量序列，稱為染色體或基因的字符串。染色體一般被表達為一個簡單的字符串或數(shù)字字符串，但也適用于于特殊問題的表達方法，這個過程稱為編碼。首先，算法隨機生成一定數(shù)量的個體，有時操作者可以在隨機生成的過程中進行干預(yù)，以提高初始種群的質(zhì)量。每一個體在每一代，都被評估并通過 適應(yīng)度函數(shù) 的計算來得到一個 適應(yīng)度 的數(shù)值。個體按照適應(yīng)排度序，在前面的通常是適應(yīng)度高的。 “高”是指對初始群的低適應(yīng)度來講的。 下一步是產(chǎn)生下一代的個體組成種群。這個過程是通過選擇和繁殖，包括復(fù)制，包括交配（ crossover，算法在該領(lǐng)域的研究，就是我們所說的交叉操作）和突變（ mutation）。選擇是根據(jù)的 新的個體的適應(yīng)程度來執(zhí)行，但在同一時間并不意味著徹底的用適應(yīng)度的高低來作為標(biāo)準參考，因為只是選擇適應(yīng)度高的個體將可能導(dǎo)致，算法快速收斂到局部最優(yōu)解最佳的解決方案但不是全局的最有解決方案，我們稱之為早熟。作為一種妥協(xié)，根據(jù)遺傳算法的原則基礎(chǔ)上：適應(yīng)度越高，被選中的機會越高，適應(yīng)低被選中的機會越低。通過對初始數(shù)據(jù)的選擇，可組成一個相對最優(yōu)的群體。然后，被選擇后的個體進入交配過程。遺傳算法有交配的概率（也稱為交叉概率），通常的范圍是 1，這個交配的概率反映了兩個選定的個體交配的概率。例如，交配概率為 ， 80％“夫婦”可以生育后代。通過交配，每兩個人產(chǎn)生兩個新個體，而原來的“老”的個體將會被替代。交配父母的染色體交換，導(dǎo)致了兩個新的染色體產(chǎn)生，第一個個體前一半是父親的染 引言 8 色體，母親的則是后半段，第二個人則剛好相反。這里位置被稱為是隨機生成的交叉點，所指的半段并不是真正意義以上的一半。交叉點可以是任何染色體上的位置。下一步是突變基因突變產(chǎn)生新的“孩子”個體。一般遺傳算法有一個固定的突變常數(shù)（又稱突變率）一般為 ，這代表了基因突變的概率。根據(jù)這個概率，新個體的染色體隨機突變通常是改變一個字節(jié)（ 0到 1，或 0的變化）的染色體。 通過（選擇，交叉和變異）這一系列的過程之后，新一代的個體，從最初的一代是不同的，而且一代又一代的朝著提高適應(yīng)度的方向發(fā)展，最好的人總是更要被選擇產(chǎn)生下一代，適應(yīng)度低的會逐漸被淘汰。這個過程不斷重復(fù)：每個個體都被評估，計算每一個個體的適應(yīng)度，兩個個體交配和突變，產(chǎn)生第三代。一遍又一遍，直到滿足終止條件。一般的終止條件有以下幾種： 進化次數(shù)限制； 計算消耗的資源約束（如計算時間，計算所占用的內(nèi)存） 。 個體滿足的最優(yōu)值的條件，即已經(jīng)找到最佳值 。 適應(yīng)已經(jīng)達到飽和，繼續(xù)進化不會有適應(yīng)度更好 的個體 。 人為干預(yù) 。 超過兩個或兩個以上的組合。 引言 9 圖 遺傳 算法的工作原理示意圖 算法 Dijkstra算法的基本思路是：設(shè)置一個頂點集合 S，從一個源點 S到集合中定點最終最短路徑的權(quán)重已經(jīng)確定。算法反復(fù)選擇最短路徑估計頂點 i∈ VS，將 I并入 S， I所有的出邊松弛 原始的 Dijkstra算法在圖形數(shù)據(jù)存儲和節(jié)點之間的關(guān)系和距離的計算時，基于網(wǎng)絡(luò)的權(quán)重矩陣，形成關(guān)聯(lián)矩陣，鄰接矩陣和距離矩陣，需要定義 n n數(shù)組進行儲存數(shù)據(jù)，其中 N為網(wǎng)絡(luò)節(jié)點，網(wǎng)絡(luò)節(jié)點太多時，將占用大量的計算 機內(nèi)存。 （ 2）原始的 Dijkstra算法的運行時一般把網(wǎng)絡(luò)節(jié)點分為沒有被標(biāo)記節(jié)點，臨時標(biāo)記節(jié)點，永久標(biāo)記節(jié)點。網(wǎng)絡(luò)中的所有節(jié)點初始化為未標(biāo)記的節(jié)點，在搜索的過程中與最短路徑的節(jié)點連接的節(jié)點為臨時標(biāo)記的節(jié)點，每循環(huán)從臨時標(biāo)記節(jié)點的路徑長度最短的節(jié)點的節(jié)作為永久性標(biāo)志的節(jié)點，直到找到目標(biāo)節(jié)點或所有節(jié)點搜索算法結(jié)束前都將被永久標(biāo)記節(jié)點。影響了該算法的執(zhí)行效率是根據(jù)算法的描述，閱歷全部臨時標(biāo)記節(jié)點是 Dijkstra算法的瓶頸。 設(shè)計方案的可行性分析和預(yù)期目標(biāo) 預(yù)期目標(biāo)： 1. 廣泛收集相關(guān)資料，研究經(jīng)典 Dijkstra算法的主要思想及其實現(xiàn) 2．對目前應(yīng)用于 Dijkstra算法的數(shù)據(jù)結(jié)構(gòu)和搜索技術(shù)進行學(xué)習(xí)研究 3. 采用圖的鄰接矩陣或鄰接表實現(xiàn)最短路徑問題中圖的存儲 4．采用 Dijkstra算法求從某個源點到其余各頂點的最短路徑 5．將上述功能作為類的成員函數(shù)實現(xiàn)，編寫主函數(shù)測試上述功能 6. 以 C作為開發(fā)工具實現(xiàn)改進最短路徑算法的代碼編制，完成算法的實現(xiàn) 可行性分析： 個人能力方面：有一定的專業(yè)知識，技術(shù)能力，了解行業(yè)背景，有相應(yīng)的資料 個人環(huán)境方面：又上網(wǎng)條件，有充足的相關(guān)資料和書 籍，可以獲得充分的研引言 10 究資源 軟件方面： C，它具有簡單，面向過程，穩(wěn)定，與平臺無關(guān)，解釋型，多線程，動態(tài)等特點，因此將其作為首選工具。由于所需要的硬件配置要求不高，對于代碼編制，和算法的實現(xiàn)都是非常合適的。所以完全具備設(shè)計方案所需要的軟件條件。 無經(jīng)濟方面問題 相關(guān)軟件都是正版，獨立自主開發(fā) 根據(jù) Dijkstra算法，用 C語言進行編譯，使軟件可以實現(xiàn)查詢最短路徑的功能。主要研究并實現(xiàn)以下內(nèi)容功能： 1 加載、更換地圖，并可以在地圖上標(biāo)注大 量節(jié)點，使之連接成各個路線，提供大量路線選擇方案 2選擇任意起點和終點，只需要查詢起點和終點間的最短路徑，便可快速計算出之間的最短距離，挑選最短的路線 3添加數(shù)據(jù)庫，實現(xiàn)儲存、加載數(shù)據(jù)的功能，使先前的操作得到保留并可以隨時調(diào)用 Dijkstra 經(jīng)典算法的研究 11 第二章 Dijkstra 經(jīng)典算法的研究 Dijkstra算法原理 EW 提出的 Dijkstra算法圖表理論，一個眾所周知的最短路徑算法Dijkstra算法是在 1959年設(shè)計的，使用的數(shù)字點到其他頂點的最短路徑可以得到。原始 Dijkstra算法的網(wǎng)絡(luò)節(jié)點分為三個部分： 未標(biāo)記節(jié)點，臨時標(biāo)記的節(jié)點和永久標(biāo)記的節(jié)點。網(wǎng)絡(luò)中的所有節(jié)點啟動的第一個節(jié)點未標(biāo)記的節(jié)點，在搜索的過程當(dāng)中，與最短路徑中的結(jié)點相互連通的結(jié)點為臨時標(biāo)記結(jié)點，每個周期的循環(huán)全部是從臨時標(biāo)記節(jié)點的最短的路徑長度作為永久紀節(jié)點，直到找到目標(biāo)節(jié)點或所有節(jié)點成為永久標(biāo)記節(jié)點算法結(jié)束。 假設(shè)每個人都有一個標(biāo)簽（ WJ， PJ），其中 WJ是最短路徑長度 S從起源點到 j點（從頂點的最短路徑本身是零路（沒有弧的道路），其長度等于零） 。 PJ JJ是從 s到前一個點的最短路徑。求解從起源點到 j點的小號的基本過程，最短路徑算法如 下： 1）初始化。原點設(shè)置：① WS= 0， PS是空的 。②其他點： WI =∞， PI=？（ 3）標(biāo)記的起源點 S，設(shè) ?= S，所有其他點設(shè)置未標(biāo)記 2）標(biāo)記的點 k到其直接連接的測試未標(biāo)記點 j的距離，并設(shè)置： WJ= MIN{WJ周DKJ}的類型， DKJ點 k的直接連接距離 J. 3）選擇下一個點。從所有未標(biāo)記的節(jié)點，選擇 WJ最小的一個 I： WI=MIN WJ，I點選擇為的最短路徑點，并設(shè)置為已標(biāo)記 . 4）找到 I的第一點。從標(biāo)記點中，找到點 I直接連接的點 j*，作為前點，設(shè)：I= J *。 5）標(biāo)記點 I。如果所有點已標(biāo)記，該 算法將徹底計算出來，否則，記為 K =I，轉(zhuǎn)到 2）繼續(xù)。 Dijkstra 經(jīng)典算法的研究 12 Dijkstra算法最短路徑應(yīng)用演示 圖 Dijkstra算法最短路徑應(yīng)用演示圖 圖 從 0節(jié)點到 4節(jié)點的最短路徑 Dijkstra算法的仿真實現(xiàn) 根據(jù)上面的理論與思想，本文使用 Microsoft公司的 visual studio2021軟件，visual C語言， Access數(shù)據(jù)庫編寫，制作以 Dijkstra算法為基礎(chǔ)的可以查詢最短路徑的軟件，使最短路徑搜索查詢的功能得到了實現(xiàn)。以下是用到的一 段 Dijkstra算法的關(guān)鍵的代碼： private void ShortestDist(int s) { for (int i = 0。 i NUM。 i++) { //dist和 path數(shù)組初始化 dist[i] = [s, i]。 //鄰接矩陣第 s行元素賦值到 dist中 S[i] = 0。 //已求出最短路徑的頂點集合初始化 Dijkstra 經(jīng)典算法的研究 13 if (i != s amp。amp。 dist[i] ) { path[i] = s。 } else path[i] = 1。 //路徑存放數(shù)組初始 化 } S[s]=1。 //頂點 s加入頂點集合 dist[s] = 0。 /* 循環(huán)計算該場所與鄰接場所之間的最短距離 */ for (int i = 0。 i NUM 1。 i++) { //從頂點 s確定 n1條路徑 double min = 。 int u = s。 for (int j = 0。 j NUM。 j++) { //選擇當(dāng)前不在集合 S中具有最短路徑的頂點 u /* 如果有路徑比目前的最小值還小，則替換這個最小值 */ if (S[j] == 0 amp。amp。 dist[j] min) { u = j。 min = dist[j]。 } } S[u] = 1。 //將頂點 u加入集合 S，表示它已在最短路徑上 for (int w = 0。 w NUM。 w++) { //修改 if (S[w] == 0 amp。amp。 [u, w] amp。amp。 dist[u] + [u, w] dist[w]) { dist[w] = dist[u] + [u, w]。 path[w] = u。 } } } } public void getdata(int s, int e) { D[0] = e。 int k。 for (k = 0。 D[k] != s。 k++) { if (D[k] == 1) { (抱歉，沒有找到通路 )。 return。 } D[k + 1] = path[D[k]]。 } Dijkstra 經(jīng)典算法的研究 14 if (S[e] != 0) { for (。 k != 1。 k) { listline = listline + [D[k]][nname].ToString() + 。 (D[k])。 if ( = 2) { length = le