基于改进粒子群优化算法的排课问题

doi:10.3724/SP.J.1087.2013.00207

计算机应用 ›› 2013, Vol. 33 ›› Issue (01): 207-210.DOI: 10.3724/SP.J.1087.2013.00207

基于改进粒子群优化算法的排课问题

王念桥,姚四改

武汉职业技术学院电子信息工程学院，武汉 430074

收稿日期:2012-06-30 修回日期:2012-08-12 出版日期:2013-01-01 发布日期:2013-01-09
通讯作者: 王念桥
作者简介:王念桥(1971－)，男，湖北武汉人，讲师,硕士，主要研究方向：软件工程、智能控制机器人；姚四改(1965－)，女，湖北襄樊人，副教授，主要研究方向：计算机辅助设计。

Curriculum scheduling based on improved particle swarm optimization algorithm

WANG Nianqiao,YAO Sigai

Department of Electronic and Information, Wuhan Institute of Technology, Wuhan Hubei 430074, China

Received:2012-06-30 Revised:2012-08-12 Online:2013-01-01 Published:2013-01-09
Contact: WANG Nianqiao

摘要/Abstract

摘要： 深入分析了排课问题，提出一种基于离散粒子群的排课算法，构建了相应的解题框架。针对粒子群算法有后期收敛速度慢、易收敛于局部最优的缺点，结合排课问题的特点，对粒子群算法作了改进。在三维空间中建立模型，采用避免冲突的种群初始化加快收敛，并且引入变异操作避免陷入局部最优等。实践表明改进后的粒子群算法能有效地解决排课问题。

关键词: 排课问题, 粒子群优化算法, 组合优化, 变异

Abstract: After analyzing the problems of curriculum scheduling, an algorithm based on discrete particle swarm algorithm for the curriculum scheduling was proposed, with a framework for solving the problem. Because the particle swarm algorithm has a slow convergence speed during late period of its iterations and can easily be trapped in local optimal solution, an improved algorithm was applied with fully considering the features of curriculum scheduling. The algorithm was modeled in three-dimensional space, its particles were initialized with avoiding conflicts, and mutation was introduced to avoid being trapped in optimal solution, etc. The application makes it clear that the proposed algorithm can solve the curriculum scheduling problem effectively.

Key words: curriculum scheduling problem, Particle Swarm Optimization (PSO) algorithm, combinatorial optimization, mutation

中图分类号:

TP301.6

王念桥姚四改. 基于改进粒子群优化算法的排课问题[J]. 计算机应用, 2013, 33(01): 207-210.

WANG Nianqiao YAO Sigai. Curriculum scheduling based on improved particle swarm optimization algorithm[J]. Journal of Computer Applications, 2013, 33(01): 207-210.

参考文献

[1]ADEWUMI A O, SAWYERR B A, MONTAZ A M. A heuristic solution to the university timetabling problem ［J］. Engineering Computations, 2009, 26(8): 972-984.

[2]EVEN S, ITAI A, SHAMIR A. On the complexity of time table and multi-commodity flow problems ［J］. SIAM Journal on Computing, 1976, 5(4): 691-703.

[3]程学先,祝苏薇.一种基于动态规划的课程调度算法的研究与实现［J］.武汉理工大学学报:交通科学与工程版,2006,30(3):485-488.

[4]车明,秦存秀,刘凯.基于改进回溯算法的计算机排课系统［J］.沈阳工业大学学报,2006,28(6):667-670.

[5]SELIM S M. Split vertices in vertex colouring and their application in developing a solution to the faculty timetable problem ［J］. The Computer Journal, 1988, 31(1): 76-82.

[6]邓曦辉.浅谈贪心算法在排课系统中的应用［J］.电脑与电信,2011(7):29-30.

[7]梁艳春,吴春国,时小虎,等.群智能优化算法理论与应用［M］.北京:科学出版社,2009.

[8]KENNEDY J, EBERHART R C. Particle swarm optimization ［C］// Proceedings of IEEE International Conference on Neutral Networks. Piscataway: IEEE Press, 1995: 1942-1948.

[9]KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm ［C］// Proceedings of the IEEE International Conference on Systems,Man and Cybernetics. Piscataway: IEEE Press, 1997: 4104-4108.

[10]WANG K P, HUANG L, ZHOU C G, et al. Particle swarm optimization for traveling salesman problem ［C］// Proceedings of the IEEE International Conference on Machine Learning and Cybernetics. Piscataway: IEEE Press, 2003: 1583-1585.

[11]SHI X H, XING X L, WANG Q X, et al. A discrete PSO method for generalized TSP problem ［C］// Proceedings of the Third International Conference on Machine Learning and Cybernetics. Piscataway: IEEE Press, 2004: 2378-2383.

[12]吕振肃，侯志荣.自适应变异的粒子群优化算法［J］.电子学报，2004,32(3)：416-420.

[1]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[4]	付安兵, 魏文红, 张宇辉, 郭文静. 基于准反向变异的实数笛卡尔遗传编程算法[J]. 计算机应用, 2021, 41(2): 479-485.
[5]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[6]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[7]	李丽荣, 杨坤, 王培崇. 融合头脑风暴思想的教与学优化算法[J]. 计算机应用, 2020, 40(9): 2677-2682.
[8]	王博, 刘连生, 韩绍程, 祝世兴. 基于多策略融合的混合多目标蝗虫优化算法[J]. 计算机应用, 2020, 40(9): 2670-2676.
[9]	郭秀婷, 朱昶胜, 张生财, 赵奎鹏. 分形插值在风速时间序列中的应用[J]. 计算机应用, 2020, 40(9): 2628-2633.
[10]	罗斌, 于波. 移动边缘计算中基于粒子群优化的计算卸载策略[J]. 计算机应用, 2020, 40(8): 2293-2298.
[11]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[12]	周文峰, 梁晓磊, 唐可心, 李章洪, 符修文. 具有拓扑时变和搜索扰动的混合粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1913-1918.
[13]	李章洪, 梁晓磊, 田梦丹, 周文峰. 求解排列组合问题的解空间动态缩减策略[J]. 计算机应用, 2020, 40(7): 2016-2020.
[14]	霍晴晴, 郭健全. 基于改进遗传算法的生鲜多目标闭环物流网络模型[J]. 计算机应用, 2020, 40(5): 1494-1500.
[15]	杨云亭, 王鹏. 求解旅行商问题的多尺度量子自由粒子优化算法[J]. 计算机应用, 2020, 40(5): 1278-1283.

基于改进粒子群优化算法的排课问题

Curriculum scheduling based on improved particle swarm optimization algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics