干货 | 遗传算法(Genetic Algorithm) Java 详细代码及注释

代码说明

遗传算法解决TSP旅行商问题

算法分为4个类:

GeneticAlgorithm

SpeciesIndividual

SpeciesPopulation

TSPData

数据规模: 10 cities, 20 cities and 31 cities.

类说明:

GeneticAlgorithm: 遗传算法的主体部分,包括选择、交叉、变异

SpeciesIndividual: 物种个体类

SpeciesPopulation: 物种种群类

TSPData: TSP数据类

MainRun: 主函数运行类

运行平台:

eclipse + windows10

详细代码

MainRun.java

主函数运行类,也就是程序入口。在这里创建算法类,创建种群,并开始运行我们的算法。得出结果以后,打印出来。

package GeneticTSP;


/**
 * 主函数运行类
 */

public class MainRun {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //创建遗传算法驱动对象
        GeneticAlgorithm GA=new GeneticAlgorithm();

        //创建初始种群
        SpeciesPopulation speciesPopulation = new SpeciesPopulation();

        //开始遗传算法(选择算子、交叉算子、变异算子)
        SpeciesIndividual bestRate=GA.run(speciesPopulation);

        //打印路径与最短距离
        bestRate.printRate();

    }

}

TSPData.java

测试数据类,在这里做城市坐标数据等的输入。我直接写死在程序里了,有需要的朋友直接改动一下做一个IO就差不多了。disMap城市距离矩阵,记录各个城市间的距离。比如disMap[i][j]就是城市i城市j之间的距离。

package GeneticTSP;

/**
 * TSP数据类
 * 包含:
 *         disMap 各个城市间距离矩阵
 */

public class TSPData {

    static int CITY_NUM; //城市数
    static final int SPECIES_NUM=200; //种群数
    static final int DEVELOP_NUM=1000; //进化代数
    static final float pcl=0.6f,pch=0.95f;//交叉概率
    static final float pm=0.4f;//变异概率
    static final float[][] disMap; //地图数据
    static
    {
//        int[][] cityPosition={
//                {0,0},{12,32},{5,25},{8,45},{33,17},
//                {25,7},{15,15},{15,25},{25,15},{41,12}};//10个城市(最优解:147)
//        int[][] cityPosition={
//                {60,200},{180,200},{80,180},{140,180},
//                {20,160},{100,160},{200,160},{140,140},
//                {40,120},{100,120},{180,100},{60,80},
//                {120,80},{180,60},{20,40},{100,40},
//                {200,40},{20,20},{60,20},{160,20}};//20个城市(最优解:870)
//        
        //城市坐标集合
        int[][] cityPosition={
                {1304,        2312},{3639,        1315},         
                {4177,        2244},{3712,        1399},            
                {3488,        1535},{3326,        1556},         
                {3238,        1229},{4196,        1004},         
                {4312,         790},{4386,         570},
                {3007,        1970},{2562,        1756},
                {2788,        1491},{2381,        1676},
                {1332,         695},{3715,        1678},
                {3918,        2179},{4061,        2370},
                {3780,        2212},{3676,        2578},
                {4029,        2838},{4263,        2931},
                {3429,        1908},{3507,        2367},
                {3394,        2643},{3439,        3201},
                {2935,        3240},{3140,        3550},
                {2545,        2357},{2778,        2826},
                {2370,        2975}};//31个城市(最优解:14700)

        //路径集合
        CITY_NUM=cityPosition.length;
        disMap=new float[CITY_NUM][CITY_NUM];
        for(int i=0;i<CITY_NUM;i++)
        {
            for(int j=i;j<CITY_NUM;j++)
            {
                float dis=(float)Math.sqrt(Math.pow((cityPosition[i][0] - cityPosition[j][0]),2) + Math.pow((cityPosition[i][1] - cityPosition[j][1]),2));

                disMap[i][j]=dis;
                disMap[j][i]=disMap[i][j];
            }
        }   
    }

}

SpeciesIndividual.java

物种个体类,每一个个体的染色体对应着一个解决方案。下面做几点说明:

