基于改进人工鱼群算法的智能组卷的研究

石慧升 王彦志

[摘要]本文针对智能组卷问题的特点对基本人工鱼群算法进行了相应的改进与优化，为群体智能算法应用于组合优化问题进行了一些探索。

[关键词]智能组卷 组合优化问题 人工鱼群算法

引言：随着计算机技术、互联网技术、多媒体技术的迅速发展，计算机广泛应用于各种领域，尤其是在教育领域，计算机科学技术与教育学的融合在计算机辅助教育，方面得到了突飞猛进的发展，本文在对基本人工鱼群算法分析研究的基础上，针对其不足之处研究了人工鱼群算法的改进方法，并采用实现了相应的改进算法。通过对比遗传算法实验结果表明，改进的人工鱼群算法的组卷成功率略低于遗传算法，但是组卷所需时间小于遗传算法且满意度由增加到，它在一定程度上提高了基本人工鱼群算法的寻优精度，为计算机辅助教学系统的实际应用进行了一些探索。

1智能组卷问题的几种智能算法

1.1随机组卷法：随机组卷法是出现最早的组卷算法，其基本思想是：首先根据用户输入的试卷约束标准，利用计算机和数据库技术从试题库中任意抽取一道试题，然后判断该试题是否满足用户设置的难度系统、区分度等约束条件，若满足则添加到试卷中，若不满足，则继续试探直到生产满足用户需求的试卷为止。随机组卷法的优点是简单易实现，缺点是算法执行过程中，抽不到满足要求的试题时，容易陷入死循环、算法精度不高、对试题库要求较高，随机组卷算法要求数据库中的试题量不大，以及试题分布良好;当试题库较大，且分布不是很均匀的情况下，随机组卷的成功率较低。因此，随机组卷的整体效率和组卷成功率均较低，不能很好地满足用户的需要。

1.2遗传算法：遗传算法：其基本思想是借鉴自然界中生物进化过程中适者生存优胜劣的自然淘汰机制而形成的一种自适应优化搜索算法，模拟生物群体的繁殖、交配和变异现象，从一个种群开始，产生更适应环境的一些个体。以此一代一代地迭代，最后随着时间的推移收敛到一个最适应环境的一些个体遗传算法是使用频率较高的一种组卷算法，自提出以来受到国内外学者的广泛关注，在智能组卷问题中，中的一个个体代表一套试卷，个体的适应值大小反应了试卷满足用户要求的程度。适应度与目标函数值的成反比即目标函数值越小，个体的适应度越大，相应生成的试卷则越满足实际用户的要求。遗传算法中选择不同的染色体编码策略对算法性能影响较大，也是将遗传算法应用于某一具体问题时，首要解决的关键问题。常见的编码策略有：二进制编码、十进制编码、混合编码等。在实际应用中应根据需要解决的问题的特点，在进行大量分析研究的基础上选择最适合的编码策略。

2人工鱼群算法理论

人工鱼群算法是李晓晶博士等通过对自然界鱼群的长期观察而提出的一种启发式搜索算法。主要利用鱼群的觅食、追尾、聚群、随机游行为，通过鱼群中单个个体的局部寻优达到最终寻找全局最优解的目的。算法具有全局收敛性好、对初值要求不高、鲁棒性强等优点并且算法只需对目标函数的函数值优劣进行比较，不需要目标函数的适应度等特殊信息，有着较快的收敛速度，能很好解决非线性函数优化等问题。人工鱼模型中的人工鱼是自然界中鱼的一个模拟实体，常用作问题的说明和分析。人工鱼模型可以将人工鱼看成是封装了自身数据和一系列行为的实体。

3人工鱼群算法求解智能组卷问题

求解智能组卷问题是本文重点研究的内容，使用算法进行智能组卷涉及到算法收敛速度和寻找全局最优解的问题。如何使人工鱼群算法快速有效的搜索到全局最优解是本文研究的重要内容。随机组卷法对数据库的要求比较苛刻;遗传算法容易出现早熟现象;故不能很好的满足实际组卷的要求。人工鱼群算法具有实现简单、只需比较目标函数值优劣、初值要求低、收敛速度快的特点，本文将应用于智能组卷系统。尝试对中人工鱼的觅食行为、聚群行为、追尾行为进行设计，实验结果表明基本的人工鱼群算法组卷成功率不高，但满意度相对于随机组卷有所提高。

智能组卷问题在传统的教学中，试卷通常采用教师根据教学大纲和实际教学情况的方式进行组卷的。每次考试前，教师需要花费很多的精力和时间组出一份难易程度适中、能准确检测学生学习情况的试卷。随着计算机辅助教育的广泛推广，计算机技术不仅仅是一门学科，而逐渐成为教学活动中必不可少的教学工具和进行教学管理的重要手段之一。利用计算技术和智能算法进行组卷，有助于减轻教师的负担，使教师将更多的精力用在教学或者科研上。智能组卷系统是指将教育专家的组卷经验和人工智能算法结合起来，根据用户设置的组卷约束参数，利用组卷算法搜索试题库中满足组卷约束条件的试题，从而生成满足用户要求的试卷。智能组卷基础理论主要涉及：组卷目标约束、组卷问题的数学模型、试卷的评价指标、自动组卷算法、算法的编码方式及试题库中试题的结構等内容。目前，自动组卷算法是组卷系统研究的难点与重点，也是本文所要进行讨论的主要内容。

4人工鱼群算法的改进

人工鱼群算法是近几年发展起来的一种新型寻优算法，它主要是通过模拟鱼群的觅食、追尾、聚群等行为进行寻优，利用单个个体局部最优信息，从而寻找全局最优解的目的，基本的人工鱼算法具有良好的跳出局部极值、寻找到全局极值的能力、对算法的初始化要求不高，该算法简单，易于编程程序实现，具有较好的收敛性能。由于人工鱼的行为是局部寻优行为，算法在执行过程中可能会陷于局部极值，难以找到全局最优解。为了提高人工鱼群算法的寻优能力和算法的寻优精度，本文从改进人工鱼的觅食、聚群、追尾行为及引入人工鱼跳跃行为的方向改进，帮助算法更精确、更快的寻找到全局最优解，提局寻优能力。

5结论：本文虽然在人工鱼群算法应用于智能组卷模块的技术实现上做了一定的探索，但今后依然有许多问题有待于做进一步的研究和改进。人工鱼群算法是仿生优化算法的一种，目前对人工鱼群算法的研究还处在初始阶段，有很多不足的地方。寻优的不足之处是，在本系统中当组卷约束条件设置的极端且精度要求高的情况下，组卷成功率有所降低。