基于遗传算法的组卷系统的PHP的一种实现

遗传算法（Genetic Algorithm，简称GA）是一种模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解，它常用来解决多约束条件下的最优问题，由美国的J.Holland教授1975年首先提出。

遗传算法的基本操作及步骤：

（1）初始化种群：随机生成N个个体作为初始种群。

（2）根据适应度函数计算适应度

（3）选择（我个人理解的是“自然选择”阶段，后面部分是网上抄的）：按比例的适应度计算，基于排序的适应度计算，可以挑选以下算法：轮盘赌选择、随机遍历抽样、局部选择、截断选择、锦标赛选择

（4）交叉（我个人理解的是“基因重组”阶段，后面部分是网上抄的），基因重组是结合来自父代交配种群中的信息产生新的个体。依据个体编码表示方法的不同，可以有以下的算法：实值重组；离散重组；中间重组；线性重组；扩展线性重组。二进制交叉、单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉。

（5）变异（我个人理解的是“基因突变”阶段，后面部分是网上抄的），交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化。依据个体编码表示方法的不同，可以有以下的算法：实值变异、二进制变异。

以下的组卷代码仅仅是为了演示遗传算法的流程，在实际组卷系统中不会采用以下方法和代码，有些步骤我认为在组卷系统中根本不适用，但是写着方便。

2.目前制作一个很简单的，只检测难度系数的组卷系统，对知识点的覆盖率和题型等均无考虑，其实用遗传算法解决这个问题有点大材小用，哈哈

代码中用到的两个函数：格雷码转十进制码和十进制码转格雷码

