schedule.cpp

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

////////////////////////////////////
// (C)2007-2008 Coolsoft Company. //
// All rights reserved.           //
// http://www.coolsoft-sd.com     //
// Licence: licence.txt           //
////////////////////////////////////

#include "stdafx.h"
#include <iostream>
#include <vector>

#include "..\ChildView.h"
#include "Configuration.h"
#include "Schedule.h"
#include "Room.h"

// Handles event that is raised when algorithm finds new best chromosome
void ScheduleObserver::NewBestChromosome(const Schedule& newChromosome)
{
	if( _window )
		_window->SetSchedule( &newChromosome );
}

// Handles event that is raised when state of execution of algorithm is changed
void ScheduleObserver::EvolutionStateChanged(AlgorithmState newState)
{
	if( _window )
		_window->SetNewState( newState );

	newState != AS_RUNNING ? ReleaseEvent() : BlockEvent();
}

// Initializes chromosomes with configuration block (setup of chromosome)
Schedule::Schedule(int numberOfCrossoverPoints, int mutationSize,
				   int crossoverProbability, int mutationProbability) : _mutationSize(mutationSize),
				   _numberOfCrossoverPoints(numberOfCrossoverPoints),
				   _crossoverProbability(crossoverProbability),
				   _mutationProbability(mutationProbability),
				   _fitness(0)
{
	// reserve space for time-space slots in chromosomes code
	_slots.resize( DAYS_NUM * DAY_HOURS * Configuration::GetInstance().GetNumberOfRooms() );

	// reserve space for flags of class requirements
	_criteria.resize( Configuration::GetInstance().GetNumberOfCourseClasses() * 5 );
}

// Copy constructor
Schedule::Schedule(const Schedule& c, bool setupOnly)
{
	if( !setupOnly )
	{
		// copy code
		_slots = c._slots;
		_classes = c._classes;

		// copy flags of class requirements
		_criteria = c._criteria;

		// copy fitness
		_fitness = c._fitness;
	}
	else
	{
		// reserve space for time-space slots in chromosomes code
		_slots.resize( DAYS_NUM * DAY_HOURS * Configuration::GetInstance().GetNumberOfRooms() );

		// reserve space for flags of class requirements
		_criteria.resize( Configuration::GetInstance().GetNumberOfCourseClasses() * 5 );
	}

	// copy parameters
	_numberOfCrossoverPoints = c._numberOfCrossoverPoints;
	_mutationSize = c._mutationSize;
	_crossoverProbability = c._crossoverProbability;
	_mutationProbability = c._mutationProbability;
}

// Makes copy ot chromosome
Schedule* Schedule::MakeCopy(bool setupOnly) const
{
	// make object by calling copy constructor and return smart pointer to new object
	return new Schedule( *this, setupOnly );
}

// Makes new chromosome with same setup but with randomly chosen code
Schedule* Schedule::MakeNewFromPrototype() const
{
	// number of time-space slots
	int size = (int)_slots.size();

	// make new chromosome, copy chromosome setup
	Schedule* newChromosome = new Schedule( *this, true );

	// place classes at random position
	const list<CourseClass*>& c = Configuration::GetInstance().GetCourseClasses();
	for( list<CourseClass*>::const_iterator it = c.begin(); it != c.end(); it++ )
	{
		// determine random position of class
		int nr = Configuration::GetInstance().GetNumberOfRooms();
		int dur = ( *it )->GetDuration();
		int day = rand() % DAYS_NUM;
		int room = rand() % nr;
		int time = rand() % ( DAY_HOURS + 1 - dur );
		int pos = day * nr * DAY_HOURS + room * DAY_HOURS + time;

		// fill time-space slots, for each hour of class
		for( int i = dur - 1; i >= 0; i-- )
			newChromosome->_slots.at( pos + i ).push_back( *it );

		// insert in class table of chromosome
		newChromosome->_classes.insert( pair<CourseClass*, int>( *it, pos ) );
	}

	newChromosome->CalculateFitness();

	// return smart pointer
	return newChromosome;
}

