您所在位置：主题：[原创]车间作业调度问题遗传算法通用MATLAB源码
greensim
[专家分：0] 发布于 2009-07-26 17:22:00
车间作业调度问题是一种NP完全问题，下面的源码是车间作业调度问题的源码，算法设计细节主要参考了以下文献
谢胜利，董金祥，黄强. 基于遗传算法的车间作业调度问题求解. 计算机工程与应用. 2002
function [S_best,T_min,LC]=JSPGA(M,N,Pc,Pm,Q,W)
%% 车间作业调度问题遗传算法
% GreenSim团队原创作品，转载请注明
% GreenSim团队长期从事算法设计、代写程序等业务
% 欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url]
%% 输入参数列表
% M 遗传算法进化代数
% N 种群规模
% Pc 交叉概率
% Pm 变异概率
% Q 机器序号矩阵
% W 操作时间矩阵
%% 输出参数列表
% S_best 最优调度方案，m×1的细胞结构，每个细胞单元为La×2的矩阵
% T_min 最优调度方案对应的最短调度时间
% LC 历史最优适应值收敛曲线
%% 第一步：参数初始化
[n,k]=size(Q);%n为工件总数，k为工序总数
m=max(max(Q));%m为机器总数
S_best=cell(m,1);
T_min=inf;
LC=zeros(1,M);
%% 第二步：产生初始种群
farm=InitPop(N,Q,W,n,k,m);%调用产生初始种群的子函数
%%
counter=0;%设置迭代计数器
while counter<M%停止条件为达到最大迭代次数
%% 第三步：交叉
FARM=Cross(farm,Pc,m);%调用交叉子函数
%% 第四步：变异
FARM=Mutate(FARM,Pm,m);%调用变异子函数
%% 第五步：修正算子
FARM=Modify(FARM,Q,W,n,k);%调用修正子函数
%% 第六步：计算适应值
FITNESS=Fit(FARM);%调用计算适应值的子函数
%% 第七步：选择复制
[farm,fitness]=Select(FARM,FITNESS);%调用选择复制子函数
%% 第八步：记录和更新
[S_best,T_min,LC]=Updata(S_best,T_min,LC,farm,fitness,counter);%记录和更新子函数
counter=counter+1;
disp(counter);
end
function FARM=Cross(farm,Pc,m)
%% 子函数：交叉子函数
%% 输入参数列表
% farm 交叉操作之前的种群
% Pc 交叉概率
% Q 机器序号矩阵，n×k的矩阵
% W 操作时间矩阵，n×k的矩阵
% n 工件总数
% k 工序总数
% m 机器总数
%% 输出参数列表
% FARM 输出种群
%%
N=size(farm,2);
newfarm=cell(m,2*N);
SER=randperm(N);
A=farm(:,1);
B=farm(:,N);
pos=unidrnd(m-1);
AA=[A(1:pos,:);B((pos+1):end,:)];
BB=[B(1:pos,:);A((pos+1):end,:)];
newfarm(:,1)=AA;
newfarm(:,2)=BB;
for i=1:(N-1)
A=farm(:,SER(i));
B=farm(:,SER(i+1));
pos=unidrnd(m-1);
AA=[A(1:pos,:);B((pos+1):end,:)];
BB=[B(1:pos,:);A((pos+1):end,:)];
newfarm(:,2*i+1)=AA;
newfarm(:,2*i+2)=BB;
end
%%
for i=1:(2*N)
if Pc>rand
A=newfarm(:,i);
for j=1:m
Aj=A{j};
L=size(Aj,2);
if L>2
pos=unidrnd(L-2)+1;
Bj=[Aj(:,1),Aj(:,(pos+1):end),Aj(:,2:pos)];
A{j}=Bj;
end
end
newfarm(:,i)=A;
end
end
FARM=[farm,newfarm];
function FARM=Mutate(FARM,Pm,m)
%% 子函数：变异子函数
%% 输入参数列表
% FARM 交叉操作之后新旧种群的合并种群
% Pm 变异概率
%% 输出参数列表
% FARM 输出种群
%%
NN=size(FARM,2);
for i=1:NN
if Pm>rand
A=FARM(:,i);
for j=1:m
Aj=A{j};
L=size(Aj,2);
if L>2
pos=randperm(L-1)+1;
pos1=pos(1);
pos2=pos(2);
temp=Aj(:,pos1);
Aj(:,pos1)=Aj(:,pos2);
Aj(:,pos2)=temp;
A{j}=Aj;
end
end
FARM(:,i)=A;
end
end
欢迎访问GreenSim团队主页：http://blog.sina.com.cn/greensim
[color=red]欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url][/color]
function [S_best,T_min,LC]=Updata(S_best,T_min,LC,farm,fitness,counter)
%% 子函数：记录和更新子函数
%% 输入参数列表
% S_best 最优调度方案，m×1的细胞结构，每个细胞单元为La×2的矩阵
% T_min 最优调度方案对应的最短调度时间
% LC 历史最优适应值收敛曲线
% farm 种群
% fitness 种群的适应值
% counter 计数器
%% 输出参数列表
% S_best 最优调度方案，m×1的细胞结构，每个细胞单元为La×2的矩阵
% T_min 最优调度方案对应的最短调度时间
% LC 历史最优适应值收敛曲线
%%
minfitness=min(fitness);
pos=find(fitness==minfitness);
POS=pos(1);
if minfitness<=T_min
T_min=minfitness;
S_best=farm(:,POS);
end
LC(counter+1)=T_min;
谢胜利，董金祥，黄强. 基于遗传算法的车间作业调度问题求解. 计算机工程与应用. 2002
function [S_best,T_min,LC]=JSPGA(M,N,Pc,Pm,Q,W)
%% 车间作业调度问题遗传算法
% GreenSim团队原创作品，转载请注明
% GreenSim团队长期从事算法设计、代写程序等业务
% 欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url]
%% 输入参数列表
% M 遗传算法进化代数
% N 种群规模
% Pc 交叉概率
% Pm 变异概率
% Q 机器序号矩阵
% W 操作时间矩阵
%% 输出参数列表
% S_best 最优调度方案，m×1的细胞结构，每个细胞单元为La×2的矩阵
% T_min 最优调度方案对应的最短调度时间
% LC 历史最优适应值收敛曲线
%% 第一步：参数初始化
[n,k]=size(Q);%n为工件总数，k为工序总数
m=max(max(Q));%m为机器总数
S_best=cell(m,1);
T_min=inf;
LC=zeros(1,M);
%% 第二步：产生初始种群
farm=InitPop(N,Q,W,n,k,m);%调用产生初始种群的子函数
%%
counter=0;%设置迭代计数器
while counter<M%停止条件为达到最大迭代次数
%% 第三步：交叉
FARM=Cross(farm,Pc,m);%调用交叉子函数
%% 第四步：变异
FARM=Mutate(FARM,Pm,m);%调用变异子函数
%% 第五步：修正算子
FARM=Modify(FARM,Q,W,n,k);%调用修正子函数
%% 第六步：计算适应值
FITNESS=Fit(FARM);%调用计算适应值的子函数
%% 第七步：选择复制
[farm,fitness]=Select(FARM,FITNESS);%调用选择复制子函数
%% 第八步：记录和更新
[S_best,T_min,LC]=Updata(S_best,T_min,LC,farm,fitness,counter);%记录和更新子函数
counter=counter+1;
disp(counter);
end
function FARM=Cross(farm,Pc,m)
%% 子函数：交叉子函数
%% 输入参数列表
% farm 交叉操作之前的种群
% Pc 交叉概率
% Q 机器序号矩阵，n×k的矩阵
% W 操作时间矩阵，n×k的矩阵
% n 工件总数
% k 工序总数
% m 机器总数
%% 输出参数列表
% FARM 输出种群
%%
N=size(farm,2);
newfarm=cell(m,2*N);
SER=randperm(N);
A=farm(:,1);
B=farm(:,N);
pos=unidrnd(m-1);
AA=[A(1:pos,:);B((pos+1):end,:)];
BB=[B(1:pos,:);A((pos+1):end,:)];
newfarm(:,1)=AA;
newfarm(:,2)=BB;
for i=1:(N-1)
A=farm(:,SER(i));
B=farm(:,SER(i+1));
pos=unidrnd(m-1);
AA=[A(1:pos,:);B((pos+1):end,:)];
BB=[B(1:pos,:);A((pos+1):end,:)];
newfarm(:,2*i+1)=AA;
newfarm(:,2*i+2)=BB;
end
%%
for i=1:(2*N)
if Pc>rand
A=newfarm(:,i);
for j=1:m
Aj=A{j};
L=size(Aj,2);
if L>2
pos=unidrnd(L-2)+1;
Bj=[Aj(:,1),Aj(:,(pos+1):end),Aj(:,2:pos)];
A{j}=Bj;
end
end
newfarm(:,i)=A;
end
end
FARM=[farm,newfarm];
function FARM=Mutate(FARM,Pm,m)
%% 子函数：变异子函数
%% 输入参数列表
% FARM 交叉操作之后新旧种群的合并种群
% Pm 变异概率
%% 输出参数列表
% FARM 输出种群
%%
NN=size(FARM,2);
for i=1:NN
if Pm>rand
A=FARM(:,i);
for j=1:m
Aj=A{j};
L=size(Aj,2);
if L>2
pos=randperm(L-1)+1;
pos1=pos(1);
pos2=pos(2);
temp=Aj(:,pos1);
Aj(:,pos1)=Aj(:,pos2);
Aj(:,pos2)=temp;
A{j}=Aj;
end
end
FARM(:,i)=A;
end
end
欢迎访问GreenSim团队主页：http://blog.sina.com.cn/greensim
[color=red]欢迎访问GreenSim——算法仿真团队→[url=http://blog.sina.com.cn/greensim]http://blog.sina.com.cn/greensim[/url][/color]
function [S_best,T_min,LC]=Updata(S_best,T_min,LC,farm,fitness,counter)
%% 子函数：记录和更新子函数
%% 输入参数列表
% S_best 最优调度方案，m×1的细胞结构，每个细胞单元为La×2的矩阵
% T_min 最优调度方案对应的最短调度时间
% LC 历史最优适应值收敛曲线
% farm 种群
% fitness 种群的适应值
% counter 计数器
%% 输出参数列表
% S_best 最优调度方案，m×1的细胞结构，每个细胞单元为La×2的矩阵
% T_min 最优调度方案对应的最短调度时间
% LC 历史最优适应值收敛曲线
%%
minfitness=min(fitness);
pos=find(fitness==minfitness);
POS=pos(1);
if minfitness<=T_min
T_min=minfitness;
S_best=farm(:,POS);
end
LC(counter+1)=T_min;