afsa.cpp

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

#include "StdAfx.h"
#include ".\afsa.h"

AFSA::AFSA(int Visual,int Try_Number,Question_List_Class* Question_List,int Number_Of_Question,long* Knowledge_Number_List,int Number_Of_Knowledge,int Want_Hardest,int Want_Hard,int Want_Normal,int Want_Easy,int Want_Easist,float Level_Weight,float Cover_Weight,float Point_Weight,int Number_Of_fish,float Delta)
{
	//只给一次随机数种子
	static int a=0;
	if(a!=1){
		a=1;
		srand((unsigned)time(NULL));
	}
	this->Relation_Of_Fishes=NULL;
	this->Fish=NULL;
	this->Cover_Weight=Cover_Weight;
	this->Delta=Delta;
	this->Level_Weight=Level_Weight;
	this->Point_Weight=Point_Weight;
	this->Try_Number=Try_Number;
	this->Visual=Visual;
	this->Want_Easist=Want_Easist;
	this->Want_Easy=Want_Easy;
	this->Want_Hard=Want_Hard;
	this->Want_Hardest=Want_Hardest;
	this->Want_Normal=Want_Normal;
	this->Amount_Of_Dimension=Number_Of_Question;
	this->Question_List=new Question_List_Class[Number_Of_Question];
	for(int i=0;i<Number_Of_Question;i++){
		this->Question_List[i].Number_Of_Cover_Knowledge=Question_List[i].Number_Of_Cover_Knowledge;
		this->Question_List[i].Knowledge_Number_List=new long[this->Question_List[i].Number_Of_Cover_Knowledge];
		for(int j=0;j<Question_List[i].Number_Of_Cover_Knowledge;j++)
			this->Question_List[i].Knowledge_Number_List[j]=Question_List[i].Knowledge_Number_List[j];
		this->Question_List[i].Question_Hard_Level=Question_List[i].Question_Hard_Level;
		this->Question_List[i].Question_Number=Question_List[i].Question_Number;
		this->Question_List[i].Question_Value=Question_List[i].Question_Value;
	}
	this->Number_Of_Knowledge=Number_Of_Knowledge;
	this->Knowledge_Number_List=new long[Number_Of_Knowledge];
	for(i=0;i<Number_Of_Knowledge;i++)
		this->Knowledge_Number_List[i]=Knowledge_Number_List[i];
	//计算人工鱼的条数
	if(Number_Of_fish<=0){
		this->Number_Of_fish=this->Amount_Of_Dimension/10+3;
		Number_Of_fish=this->Amount_Of_Dimension/10+3;
	}
	else this->Number_Of_fish=Number_Of_fish;
	this->Fish=new Fish_Class[Number_Of_fish];
	for(i=0;i<Number_Of_fish;i++)
		this->Fish[i].Amount_Of_Neighbour=0;//邻居数为0
	this->Relation_Of_Fishes=new int*[this->Number_Of_fish];
	for(i=0;i<this->Number_Of_fish;i++){
		this->Relation_Of_Fishes[i]=new int[this->Number_Of_fish];
		for(int j=0;j<this->Number_Of_fish;j++)
			this->Relation_Of_Fishes[i][j]=0;//邻居数为0
	}
	for(i=0;i<this->Number_Of_fish;i++){
		this->Fish[i].Position=new int[this->Amount_Of_Dimension];
		for(int k=0;k<this->Amount_Of_Dimension;k++){
			this->Fish[i].Position[k]=rand()%2;
		}
	}
	for(i=0;i<this->Number_Of_fish;i++)
		this->Set_Neighbour(i);
	int ig1,ig2,best_position;
	float ig3,best_food;
	best_food=-1;
	for(i=0;i<this->Number_Of_fish;i++){
		this->Set_Food_Consistence(i,this->Get_Food_Consistence(this->Fish[i].Position,ig1,ig2,ig3));
		if(best_food==-1){
			best_food=this->Fish[i].Food_Consistence;
			best_position=i;
		}
		else{
			if(best_food>this->Fish[i].Food_Consistence){
				best_food=this->Fish[i].Food_Consistence;
				best_position=i;
			}
		}
	}
	this->Bulletin_Board.Food_Consistence=best_food;
	this->Bulletin_Board.Amount_Of_Neighbour=this->Fish[best_position].Amount_Of_Neighbour;
	this->Bulletin_Board.Position=new int[this->Amount_Of_Dimension];
	for(i=0;i<this->Amount_Of_Dimension;i++)
		this->Bulletin_Board.Position[i]=this->Fish[best_position].Position[i];
}

