資源描述：
《計(jì)算智能課程設(shè)計(jì)報(bào)告_粒子群優(yōu)化算法求解旅行商問(wèn)題_matlab實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、.........................摘要：TSP是一個(gè)典型的NPC問(wèn)題。本文首先介紹旅行商問(wèn)題和粒子群優(yōu)化算法的基本概念。然后構(gòu)造一種基于交換子和交換序[1]概念的粒子群優(yōu)化算法，通過(guò)控制學(xué)習(xí)因子和、最大速度，嘗試求解旅行商問(wèn)題。本文以中國(guó)31個(gè)省會(huì)城市為例，通過(guò)MATLAB編程實(shí)施對(duì)旅行商問(wèn)題的求解,得到了一定優(yōu)化程度的路徑，是粒子群優(yōu)化算法在TSP問(wèn)題中運(yùn)用的一次大膽嘗試。關(guān)鍵字：TSP問(wèn)題；粒子群優(yōu)化算法；MATLAB；中國(guó)31個(gè)城市TSP。專(zhuān)業(yè)資料分享.........................粒子群優(yōu)化算法求解旅行商問(wèn)題
2、1.引言1.旅行商問(wèn)題的概述旅行商問(wèn)題，即TSP問(wèn)題（TravelingSalesmanProblem）又譯為旅行推銷(xiāo)員問(wèn)題貨郎擔(dān)問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題，其描述非常簡(jiǎn)單，但最優(yōu)化求解非常困難，若用窮舉法搜索，對(duì)N個(gè)城市需要考慮N！種情況并兩兩對(duì)比，找出最優(yōu)，其算法復(fù)雜性呈指數(shù)增長(zhǎng)，即所謂“指數(shù)爆炸”。所以，尋求和研究TSP問(wèn)題的有效啟發(fā)式
3、算法，是問(wèn)題的關(guān)鍵。2.粒子群優(yōu)化算法的概述粒子群優(yōu)化算法(ParticleSwarmoptimization,PSO)又翻譯為粒子群算法、微粒群算法、或微粒群優(yōu)化算法。是通過(guò)模擬鳥(niǎo)群覓食行為而發(fā)展起來(lái)的一種基于群體協(xié)作的隨機(jī)搜索算法。通常認(rèn)為它是群集智能(Swarmintelligence,SI)的一種。它可以被納入多主體優(yōu)化系統(tǒng)?(MultiagentOptimizationSystem,MAOS).粒子群優(yōu)化算法是由Eberhart博士和Kennedy博士發(fā)明。PSO模擬鳥(niǎo)群的捕食行為。一群鳥(niǎo)在隨機(jī)搜索食物，在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都
4、不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周?chē)鷧^(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥(niǎo)。我們稱(chēng)之為“粒子”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitnessvalue)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過(guò)迭代找到最優(yōu)解，在每一次疊代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己。第一個(gè)就是粒子本身所找
5、到的最優(yōu)解，這個(gè)解叫做個(gè)體極值pBest，另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值gBest。另外也可以不用整個(gè)種群而只是用其中一部分最優(yōu)粒子的鄰居，那么在所有鄰居中的極值就是局部極值。3.粒子群優(yōu)化算法求解旅行商問(wèn)題旅行商問(wèn)題是一個(gè)典型的、易于描述卻難于處理的組合優(yōu)化問(wèn)題,并且是一個(gè)NP完全難題,其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長(zhǎng)的,對(duì)n個(gè)城市而言,可能的路徑總(n-1)!。隨著n的增加,路徑數(shù)將按數(shù)率急劇增長(zhǎng),即所謂的“指數(shù)爆炸”,所以一般很難精確地求出其最優(yōu)解,因而尋找出其有效的近似求解算法就具有重要的理論意義。而粒子群
6、優(yōu)化算法是解決復(fù)雜問(wèn)題的有效方法,自然也能應(yīng)用于解決旅行商問(wèn)題。專(zhuān)業(yè)資料分享.........................PSO模擬鳥(niǎo)群的捕食行為。一群鳥(niǎo)在隨機(jī)搜索食物，在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周?chē)鷧^(qū)域。1.粒子群算法的基本思想[2]1.粒子群優(yōu)化算法的基本原理一個(gè)由個(gè)粒子(Particle)組成的群體(Swarm)在維搜索空間中以一定的速度飛行，每個(gè)粒子在搜索時(shí)，考慮到了自己搜索到的的歷史最好點(diǎn)和群體內(nèi)(或
7、領(lǐng)域內(nèi))其它粒子的最好點(diǎn)，在此基礎(chǔ)上進(jìn)行位置(狀態(tài)、也就是解)的變化。第個(gè)粒子的位置表示為：第個(gè)粒子的速度表示為：，第個(gè)粒子所經(jīng)歷的歷史最好點(diǎn)表示為：群體內(nèi)(或領(lǐng)域內(nèi))所有粒子所經(jīng)歷過(guò)的最好的點(diǎn)表示為：。一般來(lái)說(shuō)，粒子的位置和速度都是在連續(xù)的實(shí)數(shù)空間內(nèi)進(jìn)行取值，粒子的位置和速度根據(jù)如下方程進(jìn)行變化其中，為慣性權(quán)重。和稱(chēng)為學(xué)習(xí)因子(LearningFactor)或加速系數(shù)(AccelerationCoefficient)，一般為正常數(shù)。學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)或領(lǐng)域內(nèi)的歷史最優(yōu)點(diǎn)靠近。和通
8、常等于2。，，是在區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù)。粒子的速度被限制在一個(gè)最大的范圍內(nèi)。當(dāng)把群體內(nèi)所有粒子都作為領(lǐng)域
