我有一个大学课程表调度的问题,我正在尝试使用遗传算法来解决。我想知道对于此问题最好的编码类型是什么,它也可以帮助我满足一些限制条件。对于这个问题,时间表将具有以下结构,
- 将安排总共5天的时间表(星期一到星期五)。
- 每天将有5个不同的时间段,并且一个时间段将有一个授课。
- 然而,实验课将在连续两个时间段内进行。
- 时间表还将告诉每个授课的教室编号(或实验室编号)以及每个授课的讲师姓名。
现在,时间表看起来像这样,(图片中有多个时间段,但我将只考虑将时间表划分为这么多时间段之一的5个时间段)
这是一个部分班级的时间表。一个单独的时间表中大约有25个班级。
现在,我已经按照以下格式将每门课程、其班级和授课教师的数据写入一个文件中,
1
Object Oriented Programming
CS-3B
Dr Ali Hassan
,
2
Object Oriented Programming
SE-3A
Dr Ali Hassan
,
3
Remote Sensing and GIS
CS-7F
Dr Tom Baker
为了表示时间表,我已经将文件制作成这样:
0
1
2 2 9
3 2 9
0
2
2 1 9
3 1 9
0
3
2 5 36
4 1 36
- 0 是分隔符,用于将一个对象与另一个对象分开。
- 第一个数字基本上是课程的ID。 "1" 实际上代表了我的第一个文件中的第一个对象(即面向对象编程,CS-3A,Ali Hassan博士)。
- 第二行表示课程时间表中课程 id = 1 的第一堂课。格式如下,第一个数字 是 星期几。 第二个数字 是 时间段。 第三个数字 是 教室号码。 因此,在这种情况下,它表示课程id = 1的第一次讲座将在“星期二”,在“第2个时间段”和“9号教室”举行。
- 第三行表示同一门课程的第二堂课。
现在我需要对这个时间表进行编码。我选择使用二进制编码(当然,我可以转向其他编码方式,但需要知道哪种编码方式以及如何操作),并进行编码如下:
00000001 00000010 00000010 00001001 00000011 00000010 00001001
00000010 00000010 00000001 00001001 00000011 00000001 00001001
00000011 00000010 00000101 00100100 00000100 00000001 00100100
00000100 00000010 00000001 00001101 00000100 00000010 00000110
00000101 00000010 00000010 00001101 00000011 00000001 00000011
考虑到课程总数可能在200-220之间,因此我选择了8位编码。
采用以下格式进行编码:
Course_ID First_Lecture_Day First_Lecture_Slot First_Lecture_Room 2nd_Lec_Day 2nd_Lec_Slot 2nd_Lec_Room
现在,我想知道以下几件事情:
- 这个编码方式是否正确?或者我应该用其他方式来处理?
- 这个方案存在一个严重问题,即我有以下两个限制条件:
ss
- 实验室讲座必须在连续的两个时间段内进行。
- 课程讲座必须在不同的天数进行,即同一天不能有两个课程讲座。
现在,我可以通过在适应度函数中实现来解决第二个问题(我假设。我还没有进入那里,但我正在考虑我可以在那里解决此问题)
然而,我不知道如何解决第一个问题?是否有特定的方法可以指示遗传算法始终将实验室讲座保持在连续的时间段内?例如,我在我的二进制编码中使用另一个位,就像这样:
00000001 00000010 00000010 00001001 00000011 00000010 00001001 00000000
00000010 00000010 00000001 00001001 00000011 00000001 00001001 00000001
其中最后一位将告诉课程是实验室还是课程。根据该位,如果您更改讲座时间,则如果实验室位打开,则同时更改两个讲座时间,以便它们保持在一起,因此实验室将连续进行?我如何确保这一点?有人可以指导我吗?
另外,是否应该在遗传算法的编码过程中使用其他方法?谢谢。