探析遗传算法研究及其在排课问题中的应用

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

1、西南交通大学硕士学位论文遗传算法研究及其在排课问题中的应用姓名：陈本庆申请学位级别：硕士专业：交通信息工程及控制指导教师：马永强20030401西南交通大学硕士研究生学位论文第1页摘要随着计算机技术的飞速发展，人们已经可以让计算机完成一些过去无法想象的任务。但现代科学理论研究与实践中存在着大量与组合优化、自适应等相关的问题。使用常规方法解决这些问题，除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题显得无能为力。遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于处理传统搜索方

2、法难以解决的复杂的和非线性的问题。经过近40年的发展，遗传算法在理论研究与实际应用中取得了巨大的成功，但相对其鲜明的生物基础，其数学基础还感相对不完善的。本文从遗传算法的基本理论入手，针对基本遗传算法(SGA)不以概率1收敛于最优解的问题，提出了～些改进方法并对其收敛性进行证明。主要有以下几方面工作：(1)将二进制编码遗传算法的模式定理扩展到由有限整数、字母或取值个数有限的浮点数编码。或它们混合编码的遗传算法范围；(2)提出最佳个体替换策略遗传算法0u!coA)、优势群体优先策略遗传算法侣CFGA)，对遗传

3、算法进行改进；(3)使用随机过程理论Markov链对RECGA进行了收敛性分析；(4)使用泛函分析理论压缩映射原理对scFG_A进行了收敛性分析；(5)使用遗传算法设计了解决NP类问题(排课问题)的测试程序(CAP)，并根据RECGA对算法进行改进并进行测试。cAP测试程序的实验结果表明，使用最佳个体替换策略(REC)改进遗传算法明显地提高了算法效率。同时，对RECGA、SCFGA的收敛性证明在遗传算法研究中具有一定的理论意义。关键词遗传算法；模式定理；排课闯题；收敛性：时阁复杂性西南交通大学硕士研究生学位

4、论文第n页AbstractTodaywitnessestherapiddevelopmentofcomputertechnology．Sometasksthatwereimpossibleinthepastcanbeaccomplishedwithcomputer．However,therearestillmanyissuestobetackledwithinmodernscientifictheoryresearchandpractice．withregardtoCombination&Optimizat

5、ionandself-adaptationetc．Routinemethodsarequitehelpfulresolvingsimpleoptimizationandself-adaptationproblemsbuthelplessforcomplicatedlarge·scalesystems．GeneticAlgorithms．basedonthebiologicalmechanismofnaturalselection＆heredityandleveragingcolonysearchingtec

6、hnology,isparticularlyapplicablefortheresolutionofcomplicated＆non-linearproblemsintractablewithtraditionalsearchingmethods．Fornearly40years’development。GeneticAlgorithmshasmadegreatachievementsinboththeoryresearchandpracticalapplications．However,itsmathema

7、ticalfoundationisstillincompletecomparedwiththedistinctiveandsoundbiologicfoundation．ThispaperstartswiththebasictheoryofGeneticAlgorithms．Then，somemodificationmethodsareadvancedandsomeconvergenceproofsmade，aimingattheproblemthattheprobabilityofSimpleGeneti

8、cAlgorithm(SGA)convergedtooptimalsolutionislessthan1．Themajortasksinclude：(1)ExpandtheschematheoremforGA．TheschematheoremwithbinarycodingadvancedbyProfessorHollandisexpandedtolimitedinteger,letter,floatingpoi