应用人工生命模型Bug／BACO求解组卷问题研究

钱 乾

(安徽工程大学计算机与信息学院，安徽 芜湖241000安徽商贸职业技术学院电子信息工程系，安徽 芜湖241002)

周鸣争

（安徽工程大学计算机与信息学院，安徽 芜湖241000）

程美英

（安徽商贸职业技术学院电子信息工程系，安徽 芜湖240002）

赵传信

（安徽师范大学数学与计算机学院，安徽 芜湖241002）

自20世纪90年代初意大利学者Dorigo M提出蚁群优化算法（ACO）以来，许多学者致力于该算法的改进。文献［1］将遗传算法交替在搜索空间及解空间中工作的方式与使用自定义搜索空间的连续域蚁群优化算法相集合，提出了二进制蚁群优化算法（或称二元蚁群优化算法），并在连续域（如函数优化）及离散域（0／1背包问题、组卷问题、二次分配问题等）［2］优化问题中均得到了较好的应用。“探索和利用”的冲突是二元蚁群优化算法固有的缺陷，而拥塞控制策略［3］、捕食与区域划分算子［4］、搜索偏向控制函数［5］等的引入可以弥补其早熟收敛的缺陷，但这在一定程度上导致算法评价次数的增加，从算法执行时间来看，这种伪并行（顺序）算法的计算复杂性严重阻碍其在大规模优化问题中的应用。下面，笔者从人工生命的角度对二元蚁群优化算法重新进行描述。

1 Bug－BACO算法

图1 一维Bug人工生命模型

图2 Bug－BACO算法原理图

假设有一个人工生命叫作Bug，它爬行在一条长长的纸带上（见图1，其实质是一个一维二元细胞自动机），纸带上每个方格的颜色 ｛黑、白｝可用细胞状态0／1代替（黑色代表细胞的状态为0，白色代表细胞的状态为1），Bug遍历完一趟图1的纸带，实质上就是完成了一次对候选解的选择过程。因此，可以将图1的一维二元细胞自动机引入到蚁群算法中，让蚂蚁在图1所示的一维网格上移动，将蚂蚁遵循的数学模型作为细胞自动机的转换函数。探索和利用的冲突是蚁群优化固有的缺陷，为防止算法陷入局部最优，在算法中引入了更多的随机扰动因素，提出了基于Bug人工生命模型的二元蚁群优化算法Bug－BACD算法（见图2）。

假设在一条直线上均匀分布着L个细胞，蚂蚁种群的规模为m；细胞状态集合Q∈｛0，1｝，∀t，蚂蚁k，第i（i＝1，2，…，L）个细胞状态0上分布的信息素为第i个细胞状态1上分布的信息素为：Pp为预先设定的一个扰动概率，任意时刻，若则蚂蚁选择状态0（即Q ＝0），反之选择状态1（即Q＝1）。经过t时刻，当所有蚂蚁完成一次对细胞内部状态的选择后，细胞内部的信息素按下列公式进行更新调整：

为了改善算法的全局收敛性，将信息素设置了上、下界，若信息素更新之后大于τmax，则将其置为τmax，反之将其置为τmin。

2 Bug－BACO算法求解组卷问题

2.1 组卷问题数学模型描述

智能组卷指计算机按照用户输入的要求，自动抽取满足用户需求的一套试卷的过程。试卷中的每一道题目，由n维向量来描述（ai1，ai2，ai3，ai4，ai5，ai6…，ain），其中，ai1为第i题的题型；ai2为第i题的题分；ai3为题目难度；ai4为教学要求；ai5为知识单元；ai6为估时；…。一份试卷就决定一个m×n矩阵Sg＝（aij）n×m，其中，m 是试卷所含的题目数，则组卷的数学模型可描述如下［6］：

表1 Bug－BACO算法求解组卷问题试验结果表

2.2 Bug－BACO算法求解组卷问题性能分析

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量，而度量一个程序的执行时间通常有事前统计法和事后统计法。笔者使用事后统计方法中的cl ock／CLOCKS＿PER＿SEC，且所有程序均在3.0 GHZ、3.25 GB内存的计算机上运行。题库规模为500（题型为填空题、选择题、判断题、改错题和编程题，每种题型各100道），卷面总分为100，时间100 min，试卷难度0.6，教学要求分值分布为（识记10分、理解35分、综合35分、应用20分），知识单元共10个，其相应的知识分值分布为（10分、4分、10分、10分、14分、8分、12分、8分、10分、14分），试卷中各种题型要求的个数分别为：填空题10道、选择题10道、编程题2道、改错题5道、判断题5道。假设种群规模m＝30，ρ＝0.95，Pp＝0.5，每隔10代运行10次，求解平均最优值及平均运行时间（以毫秒ms为计量单位）如表1所示。

由表1可知，利用Bug－BACO算法虽然能在多项式时间内逃离局部最优的陷阱并得到问题的最优满意解，但是实际运行算法得到平均最优值19.5547的时间为373837.2 ms，这在实际应用中用户是无法忍受的。因此，降低算法的运行时间成为首要解决的关键问题。

