多目标遗传算法
遗传算法的优化目标一般为最小化优化,将目标(2)转化为最小化优化min -S,另外,本文建立了供应商选择问题的多目标优化模型,同时考虑成本与供应商响应能力2个优化目标,采用Pareto占优思想处理多个目标,求得多个互不占有的非劣解,每个解的侧重点不同,即得到的多个方案在2个优化目标上均存在优势。算法步骤:
Step1:输入问题数据,功能型服务供应商的相关参数,包括供应商的数目n、单位运输成本、单位增值服务成本、固定费用、运输距离、最大业务承担量等,以及服务供应的服务预期质量和服务感知质量。
Step2:设置算法参数,种群规模N、最大迭代次数Max_gen、交叉概率Pc、变异概率Pm,迭代计数器k=1。
Step3:种群初始化,物流服务供应商选择问题的解编码为0-1表示的一组排列
,若选择供应商i提供物流服务,则
,否则
;随机产生N组排列组成初始种群,但需要验证随机解满足供应商选择的最小数目以及最大业务承担量不少于需求量两个约束,若不满足上述两条约束,需要重新生成随机解。
Step4:计算初始种群的目标值,①解码操作,根据下层规划的目标函数可知,只有优先使用客户服务满意度指数高的供应商提供货物,才能保证全局客户满意度最大;因此,在分配供应商的货运量时,依次由客户服务满意度指数高的供应商提供货物,尽可能达到其最大业务承担量,初始解中某些已选择的供应商可能未分配到业务量,故需要对初始解进行修改,使得分配业务量的供应商i在初始解中的
。②根据公式(1)及修改后的初始解计算供应商的成本费用,根据公式(2)及解码操作后各供应商的业务量计算客户满意度指数。
Step5:交叉操作,随机将种群个体进行两两配对,并生成服从(0, 1)均匀分布的随机概率,若随机概率小于交叉概率Pc,则进行交叉操作,否则不执行。交叉操作的具体内容:随机生成两个交叉点,交换两个配对个体在交叉点间的元素,生成两个新解,判断新解是否满足供应商选择的最小数目以及最大业务承担量不少于需求量两个约束,若成立,则保留新解至交叉种群,否则丢弃新解。
Step6:变异操作,针对每个供应商生成服从(0, 1)均匀分布的n个随机概率,判断随机概率是否小于变异概率Pm,若成立,则改变供应商的
的取值,使用等位基因进行替换,将新解保留至变异种群。
Step7:合并种群,将初始种群、交叉种群、变异种群进行合并,计算合并种群的目标值。
Step8:筛选非劣解,计算合并种群中非劣解的支配关系,确定非劣解集Q。
Step9:更新种群,统计非劣解集Q中非劣解的数目,若小于种群规模N,则随机生成多个随机初始解进行补充,以维持新初始种群的规模,否则,随机选择N个非劣解组成新初始种群。
Step10:算法终止条件,判断k<Max_gen,若成立,则令k=k+1,转至Step5。
Step11:输出最优解,输出非劣解集Q,对非劣解进行解码操作,获得修改后的非劣解、各供应商的业务量以及对应的两个目标值。
解释
1.支配( dominate)与非劣(non- inferior在多标优化问题中,如果个体p至少有一个目标比个体q的好,而且个体p的所有目标都不比个体q的差,那么称个体p支配个体q( p dominates q),或者称个体q受个体p支配(q is dominated by p),也可以说,个体p非劣于个体q( p Is non- inferior to g)。
2.序值(rank)和前端(ront)
如果p支配q,那么p的序值比q的低。如果p和q互不支配,或者说,p和q相互非劣,那么p和q有相同的序值。序值为1的个体属于第一前端,序值为2的个体属于第二前端,依次类推。显然,在当前种群中,第一前端是完全不受支配的,第二前端受第一前端中个体的支配。这样,通过排序,可以将种群中的个体分到不同的前端。
3.拥挤距离( crowding distance)
拥挤距离用来计算某前端中的某个体与该前端中其他个体之间的距离,用以表征个体间的拥挤程度。显然,拥挤距离的值越大,个体间就越不拥挤,种群的多样性就越好。需要指出的是,只有处于同一前端的个体间才需要计算拥挤距离,不同前端之间的个体计算拥挤距离是没有意义的。
代码
clc;clear;
tic;
%% 初始化
PopSize=200;%种群大小
MaxIteration =200;%最大迭代次数
R=50;
load('cc101');
shuju=c101;
bl=0;
cap=800; %车辆最大装载量
%% 提取数据信息
E=shuju(1,5); %配送中心时间窗开始时间
L=shuju(1,6); %配送中心时间窗结束时间
zuobiao=shuju(:,2:3); %所有点的坐标x和y
% vertexs= vertexs./1000;
customer=zuobiao(2:end,:); %顾客坐标
cusnum=size(customer,1); %顾客数
v_num=6; %车辆最多使用数目
demands=shuju(2:end,4); %需求量
a=shuju(2:end,5); %顾客时间窗开始时间[a[i],b[i]]
b=shuju(2:end,6); %顾客时间窗结束时间[a[i],b[i]]
s=shuju(2:end,7); %客户点的服务时间
h=pdist(zuobiao);
% dist=load('dist1.mat');
% dist=struct2cell(dist);
% dist=cell2mat(dist);
% dist=dist./1000; %实际城市间的距离
location1=squareform(h); %距离矩阵,满足三角关系,暂用距离表示花费c[i][j]=dist[i][j]
%% 遗传算法参数设置
alpha=100000; %违反的容量约束的惩罚函数系数
belta=900;%违反时间窗约束的惩罚函数系数
belta2=60;
chesu=0.667;
N=cusnum+v_num-1; %染色体长度=顾客数目+车辆最多使用数目-1
% location1=load('location1_100.txt');%优化100个城市
% location2=load('A_location2_100.txt');
% location1=load('location1.txt');
% location2=load('location2.txt');
% CityNum =size(location1,2);%城市数
V=N;
M=2;
pc=0.8;pm=0.9;
%% 初始化种群
init_vc=init(cusnum,a,demands,cap); %构造初始解
chromosome(:,1:N)=InitPopCW(PopSize,N,cusnum,init_vc);
% for i=1:PopSize
% % chromosome(i,1:CityNum)=randperm(CityNum);
% chromosome(i,V+1:V+2)=costfunction(chromosome(i,1:V),location1,location2);
% end
chromosome(:,V+1:V+2)=calObj(chromosome,cusnum,cap,demands,a,b,L,s,location1,alpha,belta,belta2,chesu,bl); %计算种群目标函数值
%%
[chromosome,individual]= non_domination_sort_mod(chromosome,N);%将解分 最后一列为拥挤度 倒数第二列为分级数
index=find(chromosome(:,N+3)==1);
costrep=chromosome(index,N+1:N+2);%第一级即非劣解
%% 主循环
pool = round(PopSize/2); %突变池规模
for Iteration=1:MaxIteration
if ~mod(Iteration,10)
fprintf('current iter:%d\n',Iteration)
disp([' Number of Repository Particles = ' num2str(size(costrep,1))]);
end
parent_chromosome = selection_individuals(chromosome,pool,2);
parent_var=parent_chromosome(:,1:N);%分离出解向量
%% 交叉
offspring_var=[];offspring_cost=[];
for ic=1:pool/2
m1=randi(pool);%选出交叉向量
m2=randi(pool);
while m1==m2
m1=randi(pool);
end
scro(1,:)=parent_var(m1,:);
scro(2,:)=parent_var(m2,:);
if rand<pc
c1=randi(N);%选出交叉位置
c2=randi(N);
while c1==c2
c1=randi(N);
end
chb1=min(c1,c2);
chb2=max(c1,c2);
middle=scro(1,chb1+1:chb2);
scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);
scro(2,chb1+1:chb2)=middle;
for i=1:chb1
while find(scro(1,chb1+1:chb2)==scro(1,i))
zhi=find(scro(1,chb1+1:chb2)==scro(1,i));
y=scro(2,chb1+zhi);
scro(1,i)=y;
end
while find(scro(2,chb1+1:chb2)==scro(2,i))
zhi=find(scro(2,chb1+1:chb2)==scro(2,i));
y=scro(1,chb1+zhi);
scro(2,i)=y;
end
end
for i=chb2+1:N
while find(scro(1,1:chb2)==scro(1,i))
zhi=find(scro(1,1:chb2)==scro(1,i));
y=scro(2,zhi);
scro(1,i)=y;
end
while find(scro(2,1:chb2)==scro(2,i))
zhi=find(scro(2,1:chb2)==scro(2,i));
y=scro(1,zhi);
scro(2,i)=y;
end
end
end
if rand<pm%逆序变异
m1=randi(N);
m2=randi(N);
while m1==m2
m1=randi(N);
end
loc1=min(m1,m2);loc2=max(m1,m2);
scro(1,loc1:loc2)=fliplr(scro(1,loc1:loc2));
% tt=scro(1,m2);
% scro(1,m2)=scro(1,m1);
% scro(1,m1)=tt;
end
if rand<pm%对换变异
m1=randi(N);
m2=randi(N);
while m1==m2
m1=randi(N);
end
tt=scro(2,m2);
scro(2,m2)=scro(2,m1);
scro(2,m1)=tt;
end
scro_cost(1,:)=calObj(scro(1,:),cusnum,cap,demands,a,b,L,s,location1,alpha,belta,belta2,chesu,bl);
% scro_cost(1,:)=costfunction(scro(1,:),location1,location2);
scro_cost(2,:)=calObj(scro(2,:),cusnum,cap,demands,a,b,L,s,location1,alpha,belta,belta2,chesu,bl);
% scro_cost(2,:)=costfunction(scro(2,:),location1,location2);
offspring_var=[offspring_var;scro];%解
offspring_cost=[offspring_cost;scro_cost];%适应度
end
offspring_chromosome(:,1:V)=offspring_var;
offspring_chromosome(:,V+1:V+M)=offspring_cost;
main_pop = size(chromosome,1);
offspring_pop = size(offspring_chromosome,1);
intermediate_chromosome(1:main_pop,:) = chromosome;
intermediate_chromosome(main_pop + 1 :main_pop + offspring_pop,1 : M+V) = ...
offspring_chromosome;
intermediate_chromosome = ...
non_domination_sort_mod(intermediate_chromosome,N);
%% 选择
chromosome = replace_chromosome(intermediate_chromosome,PopSize,N);
index=find(intermediate_chromosome(:,N+3)==1);
costrep=intermediate_chromosome(index,N+1:N+2);
cost=intermediate_chromosome(:,N+1:N+2);
if ~mod(Iteration,1)
figure (1)
plot(costrep(:,1),costrep(:,2),'r*',cost(:,1),cost(:,2),'kx');
xlabel('F1');ylabel('F2');
title(strcat('Interaction ',num2str(Iteration), ' Pareto non-dominated solutions'));
% hold on
end
if ~mod(Iteration,MaxIteration)
% if ~mod(Iteration,1)
fun_pf=costrep;
[fun_pf,~]=sortrows(fun_pf,1);
plot(fun_pf(:,1),fun_pf(:,2),'k*-');
title(strcat('Interaction ',num2str(Iteration), ' Pareto non-dominated solutions'));
hold on;
grid on;
end
end
*************************************如需帮忙V:zhangshu2274
结果
最够可以根据自己理解,先择合适的,其中两个函数为距离和时间惩罚成本。
选择一个合适的解后,输入代码便可以得到车辆使用数目等一些内容:
如有疑问联系****zhangshu2274
更多推荐
matlab遗传算法求解带时间窗的多目标函数求解NSGA-Ⅱ(pateto)帕累托-单车厂-多车辆-各种成本的解决算法
发布评论