栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【运筹优化】GA遗传算法求解TSP问题(Java实现)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【运筹优化】GA遗传算法求解TSP问题(Java实现)

文章目录
  • 代码
    • Genome基因类
    • GeneticAlgorithm_TSP遗传算法类
  • 运行结果


代码 Genome基因类
import lombok.Data;
import lombok.NoArgsConstructor;


@Data
@NoArgsConstructor
public class Genome {
    // 距离矩阵
    public static double[][] dist;
    // 基因序列
    private int[] genomeArray;
    // 适应度函数值
    private double fitness;
    // 序列对应的路径长度
    private double pathLen;

    // 构造函数
    public Genome(int[] genomeArray) {
        this.genomeArray = genomeArray.clone();
        updateFitnessAndPathLen();
    }

    // 获取适应值和路径长度
    public void updateFitnessAndPathLen(){
        pathLen = Genome.getPathLen(genomeArray);
        fitness = 10000d/pathLen;
    }

    // 求路程长度
    public static double getPathLen(int[] path) {
        double pathLen = 0.0;
        for (int i = 1; i < path.length; i++) {
            // 起点到终点途径路程累加
            pathLen += dist[path[i - 1]][path[i]];
        }
        // 然后再加上返回起点的路程
        pathLen += dist[path[0]][path[path.length - 1]];
        return pathLen;
    }

}
GeneticAlgorithm_TSP遗传算法类
import java.io.IOException;
import java.io.Serializable;
import java.util.*;


public class GeneticAlgorithm_TSP implements Serializable {
    // 城市坐标集合 <[x,y]>
    List locationList;
    // 距离矩阵
    double[][] dist;
    // 城市数量
    int cityNum;
    // 放置所有的种群基因信息
    private List population = new ArrayList<>();
    // 新一代的种群基因信息
    private List newPopulation = new ArrayList<>();
    // 种群数量信息
    private int popSize = 100;
    // 种群总的适应度数值
    private double totalFitness = 0;
    // 最好的适应度的对应的染色体(基因序列、路径序列)
    private Genome bestGenome;
    // 基因突变概率
    private double mutationRate = 0.4;
    // 基因交叉概率
    private double crossoverRate = 0.98;
    // 遗传的代数(第几代)
    private int t = 0;
    // 变异对换次数
    private double variationExchangeCount = 1;
    // 遗传最大的迭代次数
    private int MAX_GEN = 200000;
    // 复制最优解的次数(选择种群的最优个体,然后复制几次,将最优个体复制多个,存到新的集合中)
    int cloneNumOfBestIndividual = 3;
    // 最佳迭代数
    private int bestT = 0;
    // 随机函数对象
    public Random random;
    // 各个个体的累积概率
    double[] probabilitys;

    public GeneticAlgorithm_TSP(List locationList) {
        this.locationList = locationList;
    }

    public void solve() throws IOException, ClassNotFoundException {
        initVar();
        solver();
    }

    public void solver() throws IOException, ClassNotFoundException {
        while (t < MAX_GEN) {
            popSize = population.size();
            // 基因进化
            evolution();
            // 更新种群
            population = copyGenomeList(newPopulation);
            t++;
        }
        // 输出结果
        System.out.println("最佳迭代次数:" + bestT);
        System.out.println("最短路程为:" + bestGenome.getPathLen());
        int[] bestPath = new int[cityNum + 1];
        System.arraycopy(bestGenome.getGenomeArray(), 0, bestPath, 0, bestGenome.getGenomeArray().length);
        bestPath[cityNum] = bestPath[0];
        System.out.println("最佳路径为:" + Arrays.toString(bestPath));
    }

    // 进化函数
    // 进化函数,正常交叉变异
    public void evolution() {
        //更新累积概率和总适应度
        updateProbabilityAndTotalFitness();
        // 挑选某代种群中适应度最高的个体
        HashSet actionIndex = selectBestGenomeAndJoinNext();
        // 赌轮选择策略对剩下的scale-1个个体进行随机的交叉,变异
        while (newPopulation.size() < population.size()) {
            double r = random.nextDouble();
            for (int j = 0; j < probabilitys.length; j++) {
                if (r <= probabilitys[j]) {
                    newPopulation.add(population.get(j));
                    break;
                }
            }
        }

        // 交叉
        if (random.nextDouble() <= crossoverRate) {
            int r = random.nextInt(cityNum);
            int k = random.nextInt(cityNum);
            while (r == k){
                r = random.nextInt(cityNum);
            }
            cross(k, r);
        }

        for (int i = 0; i < population.size(); i++) {
            // 变异
            if (random.nextDouble() <= mutationRate) {
                variation(i);
            }
        }

    }