AFSA::~AFSA(void)
{
	for(int i=0;i<this->Amount_Of_Dimension;i++)
		delete[] this->Question_List[i].Knowledge_Number_List;
	delete[] this->Question_List;
	delete[] this->Knowledge_Number_List;
	for(int i=0;i<this->Number_Of_fish;i++)
		delete[] this->Fish[i].Position;
	delete[] this->Fish;
	delete[] this->Bulletin_Board.Position;
	for(i=0;i<this->Number_Of_fish;i++)
		delete[] this->Relation_Of_Fishes[i];
	delete[] this->Relation_Of_Fishes;
	
}
// 设置某条鱼的食物浓度，鱼在数组中的号，鱼的食物浓度
int AFSA::Set_Food_Consistence(int Symbol_Of_Fish, float Food_Consistence)
{
	if(this->Number_Of_fish<=Symbol_Of_Fish||Symbol_Of_Fish<0||this->Fish==NULL) return 0;
	else{
		this->Fish[Symbol_Of_Fish].Food_Consistence=Food_Consistence;
		return 1;
	}
}

int AFSA::Rand_Move(int Symbol_Of_Fish)
{
	if(this->Number_Of_fish<=Symbol_Of_Fish||Symbol_Of_Fish<0||this->Fish==NULL) return 0;
	else{
		int* temp=new int[this->Amount_Of_Dimension];
		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 flag=true;
			for(int k=0;flag;k++){
				if(temp[k]==0){
					if(rand_number==0){
						temp[k]=1;
						this->Fish[Symbol_Of_Fish].Position[k]=rand()%2;
						flag=false;
					}
					else{
						rand_number--;
					}
				}
			}
		}
		this->Set_Neighbour(Symbol_Of_Fish);
		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));
		delete[] temp;
		return 1;
	}
			
}