3 Bug－PBACO算法

3.1 Bug－PBACO算法模型

图3 Bug－BACO算法基本模型

并行策略的选择对蚁群算法的并行实现至关重要。目前蚁群算法的并行策略有如下5种［7］，即并行独立蚁群、并行交互蚁群、并行蚂蚁、解决方案元素的并行评估以及蚂蚁和解决方案元素的并行结合。根据研究需要，笔者采用并行蚂蚁的并行策略。假设并行机群中，处理器的数目为n，种群规模为m，细胞状态集合Q＝｛0，1｝，Pp为预先设定的一个概率。初始时刻，主处理机将原始蚂蚁群体平分为n个子种群，每个子种群的规模为m／n，将n个子种群发送到n个处理机中，各处理机独立运行Bug人工生命模型二元蚁群优化算法，并将各子种群的最优个体适应值发送给主处理机，主处理机收集整理并得出全局最优解（见图3）。

3.2 Bug－PBACO算法求解组卷问题计算时间分析

假设并行群集系统中共用m只蚂蚁，问题的规模为题库的规模lc·vm（其中，vm为题型数目；lc为题库中每种题型的个数），并行机群中处理机的个数为n，且Bug－BACO算法和Bug－PBACO算法都迭代了相同的次数Nc，所需要的时间为Times（m，Nc），那么针对Bug－PBACO算法，每个处理机上的计算时间为Times（m，Nc）／n，因各处理机独立并行地工作，不进行信息的交换，故迭代次的Bug－PBACO算法所花费的时间为Time（n）＝Times（m，Nc）。

设ts为算法启动时间，tw为传输每个字节的时间，P为传输的信包长度，则进行一次群集通信所需要的时间为（ts＋P·tw）·log n，因在Bug－PBACO算法中只有2次群集通信，即初始时刻主处理机向各子种群散发信息素初始矩阵以及结束时主处理机收集各子种群的最优适应值，假设个体最优适应值所占的字节为2，共有（lc·vm·2＋2）字节，那么一次迭代的时间为Tc＝［2·ts＋（lc·vm·tw）］·log n，由此，整个Bug－PBACO算法运行的时间为：

3.3 处理机数目的选择及算法的加速比

式（2）反映了Bug－PBACO算法的并行计算时间与处理机数目之间的函数关系，由此可以通过对Time（n）关于变量n求导来求解算法应该选择最优处理机的个数，从而使得计算时间最短。

令Time′（n）＝0，即：

则算法的加速比：

因Bug－BACO算法求解组卷问题的时间复杂度为O（Nc·m·lc·vm），带入式（5）中，则有：

由式（5）可知，随着处理机数目的增加，加速比呈递增趋势，算法的效率反而减小。

4 仿真试验

题库规模为500，计算机配置时节点之间通过以太网互连，每个节点均安装windows操作系统及MPI并行函数库，采用C语言绑定MPI函数库进行测试，相关配置信息可参考文献［8］。

试验中，处理机数目n＝4，每个处理机上的蚂蚁数目为30，ρ＝0.95，Pp＝0.5，每隔10代运行10次。

表2所示为运行Bug－PBACO算法求解组卷问题的试验结果。从表2可以看出，对Bug－BACO算法实施并行化处理技术能有效地缩短算法的运行时间，同时没有降低算法的求解质量。

表2 运行Bug－PBACO求解组卷问题试验结果

5 结 语

Bug－BACO算法作为蚁群算法改进的一种，对于中小规模的优化应用问题，一般能够在许可的时间内得到满意解，而对于大规模的优化应用问题，如组卷问题在许可的时间内则很难得到满意解。利用蚁群算法固有的并行特性，将并行化处理技术与Bug－BACO算法相结合形成Bug－PBACO算法，其求解大规模优化问题的能力明显优于Bug－BACO算法，这为提高二元蚁群优化算法的执行效率提供了一种新的作用机制。

［1］熊伟清，魏平 .二进制蚁群进化算法［J］.自动化学报，2007，33（3）：259－264.

［2］熊伟清，魏平，赵杰煜 .传递信号的二元蚁群算法［J］.模式识别与人工智能，2007，20（1）：15－20.

［3］严彬，熊伟清，程美英，等 .带拥塞控制的多种群二元蚁群算法［J］.控制理论与应用，2009，26（4）：387－394.

［4］叶青，熊伟清，李纲 .多目标优化的多种群混合行为二元蚁群算法［J］.计算机工程与应用.2011，47（17）：37－41.

［5］胡钢，熊伟清，张翔，等 .可控搜索偏向的二元蚁群算法［J］.控制理论与应用，2011，28（8）：1071－1080.

［6］程美英，熊伟清，魏平 .基于二元蚁群算法求解组卷问题［J］.计算机应用研究，2008，25（9）：2637－3639.

［7］章春芳 .自适应的并行蚁群算法及其应用［D］.扬州：扬州大学，2006.

［8］胡珂 .基于MPI的并行蚁群算法研究［D］.昆明：昆明理工大学，2011.