    // 单点映射交叉
    private void cross(int k1, int k2) {
        // 获取要交叉的两个基因
        int[] genomeArray1 = newPopulation.get(k1).getGenomeArray();
        int[] genomeArray2 = newPopulation.get(k2).getGenomeArray();
        // 找到交叉位置
        int crossIndex = random.nextInt(cityNum);
        // 获取交叉片段
        for (int i = 0; i <= crossIndex; i++) {
            int temp = genomeArray1[i];
            genomeArray1[i] = genomeArray2[i];
            genomeArray2[i] = temp;
        }
        // 找到重复基因
        HashSet set = new HashSet<>();
        // 
        HashMap repeatMap = new HashMap<>();
        for (int i = 0; i < genomeArray1.length; i++) {
            if (!set.add(genomeArray1[i])) {
                repeatMap.put(i, genomeArray1[i]);
            }
        }
        set.clear();
        for (int i = 0; i < genomeArray2.length; i++) {
            if (!set.add(genomeArray2[i])) {
                for (int key : repeatMap.keySet()) {
                    genomeArray1[key] = genomeArray2[i];
                    genomeArray2[i] = repeatMap.get(key);
                    repeatMap.remove(key);
                    break;
                }
            }
        }
        // 交叉完毕,将基因放回个体,再将个体放回种群,并更新他们的适应值和路径长度
        newPopulation.get(k1).setGenomeArray(genomeArray1);
        newPopulation.get(k1).updateFitnessAndPathLen();
        newPopulation.get(k2).setGenomeArray(genomeArray2);
        newPopulation.get(k2).updateFitnessAndPathLen();
    }

    public void cross2(int k1, int k2) {
        // 获取要交叉的两个基因
        int[] genomeArray1 = newPopulation.get(k1).getGenomeArray();
        int[] genomeArray2 = newPopulation.get(k2).getGenomeArray();
        //使用LinkedHashSet存储元素,方便替换元素时,对元素进行删减
        LinkedHashSet hashSetI = new LinkedHashSet<>();
        LinkedHashSet hashSetJ = new LinkedHashSet<>();
        for (int k = 0; k < this.cityNum; k++) {
            hashSetI.add(genomeArray1[k]);
            hashSetJ.add(genomeArray2[k]);
        }
        //开始交换的位置,一直交换到尾部,即单点交叉(begin至少要从1开始,否则没有意义)
        int begin = random.nextInt(this.cityNum - 1) + 1;
        for (int k = begin; k < this.cityNum; k++) {
            //交换两个基因的对应位置
            int temp = genomeArray1[k];
            genomeArray1[k] = genomeArray2[k];
            genomeArray2[k] = temp;
            //删除对应的元素,该元素已经在k位置了
            hashSetI.remove(genomeArray1[k]);
            hashSetJ.remove(genomeArray2[k]);
        }
        //重新填充非交叉区域的元素
        begin = 0;
        for (Integer element : hashSetI) {
            genomeArray1[begin++] = element;
        }
        begin = 0;
        for (Integer element : hashSetJ) {
            genomeArray2[begin++] = element;
        }
        // 交叉完毕,将基因放回个体,再将个体放回种群,并更新他们的适应值和路径长度
        newPopulation.get(k1).setGenomeArray(genomeArray1);
        newPopulation.get(k1).updateFitnessAndPathLen();
        newPopulation.get(k2).setGenomeArray(genomeArray2);
        newPopulation.get(k2).updateFitnessAndPathLen();
    }

    // 变异(多次对换)
    private void variation(int k) {
        Genome genome = newPopulation.get(k);
        int[] genomeArray = genome.getGenomeArray();
        for (int i = 0; i < variationExchangeCount; i++) {
            int r1 = random.nextInt(cityNum);
            int r2 = random.nextInt(cityNum);
            while (r1 == r2) {
                r1 = random.nextInt(cityNum);
                r2 = random.nextInt(cityNum);
            }
            //交换
            int temp = genomeArray[r1];
            genomeArray[r1] = genomeArray[r2];
            genomeArray[r2] = temp;
        }
        //将变异后的基因序列放回个体
        genome.setGenomeArray(genomeArray);
        // 更新基因的适应值和路程长度
        genome.updateFitnessAndPathLen();
        //将变异后的个体放回种群
        newPopulation.set(k, genome);
    }

