timespacechromosome.cpp

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

/*
File timespacechromosome.cpp
*/

/*
Copyright 2005 Lalescu Liviu.

This file is part of FET.

FET is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

FET is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with FET; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/


#include "genetictimetable_defs.h"
#include "timespacechromosome.h"
#include "rules.h"
#include "timeconstraint.h"
#include "spaceconstraint.h"

#include <iostream>
using namespace std;

int better(Rules& r, TimeSpaceChromosome& c1, TimeSpaceChromosome& c2){ //returns true if c1 is better than c2
	//Here the order is important, you have to compute firstly the hard fitness, then the soft fitness
	int hf1=c1.hardFitness(r);
	int sf1=c1.softFitness(r);
	int hf2=c2.hardFitness(r);
	int sf2=c2.softFitness(r);

	return better(hf1, sf1, hf2, sf2);
}

//defined in timechromosome.cpp
/*int better(int hf1, int sf1, int hf2, int sf2){
	return hf1<hf2 || hf1==hf2 && sf1<sf2;
}*/

//critical function here - must be optimized for speed
void TimeSpaceChromosome::copy(Rules& r, TimeSpaceChromosome& c){
	this->_hardFitness=c._hardFitness;
	this->_softFitness=c._softFitness;

	assert(r.internalStructureComputed);

	for(int i=0; i<r.nInternalActivities; i++){
		this->times[i] = c.times[i];
		this->rooms[i] = c.rooms[i];
	}
	//memcpy(times, c.times, r.nActivities * sizeof(times[0]));
}

