|
多目标蚁群算法路径规划（四）
文章目录
多目标蚁群算法路径规划（四） 零、系列前言（一定要看）一、内容说明1.1 本章内容说明1.2 本章主要分享内容简介(摘要)
二. 多目标计算预先准备2.1 多目标规划时候需要考虑的问题1. 明确目标函数之间的权衡关系2. 目标函数的设计3. 常用的目标函数选择
2.2. 常用求解多目标算法1. 算法综述2. 不同多目标算法的比对
三、完整多目标求解结果过程展示3.1 数据获取3.2 数据预处理3.2 约束条件整理3.3 初步运行求解3.4 启发式参数设计优化3.5 多目标求解的怕累托排序3.6 路径求解结果的调度优化3.7 规划结果的分析讨论3.8 优化改进算法与多算法比对3.9 根据问题背景多角度改进优化3.10 经典数据集的运算与总结
四。相关的求解代码4.1 蚁群多目标路径求解4.2 蚁群多目标路径求解非支配排序主函数4.3 非支配排序
零、系列前言（一定要看）
本系列为总结本人近2年多关于启发式算法解决路径规划的相关内容。主要从以下几个主题内容进行系列写作1.常见的数据获取方式与处理过程、，2、算法的基础流程，3.常见算法改进，4.多目标排序、5.基于应用场景的改进、6.其他相关问题、7、批量运行测试数据本系列全程免费提供相关代码。本系列代码来源主要参考网上相关博客与文献、根据不同实际需求重构的代码。本文所有提供的代码与文字说明仅供参考，不作为商业目的。对内容有疑问或是错误部分可以留言或私信。有偿定制特定功能, qq:1602480875。价格范围60—500。（建议优先看完系列内容，尝试系列中的代码，这些都是免费且能解决大部分问题。），具体代码后续会以完整形式上传百度云。 更新时间：2022年1月2日 全文共33000字建议收藏
一、内容说明
1.1 本章内容说明
多目标计算的原因多目标求解的预先的准备多目标计算的流程计算结果展示与部分代码分享。一个完整流程结果的展示下期预告
1.2 本章主要分享内容简介(摘要)
一个真实环境的决策过程中通常包含不止一个目标需要满足最优条件，而且这些目标之间还存在相互矛盾与制约。为了权衡（trades-off）不同目标的最优条件，决策过程退而求其次计算出目标最优的包络曲线（帕累托最优解）。我们希望获得的规划结果在多个角度都是约束条件中最优的且我们可以根据实际的需求选择帕累托曲线上的点。首先本文第一部分介绍进行多目标规划时候需要考虑的问题，确认问题是否有必要考虑多目标设计。以及常用的多目标选择以及需要注意的事项，针对常用的多目标算法进行分享说明与常用算法框架第二部分本文是对多目标算法的比对与结果评价的常用方法进行总结。相比单目标只需比较的最终目标的大小，多目标的比较方法相对复杂通常用的方法包括：1.权衡曲线分析，2.取非支配真实总体，3.错误率，4.空间分布指标（非支配总体数量（NOVG）、非支配真实总体数量（OTNVG）、非支配真实总体率（OTNVGR）、失误率（ER）、空间分布指标（S））等。最后总结不同多目标算法设计思路的特点与局限性。第三部分展示一个完整的多目标规划流程结果：1. 数据设计，2. 数据划分，3.多目标路径规划，4.计算帕累托非支配前沿解，5.对计算后的线路根据车辆数目约束求调度结果，6.算法结果评价
二. 多目标计算预先准备
2.1 多目标规划时候需要考虑的问题
1. 明确目标函数之间的权衡关系
我们在设计多目标评价函数时首先需要考虑的是选择的的目标之间是否有线性相关性，这个部分是决定后续求解过程中排序结果的分布。通常我们在文献中经常看到最短路径和碳排放或是最小成本同时作为目标函数，如果只是简单将两者组合就容易导致出现典型的没有考虑目标的线性相关关系缺少判断。这也是经常导致结果不理想，数据结果难以解释。 例如：
最
短
路
径
=
∑
车
辆
行
驶
距
离
最短路径=\sum 车辆行驶距离
最短路径=∑车辆行驶距离
碳
排
放
=
车
辆
行
驶
总
距
离
×
二
氧
化
碳
排
放
碳排放=车辆行驶总距离×二氧化碳排放
碳排放=车辆行驶总距离×二氧化碳排放
成
本
=
距
离
∗
油
价
+
车
辆
数
目
∗
固
定
消
耗
成本=距离*油价+车辆数目*固定消耗
成本=距离∗油价+车辆数目∗固定消耗 上述两者数学上都与路径长度线性相关，在导致求解的最优解只会有一个方向，不存在权衡的过程。只需要将两者合并转化成本作为一个与行驶距离相关的单目标函数函数.这种情况下没必要考虑成多目标函数进行设计。
2. 目标函数的设计
那么如何设计一个好的多目标函数呢？我们还是以上述两个目标函数为例考虑，对目标函数进行修改。 首先重新思考车辆碳排放的过程是否除了路径相关还与其他什么联系，比如：1.考虑车辆运输载重对碳排放的权重是否同等于或是大于行驶路径的长度。2.车辆的频繁启动与停留是否也是重要需要考虑的因素。当我们考虑在两个条件后就会使碳排放成本不完全与行驶路径距离相关，并非路径越短就会使碳排放越低。两者可以出现相互制约的结果，有时路径长而碳排放则表现为较低的水平（如图）。同时单次规划上路径点的个数也是制约的目标求解的限制因素。
最
短
路
径
=
∑
车
辆
线
路
最短路径=\sum 车辆线路
最短路径=∑车辆线路
碳
排
放
=
f
u
n
c
t
i
o
n
（
车
辆
载
重
，
行
驶
距
离
）
×
二
氧
化
碳
排
放
+
f
u
n
c
t
i
o
n
2
（
路
径
经
过
点
数
目
）
碳排放=function（车辆载重，行驶距离）×二氧化碳排放+function2（路径经过点数目）
碳排放=function（车辆载重，行驶距离）×二氧化碳排放+function2（路径经过点数目）
3. 常用的目标函数选择
本文整理了一些常用的多目标函数，但在具体实际应用过程中需要根据问题背景进行考虑。1）满意度与成本，2）路径长度与碳排放 3）成本与调度等（待补充，也可留言补充）。 
满意度计算模型： 
2.2. 常用求解多目标算法
1. 算法综述
目前常用的多目标求解算法包括线性求解器直接计算，通过启发式算法求解例如：NSGA-Ⅱ，NSGA-Ⅲ，MDVRPTW-Ⅱ等。其核心部分都是通过启发算法获得初始解，通过非支配排序过程对启发是求解的结果进行排序分层。根据每一层排序结果进行下一轮的重新迭代，以此多次迭代得到多目标排序结果。然后将排序结果绘制帕累托非支配解，根据实际需求求解出最优的前沿解。 
2. 不同多目标算法的比对
采用非支配总体数量（NOVG）、非支配真实总体数量（OTNVG）、非支配真实总体率（OTNVGR）、失误 率（ER）、空间分布指标（S）五个评价指标，评价算法性能优劣。
非支配总体数量（NOVG）：表示非支配解集中解的个数。非支配解集中的 解的数量越多，表示此算法对特定场景下的问题求解时，可以得到更多的解，解的多 样性越好，非支配解集越优。非支配真实总体数量（OTNVG）：指非支配解集中的可行解在此特定问题下标准解集的数量。此评价指标与非支配解集中较差的解集无关，表示运行算法得到的非支配解集中最优解的个数。非支配真实总体率（OTNVGR）：表示非支配真实总体数量占此特定问题标准解集中的百分比。此指标有效防止了对于不同问题的标准解集的数量不同，从而使非支配真实总体数量指标失效的问题。例如：运行蚁群算法和遗传算法得出的帕累托前沿解，经过再次非支配排序，共同构成了此问题的标准解集（包含 10 个解），其中蚁群算法的帕累托前沿解集中有 6 个解与标准解集重复，那么蚁群算法运算结果的非支配真实总体率为百分之 60%。失误率（ER）：该指标由 Van Veldhuizen 提出，指的是非支配解集中可行解不在最优解集中解的个数，占标准解集的百分比。
  
