afsa.cpp

一个试卷自动生成的利用人工鱼群算法的程序

			for(int j=0;j<this->Amount_Of_Dimension;j++){
				temp_position[j]=this->Fish[Symbol_Of_Fish].Position[j];
			}
			//对temp做一次随机移动
			for(int j=0;j<this->Amount_Of_Dimension;j++){//没选过的维赋值为0
				temp[j]=0;
			}
			int scope=this->Amount_Of_Dimension;
			for(int i=0;i<this->Visual;i++,scope--){//随机移动的步长不超过visual
				//随机选择一个尚未选过的维
				int rand_number=rand()%scope;//从0开始
				//选择第rand_number个未被选择的维
				bool flag2=true;
				for(int k=0;flag2;k++){
					if(temp[k]==0){
						if(rand_number==0){
							temp[k]=1;
							temp_position[k]=rand()%2;
							flag2=false;
						}
						else{
							rand_number--;
						}
					}
				}
			}
			//是否找到更优解
			int ignore1,ignore2;
		    float ignore3;
			float food;
			food=this->Get_Food_Consistence(temp_position,ignore1,ignore2,ignore3);
			if(food<this->Fish[Symbol_Of_Fish].Food_Consistence){
				flag=false;
				for(int k=0;k<this->Amount_Of_Dimension;k++){
					this->Fish[Symbol_Of_Fish].Position[k]=temp_position[k];
				}
				this->Set_Food_Consistence(Symbol_Of_Fish,food);
				this->Set_Neighbour(Symbol_Of_Fish);
			}
		}
		if(flag==false){
			delete[] temp;
			delete[] temp_position;
			return 1;
		}
		else{
			delete[] temp;
			delete[] temp_position;
			return this->Rand_Move(Symbol_Of_Fish);
		}
	}
}

// 聚群
int AFSA::Swarm(int Symbol_Of_Fish)
{
	if(this->Number_Of_fish<=Symbol_Of_Fish||Symbol_Of_Fish<0||this->Fish==NULL) return 0;
	else{//邻居数为0时，food*this->Fish[Symbol_Of_Fish].Amount_Of_Neighbour==0，条件横成立，应预防
		if(this->Fish[Symbol_Of_Fish].Amount_Of_Neighbour!=0){
			int *centre2=new int[this->Amount_Of_Dimension];
		    float *centre=new float[this->Amount_Of_Dimension];
			for(int i=0;i<this->Amount_Of_Dimension;i++){
				centre[i]=0;
			}
			for(i=0;i<this->Number_Of_fish;i++){
				if(i!=Symbol_Of_Fish)
					if(this->Relation_Of_Fishes[Symbol_Of_Fish][i]==1)
						for(int j=0;j<this->Amount_Of_Dimension;j++) centre[j]+=this->Fish[i].Position[j];
			}
			for(i=0;i<this->Amount_Of_Dimension;i++) 
				centre[i]/=this->Fish[Symbol_Of_Fish].Amount_Of_Neighbour;
			for(i=0;i<this->Amount_Of_Dimension;i++) 
				if(centre[i]>=0.5) centre2[i]=1;
				else centre2[i]=0;
			delete[] centre;
			int ignore1,ignore2;
			float ignore3,food;
			food=this->Get_Food_Consistence(centre2,ignore1,ignore2,ignore3);
			if(food*this->Fish[Symbol_Of_Fish].Amount_Of_Neighbour<this->Delta*this->Fish[Symbol_Of_Fish].Food_Consistence){
				for(i=0;i<this->Amount_Of_Dimension;i++){
					if(this->Fish[Symbol_Of_Fish].Position[i]!=centre2[i]){
						int rand_number=rand()%2;
						this->Fish[Symbol_Of_Fish].Position[i]=rand_number;
					}
				}
				this->Set_Food_Consistence(Symbol_Of_Fish,this->Get_Food_Consistence(this->Fish[Symbol_Of_Fish].Position,ignore1,ignore2,ignore3));
				this->Set_Neighbour(Symbol_Of_Fish);
				delete[] centre2;
				return 1;
			}
			else{
				delete[] centre2;
				return this->Prey(Symbol_Of_Fish);
			}
		}
		else{
			return this->Prey(Symbol_Of_Fish);
		}
	}
}

