探析基于遗传算法的排课问题研究

《探析基于遗传算法的排课问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南交通大学硕士学位论文基于遗传算法的排课问题研究姓名：熊学申请学位级别：硕士专业：交通信息工程及控制指导教师：严余松20080601西南交通大学硕士研究生学位论文第1页摘要排课问题是一个有约束、多目标的组合优化问题，已经被证明是一个NP完全问题。遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法，由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。本文将遗传算法应用于排课问题求解，首先讨论了排课问题的影响要素、主要约束条件、求解目标和组合不确定性，建立了排课问题的数学模型；其

2、次根据排课问题的特点将课表编排分解为时间安排和教室安排两部分在时间安排中分两个步骤进行，一是对某一门课程的时间安排(单目标)，从中找到几个近似最优的安排方案，二是对所有课程集合的时间安排(多目标)，寻找所有课程安排的一个先后顺序排列。然后在时间安排的基础上对教室进行安排，提出了解决“甩课"问题的“回溯”调整方法。本文讨论的模型是遗传算法在排课问题中一种很有效的应用，随着对此问题越来越多的关注，相信遗传算法一定可以更好的解决排课问题。关键词：排课问题；遗传算法；数学模型；时间安排；教室安排；回溯调整西南交通大学硕士研究生学位论文第1

3、I页●l-_-●_-_-●-______--●_l_●-_●_______●__-_-_I--I-______-，，____-___________-________l_●--_______-__-_____-●____一一AbstractTimetablingProblem(TTP)isaMulti一0DjectiveCombinationOptimizationProblemwithconstraints，andalsohasbeenprovedasaNP—Completedproblem；GeneticAlgorithm(G

4、A)isahigh—effectiveparallelingprocessing，randomlysearchingandself—applicablealgorithmbasedonthedevelopmentofthenatureevolutionandoption．Duetoitsstrength，itisparticularlyapplicabletooperatethetraditionalsearchingalgorithmandtacklethecomplicatednonlinearproblem．Theartic

5、leappliestheGAtotheclasstimetabling．Thedeterminantfactors，1imitedconditions，thesolvingobjectivesanduncertaintyofthecombinationhavebeendiscussedtosetupthemathematicalmodule：secondlythetimetablehasbeendividedintothearrangementoftimeandclassroomaccordingtothecharacterist

6、icsoftheproblemofclassarrangement．Timetablingisbeingprocessedintwosteps，thefirstistoarrangethetimeforsingularcourse(solo-objective)andfindoutseveralmostoptimalsolutions，thesecondistoarrangethetimeforallthecourses(multi—objectives)andfindoutthesequencesofallthecourses．

7、Onthebasisoftimetable，theclassroomswiiibeorganizedandtheadjustmentapproachofdating—backwillbeproposedtosolvetheproblemofchaoticclassarrangement．Themodulediscussedinthearticleisaneffectiveapplicationofsolvingtheproblemofarrangingtheclass．Asthemorefocusesbeingdevotedtot

8、heproblem，theGAisbelievedtoabetterapproach．Key,ords：TheproblemMathematicalModule：Dating’。backAdjustmentofclassarrangement：Ti