首页 / 算法 / 粒子群算法求解三维装箱问题
粒子群算法求解三维装箱问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了粒子群算法求解三维装箱问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5670字，纯文字阅读大概需要9分钟。
内容图文
粒子群算法求解三维装箱问题
三维装箱问题介绍
三维装箱问题定义为：给定 i 种长宽高为 Li、Wi、 Hi 的集装箱和 j 种长宽高为 lj、wj、hj ，重量为 mj 的货物，在考虑一定约束条件的同时，最大化地利用集装箱的体积或载重量，将货物装载到一个或多个集装箱中。集装箱装载问题可以根据集装箱数量、集装箱形状、装载维度、装载目标、货物种类、货物到达情况等进行分类。
基本约束条件
（1）体积约束
集装箱装载货物的过程中，空间不断缩小，集装箱体积与货物体积是装载可行性的主要标准。
（2）重量约束
货物的总重量小于或等于集装箱的最大承载量时，货物才可装入集装箱中。
（3）重量平衡约束
为了使集装箱均匀地装载货物，在制定装载方案时，应充分考虑货物摆放的重心约束。集装箱内货物的稳定有助于提高交通运输的稳定性，因此尽量减少货物之间的空隙，同时将密度较大并且质量较大的货物放入最底端，以保证集装箱的稳定性。
（4）方向约束
在确定货物装载顺序时，还需考虑特定类型货物的摆放方向，如果客户没有提出任何方向限制，那么可以根据装载需求进行装载，以提高装载效率。
（5）承载约束
在进行分层装载时，要充分考虑货物的最大承载压力，否则下面的货物会因为承载压力不够而导致损坏，因此装载层数以及装载顺序都需要被限制。
（6）装载顺序约束
不同订单的货物应按照不同的装载优先级进行处理。
模型假设
本文主要针对集装箱装载布局进行研究，将体积约束、重量约束、重量平衡约束、方向约束作为约束条件。为了提高集装箱的利用效率，将集装箱体积利用率最大作为目标函数。现将模型做如下假设
（1）集装箱形状假设为长方体。
（2）集装箱内货物的位置没有区域限制。
（3）货物均为长方体且质量分布均匀。
（4）货物可以保持其形状和尺寸，不会由于堆叠而变形，不是危险品等特殊货物。
（5）不考虑途中货物的加载与卸载。
模型建立
粒子群算法
粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。PSO算法就从鸟类这种生物种群的觅食行为特性中得到启发并用于求解优化问题。
用一种粒子来模拟上述的鸟类个体，每个粒子可视为N维搜索空间中的一个搜索个体，粒子的当前位置即为对应优化问题的一个候选解，粒子的飞行过程即为该个体的搜索过程．粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整．粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子单独搜寻的最优解叫做个体极值，粒子群中最优的个体极值作为当前全局最优解。不断迭代，更新速度和位置。最终得到满足终止条件的最优解。
参数设置
%% Problem Definition
model=SelectModel(); % Select Model
CostFunction=@(xhat) MyCost(xhat,model); % Cost Function
VarSize=[model.N model.N]; % Decision Variables Matrix Size
nVar=prod(VarSize); % Number of Decision Variables
VarMin=0; % Lower Bound of Decision Variables
VarMax=1; % Upper Bound of Decision Variables
%% PSO Parameters
MaxIt=250; % Maximum Number of Iterations
nPop=150; % Population Size (Swarm Size)
w=1; % Inertia Weight
wdamp=0.99; % Inertia Weight Damping Ratio
c1=1.5; % Personal Learning Coefficient
c2=2.0; % Global Learning Coefficient
粒子群代码
%% Initialization
empty_particle.Position=[];
empty_particle.Cost=[];
empty_particle.Sol=[];
empty_particle.Velocity=[];
empty_particle.Best.Position=[];
empty_particle.Best.Cost=[];
empty_particle.Best.Sol=[];
particle=repmat(empty_particle,nPop,1);
BestSol.Cost=inf;
for i=1:nPop
% Initialize Position
particle(i).Position=unifrnd(VarMin,VarMax,VarSize);
% Initialize Velocity
particle(i).Velocity=zeros(VarSize);
% Evaluation
[particle(i).Cost, particle(i).Sol]=CostFunction(particle(i).Position);
% Update Personal Best
particle(i).Best.Position=particle(i).Position;
particle(i).Best.Cost=particle(i).Cost;
particle(i).Best.Sol=particle(i).Sol;
% Update Global Best
if particle(i).Best.Cost<BestSol.Cost
BestSol=particle(i).Best;
end
end
BestCost=zeros(MaxIt,1);
%% PSO Main Loop
for it=1:MaxIt
for i=1:nPop
% Update Velocity
particle(i).Velocity = w*particle(i).Velocity ...
+c1*rand(VarSize).*(particle(i).Best.Position-particle(i).Position) ...
+c2*rand(VarSize).*(BestSol.Position-particle(i).Position);
% Apply Velocity Limits
particle(i).Velocity = max(particle(i).Velocity,VelMin);
particle(i).Velocity = min(particle(i).Velocity,VelMax);
% Update Position
particle(i).Position = particle(i).Position + particle(i).Velocity;
% Velocity Mirror Effect
IsOutside=(particle(i).Position<VarMin | particle(i).Position>VarMax);
particle(i).Velocity(IsOutside)=-particle(i).Velocity(IsOutside);
% Apply Position Limits
particle(i).Position = max(particle(i).Position,VarMin);
particle(i).Position = min(particle(i).Position,VarMax);
% Evaluation
[particle(i).Cost, particle(i).Sol] = CostFunction(particle(i).Position);
% Mutation
NewParticle=particle(i);
NewParticle.Position=Mutate(particle(i).Position, model);
[NewParticle.Cost, NewParticle.Sol]=CostFunction(NewParticle.Position);
if NewParticle.Cost<=particle(i).Cost || rand < 0.1
particle(i)=NewParticle;
end
% Update Personal Best
if particle(i).Cost<particle(i).Best.Cost
particle(i).Best.Position=particle(i).Position;
particle(i).Best.Cost=particle(i).Cost;
particle(i).Best.Sol=particle(i).Sol;
% Update Global Best
if particle(i).Best.Cost<BestSol.Cost
BestSol=particle(i).Best;
end
end
end
% Local Search based on Mutation
for k=1:3
NewParticle=BestSol;
NewParticle.Position=Mutate(BestSol.Position, model);
[NewParticle.Cost, NewParticle.Sol]=CostFunction(NewParticle.Position);
if NewParticle.Cost<=BestSol.Cost
BestSol=NewParticle;
end
end
BestCost(it)=BestSol.Cost;
disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
w=w*wdamp;
% Plot Best Solution
figure(1);
PlotSolution(BestSol.Sol,model);
pause(0.01);
end
%% Results
figure;
plot(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
结果展示
店铺地址
欢迎加入群智能讨论群
新群人少，请多多关照
QQ群：688369315
内容总结
以上是互联网集市为您收集整理的粒子群算法求解三维装箱问题全部内容，希望文章能够帮你解决粒子群算法求解三维装箱问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。