排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中,涉及到的因素较多,是一个多目标的调度问题,在运筹学中被称为时间表问题(Timetable Problem,TTP)。设一个星期有n个时段可排课,有m位教师需要参与排课,平均每位教师一个星期上k节课,在不考虑其他限制的情况下,能够推出的可能组合就有 种,如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法,如模拟退火,列表寻优搜索和约束满意等。
Github : https://github.com/xiaochus/GeneticClassSchedule
遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的流程如下所示:
遗传算法首先针对待解决问题随机生成一组解,我们称之为种群(Population)。种群中的每个个体都是问题的解,在优化的过程中,算法会计算整个种群的成本函数,从而得到一个与种群相关的适应度的序列。如下图所示:
为了得到新的下一代种群,首先根据适应度对种群进行排序,从中挑选出最优的几个个体加入下一代种群,这一个过程也被称为精英选拔。新种群余下的部分通过对选拔出来的精英个体进行修改得到。
对种群进行修改的方法参考了生物DAN进化的方法,一般使用两种方法: 变异 和 交叉 。 变异 的做法是对种群做一个微小的、随机的改变。如果解的编码方式是二进制,那么就随机选取一个位置进行0和1的互相突变;如果解的编码方式是十进制,那么就随机选取一个位置进行随机加减。 交叉 的做法是随机从最优种群中选取两个个体,以某个位置为交叉点合成一个新的个体。
经过突变和交叉后我们得到新的种群(大小与上一代种群一致),对新种群重复重复上述过程,直到达到迭代次数(失败)或者解的适应性达到我们的要求(成功),GA算法就结束了。
算法实现
首先定义一个课程类,这个类包含了课程、班级、教师、教室、星期、时间几个属性,其中前三个是我们自定义的,后面三个是需要算法来优化的。
接下来定义cost函数,这个函数用来计算课表种群的冲突。当被测试课表冲突为0的时候,这个课表就是个符合规定的课表。冲突检测遵循下面几条规则:
使用遗传算法进行优化的过程如下,与上一节的流程图过程相同。
init_population :随机初始化不同的种群。
mutate :变异操作,随机对 Schedule 对象中的某个可改变属性在允许范围内进行随机加减。
crossover :交叉操作,随机对两个对象交换不同位置的属性。
evolution :启动GA算法进行优化。
实验结果
下面定义了3个班,6种课程、教师和3个教室来对排课效果进行测试。
优化结果如下,迭代到第68次时,课程安排不存在任何冲突。
选择1203班的课表进行可视化,如下所示,算法合理的安排了对应的课程。
前言:
不管学习哪门语言都希望能做出实际的东西来,这个实际的东西当然就是项目啦,不用多说大家都知道学编程语言一定要做项目才行。
这里整理了70个Python实战项目列表,都有完整且详细的教程,你可以从中选择自己想做的项目进行参考学习练手,你也可以从中寻找灵感去做自己的项目。
1、【Python 图片转字符画】
2、【200行Python代码实现2048】
3、【Python3 实现火车票查询工具】
4、【高德API+Python解决租房问题 】
5、【Python3 色情图片识别】
6、【Python 破解验证码】
7、【Python实现简单的Web服务器】
8、【pygame开发打飞机 游戏 】
9、【Django 搭建简易博客】
10、【Python基于共现提取《釜山行》人物关系】
11、【基于scrapy爬虫的天气数据采集(python)】
12、【Flask 开发轻博客】
13、【Python3 图片隐写术】
14、【Python 实现简易 Shell】
15、【使用 Python 解数学方程】
16、【PyQt 实现简易浏览器】
17、【神经网络实现手写字符识别系统 】
18、【Python 实现简单画板】
19、【Python实现3D建模工具】
20、【NBA常规赛结果预测——利用Python进行比赛数据分析】
21、【神经网络实现人脸识别任务】
22、【Python文本解析器】
23、【Python3 &OpenCV 视频转字符动画】
24、【Python3 实现淘女郎照片爬虫 】
25、【Python3实现简单的FTP认证服务器】
26、【基于 Flask 与 MySQL 实现番剧推荐系统】
27、【Python 实现端口扫描器】
28、【使用 Python 3 编写系列实用脚本】
29、【Python 实现康威生命 游戏 】
30、【川普撞脸希拉里(基于 OpenCV 的面部特征交换) 】
31、【Python 3 实现 Markdown 解析器】
32、【Python 气象数据分析 -- 《Python 数据分析实战》】
33、【Python实现键值数据库】
34、【k-近邻算法实现手写数字识别系统】
35、【ebay在线拍卖数据分析】
36、【Python 实现英文新闻摘要自动提取 】
37、【Python实现简易局域网视频聊天工具】
38、【基于 Flask 及爬虫实现微信 娱乐 机器人】
39、【Python实现Python解释器】
40、【Python3基于Scapy实现DDos】
41、【Python 实现密码强度检测器】
42、【使用 Python 实现深度神经网络】
43、【Python实现从excel读取数据并绘制成精美图像】
44、【人机对战初体验:Python基于Pygame实现四子棋 游戏 】
45、【Python3 实现可控制肉鸡的反向Shell】
46、【Python打造漏洞扫描器 】
47、【Python应用马尔可夫链算法实现随机文本生成】
48、【数独 游戏 的Python实现与破解】
49、【使用Python定制词云】
50、【Python开发简单计算器】
51、【Python 实现 FTP 弱口令扫描器】
52、【Python实现Huffman编码解压缩文件】
53、【Python实现Zip文件的暴力破解 】
54、【Python3 智能裁切图片】
55、【Python实现网站模拟登陆】
56、【给Python3爬虫做一个界面.妹子图网实战】
57、【Python 3 实现图片转彩色字符】
58、【自联想器的 Python 实现】
59、【Python 实现简单滤镜】
60、【Flask 实现简单聊天室】
61、【基于PyQt5 实现地图中定位相片拍摄位置】
62、【Python实现模板引擎】
63、【Python实现遗传算法求解n-queens问题】
64、【Python3 实现命令行动态进度条】
65、【Python 获取挂号信息并邮件通知】
66、【Python实现java web项目远端自动化更新部署】
67、【使用 Python3 编写 Github 自动周报生成器】
68、【使用 Python 生成分形图片】
69、【Python 实现 Redis 异步客户端】
70、【Python 实现中文错别字高亮系统】
最后:
以上项目列表希望可以给你在Python学习中带来帮助~
获取方式:转发 私信“1”