【正文】 Algorithm)、遺傳編程 (Geic Programming)、進(jìn)化策略 (Evolution Strategies)以及進(jìn)化規(guī)劃 (Evolutionary Programming)。傳統(tǒng)的優(yōu)化算法在面對(duì)這些大型問(wèn)題時(shí)，需要遍歷整個(gè)搜索空間，從而會(huì)產(chǎn)生搜索的組合爆炸，無(wú)法在多項(xiàng)式時(shí)間內(nèi)完成搜索，無(wú)論是在計(jì)算速度、收斂性、初值敏感性等方面都遠(yuǎn)不能滿足要求，因此很難用于工程優(yōu)化問(wèn)題的求解。這一類問(wèn)題的共同點(diǎn)是選出最合理、達(dá)到最優(yōu)目標(biāo)的方案，這就是工程優(yōu) 化問(wèn)題。至今已出現(xiàn)線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動(dòng)態(tài)規(guī)劃、隨機(jī)規(guī)劃、網(wǎng)絡(luò)流等許多分支，最優(yōu)化理論和算法在實(shí)際應(yīng)用中正在發(fā)揮著越來(lái)越重要的作用。但是由于受到計(jì)算手段等歷史條件的限制，在 20 世紀(jì) 40 年代以前，最優(yōu) 化理論還不能形成一門學(xué)科。最優(yōu)化方法就是從眾多可能的解決方案中選擇最佳者，以達(dá)到最優(yōu)目標(biāo)的科學(xué)。這對(duì)國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域來(lái)說(shuō)， 應(yīng)用前景是巨大的。在結(jié)構(gòu)力學(xué)、生命科學(xué)、材料科學(xué)、環(huán)境科學(xué)、控制論等其他科學(xué)研究領(lǐng)域也有廣泛應(yīng)用。 第 1章 緒 論 引言 最優(yōu)化問(wèn)題就是從所有可能的方案中選擇出最合理的、達(dá)到最優(yōu)目標(biāo)的方案，即最優(yōu)方案問(wèn)題，搜索最優(yōu)方案的方法就是最優(yōu)化 方法。 最后，本文將改進(jìn)的粒子群算法在 burma14 和 oliver30 這兩個(gè) TSP 實(shí)例中進(jìn) 行了仿真，得到了較為滿意的結(jié)果。 本文首先分析了粒子群優(yōu)化 算法的原理，應(yīng)用粒子群優(yōu)化算法的步驟，以及算法中經(jīng)驗(yàn)參數(shù)的設(shè)置， 總結(jié)了目前 PSO 算法研究的成果，對(duì)比分析了目前對(duì)粒子群優(yōu)化算法的多種改進(jìn)。 旅行商問(wèn)題 (Traveling Salesman ProblemTSP)是圖論中一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，是一個(gè)典型的 NP 難題，許多實(shí)際問(wèn)題都可以轉(zhuǎn)化為旅行商問(wèn)題。目前對(duì)粒子群優(yōu)化算法的研究尚處于初期，它今后的發(fā)展還有許多工作需要不斷充實(shí)提高。 摘 要 粒子群優(yōu)化算法是一種新型的進(jìn)化計(jì)算技術(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)化算法為主要研究對(duì)象，尋找求解實(shí)際問(wèn)題的更加有效的改進(jìn)算法是很有意義的。本文 對(duì) 一種新的進(jìn)化粒子群算法在 TSP 中的應(yīng)用 研究。 其次，基于對(duì)粒子群優(yōu)化算法原理的分析， 實(shí)現(xiàn) 了一種基于 TSP 的改進(jìn)的粒子群優(yōu)化算法：求解 TSP 的混合粒子群算法 ， 結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想來(lái)解決 TSP 問(wèn)題。 關(guān)鍵詞 ： 粒子群優(yōu)化算法 ； 旅行商問(wèn)題 ； 混合粒子群算法 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)化算法簡(jiǎn)介 .............................................................................................. 3 群智能簡(jiǎn)介 .................................................................................................. 3 粒子群優(yōu)化算法的概述 .............................................................................. 5 旅行商問(wèn)題 .................................................................................................. 6 粒子群優(yōu)化算法的國(guó)內(nèi) 外研究現(xiàn)狀 ..................................................................... 6 粒子群優(yōu)化算法的研究意義 ................................................................................. 8 第 2 章 粒子群優(yōu)化算法 ...................................................................................................... 9 粒子群算法的原理 ................................................................................................. 9 粒子群優(yōu)化算法和遺傳算法 (GA)的比較 ........................................................... 11 粒子群優(yōu)化算法的特點(diǎn)及應(yīng)用關(guān)鍵 ................................................................... 12 PSO 的關(guān)鍵術(shù)語(yǔ) ....................................................................................... 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 混合粒子群算法 .......