群体智能-果蝇算法

是的，今天要说的就是果蝇算法，“果蝇”就是你理解的那个果蝇，这是在2011年由Wen-Tsao Pan提出的有一种新型的群体智能优化算法。

1，引言：

演化式计算是一种共享名词，系指达尔文进化论的 ”适者生存，不适者淘汰”，以此观念来实际模拟自然界演化过程所建立的演算方式，例如早期Holland (1975) 教授的遗传算法(Genetic Algorithms)。然而，后进者开始将演化重心转移到动物的觅食行为与群体行为上，最早是以Dorigo (1997)教授所提出的蚁群算法(Ant Colony Algorithm) ，该算法

是藉由蚂蚁在行进时，会释放出身体的分泌物，所谓的费洛蒙而能找出最短路径，达成优化境界。其后最早被提出的演算，也就是Eberhart(1995)教授的粒子群算法(Particle Swarm Optimization)。此算法是仿真鸟群的觅食行为，藉由迭代搜寻目前离食物最近的鸟的周围区域，最后能接近食物，达到所研究问题的最佳解。这两种算法皆是藉由动物群体觅食行为而发展出来的，因此有学者称为群体智能或是群智能算法。而它们也都必须透过迭代的搜寻才能搜寻到最佳解，因此亦属于演化式计算的领域。不论如何，生物为求生存必定有其存活的本能与方法，这些方法也是许多学者努力研究的方向。2011年Wen-Tsao Pan从果蝇的觅食行为得到启发，因而提出果蝇优化算法(Fruit Fly Optimization Algorithm, FOA).

2，关于FOA的基本概念：

果蝇优化算法(Fruit Fly Optimization Algorithm, FOA)是一种基于果蝇觅食行为推演出寻求全局优化的新方法。果蝇本身在感官知觉上优于其他物种，尤其在嗅觉与视觉上，如图1 所示。果蝇的嗅觉器官能很好地搜集漂浮在空气中的各种气味，甚至能嗅到40 公里以外的食物源。然后，飞近食物位置后亦可使用敏锐的视觉发现食物与同伴聚集的位置，并且往该方向飞去。

图1 果蝇的身体构造

依照果蝇搜寻食物的特性，将其归纳为几个必要的步骤与程序范例，以提供读者参考，读者可配合图二进行了解：

图2 果蝇群体迭代搜寻食物的示意图

其步骤为:

(1) 随机初始果蝇群体位置。

Init X_axis

Init Y_axis

(2) 附与果蝇个体利用嗅觉搜寻食物de随机方向与距离。

Xi= X_axis + Random Value

Yi= Y_axis + Random Value

(3) 由于无法得知食物位置，因此先估计与原点的距离(Dist)，再计算

味道浓度判定值(S)，此值为距离的倒数。

Disti=sqrt(X_i^2+Y_i^2 )；

Si=1/Disti

(4) 味道浓度判定值(S)代入味道浓度判定函数(或称为Fitness function)以求出该果蝇个体位置的味道浓度(Smelli)。

Smelli = Function(Si)

(5) 找出此果蝇群体的中味道浓度最高的果蝇(求极大值)

[bestSmell bestIndex] = max(Smell)

(6) 保留最佳味道浓度值与x、y 坐标，此时果蝇群体利用视觉往该位置飞去。

Smellbest = bestSmell

X_axis = X(bestIndex)

Y_axis = Y(bestIndex)

(7) 进入迭代寻优，重复执行步骤2-5，并判断味道浓度是否优于前一迭代味道浓度，若是则执行步骤6。

3，举例：解析果蝇优化算法求解极小值

以FOA 求得函数极小值，其函数为:

y = -5 + x*x

其极小值的解答为-5。随机初始化果蝇群体位置区间为[0,10]，迭代的果蝇搜寻食物的随机飞行方向与距离区间为[-1,1]。经由100 次迭代搜寻极小值后，程序执行结果逐渐逼近该函数极值之解答。图2为迭代搜寻函数极值的解所绘制的曲线图，由上图可发现该曲线逐渐逼近函数极小值-5，而该群果蝇之坐标为(46.9049, 82.8723)。

图2 迭代求解极小值函数曲线和果蝇搜寻轨迹

3.1，详细说明如下:

(1) 随机初始果蝇群体位置。

