Matlab 三维装箱遗传算法实现

就基本的遗传算法思路，原理参考这一篇：二维装箱以及扩展到三维装箱问题的基于遗传算法代码实现_小陳参上的博客-CSDN博客_装箱问题遗传算法

代码结构为：

Genetic主函数：getPermut函数——Product函数——edge变换长宽高函数、Combination结合函数、aberrance变异函数、Select选择函数

plotPermute函数——plotPackage函数

Main主函数：

% 使用遗传算法得到最大装载方式
%　定义初始种群为100个
%  交叉方式为两两交叉组合，分裂概率为0.7
%  变异方式为随机变异，变异概率为0.3
%  然后进行选择 选择前面最优的100个rateCom=0.7;%结合概率
rateAbe=0.3;%变异概率
populations=10;%种群大小
Maxtime=10;%最大迭代时间
BigSet=[1,1,1,100;2,2,2,100];% 表示可用箱子，前三个属性表示箱子三维尺寸，第四个属性为箱子数量
xscale=10;
yscale=10;
zscale=10;%箱子尺寸限制%----使用遗传算法-----%
%xscale 表示容器x长度
%yscale 表示容器y长度
%zscale 表示容器z长度
%SolutionPosition 物体摆放点（左前下角）
%SolutionQ 物体摆放种类
%SolutionD 物体摆放方向
%SolutionV 物体体积
[SolutionQ,SolutionD,SolutionPosition,SolutionV]...=Genetic(rateCom,rateAbe,populations,BigSet,xscale,yscale,zscale,Maxtime);%根据得到的位置序列，对应的物体种类、物体方向进行绘图
plotPermute(SolutionPosition,SolutionQ,SolutionD,BigSet);

Genetic函数：

%物体排序序列Q（queue）,先确定Q长度的上限，例如5462527415242831324231425465...
%物体方向序列D（direction），由6进制序列组合 13243546242315253645...
%适应度函数Fit,使用V容积来进行判断，越大越优。
%结束条件为没有可用点序列
%　定义初始种群为100个
%  交叉方式为单点交叉组合，分裂概率为0.7
%  变异方式为随机点变异，变异概率为0.3
%  然后进行选择 选择前面最优的100个% 初始迭代次数t=0 最高迭代次数t_max=10000%BigSet，表示初始可用箱子，前三项对于x,y,z物体尺寸，第四项对应数量function[solutionQ,solutionD,solutionPosition,solutionV]...=Genetic(rate1,rate2,populations,BigSet,...xscale,yscale,zscale,Maxtime)% rate1百分数 预设定为2的倍数
% Maxtime为最大运行次数
% BigSet 表示每种类型的箱子与对应的尺寸，与数量信息，例如:%3、4、5、6表示长度为3，宽度为4，高度为5，有6个
% populations为种群数量%---预处理过程------%BigSet(:,5)=BigSet(:,1).*BigSet(:,2).*BigSet(:,3);%---确定最小体积----M=min(BigSet(:,5));%---确定序列长度----Qsize=floor(xscale*yscale*zscale/M);Q=[];D=[];%--初始化Q,D----BoxPermu=[];for g=1:size(BigSet,1)if BigSet(g,4)==0break;endBoxPermu=[BoxPermu,ones( 1,BigSet(g,4) ).*g];end%生成一个全体物体集，便于下一步随机选出tempBoxPerms=[];%临时箱子排序for q=1:10*populationstempBoxPerms=[tempBoxPerms;BoxPermu( randperm(length(BoxPermu)) )];endBoxPermu=tempBoxPerms;%得到具有行数为10倍人口的箱子序列表for k=1:2*populationsQ(k,:)=BoxPermu(floor(rand().*size(BoxPermu,1))+1,:); %从上述箱子序列表挑出2倍人口的箱子序列Q%-----总共有六个方向，得到方向序列----D(k,1:size(Q(k,:),2))=floor(rand(1, size(Q(k,:),2) ).*6)+1;%顺便得到方向序列Dend%----开始填充---position=[];BoxNum=[];    V=[];for i=1:2*populations% 对于每一条序列，使用getPermut函数计算对应的位置序列position，箱子数量系列BoxNum（因为输入序列Q肯定是过多的），体积序列V%[position(i),BoxNum(i),V(i)][position1,BoxNum(i),V(i)]=getPermut(Q(i,:),D(i,:),...xscale,yscale,zscale,BigSet);position(i,1:BoxNum(i),1:3)=position1; %砍掉后面塞不进去的end%---进行第一次选择，从2倍人口选出最优的1倍人口的序列们----[Q,D,position,BoxNum,V]=Select(Q,D,position,BoxNum,V,populations);    %----主代码-----for time=1:Maxtime%---交叉----[Q,D]=Combination(Q,D,BoxNum,populations,rate1);%---变异----[Q,D]=aberrance(Q,D,populations,rate1,rate2,BoxNum,BigSet);%---填充----position=[];BoxNum=[];    V=[];for i=1:2*populations%要修改position1=[];[position1,BoxNum(i),V(i)]=getPermut(Q(i,:),D(i,:),...xscale,yscale,zscale,BigSet);position(i,1:BoxNum(i),1:3)=position1;          end%---选择----[Q,D,position,BoxNum,V]=Select(Q,D,position,BoxNum,V,populations); timeend[~,theindex]=max(V(:));solutionQ=Q(theindex,1:BoxNum(theindex));solutionD=D(theindex,1:BoxNum(theindex));solutionV=V(theindex);solutionPosition=position(theindex,:,:);solutionPosition=reshape(solutionPosition,size(solutionPosition,2),3);solutionPosition(solutionPosition(:,1)+solutionPosition(:,2)+solutionPosition(:,3)==0,:)=[];solutionPosition=[[0,0,0];solutionPosition];end

