一、VRP简介
遗传算法 (Genetic Algorithm, GA) 密歇根大学由美国密歇根大学组成John Holland教授首先提出的, 基于达尔文的进化论和孟德尔的遗传理论， 自适应全局优化的概率搜索算法[2]是模拟生物在自然环境中的遗传和进化过程形成的。遗传算法从一组随机种群开始， 三个遗传操作算子通过选择、杂交和变异，使目标函数向最优解进化， 使遗传算法具有其他传统方法所没有的特点。
遗传算法首先以某种形式解决问题， 编码后的解称为染色体 (个体) 。随机选择N个染色体形成初始组种， 根据预定的评价函数计算适应性， 性能好的染色体适应性高。复制适应性高的染色体， 通过遗传算子 (选择、交叉 (重组) 、变异) 产生一群更适合环境的新染色体， 形成新的种群。按照适者生存和优胜劣汰的原则，逐代演变出越来越好的近似解， 在每一代, 根据问题域中个体的适应性选择个体， 并借助自然遗传学的遗传算子进行组合交叉和变异， 产生代表新解集的种群。这一过程将导致后生代种群像自然进化一样更适合环境， 解码一代种群中种群中最好的个体， 可作为近似问题的最优解。
遗传算法流程图如图1所示： 
图1 遗传算法流程图
多配送中心的运输问题形式化描述为：产品有n个生产地S (S1, S2, …, Sn) , 有m个销售地E (e1, e2, ……, em) , 其中Sn代表N个生产地， em表示第m个销售地。n个产地产量为P (p1, p2, …pn) , m销售地点所需的销售量T (t1, t2…tm) , 运输费用为c (si, ej) 元/吨。Wr总运输费用。
物流多配送中心运输问题的数学模型如下： 其中, 式 (1) 物流多配送中心运输问题的目标函数， 表示产品总运输成本最小化；类型 (2) 和 (3) 表示约束条件， 式 (2) 生产地实际输出的产品总量不得超过其产量， 式 (3) 销售地实际获得的产品总量不得超过其需求。
xi, j=0, 1决策变量, 其描述意义如表1所示。 表1 描述决策变量的意义 本文采用基于自然数的编码方法， 因为产品的生产地S (S1, S2, …Sn) 和销售地E (e1, e2, em) 已知, 故将每一个si→ej运输产品是否为基因， 也即xi, j, 如wi, j, 则编为1, 如wi, j, 则编为0。
染色体为 (x1, 1, x1, 2, 。。。, x1, m, x2, 1, x2, 2, 。。。, x2, m, 。。。, xn, 1, xn, 2, 。。。xn, m, ) , 其中xi, j表示产地si是否出售ej运送产品, 染色体长度为n×m[5]。
染色体中基因的位置不考虑， 对染色体中基因之间的逻辑、关联等关系进行分类。例如, “x1, 1, x1, 2, 。。。, x1, m通过生产地衍生的编码， 这m个基因可以定义为行基因群；x1, 1, x2, 1。。。xn, 1, 基因是通过销售地点衍生出来的， 虽然染色体的位置不在一起， 列基因群仍然可以定义。在编码过程中，基因群对模型解的搜索有很大的帮助。
考虑到非法性和区域性的搜索， 编码过程中应注意两点：①在线规划中， 基可行解中存在最优解， 基可行解中基变量的数量为n m-1个, 染色体中基因的数量也应该是1n m-1个;②考虑到一个产地向所有销售地运输物资，一个销售地必须由所有生产地运输物资，一般不是最佳解决方案。 在搜索遗传算子的过程中， 最好出现在一行基因群全1和一列基因群全1染色体中。
数学模型的约束很复杂， 用遗传算法求解时， 只有目标函数， 因此，约束是通过惩罚来处理的， 将约束条件转化为目标函数的一部分， 确保种群中染色体的多样性， 继续搜索遗传算法。
使用以下变化将限制条件， 式 (2) 变为目标函数的一部分:
在遗传算法中， 由于物流多配送中心运输模型的目标函数为正数，因此需要非负适应函数。 为简单起见， 在这里，我们直接将目标函数的倒数作为适应函数， 即fi=1/Zi。其中fi适应染色体i， Zi约束处理后对应染色体I的目标函数值， 即染色体I对应的总运输成本 违反约束处罚值。
- 交叉算子 ①部分匹配交叉 在两个父代个体中随机选择两个交叉点， 确定匹配段， 一系列映射关系是根据选定的匹配段定义的。 交换两个父个体的匹配段， 然后对匹配段以外的其他基因位， 使用最初的父码， 相应位置的代码值根据映射关系进行交换。
②顺序交叉 两个父亲交叉时， 通过保留一个父个体的一段序列和另一个父个体的相对顺序来生成子个体。首先, 随机选择两个交叉点， 父2个交叉点中间的子序列保持不变， 父个体2从第二个交叉点开始倒序重排， 删除父个体1中现有的码值， 然后将这个排列从第二个交叉点的位置复制给父个体1， 这就产生了父个体1对应的子个体。
- 变异算子 变异算子包括倒位变异和交换变异。倒位变异是指随机选择段序列， 倒排序列中的元素， 也就是说，个体；交换变异是指在一个个体中随机选择两个， 并交换它们的位置， 即变异后的个体。
例如：染色体 (1, 0, 1, ︳0, 0, 1︳, 1, 1, 0) , 倒排中间的段序列 (1, 0, 1, ︳1, 0, 0︳, 1, 1, 0) , 这叫倒变异；对染色体而言 (0, 1, 1, 0, 1, 0, 1, 1, 0) , 交换第一个0和第二个1， 得到染色体 (1, 0, 1, 0, 1, 0, 1, 1, 0) , 是变换变异。
Step1.设置遗传算法参数， 主要有交叉率Pc, 变异率Pm和种群规模TotalPop, 算法代数Generation;
Step2:gen=0；使用自然数编码， 随机产生的个体数为TotalPop初始种群；
Step三、解码工作， 将染色体翻译成运输成本， 这里的运输成本为总运输费用 总惩罚值, 并计算各染色体的适应值；
Step4:gen=gen 1;如gen>Generation, 算法结束, 否则继续;
Step5.交叉变异， 交叉算子采用部分匹配和顺序交叉， 变异采用倒位变异和交换变异；
Step6:把第 (gen-1) 代和第gen一代染色体合并， 解码计算各自的适应值；染色体按适应值由大到小排列；
Step7:根据适应值由大到小的顺序， 从合并的数量为2*TotalPop在选择染色体之前TotalPop作为下一代父代的染色体， 转Step4;
二、部分源代码
clear; clc %W=80; %每辆车的载重 %Citynum=50; %客户数量 %Stornum=4;%仓库个数 %C %%第二三列 客户坐标，第四列 客户需求 51,52,53,54为四个仓库 %load('p01-n50-S4-w80.mat'); %载入测试数据，n客户服务点数，S仓库个数,w车辆载重量 %load('p02-n50-S4-w160.mat'); %load('p04-n100-S2-w100.mat'); %load('p05-n100-S2-w200.mat'); load('p06-n100-S3-w100.mat'); %load('p12-n80-S2-w60.mat'); % load('ppp-n30-s3-w-60.mat') %load('ppp-n25-s3-w-50.mat') w=[];%存储每代的最短总路径 G=100;%种群大小 v1=60; v2=300; [dislist,Clist]=vrp(C);%dislist为距离矩阵 ，Clist为点坐标矩阵及客户需 L=[];%存每个种群的回路长度 for i=1:G Parent(i,:)=randperm(Citynum);%随机产生路径 L(i,1)=curlist(Citynum,Clist(:,4),W,Parent(i,:),Stornum,dislist); end Pc=0.8;%交叉比率 Pm=0.3;%变异比率 species=Parent;%种群 children=[];%子代 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% disp('正在运行，时间比较长，请稍等.........') g=50; for generation=1:g %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% tic fprintf('\n正在进行第%d次迭代，共%d次..........',generation,g); Parent=species;%子代变成父代 children=[];%子代 Lp=L; %选择交叉父代 [n m]=size(Parent); %交叉，代处理 for i=1:n for j=i:n if rand<Pc crossover end end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [n m]=size(Parent); for i=1:n if rand<Pm parent=Parent(i,:);%变异个体 X=floor(rand*Citynum)+1; Y=floor(rand*Citynum)+1; Z=parent(X); parent(X)=parent(Y); parent(Y)=Z; %基因交换变异 children=[children;parent]; end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %计算子代适应值(即路径长度) (这块用时比较长) [m n]=size(children); Lc=zeros(m,1);%子代适应值 for i=1:m Lc(i,1)=curlist(Citynum,Clist(:,4),W,children(i,:),Stornum,dislist); end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %淘汰子代 剩余前G个最优解 [m n]=size(children); if(m>G) [m n]=sort(Lc); children=children(n(1:G),:); Lc=Lc(n(1:G)); end %淘汰种群 species=[children;Parent]; L=[Lc;Lp]; [m n]=sort(L); species=species(n(1:G),:); %更新世代 L=L(n(1:G)); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %加入Opt优化 %分配仓库进行opt temp=initialStor(Citynum,Clist(:,4),W,species(1,:),Stornum,dislist);%存储分配仓库后的结果【52 14 5 52 53 6 9 8 53......】 Rbest=temp; L_best=L(1); [m n]=size(temp); start=1; car=[];%存放opt优化后的结果 i=2; while (i<n+1) if (temp(i)>Citynum) cur=[]; cur=Opt(i-start,[1:i-start,1:i-start] 标签： 1000w100rj电阻