【作者】 吴小娟；

【导师】 吕强；

【作者基本信息】 苏州大学 ， 计算机应用技术， 2008， 硕士

【摘要】 蚁群优化(ACO)算法在国内外已经取得了很多的研究成果,也有很多应用证实了其在解决组合优化问题中的优越性,本文研究将ACO算法应用于大学课程时间表问题。本文分析了大学课程时间表问题(UCTP)的特征和求解目标,结合已有蚂蚁算法(MMAS)的求解策略,构建了一个新的大学课程时间表问题的求解模型,相比原有的MMAS求解UCTP算法,新的计算模型充分利用启发式搜索的特征,定义了基于软限制条件的新的启发因子,并在不同规模的问题实例上进行实验,结果表明本文的MMAS算法框架可以方便地融合新的技术来提高解的质量。鉴于任何元启发算法在解决特定问题时,都必须充分分析问题实例的特征、结合问题本身的逻辑,本文对新MMAS-UCTP算法进行了改进,对按照一般ACO准则构造出来的解进行可行化,具体采用了三种可行化技术:improve,shu?e,survive,结果表明改进后的算法质量有明显地提高。最后,所有的蚂蚁通过共享同一信息素的方式并行构造解,实现了本课题中MMAS-UCTP算法的并行化。实验表明,并行化的结果在解的质量和运行时间方面都有很好的表现。更多还原

【Abstract】 Ant colony algorithms have been well studied all over the world. There are a lotof successful applications which prove that ACO algorithms are good solutions to mostof the Combinational Optimization Problems. This thesis studies how to apply ACOalgotrithm to the University Timetabling Problem(UCTP).On the basis of analyzing the properties of UCTP and the object of the prob-lem,a new computing model which combines with the max-min ant system(MMAS)algorithm is constructed. Compared with the original MMAS-UCTP, the new modeltakes more advantage of metaheuristic searching strategy and is enhanced with a newheuristic information which relies on the soft constraint violation(scv). The algorithmis implemented and tested on several problems with di?erent scales and the resultsshow that the new MMAS-UCTP can conveniently merge the new techniques, whichmay improves the solution’s quality.It is well known that any metaheuristic algorithms should analyze the propertiesand the logic of the given problem before solving it. Here the thesis try to improve theMMAS-UCTP algorithm, i.e. to make the solutions constructed by the general ACOalgorithm feasible. Specifically speaking, the technique includes three parts named im-prove, shu?e and survive, the experiments show that the results are highly improved.Finally, the thesis parallelize the new MMAS-UCTP algorithm by parallelizingant’s solution construction with sharing a common pheromone matrix. The experi-ments show that the final solution achieves good performance on both solution qualityand running time.更多还原