遗传算法求最短路径matlab程序,最短路径算法Java

　　00-10101、问题描述2、编码3、个体类4、遗传算法解决最短路径问题的主要方法5、适应度6、选择算子7、交叉算子8、变异算子9、摘要遗传算法(GA)由美国的John holland于20世纪70年代首先提出。该算法是根据自然界生物的进化规律设计和提出的。它是模拟达尔文生物进化论的自然选择和遗传机制的生物进化过程的计算模型，是通过模拟自然进化过程来搜索最优解的方法。

　　00-1010图1显示了一个最短路径问题。每条边代表一条可通过的弧，边上的值表示这条弧的长度。许多弧连接起来形成一条路径，目标是找到一条从节点0到节点5的最短路径。

　　00-1010从表型到基因型的映射称为编码。在图1中，每条路径的每个节点对应一个基因，每条路径可以通过节点的有序组合映射成一个向量。每个向量的长度为6，起始和结束位置的值分别为0和5，分别代表节点0的起点和节点5的终点。在图1中，节点之间的边的长度表示节点之间的距离。如果两个节点无限连接，这两个节点之间的距离是一个非常大的数m，由于向量长度固定为6，且解可能不包含所有节点，所以个体中可能存在多个相邻重复的节点，所以节点与自身的距离设为0。

　　00-1010每个个体包含两个属性：路径Path和适应度长度(即路径长度)。每个个体的路径属性的起点是0，终点是5。其他位置的值随机生成(0-5范围内的整数)，向量长度固定为6。类中定义的compareTo方法用于通过在选择运算符中使用迭代器来删除个体。

