粒子群算法求TSP問題

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