|
就基本的遗传算法思路，原理参考这一篇：二维装箱以及扩展到三维装箱问题的基于遗传算法代码实现_小陳参上的博客-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)==0
break;
end
BoxPermu=[BoxPermu,ones( 1,BigSet(g,4) ).*g];
end%生成一个全体物体集，便于下一步随机选出
tempBoxPerms=[];%临时箱子排序
for q=1:10*populations
tempBoxPerms=[tempBoxPerms;BoxPermu( randperm(length(BoxPermu)) )];
end
BoxPermu=tempBoxPerms;%得到具有行数为10倍人口的箱子序列表
for k=1:2*populations
Q(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;
%顺便得到方向序列D
end
%----开始填充---
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);
time
end
[~,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 %由于矩阵的限制，后面会有很多的0
i=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<size(PointSet,1)% 可以添加
Position=[Position;PointSet(index,:)];%核心部分，可用点添加
%已经使用过点将其删除，新的序列为该点的衍生3点加上该点前面的点与后面的点
PointSet=[PointSet(1:index-1,:);
PointInfom;
PointSet(index+1:end,:)];
else %如果刚好是最后一个，直接截去再拼接
index;
size(PointSet,1);
if size(PointSet,1)~=0
Position=[Position;PointSet(index,:)]; %核心部分
PointSet=[PointSet(1:index-1,:);
PointInfom;
PointSet(index+1:end,:)];
end
end
end
PointSet=unique(PointSet,'rows');
end
V=0;
for k=1:i
if Q(k)~=0
V=V+BigSet(Q(k),5);计算该条序列（Q,D）对应体积
end
end
end
Product函数
% 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,z
if (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)<boxsizeMin
point(1,:)=[0,0,0];
end
if yscale-point(2,2)<boxsizeMin
point(2,:)=[0,0,0];
end
if zscale-point(3,3)<boxsizeMin
point(3,:)=[0,0,0]; %因此前面栈中函数需要进行筛选
end
break;
else
i=i+1;%如果该点没能放置，则进行下一个，并删除该点
end
%如果从该起始点集合都不能满足放置，则 point(1)=[0,0,0];
% point(2)=[0,0,0];
% point(3)=[0,0,0];仍然保持，并且i超出了范围
end
end
edge函数，用来得到给定方向D下的长宽高
% 立方体边长函数
% -------对于给定的物体类型（单个）与方向（单个），得到变换之后的x,y,z
function length=edge(Q,D,BigSet)
switch D
case 1
length(1)=BigSet(Q,1);
length(2)=BigSet(Q,2);
length(3)=BigSet(Q,3);
case 2
length(1)=BigSet(Q,2);
length(2)=BigSet(Q,1);
length(3)=BigSet(Q,3);
case 3
length(1)=BigSet(Q,3);
length(2)=BigSet(Q,2);
length(3)=BigSet(Q,1);
case 4
length(1)=BigSet(Q,2);
length(2)=BigSet(Q,3);
length(3)=BigSet(Q,1);
case 5
length(1)=BigSet(Q,3);
length(2)=BigSet(Q,1);
length(3)=BigSet(Q,2);
case 6
length(1)=BigSet(Q,1);
length(2)=BigSet(Q,3);
length(3)=BigSet(Q,2);
end
end
Combination函数
%结合函数
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，son2
k=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
aberrance函数
%变异函数
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=aber
count=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的含义
end
Table=BigSet(:,4);%提取初始可用表
for m=Tal1(:,1)
Table(m)=Table(m)-Tal1(m,2);%获取变异可用表
end
%----从变异可用表中，获取五个物体
Permuta=[];
for b=1:size(Table,1)
if Table(b)==0
continue;
end
Permuta=[Permuta, ones(1,Table(b)).*b ];
end
PermutaIndex=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=temp
D(populations+populations*rate1+count,r)=floor(rand()*6)+1;
end
end
end
Select函数：
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;
end
V=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
以上是Genetic函数。就是计算出迭代次数限制下的较优排序，下面是可视化部分：
plotPermute函数：
%绘画图形，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
plotPackage函数：
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
后记：当初简单跑了一下，是可以跑出来的。原本是用于2019 MCM B 的解决（当然是事后练习啦）
根据网上的CSDN其他回答的思路写的，给我自己折腾的细节还蛮多的，不想大家在这个问题上浪费太多时间，因此把它整理出来。
记得当时主要参考的是这一篇的思路。
二维装箱以及扩展到三维装箱问题的基于遗传算法代码实现_小陳参上的博客-CSDN博客_装箱问题遗传算法
|