schedule.cpp

利用遗传算法自动进行排课

			{
				// check for overlapping with other classes at same time
				const list<CourseClass*>& cl = _slots[ t + i ];
				for( list<CourseClass*>::const_iterator it = cl.begin(); it != cl.end(); it++ )
				{
					if( cc != *it )
					{
						// professor overlaps?
						if( !po && cc->ProfessorOverlaps( **it ) )
							po = true;

						// student group overlaps?
						if( !go && cc->GroupsOverlap( **it ) )
							go = true;

						// both type of overlapping? no need to check more
						if( po && go )
							goto total_overlap;
					}
				}
			}
		}

total_overlap:

		// professors have no overlaping classes?
		if( !po )
			score++;
		_criteria[ ci + 3 ] = !po;

		// student groups has no overlaping classes?
		if( !go )
			score++;
		_criteria[ ci + 4 ] = !go;
	}

	// calculate fitess value based on score
	_fitness = (float)score / ( Configuration::GetInstance().GetNumberOfCourseClasses() * DAYS_NUM );
}

// Pointer to global instance of algorithm
Algorithm* Algorithm::_instance = NULL;

// Synchronization of creation and destruction of global instance
CCriticalSection Algorithm::_instanceSect;

// Returns reference to global instance of algorithm
Algorithm& Algorithm::GetInstance()
{
	CSingleLock lock( &_instanceSect, TRUE );

	// global instance doesn't exist?
	if( _instance == NULL )
	{
		// set seed for random generator
		srand( GetTickCount() );

		// make prototype of chromosomes
		Schedule* prototype = new Schedule( 2, 2, 80, 3 );

		// make new global instance of algorithm using chromosome prototype
		_instance = new Algorithm( 100, 8, 5, prototype, new ScheduleObserver() );
	}

	return *_instance;
}

// Frees memory used by gloval instance
void Algorithm::FreeInstance()
{
	CSingleLock lock( &_instanceSect, TRUE );

	// free memory used by global instance if it exists
	if( _instance != NULL )
	{
		delete _instance->_prototype;
		delete _instance->_observer;
		delete _instance;

		_instance = NULL;
	}
}

// Initializes genetic algorithm
Algorithm::Algorithm(int numberOfChromosomes, int replaceByGeneration, int trackBest,
					 Schedule* prototype, ScheduleObserver* observer) : _replaceByGeneration(replaceByGeneration),
					 _currentBestSize(0),
					 _prototype(prototype),
					 _observer(observer),
					 _currentGeneration(0),
					 _state(AS_USER_STOPED)
{
	// there should be at least 2 chromosomes in population
	if( numberOfChromosomes < 2 )
		numberOfChromosomes = 2;

	// and algorithm should track at least on of best chromosomes
	if( trackBest < 1 )
		trackBest = 1;

	if( _replaceByGeneration < 1 )
		_replaceByGeneration = 1;
	else if( _replaceByGeneration > numberOfChromosomes - trackBest )
		_replaceByGeneration = numberOfChromosomes - trackBest;

	// reserve space for population
	_chromosomes.resize( numberOfChromosomes );
	_bestFlags.resize( numberOfChromosomes );

	// reserve space for best chromosome group
	_bestChromosomes.resize( trackBest );

	// clear population
	for( int i = (int)_chromosomes.size() - 1; i >= 0; --i )
	{
		_chromosomes[ i ] = NULL;
		_bestFlags[ i ] = false;
	}
}

// Frees used resources
Algorithm::~Algorithm()
{
	// clear population by deleting chromosomes 
	for( vector<Schedule*>::iterator it = _chromosomes.begin(); it != _chromosomes.end(); ++it )
	{
		if( *it )
			delete *it;
	}
}

