DA 蜻蜓优化算法 - 逐句拆解 - 含代码

DA 蜻蜓优化算法

1、算法简介

蜻蜓优化算法( Dragonfly algorithm，DA)是Seyedali Mirjalili等于2016年提出的一种新型启发式智能优化算法[1]。其主要灵感源于自然界中蜻蜓的静态和动态群集行为，具有寻优能力强等特点。

先来了解了解蜻蜓吧（笑）：

• 自然界大约有3000种已知的蜻蜓品种
• 蜻蜓是自然界的飞行专家，飞行速度可达35英里每小时
• 蜻蜓以小昆虫为食，成年蜻蜓一天可以吃掉30至100只蚊子，妥妥的益虫

2、算法原理

蜻蜓算法是一种新型智能群优化算法，其原理是模拟大自然中蜻蜓寻找猎物的行为。

该算法源于自然中蜻蜓动态和静态的智能群行为，对蜻蜓的飞行线路、躲避天敌及寻找食物等生活习性进行数学建模。

• 在动态群中，为获得更好的生存环境（migration），大量的蜻蜓集群朝着共同的方向进行远距离迁徙；

• 在静态群中，为寻找其他飞行猎物（fading），由小部分蜻蜓组成的各个小组，在较小的范围内来回飞行。

蜻蜓飞行过程中的局部运动与飞行路径的临时突变是静态群的主要特征。

在自然界中，蜻蜓的生活习性可以归纳为５类行为方式：分离、排队、结盟、寻找猎物和躲避天敌。

3、算法细节

公式序号对应原论文（这部分暂时看不明白也没事，后面会详细讲解）

3.1、分离

分离是每个蜻蜓个体与同类分开的行为。分离行为的数学表达式为：
$$S_i=-\underset{j=1}{\stackrel{N’}{\Sigma }}\left(X-X_j\right)\text{\hspace{1em}(3.1)}$$
式中$N^{\prime }$为邻近个体的个数；$S_i$为第$i$个蜻蜓同类之间分离行为的位置向量；$X$为个体所在位置；$X_j$为相邻个体蜻蜓$j$所处的位置。

3.2、成队

排队是指每个蜻蜓个体在飞行时与相邻个体之间的速度匹配。排队行为的数学表达式为：

$$A_i=\frac{{\Sigma }_{j=1}^{N^{\prime }}{V}_j}{N^{\prime }}\text{\hspace{1em}(3.2)}$$
式中$A_i$ 为第 $i$ 个蜻蜓个体排队行为的位置向量；$V_j$ 为相邻个体的飞行速度。

3.3、结盟

结盟指蜻蜓与相邻同类之间彼此聚在一起的集群行为。结盟行为的数学表达式为：
$$C_i=\frac{{\Sigma }_{j=1}^{N^{\prime }}{X}_j}{N^{\prime }}-X\text{\hspace{1em}(3.3)}$$
式中$C_i$为第$i$个蜻蜓个体结盟行为的位置向量。

3.4、寻找猎物

寻找猎物指个体为生存搜寻猎物的行为。寻找猎物行为的数学表达式为：
$$F_i=X^{+}-X\text{\hspace{1em}(3.4)}$$
式中$F_i$ 代表第$i$个蜻蜓个体猎食行为的位置向量；

$X^{+}$代表待捕食的猎物所处的位置。

3.5、躲避天敌

个体出于生存的本能，需时刻警惕天敌的行为。躲避天敌行为的数学表达式为：
$$E_i=X^{-}+X\text{\hspace{1em}(3.5)}$$
式中$E_i$为第$i$个蜻蜓个体逃避天敌行为的位置向量；$X^{-}$ 为蜻蜓猎食所处的位置。步向量表示为蜻蜓的飞行方向以及步长，其数学式如下：

$$\Delta X_{t+1}=\left(s{S}_i+a{A}_i+c{C}_i+f{F}_i+e{E}_i\right)+w\Delta X_i\text{\hspace{1em}(3.6)}$$
式中：$a$为对齐权重；$c$为凝聚权重；$e$为天敌权重因子；$f$为猎物权重因子；$s$为分离权重；$t$为当前迭代次数；$w$ 为惯性权重。

在自然界中，出于生存需要，大部分时间蜻蜓都是运动的，因此所处位置也需实时更新。更新蜻蜓个体所处位置的向量，数学表达式如下：
$$X_{t+1}=X_t+\Delta X_{t+1}\text{\hspace{1em}(3.7)}$$
要达到使算法性能进一步得到强化的目的，在同类个体附近无临近解时，通过使用Ｌéｖｙ飞行的方法绕搜索空间飞行，进行蜻蜓位置的更新：
$$X_{t+1}=X_i+Levy(d)\Delta X_i\text{\hspace{1em}(3.8)}$$
其中$d$代表维度，Ｌéｖｙ函数计算如下:
$$Levy\left(x\right)=0.01\ast \frac{r_1\ast \delta }{|r_2{|}^{\frac{1}{\beta }}}\text{\hspace{1em}(3.9)}$$

