人工鱼群算法

1、人工鱼群算法及其在智能组卷中的应用,人工鱼群算法的背景,1.1群智能(SI) Swarm Intelligence (SI)的概念最早由Beni、Hackwood和在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz 在他们的著作Swarm Intelligence: From Natural to Artificial Systems 中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于

2、群智能。,人工鱼群算法的背景,Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。,人工鱼群算法的背景,1.2 人工生命 研究具有某些生命基本特征的人工系统。包括两方面的内容： 1、研究如何利用计算技术研究生物现象； 2、 研究如何利用生物技术研究计算问题。 我们关注的是第二点。 如何利用生物技术研究计算问题是人工生命研究的重要方向，现已有了很多源于生物现象的计算技巧， 例如人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。,2003年李晓磊、邵之江等提出的人工鱼群算法

3、(AFSA)，它利用自上而下的寻优模式模仿自然界鱼群觅食行为，主要利用鱼的觅食、聚群和追尾行为，构造个体底层行为；通过鱼群中各个体的局部寻优，达到全局最优值在群体中凸现出来的目的。在基本运算中引入鱼群的生存机制、竞争机制以及鱼群的协调机制，提高算法的有效效率。,算法介绍,算法介绍,2.1人工鱼群算法描述 在一片水域中，鱼存在的数目最多的地方就是本水域中富含营养物质最多的地方，依据这一特点来模仿鱼群的觅食，聚群，追尾等行为，从而实现全局最优，这就是鱼群算法的基本思想。鱼类的活动中，觅食行为，聚群行为，追尾行为和随机行为与寻优命题的解决有较密切的关系，如何利用简单有效的方式来构造实现这些行为将是算

4、法实现的主要问题。,算法介绍,2.2基本概念 假设在一个n维的目标搜索空间中，有N条组成一个群体的人工鱼，每天人工鱼个体的状态可表示为向量X=（x1,x2,xn）,其中xi（i=1,n）为欲寻优的变量：人工鱼当前所在位置的食物浓度表示为Y=f(X),其中Y为目标函数；人工鱼个体间距离表示为 d=|Xi-Xj |; visual表示人工鱼的感知范围，step为人工鱼移动步长，为拥挤度因子；trynumber表示人工鱼每次觅食最大试探次数。,算法介绍,2.3算法的优点 1）只需比较目标函数值，对目标函数的性质要求不高。 2）对初值的要求不高，随机产生或设为固定值均可。 3）对参数设定的要求不高，容

5、许范围大。 4）具备并行处理能力，寻优速度较快。 5）具备全局寻优能力，能快速跳出局部极值点。,算法介绍,2.4行为描述 （1）随机行为(AF-Random)：指人工鱼在视野内随机移动，当发现食物时，会向食物逐渐增多的方向快速的移动。 （2）觅食行为(AF-prey)：指鱼循着食物多的方向游动的一种行为，人工鱼Xi在其视野内随机选择一个状态Xj，分别计算它们的目标函数值进行比较，如果发现Yj比Yi优，则Xi向Xj的方向移动一步；否则，Xi继续在其视野内选择状态Xj，判断是否满足前进条件，反复尝试trynumber次后，仍没有满足前进条件，则随机移动一步使Xi到达一个新的状态。表达式如下：,算法

