粒子群算法解決TSP問題

《粒子群算法解決TSP問題》由會員分享，可在線閱讀，更多相關《粒子群算法解決TSP問題（15頁珍藏版）》請在裝配圖網上搜索。

1、 河南理工大學 計算機科學與技術學院 課程設計報告 2014— 2015學年第一學期 課程名稱 Java語言程序設計 設計題目 利用粒子群算法解決TSP問題 姓 名 朱超琦 學 號 3613090102 專業(yè)班級 計科合13 指導教師 劉 志 中 2015年 1 月 2 日 目錄 一．課程設計內容 2 (一)課程設計題目 2 (二)課程設計目的 2

2、 (三)課程設計要求 2 二．算法相關知識 2 (一) 粒子群算法簡介 2 (二) 人工生命簡介 3 (三) 粒子群算法的流程圖及偽代碼： 4 三.算法的JAVA實現 5 四. 課程設計的總結體會 14 五．參考文獻 14 一．課程設計內容 (一)課程設計題目 應用粒子群算法(Particle Swarm Optimization) 求解 旅行商問題（TSP）； 旅行商問題： 即TSP問題（Travelling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要

3、拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值 (二)課程設計目的 1.訓練應用算法求解實際問題； 2訓練應用Java語言實現具體問題的求解算法； 3.到達理解java語言的應用特點以及熟練應用java語言的目標。 (三)課程設計要求 1.讀懂算法，理解算法計算過程中每一步操作是如何實現的； 2.設計函數優(yōu)化的編碼格式； 3.采用java 語言編程實現算法的求解過程； 4.掌握粒子群算法的基本原理 ,了解在JAVA 環(huán)境中實現粒子群算法的過程。 二．算法相關知識

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

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

6、) present[i] = present[i] + v[i] 其中v[i]代表第i個粒子的速度，w代表慣性權值,c1和c2表示學習參數，rand()表示在0-1之間的隨機數,pbest[i]代表第i個粒子搜索到的最優(yōu)值,gbest代表整個集群搜索到的最優(yōu)值,present[i]代表第i個粒子的當前位置。 (二) 人工生命簡介 "人工生命"是來研究具有某些生命基本特征的人工系統。 兩方面內容 1. 研究如何利用計算技術研究生物現象 2. 研究如何利用生物技術研究計算問題 我們現在關注的是第二部分的內容。 現在已經有很多源于生物現象的計算技巧. 例如,人工神經網絡是簡化

7、的大腦模型。遺傳算法是模擬基因進化過程的. 社會系統。 現在我們討論另一種生物系統- 社會系統。更確切的是, 在由簡單個體組成的群落與環(huán)境以及個體之間的互動行為。 也可稱做"群智能"(swarm intelligence). 這些模擬系統利用局部信息從而可能產生不可預測的群體行為 例如floys 和birds 他們都用來模擬魚群和鳥群的運動規(guī)律, 主要用于計算機視覺和計算機輔助設計。 在計算智能(computational intelligence)領域有兩種基于群智能的算法.蟻群算法(ant colony optimization)和PSO粒子群算法(particle swarm o

8、ptimization). 前者是對螞蟻群落食物采集過程的模擬。已經成功運用在很多離散優(yōu)化問題上。粒子群優(yōu)化算法(PSO) 也是起源對簡單社會系統的模擬。 最初設想是模擬鳥群覓食的過程. 但后來發(fā)現PSO是一種很好的優(yōu)化工具。 (三) 粒子群算法的流程圖及偽代碼： 1.流程圖： 2.偽代碼： For each particle ____Initialize particle END Do ____For each particle ________Calculate fitness value ________If the fitness value is b

9、etter than the best fitness value (pBest) in history ____________set current value as the new pBest ____End ____Choose the particle with the best fitness value of all the particles as the gBest ____For each particle ________Calculate particle velocity according equation (a) ________Update part