基因:这里要解决的是TSP问题,因此我们直接采用城市序列作为基因的编码。染色体由随机排列的基因组成。

物种适应度:我们说了,物种适应度是评判物种个体的好坏的一个标准。那么,对于TSP问题,解决方案的总距离越小当然就越好了。因此我们直接用了总距离的倒数作为物种适应度。那么,总距离越小,物种适应度相应就越大了。

最后再加一个打印解决方案的方法,就是把城市排列输出来。至于贪婪法生成基因,大家了解一下,这里不做介绍。

package GeneticTSP;

import java.util.Random;

/**
 * 个体类
 * 包含:
 *         1.createByRandomGenes 初始物种基因(随机) 基因直接用城市序列编码
 *         2.calFitness 计算物种适应度
 *         3.printRate 打印路径
 */

public class SpeciesIndividual {

    String[] genes;//基因序列
    float distance;//路程
    float fitness;//适应度
    SpeciesIndividual next;
    float rate;

    SpeciesIndividual()
    {
        //初始化
        this.genes=new String[TSPData.CITY_NUM];
        this.fitness=0.0f;
        this.distance=0.0f;
        this.next=null;
        rate=0.0f;
    }

    //初始物种基因(随机)
    void createByRandomGenes()
    {
        //初始化基因为1-CITY_NUM序列
        for(int i = 0;i < genes.length;i++)
        {
            genes[i]=Integer.toString(i+1);
        }

        //获取随机种子
        Random rand=new Random();

        for(int j=0;j<genes.length;j++)
        {
            int num= j + rand.nextInt(genes.length-j);

            //交换
            String tmp;
            tmp=genes[num];
            genes[num]=genes[j];
            genes[j]=tmp;
        }
    }

    //初始物种基因(贪婪)
    void createByGreedyGenes()
    {
        Random rand=new Random();
        int i= rand.nextInt(TSPData.CITY_NUM); //随机产生一个城市作为起点
        genes[0]=Integer.toString(i+1);
        int j;//终点
        int cityNum=0;
        do
        {
            cityNum++;

            //选出单源最短城市
            float minDis=Integer.MAX_VALUE;
            int minCity=0;
            for(j=0;j<TSPData.CITY_NUM;j++)
            {
                if(j != i)
                {
                    //判是否和已有重复
                    boolean repeat=false;
                    for(int n=0;n<cityNum;n++)
                    {
                        if(Integer.parseInt(genes[n]) == j+1)
                        {
                            repeat=true;//重了
                            break;
                        }
                    }
                    if(repeat == false)//没重
                    {
                        //判长度
                        if(TSPData.disMap[i][j] < minDis)
                        {
                            minDis=TSPData.disMap[i][j];
                            minCity=j;
                        }
                    }
                }
            }

            //加入到染色体
            genes[cityNum]=Integer.toString(minCity+1);
            i=minCity;
        }while(cityNum < TSPData.CITY_NUM-1);
    }

    //计算物种适应度
    void calFitness()
    {
        float totalDis=0.0f;
        for(int i = 0;i < TSPData.CITY_NUM;i++)
        {
            int curCity=Integer.parseInt(this.genes[i])-1;
            int nextCity=Integer.parseInt(this.genes[(i+1) % TSPData.CITY_NUM])-1;

            totalDis += TSPData.disMap[curCity][nextCity];
        }

        this.distance=totalDis;
        this.fitness=1.0f/totalDis;
    }

    //深拷贝
    public SpeciesIndividual clone()
    {   
        SpeciesIndividual species=new SpeciesIndividual();

        //复制值
        for(int i=0;i<this.genes.length;i++)
            species.genes[i]=this.genes[i];
        species.distance=this.distance;
        species.fitness=this.fitness;

        return species; 
    }

    //打印路径
    void printRate()
    {
        System.out.print("最短路线:");
        for(int i=0;i<genes.length;i++)
            System.out.print(genes[i]+"->");
        System.out.print(genes[0]+"\n");
        System.out.print("最短长度:" + distance);
    }

}

SpeciesPopulation.java

