timespacechromosome.cpp

基于遗传算法的排课软件源码 根据需要安排合理的课程时间等

	return this->_softFitness;
}

//critical function here - must be optimized for speed
void TimeSpaceChromosome::crossover(Rules& r, TimeSpaceChromosome& c1, TimeSpaceChromosome& c2){
	assert(r.internalStructureComputed);

	int q=rand()%(r.nInternalActivities+1);
	int i;
	for(i=0; i<q; i++)
		this->times[i]=c1.times[i];
	//memcpy(times, c1.times, q*sizeof(times[0]));
	for(; i<r.nInternalActivities; i++)
		this->times[i]=c2.times[i];
	//memcpy(times+q, c2.times+q, (r.nActivities-q)*sizeof(times[0]));
	
	q=rand()%(r.nInternalActivities+1);
	for(i=0; i<q; i++)
		this->rooms[i]=c1.rooms[i];
	for(; i<r.nInternalActivities; i++)
		this->rooms[i]=c2.rooms[i];

	this->_hardFitness = this->_softFitness = -1;
}

//critical function here - must be optimized for speed
void TimeSpaceChromosome::mutate1(Rules& r){
	int p,q,k;
	
	assert(r.internalStructureComputed);

	p=rand()%r.nInternalActivities;

	do{
		q=rand()%r.nInternalActivities;
	}while(p==q); //I think this is the fastest solution
		//because, suppose we have 10% of allowed values for q. Then, the probability 
		//that this step is performed 10 times is (0.9)^10=0.34...
		//obviusly, 10% is very little, generally we deal with more than 90% allowed values
	int m=rand()%100;
	if(m<50){
		k=this->times[p]; 
		this->times[p]=this->times[q]; 
		this->times[q]=k; //exchange the values
	}
	else{
		k=this->rooms[p];
		this->rooms[p]=this->rooms[q];
		this->rooms[q]=k;
	}

	this->_hardFitness = this->_softFitness = -1;
}

//critical function here - must be optimized for speed
void TimeSpaceChromosome::mutate2(Rules& r){
	assert(r.internalStructureComputed);
	
	int p,k;
	int m=rand()%100;
	if(m<50){
		p=rand()%r.nInternalActivities;
		k=rand()%r.nHoursPerWeek;
		this->times[p]=k;
	}
	else{
		p=rand()%r.nInternalActivities;
		k=rand()%r.nInternalRooms;
		this->rooms[p]=k;
	}

	this->_hardFitness = this->_softFitness = -1;
}

//critical function here - must be optimized for speed
int TimeSpaceChromosome::getTeachersMatrix(Rules& r, int16 a[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY]){
	assert(r.initialized);
	assert(r.internalStructureComputed);
	
	int conflicts=0;

	int i;
	for(i=0; i<r.nInternalTeachers; i++)
		for(int j=0; j<r.nDaysPerWeek; j++)
			for(int k=0; k<r.nHoursPerDay; k++)
				a[i][j][k]=0;

	for(i=0; i<r.nInternalActivities; i++)
		if(this->times[i]!=UNALLOCATED_TIME) {
			int hour = this->times[i] / r.nDaysPerWeek;
			int day = this->times[i] % r.nDaysPerWeek;
			Activity* act=&r.internalActivitiesList[i];
			for(int dd=0; dd<act->duration && hour+dd<r.nHoursPerDay; dd++)
				for(int it=0; it<act->nTeachers; it++){
					int tch=act->teachers[it];
					int tmp=a[tch][day][hour+dd];
					if(act->parity==PARITY_WEEKLY){
						conflicts += tmp<2 ? tmp : 2;
						a[tch][day][hour+dd]+=2;
					}
					else{
						assert(act->parity==PARITY_BIWEEKLY);
						conflicts += tmp<2 ? 0 : 1;
						a[tch][day][hour+dd]++;
					}
				}
		}
		
	return conflicts;
}

