0 567
平均区分度 0 369
0 382
0 354
0 374
0 390
多知识点
试题总数量 105
112
81
120
125
掌握程序
了解 理解 掌握 应用 综合应用 总计数量
表 2 掌握程度基本信息 题型
选择Байду номын сангаас
填空
判断
简答
205
201
194
52
234
194
162
61
191
163
98
67
29
51
11
69
4
3
2) 用蚂蚁算法求 解出新的可行解, 并将其保 存
下来。
a)将已访问节点列表设置为 NULL, 初始化蚂蚁
未访问节点列表使其成为全集, 然后初始化允许访问
节点列表。
b) 确定蚂蚁路径 的起点, 已访问节 点列表、未 访问结点列表以及允许访问节点列表, 利用下一个结
点的选择策略选择结点。
c)修改已访问节点列表、未访问结点列表以及允 许访问节点列表, 重新计算边的易访问度。
f) 。
3) 将蚂蚁搜寻得到的路径种群保存下来。
4) 比较所有的可行解, 输出最优解。
2 实验与分析
题的具体情况如 表 1所 示, 试题 的掌握程 度如表 2
所示。
表 1 试题库中的基本信息
参数
选择
填空
题型 判断
简答
应用
平均每章
试题数量
51
47
31
22
19
平均难度 0 402
0 421
0 398
0 491
协议 算法及仿真
2011年第 24卷第 4期 E lectron ic Sc i& T ech /A pr 15, 2010
蚁群混合遗传算法的研究及应用
柏建普, 吴 强
(内蒙古科技大学 信息工程 学院, 内 蒙古 包头 014010) 摘 要 为解决组卷过程中 在一定约束条件下存在的多目标优化问题, 结合蚁群算法和 遗传算法各 自的优点 和它 们融合的基础, 提出了一种蚁群算法融合 到遗传算法的策略: 在组卷的前阶段利用遗传算 法群体性 全局搜索能 力, 快 速形成初始解, 在满足终止遗传算法的条 件后, 将 遗传算法调度的较优解转化为蚁群算法 所需要的 初期信息素, 然后 利用蚁群算法所具有的 正反馈、高效等特点快速形成试卷最优解。实践结果证明此算法改善 了试卷的质 量以及系 统的 运行效率, 生成的试卷符合要求 , 达到预 期的结果。 关键词 蚁群算法 ; 遗传算 法; 混合 算法; 组 卷问题 中图分类号 TP301 6 文献标识码 A 文章编 号 1007- 7820( 2011) 04- 020- 04
( 2) 适应度函数。 适应度函数的选 取应该与需要解 决的问题相 结 合, 根据目 标函数来 决定, 本 文中的适 应度函数 F 定义 为 F = F , M easure 其 FM easure 为 评 估 聚 类 算 法 的
图 2 适应度函数流程图
( 3)选择算子。 用锦标赛选择的方法, 根据适应度函数选取要进 行交叉的个体, 然后在锦标赛选择法中, 随机从种群 中挑选预定数目的个体, 从这些个体中选择出具有较 好适应度的个体做为父个体, 这个过程要重复进行, 直到完成所有的父个体选择。
( 1)
x = x + N ( 0,
)
( 2)
其中, N ( 0, )是均值是 0; 标准差是 , 它是 独 立高斯随机数向量。
通过以上描 述, 在混合算 法的后阶 段用蚁群 算 法, 根据 T SP 问题 [ 14] 求解的方法, 流程如下:
1) 将进化种群的信息转化成 蚂蚁出行的信息 素 浓度矩阵。
www d ian zik e ji o rg
21
协议 算法及仿真
柏 建普, 等 : 蚁群混 合遗传算法的研究及应用
( 4) 交叉算子。 利用均匀交叉的方法 [ 11- 13] , 将每个点都作为潜
在的交叉点, 其破坏性能促进对解空间的搜索, 能搜
索到其他交叉方法不能搜索到的模式。其过程是首先
随机产生与父辈个体编码等长的二进制交叉模板串,
d) 判断蚂蚁的未访问结点列 表是不是为 NULL,
若不是, 转到步骤 b); 若是, 则转入步骤 e)。
e)回到出发点, 利用信息素局部的更新策略更新 各节点信息素浓度, 转到步骤 a)。
f) 评估当前蚂蚁通过的路径, 更新为最优路径。
g)判断能否达到 的蚂蚁外出觅食 的次数, 若 不 能, 则次数加 1, 转 到步骤 a), 若能, 则转到步 骤
服遗传算法在搜索到一定阶段时最优解的搜索效率低
以及蚁群算法初始信息素匾乏的问题。
1 3 算法融合的基本环节及其步骤 根据混合算法的思想, 寻找两种算法的最佳结合
点是关键所在。为此提出以下策略用以确保两种算法
的融合在最佳时期。如图 1所示, 设置其最小遗传迭 代次数 ( tb 时刻 )和最大遗传迭代次数 ( tc 时刻 ), 然 后在遗传算法迭代过程中统计子代群体的进化率, 以 及设置子代群体的最小进化率。最后在设置迭代次数
R esearch on and A pp lication of Ant Colony A lgorithm s Hybrid G enetic A lgorithm s
Ba i Jianpu, W u Q iang ( Schoo l of In form at ion Engin eering, InnerM ongo lia Techno logy U n iversity, Baotou 014010, Ch ina) Abstract In order to solve the p rob lem of mu lti ob jective op tmi ization in test p ap er generat ion und er some re stricted cond itions, th is p ap er p roposes fus ing an ant co lony a lgorithm in to the gen et ic algorithm on the basis of the advan tages of th e an t co lony a lgorithm and genetic algorithm and the foundation for the ir fu sion: u sing the global search ing capab ility of the gen et ic algorithm at the early stage of test paper generation, transform ing the op tmi al solu tion schedu led by th e genetic algorithm in to in it ial pheromone th e ant colony need s, and then qu ick ly form ing optmi al so lu tion to th e test pap er by tak ing advan tage of the fact that the an t colony algorithm has the pos itive and negative feedback and the characteristic of h igh effic ien cy. App lication show s th at th is a lgorithm mi proves the qu ality of the test and efficiency of the system s and the generated paper meets the requ irem en t w ith d es ired effect ach ieved. K eywords ant co lony a lgorithm s; gen et ic algorithm s; hybrid algorithms; test paper gen eration
遗传算法 [ 1] ( G enetic A lgorithm s, GA ) 是一种 模 拟自然选择和遗传机制的优化搜索方法, 具有广泛的 适用性。它作为一种实用、高效、鲁棒性较强的优化 技术, 发展迅速, 在各种不同领域中得到广泛应用, 引起学者和专家的关注, 这表现出它具有较强的解决 问题能力。但是遗传算法也有收敛速度比较慢, 对系 统中的反馈信息利用不够, 当求解到一定范围时, 会 产生大量的冗余迭代, 使求解精确效率降低。
的范围内, 如果连续 N 代的子代群体的进化率都 小 于最小进化率, 证明这时遗传算法的优化速度较低, 可以终止遗传算法的过程, 进入蚁群算法。
依据蚁群算法和遗传算法融合的基本思想, 设计 混合算法的操作过程为:
( 1) 染色体的选择、编码以及初始种群的生成。
染色体 用蚁群 算法中 的参数 , , , 0, Q, 这样能利 用 遗传 算 法确 定蚁 群 算法 的 最优 参 数 组 合 [ 9] 。由于实数编码的遗传算法具有精度高、搜索空 间大、易引入特定领域的启发性信息等优点, 所以在 混合算法中可以采用十进制实数编码。初始化种群根 据预设的数量采用随机方式产生。
强等共同 的 特点。广 泛 地 用 于智 能 离 散 系 统工 程 优化, 根据两者各自的优缺点, 本文将这两个算法融 合, 使其优势互补, 提高混合算法的优化性能。
1 蚁群混合遗传算法在组卷问题中的融合
1 1 算法融合的可行性 遗传算法具有较强的全局搜索能力, 尤其是当交
叉概率较大时, 可以产生大量的新个体, 提高了全局 搜索范围。蚁群算法用信息正反馈原理并加入启发式 的搜索思想, 具有了局部搜索能力强和收敛速度快等 优点。遗传算法和蚁群算法具有互补性, 它们可有机 融合 [ 6- 7] 在一起, 用来克服缺点, 发挥优点。 1 2 算法融合的基本思想