| 遗传算法 | 您所在的位置：网站首页 › 遗传算法java实现 › 遗传算法 |
遗传算法
|
嗯哼，第一次写博客，准确说是第一次通过文字的方式记录自己的工作，闲话少叙，技术汪的博客就该直奔技术主题（关于排版问题，会在不断写博客的过程中慢慢学习，先将就着用吧，重在技术嘛~~~）。 遗传算法（Genetic Algorithm, GA），作为很多人接触智能优化算法的第一个算法，互联网上关于遗传算法的资料不可谓不多，但由于其不是本文的重点，故在此不过细展开，只简单说下大概思想：根据现代生物学理论 “物竞天择，适者生存” 原理，不断淘汰适应能力差的个体，模拟生物进化过程。大致步骤为： 生成一个初始种群（Initial Population）； 通过计算种群中各个个体（Individual）的适应度（Fitness）大小来表示种群中各个个体的对环境的适应能力； 根据 “适者生存” 原则选择（Select）部分个体繁衍（即Cross、Mutation操作）生成子代种群； 判断是否满足进化结束条件（即算法终止条件）. 若满足，结束进化，输出结果；否则，重复执行步骤2~3.[注]本文用于求解TSP的遗传算法并非经典遗传算法，而是针对TSP特征写的一个简化版的遗传算法，求解质量比较low，毕竟是第一个java程序，还是要预留些改进空间么不是~~~，下一篇文章将针对本文所用的遗传算法进行改进，给个传送门（Java版GA_TSP （2））。 旅行商问题（Travel Salesman Problem, TSP）作为运筹学分支组合优化中的经典问题，一直备受关注。大白话的说法是：一个旅行商从某一城市出发，希望以最短的路程完成对N个城市的巡回访问，并最终回到出发城市。专业一点的说法是：在有向图中，从某一点开始，以最小代价不重不漏的遍历所有点，并返回初始点。 关于Java必须多说两句。首先，Java语言是新学的，之前一直用的MATLAB，然而实验室的工作站带MATLAB还可以，自己的破笔记本实在带不动。感觉每次用MATLAB运行代码，我的小本都会经历一场生死，从点击“Run” 360小球噌的一下窜上95%那一瞬间，仿佛全世界就是剩下了小本呼哧呼哧的挣扎。 本着人道主义精神，终于在某个深夜卸载了MATLAB，顿时感觉小本的重量都轻了许多（可能是幻觉吧）。MATLAB是卸载了，但毕业还要写代码啊，总不能不毕业吧，所以之后选用Python试了试，相比动辄十几个G的MATLAB，几十M的Python用起来确实不错，在加上Python语言本身确实简单，对代码汪想法的快速程序表达非常友好，以及那句“人生苦短，我用Python”，使得我一度认为Python应该就是我的最终选择了，但是……但是……但是用Python跑了GA&TSP后我就动摇了，运行速度着实堪忧，可能是自己技术太渣，即使使用Pypy也不能达到我的预期，而作为对算法实现效率有着苛刻要求的组合优化问题，为了把其他论文中的求解结果给PK下去，所以……所以……所以我又抛弃了Python。 之所以没有选用高效率的且大一就学过的C语言，则是因为实在搞不定C语言的内存管理，对于指针的使用更是随心而动，致使最后Debug的时候就像二哈咬刺猬，都不知道从哪下口…… 嗯哼，然后就是Java了，选择Java就是在使用了排除法后的选择，兼顾了我笔记本的性能缺陷与运行效率。说了这么多，终于到达战场，干货出场：
遗传算法示意图 下面上代码： Data类：用来放客户点的坐标，也可以用I/O流从外部文件中获取。 1 package GA; 2 3 public class Data { 4 public static double[][] XY(){ 5 double [][] xy = new double [][] { 6 { 1304 , 2312 } , 7 { 3639 , 1315 } , 8 { 4177 , 2244 } , 9 { 3712 , 1399 } , 10 { 3488 , 1535 } , 11 { 3326 , 1556 } , 12 { 3238 , 1229 } , 13 { 4196 , 1004 } , 14 { 4312 , 790 } , 15 { 4386 , 570 } , 16 { 3007 , 1970 } , 17 { 2562 , 1756 } , 18 { 2788 , 1491 } , 19 { 2381 , 1676 } , 20 { 1332 , 695 } , 21 { 3715 , 1678 } , 22 { 3918 , 2179 } , 23 { 4061 , 2370 } , 24 { 3780 , 2212 } , 25 { 3676 , 2578 } , 26 { 4029 , 2838 } , 27 { 4263 , 2931 } , 28 { 3429 , 1908 } , 29 { 3507 , 2367 } , 30 { 3394 , 2643 } , 31 { 3439 , 3201 } , 32 { 2935 , 3240 } , 33 { 3140 , 3550 } , 34 { 2545 , 2357 } , 35 { 2778 , 2826 } , 36 { 2370 , 2975 } 37 }; 38 return xy; 39 } 40 }
DistanceMatrix类：用来计算各客户点间的欧氏距离。原打算也放在GATSP类中，但考虑到有些问题中距离矩阵是给定的，而不是通过公式计算得到的，就单独拿出来了。 1 package GA; 2 3 public class DistanceMatrix { 4 public static double[][] DistMatrix(double[][] xy){ 5 //计算距离矩阵 6 int N = xy.length; 7 double[][] DM = new double[N][N]; 8 for (int i = 0; i < N; i++) { 9 for (int j = 0; j < N; j++) { 10 DM[i][j] = Math.hypot(xy[i][0] - xy[j][0],xy[i][1] - xy[j][1]); 11 } 12 } 13 return DM; 14 } 15 }
Pop类：用来放置对Pop的操作方法，包括计算适应度的fit()函数（貌似这个命名不规范，但是我懒呀，我就不改，你能怎样？？？）和寻找并记录最有个体的Max()函数（写这个函数以及初始化种群的时候非常怀恋MATLAB，MATLAB中自带的的max()能够同时获取最大值的索引，初始化种群就更简单了，一个randperm()解决所有问题。） 1 package GA; 2 3 public class Pop { 4 5 public static double fit(int[] Ind) { 6 //计算适应度函数 7 double[][] xy = Data.XY(); 8 double[][] DM = DistanceMatrix.DistMatrix(xy); 9 double dist = 0.0; 10 int s = Ind.length; 11 12 for (int i0 = 0; i0 < s - 1; i0++) { 13 dist += DM[Ind[i0] - 1][Ind[i0 + 1] - 1]; 14 } 15 dist += DM[Ind[Ind.length - 1] - 1][Ind[0] - 1]; 16 return 1/dist; 17 } 18 19 public static double[] Max(double[] Fit) { 20 //寻找最优个体及相应的位置 21 double[] max = new double[2]; 22 double maxFit = 0.0; 23 double maxIndex = -1; 24 for (int i = 0; i < Fit.length; i++) { 25 if (Fit[i] > maxFit) { 26 maxFit = Fit[i]; 27 maxIndex = (double)i; 28 } 29 } 30 max[0] = maxFit; 31 max[1] = maxIndex; 32 return max; 33 } 34 }
Sharking类：存放扰动算子，想着以后其他智能算法中也能用得着，就一次性造好轮子，以后就能直接用了，写这几个扰动算子的时候也想夸夸MATLAB强大的轮子库, 如fliplr() 就是很好的轮子，还有对数组的各种切割、拼接神奇操作，让我只能一边痛苦的造着轮子，一边默念“效率第一，Java无敌”…… 1 package GA; 2 3 import java.util.Random; 4 5 public class Sharking { 6 7 public static int[] Swap(int[] S) { 8 //交换操作 9 10 Random rand = new Random(); 11 int I = rand.nextInt(S.length); 12 int J = rand.nextInt(S.length); 13 14 int tmp = S[I]; 15 S[I] = S[J]; 16 S[J] = tmp; 17 18 return S; 19 } 20 21 public static int[] Flip(int[] S) { 22 //翻转操作 23 24 int[] S0 = new int [S.length]; 25 26 Random rand = new Random(); 27 int tmpI = rand.nextInt(S.length); 28 int tmpJ = tmpI; 29 while(tmpI==tmpJ) { 30 tmpJ = rand.nextInt(S.length); 31 } 32 int I = Math.min(tmpI, tmpJ); 33 int J = Math.max(tmpI, tmpJ); 34 35 for (int i = 0; i < S0.length;i++) { 36 if (i >= I && i = I && i 23->29->19->……”这种结果，心里实在不是很平衡，所以，我决定……下次学习下Java的绘图。 Ps:还是截图纪念下第一次Java写遗传算法~~~
[完]
|
【本文地址】