文章/答案/技术大牛

发布

社区首页 >专栏 >干货 | 人工鱼群算法超详细解析附JAVA代码

干货 | 人工鱼群算法超详细解析附JAVA代码

用户1621951

发布于 2019-06-06 03:15:47

1.4K00

代码可运行

文章被收录于专栏：数据魔术师数据魔术师

运行总次数：0

代码可运行

写在前面

说到这个人工鱼群算法，又想起了小编的卢浮宫……在今年年初的美赛中，小编用的就是这个算法，只不过……参加今年美赛的同学都懂的。

好了不扯了，本着学习的心态，还是想把这个算法写一写，给大家科普一下的吧。

01 人工鱼群算法

人工鱼群算法为山东大学副教授李晓磊2002年从鱼找寻食物的现象中表现的种种移动寻觅特点中得到启发而阐述的仿生学优化方案。

1.1 定义

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

人工鱼拥有以下几种典型行为:

(1)觅食行为：一般情况下鱼在水中随机地自由游动,当发现食物时,则会向食物逐渐增多的方向快速游去。

(2)聚群行为: 鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群，鱼聚群时所遵守的规则有三条：

分隔规则：尽量避免与临近伙伴过于拥挤;

对准规则：尽量与临近伙伴的平均方向一致;

内聚规则：尽量朝临近伙伴的中心移动。

(3)追尾行为：当鱼群中的一条或几条鱼发现食物时,其临近的伙伴会尾随其快速到达食物点。

(4)随机行为：单独的鱼在水中通常都是随机游动的，这是为了更大范围地寻找食物点或身边的伙伴。

1.2 算法具体过程

人工鱼群算法实现的步骤：

1. 初始化设置，包括种群规模N、每条人工鱼的初始位置、人工鱼的视野Visual、步长step、拥挤度因子δ、重复次数Trynumber；

2. 计算初始鱼群各个体的适应值，取最优人工鱼状态及其值赋予给公告牌；

3. 对每个个体进行评价，对其要执行的行为进行选择，包括觅食Pray、聚群Swarm、追尾Follow和评价行为bulletin；

4. 执行人工鱼的行为，更新自己，生成新鱼群；

5. 评价所有个体。若某个体优于公告牌，则将公告牌更新为该个体；

6. 当公告牌上最优解达到满意误差界内或者达到迭代次数上限时算法结束，否则转步骤3。

1.3 算法流程图

1.4 算法伪代码

结合上面的流程图，伪代码很容量理解了。

02 参数解析

人工鱼群算法有5个基本参数：群规模N、人工鱼的视野Visual、步长Step、拥挤度因子δ、重复次数Trynumber。

2.1 视野Visual

动物的观察力是及其深奥的，它可以很快的洞察到周边的物体，鱼类的视野中分为连续型视野和离散型视野两类。应用如下方法实现虚拟人工鱼的视觉：

图2.1(a)表示具有连续型视野的一条假设的人工鱼个体，它能看到的区域 Visual 为以现在位置 Xi为圆心一定距离为半径的圆形区域，地点 Xj为它在一个时候巡视到的视点种另一地方，如果这个地点的食物量比之前地方的多，就决定去这个地方前进步长的随机数达到地点 Xnext；

人工鱼的离散型视野为与节点位置 Xi 相邻且相通的所有节点，如图 2.1(b)所示，根据判断边的代价来选择下一步位置 Xnext。

由于视野对算法中个行为都有较大影响，因此，它的变化对收敛性能影响也比较复杂。

当视野范围较小时，人工鱼的觅食行为和随机行为比较突出；视野范围较大时，人工鱼的追尾行为和聚群行为将变得比较突出，相应的算法的复杂度也会有所上升。

总的来说：视野越大，越容易使人工鱼发现全局最优解并收敛。

2.2 步长Step

对于固定步长，随着步长的增加，收敛的速度得到了一定的加速，但在超过一定的范围后，有使得收敛速度减缓，步长过大时会出现震荡现象而大大影响收敛速度。