种群类,总群由物种组成。该类功能主要是把物种聚集起来形成总群的。我们姑且就当做一个物种只有一个个体。

package GeneticTSP;

/**
 * 种群类
 * 包含:
 *         1.add 添加物种
 *         2.traverse 遍历
 */

public class SpeciesPopulation {

    SpeciesIndividual head;//头结点
    int speciesNum;//物种数量

    SpeciesPopulation()
    {
        head=new SpeciesIndividual();
        speciesNum=TSPData.SPECIES_NUM;
    }

    //添加物种
    void add(SpeciesIndividual species)
    {
        SpeciesIndividual point=head;//游标
        while(point.next != null)//寻找表尾结点
            point=point.next;
        point.next=species;
    }

    //遍历
    void traverse()
    {
        SpeciesIndividual point=head.next;//游标
        while(point != null)//寻找表尾结点
        {
            for(int i=0;i<TSPData.CITY_NUM;i++)
                System.out.print(point.genes[i]+" ");
            System.out.println(point.distance);
            point=point.next;
        }
        System.out.println("_______________________");
    }

}

GeneticAlgorithm.java

重头戏来了。下面重点介绍GA算法类中的几个方法:

createBeginningSpecies

创建种群,100%随机创建或者40%贪婪创建。40%贪婪创建就是40的物种采用贪婪算法生成基因。物种数由TSPData类中的物种数指定。

calRate

计算每一物种被选中的概率。物种个体中的rate变量记录了该概率。

select

轮盘制选择物种进行染色体交叉。这里的策略讲讲,我们的目标是选出优秀个体染色体交叉生成新的种群。然后再提一句,该方法只是选择个体而已,还没进行交叉操作。

1) 我们先找出最大适应度的个体。然后复制该个体到新种群去,复制数量占原来种群的1/4。

2) 然后新种群的3/4我们采用轮盘制选择,选择概率随机产生,毕竟大自然选择也是看天意的……然后每次选择那些,选中的概率(前面算出来了)大于或等于随机概率的个体,塞进新种群。注意边界处理。

crossover

交叉操作,以一定的概率区间进行。详细说明一下步骤:

1) 先随机找出两个个体(个体point和个体point.next)。

2) 在一定的概率区间。对个体point和个体point.next进行如下操作:

循环 i to city_num(i随机产生)

找出point.genes中与point.next.genes[i]相等的位置fir

找出point.next.genes中与point.genes[i]相等的位置sec

然后执行如下交换操作:

直到结束循环

mutate

变异操作。每一种物种都有变异的可能,我们以一定概率进行。在这个TSP问题中,我们采用的变异操作其实跟迭代搜索那个two opt有点类似。在基因序列中,随机产生i~j的区间,然后将区间反转,形成新的染色体。很easy吧……

package GeneticTSP;

import java.util.Random;

/**
 * 遗传算法类
 * 包含:
 *         1.run 开始跑算法
 *         2.createBeginningSpecies 创建种群
 *         3.calRate 计算每一种物种被选中的概率
 *      4.select  轮盘策略 选择适应度高的物种
 *      5.crossover 染色体交叉
 *      6.mutate 染色体变异
 *      7.getBest 获得适应度最大的物种
 */

public class GeneticAlgorithm {

        //开始遗传
        SpeciesIndividual run(SpeciesPopulation list)
        {
            //创建初始种群
            createBeginningSpecies(list);

            for(int i=1;i<=TSPData.DEVELOP_NUM;i++)
            {
                //选择
                select(list);

                //交叉
                crossover(list);

                //变异
                mutate(list);
            }   

            return getBest(list);
        }

        //创建初始种群
        void createBeginningSpecies(SpeciesPopulation list)
        {
            //100%随机
            int randomNum=(int)(TSPData.SPECIES_NUM);
            for(int i=1;i<=randomNum;i++)
            {
                SpeciesIndividual species=new SpeciesIndividual();//创建结点
                species.createByRandomGenes();//初始种群基因

                list.add(species);//添加物种
            }

//            //40%贪婪
//            int greedyNum=TSPData.SPECIES_NUM-randomNum;
//            for(int i=1;i<=greedyNum;i++)
//            {
//                SpeciesIndividual species=new SpeciesIndividual();//创建结点
//                species.createByGreedyGenes();//初始种群基因
    //
//                this.add(species);//添加物种
//            }
        }

