遗传基因算法组卷.docx

资源描述

遗传基因算法组卷.docx

《遗传基因算法组卷.docx》由会员分享，可在线阅读，更多相关《遗传基因算法组卷.docx（16页珍藏版）》请在冰点文库上搜索。

遗传基因算法组卷.docx

遗传基因算法组卷

遗传算法：

自动组卷

1问题描述

1.1自动组卷模型描叙

实验的目标是用计算机运算的方式表达组卷的逻辑推演的过程，从而实现自动组卷功能。

实验采用人工智能中的遗传算法来描叙自动组卷的过程。

自动组卷模型的试卷评判标准包括试卷总分、题型分值、试卷难度、考试时间、试卷区分度。

由此构成了组卷的评判函数Y=f（试卷总分、题型分值、试卷难度、考试时间、试卷区分度）来评判试卷的好坏。

在生成一套试卷时，用户根据要求设置各种约束条件（这里即为试卷总分、题型分值、试卷难度、考试时间、试卷区分度等），这些约束条件最终转换成评判函数Y中的某些条件，用于在评判生成的试卷与目标最优的靠近程度，由此而计算出一份试卷的相对好坏。

自动组卷模型的试卷生成为从已有的题型库中（本实验中有选择题、填空题、计算题、简答题4种类型）按类型的约束的设置（如填空题的个数为10个）选择出题目，并将所有题目分类排好组成一份试卷。

自动组卷模型生成的初始试卷为按约束设置从题库种随机选择进行组卷的，所以组卷模型并没有对初始试卷的生成进行一定的选择（以后可以改进）。

自动组卷模型的终止可以有两个设置:

1.遗传代数n，并以代数n的种群最优个体为输出；2.设定评判值差距s，当遗传到某代k,存在k代的种群最优个体评判值与理想评判值的绝对值小于s时，停止并输出k代的种群最优个体。

本实验选择第一种终止方式。

下面给出与本实验中试题库中试题和试卷组成等属性说明。

（1）题型：

选择题、填空题、计算题、简答题。

在题库中，每种题型作为一个单独的目录存放。

（2）试题：

每个试题以独立的文件存放在试题库中对应的目录下。

该文件包含信息：

题目类型、题目内容、题目答案、题目分值、题目难度、题目区分度。

其中题目难度、题目区分度可根据实验经验设置，以后可以根据实际测试情况逐步修正。

本试题库试题的难度系数分为9个级别1,2,3,4,5,6,7,8,9,其中1表示最容易的，9表示最难的，1~3表示较容易的题目，4～6表示中等难度的题目，7～9表示较难的题目。

在以后的难度系数维护中可用试题的平均失分率来表示，即（1-总得分/（参加考试人数×该题分值））×10。

（3）试卷组成：

试卷组成已经给出了预设的几种组成方式，分数为100分。

（如选择题10个、填空题5个、计算题2个、简答题2个）

1.2问题的搜索形式描述（4要素）

、初始状态。

由数字1，0组成描述试卷构成的序列（即为染色体），其中染色体分为4个区间，代表4种题型，每个区间序列长度都题库中对应题型的个数（如11000-11-001001-111000001，表示题库中计算机题有5个、简答题有2个、填空题有6个、选择题有9个；且计算机题选择了题库中的1和2号题目）。

实验中的初始状态为随机生成的试卷构成序列：

×……×-×……×-×……×-×……×（其中×表示0或1；……表示任意长度的×；-表示题型区间的分隔符），其中各个区间长度由运行时题库大小决定

、后继函数。

这里后继函数为遗传算法中的遗传算子：

按照一定的交叉（Crossover）概率和交叉方法生成新的个体、按照一定概率的变异。

、目标状态。

为最优评判函数选择一定代数后种群中的最优个体，从而获得能表示相对最好试卷构成的染色体。

、路径耗散函数。

这里的耗散函数与实验中设置的初始种群大小，遗传代数有关。

相应值约达，时间、空间耗散也就越大。

1.3解决方案介绍（原理）

遗传算法采用类似基因演化的循环过程，其演算过程如下：

1）随机产生一定数目的初始种群

2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步。