三、完整多目标求解结果过程展示
过程中涉及的相关实现过程可以参照本系列前面已经发表的博客进行对照。本文的结果全部来源博主个人完成的实例。
3.1 数据获取
基于百度地图API获取实际路径距离与经纬度坐标 
3.2 数据预处理
将获取的数据转化处理，区域划分 
3.2 约束条件整理
设置约束条件与需求   
3.3 初步运行求解
区域内求解结果划分求解规划路径  比较求解过程的迭代稳定性与收敛性优化参数设置
3.4 启发式参数设计优化
- 
3.5 多目标求解的怕累托排序
将多目标规划结果进行帕累托排序，获取前沿解 
3.6 路径求解结果的调度优化
根据帕累托前沿解获取路径规划结果，绘制最优车辆线路调度
3.7 规划结果的分析讨论
获取最优线路与最优发车顺序结果 
3.8 优化改进算法与多算法比对
3.9 根据问题背景多角度改进优化
3.10 经典数据集的运算与总结
四。相关的求解代码
4.1 蚁群多目标路径求解
clc
clear
close all
% 主程序
for i=2:9
a='H:\软件安装包\项目文件\交通规划项目结果图\蚁群算法规划\工作簿1.xlsx';%文件地址
[x2,D,Cap,C,d_u,t1,v_2,cost_2]=fist_1(5,a);
D=D(1:i,1:i);
Demand=zeros(size(D,1),2);
Alpha=1;Beta=5; %
Rho=0.75; %
iter_max=100; %迭代次数
Q=10; %
m=size(D,1); %起始放置数目
qidian=1; % qidian起点坐标
[R_best,L_best,L_ave,Shortest_Route,Shortest_Length,j_1_j]=ANT_VRP_1(D,Demand,Cap,iter_max,m,Alpha,Beta,Rho,Q,qidian,d_u,t1,v_2,cost_2,x2);
Shortest_Route_1=Shortest_Route; %提取最优路线
cc=find(Shortest_Route_1==qidian);
xx_1=[];
if length(cc)==2
for i=1:1
cs_1=length(Shortest_Route_1(cc(i):cc(i+1)));
xx_1(i,1:cs_1)=Shortest_Route_1(cc(i):cc(i+1)); %路线
end
else
for i=1:length(cc)/2+2
cs_1=length(Shortest_Route_1(cc(i):cc(i+1)));
xx_1(i,1:cs_1)=Shortest_Route_1(cc(i):cc(i+1)); %路线
end
end
Shortest_Length; %提取最短路径长度
%% ==============作图==============
% figure(1) %作迭代收敛曲线图
% x=linspace(0,iter_max,iter_max);
% y=L_best(:,1);
% plot(x,y);
% xlabel('迭代次数'); ylabel('最短路径长度');
figure(2) %作最短路径图
plot(C(Shortest_Route,1),C(Shortest_Route,2),'o-');
grid on
for i =1:size(C,1)
if i==qidian
text(C(i,1),C(i,2),' 起始港口 ');
else
text(C(i,1),C(i,2),[' ' num2str(i)]);
end
end
xlabel('客户所在横坐标'); ylabel('客户所在纵坐标');
hold on
best_all(i)=1/Shortest_Length;
for i=1:length(Shortest_Route)-1
tim_1(i)=t1(Shortest_Route(i),Shortest_Route(i+1));
end
time_all=sum(tim_1);
end
hold off
disp("最后收益为：")
disp(strcat(num2str(max(best_all)),'元'))
disp("最后需要经历的港口数目：")
disp(num2str(find(best_all==max(best_all))))
disp("运行的时间：")
disp(strcat(num2str(time_all),'天'))
disp("运行的顺序：")
disp(Shortest_Route)
figure
for i =1:size(C,1)
if i==qidian
text(C(i,1),C(i,2),' 起始港口 ');
else
text(C(i,1),C(i,2),[' ' num2str(i)]);
end
end
xlabel('客户所在横坐标'); ylabel('客户所在纵坐标');
function ACO_VRPTW(all_name_sys)
%% 多目标批量计算
%% 版本0.1
%% 时间
% clear
% clc
% close all
tic
%% 输入数据解析
filepath=all_name_sys.filepath;
foler=all_name_sys.foler;
stad_pint=all_name_sys.stad_pint;
output_data_name=all_name_sys.output_data_name;
num_file_data=all_name_sys.num_file;
%% 用importdata这个函数来读取文件
c101=xlsread(foler);
%% 调试时使用
% p= mfilename('fullpath');
% [filepath,name,ext] = fileparts(p);
% c101=importdata('c104_1.txt');
% % 如果第一行不是起点，运行下面代码
% stad_pint=[ 0 86 51 0 0 1236 0 ];
% c101=[stad_pint;c101];
if c101(1,1)~=0
disp('已设置起点')
c101=[stad_pint;c101];
end
cap=600000; %车辆最大装载量
v_cap=2; %车辆速度（单位时间）
%% 锟斤拷取锟斤拷锟斤拷锟斤拷息
E=c101(1,5); %配送中心时间窗开始时间
L=c101(1,6); %配送中心时间窗结束时间
pint_list_name=c101(:,1);%名称坐标
vertexs=c101(:,2:3); %所有点的坐标x和y
customer=vertexs(2:end,:); %顾客坐标
cusnum=size(customer,1); %顾客数
v_num=25; %车辆最多使用数目
demands=c101(2:end,4); %需求量
a=c101(2:end,5); %顾客时间窗开始时间[a[i],b[i]]
b=c101(2:end,6); %顾客时间窗结束时间[a[i],b[i]]
time_x=[a,b];%时间
width=b-a; %顾客的时间窗宽度
s=c101(2:end,7); %客户点的服务时间
choose_way=input('计算的距离类型————1 坐标位置 2 经纬度===');
if choose_way==1
h=pdist(vertexs);
dist=squareform(h); %距离矩阵 坐标相减
% dist(1,3)=555;
else
% mi=vertexs;
% cc=zeros(size(mi,1));
% for j=1:size(mi,1)
% for i=j:size(mi,1)
% cc(j,i)=abs(6371004*acos((sin(deg2rad(mi(j,2)))*sin(deg2rad(mi(i,2)))+cos(deg2rad(mi(j,2)))*cos(deg2rad(mi(i,2)))*cos(deg2rad(mi(i,1)-mi(j,1))))));
% if i==j || cc(j,i)==0
% % cc(j,i)=eps;
% cc(j,i)=0;
% end
% cc(i,j)=cc(j,i);
% end
% end
% un_1_1=cc;
%
% a=a*40;
% b=b*40;
time_x=[a,b];%时间
width=b-a;
D = Haversin(vertexs);
dist=D; %距离矩阵
end
%% 锟斤拷始锟斤拷锟斤拷锟斤拷
w_PPm_b=1;%锟斤拷始锟斤拷锟斤拷锟轿?1
m=100; %蚂蚁数量
alpha=1; %信息素重要程度因子
beta=3; %启发函数重要程度因子
gama=2; %等待时间重要程度因子
delta=3; %时间窗跨度重要程度因子
r0=0.5; %r0为用来控制转移规则的参数
rho=0.85; %信息素挥发因子
Q=100; %更新信息素浓度的常数
Eta=1./dist; %启发函数
Tau=ones(cusnum+1,cusnum+1); %信息素矩阵
Table=zeros(m,cusnum); %路径记录表
iter=1; %迭代次数初值
iter_max=2; %最大迭代次数
Route_best=zeros(iter_max,cusnum); %各代最佳路径
Cost_best=zeros(iter_max,1); %各代最佳路径的成本
%% 迭代寻找最佳路径
while iter |