X_axis=10*rand();

Y_axis=10*rand();

(2) 附与果蝇个体利用嗅觉搜寻食物之随机方向与距离。

X(i)=X_axis+2*rand()-1;

Y(i)=Y_axis+2*rand()-1;

(3) 由于无法得知食物位置，因此先估计与原点之距离(Dist)，再计算味道浓度判定值(S)，此值为距离之倒数。

D(i)=(X(i)^2+Y(i)^2)^0.5;

S(i)=1/D(i);

(4) 味道浓度判定值(S)代入味道浓度判定函数(或称为Fitness function)以求出该果蝇个体位置的味道浓度(Smelli)。

Smell(i)=-5+S(i)^2;

(5) 找出此果蝇群体的中味道浓度最低的果蝇(求极小值)。

[bestSmell bestindex]=min(Smell);

(6) 保留最佳味道浓度值与x、y 坐标，此时果蝇群体利用视觉往该位

置飞去。

X_axis=X(bestindex);

Y_axis=Y(bestindex);

Smellbest=bestSmell;

(7) 进入迭代寻优，重复执行步骤2-5，并判断味道浓度是否优于前一迭代味道浓度，若是则执行步骤6.,

3.2，完整代码如下（MATLAB）：

%***清空运行环境。

clc

clear

%***随机初始果蝇群体位置。

X_axis=10*rand();

Y_axis=10*rand();

%***设置参数。

maxgen=100; %迭代次数

sizepop=20; %种群规模

%***果蝇寻优开始，利用嗅觉寻找食物。

for i=1:sizepop

%***附与果蝇个体利用嗅觉搜寻食物之随机方向与距离。

X(i)=X_axis+2*rand()-1;

Y(i)=Y_axis+2*rand()-1;

%***由于无法得知食物位置，因此先估计与原点之距离(Dist)，再计算

味道浓度判定值(S)，此值为距离之倒数。

D(i)=(X(i)^2+Y(i)^2)^0.5;

S(i)=1/D(i);

%***味道浓度判定值(S)代入味道浓度判定函数(或称为Fitness function)

以求出该果蝇个体位置的味道浓度(Smelli)。

Smell(i)=-5+S(i)^2;

end

%***找出此果蝇群体的中味道浓度最低的果蝇(求极小值)。

[bestSmell bestindex]=min(Smell);

%***保留最佳味道浓度值与x、y 坐标，此时果蝇群体利用视觉往该位

置飞去。

X_axis=X(bestindex);

Y_axis=Y(bestindex);

Smellbest=bestSmell;

%***果蝇迭代寻优开始

for g=1:maxgen

%***附与果蝇个体利用嗅觉搜寻食物之随机方向与距离。

for i=1:sizepop

X(i)=X_axis+2*rand()-1;

Y(i)=Y_axis+2*rand()-1;

%***由于无法得知食物位置，因此先估计与原点之距离(Dist)，再计算

味道浓度判定值(S)，此值为距离之倒数。

D(i)=(X(i)^2+Y(i)^2)^0.5;

S(i)=1/D(i);

%***判定值(S)代入判定函数以求出该果蝇位置的味道浓度(Smelli)。

Smell(i)= -5+S(i)^2;

end

%***找出此果蝇群体的中味道浓度最低的果蝇(求极小值)。

[bestSmell bestindex]=min(Smell);

%***判断味道浓度是否优于前一迭代味道浓度，若是则保留最佳味道

浓度值与x、y 坐标，此时果蝇群体利用视觉往该位置飞去。

if bestSmell<Smellbest

X_axis=X(bestindex);

Y_axis=Y(bestindex);

Smellbest=bestSmell;

end

%***每代最优Smell 值纪录到yy 数组中，并记录最优迭代坐标

yy(g)=Smellbest;

Xbest(g)=X_axis;

Ybest(g)=Y_axis;

end

%***绘制迭代味到浓度与果蝇飞行路径趋势图

figure(1)

plot(yy)

title('Optimization process','fontsize',12)

xlabel('Iteration Number','fontsize',12);

ylabel('Smell','fontsize',12);

figure(2)

plot(Xbest,Ybest,'b.');

title('Fruit fly flying route','fontsize',14)

xlabel('X-axis','fontsize',12);

ylabel('Y-axis','fontsize',12);