$$\delta ={\left(\frac{\Gamma \left(1+\beta \right)\ast \sin \left(\frac{\pi \beta }{2}\right)}{\Gamma \left(\frac{1+\beta }{2}\right)\ast \beta \ast 2^{\left(\frac{\beta -1}{2}\right)}}\right)}^{\frac{1}{\beta }},\Gamma \left(x\right)=\left(x-1\right)!\text{\hspace{1em}(3.10)}$$

式子中：$r_1,r_2$为 $[0,1]$ 范围内的随机数；$\beta$为常数。

为调节DA算法的搜索性能，参数值（分离权重$s$、对齐权重$a$、凝聚权重$c$、猎物权重因子$f$、天敌权重因子$e$）将在寻优过程中自适应调整。

4、算法流程

4.1、原版论文

注：while循环下第一句objective values就是fitness values

读完论文算法的伪码描述，你或许有如下疑问：

• step vectors 是指？
• 如何更新 food source 和 enemy？
• 如何更新 nerghbouring radius？

保留这些疑问，我们接着往下了解。

4.2、流程逐句拆解

本过程对应于附录代码

假设种群中有25只蜻蜓，即 TotalPopulation = 25；UpperBound、LowerBound、dim、fobj由具体问题给出；设定Max_iteration=500;

(1) 随机初始化蜻蜓种群 Initialize the dragonflies population $X_i(i=1,2,\mathrm{3...},n)$代码如下：

Positions(:,i)=rand(TotalPopulation, 1).*(UpperBound - LowerBound) + LowerBound;
1

(2) 初始化ΔX和（1）一样 Initialize step vectors $\Delta X_i(i=1,2,\mathrm{3...},n)$

DeltaX(:,i)=rand(TotalPopulation, 1).*(UpperBound - LowerBound) + LowerBound;
1

(3) While the condition is not satisfied

for iter=1:Max_iteration
1

(4) 计算每只蜻蜓的适应度 Calculate the objetive values of all dragonflies

