[原创]车间作业调度问题遗传算法Matlab源码

aiwa · 发表于 2007-3-20 07:40:41

——更多原创程序，请访问GreenSim团队的主页→<a href="http://blog.sina.com.cn/greensim" target="_blank">http://blog.sina.com.cn/greensim</a>function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- %  JSPGA.m %  车间作业调度问题遗传算法 %-------------------------------------------------------------------------- %  输入参数列表 %  M       遗传进化迭代次数 %  N       种群规模(取偶数) %  Pm      变异概率 %  T       m×n的矩阵，存储m个工件n个工序的加工时间 %  P       1×n的向量，n个工序中，每一个工序所具有的机床数目 %  输出参数列表 %  Zp      最优的Makespan值 %  Y1p     最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 %  Y2p     最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 %  Y3p     最优方案中，各工件各工序使用的机器编号 %  Xp      最优决策变量的值，决策变量是一个实数编码的m×n矩阵 %  LC1     收敛曲线1，各代最优个体适应值的记录 %  LC2     收敛曲线2，各代群体平均适应值的记录 %  最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图）%第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2%第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N     X=zeros(m,n);     for j=1:n         for i=1:m             X(i,j)=1+(P(j)-eps)*rand;         end     end     farm{k}=X; endcounter=0;%设置迭代计数器 while counter         %第三步：交叉     newfarm=cell(1,N);%交叉产生的新种群存在其中     Ser=randperm(N);     for i=1:2