        //计算每一物种被选中的概率
        void calRate(SpeciesPopulation list)
        {
            //计算总适应度
            float totalFitness=0.0f;
            list.speciesNum=0;
            SpeciesIndividual point=list.head.next;//游标
            while(point != null)//寻找表尾结点
            {
                point.calFitness();//计算适应度

                totalFitness += point.fitness;
                list.speciesNum++;

                point=point.next;
            }

            //计算选中概率
            point=list.head.next;//游标
            while(point != null)//寻找表尾结点
            {
                point.rate=point.fitness/totalFitness;
                point=point.next;
            }
        }

        //选择优秀物种(轮盘赌)
        void select(SpeciesPopulation list)
        {           
            //计算适应度
            calRate(list);

            //找出最大适应度物种
            float talentDis=Float.MAX_VALUE;
            SpeciesIndividual talentSpecies=null;
            SpeciesIndividual point=list.head.next;//游标

            while(point!=null)
            {
                if(talentDis > point.distance)
                {
                    talentDis=point.distance;
                    talentSpecies=point;
                }
                point=point.next;
            }

            //将最大适应度物种复制talentNum个
            SpeciesPopulation newSpeciesPopulation=new SpeciesPopulation();
            int talentNum=(int)(list.speciesNum/4);
            for(int i=1;i<=talentNum;i++)
            {
                //复制物种至新表
                SpeciesIndividual newSpecies=talentSpecies.clone();
                newSpeciesPopulation.add(newSpecies);
            }

            //轮盘赌list.speciesNum-talentNum次
            int roundNum=list.speciesNum-talentNum;
            for(int i=1;i<=roundNum;i++)
            {
                //产生0-1的概率
                float rate=(float)Math.random();

                SpeciesIndividual oldPoint=list.head.next;//游标
                while(oldPoint != null && oldPoint != talentSpecies)//寻找表尾结点
                {
                    if(rate <= oldPoint.rate)
                    {
                        SpeciesIndividual newSpecies=oldPoint.clone();
                        newSpeciesPopulation.add(newSpecies);

                        break;
                    }
                    else
                    {
                        rate=rate-oldPoint.rate;
                    }
                    oldPoint=oldPoint.next;
                }
                if(oldPoint == null || oldPoint == talentSpecies)
                {
                    //复制最后一个
                    point=list.head;//游标
                    while(point.next != null)//寻找表尾结点
                        point=point.next;
                    SpeciesIndividual newSpecies=point.clone();
                    newSpeciesPopulation.add(newSpecies);
                }

            }
            list.head=newSpeciesPopulation.head;
        }

        //交叉操作
        void crossover(SpeciesPopulation list)
        {
            //以概率pcl~pch进行
            float rate=(float)Math.random();
            if(rate > TSPData.pcl && rate < TSPData.pch)
            {           
                SpeciesIndividual point=list.head.next;//游标
                Random rand=new Random();
                int find=rand.nextInt(list.speciesNum);
                while(point != null && find != 0)//寻找表尾结点
                {
                    point=point.next;
                    find--;
                }

                if(point.next != null)
                {
                    int begin=rand.nextInt(TSPData.CITY_NUM);

                    //取point和point.next进行交叉,形成新的两个染色体
                    for(int i=begin;i<TSPData.CITY_NUM;i++)
                    {
                        //找出point.genes中与point.next.genes[i]相等的位置fir
                        //找出point.next.genes中与point.genes[i]相等的位置sec
                        int fir,sec;
                        for(fir=0;!point.genes[fir].equals(point.next.genes[i]);fir++);
                        for(sec=0;!point.next.genes[sec].equals(point.genes[i]);sec++);
                        //两个基因互换
                        String tmp;
                        tmp=point.genes[i];
                        point.genes[i]=point.next.genes[i];
                        point.next.genes[i]=tmp;

                        //消去互换后重复的那个基因
                        point.genes[fir]=point.next.genes[i];
                        point.next.genes[sec]=point.genes[i];

                    }
                }
            }
        }

