粒子群算法求TSP問題_第1頁
粒子群算法求TSP問題_第2頁
粒子群算法求TSP問題_第3頁
粒子群算法求TSP問題_第4頁
粒子群算法求TSP問題_第5頁
已閱讀5頁,還剩11頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、精選優(yōu)質(zhì)文檔-傾情為你奉上智能優(yōu)化算法第三次作業(yè)一分析1) 1、基本思想粒子群算法簡稱PSO,它的基本思想是模擬鳥群的捕食行為。設(shè)想這樣一個場景:一群鳥在隨機(jī)搜索食物。在這個區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中,每個優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness value),每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前

2、的最優(yōu)粒子在解空間中搜索。PSO 初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過迭代找到最優(yōu)解。在每一次迭代中,粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優(yōu)解,這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優(yōu)解,這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居,那么在所有鄰居中的極值就是局部極值。粒子公式在找到這兩個最優(yōu)值時,粒子根據(jù)如下的公式來更新自己的速度和新的位置:vi = w * vi + c1 * rand() * (pbesti - presenti) + c2 * rand() * (gbest - presenti

3、) presenti = presenti + vi其中vi代表第i個粒子的速度,w代表慣性權(quán)值,c1和c2表示學(xué)習(xí)參數(shù),rand()表示在0-1之間的隨機(jī)數(shù),pbesti代表第i個粒子搜索到的最優(yōu)值,gbest代表整個集群搜索到的最優(yōu)值,presenti代表第i個粒子的當(dāng)前位置算法步驟:(i) 初始化粒子群,給每一個粒子一個初始解idx和隨機(jī)的交換序idv。 (ii) 判斷是否達(dá)到最大迭代次數(shù)1000。若是,算法結(jié)束,輸出結(jié)果;若不是,轉(zhuǎn)到(iii)。 (iii) 根據(jù)粒子當(dāng)前位置計算下一個新解: (a) 計算A,A是一個基本交換序,表示A作用于idx得到idp; (b) 計算B=-,B是一

4、個基本交換序; (c) 按照公式v=vAB更新速度和位置。 (d) 如果得到了更好的個體位置,更新。 (iv) 如果得到了更好的群體位置,更新。1) 生成初始種群: 2) 適應(yīng)度計算3) 當(dāng)前最優(yōu)粒子位子序列4) 全局最優(yōu)位置序列5) 更新速度6) 更新位置7) 找到最優(yōu)路徑二、結(jié)果:源碼:/*問題:用粒子群算法求解TSP問題:為保證有解 用完全圖做樣例*/*洪文杰 2016-3-25. 智能優(yōu)化算法 第三次作業(yè)*/#include#include#includeusing namespace std;/-宏定義-/#define NUMBER 50 /種群規(guī)模#define GENE_NUM

5、BER 1000 /迭代次數(shù)#define G 20 /圖的頂點個數(shù)#define M 0.45 /局部最優(yōu)解選擇概率#define N 0.65 /全局最優(yōu)解選擇概率/-全局變量定義-/int FigureGG; /保存圖信息int UnitNUMBERG; /保存初始種群static structint a;int b;vNUMBERG,ANUMBERG,BNUMBERG,VNUMBER3*G; /保存種群初始速度,序列A,序列B,更新后的速度。/int PbestNUMBERG; /保存每個粒子當(dāng)前知道的最佳位置/int GbestG; /保存所有粒子知道的最佳位置int sumNUMB

6、ER; /保存?zhèn)€體環(huán)路長度int Figure_best=; /最短路徑長度int key=0; /最短路徑的個體編號int V_numberNUMBER; /更新速度的序列個數(shù)int hwjG; /保存最短路徑/-函數(shù)聲明-/void hwj_figure(); /生成完全圖void hwj_initial_population(); /生成初始種群及粒子速度void hwj_swap(int *a,int *b); /交換兩個數(shù)的值void hwj_fitness(); /計算適應(yīng)度void hwj_A(); /找到粒子與其當(dāng)前所知道的最佳位置的速度序列void hwj_B(); /找到粒

7、子與種群最佳位置的速度序列void hwj_V(); /速度更新void hwj_X(); /位置更新void hwj_best(); /找到最短路徑 /-主函數(shù)-/int main()int Key=0;coutthis is the figure:endl;hwj_figure();/cout-1生成完全圖-endl; hwj_initial_population();/cout-2初始種群-endl;while(Key!=GENE_NUMBER) hwj_initial_population();/cout-3適應(yīng)度-endl; hwj_fitness();/cout-4當(dāng)前最優(yōu)粒子位子