N-1)         A=farm{Ser(i)};%父代个体         B=farm{Ser(i+1)};         Manner=unidrnd(2);%随机选择交叉方式         if Manner==1             cp=unidrnd(m-1);%随机选择交叉点             %双亲双子单点交叉             a=[A(1:cp,

;B((cp+1):m,

];%子代个体             b=[B(1:cp,

;A((cp+1):m,:)];         else             cp=unidrnd(n-1);%随机选择交叉点             a=[A(:,1:cp),B(:,(cp+1):n)];%双亲双子单点交叉             b=[B(:,1:cp),A(:,(cp+1):n)];         end         newfarm{i}=a;%交叉后的子代存入newfarm         newfarm{i+1}=b;     end     %新旧种群合并     FARM=[farm,newfarm];         %第四步：选择复制     FITNESS=zeros(1,2*N);     fitness=zeros(1,N);     plotif=0;     for i=1

2*N)         X=FARM{i};         Z=COST(X,T,P,plotif);%调用计算费用的子函数         FITNESS(i)=Z;     end     %选择复制采取两两随机配对竞争的方式，具有保留最优个体的能力     Ser=randperm(2*N);     for i=1:N         f1=FITNESS(Ser(2*i-1));         f2=FITNESS(Ser(2*i));         if f1<=f2             farm{i}=FARM{Ser(2*i-1)};             fitness(i)=FITNESS(Ser(2*i-1));         else             farm{i}=FARM{Ser(2*i)};             fitness(i)=FITNESS(Ser(2*i));         end     end     %记录最佳个体和收敛曲线     minfitness=min(fitness)     meanfitness=mean(fitness)     LC1(counter+1)=minfitness;%收敛曲线1，各代最优个体适应值的记录     LC2(counter+1)=meanfitness;%收敛曲线2，各代群体平均适应值的记录     pos=find(fitness==minfitness);     Xp=farm{pos(1)};         %第五步：变异     for i=1:N         if Pm>rand;%变异概率为Pm             X=farm{i};             I=unidrnd(m);             J=unidrnd(n);             X(I,J)=1+(P(J)-eps)*rand;             farm{i}=X;         end     end     farm{pos(1)}=Xp;         counter=counter+1 end%输出结果并绘图 figure(1); plotif=1; X=Xp; [Zp,Y1p,Y2p,Y3p]=COST(X,T,P,plotif); figure(2); plot(LC1); figure(3); plot(LC2); 【GreenSim团队简介】——更多原创程序，请访问GreenSim团队的主页→<a href="http://blog.sina.com.cn/greensim" target="_blank">http://blog.sina.com.cn/greensim</a>     GreenSim团队长期从事建模仿真、算法设计、代写程序等业务，为您提供实验、课题、论文、项目等方面的仿真服务。     GreenSim团队擅长的学科领域主要有 【智能算法】遗传算法、模拟退火、神经网络、蚁群算法、免疫优化、支持向量机、拟物拟人 【运筹优化】数学建模、数值优化算法、大规模/非线性问题、组合优化、NP完全问题 【信息与通信】无线通信、信号处理、计算机网络 【其它学科】任何问题，只要能归结为数学问题或者算法仿真，我们都有实力和信心解决     GreenSim团队的联系方式： QQ: 330264704，535115369  Email：<a href="mailto:greensim@163.com" target="_blank">greensim@163.com</a>（来信必复）

[此贴子已经被作者于2007-3-23 12:30:16编辑过]

aiwa · 发表于 2007-3-20 07:41:05

function [Zp,Y1p,Y2p,Y3p]=COST(X,T,P,plotif) %  JSPGA的内联子函数，用于求调度方案的Makespan值 %  输入参数列表 %  X       调度方案的编码矩阵，是一个实数编码的m×n矩阵 %  T       m×n的矩阵，存储m个工件n个工序的加工时间 %  P       1×n的向量，n个工序中，每一个工序所具有的机床数目 %  plotif  是否绘甘特图的控制参数 %  输出参数列表 %  Zp      最优的Makespan值 %  Y1p     最优方案中，各工件各工序的开始时刻 %  Y2p     最优方案中，各工件各工序的结束时刻 %  Y3p     最优方案中，各工件各工序使用的机器编号%第一步：变量初始化 [m,n]=size(X); Y1p=zeros(m,n); Y2p=zeros(m,n); Y3p=zeros(m,n);%第二步：计算第一道工序的安排 Q1=zeros(m,1); Q2=zeros(m,1); R=X(:,1);%取出第一道工序 Q3=floor(R);%向下取整即得到各工件在第一道工序使用的机器的编号 %下面计算各工件第一道工序的开始时刻和结束时刻 for i=1

(1)%取出机器编号     pos=find(Q3==i);%取出使用编号为i的机器为其加工的工件的编号     lenpos=length(pos);     if lenpos>=1         Q1(pos(1))=0;         Q2(pos(1))=T(pos(1),1);         if lenpos>=2             for j=2:lenpos                 Q1(pos(j))=Q2(pos(j-1));                 Q2(pos(j))=Q2(pos(j-1))+T(pos(j),1);             end         end     end end Y1p(:,1)=Q1; Y2p(:,1)=Q2; Y3p(:,1)=Q3;%第三步：计算剩余工序的安排 for k=2:n     R=X(:,k);%取出第k道工序     Q3=floor(R);%向下取整即得到各工件在第k道工序使用的机器的编号     %下面计算各工件第k道工序的开始时刻和结束时刻     for i=1

(k)%取出机器编号         pos=find(Q3==i);%取出使用编号为i的机器为其加工的工件的编号         lenpos=length(pos);         if lenpos>=1             POS=zeros(1,lenpos);%上一个工序完成时间由早到晚的排序             for jj=1:lenpos                 MinEndTime=min(EndTime);                 ppp=find(EndTime==MinEndTime);                 POS(jj)=ppp(1);                 EndTime(ppp(1))=Inf;             end                        %根据上一个工序完成时刻的早晚，计算各工件第k道工序的开始时刻和结束时刻                         if lenpos>=2                 for j=2:lenpos                     Q1(pos(POS(j)))=Y2p(pos(POS(j)),k-1);%预定的开始时刻为上一个工序的结束时刻                     if Q1(pos(POS(j)))                         Q1(pos(POS(j)))=Q2(pos(POS(j-1)));                     end                 end             end         end     end     Y1p(:,k)=Q1;     Y2p(:,k)=Q2;     Y3p(:,k)=Q3; end%第四步：计算最优的Makespan值 Y2m=Y2p(:,n); Zp=max(Y2m);%第五步：绘甘特图 if plotif     for i=1:m         for j=1:n             mPoint1=Y1p(i,j);             mPoint2=Y2p(i,j);             mText=m+1-i;             PlotRec(mPoint1,mPoint2,mText);             Word=num2str(Y3p(i,j));             %text(0.5*mPoint1+0.5*mPoint2,mText-0.5,Word);             hold on             x1=mPoint1;y1=mText-1;             x2=mPoint2;y2=mText-1;             x3=mPoint2;y3=mText;             x4=mPoint1;y4=mText;             %fill([x1,x2,x3,x4],[y1,y2,y3,y4],'r');             fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,0.5,1]);             text(0.5*mPoint1+0.5*mPoint2,mText-0.5,Word);         end     end end function PlotRec(mPoint1,mPoint2,mText) %  此函数画出小矩形 %  输入: %  mPoint1    输入点1,较小,横坐标 %  mPoint2    输入点2,较大,横坐标 %  mText      输入的文本,序号,纵坐标 vPoint = zeros(4,2) ; vPoint(1,

= [mPoint1,mText-1]; vPoint(2,

= [mPoint2,mText-1]; vPoint(3,

= [mPoint1,mText]; vPoint(4,:) = [mPoint2,mText]; plot([vPoint(1,1),vPoint(2,1)],[vPoint(1,2),vPoint(2,2)]); hold on ; plot([vPoint(1,1),vPoint(3,1)],[vPoint(1,2),vPoint(3,2)]); plot([vPoint(2,1),vPoint(4,1)],[vPoint(2,2),vPoint(4,2)]); plot([vPoint(3,1),vPoint(4,1)],[vPoint(3,2),vPoint(4,2)]);【GreenSim团队简介】——更多原创程序，请访问GreenSim团队的主页→<a href="http://blog.sina.com.cn/greensim" target="_blank">http://blog.sina.com.cn/greensim</a>     GreenSim团队长期从事建模仿真、算法设计、代写程序等业务，为您提供实验、课题、论文、项目等方面的仿真服务。     GreenSim团队擅长的学科领域主要有 【智能算法】遗传算法、模拟退火、神经网络、蚁群算法、免疫优化、支持向量机、拟物拟人 【运筹优化】数学建模、数值优化算法、大规模/非线性问题、组合优化、NP完全问题 【信息与通信】无线通信、信号处理、计算机网络 【其它学科】任何问题，只要能归结为数学问题或者算法仿真，我们都有实力和信心解决     GreenSim团队的联系方式： QQ: 330264704，535115369  Email：<a href="mailto:greensim@163.com">greensim@163.com</a>（来信必复）

		自动登录	找回密码
密码			注-册-帐-号