m基于遗传算法的多AVG调度和货架存取货路线优化系统matlab仿真

简介: m基于遗传算法的多AVG调度和货架存取货路线优化系统matlab仿真

1.算法描述

   遗传算法GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色体”群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解。

一、遗传算法的目的

    典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题:考虑对于一群长度为L的二进制编码bi,i=1,2,…,n;有

bi{0,1}L (3-84)

给定目标函数f,有f(bi),并且

0

同时f(bi)≠f(bi+1)求满足下式

max{f(bi)|bi{0,1}L}

的bi。很明显,遗传算法是一种最优化方法,它通过进化和遗传机理,从给出的原始解群中,不断进化产生新的解,最后收敛到一个特定的串bi处,即求出最优解。

二、遗传算法的基本原理

    长度为L的n个二进制串bi(i=1,2,…,n)组成了遗传算法的初解群,也称为初始群体。在每个串中,每个二进制位就是个体染色体的基因。根据进化术语,对群体执行的操作有三种:

1.选择(Selection)

   这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时,是根据个体对环境的适应度而决定其繁殖量的,故而有时也称为非均匀再生(differential reproduction)。

2.交叉(Crossover)

   这是在选中用于繁殖下一代的个体中,对两个不同的个体的相同位置的基因进行交换,从而产生新的个体。

3.变异(Mutation)

   这是在选中的个体中,对个体中的某些基因执行异向转化。在串bi中,如果某位基因为1,产生变异时就是把它变成0;反亦反之。

遗传算法的原理可以简要给出如下:

choose an intial population

determine the fitness of each individual

perform selection

repeat

perform crossover

perform mutation

determine the fitness of each individual

perform selection

until some stopping criterion applies

    这里所指的某种结束准则一般是指个体的适应度达到给定的阀值;或者个体的适应度的变化率为零。

三、遗传算法的步骤和意义
1.初始化

选择一个群体,即选择一个串或个体的集合bi,i=1,2,...n。这个初始的群体也就是问题假设解的集合。一般取n=30-160。

通常以随机方法产生串或个体的集合bi,i=1,2,...n。问题的最优解将通过这些初始假设解进化而求出。

2.选择

根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。

给出目标函数f,则f(bi)称为个体bi的适应度。以

为选中bi为下一代个体的次数。

显然.从式(3—86)可知:

(1)适应度较高的个体,繁殖下一代的数目较多。

(2)适应度较小的个体,繁殖下一代的数目较少;甚至被淘汰。

这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。

3.交叉

对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。

例如有个体

S1=100101

S2=010111

选择它们的左边3位进行交叉操作,则有

S1=010101

S2=100111

一般而言,交 婊显譖。取值为0.25—0.75。

4.变异

根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。变异概率Pm与生物变异极小的情况一致,所以,Pm的取值较小,一般取0.01-0.2。

例如有个体S=101011。

对其的第1,4位置的基因进行变异,则有

S'=001111

   单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。
  目标函数可以表示为:

1.png

   通过优化算法处理之后,得到某个AVGj,搬运了Pj个货物,每个货物的搬运长度为Lj,那么中的路线长度,即对应我们的优化目标函数。 

2.仿真效果预览
matlab2022a仿真结果如下:

2.png
3.png
4.png
5.png
6.png
7.png

3.MATLAB核心程序

Index= [9,5,19,12,13,14,17,21,63,64,75,97];%12个目标
Xpos = (X(Index));
Ypos = (Y(Index));
 
for i = 1:length(Xpos)
    idx = find(Xeach==Xpos(i));
    if mod(idx,2)==0;
       Xpos(i) = Xpos(i)+W4+W1/2;
    else
       Xpos(i) = Xpos(i)-W1/2;
    end
end
 
 
 
 
figure;
for i = 1:length(X)
    tmps = find(Index==i);
    
    if isempty(tmps)==1
       rectangle('Position', [[X(i)-W4/2,Y(i)-W4/2] W4 W4], 'LineWidth', 1, 'EdgeColor', 'b', 'Clipping', 'off');
       hold on
    else
       rectangle('Position', [[X(i)-W4/2,Y(i)-W4/2] W4 W4], 'LineWidth', 1, 'EdgeColor', 'r', 'Clipping', 'off');
       hold on
       text(X(i)+1,Y(i)+1,num2str(i));
    end
end
plot(Starts(1),Starts(2),'--gs',...
    'LineWidth',2,...
    'MarkerSize',10,...
    'MarkerEdgeColor','b',...
    'MarkerFaceColor',[0.5,0.5,0.5]);
