【原】【优秀作业】人工鱼群优化算法

人工鱼群优化算法

一、概述

人工鱼群算法（Artificial Fish Swarm Algorithm，简称AFSA）是受鱼群行为的启发，由国内李晓磊博士于2002年提出的一种基于动物行为的群体智能优化算法，是行为主义人工智能的一个典型应用，这种算法源于鱼群的觅食行为。

在一片水域中，鱼往往能自行或尾随其它鱼，找到营养物质多的地方，因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为，从而实现寻优。

如何利用简便有效的方式来构造并实现这些行为将是算法实施的主要问题。

觅食行为主要认为就是循着食物多的方向游动的一种行为，在寻优算法中则是向较优方向前进的迭代方式。

在聚群行为中，为了保证生存和躲避危害，鱼会自然地聚集成群。鱼聚群时所遵守的规则有 3 条：

• 分隔规则，尽量避免与临近伙伴过于拥挤。
• 对准规则，尽量与临近伙伴的平均方向一致。
• 内聚规则，尽量朝临近伙伴的中心移动。

追尾行为就是一种向临近的最活跃者追逐的行为，在寻优算法中可以理解为是向附近的最优伙伴前进的过程。

二、人工鱼群算法

人工鱼个体的状态可表示为向量，其中为欲寻优的变量，人工鱼群当前所在位置的食物浓度表示为，其中为目标函数值，人工鱼个体之间的距离表示为；表示人工鱼的感知距离；表示人工鱼移动的最大步长；为拥挤度因子；为觅食行为尝试的最大次数。

人工鱼个体下一个状态的位置定义为：

其中是0-1之间的随机数，是当前人工鱼视野范围内的一个位置。由接下来的人工鱼的4种基本行为算法描述定义。

（1）觅食行为（Prey）

觅食行为是鱼类通过使用视觉来感受认知水中的食物浓度来靠近食物的一种行为。

设人工鱼当前状态为，在其感知范围内随机选择一个状态，如果在求极大问题中，（或在求极小问题中，，因为极大和极小问题可以互相转换，所以以下均以极大问题讨论），则向该方向前进一步：

反之，再重新随机选择状态，判断是否满足前进条件；反复次后，如果仍不满足前进条件，则随机移动一步。

（2）聚群行为（Swarm）

鱼类会通过靠近群体来避开危险。这也是鱼类为了保证群体的生存和躲避伤害形成的生活习性。与鸟群类似，鱼群的形成不需要首领，所以在人工鱼群算法中对人工鱼有两条规定：

• 人工鱼尽量向视野范围$Visual$内的小伙伴的中心位置移动。
• 人工鱼如果发现一个位置太过拥挤就不会向这个位置靠近。

设人工鱼当前状态为，探索当前邻域内（即$d_{ij}<visual$）的伙伴数目$n_f$及中心位置$x_c$，如果$\frac{1}{n_f}y_c>\delta Y_i$，表明伙伴中心有较多的食物并且不太拥挤，则朝伙伴的中心位置方向前进一步：</visual$）的伙伴数目$n_f$及中心位置$x_c$，如果$\frac{1}{n_f}y_c>

否则执行觅食行为。

（3）追尾行为（Follow）

当鱼类寻找食物时，鱼群中的一条或多条鱼找到了食物，其它鱼类会通过跟随这些鱼来找到食物，这便是追尾行为。

设人工鱼当前状态为，探索当前邻域内（即$d_{ij}<visual$）的伙伴数目$n_f$及伙伴中$y_{max}$为最大的伙伴$x_{max}$，如果$\frac{1}{n_f}>\delta Y_iX_{max}X_{max}$的方向前进一步：</visual$）的伙伴数目$n_f$及伙伴中$y_{max}$为最大的伙伴$x_{max}$，如果$\frac{1}{n_f}>

否则执行觅食行为。

（4）随机行为

随机行为的实现较简单，就是在视野中选择一个状态，然后向该方向移动，其实，它是觅食行为的一个缺省行为，即的下一个位置为：

（5）行为选择

这是鱼类的生存习惯，反映出了鱼类的自主行为。在人工鱼群算法中，觅食行为奠定了算法的收敛基础，聚群行为增强了算法收敛的稳定性，追尾行为增强了算法收敛的快速性与全局性，行为选择策略则是为算法收敛的速度与稳定性提供了保障。

