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