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

人工鱼群优化算法

一、概述

人工鱼群算法(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_i,表明伙伴X_{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人选择,那么我们就邀请该课程设计者开设该课程的组队学习。


(0)

相关推荐

  • 那些可以连读的汉字

    不正是歪,不好是孬,小土是尘,合手是拿,四方木是楞,人工石是砼-- 歪(wāi):不正的合文,可以引申为不正派.斜靠等义. 甭(béng):不用二字的合文,最初为北方方言. 孬(nāo):不好的合文, ...

  • 【优秀作业】粒子群优化算法

    粒子群优化算法 一.概述 粒子群优化算法(Particle Swarm Optimization,PSO)的思想来源于对鸟捕食行为的模仿,最初,Reynolds.Heppner 等科学家研究的是鸟类飞 ...

  • 【优化求解】基于人工鱼群求解多目标优化问题【Matlab 480期】

    一.简介 1.1 觅食行为   指鱼循着食物多的方向游动的一种行为,人工鱼X i X_iXi在其视野内随机选择一个状态X j X_jXj,分别计算它们的目标函数值进行比较,如果发现Y j Y_jYj比 ...

  • B计划《中医诊断》第28课优秀作业

    中医经典魔鬼特训班的作业是手写作业.拍照上传. 手写作业是检查网络学习质量的途径,是学员认真学习.辛勤付出的最好见证,也是养成习惯.磨练意志的最佳途径. 同学们都积极主动.克服困难,严格按要求.高质量 ...

  • B计划《针灸学导论》第1课优秀作业

    中医经典魔鬼特训班的作业是手写作业.拍照上传. 手写作业是检查网络学习质量的途径,是学员认真学习.辛勤付出的最好见证,也是养成习惯.磨练意志的最佳途径. 同学们都积极主动.克服困难,严格按要求.高质量 ...

  • 学生风采|学生优秀作业的评比和展示活动(第三期)

    为了进一步形成良好的作业习惯,提高学生的书写水平,继承和发扬庄小学生作业工整.美观.干净的优良传统,同时也为了强化学校的教学管理,促进学生良好学习品质的养成,让每个孩子学有标杆.做有榜样!学校决将开展 ...

  • 散播焦虑预警 | 看看别人的优秀作业,再看看自己。

    我们非常清楚散播焦虑这种事情会挨骂甚至要被打的. 但是很多时候打击教育也是一种教育,"焦虑"的根本往往是因为你像一个懒瓜一样根本没有任何行动,坐在窗口对着外面沉思:"我到 ...

  • 问花学堂第十二期优秀作业选评

    2021 5.22 问花 景山万春亭(读你) 叹老槐梦破,故国神伤,风雨近千年,飞檐不歇帝王气: 恰云阙南襟,钟楼北倚,江山收一袖,曲槛犹新草木春. 王永江:怀古写今,脉络清晰,结句有味. 赠王永江老 ...

  • 学生风采|学生优秀作业的评比和展示活动(第五期)

    为了进一步形成良好的作业习惯,提高学生的书写水平,继承和发扬庄小学生作业工整.美观.干净的优良传统,同时也为了强化学校的教学管理,促进学生良好学习品质的养成,让每个孩子学有标杆.做有榜样!学校决将开展 ...

  • 初中数学教坛新秀优秀作业及课例设计展播14明德学校尹国凤

    教坛新秀评比 课堂设计 作业展播 尹国凤 2021年2月至4月,初中数学学科依托孔祥骞名师工作室平台,利用名师工作室相关资源,开展了为期两个月的培训.指导.课堂教学评比活动.在此次活动中,参赛教师扎实 ...