|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <math.h>
|
|
|
#include "UTLab.h"
|
|
|
#define N 32//每个染色体的基因数
|
|
|
//#define W 100//试卷总分值
|
|
|
#define TYPE -1//题型数量
|
|
|
//#define M 2 //目标数目
|
|
|
//#define TYPE -1//求最大还是求最小
|
|
|
#define GEN 100//迭代次数
|
|
|
#define POP_SIZE 30//种群大小
|
|
|
#define SELECTQUE_SIZE 250 //选择题题库总量
|
|
|
#define TKQUE_SIZE 200 //填空题题库总量
|
|
|
#define ZHGQUE_SIZE 50 //主观题题库总量
|
|
|
#define NUM 4//题目特征数目
|
|
|
#define NUMCH 6//章节数目
|
|
|
#define NUMD 3//难度数目
|
|
|
#define DRATE1 0.2 //难度系数为1的预定义比率
|
|
|
#define DRATE2 0.6
|
|
|
#define DRATE3 0.2
|
|
|
#define CHRATE1 0.1//预定义每章的分值比率
|
|
|
#define CHRATE2 0.2
|
|
|
#define CHRATE3 0.2
|
|
|
#define CHRATE4 0.2
|
|
|
#define CHRATE5 0.2
|
|
|
#define CHRATE6 0.1
|
|
|
#define RCH 0.5
|
|
|
#define RD 0.5
|
|
|
#define P_MUTATION 0.008//变异系数
|
|
|
#define P_CROSSOVER 0.8//交叉系
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
double OBJECTIVE[POP_SIZE+1];
|
|
|
double DRATE[NUMD+1]={0,DRATE1,DRATE2,DRATE3}; //预定义难度系数比例
|
|
|
double CHRATE[NUMCH+1]={0,CHRATE1,CHRATE2,CHRATE3,CHRATE4,CHRATE5,CHRATE6};//预定义章节比
|
|
|
double CHROMOSOME[POP_SIZE+1][N+1];//染色体数组
|
|
|
double q[POP_SIZE+1];//存储选题到的题号的数组
|
|
|
int SELECTQUESTION[SELECTQUE_SIZE+1][NUM];//选择题题库;1/分值；2、章节；3、难度；
|
|
|
int TKQUESTION[TKQUE_SIZE+1][NUM];//填空题题库;1/分值；2、章节；3、难度；
|
|
|
int ZHGQUESTION[ZHGQUE_SIZE+1][NUM];//主观题题库;1/分值；2、章节；3、难度；
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
static double caucal(double x[]); //计算新染色体的章节和难度比
|
|
|
static void initialquestion(void);//初始化题库
|
|
|
static void initialrate(void);//初始化各比例
|
|
|
static void initialization(void);//初始化
|
|
|
static void evaluation(int gen);
|
|
|
static void objective_function(void);
|
|
|
static void selection(void);
|
|
|
static void crossover(void);
|
|
|
static void mutation(void);
|
|
|
static int constraint_check(double x[]);
|
|
|
|
|
|
|
|
|
static double caucal(double x[])
|
|
|
{int i,j,t,s,m;
|
|
|
double chrate[NUMCH+1],drate[NUMD+1];//定义各章节分值比和难度比
|
|
|
double da=0;
|
|
|
double ba=0;
|
|
|
for (j=0;j<=NUMCH;j++)
|
|
|
{chrate[j]=0;}
|
|
|
|
|
|
for (j=0;j<=NUMD;j++)
|
|
|
{drate[j]=0;}
|
|
|
|
|
|
for(j=1;j<=30;j++)
|
|
|
{t=int(x[j]);
|
|
|
if(j<=15)
|
|
|
{
|
|
|
s=SELECTQUESTION[t][2];
|
|
|
chrate[s]+=2;
|
|
|
m=SELECTQUESTION[t][3];
|
|
|
drate[m]+=2;
|
|
|
}
|
|
|
else if(j>15&&j<=25)
|
|
|
{
|
|
|
s=TKQUESTION[t][2];
|
|
|
chrate[s]+=2;
|
|
|
m=TKQUESTION[t][3];
|
|
|
drate[m]+=2;
|
|
|
}
|
|
|
else
|
|
|
{s=ZHGQUESTION[t][2];
|
|
|
chrate[s]+=10;
|
|
|
m=ZHGQUESTION[t][3];
|
|
|
drate[m]+=10;
|
|
|
}
|
|
|
}
|
|
|
for(j=1;j<=NUMCH;j++)
|
|
|
{chrate[j]=chrate[j]/100;
|
|
|
//printf("第%d个染色体第%d章的分值比是%f\n",i,j,chrate[i][j]);
|
|
|
ba+=fabs(double(chrate[j]-CHRATE[j]));
|
|
|
}
|
|
|
//printf("第个染色体章的分值比平均值%f\n",ba/NUMCH);
|
|
|
x[31]=ba/NUMCH;
|
|
|
for(j=1;j<=NUMD;j++)
|
|
|
{drate[j]=drate[j]/100;
|
|
|
//printf("第%d个染色体第%d难度的分值比是%f\n",i,j,drate[i][j]);
|
|
|
da+=fabs(double(drate[j]-DRATE[j]));
|
|
|
}
|
|
|
//printf("第染色体难度差的平均值是%f\n",da/NUMD);
|
|
|
x[32]=da/NUMD;
|
|
|
return RCH*x[31]+RD*x[32];
|
|
|
|
|
|
|
|
|
}
|
|
|
static void objective_function(void)
|
|
|
{
|
|
|
|
|
|
int i;
|
|
|
for(i = 1; i <= POP_SIZE; i++) {
|
|
|
|
|
|
OBJECTIVE[i] =RCH*CHROMOSOME[i][31]+RD*CHROMOSOME[i][32];
|
|
|
|
|
|
}
|
|
|
}
|
|
|
|
|
|
static void initialquestion(void)
|
|
|
{ int i,j;
|
|
|
for(i=1;i<=SELECTQUE_SIZE+1;i++)//将选择题输入题库
|
|
|
for(j=1;j<=NUM;j++)
|
|
|
{
|
|
|
if(j==1)SELECTQUESTION[i][j]=2;
|
|
|
if(j==2)SELECTQUESTION[i][j]=int(myu(1,7));
|
|
|
if(j==3)SELECTQUESTION[i][j]=int(myu(1,4));
|
|
|
}
|
|
|
for(i=1;i<=TKQUE_SIZE+1;i++)//将填空题输入题库
|
|
|
for(j=1;j<=NUM;j++)
|
|
|
{
|
|
|
if(j==1)TKQUESTION[i][j]=2;
|
|
|
if(j==2)TKQUESTION[i][j]=int(myu(1,7));
|
|
|
if(j==3)TKQUESTION[i][j]=int(myu(1,4));
|
|
|
}
|
|
|
|
|
|
for(i=1;i<=ZHGQUE_SIZE+1;i++)//将填空题输入题库
|
|
|
for(j=1;j<=NUM;j++)
|
|
|
{
|
|
|
if(j==1)ZHGQUESTION[i][j]=10;
|
|
|
if(j==2)ZHGQUESTION[i][j]=int(myu(1,7));
|
|
|
if(j==3)ZHGQUESTION[i][j]=int(myu(1,4));
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
|
|
static void initialrate(void)//初始化章节和难度比例
|
|
|
{ int i,j,t,s,x;
|
|
|
double chrate[POP_SIZE+1][NUMCH+1],drate[POP_SIZE+1][NUMD+1];//定义各章节分值比和难度比
|
|
|
double da=0;
|
|
|
double ba=0;
|
|
|
|
|
|
|
|
|
for (i=1;i<=POP_SIZE;i++)
|
|
|
{for (j=1;j<=NUMCH;j++)
|
|
|
{chrate[i][j]=0;}
|
|
|
}
|
|
|
for (i=1;i<=POP_SIZE;i++)
|
|
|
{for (j=1;j<=NUMD;j++)
|
|
|
{drate[i][j]=0;}
|
|
|
}
|
|
|
|
|
|
|
|
|
for(i=1; i<=POP_SIZE; i++)
|
|
|
{
|
|
|
for(j=1;j<=30;j++)
|
|
|
{t=CHROMOSOME[i][j];
|
|
|
if(j<=15)
|
|
|
{
|
|
|
s=SELECTQUESTION[t][2];
|
|
|
chrate[i][s]+=2;
|
|
|
x=SELECTQUESTION[t][3];
|
|
|
drate[i][x]+=2;
|
|
|
}
|
|
|
else if(j>15&&j<=25)
|
|
|
{
|
|
|
s=TKQUESTION[t][2];
|
|
|
chrate[i][s]+=2;
|
|
|
x=TKQUESTION[t][3];
|
|
|
drate[i][x]+=2;
|
|
|
}
|
|
|
else
|
|
|
{s=ZHGQUESTION[t][2];
|
|
|
chrate[i][s]+=10;
|
|
|
x=ZHGQUESTION[t][3];
|
|
|
drate[i][x]+=10;
|
|
|
}
|
|
|
}
|
|
|
for(j=1;j<=NUMCH;j++)
|
|
|
{chrate[i][j]=chrate[i][j]/100;
|
|
|
//printf("第%d个染色体第%d章的分值比是%f\n",i,j,chrate[i][j]);
|
|
|
ba+=fabs(double(chrate[i][j]-CHRATE[j]));
|
|
|
}
|
|
|
//printf("第%d个染色体章的分值比平均值%f\n",i,ba/NUMCH);
|
|
|
CHROMOSOME[i][31]=ba/NUMCH;
|
|
|
ba=0;
|
|
|
for(j=1;j<=NUMD;j++)
|
|
|
{drate[i][j]=drate[i][j]/100;
|
|
|
//printf("第%d个染色体第%d难度的分值比是%f\n",i,j,drate[i][j]);
|
|
|
da+=fabs(double(drate[i][j]-DRATE[j]));
|
|
|
}
|
|
|
//printf("第%d个染色体难度差的平均值是%f\n",i,da/NUMD);
|
|
|
CHROMOSOME[i][32]=da/NUMD;
|
|
|
da=0;
|
|
|
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
|
|
static void initialization(void)//初始化染色体操作
|
|
|
{
|
|
|
int i,j;
|
|
|
|
|
|
for(i=1; i<=POP_SIZE; i++)//初始化染色体，待讨论!
|
|
|
{
|
|
|
for(j=1;j<=15;j++)//选择选择题
|
|
|
CHROMOSOME[i][j]=int(myu(1,SELECTQUE_SIZE+1));
|
|
|
for(j=16;j<=25;j++)//选择填空题
|
|
|
CHROMOSOME[i][j]=int(myu(1,TKQUE_SIZE+1));
|
|
|
for(;j<=30;j++)//select postive question
|
|
|
CHROMOSOME[i][j]=int(myu(1,ZHGQUE_SIZE+1));
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
static int constraint_check(double x[])
|
|
|
{
|
|
|
int n;
|
|
|
for(n=1;n<=30;n++) if(x[n]<=0) return 0;
|
|
|
return 1;
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
void main()
|
|
|
{
|
|
|
int i, j,t,k;
|
|
|
double a;
|
|
|
q[0]=0.05; a=0.05;//定义的比率
|
|
|
for(i=1; i<=POP_SIZE; i++) {a=a*0.95; q[i]=q[i-1]+a;}
|
|
|
initialquestion();
|
|
|
initialization();
|
|
|
initialrate();
|
|
|
evaluation(0);
|
|
|
|
|
|
for(i=1; i<=GEN; i++) {
|
|
|
selection();
|
|
|
crossover();
|
|
|
mutation();
|
|
|
evaluation(i);
|
|
|
t=1; k=1;
|
|
|
for(j=1;j<=POP_SIZE;j++)
|
|
|
if(t>RCH*CHROMOSOME[j][31]+RD*CHROMOSOME[j][32])
|
|
|
{
|
|
|
t=RCH*CHROMOSOME[j][31]+RD*CHROMOSOME[j][32];
|
|
|
k=j;
|
|
|
|
|
|
}
|
|
|
printf("第%d代的最佳章节比是%f,最佳难度比是%f\n",i,CHROMOSOME[k][31],CHROMOSOME[k][32]);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
printf("题号 分值 章节 难度\n");
|
|
|
for(i=1; i<=1; i++)//输出生成的试卷
|
|
|
for(j=1;j<=30;j++)
|
|
|
{t=CHROMOSOME[i][j];
|
|
|
|
|
|
if(j<=15)
|
|
|
{ printf("%d\t",t);
|
|
|
for(k=1;k<NUM;k++)
|
|
|
printf("%d\t",SELECTQUESTION[t][k]);
|
|
|
printf("\n");
|
|
|
}
|
|
|
else if(j>15&&j<=25)
|
|
|
{ printf("%d\t",t);
|
|
|
for(k=1;k<NUM;k++)
|
|
|
printf("%d\t",TKQUESTION[t][k]);
|
|
|
printf("\n");
|
|
|
}
|
|
|
else
|
|
|
{ printf("%d\t",t);
|
|
|
for(k=1;k<NUM;k++)
|
|
|
printf("%d\t",ZHGQUESTION[t][k]);
|
|
|
printf("\n");
|
|
|
}
|
|
|
}
|
|
|
a=0;
|
|
|
for(i=1;i<=POP_SIZE;i++)
|
|
|
a+=(1-RCH*CHROMOSOME[i][31]+RD*CHROMOSOME[i][32]);
|
|
|
printf("最佳适应度为%f\n",a/0.3);
|
|
|
}
|
|
|
static void evaluation(int gen)
|
|
|
{
|
|
|
double a;
|
|
|
int i, j, label;
|
|
|
objective_function();//计算目标函数值
|
|
|
if(gen==0){
|
|
|
OBJECTIVE[0]=OBJECTIVE[1];
|
|
|
for(j = 1; j <= N; j++) CHROMOSOME[0][j]=CHROMOSOME[1][j];
|
|
|
}
|
|
|
for(i=0; i<POP_SIZE; i++){
|
|
|
label=0; a=OBJECTIVE[i];
|
|
|
for(j=i+1; j<=POP_SIZE; j++)
|
|
|
if((TYPE*a)<(TYPE*OBJECTIVE[j])) {
|
|
|
a=OBJECTIVE[j];
|
|
|
label=j;
|
|
|
}
|
|
|
if(label!=0) {
|
|
|
{
|
|
|
a=OBJECTIVE[i];
|
|
|
OBJECTIVE[i]=OBJECTIVE[label];
|
|
|
OBJECTIVE[label]=a;
|
|
|
}
|
|
|
for(j=1; j<=N; j++) {
|
|
|
a=CHROMOSOME[i][j];
|
|
|
CHROMOSOME[i][j]=CHROMOSOME[label][j];
|
|
|
CHROMOSOME[label][j]=a;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
static void selection()
|
|
|
{
|
|
|
double r, temp[POP_SIZE+1][N+1];
|
|
|
int i, j, k;
|
|
|
for(i=1; i<=POP_SIZE; i++) {
|
|
|
r=myu(0, q[POP_SIZE]);
|
|
|
for(j=0; j<=POP_SIZE; j++) {
|
|
|
if(r<=q[j]) {
|
|
|
for(k=1; k<=N; k++) temp[i][k]=CHROMOSOME[j][k];
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
for(i=1; i<=POP_SIZE; i++)
|
|
|
for(k=1; k<=N; k++)
|
|
|
CHROMOSOME[i][k]=temp[i][k];
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
static void crossover()
|
|
|
{
|
|
|
int i, j, jj, k, pop;
|
|
|
double a,r;
|
|
|
double x[N+1], y[N+1];
|
|
|
pop=POP_SIZE/2;
|
|
|
for(i=1; i<=pop; i++) {
|
|
|
if(myu(0,1)>P_CROSSOVER) continue;
|
|
|
j=(int)myu(1,16);
|
|
|
jj=(int)myu(1,16);
|
|
|
r=myu(0,1);
|
|
|
for(k=1; k<=15; k++) {
|
|
|
x[k]=int(r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k])%(SELECTQUE_SIZE+1);
|
|
|
y[k]=int(r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k])%(SELECTQUE_SIZE+1);
|
|
|
}
|
|
|
j=(int)myu(16,26);
|
|
|
jj=(int)myu(16,26);
|
|
|
r=myu(0,1);
|
|
|
for(k=16; k<=26; k++) {
|
|
|
x[k]=int(r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k])%(TKQUE_SIZE+1);
|
|
|
y[k]=int(r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k])%(SELECTQUE_SIZE+1);
|
|
|
}
|
|
|
j=(int)myu(26,31);
|
|
|
jj=(int)myu(26,31);
|
|
|
r=myu(0,1);
|
|
|
for(k=26; k<=30; k++) {
|
|
|
x[k]=int(r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k])%(ZHGQUE_SIZE+1);
|
|
|
y[k]=int(r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k])%(ZHGQUE_SIZE+1);
|
|
|
}
|
|
|
a=caucal(x);
|
|
|
if((constraint_check(x)==1)&&a<=(RCH*CHROMOSOME[j][31]+RD*CHROMOSOME[j][32]))
|
|
|
for(k=1; k<=N; k++) CHROMOSOME[j][k]=x[k];
|
|
|
a=caucal(y);
|
|
|
if((constraint_check(y)==1)&&a<=(RCH*CHROMOSOME[jj][31]+RD*CHROMOSOME[jj][32]))
|
|
|
for(k=1; k<=N; k++) CHROMOSOME[jj][k]=y[k];
|
|
|
}
|
|
|
}
|
|
|
static void mutation(void)
|
|
|
{
|
|
|
int i, j, k;
|
|
|
double x[N+1], y[N+1], infty, direction[N+1],a;
|
|
|
double INFTY=10, precision=0.0001;
|
|
|
for(i=1; i<=POP_SIZE; i++) {
|
|
|
if(myu(0,1)>P_MUTATION) continue;
|
|
|
for(k=1; k<=N; k++) x[k] = CHROMOSOME[i][k];
|
|
|
for(k=1; k<=30; k++)
|
|
|
if(myu(0,1)<0.5) direction[k]=myu(-1,1);
|
|
|
else direction[k]=0;
|
|
|
infty=myu(0,INFTY);
|
|
|
while(infty>precision) {
|
|
|
for(j=1; j<=30; j++) y[j]=int(x[j]+infty*direction[j]);
|
|
|
a=caucal(y);
|
|
|
if(constraint_check(y)==1&&a<=(RCH*CHROMOSOME[i][31]+RD*CHROMOSOME[i][32])) {
|
|
|
for(k=1; k<=N; k++) CHROMOSOME[i][k]=y[k];
|
|
|
break;
|
|
|
}
|
|
|
infty=myu(0,infty);
|
|
|
}
|
|
|
}
|
|
|
}
|