hold on
text(Starts(1)+1,Starts(2)+1,'START');
 
plot(ends(1),ends(2),'--ys',...
    'LineWidth',2,...
    'MarkerSize',10,...
    'MarkerEdgeColor','r',...
    'MarkerFaceColor',[0.5,0.5,0.5]);
 
text(ends(1)+1,ends(2)+1,'END');
title('红色为需要搬运的货物位置');
 
 
MAXGEN = 50;
NIND   = 200;
Nums   = length(Index)+Nagv+1; %优化变量数量,含义为N个货物的路线优化变量+每个agv的搬运数量变量+冲突策略判断
Chrom  = crtbp(NIND,Nums*10);
 
%sh
Areas = [];
for i = 1:length(Index)
    Areas = [Areas,[1;length(Index)-i+1]];
end
for i = 1:Nagv
    Areas = [Areas,[1;length(Index)-Nagv+1]];%每个agv最多搬运N-agv+1个,保证其他的至少可以搬运1个
end
for i = 1:1
    Areas = [Areas,[1;2]];%策略4选1
end
 
FieldD = [rep([10],[1,Nums]);Areas;rep([0;0;0;0],[1,Nums])];
 
gen   = 0;
 
%计算对应的目标值
A = floor(length(Index)*rand(1,Nagv))+1; 
S = sum(A); 
B = round(A*length(Index)/S);
if sum(B)>length(Index)
 [Vbb,Ibb]= max(B);
 B(Ibb) = B(Ibb)-(sum(B)-length(Index));
end
if sum(B)<length(Index)
 [Vbb,Ibb]= min(B);
 B(Ibb) = B(Ibb)+(length(Index)-sum(B));
end  
Xxx          = [1:length(Index),B,1];%初始值
fobj         = func_obj(Xxx);
E            = fobj;
Js           = E*ones(NIND,1);
Objv         = (Js+eps);
gen          = 0; 
 
%%
while gen < MAXGEN;   
      gen
      Pe0 = 0.9999;
      pe1 = 0.0001; 
 
      FitnV=ranking(Objv);    
      Selch=select('sus',Chrom,FitnV);    
      Selch=recombin('xovsp', Selch,Pe0);   
      Selch=mut( Selch,pe1);   
      phen1=bs2rv(Selch,FieldD);   
 
      for a=1:1:NIND  
          AA   = round(phen1(a,1:length(Index)));
          AA2  = [];
          Index_=Index;
          for i = 1:length(AA)
              AA2(i)=Index_(AA(i));
              Index_(AA(i))=[];
          end
          BB   = floor(phen1(a,1+length(Index):end-1))+1;
          S    = sum(BB); 
          BB2  = round(BB*length(Index)/S);
          if sum(BB2)>length(Index)
             [Vbb,Ibb]= max(BB2);
             BB2(Ibb) = BB2(Ibb)-(sum(BB2)-length(Index));
          end
          if sum(BB2)<length(Index)
             [Vbb,Ibb]= min(BB2);
             BB2(Ibb) = BB2(Ibb)+(length(Index)-sum(BB2));
          end   
          CC2  = round(phen1(a,end));
          
          X1   = [AA2,BB2,CC2];
 
          %计算对应的目标值
          [fobj,pathall] = func_obj(X1);
          E              = fobj;
          JJ(a,1)        = E;
          XX{a}          = X1;
          pathallX{a}    = pathall;
      end 
      
      Objvsel=(JJ);    
      [Chrom,Objv]=reins(Chrom,Selch,1,1,Objv,Objvsel);   
      gen=gen+1; 
      %保存参数收敛过程和误差收敛过程以及函数值拟合结论
      Error(gen) = mean(JJ);
end 
clc;
figure;
plot(Error,'linewidth',2);
grid on
xlabel('迭代次数');
ylabel('遗传算法优化过程');
 
 
 
[V,I]=min(JJ);
 
XX_best      = XX{I};
pathall_best = pathallX{I};
 
 
idxx = XX_best(1:length(Index));
Nums = XX_best(1+length(Index):end-1);
 
 
Color{1}='r';
Color{2}='k';
Color{3}='g';
Color{4}='y';
Color{5}='m';
Color{6}='c';
 
 
%显示每个agv搬运的货物编号
S1=0;
E1=0;
for j = 1:length(Nums)
    if j == 1
       S1=E1+1;
       E1=S1+Nums(j)-1;
       sel{j}=idxx(S1:E1); 
    else 
       S1=E1+1;
       E1=S1+Nums(j)-1;
       sel{j}=idxx(S1:E1); 
    end
    sel{j}
