此代码段中是否可以进行预分配

Question

以下是蚁群优化的代码片段。我已经删除了我认为理解代码绝对不必要的内容。其余的我不确定，因为我不熟悉matlab上的编码。然而，我在500个左右的城市运行这个算法，有500只蚂蚁和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

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

以下是您应该更改的内容：

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

Answer 2

我认为MATLAB编辑器在这种情况下给出的警告是错误的。数组不会重复调整大小，只调整一次大小。原则上，tour(end+1)=tour(1)比tour=[tour,tour(1)]更有效率，但在这种情况下，您可能不会注意到成本的差异。

如果你想加快这个代码的速度，你可以考虑对它的一些循环进行矢量化，并减少执行的索引操作的数量。例如本节：

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

可以写成：

tour = ant(k).Tour;
ind = sub2ind(size(model.D),tour,circshift(tour,-1));
ant(k).Cost = sum(model.D(ind));
if ant(k).Cost < BestSol.Cost
BestSol = ant(k);
end

这个重写的代码没有循环，通常会让事情变得更快，而且它也不会重复进行复杂的索引(ant(k).Cost是两个索引操作，在一个循环中，这会使您的速度减慢(。

有更多这样的优化机会，但重写整个函数不在这个答案的范围内。

我还没有尝试运行代码，请告诉我在使用建议的更改时是否有任何错误。