// Performes crossover operation using to chromosomes and returns pointer to offspring
Schedule* Schedule::Crossover(const Schedule& parent2) const
{
	// check probability of crossover operation
	if( rand() % 100 > _crossoverProbability )
		// no crossover, just copy first parent
		return new Schedule( *this, false );

	// new chromosome object, copy chromosome setup
	Schedule* n = new Schedule( *this, true );

	// number of classes
	int size = (int)_classes.size();

	vector<bool> cp( size );

	// determine crossover point (randomly)
	for( int i = _numberOfCrossoverPoints; i > 0; i-- )
	{
		while( 1 )
		{
			int p = rand() % size;
			if( !cp[ p ] )
			{
				cp[ p ] = true;
				break;
			}
		}
	}

	hash_map<CourseClass*, int>::const_iterator it1 = _classes.begin();
	hash_map<CourseClass*, int>::const_iterator it2 = parent2._classes.begin();

	// make new code by combining parent codes
	bool first = rand() % 2 == 0;
	for( int i = 0; i < size; i++ )
	{
		if( first )
		{
			// insert class from first parent into new chromosome's calss table
			n->_classes.insert( pair<CourseClass*, int>( ( *it1 ).first, ( *it1 ).second ) );
			// all time-space slots of class are copied
			for( int i = ( *it1 ).first->GetDuration() - 1; i >= 0; i-- )
				n->_slots[ ( *it1 ).second + i ].push_back( ( *it1 ).first );
		}
		else
		{
			// insert class from second parent into new chromosome's calss table
			n->_classes.insert( pair<CourseClass*, int>( ( *it2 ).first, ( *it2 ).second ) );
			// all time-space slots of class are copied
			for( int i = ( *it2 ).first->GetDuration() - 1; i >= 0; i-- )
				n->_slots[ ( *it2 ).second + i ].push_back( ( *it2 ).first );
		}

		// crossover point
		if( cp[ i ] )
			// change soruce chromosome
			first = !first;

		it1++;
		it2++;
	}

	n->CalculateFitness();

	// return smart pointer to offspring
	return n;
}

// Performs mutation on chromosome
void Schedule::Mutation()
{
	// check probability of mutation operation
	if( rand() % 100 > _mutationProbability )
		return;

	// number of classes
	int numberOfClasses = (int)_classes.size();
	// number of time-space slots
	int size = (int)_slots.size();

	// move selected number of classes at random position
	for( int i = _mutationSize; i > 0; i-- )
	{
		// select ranom chromosome for movement
		int mpos = rand() % numberOfClasses;
		int pos1 = 0;
		hash_map<CourseClass*, int>::iterator it = _classes.begin();
		for( ; mpos > 0; it++, mpos-- )
			;

		// current time-space slot used by class
		pos1 = ( *it ).second;

		CourseClass* cc1 = ( *it ).first;

		// determine position of class randomly
		int nr = Configuration::GetInstance().GetNumberOfRooms();
		int dur = cc1->GetDuration();
		int day = rand() % DAYS_NUM;
		int room = rand() % nr;
		int time = rand() % ( DAY_HOURS + 1 - dur );
		int pos2 = day * nr * DAY_HOURS + room * DAY_HOURS + time;

		// move all time-space slots
		for( int i = dur - 1; i >= 0; i-- )
		{
			// remove class hour from current time-space slot
			list<CourseClass*>& cl = _slots[ pos1 + i ];
			for( list<CourseClass*>::iterator it = cl.begin(); it != cl.end(); it++ )
			{
				if( *it == cc1 )
				{
					cl.erase( it );
					break;
				}
			}

			// move class hour to new time-space slot
			_slots.at( pos2 + i ).push_back( cc1 );
		}

		// change entry of class table to point to new time-space slots
		_classes[ cc1 ] = pos2;
	}

	CalculateFitness();
}

// Calculates fitness value of chromosome
void Schedule::CalculateFitness()
{
	// chromosome's score
	int score = 0;

	int numberOfRooms = Configuration::GetInstance().GetNumberOfRooms();
	int daySize = DAY_HOURS * numberOfRooms;

	int ci = 0;

	// check criterias and calculate scores for each class in schedule
	for( hash_map<CourseClass*, int>::const_iterator it = _classes.begin(); it != _classes.end(); ++it, ci += 5 )
	{
		// coordinate of time-space slot
		int p = ( *it ).second;
		int day = p / daySize;
		int time = p % daySize;
		int room = time / DAY_HOURS;
		time = time % DAY_HOURS;

		int dur = ( *it ).first->GetDuration();

		// check for room overlapping of classes
		bool ro = false;
		for( int i = dur - 1; i >= 0; i-- )
		{
			if( _slots[ p + i ].size() > 1 )
			{
				ro = true;
				break;
			}
		}

		// on room overlaping
		if( !ro )
			score++;

		_criteria[ ci + 0 ] = !ro;

		CourseClass* cc = ( *it ).first;
		Room* r = Configuration::GetInstance().GetRoomById( room );
		// does current room have enough seats
		_criteria[ ci + 1 ] = r->GetNumberOfSeats() >= cc->GetNumberOfSeats();
		if( _criteria[ ci + 1 ] )
			score++;

		// does current room have computers if they are required
		_criteria[ ci + 2 ] = !cc->IsLabRequired() || ( cc->IsLabRequired() && r->IsLab() );
		if( _criteria[ ci + 2 ] )
			score++;

		bool po = false, go = false;
		// check overlapping of classes for professors and student groups
		for( int i = numberOfRooms, t = day * daySize + time; i > 0; i--, t += DAY_HOURS )
		{
			// for each hour of class
			for( int i = dur - 1; i >= 0; i-- )