10、icle position according equation (b) ____End While maximum iterations or minimum error criteria is not attained 3.PSO的參數設置： 從上面的例子我們可以看到應用PSO解決優(yōu)化問題的過程中有兩個重要的步驟: 問題解的編碼和適應度函數。 PSO的一個優(yōu)勢就是采用實數編碼, 不需要像遺傳算法一樣是二進制編碼(或者采用針對實數的遺傳操作。例如對于問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應度函數就

11、是f(x)。 接著我們就可以利用前面的過程去尋優(yōu).這個尋優(yōu)過程是一個疊代過程，中止條件一般為設置為達到最大循環(huán)數或者最小錯誤PSO中并沒有許多需要調節(jié)的參數，下面列出了這些參數以及經驗設置 粒子數: 一般取 20 – 40. 其實對于大部分的問題10個粒子已經足夠可以取得好的結果, 不過對于比較難的問題或者特定類別的問題，粒子數可以取到100 或 200 粒子的長度: 這是由優(yōu)化問題決定, 就是問題解的長度 粒子的范圍: 由優(yōu)化問題決定,每一維可是設定不同的范圍 Vmax: 最大速度，決定粒子在一個循環(huán)中最大的移動距離,通常設定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2

12、, x3) x1 屬于 [-10, 10], 那么 Vmax 的大小就是 20 學習因子: c1 和 c2 通常等于 2. 不過在文獻中也有其他的取值. 但是一般 c1 等于 c2 并且范圍在0和4之間。 中止條件: 最大循環(huán)數以及最小錯誤要求. 例如, 在上面的神經網絡訓練例子中, 最小錯誤可以設定為1個錯誤分類, 最大循環(huán)設定為2000, 這個中止條件由具體的問題確定. 全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優(yōu)化算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優(yōu). 后者收斂速度慢一點不過很難陷入局部最優(yōu). 在實際應用中, 可以先用全局PSO找到大致的結果,再有局

13、部PSO進行搜索. 三.算法的JAVA實現 代碼實現： package noah; public class SO { private int x; private int y; public SO(int x,int y) { this.x=x; this.y=y; } public int getX() { return x; } public void setX(int x) { th

14、is.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public void print() { System.out.println("x:"+this.x+" y:"+this.y); } } package noah; import java.io.BufferedReader; impo

15、rt java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Random; public class PSO { private int bestNum; private float w; private int MAX_GEN;// 迭代次數 private int scale;// 種群規(guī)模 private int cityNum; // 城市數

16、量，編碼長度 private int t;// 當前代數 private int[][] distance; // 距離矩陣 private int[][] oPopulation;// 粒子群 private ArrayList> listV;// 每科粒子的初始交換序列 private int[][] Pd;// 一顆粒子歷代中出現最好的解， private int[] vPd;// 解的評價值 private int[] Pgd;// 整個粒子群經歷過的的最好的解，每個粒子都能記住自己搜索到的最好解 private int vP

17、gd;// 最好的解的評價值 private int bestT;// 最佳出現代數 private int[] fitness;// 種群適應度，表示種群中各個個體的適應度 private Random random; public PSO() { } public PSO(int n, int g, int s, float w) { this.cityNum = n; this.MAX_GEN = g; this.scale = s; this.w = w; } * 初始化PSO算法類 * @param file

18、name 數據文件名，該文件存儲所有城市節(jié)點坐標數據 * @throws IOException */ private void init(String filename) throws IOException { // 讀取數據 int[] x; int[] y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename))); distance = new int[cit

19、yNum][cityNum]; x = new int[cityNum]; y = new int[cityNum]; for (int i = 0; i < cityNum; i++) { // 讀取一行數據，數據格式1 6734 1453 strbuff = data.readLine(); // 字符分割 String[] strcol = strbuff.split(" "); x[i] = Integer.valueOf(strcol[1]);// x坐標 y[i] = Integer.valueOf(strcol[2

20、]);// y坐標 } // 計算距離矩陣 // ，針對具體問題，距離計算方法也不一樣，此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優(yōu)值為10628 for (int i = 0; i < cityNum - 1; i++) { distance[i][i] = 0; // 對角線為0 for (int j = i + 1; j < cityNum; j++) { double rij = Math .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]

21、) * (y[i] - y[j])) / 10.0); // 四舍五入，取整 int tij = (int) Math.round(rij); if (tij < rij) { distance[i][j] = tij + 1; distance[j][i] = distance[i][j]; } else { distance[i][j] = tij; distance[j][i] = distance[i][j]; } } } distance[cityN

