《旅行商问题JAVA代码.docx》由会员分享，可在线阅读，更多相关《旅行商问题JAVA代码.docx（17页珍藏版）》请在金锄头文库上搜索。
1、import java.util.*;public class Tsp private String cityName=北京,上海,天津,重庆,哈尔滨,长春,沈阳,呼和浩特,石家庄,太原,济南,郑州,西安,兰州,银川,西宁,乌鲁木齐,合肥,南京,杭州,长沙,南昌,武汉,成都,贵州,福建,台北,广州,海口,南宁,昆明,拉萨,香港,澳门; /private String cityEnd=new String34; private int cityNum=cityName.length; /城市个数 private int popSize = 50; /种群数量 private int maxgen
2、s = 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 selectP; /选择概率 double except
3、p; /期望概率 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 cityNum; j+) int r = (int) (M
4、ath.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.fitness = 0; citysi.selectP =
5、 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 & badpopSize-1) bad +; f
6、or(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 cityNum; i+) if(citysx.
7、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 doubledimension; temp = gp(x, d
8、imension); 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 dimension; j+) if(tempj = k) double item = tem
