【正文】 Algorithm)、遺傳編程 (Geic Programming)、進(jìn)化策略 (Evolution Strategies)以及進(jìn)化規(guī)劃 (Evolutionary Programming)。傳統(tǒng)的優(yōu)化算法在面對這些大型問題時，需要遍歷整個搜索空間，從而會產(chǎn)生搜索的組合爆炸，無法在多項式時間內(nèi)完成搜索，無論是在計算速度、收斂性、初值敏感性等方面都遠(yuǎn)不能滿足要求，因此很難用于工程優(yōu)化問題的求解。這一類問題的共同點是選出最合理、達(dá)到最優(yōu)目標(biāo)的方案，這就是工程優(yōu) 化問題。至今已出現(xiàn)線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動態(tài)規(guī)劃、隨機規(guī)劃、網(wǎng)絡(luò)流等許多分支，最優(yōu)化理論和算法在實際應(yīng)用中正在發(fā)揮著越來越重要的作用。但是由于受到計算手段等歷史條件的限制，在 20 世紀(jì) 40 年代以前，最優(yōu) 化理論還不能形成一門學(xué)科。最優(yōu)化方法就是從眾多可能的解決方案中選擇最佳者，以達(dá)到最優(yōu)目標(biāo)的科學(xué)。這對國民經(jīng)濟(jì)的各個領(lǐng)域來說， 應(yīng)用前景是巨大的。在結(jié)構(gòu)力學(xué)、生命科學(xué)、材料科學(xué)、環(huán)境科學(xué)、控制論等其他科學(xué)研究領(lǐng)域也有廣泛應(yīng)用。 第 1章 緒 論 引言 最優(yōu)化問題就是從所有可能的方案中選擇出最合理的、達(dá)到最優(yōu)目標(biāo)的方案，即最優(yōu)方案問題，搜索最優(yōu)方案的方法就是最優(yōu)化 方法。 最后，本文將改進(jìn)的粒子群算法在 burma14 和 oliver30 這兩個 TSP 實例中進(jìn) 行了仿真，得到了較為滿意的結(jié)果。 本文首先分析了粒子群優(yōu)化 算法的原理，應(yīng)用粒子群優(yōu)化算法的步驟，以及算法中經(jīng)驗參數(shù)的設(shè)置， 總結(jié)了目前 PSO 算法研究的成果，對比分析了目前對粒子群優(yōu)化算法的多種改進(jìn)。 旅行商問題 (Traveling Salesman ProblemTSP)是圖論中一個經(jīng)典的組合優(yōu)化問題，是一個典型的 NP 難題，許多實際問題都可以轉(zhuǎn)化為旅行商問題。目前對粒子群優(yōu)化算法的研究尚處于初期，它今后的發(fā)展還有許多工作需要不斷充實提高。 摘 要 粒子群優(yōu)化算法是一種新型的進(jìn)化計算技術(shù)，由 Eberhart 博士和 Kennedy 博士于1995 年提出。 PSO 算法已經(jīng)被證明是一種有效的全局優(yōu)化方法，并且廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練以及模糊系統(tǒng)控制等領(lǐng)域。因此以粒子群優(yōu)化算法為主要研究對象，尋找求解實際問題的更加有效的改進(jìn)算法是很有意義的。本文 對 一種新的進(jìn)化粒子群算法在 TSP 中的應(yīng)用 研究。 其次，基于對粒子群優(yōu)化算法原理的分析， 實現(xiàn) 了一種基于 TSP 的改進(jìn)的粒子群優(yōu)化算法：求解 TSP 的混合粒子群算法 ， 結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想來解決 TSP 問題。 關(guān)鍵詞 ： 粒子群優(yōu)化算法 ； 旅行商問題 ； 混合粒子群算法 Abstract Particle Swarm Optimization(PSO) is a new kind of evolutionary putation and was originally introduced by Eberhart and Kennedy in has since proven to be a powerful global optimization has been widely applied in function optimization,neural work training,and fuzzy system control,as PSO is a newly emerging optimization method,there are many research work should be it is very significant to seek more powerful improved algorithms based on PSO to solve concrete engineering problems. TSP (Traveling Salesman ProblemTSP) is a classic graph theory, binatorial optimization problem, is a typical NP problem, many practical problems can be ransformed into traveling salesman problem. In this paper, the evolution of a new particle swarm algorithm in the application of TSP. Firstly, elements of PSO is analyzed in this on the analysis on characteristics of PSO,the algorithm is experienced settings of parameters are also given. In the thesis,the present productions of PSO are summarized and pared. Secondly, based on the principle of particle swarm optimization analysis, the realization of a TSP based on the improved particle swarm optimization algorithm: Solving the TSP hybrid particle swarm algorithm, bined with geic algorithm, ant colony algorithm and simulated annealing algorithm to solve the Traveling Salesman Problem. Finally, the new Particle Swarm Optimization is used to emulate in two of TSP example: buram 14 and oliver 30 and obtained satisfactory results. Keywords: Particle Swarm Optimization Traveling Salesman Problem Hybrid Particle Swarm Optimization Algorithm 目 錄 摘 要 .................................................................................................................................I ABSTRACT .......................................................................................................................... II 第 1 章 緒 論 ...................................................................................................................... 1 引言 ....................................................................................................................... 1 研究背景 ............................................................................................................... 3 進(jìn)化算法簡介 .............................................................................................. 3 群智能簡介 .................................................................................................. 3 粒子群優(yōu)化算法的概述 .............................................................................. 5 旅行商問題 .................................................................................................. 6 粒子群優(yōu)化算法的國內(nèi) 外研究現(xiàn)狀 ..................................................................... 6 粒子群優(yōu)化算法的研究意義 ................................................................................. 8 第 2 章 粒子群優(yōu)化算法 ...................................................................................................... 9 粒子群算法的原理 ................................................................................................. 9 粒子群優(yōu)化算法和遺傳算法 (GA)的比較 ........................................................... 11 粒子群優(yōu)化算法的特點及應(yīng)用關(guān)鍵 ................................................................... 12 PSO 的關(guān)鍵術(shù)語 ....................................................................................... 13 PSO 算法的基本步驟和流程 ................................................................... 13 應(yīng)用 PSO 算法步驟 .................................................................................. 14 PSO 參數(shù)設(shè)置 ........................................................................................... 15 第 3 章 PSO 算法的改進(jìn)算法 ............................................................................................ 17 基于慣性權(quán)值的改進(jìn) ........................................................................................... 17 基于加速因子的 PSO 改進(jìn) .................................................................................. 18 基于鄰近群拓?fù)涞母倪M(jìn) ....................................................................................... 18 基于種群規(guī)模的改進(jìn) ........................................................................................... 20 第 4 章 一種改進(jìn)的求解 TSP 混合粒子群優(yōu)化算法 ....................................................... 21 混合粒子群算法的概述 ....................................................................................... 21 變異操作 ............................................................................................................... 21 交叉操作 ............................................................................................................... 22 混合粒子群算法 .......