多目标车辆路径问题学习全过程(详细)

一、学习前准备知识

        1.Solomon算例及目前最优解：

https://www.sintef.no/projectweb/top/vrptw/25-customers/

Search (vrp-rep.org)

        2.Solomon算例详解

        randomly generated  in problem sets R1 and R2

        clustered in problem sets C1 and C2,

        a mix of random and clustered structures in problem sets by RC1 and RC2.

        Problem sets R1, C1 and RC1 have a short scheduling horizon  and allow only a few customers  per route (approximately 5 to 10).

        In contrast, the sets R2, C2 and RC2 have a long scheduling horizon permitting many customers (more than 30)  to be serviced by the same vehicle.

根据顾客分布情况分为3类：

        C类表示顾客分布比较集中，R类顾客分布比较随机，

        RC类既有集中分布的顾客，又有随机分布的顾客。

同时每一种类型的顾客又分为两类：

        100系列的顾客表示时间窗比较窄，200系列的顾客表示时间窗比较宽。

        3.决策变量：

        1).遗传算法TSP实例中的一个个体代表着解决单目标问题中的一条完整路径，该个体就是一个决策变量。

        2).NSGAII三目标VRPTW优化问题中，一个个体的基因必须完成所有的目标任务，该个体就是一个决策变量。

        3).该例中，假定30个决策变量，在matlab中表示为1个f1的值，其余29个是用来计算f2目标函数值的，即由这30个决策变量也称基因组成的个体可以实现一次ZDT1测试函数，通过NSGAii优化后，在200种群中以期获得一个最优解，即最好的决策变量。

        数学上决策变量是目标函数的自变量，二者之间有一对一的函数映射关系。

二、NSGA-II理论学习

        1.NSGAII算法的非支配排序

        如果是三目标函数优化问题，非支配解意味着三个目标函数值都优于其余所有支配解，缺一不可，但是在非支配排序中，可能出现以下情况，导致产生多个非支配解：两个或多个个体三个目标函数值都相同；个体1的两个目标函数值优于个体2，个体2的第三个目标函数值优于个体1，但个体1与个体2都优于其余解，因此个体1和2都是非支配解，非支配等级都=1。若个体1和2均不是非支配解，非支配等级按其被支配的次数排序。

        初始化有200个体的种群，首先找出这200个体中的非支配解，放入非支配前沿面中(rank等级=1)，再根据被支配次数排序剩余个体，直至所有个体都分配好排序等级。然后在每一级的非支配等级中，分别进行拥挤度排序。排序完成。

        首先，论证每一代非支配解的存在性：

        非支配解A的定义：若是种群中其他所有的个体都无法支配解A，即没有一个个体的优化目标全部优于解A(无差异解并非支配关系)，解A就是非支配解，并非要求解A的优化目标全部优于其他所有个体，因此非支配解并非最优解，而是该种群中的均衡解，非支配排序过程：均衡解->极致次优解。

        2.NSGAII的精英选择策略

        首先选择非支配前沿面上所有非支配解，再依次选择第二等级，第三等级…选择的同时，每次比较待加入的种群数量，判断其是否多余规定初始种群个数即每次计算剩余可用种群数，如果选完所有的第五等级的种群后，剩余数量不够放时，将第五等级的个体按拥挤度距离由高到低依次排序，选择较高值，直至数量到达popsize。

        3.NSGAII的二元竞标赛选择

        避免误区：遗传算法中的选择、交叉、变异的各自执行完的数目，假定200总种群，选择出的优秀父代种群100个，交叉变异在选择的100父代种群基础上产生200个子代个体，总共300个体，如此设计的算法结构，有以下好处：

       a) 选择算子可以保证每次迭代时的初始种群都会是上一代产生的种群中的较优解；在选择算子产生的种群基础上执行交叉变异算子，同时保证了最优解的收敛导向性与多样性。

       b) 选择交叉变异执行完毕后，合并种群的操作非常重要，因为选择算子产生的种群保证了算法迭代过程继承了上一次迭代的较优解，保证了算法向着好的方向进行，即加强了算法收敛性；而交叉变异算子产生的种群，在较优解的基础上交叉变异，保证了算法多样性；合并这两个种群，效果不言而喻。

        c)局部搜索算子须在交叉变异产生的种群基础上搜索的效果劣于在选择产生的种群基础上搜索，因为选择产生种群一般都是较优解，而最优解只可能是较优解的邻域解

        而目前的算法结构的创新，也集中在增强算法的收敛性与多样性，如双种群混合遗传算法

双种群混合遗传算法
   种群 I 作为精英群体，采用扫描算法思想生产初始种群，使得种群 I 在迭代之初就
处于一个较优状态。利用变邻域搜索策略进行局部搜索，提高算法搜索到最优解的概率。

   种群 II 作为劣势群体，进行全局开发，判断种群达到早熟收敛状态时，植入外部新
个体，保证种群 II 的多样性。

   种群 I 和种群 II 通过移民算子进行种群间的协同优化，整体上提升算法稳定性和可行性。

        4.遗传算法机理研究

        遗传算法强大的全局搜索能力在于交叉变异，交叉变异的产生解可覆盖大部分解空间；局部搜索能力弱在于缺乏局部搜索算子，即无法搜索较优解附近的解空间。

        举个例子，遗传算法像个婴儿，虽然有无穷的发展方向，但是具体的最优需要严格的外界指导，在实际应用中，遗传算法在适应度与惩罚函数双重指导下进行寻优，也只能在这双重标准的界限下寻找最优解。

        求解Solomon算例时，由于时间窗过窄，寻找最优解也相对容易，但若将Solomon算例中时间窗间隔变宽，则可行解的解空间范围会随着时间窗的变宽而急剧变大，这是遗传算法搜索最优解的速度及效率将会变得越发迟缓，极大可能无法得到最优解。改进遗传算法已成必然。

        5、遗传算法本体在NSGA-II算法中的作用

        NSGA-II算法如果仅靠交叉变异获得新解，那消除约束违反数目的难度将随着决策变量的长度增加而快速递增。

        实验表明，20个节点的优化问题(三优化目标，多约束下)，NSGAII中的交叉变异都无法找到最优解。因此，在复杂问题中，NSGAII中的交叉变异仅可以作为产生新解(大概率是非可行解)的一种方式，而形成可行解和寻优过程需要局部搜索算子完成。

三、多目标优化问题的求解思路

        解决多目标问题时，首先需要明确优化目标之间是否是合作关系，当优化目标之间是合作关系时，多目标优化问题就成为了纳什均衡问题，当优化目标之间是非合作关系时，多目标优化问题就成了帕累托最优问题。

        1.多目标优化过程恶化优化结果

        多目标优化时，例如四目标优化，将优化目标修改为两两相同，此时多目标优化并没有降低为双目标优化，反而延缓了算法的收敛速度。

四、VRP变体解析

        1.MTVRP多旅途问题

持续更新中

…个人见解，如有疏漏，评论区可留言

今天的文章多目标车辆路径问题学习全过程(详细)分享到此就结束了，感谢您的阅读。