【正文】 ............................................23II基于人工智能的路徑查找優(yōu)化算法摘 要旅行商是一個古老且有趣的問題它可以描述為：給定 n個城市以及它們之間的距離 dij（城市 i到城市 j的距離） ，求解從其中一個城市出發(fā)對每個城市訪問，且僅訪問一次，最后回到出發(fā)的城市，應當選取怎樣的路線才能使其訪問完所有的城市后回到初始的城市且走過的路程最短。關鍵詞：人工智能；遺傳算法；TSP；旅行商問題IIIPath search system based on artificial intelligence algorithmsAbstractTraveling salesman is an ancient and interesting it can be described as given n cities and the distance between them dij (city i to city j, the distance), solving the access for each city, starting from one of the city and only one visit and finally back to the starting city, should select what route it back to the initial visit all the cities city and traveled the shortest.Various optimization algorithms to solve the traveling salesman problem through the expense of the accuracy of the solution in exchange for less timeconsuming, other heuristic search algorithm depends on the specific problem domain lack of universal so the geic algorithm is pared to a mon good global search algorithm. GA( geic algorithm) Was first proposed by John Holland of the University of Michigan. The GA has selfanizing, adaptive, selflearning and group evolution function so the GA has strong ability to solve problems, now the GA been applied in many fields. Today, the geic algorithm research has bee one of the hot topics of the international academic munity interdisciplinary.Key words: Artificial Intelligence。22. 概述近年，隨著計算機軟硬件的飛速發(fā)展，計算機在人類的日常、生活、學習工作中也成為了不可分割的部分。與傳統(tǒng)的優(yōu)化算法相比，具有的優(yōu)缺點如下。搜索過程不易陷入局部最優(yōu)點。例如，將遺傳算法與模糊技術、神經(jīng)網(wǎng)絡相結合，已取得了不少成果。每個位置上的符號稱為基因(gene)。Initialize P (t)。在傳統(tǒng)的遺傳算法中，編碼采用的是二進制串，用一連串的 0 和 1 來表示一個個體，然后來操作這一串 0 和 1。. 個體的評估在衍生下一代種群前，應該挑選優(yōu)秀的基因來充當親代，這樣更能符合遺傳算法的理念——物競天擇，適者生存，為此，要先對親代種群進行評估，計算出他們的適應度。當前，用的比較廣泛的選擇方法是賭輪盤 [5]，基本原理是適應度越大的個體，被選取的幾率就越大。兩點交叉是在父代中添加兩個斷點，將父代分割成三個片段，兩個親代都保留中間的基因片段到子代中，然后將第二個親代的第三個基因片段中沒有在第一個親代保留基因片段出現(xiàn)的基因從第一個親代的第一個位置開始按順序復制到第一個親代中去，如果在中間保留的基因片段沒有，而第三個片段有相同的基因，則將第三個基因片段中相同的基因刪掉。在交叉遺傳中，因為是路徑問題，所以有可能交叉后在一條路徑中會出現(xiàn)重復的城市，因此，在交叉后需要將新產(chǎn)生的子代轉換為真實的城市路徑，檢測是否出現(xiàn)了重復城市，如果檢測到有，則要重新生成，直到?jīng)]有重復城市出現(xiàn)，在這步操作中做了大量的重復且復雜的操作，而且容易出錯，不易掌控。如對 8 個城市的旅行商問題進行編碼，城市的編號分別為{1,2,3,4,5,6,7,8}，則染色體的編碼串 3 4 2 8 6 7 5 1 表示以特定的順序 3—4—2—8—6—7—5—1 來依次訪問各座城市。這樣做主要是為了克服傳統(tǒng)遺傳算法中初始化種群的盲目性，這樣初始化種群使得初代的原始基因更優(yōu)秀。輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應度函數(shù)值大小成正比。這種操作的好處是，越優(yōu)秀的個體，那么它被選取的機會也就越大，這樣積累下去，整個種群的進化也是朝著一個良性方向去進化。如果兩個親代 FF2 都是 {2,3,4,8,1,7,9,6,5}，隨機第一個子代 C1 的第一個基因就是變異操作在原理和思想上與傳統(tǒng)的差別較大，傳統(tǒng)的遺傳算法是將需要變異的基因中的某個或幾個基因做方向操作，進過改進后的遺傳算法，個體是用序號串做基因的，所以原來的傳統(tǒng)的變異操作在此處不可取，也行不通。16初始化種群評價種群個體、計算適應度尋找最優(yōu)個體并保留選擇復制交叉遺傳突變達到遺傳代數(shù)？生成新一代終止圖 52改進后遺傳算法流程圖. 數(shù)據(jù)結構設計為了簡化后面的操作，容易操控，每座城市都是用序號來表示的，然后將每座城市抽象成一個坐標系中的一個點，所以，城市與城市間的距離就可以轉換為坐標系中兩個點之間的距離。 // 映射城市在串中的位置int sum_distance。在上面的結構體中，path 表示個體的路徑，也是個體的基因所在，其中的值類型是 int，因為我們的城市是用序號來表示的，這樣做的好處就是可以很方便的從距離數(shù)組中取得任意兩個城市間的距離；label 是一個標志性數(shù)組，用來在后期的交叉操作中來判斷城市是否已經(jīng)出現(xiàn)在路徑中，當 path 中的某個位置上出現(xiàn)了一個城市，也就是一個序號，那么 label 數(shù)組中與城市序號對應的下標的位置的值就為 1，這樣可以免去每次都要掃描每個個體的基因，可以理解為用空間資源換取時間資源，label 中的值在種群初始化時都是 0，local 數(shù)組是存放個體中每個基因（城市序號）在 path 中的位置，這樣設計是為了在后期的交叉操作中不用遍歷去尋找某個基因，而是直接根據(jù)位置來索引，這樣做的好處是同樣節(jié)省了搜尋時間。系統(tǒng)包含的所有函數(shù)有：表 51 系統(tǒng)函數(shù)說明表函數(shù)名稱 作用void initialize(void)。void select(void)。void mutate(void)。 輔助函數(shù)，用來計算城市之間的路程。struct genotype temp。int sum = 0。keep_the_best()。printf(\nSuccess\n\n)。 （2）遺傳算法能夠非常有效地進行概率意義下的全局搜索。[4] 梁艷春，馮大鵬，周春光，遺傳算法求解旅行商問題時的基因片段保序 [期刊論文]，2022。指導老師認真負責的工作態(tài)度，嚴謹?shù)闹螌W精神和深厚的理論水平都使我受益匪淺。在此我向他們至以最高的敬意。[6] 劉國華，包宏，李文超，用 Matlab實現(xiàn)遺傳算法程序[J] ， 計算機應用研究 , 2022 。 經(jīng)過改進后的遺傳算法，在傳統(tǒng)遺傳算法的基礎上，應用范圍更廣了，同時實現(xiàn)起來也比較簡單，同時對于傳統(tǒng)的遺傳算法中易于收斂于局部最優(yōu)解有了很大程度上的改善。}系統(tǒng)在經(jīng)過多次運行后，得到的最優(yōu)解是 15377，與測試數(shù)據(jù)給出的標準結果一樣，只是出現(xiàn)的概率偏低，大概是 10%，出現(xiàn)的最大值是 19100，一般是 15500 左右，所以算法需要優(yōu)化的地方還很多。select()。srand(time(NULL))。 mem POPSIZE。 輔助函數(shù)，通過路程對種群中的個體排序。void read_tsp_file()。void crossover(void)。void global_2_opt(int )。至于沒用的幾個屬性，則是擴展屬性，給系統(tǒng)留有發(fā)展的空間。int sum。double Y[N_CITIES]。如，個體 P1={3,2,5,8,1,4,7,6,9}，如果該個體產(chǎn)生的變異隨機數(shù)符合變異操作，那么針對該個體的變異操作則是，先是產(chǎn)生兩個隨機數(shù)，來確定哪兩個地方變異，假如此處的產(chǎn)生的隨機數(shù)是 4 和 8，那么第 4 個位子和第 8 個位子上的基因需交換而來產(chǎn)生經(jīng)過變異后的個體（設定從 0 開始編號） ，此處產(chǎn)生的新個體 P2 是：P2={3,2,5,8,6,4,7,8,9}，可以看出，系