6、介绍,float Artificial_ fish：AF_ prey() for(i=0；i Yi retum AF_foodeonsistenee(Xinext )； ,伪代码,算法介绍,(4)追尾行为（AF-follow）指鱼向其可视区域内的最优方向移动的一种行为。人工鱼Xi搜索其视野内所有伙伴中的函数最优伙伴Xj，如果 Yj/ nf Yi,表明最优伙伴的周围不太拥挤，则Xi朝此伙伴移动一步，否则执行觅食行为。,算法介绍,float Artificial_ fish：AF_ follow() Ymax=MAX(f(Xmax),XmaxN(Xi,Visual); nf=|N(Xmax,Vis

7、ual)|; if(Ymax/ nf Yi retum AF_foodeonsistenee(Xinext )； ,伪代码,（5）公告板：是记录最优人工鱼个体状态的地方。每条人工鱼在执行完一次迭代后将自身当前状态与公告板中记录的状态进行比较，如果优于公告板中的状态则用自身状态更新公告板中的状态，否则公告板的状态不变。当整个算法的迭代结束后，输出公告板的值，就是我们所求的最优值。,算法介绍,算法介绍,2.4 算法描述 鉴于以上描述的人工鱼群行为，每条人工鱼探索它当前所处的环境状况和伙伴的状况，从而选择一种行为来实际执行，最终人工鱼集结在几个局部极值周围。一般情况下，在讨论求极大问题时，拥有较大的

8、适应值的人工鱼一般处于值较大的极值域周围，这有助于获取全局极值域，而值较大的极值区域周围一般能集结较多的人工鱼，这有助于判断并获取全局极值。具体的人工鱼群算法步骤如下：,算法介绍,Step1:确定种群规模N，在变量可行域内随机生成N个个体，设定人工鱼的可视域Visual，步长step,拥挤度因子，尝试次数trynumber Step2:计算初始鱼群各个体适应值，取最优人工鱼状态及其值赋给公告板 Step3:个体通过觅食，聚群，追尾行为更新自己，生成新鱼群。 Step4:评价所有个体。若某个体优于公告板，则将公告板更新为该个体。 Step5:当公告板上最优解达到满意误差界内，算法结束，否则转st

9、ep3。,智能组卷介绍,智能组卷问题是一个在一定的约束条件下的多目标参数优化问题,采用传统的数学方法求解相当困难,自动组卷的效率和质量完全取决于试题库设计以及抽题算法的设计。随着计算技术和人工智能的快速发展，以及教育测量理论研究的不断深入，基于教育测量理论的有关计算机辅助设计得到了广泛的应用，其中智能组卷系统的研究与开发得到了越来越多的专家学者的关注。,人工鱼群算法实例,本实例中试卷生成的规则如下： 1、尽可能覆盖考试范围内的所有叶子知识点（覆盖率的下限由教师设定）。若选择知识点A、B为考试范围，而A、B的子树如下：,人工鱼群算法实例,那么考试范围内的所有叶子知识点即为G、H、D、E、F，选题

10、时应尽力覆盖它们。试题和知识点的关系是：如果某试题在C中，则此题就覆盖了G、H两个叶子知识点；如果某试题在A中就覆盖了G、H、D三个叶子知识点；如果某试题在G中，它只覆盖G这一个叶子知识点。 2、试卷的难易度出入尽可能小。教师给出难题、较难题、普通题、较易题、简单题所占分值，试卷中各难度级别的分值和教师设定的分值的出入应在可容忍的范围内。,人工鱼群算法实例,3、试卷的总分和教师设定的总分之间的差距必须在可容忍的范围内，容忍度可设，若容忍度为0，表示必须严格一致。,人工鱼群算法实例,根据实际需求，对人工鱼群算法做了如下具体设计：鱼群的每个个体表示一个候选的解决方案，例如考试范围内有a,b,c,d

11、四道题，那么1001就是搜索空间内的一个状态，它表示选择a,d而不选b,c；一个个体可以是搜索空间内的任何一个状态。两个状态之间的距离就是两个状态之间相异的程度，如一个状态是1100另一个是0001，它们之间共有3位不相同，距离就是3。这里任一状态的适应度计算公式如下： 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

12、为：教师规定的困难、较困难、普通、较简单、简单的题目的分值；L=L1+L2+L3+L4+L5；NL=NL1+NL2+NL3+NL4+NL5；W1、W2和W3为：知识点覆盖率、难度差异和总分差异分别在搜索过程中的重要程度，默认比例是1 : 1 : 1。由上式不难看出在这里适应度函数值是越小越好，所以下面的一些比较公式作了修改。搜索开始后，首先根据搜索空间的大小确定鱼群的种群数量，随机产生鱼群中的个体。,人工鱼群算法实例,然后先进行追尾活动，每条鱼Xi都查看在自己可视域范围内（即距离小于visual，visual根据搜索空间的大小而定）的其它鱼，从中找到适应函数值最小的一个Xj ，其适应度函数值记

13、为Yj，Xj周围可视域内的其它个体数量记为nf，若Yj*nf*Yi （为拥挤度因子，此处取1），则表明Xj周围“食物”较多且不太拥挤，这时Xi对每一个自己和Xj的不同的位重新随机取值（例如Xi为1001，而Xj为1100，那么就对Xi的第2，4位重新随机取值），从而向Xj靠近。追尾活动若不成功，则进行聚群行为，每条鱼都先找出自己周围可视域内的其它鱼，形成一个小鱼群，然后找出这群鱼的中心点，这里中心点的确定方法是，若鱼群中半数以上的鱼在第位上取，则中心点的第位也为1，否则为0，接着采用和前面相同方法查看中心点的“食物”是否较多，是否拥挤，据此决定是否向中心点靠近。,人工鱼群算法实例,如果聚群失败就进行觅食活动，“鱼”随机从自身取出visual个位（visual为可视域），对其进行随机变换产生一个新状态，若新状态优于原状态则向新状态移动，否则再次进行觅食活动，重复m次后如果还是没有找到更优的状态则进行随机移动（m视搜索空间大小而定）。算法中设有公告板，每次搜索完成后用公告板同鱼群中最优的个体进行比较，若此个体优于公告板则更新公告板。算法在以下三种情况下结束，1 公