22、um - 1][cityNum - 1] = 0; oPopulation = new int[scale][cityNum]; fitness = new int[scale]; Pd = new int[scale][cityNum]; vPd = new int[scale]; Pgd = new int[cityNum]; vPgd = Integer.MAX_VALUE; bestT = 0; t = 0; random = new Random(System.currentTimeMillis()); } //

23、初始化種群，多種隨機生成辦法 void initGroup() { int i, j, k; for (k = 0; k < scale; k++){ oPopulation[k][0] = random.nextInt(65535) % cityNum; for (i = 1; i < cityNum;){ oPopulation[k][i] = random.nextInt(65535) % cityNum; for (j = 0; j < i; j++) { if (oPopulation[k][i] == oPopulat

24、ion[k][j]) { break; } } if (j == i) { i++; } } } } void initListV() { int ra; int raA; int raB; listV = new ArrayList>(); for (int i = 0; i < scale; i++) { ArrayList list = new ArrayList(); ra = random.ne

25、xtInt(65535) % cityNum; for (int j = 0; j < ra; j++) { raA = random.nextInt(65535) % cityNum; raB = random.nextInt(65535) % cityNum; while (raA == raB) { raB = random.nextInt(65535) % cityNum; } // raA與raB不一樣 SO s = new SO(raA, raB); list.add(s); }

26、 listV.add(list); } } public int evaluate(int[] chr) { // 0123 int len = 0; // 編碼，起始城市,城市1,城市2...城市n for (int i = 1; i < cityNum; i++) { len += distance[chr[i - 1]][chr[i]]; } // 城市n,起始城市 len += distance[chr[cityNum - 1]][chr[0]]; return len; } // 求一個基本交

27、換序列作用于編碼arr后的編碼 public void add(int[] arr, ArrayList list) { int temp = -1; SO s; for (int i = 0; i < list.size(); i++) { s = list.get(i); temp = arr[s.getX()]; arr[s.getX()] = arr[s.getY()]; arr[s.getY()] = temp; } } // 求兩個編碼的基本交換序列，如A-B=SS public ArrayList

28、 minus(int[] a, int[] b) { int[] temp = b.clone(); /* * int[] temp=new int[L]; for(int i=0;i list = new ArrayList(); for (int i = 0; i < cityNum; i++) { if (a[i] != temp[i]) { /

29、/ 在temp中找出與a[i]相同數值的下標index index = findNum(temp, a[i]); // 在temp中交換下標i與下標index的值 changeIndex(temp, i, index); // 記住交換子 s = new SO(i, index); // 保存交換子 list.add(s); } } return list; } // 在arr數組中查找num，返回num的下標 public int findNum(int[] arr, int num)

30、{ int index = -1; for (int i = 0; i < cityNum; i++) { if (arr[i] == num) { index = i; break; } } return index; } // 將數組arr下標index1與下標index2的值交換 public void changeIndex(int[] arr, int index1, int index2) { int temp = arr[index1]; arr[index1] = arr[index2];

31、 arr[index2] = temp; } // 二維數組拷貝 public void copyarray(int[][] from, int[][] to) { for (int i = 0; i < scale; i++) { for (int j = 0; j < cityNum; j++) { to[i][j] = from[i][j]; } } } // 一維數組拷貝 public void copyarrayNum(int[] from, int[] to) { for (int i = 0; i < c

32、ityNum; i++) { to[i] = from[i]; } } public void evolution() { int i, j, k; int len = 0; float ra = 0f; ArrayList Vi; // 迭代一次 for (t = 0; t < MAX_GEN; t++) { // 對于每顆粒子 for (i = 0; i < scale; i++) { if(i==bestNum) continue; ArrayList Vii = new

33、ArrayList(); //System.out.println("------------------------------"); // 更新速度 // Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid) Vi = listV.get(i); // wVi+表示獲取Vi中size*w取整個交換序列 len = (int) (Vi.size() * w); //越界判斷 //if(len>cityNum) len=cityNum; //System.out.println("w:"

34、+w+" len:"+len+" Vi.size():"+Vi.size()); for (j = 0; j < len; j++) { Vii.add(Vi.get(j)); } ArrayList a = minus(Pd[i], oPopulation[i]); ra = random.nextFloat(); len = (int) (a.size() * ra); //越界判斷 for (j = 0; j < len; j++) { Vii.add(a.get(j));

35、 } ArrayList b = minus(Pgd, oPopulation[i]); ra = random.nextFloat(); // ra(Pid-Xid)+ len = (int) (b.size() * ra); //越界判斷 for (j = 0; j < len; j++) { SO tt= b.get(j); Vii.add(tt); } listV.add(i, Vii); add(oPopulation[i], Vii); }

36、 // 計算新粒子群適應度，Fitness[max],選出最好的解 for (k = 0; k < scale; k++) { fitness[k] = evaluate(oPopulation[k]); if (vPd[k] > fitness[k]) { vPd[k] = fitness[k]; copyarrayNum(oPopulation[k], Pd[k]); bestNum=k; } if (vPgd > vPd[k]) { System.out.println("最佳長度"+v

37、Pgd+" 代數："+bestT); bestT = t; vPgd = vPd[k]; copyarrayNum(Pd[k], Pgd); } } } } public void solve() { int i; int k; initGroup(); initListV(); // 每顆粒子記住自己最好的解 copyarray(oPopulation, Pd); // 計算初始化種群適應度，Fitness[max],選出最好的解 for (k = 0; k

38、 < scale; k++) { fitness[k] = evaluate(oPopulation[k]); vPd[k] = fitness[k]; if (vPgd > vPd[k]) { vPgd = vPd[k]; copyarrayNum(Pd[k], Pgd); bestNum=k; } } // 打印 System.out.println("初始粒子群..."); for (k = 0; k < scale; k++) { for (i = 0; i < cityNum; i++)

39、 { System.out.print(oPopulation[k][i] + ","); } System.out.println(); System.out.println("----" + fitness[k]); } // 進化 evolution(); // 打印 System.out.println("最后粒子群..."); for (k = 0; k < scale; k++) { for (i = 0; i < cityNum; i++) { System.out.print(oPopu

40、lation[k][i] + ","); } System.out.println(); System.out.println("----" + fitness[k]); } System.out.println("最佳長度出現代數："); System.out.println(bestT); System.out.println("最佳長度"); System.out.println(vPgd); System.out.println("最佳路徑："); for (i = 0; i < cityNum; i++) {

41、System.out.print(Pgd[i] + ","); } } public static void main(String[] args) throws IOException { System.out.println("Start...."); PSO pso = new PSO(48, 5000, 30, 0.5f); pso.init("c://data.txt"); pso.solve(); } } (二)運行結果 4. 課程設計的總結體會 通過這次的課程設計，我的能力的到了很大提升，也學到了很多東西。課程設計中遇到的一系列問題，都通過討論或請教老師得到了解決，這次課程設計收貨很多，學會很多 五．參考文獻 [1]《離散粒子群優(yōu)化算法及其應用》郭文忠 陳國龍，清華大學出版社 [2]《JAVA基礎入門》傳智博客，清華大學出版社