        //变异操作
        void mutate(SpeciesPopulation list)
        {   
            //每一物种均有变异的机会,以概率pm进行
            SpeciesIndividual point=list.head.next;
            while(point != null)
            {
                float rate=(float)Math.random();
                if(rate < TSPData.pm)
                {
                    //寻找逆转左右端点
                    Random rand=new Random();
                    int left=rand.nextInt(TSPData.CITY_NUM);
                    int right=rand.nextInt(TSPData.CITY_NUM);
                    if(left > right)
                    {
                        int tmp;
                        tmp=left;
                        left=right;
                        right=tmp;
                    }

                    //逆转left-right下标元素
                    while(left < right)
                    {
                        String tmp;
                        tmp=point.genes[left];
                        point.genes[left]=point.genes[right];
                        point.genes[right]=tmp;

                        left++;
                        right--;
                    }
                }
                point=point.next;
            }
        }

        //获得适应度最大的物种
        SpeciesIndividual getBest(SpeciesPopulation list)
        {
            float distance=Float.MAX_VALUE;
            SpeciesIndividual bestSpecies=null;
            SpeciesIndividual point=list.head.next;//游标
            while(point != null)//寻找表尾结点
            {
                if(distance > point.distance)
                {
                    bestSpecies=point;
                    distance=point.distance;
                }

                point=point.next;
            }

            return bestSpecies;
        }

}

以上就是遗传算法的java代码。


运行结果:

10个城市(最优解:147)

20个城市(最优解:870)

31个城市(最优解:14700)

最后在多说一句,这代码跑不出最优解也正常。启发式算法求近似解还是得靠人品的胸弟。跑不出最优解那只能说明……小编太帅吓到编译器了而已。嗯,一定是这样的。

原文发布于微信公众号 - 数据魔术师(data-magician)

原文发表时间:2018-05-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

海量文本用 Simhash, 2小时变4秒! | 文本分析:大规模文本处理(2)

这是一个相似匹配的问题(文本相似匹配基础→ 词频与余弦相似度)。但是,亿级数据库,用传统的相似度计算方法太慢了,我们需要一个文本查询方法,可以快速的把一段文本的...

792
来自专栏人人都是极客

GPU的工作原理

在GPU出现以前,显卡和CPU的关系有点像“主仆”,简单地说这时的显卡就是画笔,根据各种有CPU发出的指令和数据进行着色,材质的填充、渲染、输出等。 较早的娱乐...

3175
来自专栏大学生计算机视觉学习DeepLearning

手指静脉细化算法过程原理解析 以及python实现细化算法

1284
来自专栏大数据文摘

改变计算技术的 9 个伟大算法

1903
来自专栏人工智能

深入机器学习系列10-ALS

交换最小二乘 ? 1 什么是ALSALS是交替最小二乘(alternating least squares)的简称。在机器学习中,ALS特指使用交替最小二乘求解...

2246
来自专栏智能算法

数据异常到底该如何检测?(一)

小编在正式进入工作之后,面对的第一个需要去解决的问题:在网络安全监测中,如何发现异常数据?如异常用户登录,异常操作等。对于网络上的问题我确实是第一次接触这样类型...

3317
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

633
来自专栏数据结构与算法

cf932E. Team Work(第二类斯特灵数 组合数)

$$m^n = \sum_{i = 0}^m C_{n}^i S(n, i) i!$$

864
来自专栏数据魔术师

运筹学教学|十分钟快速掌握单纯形法(附C++代码及算例)

国庆节就要到了! 不如今儿咱就来讨论一下去哪玩耍吧! 南京?丽江?西安?…… 众人(汗):一个月前就没票了。。。 哦……那么,就只能……学习了…… 好巧不巧,运...

4226
来自专栏人工智能头条

张雨石:Adam - 大规模分布式机器学习框架

2527

扫码关注云+社区