采用随机步长的方式在一定程度上防止了震荡现象的发生，并使得该参数的敏感度大大降低了，但最快的收敛速度还是最优固定步长的收敛速。

所以，对于特定的优化问题，我们可以考虑采用合适的固定步长或者变尺度方法来提高收敛速度。

2.3 群规模N

人工鱼的数目越多，跳出局部最优解的能力越强，同时，收敛的速度也越快。

当然，付出的代价就是算法每次迭代的计算量也越大，因此，在使用过程中，满足稳定收敛的前提下，应当尽可能的减少个体数目。

2.4 尝试次数Trynumber

尝试次数越多，人工鱼的觅食行为能力越强，收敛的效率也越高。

在局部极值突出的情况下，应该适当的减少以增加人工鱼随机游动的概率，克服局部最优解。

2.5 拥挤度因子δ

在求极大值问题中，δ=1/(αnmax),α∈(0,1]δ=1/(αnmax),α∈(0,1]；在求极小值问题中，δ=αnmax,α∈(0,1]δ=αnmax,α∈(0,1]。其中α为极值接近水平， nmax为期望在该邻域内聚集的最大人工鱼数目。

拥挤度因子与nf相结合，通过人工鱼是否执行追尾和聚群行为对优化结果产生影响。以极大值为例（极小值的情况正好与极大值相反），δ越大，表明允许的拥挤程度越小，人工鱼摆脱局部最优解的能力越强；但是收敛速度会有所减缓，这主要因为人工鱼在逼近最优解的同时，会因避免过分拥挤而随机走开或者受其他人工鱼的排斥作用，不能精确逼近极值点。

可见，虽然δ的引入避免了人工鱼过度拥挤而陷入局部最优解，但是另一方面，该参数会使得位于极值点附件的人工鱼之间存在相互排斥的影响，而难以想极值点精确逼近。

所以，对于某些局部极值不是很严重的具体问题，可以忽略拥挤的因素，从而在简化算法的同时也加快算法的收敛速度和提高结果的精确程度。

2.6 小结

1.群规模：N越大收敛越快，越容易寻得全局最优解，但是计算量越大；

2.感知范围：视野越大，越易发现全局最优解；

3.步长：决定收敛速度；

4.拥挤因子：适当选择可避免局部最优

5.重复次数：越大收敛越快，可调整随机游走概率，克服局部最优解。

03 四种基本行为

人工鱼有四种基本行为，包括觅食Pray、聚群Swarm、追尾Follow和评价行为bulletin。

3.1 觅食行为

这是鱼趋向食物的一种活动，一般认为它是通过视觉或味觉来感知水中的食物量或食物浓度来选择行动的方向。

设置人工鱼当前状态，并在其感知范围内随机选择另一个状态，如果得到的状态的目标函数大于当前的状态，则向新选择得到的状态靠近一步，反之，重新选取新状态，判断是否满足条件。

选择次数达到一定数量后，如果仍然不满足条件，则随机移动一步。

3.2 聚群行为

大量或少量的鱼聚集成群，进行集体觅食和躲避敌害，这是它们在进化过程中形成的一种生存方式。

人工鱼探索当前邻居内的伙伴数量，并计算伙伴的中心位置，然后把新得到的中心位置的目标函数与当前位置的目标函数相比较，如果中心位置的目标函数优于当前位置的目标函数并且不是很拥挤，则当前位置向中心位置移动一步，否则执行觅食行为。

鱼聚群时会遵守两条规则：一是尽量向邻近伙伴的中心移动，二是避免过分拥挤。

3.3 追尾行为

当某一条鱼或几条鱼发现食物时，它们附近的鱼会尾随而来，导致更远处的鱼也会尾随过来。

人工鱼探索周围邻居鱼的最优位置，当最优位置的目标函数值大于当前位置的目标函数值并且不是很拥挤，则当前位置向最优邻居鱼移动一步，否则执行觅食行为。