//critical function here - must be optimized for speed
int TimeSpaceChromosome::getSubgroupsMatrix(Rules& r, int16 a[MAX_TOTAL_SUBGROUPS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY]){
	assert(r.initialized);
	assert(r.internalStructureComputed);
	
	int conflicts=0;

	int i;
	for(i=0; i<r.nInternalSubgroups; i++)
		for(int j=0; j<r.nDaysPerWeek; j++)
			for(int k=0; k<r.nHoursPerDay; k++)
				a[i][j][k]=0;

	for(i=0; i<r.nInternalActivities; i++)
		if(this->times[i]!=UNALLOCATED_TIME){
			int hour=this->times[i]/r.nDaysPerWeek;
			int day=this->times[i]%r.nDaysPerWeek;
			Activity* act = &r.internalActivitiesList[i];
			for(int dd=0; dd < act->duration && hour+dd < r.nHoursPerDay; dd++)
				for(int isg=0; isg < act->nSubgroups; isg++){ //isg => index subgroup
					int sg = act->subgroups[isg]; //sg => subgroup
					int tmp=a[sg][day][hour+dd];
					if(act->parity == PARITY_WEEKLY){
						conflicts += tmp<2 ? tmp : 2;
						a[sg][day][hour+dd]+=2;
					}
					else{
						assert(act->parity == PARITY_BIWEEKLY);
						conflicts += tmp<2 ? 0 : 1;
						a[sg][day][hour+dd]++;
					}
				}
		}
		
	return conflicts;
}

//The following 2 functions (GetTeachersTimetable & GetSubgroupsTimetable)
//are very similar to the above 2 ones (GetTeachersMatrix & GetSubgroupsMatrix)
void TimeSpaceChromosome::getTeachersTimetable(Rules& r, int16 a1[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY],int16 a2[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY]){
	//assert(HFitness()==0); //This is only for perfect solutions, that do not have any non-satisfied hard constrains

	assert(r.initialized);
	assert(r.internalStructureComputed);

	int i, j, k;
	for(i=0; i<r.nInternalTeachers; i++)
		for(j=0; j<r.nDaysPerWeek; j++)
			for(k=0; k<r.nHoursPerDay; k++)
				a1[i][j][k]=a2[i][j][k]=UNALLOCATED_ACTIVITY;

	Activity *act;
	for(i=0; i<r.nInternalActivities; i++) if(this->times[i]!=UNALLOCATED_TIME) {
		act=&r.internalActivitiesList[i];
		int hour=this->times[i]/r.nDaysPerWeek;
		int day=this->times[i]%r.nDaysPerWeek;
		for(int dd=0; dd < act->duration && hour+dd < r.nHoursPerDay; dd++)
			for(int ti=0; ti<act->nTeachers; ti++){
				int tch = act->teachers[ti]; //teacher index
				if(a1[tch][day][hour+dd]==UNALLOCATED_ACTIVITY)
					a1[tch][day][hour+dd]=i;
				else
					a2[tch][day][hour+dd]=i;
			}
	}
}

void TimeSpaceChromosome::getSubgroupsTimetable(Rules& r, int16 a1[MAX_TOTAL_SUBGROUPS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY],int16 a2[MAX_TOTAL_SUBGROUPS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY]){
	//assert(HFitness()==0);	//This is only for perfect solutions, that do not have any non-satisfied hard constrains

	assert(r.initialized);
	assert(r.internalStructureComputed);

	int i, j, k;
	for(i=0; i<r.nInternalSubgroups; i++)
		for(j=0; j<r.nDaysPerWeek; j++)
			for(k=0; k<r.nHoursPerDay; k++)
				a1[i][j][k]=a2[i][j][k]=UNALLOCATED_ACTIVITY;

	Activity *act;
	for(i=0; i<r.nInternalActivities; i++) if(this->times[i]!=UNALLOCATED_TIME) {
		act=&r.internalActivitiesList[i];
		int hour=this->times[i]/r.nDaysPerWeek;
		int day=this->times[i]%r.nDaysPerWeek;
		for(int dd=0; dd < act->duration && hour+dd < r.nHoursPerDay; dd++){
			for(int isg=0; isg < act->nSubgroups; isg++){ //isg -> index subgroup
				int sg = act->subgroups[isg]; //sg -> subgroup
				if(a1[sg][day][hour+dd]==UNALLOCATED_ACTIVITY)
					a1[sg][day][hour+dd]=i;
				else
					a2[sg][day][hour+dd]=i;
			}
		}
	}
}

