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

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

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

4、idp； (b) 計算B=-，B是一個基本交換序； (c) 按照公式v=vAB更新速度和位置。 (d) 如果得到了更好的個體位置，更新。 (iv) 如果得到了更好的群體位置，更新。1） 生成初始種群： 2） 適應度計算3） 當前最優(yōu)粒子位子序列4） 全局最優(yōu)位置序列5） 更新速度6） 更新位置7） 找到最優(yōu)路徑二、結果：源碼：/*問題：用粒子群算法求解TSP問題：為保證有解 用完全圖做樣例*/*洪文杰 2016-3-25. 智能優(yōu)化算法 第三次作業(yè)*/#include<iostream>#include<stdlib.h>#include<time.h>us

5、ing namespace std;/-宏定義-/#define NUMBER 50 /種群規(guī)模#define GENE_NUMBER 1000 /迭代次數#define G 20 /圖的頂點個數#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 Pbes

6、tNUMBERG; /保存每個粒子當前知道的最佳位置/int GbestG; /保存所有粒子知道的最佳位置int sumNUMBER; /保存?zhèn)€體環(huán)路長度int Figure_best=100000; /最短路徑長度int key=0; /最短路徑的個體編號int V_numberNUMBER; /更新速度的序列個數int hwjG; /保存最短路徑/-函數聲明-/void hwj_figure(); /生成完全圖void hwj_initial_population(); /生成初始種群及粒子速度void hwj_swap(int *a,int *b); /交換兩個數的值void hwj_f

7、itness(); /計算適應度void hwj_A(); /找到粒子與其當前所知道的最佳位置的速度序列void hwj_B(); /找到粒子與種群最佳位置的速度序列void hwj_V(); /速度更新void hwj_X(); /位置更新void hwj_best(); /找到最短路徑 /-主函數-/int main()int Key=0;cout<<"this is the figure:"<<endl;hwj_figure();/cout<<"-1生成完全圖-"<<endl; hwj_initial

8、_population();/cout<<"-2初始種群-"<<endl;while(Key!=GENE_NUMBER) hwj_initial_population();/cout<<"-3適應度-"<<endl; hwj_fitness();/cout<<"-4當前最優(yōu)粒子位子序列-"<<endl;hwj_cross(); hwj_A();/cout<<"-5全局最優(yōu)位置序列-"<<endl;hwj_B();/cou

9、t<<"-6速度更新-"<<endl; hwj_V();/ cout<<"-7位置更新-"<<endl; hwj_X();/ cout<<"-8找到最優(yōu)解-"<<endl; hwj_best(); Key+; cout<<" The shortest path length is:"<<Figure_best<<endl; cout<<" Shortest path is :"

10、<<endl; for(int i=0;i<G;i+) cout<<hwji<<' ' cout<<endl;return 0;/-生成完全圖-/void hwj_figure()srand(time(NULL);int i,j;for( i=0;i<G;i+)for(j=i+1;j<G;j+)Figureij=rand()%100+1; /只需要上三角信息cout<<Figureij<<' 'cout<<endl;/-交換兩個數的值-/void hwj_swa

11、p(int *a,int *b)if(*a != *b) / 異或操作交換兩個數字的位置 *a = *b; *b = *a; *a = *b; /-生初始種群-/void hwj_initial_population()srand(time(NULL);int aG;int i,j;for(j=0;j<G;j+)aj=j;for(i=0;i<NUMBER;i+)for(j=0;j<G;j+)hwj_swap(&aj, &aj+rand()%(G-j); Unitij=aj; vij.a=rand()%G; vij.b=rand()%G;/ cout<&l

12、t;vij.a<<' '/cout<<vij.b<<' '/cout<<Unitij<<' ' /輸出驗證完全不一樣的種群且個體沒有重復基因/cout<<endl;/-計算適應度-/void hwj_fitness()int i,j;int temp;for(i=0;i<NUMBER;i+)temp=0;for(j=0;j<G-1;j+)if(Unitij>Unitij+1)temp+=FigureUnitij+1Unitij;elsetemp+=Figur

13、eUnitijUnitij+1; if(Uniti0>UnitiG)sumi=temp+FigureUnitiGUniti0; /計算每個個體的環(huán)路長度elsesumi=temp+FigureUniti0UnitiG; /cout<<sumi<<endl;/-找到粒子與其當前所知道的最佳位置的速度序-/void hwj_A()int i,j,k;int temp=sum0;for(i=0;i<NUMBER;i+)if(temp<sumi)temp=sumi;key=i;for(j=0;j<G;j+)for(k=0;k<G;k+)if(Uni

14、tkeyj=Unitik)Aij.a=j;Aij.b=k;Figure_best=temp;/-找到粒子與全局的最佳位置的速度序-/void hwj_B()int i,j,k;for(i=0;i<NUMBER;i+)for(j=0;j<G;j+)for(k=0;k<G;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(

15、)%1000/1000;if(a<=M&&b<=N)for(i=0;i<NUMBER;i+)V_numberi=0;for(j=0;j<G;j+)Vij.a=vij.a;Vij.b=vij.b;for(k=0;k<G;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=

16、0;for(i=0;i<NUMBER;i+)for(j=0;j<G;j+)if(Tj=1)temp2=1;elsefor(k=0;k<G;k+) if(vik.a=Bij.a)&&(vik.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(a<=M&&b>N)for(i=0;i<NUMBER;i+)V_numberi=0;for(j=0;j<G;j+)Vij.a=v

17、ij.a;Vij.b=vij.b;for(k=0;k<G;k+)if(vik.a=Aij.a)&&(vik.b=Aij.b)temp1=1;if(temp1=0)ViV_numberi+G.a=Aij.a;ViV_numberi+G.b=Aij.b;V_numberi+;elsetemp1=0;else if(a>M&&b<=N)for(i=0;i<NUMBER;i+)V_numberi=0;for(j=0;j<G;j+)Vij.a=vij.a;Vij.b=vij.b;for(k=0;k<G;k+)if(vik.a=Bij.a

18、)&&(vik.b=Bij.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;i<NUMBER;i+)for(j=0;j<G;j+) Vij.a=vij.a;Vij.b=vij.b;V_numberi=G;/-更新位置-/void hwj_X()int i,j;for(i=0;i<NUMBER;i+)for(j=0;j<V_numberi;j+)hwj_swap(&UnitiVij.a,&UnitiVij.b);/-找到最短路徑-/void hwj_best()int temp;int i,j;for(i=0;i<NUMBER