A list,
Ant colony algorithm is an optimization algorithm to simulate the foraging behavior of ant colonies. The ants scatter pheromones throughout the foraging process, and the ants use the amount of pheromone they perceive to decide which grid to choose.
In the initial stage, since there are no pheromones on the ground, the ant colony’s walking path is random, and the ants will continuously release pheromones to mark their walking path. Over time, several ants find food, and there are several routes from the burrow to the food. Because the behavioral trajectories of ants are randomly distributed, the number of ants on the short path is denser than those on the long path per unit time, and the pheromone concentration left by the short path is higher. This provides a strong direction for the ants behind them, and more and more ants flock to the shortest route. For an individual ant, it’s not looking for the shortest path, it’s just choosing according to probability; For the whole ant colony system, they achieve the objective effect of finding the optimal path.
Assuming that the total number of ants in the ant colony is M, each ant moves in the grid environment, and selects the next grid according to the state transition rule. Assuming that ant K is located in grid I at time T, the probability of ant K selecting the next grid J is:
In Formula (1), V represents the set of the next grid that ant K can choose; Alpha is the heuristic factor of pheromone concentration. The larger Alpha is, the more ant K tends to choose the path traveled by most ants. Beta represents the expectation heuristic factor, reflecting the effect of visibility information on ant’s selection of next position. The larger the Beta value is, the more ant K tends to choose the grid close to the target point, and the more inclined it is to move towards the visibility range. Is the pheromone concentration on the path (I,j) at time t; Represents the heuristic information on the path (I,j) at time t, which is defined as:
The core part of ant colony algorithm is to simulate the behavior of ant colony transition probability selection and calculate the transition probability by using pheromone and heuristic function value. In the process of ant state transfer, the reciprocal of the distance between the node and the target point is used as heuristic information, which is not conducive to the pre-avoidance of obstacles. And path planning in complex environment, the ant colony algorithm search in a large space, at the beginning of the optimized path pheromone concentration is small, positive feedback is not obvious especially in the process of random solution of “blind search” to produce a large number of local cross paths, reduce the operating efficiency of the ant colony algorithm, and easy to fall into local optimum, the search is to a certain degree, It is easy to stagnate, and the solutions found by all individuals are exactly the same, so further search is not conducive to finding better solutions.
Ii. Source code
t=[4 5;16 25.8;10 45;20 55;30 65;35 55;29 31;37 26;47 27;30 31.3;31 17;14 7;35.6 13.8;26.7 22.5;21 39;38 42;5 26;28 53;20 13;10 60;26 31;54 38;7 58;12 36;30 2] %24One point, the first25Origin save t.mat t load t.mat value=[1 1 1 2 3 2 1 3 3 2 2 2 2 2 1 2 3 3 1 1 2 1 1 1]; %24Value =value/100;
time=zeros(1.25); % Reconnaissance UAV time array, which contains the distance traveled by the aircraft, divided by the speed is the time, set the speed to '1'attacktime = zeros (1.25); % Strike UAV time array % Store the distance traveled by the reconnaissance mission corresponding to the UAV in a matrix of the mission as the time, and then the strike mission if selected, check whether the time is qualified. If the time is qualified, you can strike and put it into the taboo table. If the time is not qualified, select % of the probability. The goal is to complete all missions for all targets, so the total value of all drones harvested at the end of each iteration is the same, the sum of all targets; Therefore, this program gives priority to the execution of targets with large value, so as to prevent the uav from becoming less efficient after flying and fighting for a long time.1);
D=zeros(n,n);
for i=1:n
for j=1:n
if i~=j
D(i,j)=sqrt(sum((t(i,:)-t(j,:)).^2));
else
D(i,j)=1e-2; End end end %% Initialization parameter m=10; % Number of ants alpha=1; % pheromone importance factor beta=1; % heuristic function importance factor gama=2;
rho=0.3; % pheromone volatile factor Q=1.0; Eta = % amount1./D; Tau =ones(n,n)+7.1192 e-005; % pheromone matrix iter=1; % Initial number of iterations iter_max=80; Length_best =zeros(iter_max,1); Length_ave =zeros(iter_max,1); % Average length of each iteration path %% Iterates to find the best pathwhile iter<=iter_max
whta=cell(8.1);
lieend=zeros(8.1);
for zu=1:8
city_index=1:25; Table =[]; start=zeros(4.1);
temp=randperm(24);
for i=1:4
start(i)=temp(i);
end
table(:,1)=start;
j=2;
while (j<=30)
for i=1:4
if i==1%UAV1 is only responsible for "reconnaissance" missionsif table(1,(j- 1)) ~ =25
table1=table(1, :); table1=[table1;table(3:4:)]; tabu1=table1(:); The taboos for %UAV1 are displayed25Allow_index1 =~ismember(city_index,tabu1); The past become0, can walk for1】 【 if tabu = (1 4) allow_index = (0 1 1 0 1 1 1...) 】 Allow1 =city_index(allow_index1); Allow1; P1=allow1; % Calculates the city transfer probabilityif numel(allow1)~=0
for k=1:max(size(allow1))- 1
P1(k)=(tau(table(1,(j- 1)),allow1(k))^alpha)*(eta(table(1,(j- 1)),allow1(k))^beta)*10000+7.1192 e-004;
end
P1(max(size(allow1)))=7.1192 e-005;
P1=P1/sum(P1);
[d1,ind1]=sort(P1,2.'descend'); % in order d1, ind1 target1=allow1(ind1(1)); %pc1=cumsum(P1); % (p1 p1+ P2 p1+ P2 +p3 p1+ P2 +p3+p4....) 【 p1 < - > allow (1) p2<->allow(2)... 】 %target_index1=find(pc1>=rand); %target1=allow1(target_index1(1)); % return table(allow);1,j)=target1; % place the selected point in the path table rr=D(25,table(1.1));
time(table(1.1))=rr;
if j>2
for c=2:(j- 1)
rr=rr+D(table(1,c- 1),table(1,c));
end
end
rrr=rr+D(table(1,j- 1),target1); % RRR is the distance traveled by UAV1 to this point time(target1)= RRR;else
table(1,j)=25;
end
end
if table(1,(j- 1))= =25
table(1,j)=25;
end
end
if i==2%UAV2 is only responsible for the "Strike" missionif (table(2,(j- 1)) ~ =25)
table(2.1)=table(1.1); % Set its first strike to a target that UAV1 scouted. Ta2 =table(1: (4*(j- 1) +1)); % All elements before the current element tabu21=[]; tabu22=[]; tabu2=[];for y=1:24
if sum(ta2==y)==2tabu21=[tabu21;y]; Tabu22 =setdiff(tabu22=setdiff)1:24,ta2); %一次都没出现的放在tabu22里
tabu2=[tabu21',tabu22]; Allow_index2 =~ismember(city_index,tabu2); The past become0, can walk for1】 【 if tabu = (1 4) allow_index = (0 1 1 0 1 1 1...) 】 Allow2 =city_index(allow_index2); Allow2; P2=allow2; % Calculates the city transfer probabilityfor k=1:(length(allow2)- 1)
P2(k)=tau(table(2,(j- 1)),allow2(k))*eta(table(2,(j- 1)),allow2(k))*value(allow2(k))*10000;
end
P2(max(size(allow2)))=7.1192 e-005;
P2=P2/sum(P2);
[d2,ind2]=sort(P2,2.'descend'); % in order d1, ind1 target2=allow2(ind2(1)); %target2=d1(1); %pc2=cumsum(P2); % (p1 p1+ P2 p1+ P2 +p3 p1+ P2 +p3+p4....) 【 p1 < - > allow (1) p2<->allow(2)... 】 %target_index2=find(pc2>=rand); Allow2 (target_index2(1)); %table(); allow ();2,j)=target2; % place the selected point in the path table oo=D(25,table(2.1));
attacktime(table(2.1))=oo;
if j>2
for c=2:(j- 1)
oo=oo+D(table(2,c- 1),table(2,c));
end
end
ooo=oo+D(table(2,j- 1),target2); %ooo is the distance UAV2 traveled to this pointif numel(d2)>5
u=2;
while (ooo>time(target2)+20 & u<6)
target2=allow2(ind2(u));
ooo=oo+D(table(2,(j- 1)),target2);
u=u+1;
end
end
table(2,j)=target2;
attacktime(target2)=ooo;
end
if table(2,(j- 1))= =25
table(2,j)=25;
end
end
if i==3%UAV3 is a "search and beat" missionif table(3,(j- 1)) ~ =25
ta3=table(1: (4*(j- 1) +2));
tabu3=[];
tabu3c=[];
for y=1:24
if sum(ta3==y)==2tabu3=[tabu3;y]; End end % occurs twice and is placed in tabu3for y=1:24
if sum(ta3==y)==1tabu3c=[tabu3c;y]; Allow_index3 =~ismember(city_index,tabu3); The past become0, can walk for1】 【 if tabu = (1 4) allow_index = (0 1 1 0 1 1 1...) 】 Allow3 =city_index(allow_index3); Allow3; allow3; allow3; % Calculates the city transfer probabilityfor k=1:(length(allow3)- 1)
%if ismember(allow3(k),tabu3c)==1
h=table(3,(j- 1))
P3(k)=(tau(table(3,j- 1),allow3(k))^alpha)*(eta(table(3,(j- 1)),allow3(k))^beta)*value(allow3(k))*10000+7.1192 e-005; % This is to be typed and needs value %else
%P3(k)=(tau(table(3,(j- 1)),allow3(k))^alpha)*(eta(table(3,(j- 1)),allow3(k))^beta)*100+7.1192 e-005; % These are for reconnaissance and have no value %end
end
P3(max(size(allow3)))=7.1192 e-009;
P3=P3/sum(P3);
[d3,ind3]=sort(P3,2.'descend'); % in order d1, ind1 target3=allow3(ind3(1)); Select the next city %pc3=cumsum(P3); % (p1 p1+ P2 p1+ P2 +p3 p1+ P2 +p3+p4....) 【 p1 < - > allow (1) p2<->allow(2)... 】 %target_index3=find(pc3>=rand); Allow3 (target_index3())1)); %table(); allow ();3,j)=target3; % Place the selected point in the path table ww=D(25,table(3.1));
time(table(3.1))=ww;
if j>2
for c=2:(j- 1)
ww=ww+D(table(3,c- 1),table(3,c));
end
end
www=ww+D(table(3,j- 1),target3); % WWW is the distance UAV3 traveled to this pointif ismember(target3,tabu3c)= =0% Time (target3)= WWW; table(3,j)=target3;
else% Strike task attackTime (target3)= WWW;if numel(d3)>5
u=2;
while (www>time(target3)+20 & u<6)
target3=allow3(ind3(u));
www=ww+D(table(3,(j- 1)),target3);
u=u+1;
end
end
attacktime(target3)=www;
table(3,j)=target3; %www<time(target3)+10The strike mission is reasonableend
end
if table(3,(j- 1))= =25
table(3,j)=25;
end
end
if i==4%UAV4 is a "search and attack" missionif table(4,(j- 1)) ~ =25
ta4=table(1: (4*(j- 1) +3));
tabu4=[];
tabu4c=[];
for y=1:24
if sum(ta4==y)==2tabu4=[tabu4;y]; In tabu4, you can place those that have been scouted (in tabu u4c) if selected in tabu4'And then calculate its range and compare it to the reconnaissance pathfor y=1:24
if sum(ta4==y)==1tabu4c=[tabu4c;y]; end end allow_index4=~ismember(city_index,tabu4); The past become0, can walk for1】 【 if tabu = (1 4) allow_index = (0 1 1 0 1 1 1...) 】 Allow4 =city_index(allow_index4); P4=allow4; % Calculates the city transfer probabilityfor k=1:(max(size(allow4))- 1)
%if ismember(allow4(k),tabu4c)==1
sxx=table(4,(j- 1))
P4(k)=(tau(table(4,(j- 1)),allow4(k))^alpha)*(eta(table(4,(j- 1)),allow4(k))^beta)*value(allow4(k))*10000+7.1192 e-005;
%else
%P4(k)=(tau(table(4,(j- 1)),allow4(k))^alpha)*(eta(table(4,(j- 1)),allow4(k))^beta)*100+7.1192 e-005;
%end
end
P4(max(size(allow4)))=7.1192 e-009;
P4=P4/sum(P4);
[d4,ind4]=sort(P4,2.'descend'); % in order d1, ind1 target4=allow4(ind4(1)); %pc4=cumsum(P4); % (p1 p1+ P2 p1+ P2 +p3 p1+ P2 +p3+p4....) 【 p1 < - > allow (1) p2<->allow(2)... 】 %target_index4=find(pc4>=rand); Allow4 (target_index4(1)); %table(); allow ();4,j)=target4; % place the selected point in the path table qq=D(25,table(4.1));
time(table(4.1))=qq;
if j>2
for c=2:(j- 1)
qq=qq+D(table(4,c- 1),table(4,c));
end
end
qqq=qq+D(table(4,j- 1),target4); % WWW is the distance UAV3 traveled to this pointif ismember(target4,tabu4c)= =0% Time (target4)= QQQ; table(4,j)=target4;
else% Strike task attackTime (target4)= QQQ;if numel(d4)>5
u=2;
while (qqq>time(target4)+20 & u<6)
target4=allow4(ind4(u));
qqq=qq+D(table(4,j- 1),target4);
u=u+1;
end
end
attacktime(target4)=qqq;
table(4,j)=target4; %www<time(target4)+10The strike mission is reasonableend
end
if table(4,(j- 1))= =25
table(4,j)=25; End end end % End of a columnCopy the code3. Operation results
Fourth, note
Version: 2014 a