《三維裝箱-程序5頁》由會員分享，可在線閱讀，更多相關《三維裝箱-程序5頁（5頁珍藏版）》請在裝配圖網上搜索。
1、基于遺傳模擬退火算法的三維裝箱問題研究
從計算復雜性理論來講,裝箱問題是一個NP難題,很難精確求解。目前的求解方法主要是一些近似算法,如NF(NextFit)近似算法、FF(FirstFit)近似算法、FFD(FirstFitDecreasing)近似算法等。近似算法的求解結果與物品的體積數據有較大關系,有時在極端情況下的求解結果很不理想。
本文以三維離線裝箱問題為研究對象，利用遺傳算法和模擬退火算法集成的思路對該問題進行求解，并編寫程序代碼在 Matlab 環(huán)境下進行實現(xiàn)。
1、 問題描述
假設有一批待裝貨物,它們有多種貨物種類,每種貨物的尺寸重量是不同的,對一尺寸己知的集裝箱進
2、行裝載。這里所面臨的問題是在滿足一定約束的條件下,需要找到一種裝箱方案進行裝載,能夠得到一種最佳的裝載效果,這里指的是空間容積率最高或者載重利用率達到最高。
2、 優(yōu)化模型
優(yōu)化模型中的目標函數值可以評價裝箱方案的優(yōu)劣，本文考慮待裝箱子的空間利用率最大以及所使用箱子數目最小，目標函數規(guī)定為：
其中：m 為所使用的箱子數目，Cmax為一個足夠大的常數，在本文中取為1000，以保證Cmax/m為大于 1 的正數，后一項為箱子的空間利用率，u為裝箱方案違背約束條件時的處罰值。
注：幫人代寫matlab程序，有問題請咨詢qq：778961303
部分代碼如下：
%
3、 Use: 遺傳模擬退火算法主程序
% 輸入變量（可修改量）： Box：箱子的屬性
% Cargo：貨物的屬性
% order：要求貨物的裝載次序
%
%
% 輸出：
4、bestLoadOrder:具體裝箱
% author： 怡寶2號
clc;
clear;
close all;
tic
%% 數據錄入
% Box=[2.33 1.78 2.197 5000]; % 貨箱數據 長，寬，高，限重
% Cargo=[0.94 0.68 0.39 0.249288 270.5 6;0.81 1.02 0.6 0.495720 896 2;...
% 0.81 1.02 0.70 0.578340 868 4;0.73 0.69 0.80 0.40296 240 2;...
% 1.
5、20 0.72 0.72 0.622080 280 2;1.10 0.84 0.26 0.24024 80 1;...
% 0.80 0.74 0.72 0.426240 180 1;1.60 1.07 0.75 1.28400 774 12;...
% 1.19 1.11 1.08 1.426572 960 11;1.19 1.11 0.9 1.18810 800 10;...
% 1.40 1.16 1.20 1.948800 420 8;0.82 0.37 0.18 0.54612 40 5]; % 貨物數據
%長度（
6、m） 寬度（m） 高度（m） 體積（m^3） 重量（kg） 數量
order=[6,3,11,7,8,5,1,2,4,9,10,12;];
cmax=300; %所使用的箱子數參數
% save Box Box
% save Cargo Cargo
% toc
%% 模擬退火參數
tic
T=100; % 初始溫度
Tend=1e-3; % 終止溫度
L=5; % 各溫度下的迭代次數（鏈長）
q=0.8; %降溫速率
G=100;
%% 遺傳參數
Pc=0.9;
7、%交叉概率
Pm=0.05; %變異概率
popsize=20;
retain=10;
GGAP=0.9; %代溝
%% 加載數據
load Box
load Cargo
%%
N=size(Cargo,1); % 待裝箱類別數
for i=1:popsize
chrom(i,:)=randperm(N); %隨機產生一個裝箱順序
end
for i=1:popsize
tempchrom=chrom(i,:);
[RestSpace,LoadOrder]=IniOrd
8、er(tempchrom,Box,Cargo);
fitness(i)=FitFun(cmax,RestSpace,LoadOrder,Box,tempchrom,order);
end
fitness=fitness;
%% 計算迭代的次數 Time
Time=ceil(double(solve([1000*(0.8)^x=,num2str(Tend)]))); %solve(1000*(0.8)^x=1e-3)這樣也可以
count=0; %迭代計數
Obj=[]; %目標值矩陣初始化
track
9、=[]; %每代的最優(yōu)路線矩陣初始化
bestchrom=[];
%% 迭代
while T>Tend
count=count+1; %更新迭代次數
temp=[];
[temp index]=sort(fitness,descend);
chrom=chrom(index,:);
chromone=chrom(1:retain,:);
fitnessone=temp(1:retain,:);
chromtwo=chrom(retain+1:end,:);
10、
%% 交叉操作
SelCh=Recombin(chromtwo,Pc);
%% 變異
SelCh=Mutate(SelCh,Pm);
tempchrom=[];
for i=1:size(SelCh,1)
tempchrom=SelCh(i,:);
[RestSpace,LoadOrder]=IniOrder(tempchrom,Box,Cargo);
fitnesstwo(i,:)=FitFun(cmax,RestSpace,LoadOrder
11、,Box,tempchrom,order);
end
for k=1:L
%% 產生新解
for j=1:(popsize-retain)
newchrom(j,:)=randperm(N);
end
tempchrom=[];
for i=1:(popsize-retain)
tempchrom=newchrom(i,:);
[RestSpace,L
12、oadOrder]=IniOrder(tempchrom,Box,Cargo);
newfitness(i,:)=FitFun(cmax,RestSpace,LoadOrder,Box,tempchrom,order);
end
newfitness=G-newfitness;
for i=1:(popsize-retain)
if newfitness(i,:)
13、);
fitnesstwo(i,:)=G-newfitness(i,:);
elseif exp(-(newfitness(i,:)-fitnesstwo(i,:))/T)
SelCh(i,:)=newchrom(i,:);
fitnesstwo(i,:)=G-newfitness(i,:);
% else %則原種群和解不變,即不接受模擬退火的選擇
end
end
end
三維裝箱-程序5頁
