【智能算法】果蝇算法（FOA）原理及实现

---

1.背景

2011年，Pan受到果蝇搜索食物自然行为的启发，提出了果蝇优化算法(Fruit Fly Optimization Algorithm，FOA)。

2.算法原理

2.1算法思想

果蝇根据气味确定食物位置，食物的距离影响气味的浓度。每次搜寻果蝇的位置会根据气味最浓的果蝇位置附近进行随机游走。

2.2算法过程

群体位置初始化:
这里将求解问题中的解向量$x$映射到果蝇算法空间$(X,Y)$。
$$\begin{gathered} X_{\_axis}=lb+rand\ast (ub-lb) \\ {Y}_{\_axis}=lb+rand\ast (ub-lb) \end{gathered}$$
计算气味浓度：
由于事先不知道食物的具体位置，因此根据计算果蝇与原点的距离，气味浓度与距离呈反比。
$$\begin{gathered} Dis{t}_i=\sqrt{X_i^2+Y_i^2} \\ {S}_i=\frac{1}{Dis{t}_i} \end{gathered}$$
其中，$S_i$表示第$i$只果蝇位置处的浓度判定值。
气味浓度评定与位置更新：
将浓度判定值代入适应度函数计算得到气味浓度值$Smel{l}_i$：
$$Smel{l}_i=fitness(S_i)$$
对所有果蝇的气味浓度值进行排序，得到气味浓度最强的果蝇位置：
$$[bestSemll,bestIdx]=min(Smell)$$
果蝇群体下次飞行位置更新为：
$$\begin{gathered} X=X(bestIdx)+rand \\ Y=Y(bestIdx)+rand \end{gathered}$$

3.代码实现

% 果蝇优化算法
function [Best_pos, Best_fitness, Iter_curve, History_pos, History_best, BestX, BestY] = FOA(pop, dim, ub, lb, fobj, maxIter)
%pop 种群数量
%dim 问题维数
%ub 变量上边界
%lb 变量下边界
%maxIter 最大迭代次数
%ouput
%Best_pos 全局果蝇最优位置
%Best_fitness 全局最优位置对应的适应度值
%Iter_curve 每代最优适应度值
%History_pos 每代果蝇种群位置
%History_best 每代最优果蝇位置
%BestX 最优果蝇位置X距离
%BestY 最优果蝇位置Y距离
%% 算法初始化
% 果蝇位置初始化 
for i = 1:dim
    X_axis(:,i) = lb(i)+rand(pop,1)*(ub(i)-lb(i));
    Y_axis(:,i) = lb(i)+rand(pop,1)*(ub(i)-lb(i));
end
% 最优适应度值初始化
Best_fitness = inf;
% 参数初始化
X = zeros(pop, dim);
Y = zeros(pop, dim);
S = zeros(pop, dim);
Dist = zeros(pop, dim);
Smell = zeros(1, pop);
Iter_curve = zeros(1, maxIter);
%% 迭代
for t = 1:maxIter
    for i = 1:pop
        % 果蝇通过气味确定食物方向
        X(i,:) = X_axis(i,:) + 2 * rand(1, dim) - 1;
        Y(i,:) = Y_axis(i,:) + 2 * rand(1, dim) - 1;
        % 计算距离
        Dist(i,:) = (X(i,:).^2 + Y(i,:).^2).^0.5;
        S(i,:) = 1./Dist(i,:);
        % 检查边界
        Flag4ub=S(i,:)>ub;
        Flag4lb=S(i,:)<lb;
        S(i,:)=(S(i,:).*(~(Flag4ub+Flag4lb)))+ub.*Flag4ub+lb.*Flag4lb;
        % 计算浓度
        Smell(i) = fobj(S(i,:));
    end
    % 最优适应度值&位置
    [bestSmell, bestIndex] = min(Smell);
    % 保存位置
    for i = 1:pop
        X_axis(i,:) = X(bestIndex,:);
        Y_axis(i,:) = Y(bestIndex,:);
    end
    if bestSmell < Best_fitness
        Best_fitness = bestSmell;
        Best_pos = S(bestIndex,:);
    end
    BestXTemp = X(bestIndex,:);
    BestYTemp = Y(bestIndex,:);
    %记录距离值
    History_pos{t} = S;
    History_best{t} = Best_pos;
    BestX{t} = BestXTemp;
    BestY{t} = BestYTemp;
    Iter_curve(t) = Best_fitness;
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

优化问题：
以CEC2005测试函数为例

clear,clc,close all
x = -32:0.1:32;
y = x;
L = length(x);
for i = 1:L
    for j = 1:L
        f(i,j) = fun([x(i) y(j)]);
    end
end
surfc(x, y, f, 'LineStyle', 'none', 'FaceAlpha',0.5);

% 设定果蝇参数
pop = 50;
dim = 2;
ub = [32, 23];
lb = [-32, -32];
maxIter = 100;
fobj = @(x) fun(x);

% 求解
[Best_pos, Best_fitness, Iter_curve, History_pos, History_best, BestX, BestY] = FOA(pop, dim, ub, lb, fobj, maxIter);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21