基于蚁群算法的约束求解

《基于蚁群算法的约束求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP301.6单位代码：10190研究生学号：201307026密级：无硕士学位论文基于蚁群算法的约束求解BasedonAntColonyAlgorithmofConstraintSolving研究生姓名：曹严清专业：计算机技术指导教师姓名：王涛指导教师职称：副教授2016年4月硕士学位论文长春工业大学硕士学位论文原创性声明本人郑重声明：所呈交的硕士学位论文，《基于蚁群算法的约束求解》是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集

2、体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者签名：年月日长春工业大学硕士学位论文版权使用授权书本学位论文作者及指导教师完全了解“长春工业大学硕士学位论文版权使用规定”，同意长春工业大学保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权长春工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。作者签名：年月日校内指导教师签名：年月日硕士学位论文摘要约束满足问题是人工智能中一个非常重要的分支，现实中很多问题都可以被抽象成用约束算法来解决的问

3、题，向生产调度和资源配置就常用约束算法来求解，在实际问题中问题的规模可能会非常大，也肯能是NP难问题，如果用传统的方法可能很难在在合理的时间内得到满意的解，而约束求解算法在解决这类问题时有着很高的效率，约束算法中常用的是回溯算法如MAC算法，在回溯算法中也会嵌入弧相容的算法，弧相容是用来删除一些不相容的值，来压缩解空间，从而提高求解效率。通过仿生学的研究，人们发现个体行为简单的蚂蚁可以在没有群体指挥的情况下完成复杂的任务，通过进一步的研究发现蚂蚁通过释放信息素来完成合作交流的。在这个过程的启发下意大利学者M.Dorigo,V.Maniezzo等人提出了蚁群算法，由于

4、蚁群的觅食过程和TSP问题很相似，所以蚁群算法通常用来解决TSP问题。同样蚁群算法也被用于生产调度，组合优化，数据挖掘等领域。约束求解技术虽然在求解约束满足问题时有着很好的效率，但在实际问题中，如果问题规模很大，对时间的要求很高，使用回溯算法和相容性技术需要更多的时间，但如果使用蚁群算法来求解约束满足问题，因为不需要回溯也没有因使用相容性技术简化网络时所带来的巨大的时间开销，所以求解效率会更高。本文以约束求解算法和基本的蚁群算法为基础，使用蚁群算法来求解约束满足问题。(1)本文分析讨论了算法框架MAC,和嵌入在MAC算法中的一些弧相容算法，如AC3，AC4，AC6，

5、AC2001算法，分析解释了MAC算法如何回溯和如何选择分支策略，AC3，AC4，AC6，AC2001算法检查方式和检查次数有关的各自具有的数据结构。介绍了蚁群算法的原理和基本蚁群算法求解TSP问题。(2)将适用于约束求解的benchmark数据建立成相应的TSP问题的模型，把每个变量的变量值映射成TSP问题中的一个城市，蚂蚁在爬行的时候并不会走完每个城市，只会走每个变量的一个值(3)蚂蚁在对下一个节点进行选择时所遵循的概率公式会有所不同，本文提出了两个公式，公式一蚂蚁只遵循信息素浓度，公式二中会有信息素浓度因素，但同样会有想基本蚁群算法概率公式中的距离这种局部因素

6、，这里的局部因素是待选择节点与蚂蚁已走过节点之间所增加的冲突数。(4)通过与MAC-AC3算法进行对比，说明了算法的有效性。关键词：约束满足问题弧相容蚁群算法TSP问题I硕士学位论文AbstractConstraintsatisfactionproblemisaveryimportantbranchofartificialintelligence,whichinrealityalotofproblemscanbeabstractedasconstraintalgorithmtosolvetheproblem,commonlyusedconstraintstoprod

7、uctionschedulingandresourceallocationalgorithmtosolvethepracticalproblemsinthescaleoftheproblemmaybeverybig,alsocanisanp-hardproblem,ifusethetraditionalmethodscanbedifficulttoobtainsatisfactorysolutioninareasonableamountoftime,andconstraintsolvingalgorithmwithhighefficiencyindealingw