void TimeSpaceChromosome::init(Rules& r){
	assert(r.internalStructureComputed);

	for(int i=0; i<r.nInternalActivities; i++){
		this->times[i]=UNALLOCATED_TIME;
		this->rooms[i]=UNALLOCATED_SPACE;
	}

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

bool TimeSpaceChromosome::read(Rules& r, const QString& filename){
	assert(r.initialized);

	QFile file(filename);
	if(!file.open(IO_ReadOnly))
		assert(0);
	QTextStream tis(&file);
	this->read(r, tis);
	file.close();

	return true;
}

bool TimeSpaceChromosome::read(Rules &r, QTextStream &tis){
	assert(r.initialized);
	assert(r.internalStructureComputed);

	for(int i=0; i<r.nInternalActivities; i++){
		tis>>this->times[i];
		tis>>this->rooms[i];
		if(tis.eof()){
			//The rules and the solution do not match (1)
			return false;
		}

		if(this->times[i]>=r.nHoursPerWeek && this->times[i]!=UNALLOCATED_TIME){
			//The rules and the solution do not match (2)
			return false;
		}
		if(this->rooms[i]>=r.nInternalRooms && this->rooms[i]!=UNALLOCATED_SPACE){
			//The rules and the solution do not match (3)
			return false;
		}	
	}
	
	this->_hardFitness=this->_softFitness=-1;

	return true;
}

void TimeSpaceChromosome::write(Rules& r, const QString &filename){
	assert(r.initialized);

	QFile file(filename);
	if(!file.open(IO_WriteOnly))
		assert(0);
	QTextStream tos(&file);
	this->write(r, tos);
	file.close();
}

void TimeSpaceChromosome::write(Rules& r, QTextStream &tos){
	assert(r.initialized);
	assert(r.internalStructureComputed);

	for(int i=0; i<r.nInternalActivities; i++){
		tos<<this->times[i]<<endl;
		tos<<this->rooms[i]<<endl;
	}
}

void TimeSpaceChromosome::makeTimesRoomsUnallocated(Rules& r){
	assert(r.initialized);
	assert(r.internalStructureComputed);

	for(int i=0; i<r.nInternalActivities; i++){
		this->times[i]=UNALLOCATED_TIME;
		this->rooms[i]=UNALLOCATED_SPACE;
	}

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

void TimeSpaceChromosome::makeTimesRoomsRandom(Rules& r){
	assert(r.initialized);
	assert(r.internalStructureComputed);

	for(int i=0; i<r.nInternalActivities; i++){
		this->times[i] = rand()%r.nHoursPerWeek;
		this->rooms[i]=rand()%r.nInternalRooms;
	}

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


int TimeSpaceChromosome::hardFitness(Rules& r, QString* conflictsString){
	assert(r.initialized);
	assert(r.internalStructureComputed);

	if(this->_hardFitness>=0 && conflictsString==NULL)
	//If you want to see the log, you have to recompute the fitness, even if it is
	//already computed
		return this->_hardFitness;
		
	//Repair the chromosome - we enter here with the assumption that
	//the time constraints of type ConstraintActivityPreferredTime,
	//ConstraintActivitiesSameTime and Constraint2ActivitiesConsecutive
	//do not contradict one with each other.
	//I had good reasons here not to repair activities that are scheduled too late
	//(that is, have the hour+duration>nHoursPerDay.
	//The reason is that there might be a mutation by swapping 2 activities,
	//and I want it to consider all the variants.
	//I might be wrong :-)
	
	//1)preferred times
	for(int i=0; i<r.nInternalActivities; i++){
		if(r.fixedDay[i]>=0 && r.fixedHour[i]>=0){
			this->times[i] = r.fixedDay[i] + r.fixedHour[i] * r.nDaysPerWeek;
		}
		else if(r.fixedDay[i]>=0 && this->times[i]!=UNALLOCATED_TIME){
			this->times[i] = r.fixedDay[i] + (this->times[i]/r.nDaysPerWeek)*r.nDaysPerWeek;
		}
		else if(r.fixedHour[i]>=0 && this->times[i]!=UNALLOCATED_TIME){
			this->times[i] = (this->times[i]%r.nDaysPerWeek) + r.fixedHour[i]*r.nDaysPerWeek;
		}
	}
	//2)same starting day and/or hour
	for(int i=0; i<r.nInternalActivities; i++){
		if(r.sameDay[i]>=0 && r.sameHour[i]>=0 && this->times[r.sameDay[i]]!=UNALLOCATED_TIME && this->times[r.sameHour[i]]!=UNALLOCATED_TIME){
			int d = this->times[r.sameDay[i]] % r.nDaysPerWeek;
			int h = this->times[r.sameHour[i]] / r.nDaysPerWeek;
			this->times[i] = d + h * r.nDaysPerWeek;
			if(r.fixedDay[i]>=0)
				assert(r.fixedDay[i]==d);
			if(r.fixedHour[i]>=0)
				assert(r.fixedHour[i]==h);
		}
		if(r.sameDay[i]>=0 && this->times[i]!=UNALLOCATED_SPACE && this->times[r.sameDay[i]]!=UNALLOCATED_TIME){
			int d = this->times[r.sameDay[i]] % r.nDaysPerWeek;
			int h = this->times[i] / r.nDaysPerWeek;
			this->times[i] = d + h * r.nDaysPerWeek;
			if(r.fixedDay[i]>=0)
				assert(r.fixedDay[i]==d);
		}
		if(r.sameHour[i]>=0 && this->times[i]!=UNALLOCATED_SPACE && this->times[r.sameHour[i]]!=UNALLOCATED_TIME){
			int d = this->times[i] % r.nDaysPerWeek;
			int h = this->times[r.sameHour[i]] / r.nDaysPerWeek;
			this->times[i] = d + h * r.nDaysPerWeek;
			if(r.fixedHour[i]>=0)
				assert(r.fixedHour[i]==h);
		}
	}
	
	//repairing - space constraints
	for(int i=0; i<r.nInternalActivities; i++)
		if(r.fixedRoom[i]>=0)
			this->rooms[i]=r.fixedRoom[i];
			
	for(int i=0; i<r.nInternalActivities; i++)
		if(r.sameRoom[i]>=0 && this->rooms[r.sameRoom[i]]!=UNALLOCATED_SPACE){
			this->rooms[i]=this->rooms[r.sameRoom[i]];
			if(r.fixedRoom[i]>=0)
				assert(r.fixedRoom[i]==this->rooms[i]);
		}
	
	this->_hardFitness=0;
	//here we must not have compulsory activity preferred time nor 
	//compulsory activities same time
	//Also, here I compute soft fitness (for faster results,
	//I do not want to pass again through the constraints)
	this->_softFitness=0;
	for(int i=0; i<r.nInternalTimeConstraints; i++)
		if(r.internalTimeConstraintsList[i]->compulsory==true)
			this->_hardFitness += r.internalTimeConstraintsList[i]->fitness(*this, r, conflictsString);
		else
			//not logged here
			this->_softFitness += r.internalTimeConstraintsList[i]->fitness(*this, r, NULL);
			
	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;	
		}
			
	for(int i=0; i<r.nInternalSpaceConstraints; i++)
		if(r.internalSpaceConstraintsList[i]->compulsory==true)
			this->_hardFitness += r.internalSpaceConstraintsList[i]->fitness(*this, r, days, hours, conflictsString);
		else
			//not logged here
			this->_softFitness += r.internalSpaceConstraintsList[i]->fitness(*this, r, days, hours, NULL);

	return this->_hardFitness;
}

int TimeSpaceChromosome::softFitness(Rules& r, QString* conflictsString){
	assert(r.initialized);
	assert(r.internalStructureComputed);

	if(this->_softFitness>=0 && conflictsString==NULL) 
	//If you want to see the log, you have to recompute the fitness, even if it is 
	//already computed
		return this->_softFitness;
	
	assert(this->_softFitness>=0); //I must have calculated this before - this is just a check
	//I prefer to compute the soft fitness also in the hard fitness calculation,
	//to avoid double passing through the constraints

	this->_softFitness=0;
	for(int i=0; i<r.nInternalTimeConstraints; i++)
		if(r.internalTimeConstraintsList[i]->compulsory==false)
			this->_softFitness += r.internalTimeConstraintsList[i]->fitness(*this, r, conflictsString);

	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;	
		}
			
	for(int i=0; i<r.nInternalSpaceConstraints; i++)
		if(r.internalSpaceConstraintsList[i]->compulsory==false)
			this->_softFitness += r.internalSpaceConstraintsList[i]->fitness(*this, r, days, hours, conflictsString);