Tsp遗传算法代码非常好(共10页).doc

《Tsp遗传算法代码非常好(共10页).doc》由会员分享，可在线阅读，更多相关《Tsp遗传算法代码非常好(共10页).doc（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上package GA;import java.util.*;public class Tsp private String cityName=北京,上海,天津,重庆,哈尔滨,长春,沈阳,呼和浩特,石家庄,太原,济南,郑州,西安,兰州,银川,西宁,乌鲁木齐,合肥,南京,杭州,长沙,南昌,武汉,成都,贵州,福建,台北,广州,海口,南宁,昆明,拉萨,香港,澳门; /private String cityEnd=new String34; private int cityNum=cityName.length; /城市个数 private int popSize = 50;

2、/种群数量 private int maxgens = 20000; /迭代次数 private double pxover = 0.8; /交叉概率 private double pmultation = 0.05; /变异概率 private long distance = new longcityNumcityNum; private int range = 2000; /用于判断何时停止的数组区间 private class genotype int city = new intcityNum; /单个基因的城市序列 long fitness; /该基因的适应度 double sele

3、ctP; /选择概率 double exceptp; /期望概率 int isSelected; /是否被选择 private genotype citys = new genotypepopSize; /* * 构造函数，初始化种群 */ public Tsp() for (int i = 0; i popSize; i+) citysi = new genotype(); int num = new intcityNum; for (int j = 0; j cityNum; j+) numj = j; int temp = cityNum; for (int j = 0; j cityN

4、um; j+) int r = (int) (Math.random() * temp); citysi.cityj = numr; numr = numtemp - 1; temp-; citysi.fitness = 0; citysi.selectP = 0; citysi.exceptp = 0; citysi.isSelected = 0; initDistance(); /* * 计算每个种群每个基因个体的适应度，选择概率，期望概率，和是否被选择。 */ public void CalAll() for( int i = 0; i popSize; i+) citysi.fitne

5、ss = 0; citysi.selectP = 0; citysi.exceptp = 0; citysi.isSelected = 0; CalFitness(); CalSelectP(); CalExceptP(); CalIsSelected(); /* * 填充，将多选的填充到未选的个体当中 */ public void pad() int best = 0; int bad = 0; while(true) while(citysbest.isSelected = 1 & bestpopSize-1) best +; while(citysbad.isSelected != 0

6、& badpopSize-1) bad +; for(int i = 0; i0) x = (int)(Math.random()*popSize); y = (int)(Math.random()*popSize); executeCrossover(x,y);/x y 两个体执行交叉 pop-; /* * 执行交叉函数 * param 个体x * param 个体y * 对个体x和个体y执行佳点集的交叉，从而产生下一代城市序列 */ private void executeCrossover(int x,int y) int dimension = 0; for( int i = 0 ;i

7、 cityNum; i+) if(citysx.cityi != citysy.cityi) dimension +; int diffItem = 0; double diff = new doubledimension; for( int i = 0 ;i cityNum; i+) if(citysx.cityi != citysy.cityi) diffdiffItem = citysx.cityi; citysx.cityi = -1; citysy.cityi = -1; diffItem +; Arrays.sort(diff); double temp = new doubled

8、imension; temp = gp(x, dimension); for( int k = 0; k dimension;k+) for( int j = 0; j 0 ) if(citysx.citytempi = -1) citysx.citytempi = (int)diffdimension - tempDimension; tempDimension -; tempi +; Arrays.sort(diff); temp = gp(y, dimension); for( int k = 0; k dimension;k+) for( int j = 0; j 0 ) if(cit

9、ysy.citytempi = -1) citysy.citytempi = (int)diffdimension - tempDimension; tempDimension -; tempi +; /* * param individual 个体 * param dimension 维数 * return 佳点集 (用于交叉函数的交叉点） 在executeCrossover()函数中使用 */ private double gp(int individual, int dimension) double temp = new doubledimension; double temp1 =