3.4 随机行为

它是觅食行为的一个缺省行为，指人工鱼在视野内随机移动。当发现食物时，会向食物逐渐增多的方向快速的移动。

04 行为选择

公告牌是记录最优人工鱼个体状态的地方。每条人工鱼在执行完一次迭代后将自身当前状态与公告牌中记录的状态进行比较，如果优于公告牌中的状态则用自身状态更新公告牌中的状态，否则公告牌的状态不变。

当整个算法的迭代结束后，公告牌的值就是最优解。

行为评价是用来反映鱼自主行为的一种方式，在解决优化问题时选用两种方式评价：一种是选择最优行为执行；另一种是选择较优方向。

对于解决极大值问题，可以使用试探法，即模拟执行群聚、追尾等行为，然后评价行动后的值选择最优的来执行，缺省的行为为觅食行为。

一般通过试探法，模拟执行上述几种行为，评价后选择最大者实行；

05 终止条件

迭代终止条件：

1. 通常的方法是判断连续多次所得值得均方差小鱼允许的误差；

2. 或判断聚集于某个区域的人工鱼的数目达到某个比例；

3. 或连续多次所得的均值不超过已寻找的极值；

4. 或限制最大迭代次数。

若满足终止条件，则输出公告牌的最优记录；否则继续迭代。

06 实现代码JAVA

以下代码是实现求解一个二元函数最优值问题的。代码下载移步留言区。

主函数测试类

 1package AFAS_PACK;
 2
 3import java.io.IOException;
 4
 5public class mainTest {
 6
 7    /**
 8     * @param args
 9     * @throws IOException
10     * @author sun 
11     */
12    public static void main(String[] args) throws IOException {
13        //int fishNum, int tryTime, int dim, double step, double delta, double visual   
14        System.out.println("begin");
15        AFAS run = new AFAS(10,5,2,5,0.2,10);
16          run.doAFAS(40 );//括号内为迭代次数
17    }
18
19}

人工鱼类

 1package AFAS_PACK;
 2
 3import java.io.IOException;
 4
 5public class Fish {
 6    public int dim;                   //每条鱼的维度
 7    public int[] x;                //每条鱼的具体多维坐标
 8    public double fit;                //鱼的适应值，浓度
 9    public int visaul;             //每条鱼的视野
10    public final double[] H = new double[256];
11    public final double[] W = new double[256];
12
13
14    public Fish(int dim, int visaul) throws IOException {
15        super();
16        this.dim = dim;
17        this.visaul = visaul;
18        x = new int[dim];
19        for(int i=0;i<dim;i++)
20            x[i] = (int) Math.floor(256*Math.random());
21        fit = 0;
22        //init();
23    }
24    /*getfit = newfunction(this.x[0],this.x[1]);*/
25
26
27    public double distance(Fish f)
28    {
29        double a = 0;
30        for(int i=0;i<dim;i++)
31        {
32            if(this.x[i]-f.x[i]==0)
33                a = 0.00001;
34            else 
35                a += (this.x[i]-f.x[i])*(this.x[i]-f.x[i]);
36        }
37        return Math.sqrt(a);
38    }
39
40
41    public  double newfunction(int[] w) throws IOException {          
42
43        return -(w[0]*w[0]-160*w[0]+640+w[1]*w[1]-260*w[1]+16900);
44
45    }
46}