8、序列-endl;hwj_cross(); hwj_A();/cout-5全局最優(yōu)位置序列-endl;hwj_B();/cout-6速度更新-endl; hwj_V();/ cout-7位置更新-endl; hwj_X();/ cout-8找到最優(yōu)解-endl; hwj_best(); Key+; cout The shortest path length is:Figure_bestendl; cout Shortest path is :endl; for(int i=0;iG;i+) couthwji ; coutendl;return 0;/-生成完全圖-/void hwj_figure

9、()srand(time(NULL);int i,j;for( i=0;iG;i+)for(j=i+1;jG;j+)Figureij=rand()%100+1; /只需要上三角信息coutFigureij ;coutendl;/-交換兩個數(shù)的值-/void hwj_swap(int *a,int *b)if(*a != *b) / 異或操作交換兩個數(shù)字的位置 *a = *b; *b = *a; *a = *b; /-生初始種群-/void hwj_initial_population()srand(time(NULL);int aG;int i,j;for(j=0;jG;j+)aj=j;for

10、(i=0;iNUMBER;i+)for(j=0;jG;j+)hwj_swap(&aj, &aj+rand()%(G-j); Unitij=aj; vij.a=rand()%G; vij.b=rand()%G;/ coutvij.a ;/coutvij.b ;/coutUnitij ; /輸出驗證完全不一樣的種群且個體沒有重復(fù)基因/coutendl;/-計算適應(yīng)度-/void hwj_fitness()int i,j;int temp;for(i=0;iNUMBER;i+)temp=0;for(j=0;jUnitij+1)temp+=FigureUnitij+1Unitij;elsetemp+=

11、FigureUnitijUnitij+1; if(Uniti0UnitiG)sumi=temp+FigureUnitiGUniti0; /計算每個個體的環(huán)路長度elsesumi=temp+FigureUniti0UnitiG; /coutsumiendl;/-找到粒子與其當(dāng)前所知道的最佳位置的速度序-/void hwj_A()int i,j,k;int temp=sum0;for(i=0;iNUMBER;i+)if(tempsumi)temp=sumi;key=i;for(j=0;jG;j+)for(k=0;kG;k+)if(Unitkeyj=Unitik)Aij.a=j;Aij.b=k;Fi

12、gure_best=temp;/-找到粒子與全局的最佳位置的速度序-/void hwj_B()int i,j,k;for(i=0;iNUMBER;i+)for(j=0;jG;j+)for(k=0;kG;k+)if(Unitkeyj=Unitik)Bij.a=j;Bij.b=k;/-速度更新-/void hwj_V()float a,b;int i,j,k,t;int temp1=0;int temp2=0;int TG=0;srand(time(NULL);a=rand()%1000/1000;b=rand()%1000/1000;if(a=M&b=N)for(i=0;iNUMBER;i+)V

13、_numberi=0;for(j=0;jG;j+)Vij.a=vij.a;Vij.b=vij.b;for(k=0;kG;k+)if(vik.a=Aij.a)&(vik.b=Aij.b)temp1=1;if(Bik.a=Aij.a)&(Bik.b=Aij.b)Tk=1;if(temp1=0)ViV_numberi+G.a=Aij.a;ViV_numberi+G.b=Aij.b;V_numberi+;elsetemp1=0;for(i=0;iNUMBER;i+)for(j=0;jG;j+)if(Tj=1)temp2=1;elsefor(k=0;kG;k+) if(vik.a=Bij.a)&(vik

14、.b=Bij.b)temp2=1; if(temp2=0)ViV_numberi+G.a=Bij.a;ViV_numberi+G.b=Bij.b;V_numberi+; elsetemp2=0;else if(aN)for(i=0;iNUMBER;i+)V_numberi=0;for(j=0;jG;j+)Vij.a=vij.a;Vij.b=vij.b;for(k=0;kM&b=N)for(i=0;iNUMBER;i+)V_numberi=0;for(j=0;jG;j+)Vij.a=vij.a;Vij.b=vij.b;for(k=0;kG;k+)if(vik.a=Bij.a)&(vik.b=Bi

15、j.b)temp1=1;if(temp1=0)ViV_numberi+G.a=Bij.a;ViV_numberi+G.b=Bij.b;V_numberi+;elsetemp1=0;elsefor(i=0;iNUMBER;i+)for(j=0;jG;j+) Vij.a=vij.a;Vij.b=vij.b;V_numberi=G;/-更新位置-/void hwj_X()int i,j;for(i=0;iNUMBER;i+)for(j=0;jV_numberi;j+)hwj_swap(&UnitiVij.a,&UnitiVij.b);/-找到最短路徑-/void hwj_best()int temp;int i,j;for(i=0;iNUMBER;i+)temp=0;for(j=0;j

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論