行为选择策略：根据所要解决的问题性质，对人工鱼当前所处的环境进行评价，从而选择一种行为。如较常用的评价方法就是选择各行为中使得向最优方向前进最大的行为，也就是各行为中使得人工鱼的下一个状态最优的行为，如果没有能使下一状态优于当前状态的行为，则采取随机行为。

三、基于人工鱼群算法的一元非线性函数寻优

一元非线性函数为：

我们寻找。

本案例人工鱼数为100，感知距离为1，最大迭代次数为50，拥挤度因子为0.618，觅食最大试探次数为100，移动步长为0.1。

创建初始人工鱼群的代码如下：

function X=Init(Nfish,FieldDR)
%输入：
% Nfish 鱼群大小
% FieldDR 鱼的活动范围
%输出：
% X 产生的初始人工鱼群
    Nvar = size(FieldDR,2);
    X = zeros(Nfish,Nvar);
    for i=1:Nfish
        X(i,:) = FieldDR(1,:)+(FieldDR(2,:)-FieldDR(1,:)).*rand(1,Nvar);
    end
end


目标函数（食物浓度函数）代码如下：

function [Y] = FoodConsistence(X)
    Y = X.*sin(10*pi.*X)+2;
end


距离函数代码如下：

function D = Dist(Xi,X)
%计算第i条鱼与所有鱼的位置，包括本身。
    col=size(X,1);
    D=zeros(1,col);
    for j=1:col
        D(j) = norm(Xi-X(j,:));
    end
end


觅食行为的代码如下：

function [Xnext,Ynext] = Prey(Xi,ii,visual,step,try_number,FieldDR,lastY)
%觅食行为
%输入：
%Xi          当前人工鱼的位置
%ii          当前人工鱼的序号
%visual      感知范围
%step        最大移动步长
%try_number  最大尝试次数
%FieldDR     各个数的上下限
%lastY       上次的各人工鱼位置的食物浓度
%输出：
%Xnext       Xi人工鱼的下一个位置  
%Ynext       Xi人工鱼的下一个位置的食物浓度
    Xnext = [];
    Yi = lastY(ii);
    for i=1:try_number
        Xj = Xi+(2*rand(1,length(Xi))-1)*visual;
        Yj = FoodConsistence(Xj);
        if Yi<Yj
            Xnext = Xi+rand*step*(Xj-Xi)/norm(Xj-Xi);
            for k=1:length(Xnext)
                if  Xnext(k)>FieldDR(2,k)
                    Xnext(k) = FieldDR(2,k);
                end
                if  Xnext(k)<FieldDR(1,k)
                    Xnext(k) = FieldDR(1,k);
                end
            end
            break;
        end
    end
    %随机行为
    if isempty(Xnext)
        Xnext = Xi+(2*rand(1,length(Xi))-1)*visual;
        for i=1:length(Xnext)
            if  Xnext(i)>FieldDR(i,2)
                Xnext(i) = FieldDR(i,2);
            end
            if  Xnext(i)<FieldDR(i,1)
                Xnext(i) = FieldDR(i,1);
            end
        end
    end
    Ynext = FoodConsistence(Xnext);
end


聚群行为的代码如下：

function[Xnext,Ynext]=Swarm(X,i,visual,step,deta,try_number,FieldDR,lastY)
% 聚群行为
%输入：
%X           所有人工鱼的位置
%i           当前人工鱼的序号
%visual      感知范围
%step        最大移动步长
%deta        拥挤度
%try_number  最大尝试次数
%FieldDR     各个数的上下限
%lastY       上次的各人工鱼位置的食物浓度
%输出：
%Xnext       Xi人工鱼的下一个位置  
%Ynext       Xi人工鱼的下一个位置的食物浓度
    Xi = X(i,:);
    D = Dist(Xi,X);
    index = find(D>0 & D<visual);
    nf = length(index);
    if nf>0
        if length(index)==1
            Xc = X(index,:);
        else
            Xc = mean(X(index,:));
        end
        Yc = FoodConsistence(Xc);
        Yi = lastY(i);
        if Yc/nf > deta*Yi
            Xnext = Xi+rand*step*(Xc-Xi)/norm(Xc-Xi);
            for i = 1:length(Xnext)
                if  Xnext(i) > FieldDR(2,i)
                    Xnext(i) = FieldDR(2,i);
                end
                if  Xnext(i) < FieldDR(1,i)
                    Xnext(i) = FieldDR(1,i);
                end
            end
            Ynext = FoodConsistence(Xnext);
        else
            [Xnext,Ynext] = Prey(Xi,i,visual,step,try_number,FieldDR,lastY);
        end
    else
        [Xnext,Ynext] = Prey(Xi,i,visual,step,try_number,FieldDR,lastY);
    end