    //初始化变量
    public void initVar() {
        this.cityNum = locationList.size();
        this.population = new ArrayList<>();
        random = new Random(System.currentTimeMillis());
        //初始化距离矩阵
        dist = new double[cityNum][cityNum];
        for (int i = 0; i < cityNum; i++) {
            for (int j = i; j < cityNum; j++) {
                if (i != j) {
                    dist[i][j] = getDistance(locationList.get(i), locationList.get(j));
                    dist[j][i] = dist[i][j];
                }
            }
        }
        Genome.dist = dist;
        //初始化种群信息
        List path = new ArrayList<>();
        for (int i = 0; i < cityNum; i++) {
            path.add(i);
        }
        for (int i = 0; i < popSize; i++) {
            Collections.shuffle(path);
            int[] initPath = new int[cityNum];
            for (int j = 0; j < path.size(); j++) {
                initPath[j] = path.get(j);
            }
            Genome genome = new Genome(initPath.clone());
            population.add(genome);
        }
        bestGenome = copyGenome(population.get(0));
        for (int i = 1; i < popSize; i++) {
            Genome genome = population.get(i);
            if (bestGenome.getFitness() < genome.getFitness()) {
                bestGenome = copyGenome(genome);
            }
        }
        System.out.println("初始解为:" + bestGenome.getPathLen());
    }

    // 挑选种群中适应度最大的个体基因直接加入下一代种群
    public HashSet selectBestGenomeAndJoinNext() {
        newPopulation = new ArrayList<>();
        HashSet actionIndex = new HashSet<>();
        Genome tempBest = population.get(0);
        int maxIndex = 0;
        for (int i = 1; i < population.size(); i++) {
            if (population.get(i).getFitness() > tempBest.getFitness()) {
                tempBest = population.get(i);
                maxIndex = i;
            }
        }
        actionIndex.add(maxIndex);
        if (tempBest.getFitness() > bestGenome.getFitness()) {
            bestGenome = copyGenome(tempBest);
            bestT = t;
//            System.out.println("当前代数:" + t + " : " + bestGenome.getPathLen());
        }
        for (int i = 0; i < cloneNumOfBestIndividual; i++) {
            newPopulation.add(copyGenome(tempBest));
        }
        return actionIndex;
    }

    // 更新各个个体的累积概率和种群总适应度
    public void updateProbabilityAndTotalFitness() {
        probabilitys = new double[population.size()];
        totalFitness = 0;
        for (Genome genome : population) {
            totalFitness += genome.getFitness();
        }
        double rate = 0.0;
        for (int i = 0; i < population.size(); i++) {
            rate += (population.get(i).getFitness() / totalFitness);
            probabilitys[i] = rate;
        }
    }

    // 计算两点之间的距离(使用伪欧氏距离,可以减少计算量)
    private double getDistance(double[] place1, double[] place2) {
        // 伪欧氏距离在根号内除以了一个10
        return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)) / 10.0);
//        return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)));
    }

    // 拷贝单个基因
    public Genome copyGenome(Genome genome) {
        Genome copy = new Genome();
        copy.setGenomeArray(genome.getGenomeArray().clone());
        copy.setFitness(genome.getFitness());
        copy.setPathLen(genome.getPathLen());
        return copy;
    }

    // 拷贝基因集合
    public List copyGenomeList(List genomeList) {
        List copyList = new ArrayList<>();
        for (Genome genome : genomeList) {
            copyList.add(copyGenome(genome));
        }
        return copyList;
    }

}
运行结果
遗传算法求解tsp问题:48个城市...
初始解为:39492.9415375181
最佳迭代次数:18085
最短路程为(伪欧氏距离):11716.839185306864
最佳路径为:[37, 0, 7, 8, 39, 14, 32, 11, 10, 22, 40, 15, 21, 2, 33, 13, 12, 24, 4, 47, 28, 1, 3, 25, 41, 9, 34, 44, 23, 31, 38, 20, 46, 19, 45, 35, 6, 5, 36, 18, 16, 42, 26, 29, 27, 17, 43, 30, 37]
求解用时:3.007 s
-------------------------------------------------------------------------
遗传算法求解tsp问题:48个城市...
初始解为:126129.17281692004
最佳迭代次数:94162
最短路程为(欧氏距离):37319.47142582528
最佳路径为:[21, 15, 40, 33, 2, 13, 24, 4, 28, 1, 25, 3, 34, 44, 9, 23, 41, 47, 38, 31, 20, 46, 22, 12, 10, 11, 19, 32, 45, 29, 26, 18, 36, 16, 42, 5, 35, 17, 27, 6, 43, 30, 37, 14, 39, 8, 7, 0, 21]
求解用时:3.044 s
-------------------------------------------------------------------------

补充:以上使用的是tsplib上的数据att48,这是一个对称TSP问题,城市规模为48,其最优值为10628(伪欧氏距离)。tsplib地址:http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950522.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号