【原创】异构计算系统中基于遗传算法的任务分配与调度

[greensim]

异构计算系统是包含一组相异系统结构的机器连接机器的高速互连网络通信协议操作系统和相关开发环境等的集成计算系统，为了更好地利用异构计算系统的优势，可将一个大的任务分解为若干子任务，每个子任务内部包含的计算是同类性质的。而不同的子任务之间可能是不同类型的计算，需要不同系统结构的机器。任务分解完成后的工作是任务分配和任务调度，分别是将子任务分配给合适的机器，对每个机器上的子任务和机器间的数据传输进行调度。本源码由GreenSim团队原创，转载请注明，有意购买源码或代写相关程序，请与GreenSim团队联系。

function [BestX1,BestX2,BestY,AllFarm1,AllFarm2,LC1,LC2]=GSA(M,N,Pm,Pd,K,t0,alpha,TaskP,Theta,Phi)
%% 异构计算系统中的任务分配与调度问题的遗传算法通用MATLAB函数
% GreenSim团队原创作品，转载请注明
% 欢迎访问GreenSim——算法仿真团队→http://blog.sina.com.cn/greensim
%% 输入参数列表
% M------------遗传算法进化代数
% N------------种群规模，取偶数
% Pm-----------变异概率调节参数
% Pd-----------变异程度调节参数，0<Pd<1，越大，变异的基因位越多
% K------------同一温度下状态跳转次数
% t0-----------初始温度
% alpha--------降温系数
% TaskP--------任务优先矩阵，m×m矩阵，TaskPij=1表示任务i需在j之前完成，TaskPij=0时任务i和j没有优先关系
% Theta--------任务执行时间矩阵，m×n矩阵，Thetaij表示任务i在处理机j上的执行时间
% Phi----------任务之间数据传输时延矩阵，m×m矩阵，Phiij表示任务i与任务j之间的数据传输时延
%% 输出参数列表
% BestX1--------最好个体的编码的分配部分
% BestX2--------最好个体的编码的调度部分
% BestY---------最好个体的目标函数值
% LC1-----------最优个体适应值的收敛曲线，M×1
% LC2-----------种群平均适应值的收敛曲线，M×1
% AllFarm1------分配部分各代种群的集合，M×1的细胞结构
% AllFarm2------调度部分各代种群的集合，M×1的细胞结构

%% -----------------------初始化----------------------------------
[m,n]=size(Theta);
[AA,BB]=QJHJ(TaskP);%调用子函数，建立每一个任务的前任务集和后任务集
[farm1,farm2]=Initialization(N,TaskP,AA,BB,n);%调用子函数，种群初始化
%输出参数初始化
BestX1=zeros(1,m);
BestX2=zeros(1,m);
BestY=inf;
LC1=zeros(M,1);
LC2=zeros(M,1);
AllFarm1=cell(M,1);
AllFarm2=cell(M,1);
%控制参数初始化
mm=1;%迭代计数器
t=t0;%温度指示器
BestPos=1;%初始时任意指定被保护个体

%% -----------------------迭代过程---------------------------------
while mm<=M%设置停止条件
%% ----------------------变异退火算子------------------------------
for i=1:N
if rand>Pm&&i~=BestPos
%如果随机数大于变异概率门限值，并且不属于保护个体，就对其实施变异
X1=farm1(i,:);%取出该个体
X2=farm2(i,:);
k=1;
while k<=K%每一个温度下的状态转移次数
%调用变异子函数
[Y1,Y2]=Mutation(X1,X2,Pd,AA,BB,n);
%调用计算适应值子函数
%[YI,ZI,FI,TGWI,VGWI,f1I,f2I]=Fitness(I,TaskT,TaskV,RT,RV);
%[YJ,ZJ,FJ,TGWJ,VGWJ,f1J,f2J]=Fitness(J,TaskT,TaskV,RT,RV);
[St,Ft,ZB]=Fitness(Y1,Y2,TaskP,Theta,Phi);
if ZB<ZA
farm1(i,:)=Y1;
farm2(i,:)=Y2;
elseif rand<exp((ZA-ZB)/(ZA*t))
farm1(i,:)=Y1;
farm2(i,:)=Y2;
else
farm1(i,:)=X1;
end
k=k+1;
end
end
end


%% -----------------------交叉算子---------------------------------
newfarm1=zeros(size(farm1));
newfarm2=zeros(size(farm2));
Ser=randperm(N);%用这个函数保证随机配对
for i=1:2:(N-1)
FA1=farm1(Ser(i),:);
FB1=farm1(Ser(i+1),:);
FA2=farm2(Ser(i),:);
FB2=farm2(Ser(i+1),:);
[SA1,SB1,SA2,SB2]=CrossOver(FA1,FB1,FA2,FB2);
newfarm1(i+1,:)=SB1;
newfarm2(i,:)=SA2;
newfarm2(i+1,:)=SB2;
end
%新旧种群合并
FARM1=[farm1;newfarm1];
FARM2=[farm2;newfarm2];

%% -----------------------选择复制---------------------------------
FIT_Y=zeros(2*N,1);
fit_Y=zeros(N,1);
for i=1:(2*N)
X1=FARM1(i,:);
X2=FARM2(i,:);
%[Y,Z,F,TGW,VGW,f1,f2]=Fitness(XX,TaskT,TaskV,RT,RV);
[St,Ft,Y]=Fitness(X1,X2,TaskP,Theta,Phi);
FIT_Y(i)=Y;
end
Ser=randperm(2*N);
for i=1:N
ff1=FIT_Y(Ser(2*i-1));
ff2=FIT_Y(Ser(2*i));
if ff1<=ff2
farm1(i,:)=FARM1(Ser(2*i-1),:);
farm2(i,:)=FARM2(Ser(2*i-1),:);
fit_Y(i)=FIT_Y(Ser(2*i-1));
else
farm1(i,:)=FARM1(Ser(2*i),:);
farm2(i,:)=FARM2(Ser(2*i),:);
fit_Y(i)=FIT_Y(Ser(2*i));
end
end

%% -----------------------记录与更新-------------------------------
minY=min(fit_Y);
meanY=mean(fit_Y);
LC1(mm)=minY;
LC2(mm)=meanY;
pos=find(fit_Y==minY);
BestPos=pos(1);
BestX1=farm1(BestPos,:);
BestX2=farm2(BestPos,:);
BestY=fit_Y(BestPos);
AllFarm1{mm}=farm1;
AllFarm2{mm}=farm2;
disp(mm);
mm=mm+1;
t=t*alpha;
end