end


追尾行为的代码如下：

function[Xnext,Ynext]=Follow(X,i,visual,step,deta,try_number,FieldDR,lastY)
% 追尾行为
%输入：
%X           所有人工鱼的位置
%i           当前人工鱼的序号
%visual      感知范围
%step        最大移动步长
%deta        拥挤度
%try_number  最大尝试次数
%FieldDR        各个数的上下限
%lastY       上次的各人工鱼位置的食物浓度
%输出：
%Xnext       Xi人工鱼的下一个位置
%Ynext       Xi人工鱼的下一个位置的食物浓度
    Xi = X(i,:);
    D = Dist(Xi,X);
    index = find(D>0 & D<visual);
    nf = length(index);
    if nf>0
        XX = X(index,:);
        YY = lastY(index);
        [Ymax,Max_index] = max(YY);
        Xmax = XX(Max_index,:);
        Yi = lastY(i);
        if Ymax/nf > deta*Yi;
            Xnext = Xi+rand*step*(Xmax-Xi)/norm(Xmax-Xi);
            for i=1:length(Xnext)
                if  Xnext(i)>FieldDR(2,i)
                    Xnext(i) = FieldDR(2,i);
                end
                if  Xnext(i)<FieldDR(2,i)
                    Xnext(i) = FieldDR(2,i);
                end
            end
            Ynext = FoodConsistence(Xnext);
        else
            [Xnext,Ynext]=Prey(Xi,i,visual,step,try_number,FieldDR,lastY);
        end
    else
        [Xnext,Ynext] = Prey(Xi,i,visual,step,try_number,FieldDR,lastY);
    end
end


人工鱼群算法代码如下：

clc
clear 
close all
figure
hold on
ezplot('x*sin(10*pi*x)+2',[-1,2]);

%% 参数设置
fishnum = 100;        %生成100只人工鱼
MAXGEN = 50;          %最多迭代次数
try_number = 100;     %最多试探次数
visual = 1;           %感知距离
delta = 0.618;        %拥挤度因子
step = 0.1;           %步长

%% 初始化鱼群
FieldDR = [-1;2];
X = Init(fishnum,FieldDR);
gen = 1;
BestY = -1*ones(MAXGEN,1); %每步中最优的函数值
BestX = -1*ones(MAXGEN,1); %每步中最优的自变量
besty = -inf;              %最优函数值
Y = FoodConsistence(X);

%% 算法开始
while gen<=MAXGEN    
    for i=1:fishnum
        %% 聚群行为
        [Xi1,Yi1] = Swarm(X,i,visual,step,delta,try_number,FieldDR,Y); 
        %% 追尾行为
        [Xi2,Yi2] = Follow(X,i,visual,step,delta,try_number,FieldDR,Y); 
        if Yi1>Yi2
            X(i,:) = Xi1;
            Y(i,1) = Yi1;
        else
            X(i,:) = Xi2;
            Y(i,1) = Yi2;
        end
    end
    [Ymax,index] = max(Y);   
    if Ymax>besty
        besty = Ymax;
        bestx = X(index,:);
        BestY(gen) = Ymax;
        BestX(gen,:) = X(index,:);
    else
        BestY(gen) = BestY(gen-1);
        BestX(gen,:) = BestX(gen-1,:);
    end
    plot(bestx,besty,'.','color',[gen/MAXGEN,0,0])
    disp([gen,bestx,besty]);
    gen = gen+1;
end
plot(bestx,besty,'ro','MarkerSize',20)
xlabel('x')
ylabel('y')
title('鱼群算法迭代过程中最优坐标移动')

%% 优化过程图
figure
plot(1:MAXGEN,BestY)
xlabel('迭代次数')
ylabel('优化值')
title('鱼群算法迭代过程')


最优解的变化

50次鱼群算法迭代结果

最终，对应最大值为。人工鱼群算法寻优得到最优值接近函数实际最优值，说明该算法具有较强的函数极值寻优能力。

