基于蚁群遗传算法的最小图着色数研究

《基于蚁群遗传算法的最小图着色数研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据声明本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：丕垫叠堕i圣日期：--／_otu-．b．1旨关于学位论文使用权的说明本人完全了解太原理工大学有关保管、使用学位论文的规定，其中包括：①学校有权保管、并向有关部门送交学位论文的原件与复印件；②学校可以采用影印、缩印或其它复制手段复制并保存学位

2、论文；⑧学校可允许学位论文被查阅或借阅；④学校可以学术交流为目的，复制赠送和交换学位论文：⑤学校可以公布学位论文的全部或部分内容(保密学位论文在解密后遵守此规定)。签名：日期：≯}婶．6．f孑导师签名：≥乏q秀日期：秒IV．易．咿万方数据太原理工大学硕士研究生学位论文基于蚁群遗传算法的最小图着色数研究摘要图着色问题由最初的“四色猜想”问题引申而来，研究者们不断将其应用于解决各类实际问题，包括频道分配问题、任务调度问题、停机位分配问题等组合优化问题。虽然图着色问题的应用范围非常之广，但是确定图的着色数却是一个十分困难的事

3、情。关于图着色的算法研究非常之多，大体分为精确算法和近似算法。精确算法借助严格的数学方法来获得最精确最优解，但其复杂度相当高，因此只能把它当作一种理想的求解算法而一般不应用于实际求解。近似算法凭借其快速搜索的性能而获得问题的更优解，在问题研究领域中得到广泛应用。目前关于图着色问题的近似算法求解方法很多，而遗传算法和蚁群算法作为最具代表的两种算法，在图着色问题上得到不断应用和改进。遗传算法由于自身具有的特性(自组织、自适应性、全局收敛性等特点)，因此能够寻求更优解。但是由于其复杂的结构设计(包括编码方式、适应度函数的设定

4、、遗传算子的设定)，微小的设计偏差都会影响算法求解的结果。因此针对图着色这一特殊问题，提出了合适的编码方式和采用特殊的遗传算子一换位算子、切断算子、拼接算子等；借助符号编码方式来很好的描述问题的约束条件；借助换位算子来保证下一代群体始终向着更优解的方向搜索，加快收敛到最优解的速度；借助切断算子和拼接算子为染色体种群的多样性发展提供了万方数据太原理工大学硕士研究生学位论文更多可能。在使用改进的遗传算法求解图着色问题时，虽然比传统的遗传算法的收敛速度更快，但是其初始群体比较单一，为了减少初始种群的个数从而达到求解更优解的目

5、的，提出用一种算法的搜索结果作为改进遗传算法的初始解。由于贪心算法实现简单，寻优度不高；禁忌搜索算法本身也是对初始群体依赖性较大，也不适于解决改进遗传算法所要解决的问题；模拟退火算法虽避免了对初值的依赖性，但是求解结果并不能方便的转换为传统遗传算法的初始解结构。蚁群算法具有局部收敛性，能准确的描述图着色问题的约束条件，并且所求解的结果能很方便的转换为传统遗传算法的初始解结构，因此更适合于进行初始化搜索。本文首先介绍了传统遗传算法的设计及其用于求解图着色问题时存在的缺陷，针对图着色问题的特殊性，根据遗传算法的编码方式和特

6、殊算子，提出了改进的遗传算法模型，即编码方式采用符号编码，而遗传算子的设计则采用基因换位算子、拼接算子、切断算子来取代原来的交叉算子，使求解过程始终朝着更优的方向发展，加快了收敛速度。然后针对改进遗传算法的求解模型存在的初始群体单一性问题，提出了用蚁群搜索算法为其提供初始解的思想。最后总体介绍了融合算法的求解过程，并用Matlab工具对标准着色算例的图和大量随机生成的图进行仿真实验，实验结果证明了本文提出的算法的有效性。万方数据太原理工大学硕士研究生学位论文关键词：图着色，遗传算法，基因移位算子，切断算子，拼接算子万方

7、数据太原理工大学硕士研究生学位论文万方数据太原理工大学硕士研究生学位论文ANTCOLONYSYSTEMGENETICALGORITHMFORGRAPHC0LORINGABSTRACTGraphcoloringisextendedinmeaningtheoriginal“FourColorTheorem”，andgradually,manyresearchersappliedittosolvesomeactualproblems，suchasChannelallocationproblem，Taskschedulingp

8、roblem，SlotsallocationproblemandSOon．Itisdifficulttoconfirmthegraphcoloringnumber，althoughgraphcoloringWaSusedextensively．Lotsofresearchersputforwardmanykindsofalgori