人工鱼群算法全解

人工鱼群算法（AFSA）及其在智能组卷中的应用自动化工程学院内容纲要•1.AFSA背景•2.AFSA概述•3.AFSA实例人工鱼群算法的背景•1.1群智能(SI)SwarmIntelligence(SI)的概念最早由Beni、Hackwood在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz在他们的著作《SwarmIntelligence:FromNaturaltoArtificialSystems》中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。人工鱼群算法的背景Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群、鱼群都是Swarm的典型例子。人工鱼群算法的背景•1.2人工生命具有某些生命基本特征的人工系统。包括两方面的内容：1、研究如何利用计算技术研究生物现象；2、研究如何利用生物技术研究计算问题。我们关注的是第二点。如何利用生物技术研究计算问题是人工生命研究的重要方向，现已有了很多源于生物现象的计算技巧，例如人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。•2003年李晓磊、邵之江等提出的人工鱼群算法(AtificialFish-SwarmAlgorithm，AFSA)，它利用自上而下的寻优模式模仿自然界鱼群觅食行为，主要利用鱼的觅食、聚群和追尾行为，构造个体底层行为；通过鱼群中各个体的局部寻优，达到全局最优值在群体中凸现出来的目的。在基本运算中引入鱼群的生存机制、竞争机制以及鱼群的协调机制，提高算法的有效效率。人工鱼群算法概述人工鱼群算法概述•2.1AFSA基本思想在一片水域中，鱼存在的数目最多的地方就是本水域中富含营养物质最多的地方，依据这一特点来模仿鱼群的觅食，聚群，追尾等行为，从而实现全局最优，这就是鱼群算法的基本思想。鱼类的活动中，觅食行为，聚群行为，追尾行为和随机行为与寻优命题的解决有较密切的关系，如何利用简单有效的方式来构造实现这些行为将是算法实现的主要问题。人工鱼群算法概述•2.2AFSA基本概念假设在一个n维的目标搜索空间中，有N条组成一个群体的人工鱼，每天人工鱼个体的状态可表示为向量X=（x1,x2,……xn）,其中xi（i=1,……n）为欲寻优的变量：人工鱼当前所在位置的食物浓度表示为Y=f(X),其中Y为目标函数；人工鱼个体间距离表示为d=||Xi-Xj||;visual表示人工鱼的感知范围，step为人工鱼移动步长，δ为拥挤度因子；trynumber表示人工鱼每次觅食最大试探次数。人工鱼群算法概述•2.3AFSA行为描述（1）随机行为(AF-Random)：指人工鱼在视野内随机移动的行为。（2）觅食行为(AF-prey)：指鱼循着食物多的方向游动的一种行为，人工鱼Xi在其视野内随机选择一个状态Xj，分别计算它们的目标函数值进行比较，如果发现Yj比Yi优，则Xi向Xj的方向移动一步；否则，Xi继续在其视野内选择状态Xj，判断是否满足前进条件，反复尝试trynumber次后，仍没有满足前进条件，则随机移动一步使Xi到达一个新的状态。表达式如下：人工鱼群算法概述floatArtificial_fish：：AF_prey(){for(i=0；itrynumber；i++){Xj=Random(N(Xi，Visual))；if(YiYj);else;}retumAF_foodeonsistenee(Xinext)；}Random(N(Xi，Visual))表示在Xi的Visual一距离的邻域内随机取一个邻居．ijijiinextXXXXstepRandomXX)()(RstepandomXXiinext伪代码•（3）聚群行为（AF-swarm）：鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群。鱼聚群时所遵守的规则有三条:分隔规则:尽量避免与临近伙伴过于拥挤;对准规则:尽量与临近伙伴的平均方向一致;内聚规则:尽量朝临近伙伴的中心移动。人工鱼Xi搜索其视野内的伙伴数目nf及中心位置Xc，若Yc/nfδYi，表明伙伴中心位置状态较优且不太拥挤，则Xi朝伙伴的中心位置移动一步，否则执行觅食行为：人工鱼群算法概述人工鱼群算法概述floatArtificial_fish：：AF_swarm(){nf=|N(Xi,Visual)|;//Xi为中心，visual距离领域内的伙伴总数Xc=Center(N(Xi,Visul));//Xi附近所有nf个伙伴的中心位置if(Yc/nfδYi&&YiYc);elseAF_prey();retumAF_foodeonsistenee(Xinext)；}iciciinextXXXXstepRandomXX)(伪代码人工鱼群算法概述•(4)追尾行为（AF-follow）指鱼向其可视区域内的最优方向移动的一种行为。人工鱼Xi搜索其视野内所有伙伴中的函数最优伙伴Xj，如果Yj/nfδYi,表明最优伙伴的周围不太拥挤，则Xi朝此伙伴移动一步，否则执行觅食行为。人工鱼群算法概述•floatArtificial_fish：：AF_follow()•{Ymax=MAX(f(Xmax)),Xmax∈N(Xi,Visual);•nf=|N(Xmax,Visual)|;•if(Ymax/nfδYi&&YiYmax)•;•else•AF_prey();•retumAF_foodeonsistenee(Xinext)；•}imaximaxiinextXXXXstepRandomXX)(伪代码•（5）公告板：是记录最优人工鱼个体状态的地方。每条人工鱼在执行完一次迭代后将自身当前状态与公告板中记录的状态进行比较，如果优于公告板中的状态则用自身状态更新公告板中的状态，否则公告板的状态不变。当整个算法的迭代结束后，输出公告板的值，就是我们所求的最优值。人工鱼群算法概述人工鱼群算法概述•2.4具体算法步骤鉴于以上描述的人工鱼群行为，每条人工鱼探索它当前所处的环境状况和伙伴的状况，从而选择一种行为来实际执行，最终人工鱼集结在几个局部极值周围。一般情况下，在讨论求极大问题时，拥有较大的适应值的人工鱼一般处于值较大的极值域周围，这有助于获取全局极值域，而值较大的极值区域周围一般能集结较多的人工鱼，这有助于判断并获取全局极值。具体的人工鱼群算法步骤如下：算法介绍•Step1:确定种群规模N，在变量可行域内随机生成N个个体，设定人工鱼的可视域Visual，步长step,拥挤度因子δ，尝试次数try_numberStep2:计算初始鱼群各个体适应值，取最优人工鱼状态及其值赋给公告板Step3:个体通过觅食，聚群，追尾行为更新自己，生成新鱼群。Step4:评价所有个体。若某个体优于公告板，则将公告板更新为该个体。Step5:当公告板上最优解达到满意误差界内，算法结束，否则转step3。人工鱼群算法实例•智能组卷问题是一个在一定的约束条件下的多目标参数优化问题,采用传统的数学方法求解相当困难,自动组卷的效率和质量完全取决于试题库设计以及抽题算法的设计。随着计算技术和人工智能的快速发展，以及教育测量理论研究的不断深入，基于教育测量理论的有关计算机辅助设计得到了广泛的应用，其中智能组卷系统的研究与开发得到了越来越多的专家学者的关注。人工鱼群算法实例•本实例中试卷生成的规则如下：•1、尽可能覆盖考试范围内的所有叶子知识点（覆盖率的下限由教师设定）。若选择知识点A、B为考试范围，而A、B的子树如下：ACDGHBEF人工鱼群算法实例那么考试范围内的所有叶子知识点即为G、H、D、E、F，选题时应尽力覆盖它们。试题和知识点的关系是：如果某试题在C中，则此题就覆盖了G、H两个叶子知识点；如果某试题在A中就覆盖了G、H、D三个叶子知识点；如果某试题在G中，它只覆盖G这一个叶子知识点。•2、试卷的难易度出入尽可能小。教师给出难题、较难题、普通题、较易题、简单题所占分值，试卷中各难度级别的分值和教师设定的分值的出入应在可容忍的范围内。人工鱼群算法实例•3、试卷的总分和教师设定的总分之间的差距必须在可容忍的范围内，容忍度可设，若容忍度为0，表示必须严格一致。人工鱼群算法实例•根据实际需求，对人工鱼群算法做了如下具体设计：鱼群的每个个体表示一个候选的解决方案，例如考试范围内有a,b,c,d四道题，那么1001就是搜索空间内的一个状态，它表示选择a,d而不选b,c；一个个体可以是搜索空间内的任何一个状态。两个状态之间的距离就是两个状态之间相异的程度，如一个状态是1100另一个是0001，它们之间共有3位不相同，距离就是3。这里任一状态的适应度计算公式如下：•F=[UC/NC]*W1+[(|L1-NL1|+|L2-NL2|+|L3-NL3|+|L4-NL4|+|L5-NL5|)/NL]*W2+[(L-NL)/NL]*W3人工鱼群算法实例•其中UC为：需覆盖而未覆盖的叶子知识点数量；NC为：考试范围内叶子知识点总量；L1至L5为：此状态下困难、较困难、普通、较简单、简单的题目的分值；NL1至NL5为：教师规定的困难、较困难、普通、较简单、简单的题目的分值；L=L1+L2+L3+L4+L5；NL=NL1+NL2+NL3+NL4+NL5；W1、W2和W3为：知识点覆盖率、难度差异和总分差异分别在搜索过程中的重要程度，默认比例是1:1:1。由上式不难看出在这里适应度函数F值是越小越好，所以下面的一些比较公式作了修改。搜索开始后，首先根据搜索空间的大小确定鱼群的种群数量，随机产生鱼群中的个体。人工鱼群算法实例•首先进行追尾活动，每条鱼Xi都查看在自己可视域范围内（即距离小于visual，visual根据搜索空间的大小而定）的其它鱼，从中找到适应函数值最小的一个Xj，其适应度函数值记为Yj，Xj周围可视域内的其它个体数量记为nf，若Yj*nfδ*Yi（δ为拥挤度因子，此处取1），则表明Xj周围“食物”较多且不太拥挤，这时Xi对每一个自己和Xj的不同的位重新随机取值（例如Xi为1001，而Xj为1100，那么就对Xi的第2，4位重新随机取值），从而向Xj靠近。追尾活动若不成功，则进行聚群行为。人工鱼群算法实例•聚群行为：每条鱼都先找出自己周围可视域内的其它鱼，形成一个小鱼群，然后找出这群鱼的中心点，这里中心点的确定方法是，若鱼群中半数以上的鱼在第ｉ位上取１，则中心点的第ｉ位也为1，否则为0，接着采用和前面相同方法查看中心点的“食物”是否较多，是否拥挤，据此决定是否向中心点靠近。如果聚群行为不成功，则进行觅食活动。人工鱼群算法实例•觅食活动：“鱼”随机从自身取出visual个位（visual为可视域），对其进行随机变换产生一个新状态，若新状态优于原状态则向新状态移动，否则再次进行觅食活动，重复trynumber次后如果还是没有找到更优的状态则进行随机移动（trynumber视搜索空间大小而定）。人工鱼群算法实例•算法中设有公告板，每次搜索完成后用公告板同鱼群中最优的个体进行比较，若此个体优于公告板则更新公告板。算法在以下三种情况任何一种情况下结束，1公告板达到教师的要求；2搜索次数达到规定的最大搜索次数；3搜索时间达到规定的最大搜索时间。人工鱼群算法概述•综上，AFSA的优点有以下几点：1）只需比较目标函数值，对目标函数的性质要求不高。2）对初值的要求不高，随机产生或设为固定值均可。3）对参数设定的要求不高，容许范围大。4）具备并行处理能力，寻优速度较快。5）具备全局寻优能力，能快速跳出局部极值点。