四、基于人工鱼群算法的多元非线性函数寻优

多元非线性函数为

我们寻找。

[x_plot,y_plot] = meshgrid(-10:0.05:10);
z = (sin(x_plot)./x_plot).*(sin(y_plot)./y_plot);
mesh(x_plot,y_plot,z)
xlabel('第一维度x的取值范围');
ylabel('第二维度y的取值范围');
zlabel('函数值');


本案例人工鱼数为100，感知距离为2.5，最大迭代次数为50，拥挤度因子为0.618，觅食最大试探次数为100，移动步长为0.3。

其中，创建初始人工鱼群的代码，距离函数的代码，觅食行为的代码，聚群行为的代码，追尾行为的代码见第三部分。

目标函数（食物浓度函数）代码如下：

function [Y]=FoodConsistence(X)
    Y=(sin(X(:,1))./X(:,1)).*(sin(X(:,2))./sin(X(:,2)));
end


人工鱼群算法代码如下：

clc
clear
close all

%% 参数设置
fishnum = 100;       %生成100只人工鱼
MAXGEN = 50;         %最多迭代次数
try_number = 100;    %最多试探次数
visual = 2.5;        %感知距离
delta = 0.618;       %拥挤度因子
step = 0.3;          %步长

%% 初始化鱼群
FieldDR = repmat([-10;10],[1,2]);
X = Init(fishnum,FieldDR);
gen = 1;
BestY = -1*ones(MAXGEN,1);  %每步中最优的函数值
BestX = -1*ones(MAXGEN,2);  %每步中最优的自变量
besty = -inf;               %最优函数值
Y = FoodConsistence(X);

%% 算法开始
while gen<=MAXGEN
    for i=1:fishnum
        % 聚群行为
        [Xi1,Yi1] = Swarm(X,i,visual,step,delta,try_number,FieldDR,Y);         
        % 追尾行为
        [Xi2,Yi2] = Follow(X,i,visual,step,delta,try_number,FieldDR,Y);
        if Yi1>Yi2
            X(i,:) = Xi1;
            Y(i,1) = Yi1;
        else
            X(i,:) = Xi2;
            Y(i,1) = Yi2;
        end
    end
    [Ymax,index] = max(Y);
    if Ymax>besty
        besty = Ymax;
        bestx = X(index,:);
        BestY(gen) = Ymax;
        BestX(gen,:) = X(index,:);
    else
        BestY(gen) = BestY(gen-1);
        BestX(gen,:) = BestX(gen-1,:);
    end    
    figure(1);
    hold on
    plot(bestx(1),bestx(2),'.','color',[gen/MAXGEN,0,0])
    disp([gen,bestx,besty]);
    gen=gen+1;
end
plot(bestx(1),bestx(2),'ro','MarkerSize',20)
xlabel('x')
ylabel('y')
title('鱼群算法迭代过程中最优坐标移动')

%% 优化过程图
figure
plot(1:MAXGEN,BestY)
xlabel('迭代次数')
ylabel('优化值')
title('鱼群算法迭代过程')


100次鱼群算法迭代结果

最优解的变化

最终，对应最大值为。人工鱼群算法寻优得到最优值接近函数实际最优值，说明该算法具有较强的函数极值寻优能力。

五、练习

求测试函数的最小值，以及最小值点。

1. Rastrigin function：

当时，如下图所示：

Rastrigin function

2. Sphere function：

当时，如下图所示：

Sphere function

3. Beale function：

Beale function

4. Booth function：

Booth function

5. Bukin function：

Bukin function

6. three-hump camel function：

three-hump camel function

7. Hölder table function：

Hölder table function

---

目前Datawhale的开源内容分为两种：第一种是已经囊括在我们的学习路线图内的「Datawhale精品课」，第二种是暂未囊括在我们的学习路线图内的「Datawhale打磨课」。我们根据您的投票来确定精品课程的排期，打磨课程一旦完成，即可排入我们每个月的组队学习。

请选择您「十二月份」希望学习的Datawhale精品课程。如果某门课程超过100人选择，那么我们就邀请该课程设计者开设该课程的组队学习。

• 杨剑砺：数据可视化（Matplotlib））
• 陈安东：动手学数据分析
• 王复振：SQL编程语言
• 谢文睿：吃瓜教程——西瓜书+南瓜书
• 王茂霖：李宏毅机器学习（含深度学习）

---