使用遗传算法制作课程表
4.85/5 (101投票s)
如何使用遗传算法制作课程表。
目录
引言
制作课程表是 NP 难题之一。这个问题可以通过启发式搜索算法来解决，以找到最优解，但这只适用于简单的情况。对于更复杂的输入和要求，找到一个相当好的解决方案可能需要一段时间，或者根本不可能。这时遗传算法就派上用场了。在本文中，我假设您熟悉遗传算法的基本概念，并且不会详细描述它们，因为这已经说过很多次了。
背景
当您制作课程表时，必须考虑许多要求（教授、学生、课程和教室的数量、教室的大小、教室里的实验室设备等等）。这些要求可以根据其重要性分为几类。硬性要求（如果违反其中任何一条，则课程表将不可行）
- 课程只能安排在空闲的教室里。
- 任何教授或学生组在同一时间不能有超过一门课程。
- 教室必须有足够的座位容纳所有学生。
- 要将课程安排在教室中，如果课程需要实验室设备（在本例中为计算机），则该教室必须拥有实验室设备。
一些软性要求（可以打破，但课程表仍然可行）
- 教授偏好的上课时间。
- 教授偏好的教室。
- 学生组或教授的课程（按时间或空间）分布。
当然，硬性和软性要求取决于具体情况。在本例中，只实现了硬性要求。让我们开始解释构成课程表的对象。
课程表对象
教授
Professor 类具有教授的 ID 和姓名。它还包含教授所教课程的列表。
学生组
StudentsGroup 类具有学生组的 ID 和姓名，以及学生数量（组的大小）。它还包含学生组参加的课程列表。
教室
Room 类具有教室的 ID 和名称，以及座位数和设备信息（计算机）。如果教室有计算机，则预期每个座位都有计算机。ID 是内部自动生成的。
课程
Course 类具有课程的 ID 和名称。
类
CourseClass 包含一个对课程的引用，该课程属于该课程；一个对教授的引用，该教授讲授该课程；以及一个学生组列表，这些学生组参加该课程。它还存储了教室所需的座位数（学生组大小的总和），如果课程需要教室中的计算机，以及课程的持续时间（以小时为单位）。
染色体
当我们处理遗传算法时，首先要考虑的是如何表示我们的解决方案，使其能够进行交叉和变异等遗传操作。此外，我们应该知道如何指定我们解决方案的好坏程度。换句话说，我们应该能够计算我们解决方案的适应度值。
表示
我们如何表示课程表的染色体？嗯，我们需要为每个房间、每天的每个小时（我们假设时间是以小时为单位的）分配一个时间-空间槽。此外，我们假设课程不能早于上午 9 点开始，并且应在下午 9 点或之前结束（共 12 小时），工作日为周一至周五（共 5 天）。我们可以使用大小为 12*5*number_of_rooms 的 std::vector。该槽应该是一个 std::list，因为在算法执行过程中，我们允许在同一时间-空间槽内有多个课程。还有一个附加的哈希映射，用于从类对象的地址获取类开始的第一个时间-空间槽（它在向量中的位置）。课程的每个小时在向量中都有一个单独的条目，但在哈希映射中每个类只有一个条目。例如，如果一门课程从下午 1 点开始，持续三个小时，那么它在下午 1 点、下午 2 点和下午 3 点的槽中都有条目。
染色体由 Schedule 类表示，它在以下两个属性中存储课程表的表示
// Time-space slots, one entry represent one hour in one classroom
vector<list<CourseClass*>> _slots;
// Class table for chromosome
// Used to determine first time-space slot used by class
hash_map<CourseClass*, int> _classes;
此外，染色体还应存储其适应度值以及遗传操作使用的参数。
适应度值存储在此处
// Fitness value of chromosome
float _fitness;
// Flags of class requiroments satisfaction
vector<bool> _criteria;
染色体参数
// Number of crossover points of parent's class tables
int _numberOfCrossoverPoints;
// Number of classes that is moved randomly by single mutation operation
int _mutationSize;
// Probability that crossover will occure
int _crossoverProbability;
// Probability that mutation will occure
int _mutationProbability;
适应度
现在我们需要为染色体分配一个适应度值。如前所述，只有硬性要求用于计算课程表的适应度。我们这样做的方式如下：
- 每门课程可获得 0 到 5 分。
- 如果一门课程使用了空闲教室，我们就增加它的分数。
- 如果一门课程需要计算机并且它位于带有计算机的教室中，或者它不需要计算机，我们就增加该课程的分数。
- 如果一门课程位于有足够可用座位的教室中，你猜怎么着，我们就增加它的分数。
- 如果教授在同一时间没有其他课程，我们就再次增加该课程的分数。
- 我们检查的最后一件事是，参加该课程的任何学生组是否在同一时间有其他课程，如果没有，我们就增加该课程的分数。
- 如果一门课程在它占用的任何时间-空间槽中违反了规则，那么它在该规则下的分数就不会增加。
- 一门课程表总分数是所有课程分数的总和。
- 适应度值计算为
schedule_score/maximum_score，而maximum_score是number_of_classes*5。
适应度值表示为单精度浮点数 (float)，范围为 0 到 1。
交叉
交叉操作会合并两个父代哈希映射中的数据，然后根据新哈希映射的内容创建一个槽向量。交叉会“分割”两个父代的哈希映射，分成大小随机的部分。部分数量由染色体参数中的交叉点数量（加一）决定。然后，它会交替地从父代复制部分到新染色体，并形成一个新的槽向量。
// Performes crossover operation using to chromosomes
// and returns pointer to offspring
Schedule* Crossover(const Schedule& parent2) const;
变异
变异操作非常简单。它只是随机选择一门课程，并将其移动到另一个随机选择的槽。在单次操作中将要移动的课程数量由染色体参数中的变异大小决定。
// Performs mutation on chromosome
void Mutation();
算法
遗传算法相当简单。每一代，它执行两个基本操作：
- 从当前种群中随机选择 N 对父代，并通过对父代对进行交叉操作产生 N 个新染色体。
- 从当前种群中随机选择 N 个染色体，并用新染色体替换它们。如果某个染色体是种群中最好的染色体之一，算法就不会选择它进行替换。
这两个操作会重复进行，直到最好的染色体达到适应度值 1（表示课程表中的所有课程都满足要求）。如前所述，遗传算法会跟踪种群中 M 个最好的染色体，并确保它们在属于最好的染色体时不会被替换。
// Genetic algorithm
class Algorithm
{
private:
// Population of chromosomes
vector<Schedule*> _chromosomes;
// Inidicates wheahter chromosome belongs to
// best chromosome group
vector<bool> _bestFlags;
// Indices of best chromosomes
vector<int> _bestChromosomes;
// Number of best chromosomes currently saved in
// best chromosome group
int _currentBestSize;
// Number of chromosomes which are replaced in
// each generation by offspring
int _replaceByGeneration;
// Pointer to algorithm observer
ScheduleObserver* _observer;
// Prototype of chromosomes in population
Schedule* _prototype;
// Current generation
int _currentGeneration;
// State of execution of algorithm
AlgorithmState _state;
// Synchronization of algorithm's state
CCriticalSection _stateSect;
// Pointer to global instance of algorithm
static Algorithm* _instance;
// Synchronization of creation and destruction
// of global instance
static CCriticalSection _instanceSect;
public:
// Returns reference to global instance of algorithm
static Algorithm& GetInstance();
// Frees memory used by gloval instance
static void FreeInstance();
// Initializes genetic algorithm
Algorithm(int numberOfChromosomes,
int replaceByGeneration,
int trackBest,
Schedule* prototype,
ScheduleObserver* observer);
// Frees used resources
~Algorithm();
// Starts and executes algorithm
void Start();
// Stops execution of algoruthm
void Stop();
// Returns pointer to best chromosomes in population
Schedule* GetBestChromosome() const;
// Returns current generation
inline int GetCurrentGeneration() const { return _currentGeneration; }
// Returns pointe to algorithm's observer
inline ScheduleObserver* GetObserver() const { return _observer; }
private:
// Tries to add chromosomes in best chromosome group
void AddToBest(int chromosomeIndex);
// Returns TRUE if chromosome belongs to best chromosome group
bool IsInBest(int chromosomeIndex);
// Clears best chromosome group
void ClearBest();
};
观察
ScheduleObserver 类处理由遗传算法触发的事件。该类向应用程序的视图窗口发送消息。此外，您可以通过调用 WaitEvent() 方法来阻止调用线程，直到算法执行完成或停止。
// Handles event that is raised
// when algorithm finds new best chromosome
void NewBestChromosome(const Schedule& newChromosome);
// Handles event that is raised when state
// of execution of algorithm is changed
void EvolutionStateChanged(AlgorithmState newState);
// Block caller's thread until algorithm finishes execution
inline void WaitEvent() //...
如果您打算修改 NewBestChromosome 方法，请记住，如果您想保留最好的染色体以供显示，则必须制作硬拷贝（通过使用 Schedule 类的 MakeCopy 方法），因为算法可以在下一代中删除该染色体。
配置
配置文件
对象类型
- professor (
#prof标签) - 描述一位教授。 - course (
#course标签) - 描述一门课程。 - room (
#room标签) - 描述一个房间。 - group (
#group标签) - 描述一个学生组。 - course class (
#class标签) - 描述一门课，并将教授、课程和学生组关联起来。
每个对象都以其标签开头，以 #end 标签结束，所有标签必须单独一行。在对象体中，每行只包含一个键值对（属性），用 = 字符分隔。每个属性应仅指定一次，除了 #group 对象中的 group 属性，它可以有多个 group 属性。标签和键名区分大小写。以下是对象的属性列表：
#profid(数字，必需) - 教授的 ID。name(字符串，必需) - 教授的姓名。#courseid(数字，必需) - 课程的 ID。name(字符串，必需) - 课程的名称。#roomname(字符串，必需) - 教室的名称。size(数字，必需) - 教室的座位数。lab(布尔值，可选) - 指示房间是否为实验室（有计算机）；如果未指定，则默认值为 false。#groupid(数字，必需) - 学生组的 ID。name(字符串，必需) - 学生组的名称。size(数字，必需) - 学生组中的学生人数。#classprofessor(数字，必需) - 教授的 ID；将教授与课程关联。course(数字，必需) - 课程的 ID；将课程与课程关联。group(数字，必需) - 学生组的 ID；将学生组与课程关联；每门课程可以关联多个学生组。duration(数字，可选) - 课程持续时间（以小时为单位）；如果未指定，则默认值为 1。lab(布尔值，可选) - 如果课程需要房间中的计算机；如果未指定，则默认值为 false。
请注意，教授、学生组和课程对象必须在与课程类对象关联之前定义。
配置文件示例
#prof
id = 1
name = John Smith
#end
#course
id = 1
name = Introduction to Programming
#end
#room
name = R1
lab = true
size = 24
#end
#group
id = 1
name = 1O1
size = 19
#end
#class
professor = 1
course = 1
duration = 2
group = 1
group = 2
#end
#class
professor = 1
course = 1
duration = 3
group = 1
lab = true
#end
#class
professor = 1
course = 1
duration = 3
group = 2
lab = true
#end
解析配置
配置文件解析由 Configuration 类完成。ParseFile 方法打开并解析配置文件。它查找对象标签并调用适当的对象解析方法。ParseFile 方法还会清除先前解析的对象。
public:
void ParseFile(char* fileName);
private:
Professor* ParseProfessor(ifstream& file);
StudentsGroup* ParseStudentsGroup(ifstream& file);
Course* ParseCourse(ifstream& file);
Room* ParseRoom(ifstream& file);
CourseClass* ParseCourseClass(ifstream& file);
要解析文件
Configuration::GetInstance().ParseFile( "GaSchedule.cfg" );
解析的对象存储在哈希映射中，课程类除外，因此可以轻松快速地访问它们。
private:
hash_map<int, Professor*> _professors;
hash_map<int, StudentsGroup*> _studentGroups;
hash_map<int, Course*> _courses;
hash_map<int, Room*> _rooms;
list<CourseClass*> _courseClasses;
Configuration 类还包含用于检索已解析信息和对象的函数。
public:
inline Professor* GetProfessorById(int id) //...
inline int GetNumberOfProfessors() const //...
inline StudentsGroup* GetStudentsGroupById(int id) //...
inline int GetNumberOfStudentGroups() const //...
inline Course* GetCourseById(int id) //...
inline int GetNumberOfCourses() const //...
inline Room* GetRoomById(int id) //...
inline int GetNumberOfRooms() const //...
inline const list<CourseClass*>& GetCourseClasses() const //...
inline int GetNumberOfCourseClasses() const //...
附加信息
本文是基于 此文本，但采用不同的许可。