計(jì)算機(jī)科學(xué)與技術(shù)畢業(yè)論文-基于遺傳算法的tsp問題研究(已修改)
2025-06-20 15:07 本頁面
【正文】 畢業(yè)論文 題目 基于遺傳算法的 tsp問題研究 學(xué) 院 計(jì)算機(jī)與科學(xué)技術(shù) 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué) 號(hào) 202113137193 學(xué)生姓名 張 三 指導(dǎo)教師 李 四 日 期 二〇〇八年六月 摘 要 TSP 問題又稱為貨郎擔(dān)問題。 TSP 是一個(gè)典型的優(yōu)化組合問題，它需要求出旅行商從某一城市出發(fā)經(jīng)過所有城市所走路程的最短路徑，其可能的路徑數(shù)與城市個(gè)數(shù)成指數(shù)關(guān)系增長。找出有效的近似求解算法具有重要的意義。 選擇用遺傳算法去解決 TSP 問題。本論文對各個(gè)算子分別選擇的是基于序的評估函數(shù)、輪盤賭選擇法、兩點(diǎn)交叉法、兩點(diǎn)區(qū)間隨機(jī)排序變異法，并且通過 30 個(gè)城市的實(shí)際的例子來驗(yàn)證，結(jié)果求出最短路徑為 ，優(yōu)于二叉樹描述法的結(jié)果 ，啟發(fā)式搜索法的結(jié)果 ，表明遺傳算法在求解 TSP 問題上是有效的。 關(guān)鍵詞 ：組合優(yōu)化 ； TSP 問題 ；遺傳算法 ；最短路徑 Abstract TSP problem is also known as the traveling salesman problem. TSP is a typical portfolio optimization problem and needs to calculate the shortest path that a traveling salesman goes through all cities. The number of the possible paths may grow with index of the number of cities. It is of great significance to find out an effective approximate algorithm. It is used geic algorithms to solve the TSP problem. In this paper, the operators are fitness function based on sequence choice, selection with the law of roulette gambling, two point crossover, two point random interval mutation. An actual example through 30 cities is got. The result is of the shortest path, which is better than binary tree description with the result of , heuristic search with the result of , and shows that the geic algorithm for TSP is effective. Key words: Combinatorial Optimization 。 TSP 。 Geic Algorithm 。 the Shortest Path 目 錄 目 錄 ....................................
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1