3）依据适应度选择（Selected）再生个体

4）按照一定的交叉（Crossover）概率和交叉方法生成新的个体

5）按照一定的变异（Mutation）概率和变异方法生成新的个体

6）由交叉和变异产生新一代的种群，然后返回第2步。

如图1所示：

（图1）

1.3.1选择（Selected）操作

选择操作也叫复制操作,选择是遗传算法的主要元素之一,选择决定着群体中哪些个体将全部或部分的“自我”传递给下一代.选择方法的目标是给优秀的个体以指数增长的再生机会.进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大.“赌轮”选择方法,由函数select（…）实现,赌轮方法源于轮盘赌博游戏,也称为适应度比例方法.在该方法中,各个个体的选择概率和其适应度值成比例,这是目前遗传算法中最基本也是最常用的选择方法.其实现方法如下:

1）累加当前群体的适应度值,称为总值Sum,它代表着转轮的总面积.　

2）产生[0,1]之间的随机数,称为Rand.

3）用Rand乘以总值Sum.得到0与总值Sum间的值,称为转轮值,这一值是设想的转轮球落入槽走过的距离面积.

4）累加群体中个体的适应度值,检查直到某一个体使其累加值大于或等于转轮值,此个体则被选中.

设群体大小为

个体

的适应度为

则个体

被选中的概率

为:

…

由上式可见,适应度越高的个体被选中的概率也越大;反之,适应度越低的个体被选中的概率也越小.

1.3.2交叉（Crossover）操作

交叉操作是遗传算法中最主要的遗传操作.通过交叉操作可以得到新一代个体,新个体组合了其父辈个体的特性.交叉的目的是使群体信息进行充分组合,扩大搜索范围.PMX交叉算子,PMX交叉算子是Goldberg和Lingle于1985年提出来的.这种算子较简单地直接交换扩大了搜索空间,还使交叉后的非法结合合法化.PMX交叉算子可分两步实现,对于染色体

和

首先找到满足要求的两个点,两个点之间的区域称之为匹配区域,匹配区域以外的区域称为交叉区域.交叉区域必须满足下面条件之一:

（1）基因相同,但基因的排列顺序可以相同,可以不同;

（2）在匹配区域中,没有一个基因是相同的.其基本过程如下:

1）在所有的个体范围内随机选定2个配对个体.

2）配对个体上随机选出两个交叉点,这两点之间的区域称为匹配区域,匹配区域以外的区域称为交叉区域.

3）交换配对个体的交叉区域,产生原始后代.

4）确定两个交叉区域之间的映射关系.

5）根据映射关系将后代合法化.

1.3.3变异（Mutation）操作

变异是对群体中个体某些值进行改变,其目的有两个:

其一是使算法具有随机搜索能力;其二是维持种群的多样性,防止未成熟收敛现象.变异为新个体的产生提供了机会.

2算法介绍

2.1搜索算法一般介绍

2.1.1选择（Selected）操作

本实验采用类似“赌轮”选择方法。

选择过程如下：

计算当前种群所以个体的适应度值，并累加当前群体的适应度值，构造代表着转轮总面积的sum。

产生[0,1]之间的随机数，称为Rand。

用Rand乘以总值Sum。

得到0与总值Sum间的值，称为转轮值,这一值是设想的转轮球落入槽走过的距离面积。

累加群体中个体的适应度值,检查直到某一个体使其累加值大于或等于转轮值，此个体则被选中。

每次在上代群体中安装如上过程选择个体进行遗传算子的操作对象来产生新的个体并将其加如新的种群中，直到新的种群到达指定的大小。

2.1.2交叉（Crossover）操作

本实验采用类似PMX交叉算子的方式，例如:

表示试卷构成的染色体

=10001-1111100000-10001-00101、

=01010-1100010101-01100-01010。

第一步:

随机产生交叉区间,这里选择3,当然不止这一个,这只是满足要求的一组交叉位置.第二步:

交换两点确定的交叉位置,产生新的染色体

。

=10001-1111100000-01100-00101、

=01010-1100010101-10001-01010。

第三步:

合法化后代，应为这里

必为合法，所以这步可以省略。