getPermut函数：

% getPermut函数
%----根据种类序列和方向序列建立起摆放点序列Position，数量（即这条序列塞了多少箱子）序列i，体积序列V%Q(Queue 表示物体序列),单条
%D(Direction 表示方向序列)，单条
%xscale,yscale,zscale表示箱子尺寸
%BigSet包含中元素为立方体
function [Position,i,V]=getPermut(Q,D,xscale,yscale,zscale,BigSet)Position=[];%用于存放位置点，此处初始化PointSet=[0,0,0];%用于存放可行点，此处初始化for i=1:size(Q,2) %i为索引if Q(i)==0   %由于矩阵的限制，后面会有很多的0i=i-1;break;end%填装第i个立方体,从可用点集合出发%PointInfm 有两个参数，第一个表示新的可用点集合，第二个表示基于原来第几个可用点延伸[PointInfom,index]=product(           Q(i),D(i),PointSet,xscale,yscale,zscale,BigSet);该条表示的是，第Q(i)个箱子开始尝试从当前的可行点集合PointSet放入到容器中%------------删除点-----------------if index>size(PointSet,1) % 结束状态，没有可用点填充，PointTempSet=[]; 此时得到的i即为最大容纳 数量   i=i-1;break;else PointInfom( (PointInfom(:,1)+PointInfom(:,2)...+PointInfom(:,3))==0,:)=[]; %把无效的可用点坐标即原点删去%-----完成结尾拼接，删除工作-----------if index

% product 填装立方体
% Q为种类,单个
% D为方向，单个
% intialPoints为初始点集合，对于每一个箱子，进行摆放的尝试，每次成功摆放一个箱子，
%                                                   就会产生3个可用点function [point,i]=product(Q,D,intialPoints,xscale,yscale,zscale,BigSet)i=1;point(1,1:3)=[0,0,0];point(2,1:3)=[0,0,0];point(3,1:3)=[0,0,0];%点的初始化M1=min(BigSet(:,1));M2=min(BigSet(:,2));M3=min(BigSet(:,3));boxsizeMin=min([M1,M2,M3] );%箱子尺寸大小的最小限制while i<=size(intialPoints,1)%对于每一个可用点序列都进行遍历,i表示选择了第几个点进行填装E=edge(Q,D,BigSet);%通过自定义的edge函数，给定种类Q和方向D得到方向变换之后的x,y,zif (yscale-intialPoints(i,2))>=E(2)...&&(xscale-intialPoints(i,1))>=E(1)... &&(zscale-intialPoints(i,3))>=E(3) point(1,1:3)=[intialPoints(i,1)+E(1),intialPoints(i,2),intialPoints(i,3)];point(2,1:3)=[intialPoints(i,1),intialPoints(i,2)+E(2),intialPoints(i,3)];point(3,1:3)=    [intialPoints(i,1),intialPoints(i,2),intialPoints(i,3)+E(3)];%-------对这些点进行检验-------         if xscale-point(1,1)

% 立方体边长函数
% -------对于给定的物体类型（单个）与方向（单个），得到变换之后的x,y,z
function length=edge(Q,D,BigSet)switch Dcase 1length(1)=BigSet(Q,1);length(2)=BigSet(Q,2);length(3)=BigSet(Q,3);case 2length(1)=BigSet(Q,2);length(2)=BigSet(Q,1);length(3)=BigSet(Q,3);case 3length(1)=BigSet(Q,3);length(2)=BigSet(Q,2);length(3)=BigSet(Q,1);case 4length(1)=BigSet(Q,2);length(2)=BigSet(Q,3);length(3)=BigSet(Q,1);case 5length(1)=BigSet(Q,3);length(2)=BigSet(Q,1);length(3)=BigSet(Q,2);case 6length(1)=BigSet(Q,1);length(2)=BigSet(Q,3);length(3)=BigSet(Q,2);end
end