end
 
 
 
 
idxx = (1:length(Index));
Nums = XX_best(1+length(Index):end);
figure;
for i = 1:length(X)
rectangle('Position', [[X(i)-W4/2,Y(i)-W4/2] W4 W4], 'LineWidth', 1, 'EdgeColor', 'b', 'Clipping', 'off');
hold on
end
for j = 1:length(sel)
    tmps = sel{j};
    for jj = 1:length(tmps)
        rectangle('Position', [[X(tmps(jj))-W4/2,Y(tmps(jj))-W4/2] W4 W4], 'LineWidth', 1, 'EdgeColor', Color{j}, 'Clipping', 'off');
        hold on
        text(X(tmps(jj))+1,Y(tmps(jj))+1,num2str(tmps(jj)));
    end
end
 
 
plot(Starts(1),Starts(2),'--gs',...
    'LineWidth',2,...
    'MarkerSize',10,...
    'MarkerEdgeColor','b',...
    'MarkerFaceColor',[0.5,0.5,0.5]);
hold on
text(Starts(1)+1,Starts(2)+1,'START');
 
plot(ends(1),ends(2),'--ys',...
    'LineWidth',2,...
    'MarkerSize',10,...
    'MarkerEdgeColor','r',...
    'MarkerFaceColor',[0.5,0.5,0.5]);
 
text(ends(1)+1,ends(2)+1,'END');
title('相同颜色为一个agv搬运');
02_068m
相关文章
|
6天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-GRU网络的数据分类识别算法matlab仿真
本项目展示了使用MATLAB2022a实现的贝叶斯优化、CNN和GRU算法优化效果。优化前后对比显著,完整代码附带中文注释及操作视频。贝叶斯优化适用于黑盒函数,CNN用于时间序列特征提取,GRU改进了RNN的长序列处理能力。
|
13天前
|
存储 关系型数据库 分布式数据库
PolarDB的PolarStore存储引擎以其高效的索引结构、优化的数据压缩算法、出色的事务处理能力著称
PolarDB的PolarStore存储引擎以其高效的索引结构、优化的数据压缩算法、出色的事务处理能力著称。本文深入解析PolarStore的内部机制及优化策略,包括合理调整索引、优化数据分布、控制事务规模等,旨在最大化其性能优势,提升数据存储与访问效率。
22 5
|
4月前
|
安全
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
本文介绍了2023年高教社杯数学建模竞赛D题的圈养湖羊空间利用率问题,包括问题分析、数学模型建立和MATLAB代码实现,旨在优化养殖场的生产计划和空间利用效率。
208 6
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
|
4月前
|
存储 算法 搜索推荐
【2022年华为杯数学建模】B题 方形件组批优化问题 方案及MATLAB代码实现
本文提供了2022年华为杯数学建模竞赛B题的详细方案和MATLAB代码实现,包括方形件组批优化问题和排样优化问题,以及相关数学模型的建立和求解方法。
133 3
【2022年华为杯数学建模】B题 方形件组批优化问题 方案及MATLAB代码实现
|
4月前
|
数据采集 存储 移动开发
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
本文介绍了2023年五一杯数学建模竞赛B题的解题方法,详细阐述了如何通过数学建模和MATLAB编程来分析快递需求、预测运输数量、优化运输成本,并估计固定和非固定需求,提供了完整的建模方案和代码实现。
95 0
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
|
7月前
|
数据安全/隐私保护
耐震时程曲线,matlab代码,自定义反应谱与地震波,优化源代码,地震波耐震时程曲线
地震波格式转换、时程转换、峰值调整、规范反应谱、计算反应谱、计算持时、生成人工波、时频域转换、数据滤波、基线校正、Arias截波、傅里叶变换、耐震时程曲线、脉冲波合成与提取、三联反应谱、地震动参数、延性反应谱、地震波缩尺、功率谱密度
基于混合整数规划的微网储能电池容量规划(matlab代码)
基于混合整数规划的微网储能电池容量规划(matlab代码)
|
7月前
|
算法 调度
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
含多微网租赁共享储能的配电网博弈优化调度(含matlab代码)
|
7月前
|
Serverless
基于Logistic函数的负荷需求响应(matlab代码)
基于Logistic函数的负荷需求响应(matlab代码)