Java利用遗传算法求解最短路径问题

原文

遗传算法（Genetic Algorithm，GA）最早是由美国的John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

1、问题描述

图1所示为一个最短路径问题，每条边代表一条可以通行的弧，边上的数值表示这条弧的长度，多条弧相互连接形成路径，目标是寻找一条从节点0出发到节点5的最短路径。

2、编码

从表现型到基因型的映射称为编码。图1中每条路径的每个节点对应一个基因，通过对节点的有序组合可以将每条路径映射为一个向量。每个向量长度为6，起始和结束位置的数值分别为0和5，代表从节点0出发，到节点5终止，图1中节点间边的长度代表节点间的距离，若两节点间无边相连，则这两个节点间的距离为一个极大的数M。由于向量长度固定为6，而解中可能并不包含所有的节点，个体中可能会存在多个相邻且重复出现的节点，因此设置节点到其本身的距离为0。

3、个体类

每个个体包含路径Path和适应度length（即路径长度）两个属性，每个个体路径属性中的起点为0，结束点为5，其余位置数值随机生成（0-5范围内的整数），向量长度固定为6。个体类中定义的compareTo方法是为了用于在选择算子中采用迭代器进行个体的删除。

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;
        }
    }
 
}

4、遗传算法解决最短路径问题主方法

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

    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<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 10003 
2000次迭代后所有个体的最短路径长度为:9
最短路径为：[0, 2, 2, 2, 3, 5]

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

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

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

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

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

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

Java利用遗传算法求解最短路径问题的更多相关文章

  1. Java利用POI实现导入导出Excel表格

    这篇文章主要为大家详细介绍了Java利用POI实现导入导出Excel表格，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

  2. Java 阻塞队列BlockingQueue详解

    本文详细介绍了BlockingQueue家庭中的所有成员，包括他们各自的功能以及常见使用场景,通过实例代码介绍了Java 阻塞队列BlockingQueue的相关知识，需要的朋友可以参考下

  3. Java Bean 作用域及它的几种类型介绍

    这篇文章主要介绍了Java Bean作用域及它的几种类型介绍，Spring框架作为一个管理Bean的IoC容器，那么Bean自然是Spring中的重要资源了，那Bean的作用域又是什么，接下来我们一起进入文章详细学习吧

  4. Java实现世界上最快的排序算法Timsort的示例代码

    Timsort 是一个混合、稳定的排序算法，简单来说就是归并排序和二分插入排序算法的混合体，号称世界上最好的排序算法。本文将详解Timsort算法是定义与实现，需要的可以参考一下

  5. Java日期工具类的封装详解

    在日常的开发中，我们难免会对日期格式化，对日期进行计算，对日期进行校验，为了避免重复写这些琐碎的逻辑，我这里封装了一个日期工具类，方便以后使用，直接复制代码到项目中即可使用，需要的可以参考一下

  6. Java设计模式之模板方法模式Template Method Pattern详解

    在我们实际开发中，如果一个方法极其复杂时，如果我们将所有的逻辑写在一个方法中，那维护起来就很困难，要替换某些步骤时都要重新写，这样代码的扩展性就很差，当遇到这种情况就要考虑今天的主角——模板方法模式

  7. Java 中 Class Path 和 Package的使用详解

    这篇文章主要介绍了Java 中 Class Path和Package的使用详解，文章围绕主题展开详细的内容介绍，具有一定的参考价值，需要的朋友可以参考一下

  8. java SpringBoot 分布式事务的解决方案(JTA+Atomic+多数据源)

    这篇文章主要介绍了java SpringBoot 分布式事务的解决方案(JTA+Atomic+多数据源),文章围绕主题展开详细的内容介绍，具有一定的参考价值，感兴趣的小伙伴可以参考一下

  9. Java一维数组和二维数组元素默认初始化值的判断方式

    这篇文章主要介绍了Java一维数组和二维数组元素默认初始化值的判断方式，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教

  10. java实现emqx设备上下线监听详解

    这篇文章主要为大家介绍了java实现emqx设备上下线监听详解，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

随机推荐

  1. 基于EJB技术的商务预订系统的开发

    用EJB结构开发的应用程序是可伸缩的、事务型的、多用户安全的。总的来说，EJB是一个组件事务监控的标准服务器端的组件模型。基于EJB技术的系统结构模型EJB结构是一个服务端组件结构，是一个层次性结构，其结构模型如图1所示。图2：商务预订系统的构架EntityBean是为了现实世界的对象建造的模型，这些对象通常是数据库的一些持久记录。

  2. Java利用POI实现导入导出Excel表格

    这篇文章主要为大家详细介绍了Java利用POI实现导入导出Excel表格，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

  3. Mybatis分页插件PageHelper手写实现示例

    这篇文章主要为大家介绍了Mybatis分页插件PageHelper手写实现示例，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

  4. (jsp/html)网页上嵌入播放器(常用播放器代码整理)

    网页上嵌入播放器，只要在HTML上添加以上代码就OK了，下面整理了一些常用的播放器代码，总有一款适合你，感兴趣的朋友可以参考下哈，希望对你有所帮助

  5. Java 阻塞队列BlockingQueue详解

    本文详细介绍了BlockingQueue家庭中的所有成员，包括他们各自的功能以及常见使用场景,通过实例代码介绍了Java 阻塞队列BlockingQueue的相关知识，需要的朋友可以参考下

  6. Java异常Exception详细讲解

    异常就是不正常，比如当我们身体出现了异常我们会根据身体情况选择喝开水、吃药、看病、等 异常处理方法。 java异常处理机制是我们java语言使用异常处理机制为程序提供了错误处理的能力，程序出现的错误，程序可以安全的退出，以保证程序正常的运行等

  7. Java Bean 作用域及它的几种类型介绍

    这篇文章主要介绍了Java Bean作用域及它的几种类型介绍，Spring框架作为一个管理Bean的IoC容器，那么Bean自然是Spring中的重要资源了，那Bean的作用域又是什么，接下来我们一起进入文章详细学习吧

  8. 面试突击之跨域问题的解决方案详解

    跨域问题本质是浏览器的一种保护机制，它的初衷是为了保证用户的安全，防止恶意网站窃取数据。那怎么解决这个问题呢？接下来我们一起来看

  9. Mybatis-Plus接口BaseMapper与Services使用详解

    这篇文章主要为大家介绍了Mybatis-Plus接口BaseMapper与Services使用详解，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

  10. mybatis-plus雪花算法增强idworker的实现

    今天聊聊在mybatis-plus中引入分布式ID生成框架idworker，进一步增强实现生成分布式唯一ID,具有一定的参考价值，感兴趣的小伙伴们可以参考一下

返回
顶部