　　public类Individual实现comparable Individual { int[]Path=new int[6]；//存储路径int length//表示fitness public int[]getpath(){ return path；} public void set Path(int[]Path){ Path=Path；} public int getLength(){ return length；} public void setLength(int length){ this . length=length；} public int compare to(Individual o){ if(this . getlength()o . getlength()){ return-1；} else if(this . getlength()o . getlength()){ return 1；} else { return 0；} } }

　　00-1010主要方法包括(1)数据初始化(2)初始种群定义(3)选择、交叉、变异算子的循环调用(4)迭代结果输出。图1中节点间的距离用邻接矩阵的形式表示，建立一个集合表示种群，随机产生10个个体加入初始种群完成种群初始化，设置迭代次数，依次调用三个算子更新种群，最后输出结果。详细代码如下：

　　静态int[][]matrix=new int[6][6]；最终静态int M=10000静态随机rand=new Random()；Public静态void main(string[]args){//邻接矩阵matrix [0]=new int [] {0，6，3，m，m，m }；/*1*/matrix[1]=new int[]{6，0，2，5，M，M }；/*2*/matrix[2]=new int[]{3，2，0，3，4，M }；/*3*/matrix[3]=new int[]{M，5，3，0，2，3 }；/*4*/matrix[4]=new int[]{M，M，4，2，0，5 }；/*5*/matrix[5]=new int[]{M，M，M，3，5，0 }；/*6*///定义初始群体数学

　　andom(); List<Individual> Population = new ArrayList<>(); for (int i = 0; i < 10; i++) { //随机生成十个个体添加到初始种群列表 Individual Popu = new Individual(); Popu.Path[0] = 0; Popu.Path[1] = rand.nextInt(5); Popu.Path[2] = rand.nextInt(5); Popu.Path[3] = rand.nextInt(5); Popu.Path[4] = rand.nextInt(5); Popu.Path[5] = 5; Popu.length = M; Population.add(Popu); } for(int i = 0; i<2000; i++){ System.out.println("第"+(i+1)+"次迭代开始！"); //初始种群中选择出5个较优的个体 List<Individual> NewSelPopu = Selection(Population); //交叉 List<Individual> NewCroPopu = Crossover(NewSelPopu); //变异 Population = Variation(NewCroPopu); System.out.println("第"+ (i+1) + "次迭代完成！"); } //输出迭代后的种群 System.out.print("2000次迭代后集合中个体的长度："); for(Individual a : Population){ System.out.print(a.length +" "); } //对集合中的个体排序 Collections.sort(Population); //输出排序后的集合中个体的长度 System.out.print("n" +"2000次迭代后所有个体的最短路径长度为:" + Population.get(9).length); System.out.println("n"+"最短路径为：" + Arrays.toString(Population.get(9).Path)); }

5、适应度

该问题中适应度即为每个个体所代表的路径长度，适应度函数如下：

static void Fitness(Individual in){ //计算路径长度 in.length = matrix[in.Path[0]][in.Path[1]] + matrix[in.Path[1]][in.Path[2]] + matrix[in.Path[2]][in.Path[3]] + matrix[in.Path[3]][in.Path[4]] + matrix[in.Path[4]][in.Path[5]]; }

6、选择算子

输入：包含10个个体的种群。

　　输出：包含5个个体的种群。

　　计算所输入的种群的所有个体的适应度，并按照适应度将这些个体进行升序排列，删除掉其中适应度较大的五个个体，并返回剩余的种群。代码如下：

static List<Individual> Selection(List<Individual> Population){ System.out.print("排序前集合中个体的长度："); for(Individual a : Population){ System.out.print(a.length +" "); } //对集合中的个体排序 Collections.sort(Population); //输出排序后的集合中个体的长度 System.out.print("n" +"排序后集合中个体的长度:"); for(Individual a : Population){ System.out.print(a.length +" "); } //使用迭代器删除个体 Iterator<Individual> iterator = Population.iterator(); while(iterator.hasNext() && Population.size()>5){ Individual next = iterator.next(); if(next != null) iterator.remove(); } //输出删除后的个体的长度 System.out.print("n" + "选择后的个体的长度："); for(Individual a : Population){ System.out.print(a.length +" "); } System.out.println("n" + "选择完成!"); return Population; }

7、交叉算子

输入：包含5个个体的种群。

　　输出：包含7个个体的种群。

　　在经过选择算子后生成的包含5个个体的种群中随机选择两个不同的个体，选择一个不是首也不是尾的基因，将所选择的两个个体对应的基因进行交叉，并将新产生的个体添加到种群中去，返回新的种群。代码如下：

static List<Individual> Crossover(List<Individual> NewSelPopu){ //复制集合 List<Individual> CroPopu = new ArrayList<>(); for (int i = 0; i < 5; i++) { Individual ind = new Individual(); System.arraycopy(NewSelPopu.get(i).Path, 0, ind.Path, 0, 6); ind.length = NewSelPopu.get(i).length; CroPopu.add(ind); } //随机选择两个不同的个体 int i = rand.nextInt(5); int j = rand.nextInt(5); while(i == j){ j = rand.nextInt(5); } //随机选择一个不是首尾的基因进行交叉 int k = rand.nextInt(4) + 1; int l = CroPopu.get(i).Path[k]; CroPopu.get(i).Path[k] = CroPopu.get(j).Path[k]; CroPopu.get(j).Path[k] = l; //更新length并添加到集合中 Fitness(CroPopu.get(i)); Fitness(CroPopu.get(j)); NewSelPopu.add(CroPopu.get(i)); NewSelPopu.add(CroPopu.get(j)); //输出交叉产生的个体 System.out.println("交叉产生的个体为：" + Arrays.toString(CroPopu.get(i).Path) + "和" + Arrays.toString(CroPopu.get(j).Path)); //输出交叉后的个体适应度 System.out.print("交叉后的个体的长度："); for(Individual a : NewSelPopu){ System.out.print(a.length +" "); } System.out.println("n"+"交叉完成！"); return NewSelPopu; }

8、变异算子

输入：包含7个个体的种群。

　　输出：包含10个个体的种群。

　　随机选择一个个体，将这个个体的随机一个不为首或尾的基因进行变异，随机产生一个[0,5]中的数值代替该基因处的数值，将变异后产生的新的个体添加到种群中。重复以上步骤三次，共计产生三个新的个体。这里需要注意的是，由于每次选择要变异的个体都是随机的，可能存在两次甚至三次选择同一个个体进行变异的情况，这也符合自然界中生物遗传的思想。代码如下：

static List<Individual> Variation(List<Individual> NewCroPopu){ //复制集合 List<Individual> VarPopu = new ArrayList<>(); for (int i = 0; i < 7; i++) { Individual ind = new Individual(); System.arraycopy(NewCroPopu.get(i).Path, 0, ind.Path, 0, 6); ind.length = NewCroPopu.get(i).length; VarPopu.add(ind); } //变异三次 for (int i = 0; i < 3; i++) { //随机选择一个个体的一个基因进行变异 int j = rand.nextInt(7); VarPopu.get(j).Path[(rand.nextInt(4) + 1)] = rand.nextInt(5); //更新length并添加到集合中 Fitness(VarPopu.get(j)); NewCroPopu.add(VarPopu.get(j)); //输出交叉产生的个体 System.out.println("第"+ (i+1) +"次变异产生的个体为：" + Arrays.toString(VarPopu.get(i).Path)); } //输出变异后的个体适应度 System.out.print("变异后的个体的长度："); for(Individual a : NewCroPopu){ System.out.print(a.length +" "); } System.out.println("n"+"变异完成！"); return NewCroPopu; }

9、总结

本文解决的问题复杂度较低，适合代码或者遗传算法的初学者尝试解决。另外在解决该问题时，本文所采用的编码方式较为简单，虽可以很好的解决此类简单问题，但在求解更复杂的问题时可能会存在计算结果为不可行解的情况，因此在采用遗传算法解决更复杂的问题时，非常有必要对编码方式进行进一步的加工，使其更适合问题特性且计算结果更优。完整的代码如下：

import java.util.*; public class GeneticAlgorithm { static int[][] matrix = new int[6][6]; final static int M = 10000; static Random rand = new Random(); public static void main(String[] args) { //邻接矩阵 matrix[0] = new int[]{0, 6, 3, M, M, M};/*1*/ matrix[1] = new int[]{6, 0, 2, 5, M, M};/*2*/ matrix[2] = new int[]{3, 2, 0, 3, 4, M};/*3*/ matrix[3] = new int[]{M, 5, 3, 0, 2, 3};/*4*/ matrix[4] = new int[]{M, M, 4, 2, 0, 5};/*5*/ matrix[5] = new int[]{M, M, M, 3, 5, 0};/*6*/ //定义初始种群 Math.random(); List<Individual> Population = new ArrayList<>(); for (int i = 0; i < 10; i++) { //随机生成十个个体添加到初始种群列表 Individual Popu = new Individual(); Popu.Path[0] = 0; Popu.Path[1] = rand.nextInt(5); Popu.Path[2] = rand.nextInt(5); Popu.Path[3] = rand.nextInt(5); Popu.Path[4] = rand.nextInt(5); Popu.Path[5] = 5; Popu.length = M; Population.add(Popu); } //输出初始种群 for (int i = 0; i < 10; i++) { System.out.println("初始种群中第" + (i+1) + "个个体为："); for (int j = 0; j < 6; j++) { System.out.print(Population.get(i).Path[j]); } //更新length for (int j = 0; j < 10; j++) { Fitness(Population.get(j)); } System.out.println("n" +"适应度为：" +Population.get(i).length); System.out.println(); } for(int i = 0; i<2000; i++){ System.out.println("第"+(i+1)+"次迭代开始！"); //初始种群中选择出5个较优的个体 List<Individual> NewSelPopu = Selection(Population); //交叉 List<Individual> NewCroPopu = Crossover(NewSelPopu); //变异 Population = Variation(NewCroPopu); System.out.println("第"+ (i+1) + "次迭代完成！"); } //输出迭代后的种群 System.out.print("2000次迭代后集合中个体的长度："); for(Individual a : Population){ System.out.print(a.length +" "); } //对集合中的个体排序 Collections.sort(Population); //输出排序后的集合中个体的长度 System.out.print("n" +"2000次迭代后所有个体的最短路径长度为:" + Population.get(9).length); System.out.println("n"+"最短路径为：" + Arrays.toString(Population.get(9).Path)); } //选择函数,删除种群中较大的5个个体，返回两个所选的适应度最好的个体 //输入：10个个体的种群 //输出：5个个体的种群 static List<Individual> Selection(List<Individual> Population){ System.out.print("排序前集合中个体的长度："); for(Individual a : Population){ System.out.print(a.length +" "); } //对集合中的个体排序 Collections.sort(Population); //输出排序后的集合中个体的长度 System.out.print("n" +"排序后集合中个体的长度:"); for(Individual a : Population){ System.out.print(a.length +" "); } //使用迭代器删除个体 Iterator<Individual> iterator = Population.iterator(); while(iterator.hasNext() && Population.size()>5){ Individual next = iterator.next(); if(next != null) iterator.remove(); } //输出删除后的个体的长度 System.out.print("n" + "选择后的个体的长度："); for(Individual a : Population){ System.out.print(a.length +" "); } System.out.println("n" + "选择完成!"); return Population; } //交叉产生两个新的个体 //输入：5个个体的种群 //输出：7个个体的种群 static List<Individual> Crossover(List<Individual> NewSelPopu){ //复制集合 List<Individual> CroPopu = new ArrayList<>(); for (int i = 0; i < 5; i++) { Individual ind = new Individual(); System.arraycopy(NewSelPopu.get(i).Path, 0, ind.Path, 0, 6); ind.length = NewSelPopu.get(i).length; CroPopu.add(ind); } //随机选择两个不同的个体 int i = rand.nextInt(5); int j = rand.nextInt(5); while(i == j){ j = rand.nextInt(5); } //随机选择一个不是首尾的基因进行交叉 int k = rand.nextInt(4) + 1; int l = CroPopu.get(i).Path[k]; CroPopu.get(i).Path[k] = CroPopu.get(j).Path[k]; CroPopu.get(j).Path[k] = l; //更新length并添加到集合中 Fitness(CroPopu.get(i)); Fitness(CroPopu.get(j)); NewSelPopu.add(CroPopu.get(i)); NewSelPopu.add(CroPopu.get(j)); //输出交叉产生的个体 System.out.println("交叉产生的个体为：" + Arrays.toString(CroPopu.get(i).Path) + "和" + Arrays.toString(CroPopu.get(j).Path)); //输出交叉后的个体适应度 System.out.print("交叉后的个体的长度："); for(Individual a : NewSelPopu){ System.out.print(a.length +" "); } System.out.println("n"+"交叉完成！"); return NewSelPopu; } //变异两个个体 //输入：7个个体的种群 //输出：10个个体的种群 static List<Individual> Variation(List<Individual> NewCroPopu){ //复制集合 List<Individual> VarPopu = new ArrayList<>(); for (int i = 0; i < 7; i++) { Individual ind = new Individual(); System.arraycopy(NewCroPopu.get(i).Path, 0, ind.Path, 0, 6); ind.length = NewCroPopu.get(i).length; VarPopu.add(ind); } //变异三次 for (int i = 0; i < 3; i++) { //随机选择一个个体的一个基因进行变异 int j = rand.nextInt(7); VarPopu.get(j).Path[(rand.nextInt(4) + 1)] = rand.nextInt(5); //更新length并添加到集合中 Fitness(VarPopu.get(j)); NewCroPopu.add(VarPopu.get(j)); //输出交叉产生的个体 System.out.println("第"+ (i+1) +"次变异产生的个体为：" + Arrays.toString(VarPopu.get(i).Path)); } //输出变异后的个体适应度 System.out.print("变异后的个体的长度："); for(Individual a : NewCroPopu){ System.out.print(a.length +" "); } System.out.println("n"+"变异完成！"); return NewCroPopu; } //更新适应度 static void Fitness(Individual in){ //计算路径长度 in.length = matrix[in.Path[0]][in.Path[1]] + matrix[in.Path[1]][in.Path[2]] + matrix[in.Path[2]][in.Path[3]] + matrix[in.Path[3]][in.Path[4]] + matrix[in.Path[4]][in.Path[5]]; } }

public class Individual implements Comparable<Individual>{ int[] Path = new int[6]; //存储路径 int length; //表示适应度 public int[] getPath() { return Path; } public void setPath(int[] path) { Path = path; } public int getLength() { return length; } public void setLength(int length) { this.length = length; } public int compareTo(Individual o) { if(this.getLength() > o.getLength()) { return -1; } else if(this.getLength()<o.getLength()) { return 1; } else { return 0; } } }

运行结果如下：

第2000次迭代完成！2000次迭代后集合中个体的长度：9 9 9 9 9 9 9 9 9 100032000次迭代后所有个体的最短路径长度为:9最短路径为：[0, 2, 2, 2, 3, 5]

 

　　

由于问题比较简单，一般迭代100次左右就已经求得最优解，为保证结果的最优性，本文对进行了2000次迭代，迭代结果与上一篇文章中通过Dijkstra方法求得的最优解一致。

　　在进行代码的编写时也遇到了一些比较经典的问题，总结如下：

　　1.初始版本的选择算子中，先将每个个体的适应度属性存储到一个新建的数组中进行排序，此方法舍近求远，因此对其进行改进，采用Collections.sort（）对种群中的个体进行排序。

　　2.初始版本的选择算子中，采用for循环和while循环的方式删除适应度大的个体，此种方式导致程序运行时出现死循环且不能很好的实现删除5个适应度大的个体的目的，for循环中每次删除个体后种群数量发生变化，程序运行会出现异常，因此对其进行改进，采用迭代器对个体进行删除。

　　3.在交叉和变异算子中需要对集合进行复制，由于集合名代表的是集合存储的地址，直接赋值仍然会修改原集合中的数据，因此在对集合进行深层次的复制，新建个体并将原集合中的个体属性值分别赋给新个体后添加到复制集合中去。

　　到此这篇关于Java利用遗传算法求解最短路径问题的文章就介绍到这了,更多相关Java求最短路径内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。