Fitness(1,i)=fobj(X(:,i)');
1

(5) 更新猎物 (F) 和天敌 (E) Update the food source and enemy
$$Foo{d}_i=FoodSourcePosition-IndividualCurrentPosition$$

$$F_i=X^{+}-X\text{\hspace{1em}(3.4)}$$

$$Enem{y}_i=EnemyPosition-IndividualCurrentPosition$$

$$E_i=X^{-}+X\text{\hspace{1em}(3.5)}$$

% 蜻蜓的策略应该是 远离天敌，趋向猎物
% Enemy Position就是迭代中适应度最大值坐标
% Food Source Position就是迭代中适应度最小值坐标

% 初始化
Food_fitness=inf;%正无穷
Food_pos=zeros(dim,1);%10*1  0

Enemy_fitness=-inf;%负无穷
Enemy_pos=zeros(dim,1);%10*1  0



% 在迭代中更新猎物和天敌坐标
for i=1:SearchAgents_no %首先计算所有目标值
	Fitness(1,i)=fobj(X(:,i)');
	if Fitness(1,i)<Food_fitness %寻找每次迭代的最小值
		Food_fitness=Fitness(1,i);
		Food_pos=X(:,i);
	end

	if Fitness(1,i)>Enemy_fitness %寻找每次迭代的最大值
		if all(X(:,i)<ub') && all( X(:,i)>lb')
			Enemy_fitness=Fitness(1,i);
			Enemy_pos=X(:,i);
		end
	end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

(6) 更新参数 Update w, s, a, c, f and e

% w 惯性权重 Inertia weight
w=0.9-iter*((0.9-0.4)/Max_iteration); %不断减小
% s 分离权重 Separation weight
% a 对齐权重 Alignment weight
% c 内聚权重 Cohesion weight
% f 猎物吸引权重 Food attraction weight
% e 天敌规避权重 Enemy distraction weight

my_c=0.1-iter*((0.1-0)/(Max_iteration/2));% 不断减小 初始 0.0996
s=2*rand*my_c; % 分离权重 0.0013
a=2*rand*my_c; % 对齐权重 0.1884
c=2*rand*my_c; % 内聚权重 0.1791
f=2*rand;      % 猎物吸引权重 0.8826
e=my_c;        % 天敌规避权重 0.0996


% Swarm Behavior follows three Important Principles:
% 1. Separation : Individual avoid static collision with neighbor.
% 2. Alignment : Individuals velocity matched with neighbor individuals.
% 3. Cohesion : Individual tendency toward center of the herd.
% 群体行为遵循三个重要原则：
% 1. 分离：个体避免与邻居发生静态碰撞。
% 2. 结盟：个体速度与邻近个体相匹配。
% 3. 成队：个体趋向于群体中心。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(7) 计算参数 Calculate S, C, A, F (3.1)~(3.5)

% Si Separation of the i-th individual
% Eq. (3.1)
        S=zeros(dim,1);
        if neighbours_no>1
            for k=1:neighbours_no
                S=S+(Neighbours_X(:,k)-X(:,i));
            end
            S=-S;
        else
            S=zeros(dim,1);
        end
% Ai Alignment of the i-th individual
% Eq. (3.2)
        if neighbours_no>1
            A=(sum(Neighbours_DeltaX')')/neighbours_no;
        else
            A=DeltaX(:,i);
        end
% Ci Cohesion of the i-th individual
% Eq. (3.3)
        if neighbours_no>1
            C_temp=(sum(Neighbours_X')')/neighbours_no;
        else
            C_temp=X(:,i);
        end
        
        C=C_temp-X(:,i);
% Fi Food source of the i-th individual
% Eq. (3.4)
        Dist2Food=distance(X(:,i),Food_pos(:,1));
        if all(Dist2Food<=r)
            F=Food_pos-X(:,i);
        else
            F=0;
        end
% Ei Enemy position of the i-th individual
% Eq. (3.5)
        Dist2Enemy=distance(X(:,i),Enemy_pos(:,1));
        if all(Dist2Enemy<=r)
            Enemy=Enemy_pos+X(:,i);
        else
            Enemy=zeros(dim,1);
        end
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

(8) 更新邻居半径 Update neighboring radius

% 迭代次数越大，半径越大，这里代表欧氏距离
r=(ub-lb)/4+((ub-lb)*(iter/Max_iteration)*2);
1
2

(9) if 结构 如果蜻蜓有同伴 if a dragonfly has at least one neighbouring dragonfly

使用如下两个方程更新 t+1 时刻蜻蜓的 速度（velocity） 和 位置（position）：
$$\Delta X_{t+1}=\left(s{S}_i+a{A}_i+c{C}_i+f{F}_i+e{E}_i\right)+w\Delta X_i\text{\hspace{1em}(3.6)}$$

$$X_{t+1}=X_t+\Delta X_{t+1}\text{\hspace{1em}(3.7)}$$

if any(Dist2Food>r) %如果食物位置不是相邻蜻蜓位置
	%当有个体与个体 i 相邻时
	if neighbours_no>1
		for j=1:dim
			DeltaX(j,i)=w*DeltaX(j,i)+rand*A(j,1)+rand*C(j,1)+rand*S(j,1);
			if DeltaX(j,i)>Delta_max(j)
				DeltaX(j,i)=Delta_max(j);
			end
			if DeltaX(j,i)<-Delta_max(j)
				DeltaX(j,i)=-Delta_max(j);
			end
			X(j,i)=X(j,i)+DeltaX(j,i);
		end
	else
		% Eq. (3.8)
		%当没有任何个体与个体 i 相邻时
		X(:,i)=X(:,i)+Levy(dim)'.*X(:,i);
		DeltaX(:,i)=0;
	end
else
	for j=1:dim
		% Eq. (3.6)
		DeltaX(j,i)=(a*A(j,1)+c*C(j,1)+s*S(j,1)+f*F(j,1)+e*Enemy(j,1)) + w*DeltaX(j,i);
		if DeltaX(j,i)>Delta_max(j)
			DeltaX(j,i)=Delta_max(j);
		end
		if DeltaX(j,i)<-Delta_max(j)
			DeltaX(j,i)=-Delta_max(j);
		end
		% Eq. (3.7)
		X(j,i)=X(j,i)+DeltaX(j,i);
	end 
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

(9) else 结构 如果蜻蜓没有同伴

只需要更新t+1时刻的蜻蜓的位置（position）：
$$X_{t+1}=X_i+Levy(d)\Delta X_i\text{\hspace{1em}(3.8)}$$

function o=Levy(d)

	beta=3/2;
	%Eq. (3.10)
	sigma=(gamma(1+beta)*sin(pi*beta/2)/(gamma((1+beta)/2)*beta*2^((beta-1)/2)))^(1/beta);
	u=randn(1,d)*sigma;
	v=randn(1,d);
	step=u./abs(v).^(1/beta);

	% Eq. (3.9)
	o=0.01*step;
end
1
2
3
4
5
6
7
8
9
10
11
12

(10) 进行边界检查

Flag4ub=X(:,i)>ub';
Flag4lb=X(:,i)<lb';
%范围大于上限则取上限
%范围小于下限则取下限，
%否则不变
X(:,i)=(X(:,i).*(~(Flag4ub+Flag4lb)))+ub'.*Flag4ub+lb'.*Flag4lb;
1
2
3
4
5
6

5、参考文献

[1]Mirjalili S. Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems[J]. Neural Computing and Applications, 2016, 27(4): 1053-1073.

6、代码以及结果

完整代码下载地址

F6:

F20: