三维装箱算法matlab,三维装箱遗传算法matlab程序

三维装箱问题是指将若干个不同体积的物品放入若干个容器中，使得每个物品都被放入容器中，并且每个容器的使用率最高。这是一个NP-hard问题，因此使用遗传算法等启发式算法来解决较为常见。

以下是一个基于遗传算法的三维装箱程序，使用MATLAB编写：

clearvars
clc
close all

%% Problem Definition

nVar=30;           % Number of Decision Variables

VarSize=[1 nVar];   % Decision Variables Matrix Size

VarMin=0;         % Decision Variables Lower Bound
VarMax=1;         % Decision Variables Upper Bound

%% GA Parameters

MaxIt=100;            % Maximum Number of Iterations

nPop=50;              % Population Size

pc=0.8;               % Crossover Percentage
nc=2*round(pc*nPop/2); % Number of Offsprings (also Parents)

pm=0.3;               % Mutation Percentage
nm=round(pm*nPop);    % Number of Mutants

gamma=0.05;

mu=0.02;              % Mutation Rate

beta=8;               % Selection Pressure

%% Initialization

empty_individual.Position=[];
empty_individual.Cost=[];
empty_individual.Volume=[];
empty_individual.Order=[];

pop=repmat(empty_individual,nPop,1);

for i=1:nPop
    
    % Initialize Position
    pop(i).Position=unifrnd(VarMin,VarMax,VarSize);
    
    % Evaluation
    [pop(i).Volume,pop(i).Cost,pop(i).Order]=Evaluate(pop(i).Position);
    
end

% Sort Population
[~, SortOrder]=sort([pop.Cost]);
pop=pop(SortOrder);

% Store Best Solution Ever Found
BestSol=pop(1);

% Array to Hold Best Cost Values
BestCost=zeros(MaxIt,1);

% Store Cost
WorstCost=max([pop.Cost]);
MeanCost=mean([pop.Cost]);

%% Main Loop

for it=1:MaxIt
    
    % Calculate Selection Probabilities
    P=exp(-beta*[pop.Cost]/WorstCost);
    P=P/sum(P);
    
    % Crossover
    popc=repmat(empty_individual,nc/2,2);
    for k=1:nc/2
        
        % Select Parents
        i1=RouletteWheelSelection(P);
        i2=RouletteWheelSelection(P);
        
        % Perform Crossover
        [popc(k,1).Position, popc(k,2).Position]=Crossover(pop(i1).Position,pop(i2).Position);
        
        % Evaluate Offsprings
        [popc(k,1).Volume, popc(k,1).Cost, popc(k,1).Order]=Evaluate(popc(k,1).Position);
        [popc(k,2).Volume, popc(k,2).Cost, popc(k,2).Order]=Evaluate(popc(k,2).Position);
        
    end
    popc=popc(:);
    
    % Mutation
    popm=repmat(empty_individual,nm,1);
    for k=1:nm
        
        % Select Parent
        i=randi([1 nPop]);
        
        % Perform Mutation
        popm(k).Position=Mutate(pop(i).Position,mu);
        
        % Evaluate Mutant
        [popm(k).Volume, popm(k).Cost, popm(k).Order]=Evaluate(popm(k).Position);
        
    end
    
    % Merge
    pop=[pop
         popc
         popm]; %#ok
     
    % Sort Population
    [~, SortOrder]=sort([pop.Cost]);
    pop=pop(SortOrder);
    
    % Remove Extra Individuals
    pop=pop(1:nPop);
    
    % Update Best Solution Ever Found
    BestSol=pop(1);
    
    % Store Best Cost Ever Found
    BestCost(it)=BestSol.Cost;
    
    % Show Iteration Information
    disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
    
    % Plot Best Solution
    figure(1);
    PlotSolution(BestSol.Volume,BestSol.Order);
    pause(0.01);
    
    % Break If Cost is Small Enough
    if BestCost(it)<1e-6
        break;
    end
    
    % Adapt Mutation Rate
    mu=mu+gamma*(1/sqrt(nVar))*(BestSol.Cost-MeanCost)/MeanCost;
    
    % Clamp Mutation Rate
    mu=max(mu,0);
    
end

%% Results