10、new doubledimension; int p = 2 * dimension + 3; while(!isSushu(p) p+; for( int i = 0; i dimension; i+) tempi = 2*Math.cos(2*Math.PI*(i+1)/p) * (individual+1); tempi = tempi - (int)tempi; if( temp i 0) tempi = 1+tempi; for( int i = 0; i dimension; i+) temp1i = tempi; Arrays.sort(temp1); /排序 for( int

11、i = 0; i dimension; i+) for( int j = 0; j dimension; j+) if(tempj=temp1i) tempj = i; return temp; /* * 变异 */ public void mutate() double random; int temp; int temp1; int temp2; for( int i = 0 ; i popSize; i+) random = Math.random(); if(random=pmultation) temp1 = (int)(Math.random() * (cityNum); temp

12、2 = (int)(Math.random() * (cityNum); temp = citysi.citytemp1; citysi.citytemp1 = citysi.citytemp2; citysi.citytemp2 = temp; /* * 打印当前代数的所有城市序列，以及其相关的参数 */ public void print() /* * 初始化各城市之间的距离 */ private void initDistance() for (int i = 0; i cityNum; i+) for (int j = 0; j cityNum; j+) distanceij = Ma

13、th.abs(i-j); /* * 计算所有城市序列的适应度 */ private void CalFitness() for (int i = 0; i popSize; i+) for (int j = 0; j cityNum - 1; j+) citysi.fitness += distancecitysi.cityjcitysi.cityj + 1; citysi.fitness += distancecitysi.city0citysi.citycityNum - 1; /* * 计算选择概率 */ private void CalSelectP() long sum = 0; f

14、or( int i = 0; i popSize; i+) sum += citysi.fitness; for( int i = 0; i popSize; i+) citysi.selectP = (double)citysi.fitness/sum; /* * 计算期望概率 */ private void CalExceptP() for( int i = 0; i popSize; i+) citysi.exceptp = (double)citysi.selectP * popSize; /* * 计算该城市序列是否较优，较优则被选择，进入下一代 */ private void Ca

15、lIsSelected() int needSelecte = popSize; for( int i = 0; i popSize; i+) if( citysi.exceptp1) citysi.isSelected+; needSelecte -; double temp = new doublepopSize; for (int i = 0; i popSize; i+) / tempi = citysi.exceptp - (int) citysi.exceptp;/ tempi *= 10; tempi = citysi.exceptp*10; int j = 0; while (

16、needSelecte != 0) for (int i = 0; i popSize; i+) if (int) tempi = j) citysi.isSelected+; needSelecte-; if (needSelecte = 0) break; j+; /* * param x * return 判断一个数是否是素数的函数 */ private boolean isSushu( int x) if(x2) return false; for(int i=2;i=x/2;i+) if(x%i=0&x!=2) return false; return true; /* * para

17、m x 数组 * return x数组的值是否全部相等，相等则表示x.length代的最优结果相同，则算法结束 */ private boolean isSame(long x) for( int i = 0; i x.length -1; i+) if(xi !=xi+1) return false; return true; /* * 打印任意代最优的路径序列 */ private void printBestRoute() CalAll(); long temp = citys0.fitness; int index = 0; for (int i = 1; i popSize; i+)

18、 if(citysi.fitnesstemp) temp = citysi.fitness; index = i; System.out.println(); System.out.println(最佳路径的序列：); for (int j = 0; j cityNum; j+) String cityEnd=cityNamecitysindex.cityj; for(int m=0;mcityEnd.length;m+) System.out.print(cityEndm + ); /System.out.print(citysindex.cityj + cityNamecitysindex

19、.cityj + ); /System.out.print(cityNamecitysindex.cityj); System.out.println(); /* * 算法执行 */ public void run() long result = new longrange; /result初始化为所有的数字都不相等 for( int i = 0; i0) System.out.println(- 第 +num+ 代 -); CalAll(); print(); pad(); crossover(); mutate(); maxgens -; long temp = citys0.fitnes

20、s; for ( int i = 1; i popSize; i+) if(citysi.fitnesstemp) temp = citysi.fitness; System.out.println(最优的解：+temp); resultindex = temp; if(isSame(result) break; index+; if(index=range) index = 0; num+; printBestRoute(); /* * param a 开始时间 * param b 结束时间 */ public void CalTime(Calendar a,Calendar b) long

21、 x = b.getTimeInMillis() - a.getTimeInMillis(); long y = x/1000; x = x - 1000*y; System.out.println(算法执行时间：+y+.+x+ 秒); /* * 程序入口 */ public static void main(String args) Calendar a = Calendar.getInstance(); /开始时间 Tsp tsp = new Tsp(); tsp.run(); Calendar b = Calendar.getInstance(); /结束时间 tsp.CalTime(a, b); 专心-专注-专业