algorithm - 在此代码段中是否可以进行预分配？

Question

以下是蚁群优化的一段代码。我删除了我认为绝对不需要理解代码的任何内容。其余的我不确定，因为我不熟悉 matlab 上的编码。然而，我在 500 个左右的城市上运行这个算法，有 500 只 Ant 和 1000 次迭代，与 matlab 上的其他算法实现相比，代码运行速度非常慢。出于我的项目的目的，我只需要数据集，而不是在 matlab 上展示编码能力，而且我有时间限制，根本不允许我从头开始学习 matlab，因为在截止日期时没有考虑也没有预期到这一点给定，所以我从在线资源中获得了算法。

Matlab 建议在循环内预分配两个变量，因为我相信它们是会改变大小的数组。但是我不完全理解代码的这两部分的目的，所以我没能这样做。我相信这两个数组在循环的每次迭代中都会增加一个新项目，因此从技术上讲，它们应该都可以为零，并且可以根据 for 循环条件预先分配两个预期最终大小的大小，但我不确定。我试过为两个数组预分配零，但它似乎没有解决任何问题，因为 Matlab 仍然显示预分配速度建议。

我在下面对 MATLAB 建议预分配的两个变量添加了两条注释。如果有人愿意浏览它并让我知道是否可行，我们将不胜感激。

    x = 10*rand(50,1);
    y = 10*rand(50,1);
    n=numel(x);
    D=zeros(n,n);

    for i=1:n-1
        for j=i+1:n
            D(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
            D(j,i)=D(i,j);
        end
    end

    model.n=n;
    model.x=x;
    model.y=y;
    model.D=D;

nVar=model.n;

MaxIt=100;     
nAnt=50;

Q=1;

tau0=10*Q/(nVar*mean(model.D(:)));

alpha=1;
beta=5;
rho=0.6;

eta=1./model.D;
tau=tau0*ones(nVar,nVar);
BestCost=zeros(MaxIt,1);

empty_ant.Tour=[];
empty_ant.Cost=[];

ant=repmat(empty_ant,nAnt,1);

BestSol.Cost=inf;

for it=1:MaxIt

    for k=1:nAnt
        ant(k).Tour=randi([1 nVar]);

        for l=2:nVar
            i=ant(k).Tour(end);
            P=tau(i,:).^alpha.*eta(i,:).^beta;
            P(ant(k).Tour)=0;
            P=P/sum(P);
            r=rand;
            C=cumsum(P);
            j=find(r<=C,1,'first');
            ant(k).Tour=[ant(k).Tour j];
        end

        tour = ant(k).Tour;
        n=numel(tour);
        tour=[tour tour(1)]; %MatLab recommends preallocation here
        ant(k).Cost=0;

        for i=1:n
        ant(k).Cost=ant(k).Cost+model.D(tour(i),tour(i+1));
        end

        if ant(k).Cost<BestSol.Cost
            BestSol=ant(k);
        end

    end

    for k=1:nAnt
        tour=ant(k).Tour;
        tour=[tour tour(1)];

        for l=1:nVar
            i=tour(l);
            j=tour(l+1);
            tau(i,j)=tau(i,j)+Q/ant(k).Cost;
        end

    end

    tau=(1-rho)*tau;

    BestCost(it)=BestSol.Cost;

    figure(1);
    tour=BestSol.Tour;
    tour=[tour tour(1)];  %MatLab recommends preallocation here
    plot(model.x(tour),model.y(tour),'g.-');
end

Answer 1

如果您更改数组的大小，这意味着将其复制到内存中的新位置。对于小数组来说这不是一个大问题，但对于大数组来说这会极大地减慢你的代码。您使用的游览数组是固定大小的(在本例中为 51 或 n+1)，因此您应该将它们预分配为零数组。您唯一要做的就是将游览的第一个元素再次添加到末尾，因此您所要做的就是设置数组的最后一个元素。

这是您应该更改的内容:

x = 10*rand(50,1);
y = 10*rand(50,1);
n=numel(x);
D=zeros(n,n);

for i=1:n-1
    for j=i+1:n
        D(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
        D(j,i)=D(i,j);
    end
end

model.n=n;
model.x=x;
model.y=y;
model.D=D;

nVar=model.n;

MaxIt=1000;     
nAnt=50;

Q=1;

tau0=10*Q/(nVar*mean(model.D(:)));

alpha=1;
beta=5;
rho=0.6;

eta=1./model.D;
tau=tau0*ones(nVar,nVar);
BestCost=zeros(MaxIt,1);

empty_ant.Tour=zeros(n, 1);
empty_ant.Cost=[];

ant=repmat(empty_ant,nAnt,1);

BestSol.Cost=inf;

for it=1:MaxIt

    for k=1:nAnt
        ant(k).Tour=randi([1 nVar]);

        for l=2:nVar
            i=ant(k).Tour(end);
            P=tau(i,:).^alpha.*eta(i,:).^beta;
            P(ant(k).Tour)=0;
            P=P/sum(P);
            r=rand;
            C=cumsum(P);
            j=find(r<=C,1,'first');
            ant(k).Tour=[ant(k).Tour j];
        end
        tour = zeros(n+1,1);
        tour(1:n) = ant(k).Tour;
        n=numel(ant(k).Tour);
        tour(end) = tour(1); %MatLab recommends preallocation here
        ant(k).Cost=0;

        for i=1:n
        ant(k).Cost=ant(k).Cost+model.D(tour(i),tour(i+1));
        end

        if ant(k).Cost<BestSol.Cost
            BestSol=ant(k);
        end

    end

    for k=1:nAnt
        tour(1:n)=ant(k).Tour;
        tour(end) = tour(1);

        for l=1:nVar
            i=tour(l);
            j=tour(l+1);
            tau(i,j)=tau(i,j)+Q/ant(k).Cost;
        end

    end

    tau=(1-rho)*tau;

    BestCost(it)=BestSol.Cost;

    figure(1);
    tour(1:n) = BestSol.Tour;
    tour(end) = tour(1);  %MatLab recommends preallocation here
    plot(model.x(tour),model.y(tour),'g.-');
end