路径规划-基于Java+遗传算法求解应急路径规划问题-附项目源码-优质项目实战.zip

# 遗传算法在应急路径规划上的应用 ## 一、应急路径规划介绍 ### 1、应急路径规划和普通路径规划的区别 应急路径规划和传统的路径规划不同 传统的路径规划，例如使用 **迪杰斯特拉** 算法求最短路径的问题，其输入是固定的，且需要考虑的条件不会很复杂，但是一旦条件复杂或者数据量大起来，那么运算时间就会成倍数增长  而应急路径规划，因为灾情的不确定性，其路径信息是会实时更新的，并且还要考虑车辆载重、时间窗等问题，最大的区别是，应急路径规划一般的需求是车辆要能行驶到所有受灾点，还要返回起始点，这就和货郎问题十分类似了  ### 2、应急路径规划需要考虑的条件 应急车辆路径问题不同于传统的车辆路径优化问题，本文将构建带时间窗的多车辆路径优化问题，应急物资在救援中心，有N个应急需求点，救援中心有k辆车，优化目的是对救援中心和紧急需求点，组织适当的行车路线，使车辆有序地完成应急救援任务，在满足一定的约束条件（货物需求量、交发货时间、车辆容量限制）下，达到一定的目标（时间违背成本最小，应急效率最高)。 #### 1）受灾点紧急程度 受灾点紧急程度我们可以用级别 5-1 表示 5代表最紧急，1代表最不紧急 当计算适应度时，我们对每个位置递减的进行权值相乘，然后累加适应度 这里我要先当个预言家，其实写到后面我发现，我的模型存在个体适应度差距不大的问题，轮盘赌的作用聊胜于无 所以我故意将受灾点紧急程度的差距范围扩大为几百 后面如果数据跑出来不好看，还要看情况，调整为 k 或者 w 数量级的差距  **我们可以看下面两个例子：** `start -> A -> B -> C -> start` A 紧急程度：1 B 紧急程度：2 C 紧急程度：3 紧急程度适应度得分： `3*1 + 2*2 +1*3 = 10` `start -> C -> B -> A -> start` A 紧急程度：1 B 紧急程度：2 C 紧急程度：3 紧急程度适应度得分： `3*3 + 2*2 +1*1 = 14` 可以看到，运用这种算法，我们的适应度得分，会随着紧急受灾点的位置考前而增加 #### 2）时间窗 假设 A 点对物资的需求时间在 0-9 内 那么如果物资送达时间为 0-9 之间，则适应度分数不减 如果超过 9 ，我们就会依照超出的时间，减去超时对应权值，对适应度得分做减法 **例：** ```java TIME_WINDOW_WEIGHT = 10;// 时间适应度权值 carrArriveTime = 11; // 车辆到达时间 srart = 0;// 时间窗起始 end = 9;// 时间窗终止 score = score - (carrArriveTime-end)*TIME_WINDOW_WEIGHT;// 对适应度分数做减法 ``` 在本程序中，为了计算方便，我们的时间窗起始时间始终设置为 0 #### 3）受灾点物资重量需求是否满足 车辆初始载重我们都设置为 10 t 不同受灾点对物资的需求量是不同的 这里有两个策略：**强硬策略**和**缓和策略** * **缓和策略：** 如果在后期出现剩余载重不满足受灾点的情况，我们需要依照情况，对适应度得分做减法 这样好处在于不容易陷入局部最优，坏处在于可能给出的结果不满足现实需求，决策者无法更具给出的数据动态为每辆车分配不用的载重 * **强硬策略：** 如果在后期出现剩余载重不满足受灾点的情况，我们直接将这种情况排除 好处在于决策者能根据信息，做出更优的判断，坏处在于给出的数据可能无法满足强硬策略的条件，导致出不了结果 <hr/> 这里我们选择缓和策略，以避免出现程序阻塞为主 #### 4）注意点 **1、**这里我们需要注意，最后算出来的适应度得分，必须是正数 下一步交叉时，就无法使用轮盘赌法选择合适的父代了 为了保证是正数，我们可以对计算结果进行补偿（加上一个统一的数），以保证轮盘赌算法能正常执行 **2、**适应度函数要保证个体适应度差距比较大，不然轮盘赌就和随机算法没什么区别了 ## 二、遗传算法介绍 遗传算法，我之前写过一篇文章进行介绍 https://mp.weixin.qq.com/s/_mUK2mdczU4x_lekpuh6hw 在阅读下面的内容之前，如果还有对遗传算法不了解的同学，强烈建议去看一下哦 ## 三、遗传算法在应急路径规划上的应用 遗传算法的执行流程，除了适应度计算之外，其他与特定问题的条件几乎是隔离开来的 我们要做的，就是想办法将应急路径规划考虑的条件，编码成遗传算法所能识别的数据类型 ### 1、个体编码与种群初始化 #### 1）编码规则 针对路径规划问题，我们个体编码策略选择如下 路径名称用字母代替，字母在字母表中的位置即其单片染色体的编码，**数字0 表示起始点** **例如：** `start -> A -> B -> C -> start` **对应的编码为：** `0 1 2 3 0` #### 2）编码注意事项 我们的编码还要符合路径规划的要求，即： **1、**基因中起始点0个数 为 carNum +1 **2、**每个点只能出现一次，且所有点都必须出现 **3、**两个起始点不可以相邻 **4、**基因收尾必须是起始点位置 0 ``` 假设 carNum = 2 pointNum =4 正确的基因: 0 2 3 0 1 4 0 错误的基因： 0 3 3 0 1 4 0 (3受灾点重复) 0 0 3 2 1 4 0 (有两个起始点重合->有车子没出发) ``` #### 3）种群初始化 ``` GeneticAlgorithm/init() - Chromosome() // constructor - Chromosome/init() ``` * **种群初始化：** 种群初始化直接调用个体的构造函数 个体带参构造函数里有初始化方法 ```java private void init() { for (int i = 0; i < POP_SIZE ;i++) { Chromosome chromosome = new Chromosome(CAR_NUM, POINT_NUM); pop.add(chromosome); } } ``` * **个体初始化：** `init()` 方法确保生成的个体合法 ```java public Chromosome(int carNum, int pointNum) { this.carNum=carNum; this.pointNum=pointNum; geneSize = carNum+1+pointNum; gene = new int[geneSize]; for (int i = 0; i < geneSize; i++) { gene[i]=-1; } init(); } // ... public void init() { int remainStartPoints = carNum + 1; gene[0]=0; gene[geneSize-1]=0; remainStartPoints-=2; // 存放未被放置的受灾点 List<Integer> pointList = new ArrayList<>(); for (int i = 1; i <= pointNum ; i++) { pointList.add(i); } // 随机生成起始点 if (carNum>1 && geneSize>4) { while (remainStartPoints>0) { // 随机基因起始点 int tmpStartIndex = r.nextInt(geneSize - 4) + 2; if (gene[tmpStartIndex]!=0 && gene[tmpStartIndex-1]!=0 && gene[tmpStartIndex+1]!=0) { gene[tmpStartIndex]=0; remainStartPoints--; } } } for (int i = 0; i < geneSize; i++) { if (gene[i]==-1) { int randomIndex = 0; if (pointList.size()>0) { randomIndex = r.nextInt(pointList.size()); } gene[i]=pointList.get(randomIndex); pointList.remove(randomIndex); } } } ``` * **判断生成的个体是否合法：** ```java public static boolean isGoodChromosome(Chromosome chromosome) { // 1、基因不存在 if (chromosome==null || chromosome.getGene()==null || chromosome.getGene().length==0) return false; int[] gene = chromosome.getGene(); List<Integer> genePointList = new ArrayList<>(); // 基因中目标起始点的个数 int targetStartPointNum = chromosome.getCarNum() + 1; int startPointCount = 2; if (gene[gene.length-2]==0) return fa