%结合函数
function [Q,D]=Combination(Q,D,BoxNum,populations,rate1)male=randperm(populations);male=male(1:populations*rate1/2);% 先选出这些雄性male=male';female=[];for g=1:size(male,1) female(g)=floor(rand()*populations)+1;%选出雌性while male(g)==female(g)female(g)=floor(rand()*populations)+1;%保证两者不相同end   %----选择固定节点k,生成son1，son2k=floor(min(BoxNum(male(g)),BoxNum(female(g)))/5*3)+1;%在3/5的位置Q1=[Q(male(g),1:k),Q(  female(g), k:BoxNum(female(g)) ) ];Q2=[Q(female(g),1:k),Q(male(g),k:BoxNum(male(g)) )];%一次生两个儿子Q( populations+2*g-1 , 1:length(Q1) )=...Q1;%后代放入到populations的后面D(populations+2*g-1,1:length(Q1))=[D(male(g),1:k),...D(female(g),k:BoxNum(female(g)) )];Q(populations+2*g,1:length(Q2))=Q2;D(populations+2*g,1:length(Q2))=[D(female(g),1:k),...D(male(g),k:BoxNum(male(g)))];        end
end

%变异函数function [Q,D]=aberrance(Q,D,populations,rate1,rate2,BoxNum,BigSet)knotNum=3;aber=randperm(populations);% aberrance 变异   aber=aber(1:populations*rate2);%得到发生变异的个体count=0;for i=abercount=count+1;% i为变异名单中的个体temp=randperm( BoxNum(i) );temp=temp(1:knotNum);%选出五个变异节点tempQ=Q( i,:);Tal1=tabulate( tempQ);Tal1(Tal1(:,1)==0,:)=[];Tal1=Tal1(:,1:2);%统计已经使用过的箱子for r=temp %r表示变异节点Tal1( tempQ(r),2)=Tal1( tempQ(r),2)-1;%取消对它们的使用%第一次用CSDN发布，发现这个Tal1也太像Tall了，是table 1的含义endTable=BigSet(:,4);%提取初始可用表for m=Tal1(:,1)Table(m)=Table(m)-Tal1(m,2);%获取变异可用表end%----从变异可用表中，获取五个物体Permuta=[];for b=1:size(Table,1) if Table(b)==0continue;endPermuta=[Permuta, ones(1,Table(b)).*b ];endPermutaIndex=randperm(length(Permuta));%先获得关于索引的随机排列PermutaIndex=PermutaIndex( 1: length(temp) );Permuta=Permuta(PermutaIndex);%将得到的五个可用变异值再赋值回temp        for r=1:length(temp)    tempQ( temp(r) )=Permuta(r);end%将变异过的tempD放到后面   Q(populations+populations*rate1+count,:)=tempQ;%对应的方向序列进行修改D(populations+populations*rate1+count,:)=D(i);for r=tempD(populations+populations*rate1+count,r)=floor(rand()*6)+1;endend
end

function [Q,D,position,BoxNum,V]=Select(Q,D,position,BoxNum,V,populations)    %选择函数V=V';BoxNum=BoxNum';for i=1:size(V,1)V(i,2)=i;endV=sort(V);V=V(1:populations,:);position=position(V(:,2),:,:);BoxNum=BoxNum(V(:,2),:);D=D( V(:,2),:);Q=Q( V(:,2),:);   V(:,2)=[];V=V';BoxNum=BoxNum';
end

%绘画图形，Position 为矩阵，每一行代表一个箱子，Q为序列，D为序列 function []=plotPermute(Position,Q,D,BigSet)for i=1:size(D,2)Edge=edge(Q(i),D(i),BigSet);hold on;plotPackage(Position(i,1),Position(i,2),Position(i,3),...Edge(1),Edge(2),Edge(3))axis([0 10 0 10 0 10])end
end

function []=plotPackage(a,b,c,l,w,h)line([a,a],[b,b+w],[c,c])line([a,a],[b,b],[c,c+h])line([a,a],[b,b+w],[c+h,c+h])line([a,a],[b+w,b+w],[c,c+h])line([a,a+l],[b,b],[c,c])line([a,a+l],[b,b],[c+h,c+h])line([a,a+l],[b+w,b+w],[c,c])line([a,a+l],[b+w,b+w],[c+h,c+h])line([a+l,a+l],[b,b+w],[c,c])line([a+l,a+l],[b,b],[c,c+h])line([a+l,a+l],[b,b+w],[c+h,c+h])line([a+l,a+l],[b+w,b+w],[c,c+h])view(3)end

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！