人工鱼群算法类

  1package AFAS_PACK;
  2
  3
  4import java.io.IOException;
  5import java.util.Date;
  6
  7
  8
  9public class AFAS {
 10    //鱼群数目
 11        private int fishNum;
 12        //尝试次数
 13        private int tryTime;
 14        //维度
 15        private int dim;
 16        //人工鱼移动步长
 17        private int step;
 18        //拥挤度因子
 19        private double delta;
 20        //视野范围
 21        private int visual;
 22        //人工鱼群、范围内最佳鱼，遍历时的下一条鱼
 23        Fish[] fish;
 24        Fish bestfish;
 25        Fish[] nextfish;
 26        //遍历索引
 27        int index;
 28        double[][] vector;
 29        private int[] choosed;
 30        //范围内鱼群数目 fishCount
 31        public int scopelength;
 32
 33        public AFAS(){
 34
 35        }
 36        public AFAS(int fishNum, int tryTime, int dim, int step, double delta, int visual) throws IOException 
 37        {
 38            super();
 39            this.fishNum = fishNum;
 40            this.tryTime = tryTime;
 41            this.dim = dim;
 42            this.step = step;
 43            this.delta = delta;
 44            this.visual = visual;
 45            fish = new Fish[fishNum];
 46            nextfish = new Fish[3];
 47            vector = new double[fishNum][dim];
 48            choosed = new int[fishNum];
 49            index = 0;
 50            init();
 51        }
 52        public void doAFAS(int num) throws IOException 
 53        {  
 54            long startTime = new Date().getTime();
 55            double a = 0.0;
 56            int count = 1;                          //计算查找次数
 57            int len = 0;
 58            while(count<=num)
 59            {
 60
 61                 for(int i=0; i<fishNum; i++)
 62                 {
 63                     prey(i);
 64                     swarm(i);
 65                     follow(i);
 66                     bulletin(i);
 67                     System.out.println("第"+count+"遍第"+i+"条鱼结束");
 68                 }    
 69                 System.out.println(count+"当前最优值："+bestfish.fit);
 70                 for(int i=0; i<dim; i++)
 71                 {
 72                     System.out.print("位置"+(i+1)+":  "+bestfish.x[i]);  
 73                 }
 74                 System.out.println();
 75                 count++;
 76                 System.out.println("step:"+step+"    visaul:"+visual);
 77
 78            }
 79            System.out.println("最优值："+bestfish.fit);
 80            for(int i=0; i<dim; i++)
 81            {
 82                System.out.print("位置"+(i+1)+":  "+bestfish.x[i]);  
 83            }
 84            long endTime = new Date().getTime();
 85            System.out.println("本程序运行计时： "+(endTime-startTime)+" 毫秒。");
 86        }
 87
 88        private void bulletin(int i) throws IOException {
 89            Fish maxfish = new Fish(dim,visual);
 90            maxfish = nextfish[0];
 91            for(int j=0;j<3;j++)
 92            {
 93                if(nextfish[j].fit>maxfish.fit && nextfish[j].x[0]!=0 && nextfish[j].x[1]!=0)
 94                {
 95                    maxfish = nextfish[j];
 96                }
 97            }
 98            if(maxfish.fit<fish[i].fit)
 99            {
100                return ;
101            }
102            fish[i] = maxfish;
103            if(maxfish.fit>bestfish.fit)
104                bestfish = maxfish;
105        }
106        private void follow(int i) throws IOException {
107            nextfish[2] = new Fish(dim,visual);
108            Fish minfish = new Fish(dim,visual);                    // 中心位置
109            minfish = fish[i];
110            Fish[] scope = getScopefish(i);
111            int key = i;
112            if(scope!=null)
113            {
114                for(int j=0;j<scope.length;j++)
115                {
116                    if(scope[j].fit<minfish.fit)
117                    {
118                        minfish = scope[j];
119                        key = j;
120                    }
121                }
122                if(minfish.fit>=fish[i].fit)
123                    prey(i);
124                else{
125                    Fish[] newScope = getScopefish(key);
126                    if(newScope!=null)
127                    {
128                        if(newScope.length*minfish.fit<delta*fish[i].fit)
129                        {
130                            double dis = fish[i].distance(minfish);
131                            for(int k=0;k<dim;k++)
132                            {
133                                nextfish[2].x[k] = (int) (fish[i].x[k]+(minfish.x[k]-fish[i].x[k])*step*Math.random()/dis);                                 
134                            }
135                            nextfish[2].fit = nextfish[2].newfunction(nextfish[2].x);
136                        }
137                        else prey(i);
138                    }
139                    else prey(i);
140                }
141            }
142            else prey(i);
143
144        }
145        private void swarm(int i) throws IOException {                               //swam  start
146            nextfish[1] = new Fish(dim,visual);
147            int[] center = new int[dim];                    // 中心位置
148            for(int j=0;j<dim;j++)
149                center[j] = 0;
150            Fish[] scope = getScopefish(i);
151            if(scope!=null)
152            {
153                for(int j=0;j<scope.length;j++)                     // 计算人工鱼的中心位置
154                {
155                    for( i=0; i<dim; ++i )
156                        center[i] += scope[j].x[i];
157                }
158                for( i=0; i<dim; i++ )
159                    center[i] /= scope.length;                               // 人工鱼的中心位置
160                //满足条件
161                double dis=0.0;
162                Fish centerfish = new Fish(dim,visual);
163                centerfish.x = center;
164                centerfish.fit = centerfish.newfunction(centerfish.x);
165                dis = fish[i].distance(centerfish);
166                if(centerfish.fit>fish[i].fit && scope.length*centerfish.fit<delta*fish[i].fit)
167                {
168                    for(int j=0;j<dim;j++)
169                    {
170                        nextfish[1].x[j] = (int) (fish[i].x[j]+(centerfish.x[j]-fish[i].x[j])*step*Math.random()/dis);
171
172                    }
173                    nextfish[1].fit = nextfish[1].newfunction(nextfish[1].x);
174                }
175                else  prey(i); 
176            }
177            else  prey(i); 
178        }                                               //swam  end
179
180
181
182        private void prey(int i) throws IOException  {                      //prey start
183
184            Fish newfish = new Fish(dim,visual);
185            newfish.fit = 0;
186            nextfish[0] = new Fish(dim,visual);
187            for(int k=0; k<tryTime; k++ )           // 进行try_number次尝试
188            {
189                for(int j=0; j<dim; j++ )
190                {
191                    newfish.x[j] = (int) ((2*(Math.random())-1)*visual);
192
193                }
194                newfish.fit = newfish.newfunction(newfish.x);
195
196                if( newfish.fit > fish[i].fit )
197                {
198                    double dis = fish[i].distance(newfish);
199                    for(int j=0; j<dim; j++ )
200                    {
201
202                        nextfish[0].x[j] = (int) (fish[i].x[j]+(newfish.x[j]-fish[i].x[j])*step*Math.random()/dis);
203
204                    }
205                    nextfish[0].fit =nextfish[0].newfunction(nextfish[0].x); 
206                }
207                else
208                {
209
210                    for(int j=0; j<dim; j++)
211                    {
212                        nextfish[0].x[j] = (int) (fish[i].x[j]+visual*(2*(Math.random())-1));
213
214                        nextfish[0].fit = nextfish[0].newfunction(nextfish[0].x);
215
216                    }
217
218                }
219            }
220        }
221        private Fish[] getScopefish(int i) {
222            int num = 0;
223            for(int j=0;j<fishNum;j++)
224            {
225                choosed[j] = -1;
226                if(fish[i].distance(fish[j])<visual)
227                {
228                    choosed[j] = i;
229                    num++;
230                }
231            }
232            if(num!=0)
233            {
234                Fish[] scope = new Fish[num];
235                int k = 0;
236                for(int j=0;j<fishNum;j++)
237                {
238                    if(choosed[j]!=-1)
239                        scope[k++] = fish[choosed[j]];
240                }
241                return scope;
242            }
243            return null;
244        }                                                    //prey  end
245        private void init() throws IOException {
246            for(int i=0;i<fishNum;i++)
247            {
248                fish[i] = new Fish(dim,visual);
249                fish[i].fit = fish[i].newfunction(fish[i].x);
250            }
251            bestfish = new Fish(dim,visual);
252            bestfish.fit = -999999;
253        }
254}