NSGA2求多目标VRPTW配送成本满意度帕累托解MATLAB源码
2021-01-06 22:42阅读：
先说结论：
1.
多目标优化问题的各个目标函数之间应该是相互对立的，即各个目标函数不能同时达到最优。如果不是对立的，那不能称之为多目标优化问题，下述也不再适用。
2.
多目标优化问题的解法最常用的方法就是两种：一是将多目标问题转换为单目标，二是直接求帕累托解集。但这两种方法都有各自的缺点。（其实还有解法3，在下文说明）
3.
解法1将多目标问题转换成单目标优化问题的缺点或者说难点是：难以统一各个函数的量纲，难以给定各个函数合适的权重。用解法1必须解决这两个问题。
4.
解法2是求多目标函数的帕累托解集。首先很多人理解不了怕累托解集是什么东西，再一个求帕累托解集的方法比较少，最常见的就是遗传算法的NSGA2以及多目标粒子群的，其他算法基本无法实现。另外还有一个也不能算是缺点吧，就是帕累托解集是解的集合，是由很多个解组成的，对于有些问题必须提供一个方案时，还是要在解集里进行挑选。
5.
这两种算法究竟要选哪一种呢？如果你想把你的论文写的复杂一些，那就用解法2求帕累托解集，因为你可以对帕累托解集的结果进行大量的分析，而且分析后同样可以得到解法1的结果，且是有理有据的得到合理的结果（统一量纲、权重系数）。如果你想简单的解决这个问题，那就采用解法1
.
问题是外卖配送路径优化，优化目标是外卖员配送成本（行驶距离）越低越好和客户的满意度（准时性）越高越好。
是一个典型的多目标优化问题：问题的两个目标函数之间是相互对立的，两目标函数不能同时达到最优。要获得较高的客户满意度就必定要牺牲外卖员的配送成本，要降低配送员的配送成本就必定降低客户的满意度。
解法1：求帕累托解集
采用该方法的
第一个难点就是：很多人理解不了帕累托解集的概念与意义。
先看下图，这是我用
NSGA2方法求得的上述问题的帕累托解集。
解集解集，它是解的一个集合，集合里有多个解。帕累托解集的一层意思就是解集里的解谁也不比其他解优，但谁也不比其他解差。
比如在这个案例中，图中的任意一个点都代表一个解（一个方案），比如解
A配送路径的满意度是
0.712，配送成本是
1785元，解
B配送路径的满意度是
0.848，配送成本是
1888元。解
A的满意度低于解
B的满意度，但配送成本比解
B的也低。所以帕累托解集的解的一个特点就是无法区分任意两个解之间的谁优谁劣。
这时有人会问，这个解集里会不会存在解
A的满意度比
B优，而且配送成本也比
B优呢？答：不会。多目标求帕累托解集的过程其实就是一个剔除你所说的这种情况的过程，然后得到的结果就是任意两个解之间互不优劣。帕累托解集的求解过程类似于（只是类似于）固定一个成本，然后求得最优的满意度，或者固定一个满意度，求得最优的成本。所以不会存在这种疑问的情况。
第二个难点就是：对于一些问题，他终究要给出一个方案，也就是要在解集里再选一个解。这里其实就是先说结论的第
5条了。
当你得到一个帕累托解集的时候，其实你就拥有了一切。
首先，多目标转单目标，在这个解集中，你可以得到每个目标函数的最大值和最小值，可以进行归一化，这样就实现了统一量纲。
第二，其实就是结论里的方法
3，你可以固定一个目标函数来分析另一个目标函数，如要实现最低满意度
0.8时，这个时候的最优成本是多少？最低满意度是
0.7、
0.9时对应的最优成本是多少。
等等。
以上就是用帕累托解集求多目标的注意事项了，关键还是要自己能理解帕累托解集的意义。
下面是程序的另一组算例：有帕累托前沿解集、成本最优满意度最差时的方案、成本最差满意度最优时的方案、当然其他成本与满意度的方案也是可以输出的。
所有程序文件如下图
本程序为付费服务，如有需要请联系我，主页有联系方式，非诚勿扰。
%%%% NSGA2求解最小成本和满意度
%%%% by 圆 一个有心的人在用心做事
%%%% 编程时间：2020-12-21
%%%% 如有问题请联系 QQ:3171304690 /530807088(好友已满) 新浪微博:MATLAB圆创工作室
% ======================= 高 端 定 制 · 用 心 CODING
======================
clc
clear
close all
tic
data = xlsread('数据.xlsx',1,'C2:H32');
q = data(:,1);
ET = data(:,2);
T = data(:,3);
LT = data(:,4);
position = data(:,5:6);
ST = 5;
N = size(position,1) - 1;
qmax = 6;
% 车容量
speed = 200;
% 车辆行驶速度
ck = 50;
% 发车成本
a = 0.002;
%
车辆行驶单位距离成本
b = 0.5;
tbh = 5;
fitmax = 80000000;% 最大惩罚
NP = 80;
% 种群个体数量
maxgen = 500;
Pc = 0.8;
% 交叉概率
Pm = 0.2;
% 变异概率
M = 2;
%
plot(position(:,1),position(:,2),'bo')
D = zeros(N+1);
for i = 1 : N + 1
for j = i+1 : N + 1
D(i,j) = sqrt(sum((position(i,:) -
position(j,:)).^2)) * 100;
D(j,i) = D(i,j);
end
end
dim = 2 * N + 1;
%% 初始化种群
chrom = initpop(NP, M, dim, N, D, q, ET, T, LT,
ST,qmax,speed,fitmax,ck,a,b,tbh);
%% 非支配排序（non-domination-sort）
chrom = nonDominatedSort(chrom, M, dim );
%% 进化过程
figure(1);
for gen = 1 : maxgen
gen
% 选择父代用于繁殖后代。原始NSGA-II采用基于拥挤度比较算子的二进制锦标赛进行选择的
pool = round(NP/2);
tour = 2;
% 选择操作
parentchrom = tournamentSelect(chrom, pool,
tour);
% 交叉和变异操作
newchrom = geneOperator(parentchrom, M, dim, Pc,
Pm, D, q, ET, T, LT, ST ,qmax,speed,fitmax,ck,a,b,tbh);
% 子代个体和父代个体融合
Nc = size(chrom,1);
Nn = size(newchrom,1);
allchrom(1:Nc,:) = chrom;
allchrom(Nc + 1 : Nc + Nn,1 : M+dim) =
newchrom;
% 融合种群非支配排序
allchrom = nonDominatedSort(allchrom, M,
dim);
chrom = replace_chromosome(allchrom, M, dim,
NP);
plot( chrom(:,dim + 1) ,-chrom(:,dim +
2),'b*');
str = sprintf('多目标遗传算法帕累托求解第%d次迭代',gen);
title(str)
xlabel('成本');
ylabel('满意度');
pause(0.005)
hold off
end
%% 结果输出
clc
gbest = chrom(:,1:dim+M);
gbest(:,end) = -gbest(:,end);
gbest = unique(gbest,'rows');
[fg,Id] = sort(gbest(:,dim+1));
gbest = gbest(Id,:);
fgbest = gbest(:,dim+1:dim+M);
gbest = gbest(:,1:dim);
G = size(gbest,1);
fprintf('帕累托最优解数目为 %d ',G)