tiku=$tiankong;
$this->nandu=$nandu;
$this->num=$num;
$this->wc=$wc;
//初始化种群
$this->zhongqun=$this->rand_ti($this->tiku,$this->num);
}
/**
*适应应度检测
*目前制作一个很简单的只检测难度系数的，对知识点的覆盖率暂不考虑
*试卷的难度系数计算:每道题的难度系数*每道题的分数的和/总分
*适应度函数：期望的难度系数和种群的难度系数绝对值相差在可接受误差范围内即可
*@returnbool
*/
publicfunctioncheck()
{
//计算种群的难度系数
$defen=$zongfen=0;
foreach($this->zhongqunas$v){
$defen+=$v['difficulty']*$v['score'];
$zongfen+=$v['score'];
}
$ndxs=$defen/$zongfen;
if(abs($this->nandu-$ndxs)<$this->wc){
//停止筛选
//记录当前难度系数
$this->dqndxs=$ndxs;
returnfalse;
}else{
//继续筛选
returntrue;
}
}
/**
*对种群进行选择操作，
*这里只把不合格的去掉，对优秀的没有进行复制
*/
publicfunctionchoice()
{
//计算每个题的难度系数和期望难度系数差
$ndxsc=array();
foreach($this->zhongqunas$k=>$v){
$ndxsc[$k]=abs($this->nandu-$v['difficulty']);
}
arsort($ndxsc,SORT_NUMERIC);
//根据交叉率计算出产生新个体的数量
$new_num=floor($this->num*$this->h_probability);
$i=0;
//将不合格的个体从种群中删除掉
foreach($ndxscas$k=>$v){
if($new_num>$i){
unset($this->zhongqun[$k]);
$i++;
}else{
break;
}
}
}
/**
*交叉杂交操作
*/
publicfunctionhybrid()
{
//计算单倍体长度
$tm=array_rand($this->zhongqun,1);
$cross_len=floor(strlen($tm)/2);
//当种群繁殖到预定的数量时，停止繁殖
while(count($this->zhongqun)<$this->num){
if($this->hybrid_num>$this->limit){
returnfalse;
}
//随机选择两个个体进行杂交产生新个体
$rand=array_rand($this->zhongqun,2);
//杂交开始
$individuality=substr($rand[0],0,$cross_len);
$individuality.=substr($rand[1],$cross_len);
//如果新个体在种群中已存在，则重新杂交产生新个体
//新个体纳入到种群中
$this->zhongqun[$individuality]=$this->tiku[gary_to_decimal($individuality)];
$this->hybrid_num+=1;
}
returntrue;
}
/**
*种群中随机个体随机变异变异操作
*/
publicfunctionvariation()
{
$vriants=array_rand($this->zhongqun,ceil($this->v_probability*$this->num));
if(is_array($vriants)){
//有多个变种
foreach($vriantsas$v){
$i=$this->change_something($v);
if($i===false){
returnfalse;
}
$this->zhongqun[$i]=$this->tiku[gary_to_decimal($i)];
unset($this->zhongqun[$v]);
}
}else{
//只有一个变种
$i=$this->change_something($vriants);
if($i===false){
returnfalse;
}
$this->zhongqun[$i]=$this->tiku[gary_to_decimal($i)];
unset($this->zhongqun[$vriants]);
}
returntrue;
}
/**
*改变字符串一个位上的值,突变的时候，如果突变位置上为0，则改为1，反之改为0；
*@param$str
*@returnmixed
*/
privatefunctionchange_something($str)
{
$old=$str;
//为了保护我们的CPU，做个变异次数限制
if($this->vari_num>$this->limit){
returnfalse;
}
$this->vari_num+=1;
//获取当前种群中已有的个体的格雷码
$position=rand(0,strlen($str)-1);
if($str{$position}==1){
$str{$position}=0;
}else{
$str{$position}=1;
}
//如果变异后的个体已经在种群中存在，则重新变异，或者变异后的个体在题库中不存在时，重新变异
if(in_array($str,array_keys($this->zhongqun))){
$this->change_something($str);
}else{
//变异后的个体不在题库中
if(gary_to_decimal($str)>count($this->tiku)-1){
$str=$this->change_something($str);
}else{
//变异的新个体在当前种群中不存在，并且存在于题库中
return$str;
}
}
}
/**
*随机选题，其实我个人觉得组卷时采用轮盘赌的方法更适合，不过这里为了写起来简单直接采用了随机选择
*@param$array题库
*@param$num要选择的数量
*@returnarray
*/
privatefunctionrand_ti($array,$num){
$len=count($array);
$new=array();
while(count($new)!=$num){
//随即选题，并转成格雷码作为索引,由于题库数量较少，7位码就够用了
$rand_num=rand(0,$len);
$gray=decimal_to_gray($rand_num,7);
$new[$gray]=$array[$rand_num];
}
return$new;
}
/**
*组卷操作，获取卷子信息
*@returnint|string
*/
publicfunctionget_papers(){
$i=1;
while($this->check()){
if($i>$this->limit){
returnarray('status'=>0,'info'=>'系统经过长达'.$this->limit.'次的尝试，还是没有组卷成功，请尝试重新组卷！');
}
$this->choice();
//杂交
if(!$this->hybrid()){
returnarray('status'=>0,'info'=>'杂交次数过多，请尝试重新组卷，或者您可以放宽误差范围后在组卷！');
}
//变异
if(!$this->variation()){
returnarray('status'=>0,'info'=>'变异次数过多，请尝试重新组卷，或者您可以放宽误差范围后在组卷！');
}
$i++;
}
$data=array();
foreach($this->zhongqunas$k=>$v){
$data[gary_to_decimal($k)]=$v;
}
returnarray('status'=>1,'info'=>'组卷成功','num'=>$i,'data'=>$data);
}
}
$m=newzujuan(0.6,0.02,12);
$res=$m->get_papers();
if($res['status']){
echo'经过'.$res['num'].'代
';
echo'当前试卷难度系数为'.$m->dqndxs;
echo'
难度系数误差'.(abs(0.6-$m->dqndxs)).'
';
echo'

---

'; echo'
变异次数：'.$m->vari_num; echo'
杂交次数：'.$m->hybrid_num; echo'

---

试卷题目分别为：'; foreach($res['data']as$k=>$v){ echo'
第'.$k.'题'; print_r($v); } }else{ echo$res['info']; echo'

---

'; echo'
变异次数：'.$m->vari_num; echo'
杂交次数：'.$m->hybrid_num; }