// 追尾
int AFSA::follow(int Symbol_Of_Fish)
{
	if(this->Number_Of_fish<=Symbol_Of_Fish||Symbol_Of_Fish<0||this->Fish==NULL) return 0;
	else{
		int best=-1;//-1表示没有任何鱼在视线内
		for(int i=0;i<this->Number_Of_fish;i++)
			if(this->Relation_Of_Fishes[Symbol_Of_Fish][i]==1)
				if(best==-1||this->Fish[i].Food_Consistence<this->Fish[best].Food_Consistence)
					best=i;
		if(best!=-1&&this->Fish[best].Food_Consistence*this->Fish[best].Amount_Of_Neighbour<this->Fish[Symbol_Of_Fish].Food_Consistence*this->Delta){
			for(int j=0;j<this->Amount_Of_Dimension;j++)
				if(this->Fish[best].Position[j]!=this->Fish[Symbol_Of_Fish].Position[j])
					this->Fish[Symbol_Of_Fish].Position[j]=rand()%2;
			int ignore1,ignore2;
			float ignore3;
			this->Set_Food_Consistence(Symbol_Of_Fish,this->Get_Food_Consistence(this->Fish[Symbol_Of_Fish].Position,ignore1,ignore2,ignore3));
			this->Set_Neighbour(Symbol_Of_Fish);
			return 1;
		}
		else{
			return this->Swarm(Symbol_Of_Fish);
		}
	}
}

// 寻找最优解,试题列表以-1为结尾，try_number为迭代次数,负数表示最大迭代时间，Want_Most_Hard_Level_Difference可容忍的各难度部分最大分值差异，Want_Amount_Difference可容忍总分差异，Want_Cover_Difference可容忍知识点未覆盖率
int AFSA::move(long double Try_Number,long *&Questions,int Want_Most_Hard_Level_Difference,int Want_Amount_Difference,float Want_Cover_Difference)
{//使用long double 可表示更大迭代次数
	time_t time1,time2;
	time1=time(NULL);
	for(long double k=0;true;k+=1){
		int Most_Hard_Level_Difference,Amount_Difference;
		float Cover_Difference;
		this->Get_Food_Consistence(this->Bulletin_Board.Position,Most_Hard_Level_Difference,Amount_Difference,Cover_Difference);
		if(Most_Hard_Level_Difference<=Want_Most_Hard_Level_Difference&&Amount_Difference<=Want_Amount_Difference&&Cover_Difference<=Want_Cover_Difference){
			Questions=new long[this->Amount_Of_Dimension+1];//开辟足够的空间
			for(int j=0,count=0;j<this->Amount_Of_Dimension;j++){
				if(this->Bulletin_Board.Position[j]==1) Questions[count++]=this->Question_List[j].Question_Number;
			}
			Questions[count]=-1;
			return 1;
		}
		if(Try_Number>=0){
			if(k>=Try_Number){
				Questions=new long[this->Amount_Of_Dimension+1];//开辟足够的空间
				for(int j=0,count=0;j<this->Amount_Of_Dimension;j++){
					if(this->Bulletin_Board.Position[j]==1) Questions[count++]=this->Question_List[j].Question_Number;
				}
				Questions[count]=-1;
				return 0;
			}
		}
		else{
			time2=time(NULL);
			if((time2-time1)>(0-Try_Number)){
				Questions=new long[this->Amount_Of_Dimension+1];//开辟足够的空间
				for(int j=0,count=0;j<this->Amount_Of_Dimension;j++){
					if(this->Bulletin_Board.Position[j]==1) Questions[count++]=this->Question_List[j].Question_Number;
				}
				Questions[count]=-1;
				return 0;
			}
		}
		float best_food;
		best_food=this->Bulletin_Board.Food_Consistence;
		int best_position;
		best_position=-1;//-1表示此次未找到比公告板好的
		for(int i=0;i<this->Number_Of_fish;i++){
			this->follow(i);
			int ig1,ig2;
			float ig3,food;
			food=this->Get_Food_Consistence(this->Fish[i].Position,ig1,ig2,ig3);
			if(food<best_food){
				best_food=food;
				best_position=i;
			}
		}
		if(best_position!=-1){
			for(int m=0;m<this->Amount_Of_Dimension;m++){
				this->Bulletin_Board.Position[m]=this->Fish[best_position].Position[m];
			}
			this->Bulletin_Board.Food_Consistence=this->Fish[best_position].Food_Consistence;
			this->Bulletin_Board.Amount_Of_Neighbour=this->Fish[best_position].Amount_Of_Neighbour;
		}
	}
}

