现代优化计算方法-遗传算法解决TSP问题

遗传算法解决TSP问题

用遗传算法(GA)解决TSP问题，也就是第一个大作业的简单版本。数据来源tsplib中的aat48，48个城市，对称型TSP问题，最优解为10628。
距离计算公式：

参考了大神的博客，表示感谢！
下面为java代码和详细注释：

package genetic_alogrithms;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class GA {
	private int POPsize; //种群大小
	private int CITYnum; //城市数量
	private int Iteration; //迭代次数
	private double [][] Distance; //城市间的距离矩阵
	private int [] Bestsolution; //最优解数组
	private double Bestlength; //最佳长度
	private double [] Fitness; // 适应度
	private int[][] Fatherpop; //父代种群
	private int[][] Offspringpop; //子代种群
	private double[] Pa; //累计概率
	private double Pc; //交叉概率
	private double Pm; //变异概率
	private int t; //当前的代数
	private int bestT; //最佳路径出现的代数
	
	// 构造函数
	public GA(int POPsize,int CITYnum,int Iteration,double Pc,double Pm){
		this.POPsize = POPsize;
		this.CITYnum = CITYnum;
		this.Iteration = Iteration;
		this.Pc = Pc;
		this.Pm = Pm;	
	}
	
	// 读取数据
	public void read_data(String filename) throws IOException{
		int[] x = new int[CITYnum]; //定义x坐标
		int[] y = new int[CITYnum]; //定义y坐标
		Distance = new double[CITYnum][CITYnum]; //定义距离矩阵
		String strbuff;
		@SuppressWarnings("resource")
		BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); //读取数据文件
		// 获得每个城市的坐标
		for(int i=0;i<CITYnum;i++){
			strbuff = data.readLine();
			String[] s = strbuff.split(" "); //数据之间有空格
			x[i] = Integer.valueOf(s[1]); //读取x坐标
			y[i] = Integer.valueOf(s[2]); //读取y坐标
		}
		// 计算距离获得距离矩阵
		for(int i=0;i<CITYnum;i++){
			for(int j=0;j<CITYnum;j++){
				double Dij = Math.sqrt(((Math.pow(x[i]-x[j], 2))+(Math.pow(y[i]-y[j], 2)))/10.0); //距离计算公式
				Distance[i][j] = Dij;
			}
		}
		// 测试数据是否读入
//		for(int i=0;i<48;i++){
//			for(int j=0;j<48;j++){
//				System.out.println(Distance[i][j]);
//			}
//		}
	}
	
	// 初始化种群
	public void initGroup(){
		// 初始化
		Fatherpop = new int[POPsize][CITYnum];
		Offspringpop = new int[POPsize][CITYnum];
		Bestsolution = new int[CITYnum];
		Fitness = new double[POPsize];
		Pa = new double[POPsize];
		Bestlength = Integer.MAX_VALUE;
		t = 0;
		int i,j,k;
		for(i=0;i<POPsize;i++){
			for(j=0;j<CITYnum;){
				Fatherpop[i][j] = (int) (Math.random()*48); //父代随机赋值[0,48)
				// 判断是否有重复元素
				for(k=0;k<j;k++){
					if(Fatherpop[i][k]==Fatherpop[i][j]){ 
						break;
					}
				}
				if(k==j){
					j++;
				}
			}
		}
	}
	
	// 计算出每个染色体所代表的距离数值
		public double getDistance(int[] chromosome){
			double length = 0.0;
			for(int i=1;i<CITYnum;i++){
				length += Distance[chromosome[i-1]][chromosome[i]]; //得到中间城市的距离
			}
			length += Distance[chromosome[CITYnum-1]][chromosome[0]]; //首尾城市的距离
			return length;
		}
	
	// 得到每个染色体的适应度数组
	public void getFitness(){
		for(int i=0;i<POPsize;i++){
			Fitness[i] = getDistance(Fatherpop[i]);
		}
	}
	
	// 计算累积概率
	public void getPa(){
		double TotalFitness = 0; //定义种群的总的适应度
		double[] fit = new double[POPsize];
		// 计算出总适应度
		for(int i=0;i<POPsize;i++){
			fit[i] = 10.0/Fitness[i];
			TotalFitness += fit[i];
		}
		// 计算累积概率
		Pa[0] = fit[0]/TotalFitness;
		for(int j=1;j<POPsize;j++){
			Pa[j] = (fit[j]/TotalFitness) + Pa[j-1];
		}
	}
	
	// 复制染色体
		public void copyChromosome(int a,int b){
			for(int i=0;i<CITYnum;i++){
				Offspringpop[a][i] = Fatherpop[b][i];
			}
		}
	
	// 轮盘赌选择
	public void STW(){
		int selectID; //选中的父代染色体编号
		int i ,j;  //i为子代染色体编号
		for(i=0;i<POPsize;i++){
			double p = Math.random();
			for(j=0;j<POPsize;j++){
				if(p <= Pa[j]){
					break;
				}
			}
			selectID = j;
			copyChromosome(i,selectID); //把父代选中的染色体复制给子代
		}
	}

	// 选择最好的个体
	public void selectBest(){
		double best;
		int bestID = 0;
		// 获得最好个体的适应度
		best = Fitness[0];
		for(int i=0;i<POPsize;i++){
			if(best>Fitness[i]){
				best = Fitness[i];
				bestID = i;
			}
		}
		// 获得出现最好的染色体出现的代数
		if(Bestlength>best){
			Bestlength = best;
			bestT = t; 
		}
		// 获得最佳的染色体
		for(int i=0;i<CITYnum;i++){
			Bestsolution[i] = Fatherpop[bestID][i];
		}
	}
	
	// 交叉算子
	public void crossover(int a,int b){
		int rank1,rank2,i,j,flag,k;
		rank1 = (int) (Math.random()*48);
		rank2 = (int) (Math.random()*48);
		int[] chro1 = new int[CITYnum];
		int[] chro2 = new int[CITYnum];
		
		// 得到chro1[]
		// 得到染色体b中和染色体a的(rank1)位置及其以后位置不相同的信息，一共有(rank1)个
		for(k=0,j=0;k<CITYnum;k++){
			chro1[j] = Offspringpop[b][k];
			for(i=rank1;i<CITYnum;i++){
				if(Offspringpop[a][i] == chro1[j]){
					break;
				}
			}
			if(i == CITYnum){
				j++;
			}
	    }
		// 将染色体a的rank1位置及其以后位置给chro1[]
		flag = rank1;
		for(i=flag,j=flag;j<CITYnum;i++,j++){
			chro1[j] = Offspringpop[a][i];
		}
		
		// 得到chro2[]
		flag = rank2;
		// 得到a染色体不同于b染色体前rank2个的信息，为(rank2)个
		for(k=0,j=0;k<CITYnum;k++){
			chro2[j] = Offspringpop[a][k];
			// 确保每个编码不相同
			for(i=flag;i<CITYnum;i++){
				if(Offspringpop[b][i] == chro2[j]){
					break;
				}
			}
			if (i == CITYnum){
				j++;
			}
		}
		// 将前b染色体中前rank2中的信息给到chro1[]中
		for(i=flag,j=flag;j<CITYnum;j++,i++){
			chro2[i] = Offspringpop[b][j];
		}
		// 得到交叉完成后的染色体
		for(i=0;i<CITYnum;i++){
			Offspringpop[a][i] = chro1[i];
			Offspringpop[b][i] = chro2[i];
		}
	}
	
	// 随机交换型变异
	public void mutation(int a){
		int cnt,rank1,rank2,temp;
		cnt = (int)(Math.random()*48); //交换次数
		for(int i=0;i<cnt;i++){
			rank1 = (int)(Math.random()*48);
			rank2 = (int)(Math.random()*48);
			while(rank1 == rank2){
				rank2 = (int)(Math.random()*48);
			}
			// 交换
			temp = Offspringpop[a][rank1];
			Offspringpop[a][rank1] = Offspringpop[a][rank2];
			Offspringpop[a][rank2] = temp;
		}
	}
	
	// 进化（遗传+交叉+变异）
	public void evolution(){
		int i;
		double p;
		selectBest(); //得到最好的路径、最好的长度、出现最好路径的代数
		STW(); //轮盘赌选择父代，获取子代
		for(i=0;i<POPsize;i=i+2){
			p = Math.random();
			// 是否交叉
			if(p<Pc){
				crossover(i,i+1);
				}
			p = Math.random();
			// 是否变异
			if(p<Pm){
			    mutation(i);
				}
		    p = Math.random();
			if(p<Pm){
				mutation(i+1);
			    }
	     	}
		}	
	// 遗传算法
	public void ga(){
		initGroup(); //初始化种群
		getFitness(); //得到种群适应度
		getPa(); //得到累积概率
		for(t=0;t<Iteration;t++){
			evolution(); //进化 
			for(int i=0;i<POPsize;i++){
				for(int j=0;j<CITYnum;j++){
					Fatherpop[i][j] = Offspringpop[i][j]; //将子代的信息给父代，准备下一次进化
				}
			}
		 getFitness(); //得到新一代种群的适应度
		 getPa(); //得到新一代种群的累积概率
		}
		System.out.println("最佳长度出现的代数："+bestT);
		System.out.println("最佳长度："+Bestlength);
		System.out.print("最佳路径：");
		// 打印最佳路径
		for(int i=0;i<CITYnum;i++){
			System.out.print(Bestsolution[i]+" "); 
		}
	}
	
	public static void main(String[] args) throws IOException {
		GA g =new GA(240,48,5000,0.9,0.2); //构造GA类
		g.read_data("/home/mouye/aat48.txt"); //读取数据
		g.ga(); //调用遗传算法
	}
}

赏

谢谢老板

支付宝

微信