spacechromosome.h

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

/*
File spacechromosome.h
*/

/*
Copyright 2002, 2003 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
*/


#ifndef SPACECHROMOSOME_H
#define SPACECHROMOSOME_H

#include "genetictimetable_defs.h"

#include <qstring.h>
#include <qtextstream.h>
#include <qvaluevector.h>

class Rules;

/**
This class represents a chromosome (space allocation for the activities).
<p>
Every chromosome represents a solution candidate for the timetabling problem (space).
*/
class SpaceChromosome{
public:
	/**
	The genes of this chromosome (space).
	<p>
	This array represents every activity's allocated room.
	We have a special value here:
	UNALLOCATED_SPACE, which is a large number.
	*/
	int16 rooms[MAX_ACTIVITIES];

	/**
	Hard fitness; it is calculated only at the initialization
	of this chromosome or at the modification of it.
	Important assumption: the rules have to ramain the same;
	otherwise the user has to reset this value to -1
	*/
	int _hardFitness;

	/**
	Soft fitness; it is calculated only at the initialization
	of this chromosome or at the modification of it.
	Important assumption: the rules have to ramain the same;
	otherwise the user has to reset this value to -1
	*/
	int _softFitness;

	/**
	Assignment method. We need to have access to the Rules instantiation
	to know the number of activities.
	*/
	void copy(Rules& r, SpaceChromosome& c);

	/**
	Initializes a chromosome, marking all activities as unscheduled (space)
	*/
	void init(Rules& r);

	/**
	Marks the rooms of all the activities as undefined
	(all activities are unallocated).
	This is the first method of generating an initial population.
	*/
	void makeRoomsUnallocated(Rules& r);

	/**
	Randomizes the rooms of all the activities.
	This is the second method of generating an initial population.
	*/
	void makeRoomsRandom(Rules& r);

	/**
	Reads this chromosome from the disk (reads a saved solution).
	Returns false on failure, true on success.
	*/
	bool read(Rules& r, const QString &filename);

	/**
	Reads this chromosome from the disk (reads a saved solution).
	Returns false on failure, true on success.
	*/
	bool read(Rules& r, QTextStream &tis);

	/**
	Saves this chromosome to the disk (saves this solution).
	*/
	void write(Rules& r, const QString &filename);

	/**
	Saves this chromosome to the disk (saves this solution).
	*/
	void write(Rules &r, QTextStream &tos);

	/**
	Computes the unsatisfied compulsory constraints (stores the result in the
	variable _hardFitness, so that it is not recomputed when needed again later).
	ATTENTION: if the rules change, the user has to reset _hardFitness to -1
	<p>
	We need the time allocation of the activities
	<p>
	If conflictsString is not null, then this function will
	append at this string an explanation of the conflicts.
	*/
	int hardFitness(Rules& r, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/], QString* conflictsString=NULL);

	/**
	Computes the unsatisfied non-compulsory constraints (stores the result in the
	variable _softFitness, so that it is not recomputed when needed again later).
	ATTENTION: if the rules change, the user has to reset _softFitness to -1
	<p>
	We need the time allocation of the activities
	<p>
	If conflictsString is not null, then this function will
	append at this string an explanation of the conflicts.
	*/
	int softFitness(Rules& r, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/], QString* conflictsString=NULL);

	/**
	This chromosome is generated by the crossover of the two
	input chromosomes
	*/
	void crossover(Rules& r, SpaceChromosome& c1, SpaceChromosome& c2);

	/**
	This chromosome suffers mutation 1
	Random swap between two rooms
	(classical method).
	*/
	void mutate1(Rules& r);

	/**
	This chromosome suffers mutation 2.
	Changes an room into a random
	(experimental method).
	*/
	void mutate2(Rules& r);

	/**
	This function computes a matrix of rooms occupation in the week.
	Each weekly activity adds, for a room, day and hour, the value 2 to this matrix.
	(beweekly ones add only 1). So, if the value in a matrix cell is greater than 2,
	we have a conflict.
	The days and the hours represent the allocated times for the activities
	The return value is the number of conflicts (multiplied by two)
	*/
	int getRoomsMatrix(Rules& r, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/],
		int16 a[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY]);

	/**
	This is a function that retrieves the rooms timetable from
	this chromosome's "rooms" array.
	We have 2 matrices: the most used is the first one, for weekly activities
	(in this case the corresponding position in the second matrix is a
	special value, let's say UNALLOCATED_ACTIVITY)
	For bi-weekly activities we use both matrices: the first matrix
	keeps the activity scheduled for the first week, while the second
	matrix keeps the activity scheduled for the second week.
	The arrays a1 and a2 will contain the index of the activity in the rules.
	*/
	void getRoomsTimetable(Rules& r, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/], int16 a1[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY],int16 a2[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY]);
};

/**
This is a boolean function.
It returns 1 if c1 is better than c2.
<p>
We need to know the allocated time for the activities
*/
int better(Rules& r, SpaceChromosome& c1, SpaceChromosome& c2, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/]);

/**
This is a boolean function.
It returns 1 if c1 is better than c2. We have as parameters only the
fitnesses of the two chromosomes.
*/
int better(int hf1, int sf1, int hf2, int sf2);

#endif