遗传算法——最短路径问题

在9个城市中，两两互通，通过遗传算法学习最短路径，基因库是所有路径，8个基因组成染色体。

package text;


import java.util.ArrayList;
import java.util.List;

/**
 * 遗传算法
 * 
 * @author 陈成
 *
 */
public class GeneticAlgorithm {

	/**
	 * 种群大小
	 */
	private int pop_size = 10000;// 种群大小
	/**
	 * 种群
	 */
	private Route[][] pop;// 种群
	/**
	 * 交叉概率
	 */
	private double cross_rate = 0.5;// 交叉概率
	/**
	 * 突变概率
	 */
	private double mutation_rate = 0.2;// 突变概率

	/**
	 * DNA长度
	 */
	private int DNA_length;// DNA长度
	/**
	 * 基因库
	 */
	private Route[] Gene;

	/**
	 * 构造器
	 * 
	 * @param city_xy
	 * @param cityName
	 */
	public GeneticAlgorithm（int[][] city_xy String[] cityName） {
		setGene（city_xy cityName）;
		setEarliest_pop（city_xy）;
		DNA_length = cityName.length - 1;
	}

	/**
	 * 设置基因库
	 */
	private void setGene（int[][] city_xy String[] cityName） {
		/**
		 * 城市数量
		 */
		int len = city_xy.length;

		Gene = new Route[len * （len - 1）];

		int k = 0;
		for （int i = 0; i < len; i++） {
			for （int j = 0; j < len; j++） {
				if （i != j） {
					Gene[k] = new Route（）;
					Gene[k].setStartingCity（cityName[i]）;
					Gene[k].setTargetCity（cityName[j]）;
					Gene[k].setDistance（Math.sqrt（Math.pow（absolute_value（city_xy[i][0] - city_xy[j][0]） 2）
							+ Math.pow（absolute_value（city_xy[i][1] - city_xy[j][1]） 2）））;
					k++;
				}
			}
		}
	}

	/**
	 * 绝对值
	 * 
	 * @param num
	 * @return
	 */
	private int absolute_value（int num） {

		if （num >= 0） {
			return num;
		} else {
			return -num;
		}

	}

	/**
	 * 设置初代种群
	 */
	private void setEarliest_pop（int[][] city_xy） {
		int gene_num = Gene.length;
		pop = new Route[pop_size][city_xy.length - 1];

		for （int i = 0; i < pop_size; i++） {
			for （int j = 0; j < city_xy.length - 1; j++） {
				pop[i][j] = Gene[（int） （Math.random（） * gene_num）];
			}
		}
	}

	/**
	 * 得到适应性
	 * 
	 * @return
	 */
	private double get_fitness（Route[] dna） {

		double fitness = 0;

		for （int i = 0; i < dna.length; i++） {
			fitness += dna[i].getDistance（）;
		}

		for （int i = 0; i < dna.length - 1; i++） {
			if （dna[i].getTargetCity（）.equals（dna[i + 1].getStartingCity（））） {
				fitness -= 50;
			}
		}

		for （int i = 0; i < dna.length - 1; i++） {
			for （int j = i + 1; j < dna.length; j++） {
				if （（dna[i].getStartingCity（）.equals（dna[j].getStartingCity（））
						&& dna[i].getTargetCity（）.equals（dna[j].getTargetCity（）））
						|| （dna[i].getStartingCity（）.equals（dna[j].getTargetCity（））
								&& dna[i].getTargetCity（）.equals（dna[j].getStartingCity（）））） {
					fitness += 100;
				}
			}
		}

		if （dna[0].getTargetCity（）.equals（dna[1].getStartingCity（））
				&& dna[1].getTargetCity（）.equals（dna[2].getStartingCity（））
				&& dna[2].getTargetCity（）.equals（dna[3].getStartingCity（））
				&& dna[3].getTargetCity（）.equals（dna[4].getStartingCity（））
				&& dna[4].getTargetCity（）.equals（dna[5].getStartingCity（））
				&& dna[5].getTargetCity（）.equals（dna[6].getStartingCity（））
				&& dna[6].getTargetCity（

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件         232  2018-04-15 11:25  遗传算法—最短路径问题\.classpath
     文件         409  2018-04-15 11:25  遗传算法—最短路径问题\.project
     目录           0  2018-04-30 11:01  遗传算法—最短路径问题\bin\
     目录           0  2018-04-30 11:01  遗传算法—最短路径问题\bin\text\
     文件        4584  2018-04-23 10:13  遗传算法—最短路径问题\bin\text\GeneticAlgorithm.class
     文件         476  2018-04-15 11:36  遗传算法—最短路径问题\bin\text\MyMain.class
     文件        1101  2018-04-23 09:28  遗传算法—最短路径问题\bin\text\MyThread.class
     文件         935  2018-04-15 19:58  遗传算法—最短路径问题\bin\text\Route.class
     文件         999  2018-04-23 08:42  遗传算法—最短路径问题\bin\text\Util.class
     文件         951  2018-04-23 09:56  遗传算法—最短路径问题\bin\text\Window$1.class
     文件        3264  2018-04-23 09:56  遗传算法—最短路径问题\bin\text\Window.class
     目录           0  2018-04-30 11:01  遗传算法—最短路径问题\src\
     目录           0  2018-04-30 11:01  遗传算法—最短路径问题\src\text\
     文件        5357  2018-04-23 10:13  遗传算法—最短路径问题\src\text\GeneticAlgorithm.java
     文件         135  2018-04-15 11:36  遗传算法—最短路径问题\src\text\MyMain.java
     文件         545  2018-04-23 09:28  遗传算法—最短路径问题\src\text\MyThread.java
     文件         700  2018-04-15 19:58  遗传算法—最短路径问题\src\text\Route.java
     文件         663  2018-04-23 08:42  遗传算法—最短路径问题\src\text\Util.java
     文件        2889  2018-04-23 09:56  遗传算法—最短路径问题\src\text\Window.java