figure;
plot(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
grid on;

%% Functions

function [Volume, Cost, Order]=Evaluate(x)

    % Number of Items
    n=numel(x);
    
    % Item Dimensions
    D=zeros(n,3);
    for i=1:n
        D(i,:)=Dimensions(x(i));
    end
    
    % Container Dimensions
    C=[1 1 1];
    
    % Offsets
    O=zeros(n,3);
    O(1,:)=zeros(1,3);
    for i=2:n
        O(i,:)=O(i-1,:)+D(i-1,:);
    end
    
    % Positions
    J=zeros(n,3);
    for i=1:n
        J(i,:)=O(i,:)+0.5*D(i,:);
    end
    
    % Check if Feasible
    OK=all(J<=repmat(C,n,1),2);
    
    % Volume
    Volume=sum(D(:,1).*D(:,2).*D(:,3));
    
    % Cost
    Cost=inf;
    if all(OK)
        Cost=max(O(:,3)+D(:,3));
    end
    
    % Order
    [~, Order]=sort(x);

end

function [y1, y2]=Crossover(x1,x2)

    alpha=unifrnd(0,1,size(x1));
    
    y1=alpha.*x1+(1-alpha).*x2;
    y2=alpha.*x2+(1-alpha).*x1;

end

function y=Mutate(x,mu)

    n=numel(x);
    
    nmu=ceil(mu*n);
    
    j=randsample(nmu,n);
    
    sigma=0.1*(VarMax-VarMin);
    
    y=x;
    y(j)=x(j)+sigma*randn(size(j));
    
    y=max(y,VarMin);
    y=min(y,VarMax);

end

function d=Dimensions(x)

    switch x
        case 1
            d=[0.7 0.7 0.7];
        case 2
            d=[0.6 0.6 0.6];
        case 3
            d=[0.5 0.5 0.5];
        case 4
            d=[0.4 0.4 0.4];
        case 5
            d=[0.3 0.3 0.3];
        case 6
            d=[0.2 0.2 0.2];
        otherwise
            d=[0 0 0];
    end

end

function PlotSolution(Volume, Order)

    clf;
    hold on;
    box on;
    grid on;
    view(3);
    title(['Volume = ' num2str(Volume)]);
    xlabel('X');
    ylabel('Y');
    zlabel('Z');
    
    n=numel(Order);
    C=[1 1 1];
    O=zeros(n,3);
    D=zeros(n,3);
    for i=1:n
        D(i,:)=Dimensions(Order(i));
    end
    O(1,:)=zeros(1,3);
    for i=2:n
        O(i,:)=O(i-1,:)+D(i-1,:);
    end
    J=zeros(n,3);
    for i=1:n
        J(i,:)=O(i,:)+0.5*D(i,:);
    end
    
    for i=1:n
        DrawCube(J(i,:),D(i,:),[1 0 0]);
    end
    
    axis equal;
    xlim([0 C(1)]);
    ylim([0 C(2)]);
    zlim([0 C(3)]);
    
    drawnow;
    
end

function DrawCube(P,D,color)

    X=[0 1 1 0 0
       1 1 0 0 1
       1 1 0 0 1
       0 1 1 0 0]*D(1)+P(1);
   
    Y=[0 0 1 1 0
       0 1 1 0 0
       1 1 1 1 1
       1 0 0 1 1]*D(2)+P(2);
   
    Z=[0 0 0 0 0
       0 0 0 0 0
       0 1 1 0 0
       0 1 1 0 0]*D(3)+P(3);
   
    surf(X,Y,Z,'FaceColor',color,'EdgeColor','none','FaceAlpha',0.5);

end

function i=RouletteWheelSelection(P)

    r=rand;
    C=cumsum(P);
    i=find(r<=C,1,'first');

end

这个程序使用了遗传算法来解决三维装箱问题。它首先随机初始化一组个体，并使用评估函数来计算它们的成本和体积。然后，它使用选择、交叉和突变操作来生成新的个体，并使用适应度函数来评估它们的质量。最后，它从新的个体和旧个体中选择最优的个体，并将它们作为下一代的种群重复这个过程。在遗传算法的每次迭代中，程序会记录最佳成本和最佳个体，并使用Matlab绘制出最佳个体的装箱方案。