尽管PMX交叉算子可以实现交叉,而且不影响交叉区域以外其他基因的结构,但这种方法实现的交叉对交叉位置的要求十分严格,因为每次必须先要找到满足上面要求的匹配区域,才能进行交叉.首先寻找这样的交叉区域就是一件很费时的工作,不是任意两个染色体都是可以进行交叉的.即使能交叉,有的染色体交叉的较多,而有的就比较少;其次这样的交叉位置不具有随机性.

2.1.3变异（Mutation）操作

自动组卷模型中有个最基本的要求就是试卷相应题型的题目数量约束的满足.一般的变异算子往往会导致非法结构的产生.为了能够在变异过程中不产生非法结构,本实验采用染色体区段全变异算子,其实现原理说明如下:

令染色体

=10001-1111100000-10001-00101第一步:

在所有的个体码串范围内随机确定变异区间，这里选择3;

第二步:

在确定的个体串上的变异区间上计算1的个数，这里Num

（1）=2;

第三步:

以事先确定好的变异概率

将变异算子作用于确定的变异区间,可能的一种变异结果如下（这里假设变异发生）:

=10001-1111100000-00101-00101

针对自动组卷模型实验给出染色体区间全变异算子,它不受变异位置的影响,有较好的灵活性.但它每进行一次变异就改变了基因中的一个区间,这等于普通变异算子将一个区间作为一个染色题进行变异.因此,用这种变异算子进行变异时,所选的变异概率应低于普通概率.

2.2算法伪代码

以下是遗传算法总流程的伪代码。

BEGIN:

I=0;

InitializeP（I）;

FitnessP（I）;

While（notTerminate-Condition）

{

I++;

GA-OperationP（I）;

FitnessP（I）;

}

END.

3算法实现

3.1实验环境与问题规模

本实验在j2se平台上进行开发测试，运行程序需要搭建相应的j2se运行时环境。

实验的题库分为计算题（10分/个，共10个）、简答题（10分/个，共10个）、填空题（4分/个，共10个）、选择题（4分/个，共20个）。

预设生成的试卷组成为选择题（4分/个，共10个）、填空题（4分/个，共5个）、计算题（10分/个，共2个）、简答题（10分/个，共2个），总分100分，难度为4，区分度为2。

遗传的代数、种群的大小可以自行设置，这里默认是20代、10个个体。

3.2数据结构

本实验的最核心的模型对象为：

问题（Question）和个体（Individual）.其中

Question用于描叙题目的信息，其数据结构包含：

publicStringtype;

publicintscore;

publicStringcontext;

publicStringanswer;

publicintdifficulty;

publicintidentify;

Individual用于描叙构成一份试卷的信息，其数据结构包含：

publicint[]xuanze_chrom;

publicint[]tiankong_chrom;

publicint[]jisuan_chrom;

publicint[]jianda_chrom;

publicintfitness;

publicdoublechoice;

publicintparent1,parent2;

individual的变异操作：

publicvoidViaration（doubleviaration_degree）{

intviaration_sction=RandomNumber.randomIntNumber（1,4）;

if（newRandom（）.nextDouble（）

intselectednum=0;

int[]temp_viaration_section;

switch（viaration_sction）{

case1:

temp_viaration_section=this.xuanze_chrom;break;

case2:

temp_viaration_section=this.tiankong_chrom;break;

case3:

temp_viaration_section=this.jisuan_chrom;break;

default:

temp_viaration_section=this.jianda_chrom;break;

}

for（inti=0;i

if（temp_viaration_section[i]==1）selectednum++;

temp_viaration_section[i]=0;

}

while（selectednum!

=0）{

intselect=RandomNumber.randomIntNumber（0,temp_viaration_section.length-1）;

if（temp_viaration_section[select]!

=1）{

selectednum--;

temp_viaration_section[select]=1;

}}}}

Individual的交叉操作：