float AFSA::Get_Food_Consistence(int* Position,int &Most_Hard_Level_Difference,int &Amount_Difference,float &Cover_Difference)
{
	int hardest,hard,normal,easy,easist,amount;
	hardest=hard=normal=easy=easist=amount=0;
	long *covered=new long[this->Number_Of_Knowledge];
	for(int i=0;i<this->Number_Of_Knowledge;i++) covered[i]=0;
	for(i=0;i<this->Amount_Of_Dimension;i++){
		if(Position[i]==1){
			switch(this->Question_List[i].Question_Hard_Level){
				case 1:hardest+=this->Question_List[i].Question_Value;break;
				case 2:hard+=this->Question_List[i].Question_Value;break;
				case 3:normal+=this->Question_List[i].Question_Value;break;
				case 4:easy+=this->Question_List[i].Question_Value;break;
				case 5:easist+=this->Question_List[i].Question_Value;break;
			}
			amount+=this->Question_List[i].Question_Value;
			for(int j=0;j<this->Question_List[i].Number_Of_Cover_Knowledge;j++){
				bool flag;
				flag=true;
				for(int k=0;flag;k++){
					if(this->Knowledge_Number_List[k]==this->Question_List[i].Knowledge_Number_List[j]){
						covered[k]=1;
						flag=false;
					}
				}
			}
		}
	}
	Most_Hard_Level_Difference=abs(hardest-this->Want_Hardest);
	Most_Hard_Level_Difference=Most_Hard_Level_Difference<abs(hard-this->Want_Hard)?abs(hard-this->Want_Hard):Most_Hard_Level_Difference;
	Most_Hard_Level_Difference=Most_Hard_Level_Difference<abs(normal-this->Want_Normal)?abs(normal-this->Want_Normal):Most_Hard_Level_Difference;
	Most_Hard_Level_Difference=Most_Hard_Level_Difference<abs(easy-this->Want_Easy)?abs(easy-this->Want_Easy):Most_Hard_Level_Difference;
	Most_Hard_Level_Difference=Most_Hard_Level_Difference<abs(easist-this->Want_Easist)?abs(easist-this->Want_Easist):Most_Hard_Level_Difference;
	Amount_Difference=abs(amount-this->Want_Normal-this->Want_Hardest-this->Want_Hard-this->Want_Easy-this->Want_Easist);
	float c=0;
	for(i=0;i<this->Number_Of_Knowledge;i++){
		c+=covered[i];
	}
	Cover_Difference=(1-c/this->Number_Of_Knowledge);
	delete[] covered;
	return (float)((fabsf((float)(hardest-this->Want_Hardest))+fabsf((float)(hard-this->Want_Hard))+fabsf((float)(normal-this->Want_Normal))+fabsf((float)(easy-this->Want_Easy))+fabsf((float)(easist-this->Want_Easist)))/(this->Want_Hardest+this->Want_Hard+this->Want_Normal+this->Want_Easy+this->Want_Easist)*this->Level_Weight+Cover_Difference*this->Cover_Weight+((float)Amount_Difference/(this->Want_Easist+this->Want_Easy+this->Want_Hard+this->Want_Hardest+this->Want_Normal))*this->Point_Weight);
}

// 计算第Symbol_Of_Fish条鱼和其它鱼的相邻关系
int AFSA::Set_Neighbour(int Symbol_Of_Fish)
{
	if(this->Number_Of_fish<=Symbol_Of_Fish||Symbol_Of_Fish<0||this->Fish==NULL) return 0;
	else{
		for(int i=0;i<this->Number_Of_fish;i++){
			if(i!=Symbol_Of_Fish){
				int distance;
				distance=0;
				for(int j=0;j<this->Amount_Of_Dimension;j++)
					if(this->Fish[i].Position[j]!=this->Fish[Symbol_Of_Fish].Position[j]) distance++;
				if(distance>this->Visual){
					if(this->Relation_Of_Fishes[Symbol_Of_Fish][i]==0) ;
					else{
						this->Relation_Of_Fishes[Symbol_Of_Fish][i]=0;
						this->Relation_Of_Fishes[i][Symbol_Of_Fish]=0;
						this->Fish[Symbol_Of_Fish].Amount_Of_Neighbour--;
						this->Fish[i].Amount_Of_Neighbour--;//相关的鱼也要变化
					}
				}
				else{
					if(this->Relation_Of_Fishes[Symbol_Of_Fish][i]==1) ;
					else{
						this->Relation_Of_Fishes[Symbol_Of_Fish][i]=1;
						this->Relation_Of_Fishes[i][Symbol_Of_Fish]=1;
						this->Fish[Symbol_Of_Fish].Amount_Of_Neighbour++;
						this->Fish[i].Amount_Of_Neighbour++;//相关的鱼也要变化
					}
				}
			}
		}
		return 1;
	}
}
	

// 觅食
int AFSA::Prey(int Symbol_Of_Fish)
{
	if(this->Number_Of_fish<=Symbol_Of_Fish||Symbol_Of_Fish<0||this->Fish==NULL) return 0;
	else{
		bool flag=true;
		int *temp_position=new int[this->Amount_Of_Dimension];
		int* temp=new int[this->Amount_Of_Dimension];
		for(int i=0;i<this->Try_Number&&flag;i++){
			//将这条鱼拷贝到temp中