int TimeSpaceChromosome::getRoomsMatrix(Rules& r, int16 a[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY])
{
	assert(r.initialized);
	assert(r.internalStructureComputed);

	int days[MAX_ACTIVITIES], hours[MAX_ACTIVITIES];
	for(int i=0; i<r.nInternalActivities; i++)
		if(this->times[i]!=UNALLOCATED_TIME)
		{
			days[i]=this->times[i]%r.nDaysPerWeek;
			hours[i]=this->times[i]/r.nDaysPerWeek;
		}
		else{
			days[i]=UNALLOCATED_TIME;
			hours[i]=UNALLOCATED_TIME;	
		}

	int conflicts=0;

	int i;
	for(i=0; i<r.nInternalRooms; i++)
		for(int j=0; j<r.nDaysPerWeek; j++)
			for(int k=0; k<r.nHoursPerDay; k++)
				a[i][j][k]=0;

	for(i=0; i<r.nInternalActivities; i++){
		int room=this->rooms[i];
		int hour = hours[i];
		int day = days[i];
		if(room!=UNALLOCATED_SPACE && hour!=UNALLOCATED_TIME && day!=UNALLOCATED_TIME) {
			Activity* act=&r.internalActivitiesList[i];
			for(int dd=0; dd<act->duration && hour+dd<r.nHoursPerDay; dd++){
				int tmp=a[room][day][hour+dd];
				if(act->parity==PARITY_WEEKLY){
					conflicts += tmp<2 ? tmp : 2;
					a[room][day][hour+dd]+=2;
				}
				else{
					assert(act->parity==PARITY_BIWEEKLY);
					conflicts += tmp<2 ? 0 : 1;
					a[room][day][hour+dd]++;
				}
			}
		}
	}

	return conflicts;
}

void TimeSpaceChromosome::getRoomsTimetable(Rules& r,int16 a1[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY],int16 a2[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY])
{
	assert(r.initialized);
	assert(r.internalStructureComputed);

	int days[MAX_ACTIVITIES], hours[MAX_ACTIVITIES];
	for(int i=0; i<r.nInternalActivities; i++)
		if(this->times[i]!=UNALLOCATED_TIME)
		{
			days[i]=this->times[i]%r.nDaysPerWeek;
			hours[i]=this->times[i]/r.nDaysPerWeek;
		}
		else{
			days[i]=UNALLOCATED_TIME;
			hours[i]=UNALLOCATED_TIME;	
		}

	int i, j, k;
	for(i=0; i<r.nInternalRooms; i++)
		for(j=0; j<r.nDaysPerWeek; j++)
			for(k=0; k<r.nHoursPerDay; k++)
				a1[i][j][k]=a2[i][j][k]=UNALLOCATED_ACTIVITY;

	Activity *act;
	for(i=0; i<r.nInternalActivities; i++){
		act=&r.internalActivitiesList[i];
		int room=this->rooms[i];
		int day=days[i];
		int hour=hours[i];
		if(room!=UNALLOCATED_SPACE && day!=UNALLOCATED_TIME && hour!=UNALLOCATED_TIME){
			for(int dd=0; dd < act->duration && hour+dd < r.nHoursPerDay; dd++){
				if(a1[room][day][hour+dd]==UNALLOCATED_ACTIVITY)
					a1[room][day][hour+dd]=i;
				else
					a2[room][day][hour+dd]=i;
			}
		}
	}
}