publicvoidcrossover（new_pop,old_pop,intind1,intind2）{

Individualnew_ind1=old_pop.get（ind1）.copy（）;

Individualnew_ind2=old_pop.get（ind2）.copy（）;

int[]temp;

switch（RandomNumber.randomIntNumber（1,4））{

case1:

temp=new_ind1.xuanze_chrom;

new_ind1.xuanze_chrom=new_ind2.xuanze_chrom;

new_ind2.xuanze_chrom=temp;

break;

case2:

temp=new_ind1.tiankong_chrom;

new_ind1.tiankong_chrom=new_ind2.tiankong_chrom;

new_ind2.tiankong_chrom=temp;

break;

case3:

temp=new_ind1.jisuan_chrom;

new_ind1.jisuan_chrom=new_ind2.jisuan_chrom;

new_ind2.jisuan_chrom=temp;

break;

default:

temp=new_ind1.jianda_chrom;

new_ind1.jianda_chrom=new_ind2.jianda_chrom;

new_ind2.jianda_chrom=temp;

break;

}

new_ind1.parent1=ind1;

new_ind1.parent2=ind2;

new_ind2.parent1=ind1;

new_ind2.parent2=ind2;

new_pop.add（new_ind1）;

new_pop.add（new_ind2）;

}

其他遗传算子的代码请参阅附件源码。

3.3实验结果

根据计算结果，通过遗传算法自动组卷，并根据问题规模和初始数据（如题库大小）等前置条件，可以总结经验为：

到第20代的时候，相邻代数种群的最优染色体和同代种群内部染色体基本趋于一致，表示算法是收敛的。

虽然在整个遗传过程中，有时中间有些染色体优化程度比较高，没有呈线性程度优化，但是整体还是呈现收敛趋势，而且收敛速度比较快，生成的试卷也基本上能够达到预定要求。

结论：

计算机自动组卷可以大大减少教师在考试命题中的工作量，同时还可以避免由于人为因素造成的偏差在对目前的组卷系统进行分析了解的基础上结合实际命题经验，利用遗传算法的全局寻优和收敛速度快的特点，设计了组卷问题的染色体结构、适应度函数、遗传算子及结束条件所利用的遗传算法搜索速度快尽量避免同一试卷中出现同一考查点多道题的情况，使试卷的覆盖面广，组出更合理的试卷，是一种实用有效的组卷方法

3.4系统中间及最终输出结果（要求有屏幕显示）

本测试结果的约束设置为：

选择题（4分/个，共10个）、填空题（4分/个，共5个）、计算题（10分/个，共2个）、简答题（10分/个，共2个），总分100分，难度为容易。

遗传的代数、种群的大小设置为20代、10个个体。

结果如下：

=============================================================

{染色体序列：

[00000101000100010010-0100011110-00010011000-0000100110]、个体适应度：

109、个体的父母为上代的：

[0,0]}>>>>>>>>初始种群最佳个体

{染色体序列：

[00000101000100010010-0100011110-00010011000-0011001000]、个体适应度：

107、个体的父母为上代的：

[2,3]}>>>>>>>>第1代最佳个体

{染色体序列：

[00000101000100010010-0100011110-00010011000-0011001000]、个体适应度：

107、个体的父母为上代的：

[5,1]}>>>>>>>>第2代最佳个体

{染色体序列：

[00000101000100010010-0100011110-00010011000-0011001000]、个体适应度：

107、个体的父母为上代的：

[2,5]}>>>>>>>>第3代最佳个体

{染色体序列：

[01000100100000100100-0110101010-00010011000-0011001000]、个体适应度：

108、个体的父母为上代的：

[3,4]}>>>>>>>>第4代最佳个体

{染色体序列：

[01000100100000100100-0110101010-00010011000-0011001000]、个体适应度：

108、个体的父母为上代的：

[4,1]}>>>>>>>>第5代最佳个体

{染色体序列：

[01000100100000100100-0110101010-00010011000-0011001000]、个体适应度：

108、个体的父母为上代的：

[1,4]}>>>>>>>>第6代最佳个体

{染色体序列：

[01000100100000100100-0100011110-00010011000-0011001000]、个体适应度：

114、个体的父母为上代的：

[2,5]}>>>>>>>>第7代最佳个体

{染色体序列：

[01000100100000100100-0100011110-00010011000-0011001000]、个体适应度：

114、个体的父母为上代的：

[4,0]}>>>>>>>>第8代最佳个体

{染色体序列：