void Algorithm::Start()
{
	if( !_prototype )
		return;

	CSingleLock lock( &_stateSect, TRUE );

	// do not run already running algorithm
	if( _state == AS_RUNNING )
		return;

	_state = AS_RUNNING;

	lock.Unlock();

	if( _observer )
		// notify observer that execution of algorithm has changed it state
		_observer->EvolutionStateChanged( _state );

	// clear best chromosome group from previous execution
	ClearBest();

	// initialize new population with chromosomes randomly built using prototype
	int i = 0;
	for( vector<Schedule*>::iterator it = _chromosomes.begin(); it != _chromosomes.end(); ++it, ++i )
	{
		// remove chromosome from previous execution
		if( *it )
			delete *it;

		// add new chromosome to population
		*it = _prototype->MakeNewFromPrototype();
		AddToBest( i );
	}

	_currentGeneration = 0;

	while( 1 )
	{
		lock.Lock();

		// user has stopped execution?
		if( _state != AS_RUNNING )
		{
			lock.Unlock();
			break;
		}

		Schedule* best = GetBestChromosome();

		// algorithm has reached criteria?
		if( best->GetFitness() >= 1 )
		{
			_state = AS_CRITERIA_STOPPED;
			lock.Unlock();
			break;
		}

		lock.Unlock();

		// produce offepsing
		vector<Schedule*> offspring;
		offspring.resize( _replaceByGeneration );
		for( int j = 0; j < _replaceByGeneration; j++ )
		{
			// selects parent randomly
			Schedule* p1 = _chromosomes[ rand() % _chromosomes.size() ];
			Schedule* p2 = _chromosomes[ rand() % _chromosomes.size() ];

			offspring[ j ] = p1->Crossover( *p2 );
			offspring[ j ]->Mutation();
		}

		// replace chromosomes of current operation with offspring
		for( int j = 0; j < _replaceByGeneration; j++ )
		{
			int ci;
			do
			{
				// select chromosome for replacement randomly
				ci = rand() % (int)_chromosomes.size();

				// protect best chromosomes from replacement
			} while( IsInBest( ci ) );

			// replace chromosomes
			delete _chromosomes[ ci ];
			_chromosomes[ ci ] = offspring[ j ];

			// try to add new chromosomes in best chromosome group
			AddToBest( ci );
		}

		// algorithm has found new best chromosome
		if( best != GetBestChromosome() && _observer )
			// notify observer
			_observer->NewBestChromosome( *GetBestChromosome() );

		_currentGeneration++;
	}

	if( _observer )
		// notify observer that execution of algorithm has changed it state
		_observer->EvolutionStateChanged( _state );
}

// Stops execution of algoruthm
void Algorithm::Stop()
{
	CSingleLock lock( &_stateSect, TRUE );

	if( _state == AS_RUNNING )
		_state = AS_USER_STOPED;

	lock.Unlock();
}

// Returns pointer to best chromosomes in population
Schedule* Algorithm::GetBestChromosome() const
{
	return _chromosomes[ _bestChromosomes[ 0 ] ];
}

// Tries to add chromosomes in best chromosome group
void Algorithm::AddToBest(int chromosomeIndex)
{
	// don't add if new chromosome hasn't fitness big enough for best chromosome group
	// or it is already in the group?
	if( ( _currentBestSize == (int)_bestChromosomes.size() && 
		_chromosomes[ _bestChromosomes[ _currentBestSize - 1 ] ]->GetFitness() >= 
		_chromosomes[ chromosomeIndex ]->GetFitness() ) || _bestFlags[ chromosomeIndex ] )
		return;

	// find place for new chromosome
	int i = _currentBestSize;
	for( ; i > 0; i-- )
	{
		// group is not full?
		if( i < (int)_bestChromosomes.size() )
		{
			// position of new chromosomes is found?
			if( _chromosomes[ _bestChromosomes[ i - 1 ] ]->GetFitness() > 
				_chromosomes[ chromosomeIndex ]->GetFitness() )
				break;

			// move chromosomes to make room for new
			_bestChromosomes[ i ] = _bestChromosomes[ i - 1 ];
		}
		else
			// group is full remove worst chromosomes in the group
			_bestFlags[ _bestChromosomes[ i - 1 ] ] = false;
	}

	// store chromosome in best chromosome group
	_bestChromosomes[ i ] = chromosomeIndex;
	_bestFlags[ chromosomeIndex ] = true;

	// increase current size if it has not reached the limit yet
	if( _currentBestSize < (int)_bestChromosomes.size() )
		_currentBestSize++;
}

// Returns TRUE if chromosome belongs to best chromosome group
bool Algorithm::IsInBest(int chromosomeIndex)
{
	return _bestFlags[ chromosomeIndex ];
}

// Clears best chromosome group
void Algorithm::ClearBest()
{
	for( int i = (int)_bestFlags.size() - 1; i >= 0; --i )
		_bestFlags[ i ] = false;

	_currentBestSize = 0;
}