// 仅用于测试
void AFSA::test(void)
{
	printf("维数:%d\n试题列表:\n",this->Amount_Of_Dimension);
	for(int i=0;i<this->Amount_Of_Dimension;i++){
		printf("\n难度%d，题号%d，分值%d,覆盖面积%d，所包含知识点：\n",this->Question_List[i].Question_Hard_Level,this->Question_List[i].Question_Number,this->Question_List[i].Question_Value,this->Question_List[i].Number_Of_Cover_Knowledge);
		for(int j=0;j<this->Question_List[i].Number_Of_Cover_Knowledge;j++)
			printf("知识点号：%d,",this->Question_List[i].Knowledge_Number_List[j]);
	}
	printf("\n");
	printf("公告板:\n邻居数：%d,食物：%f\n",this->Bulletin_Board.Amount_Of_Neighbour,this->Bulletin_Board.Food_Consistence);
	for(i=0;i<this->Amount_Of_Dimension;i++)
		printf("%d,",this->Bulletin_Board.Position[i]);
	printf("\n");
	printf("覆盖权：%f\n",this->Cover_Weight);
	printf("拥挤系数：%f\n",this->Delta);
	printf("%d条鱼:\n",this->Number_Of_fish);
	for(i=0;i<this->Number_Of_fish;i++){
		printf("第%d条:  邻居数 %d,食物 %f\n位置：",i,this->Fish[i].Amount_Of_Neighbour,this->Fish[i].Food_Consistence);
		for(int j=0;j<this->Amount_Of_Dimension;j++)
			printf("%d,",this->Fish[i].Position[j]);
		printf("\n");
	}
	printf("\n");
	printf("知识点数%d\n知识点：",this->Number_Of_Knowledge);
	for(i=0;i<this->Number_Of_Knowledge;i++)
		printf("%d,",this->Knowledge_Number_List[i]);
	printf("\n");
	printf("难度权:%f\n", this->Level_Weight);
	printf("总分权:%f\n",this->Point_Weight);
	printf("相邻关系:\n");
	for(i=0;i<this->Number_Of_fish;i++){
		for(int j=0;j<this->Number_Of_fish;j++)
			printf("%d ",this->Relation_Of_Fishes[i][j]);
		printf("\n");
	}
	printf("\n");
	printf("尝试次数:%d\n",this->Try_Number);
	printf("可见域：%d\n",this->Visual);
	printf("Want_Easist:%f\n",(float)this->Want_Easist);
	printf("Want_Easy:%f\n",(float)this->Want_Easy);
	printf("Want_Hard:%f\n",(float)this->Want_Hard);
	printf("Want_Hardest:%f\n",(float)this->Want_Hardest);
	printf("Want_Normal:%f\n",(float)this->Want_Normal);
}