图着色问题的逆序蚁群算法研究.pdf

《图着色问题的逆序蚁群算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海理工大学学报第３６卷第５期犑．犝狀犻狏犲狉狊犻狋狔狅犳犛犺犪狀犵犺犪犻犳狅狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔犞狅犾．３６犖狅．５２０１４文章编号：１００７－６７３５（２０１４）０５－０４８３－０４犇犗犐：１０．１３２５５／犼．犮狀犽犻．犼狌狊狊狋．２０１４．０５．０１４图着色问题的逆序蚁群算法研究张丽１，２，丁晓东１，２（１．上海理工大学管理学院，上海２０００９３；２．上海工程技术大学航空运输学院，上海２０１６２０）摘要：针对经典的图着色问题，依据传统图着色算法中逆序图着色的着色思想，结合蚁群算法的搜索机制，给出了逆序

2、蚁群着色算法．根据着色进度和未着色点的相邻点度数随机动态逆序选择新的着色点，使得算法具有较强的搜索全局最优解的能力．利用计算机生产大量随机图作为测试实例，对比逆序着色算法和逆序蚁群算法，实验结果说明逆序蚁群着色算法提高了求解质量，加快了收敛速度，证明了其优良特性．同时算法效率的提高，也保证了该算法可适用于较大规模的着色问题求解．此外，还进行了一系列对比试验，得出了关键参数的合理取值范围．关键词：图着色问题；逆序着色算法；逆序蚁群着色算法中图分类号：犜犘１８文献标志码：犃犚犲狏犲狉狊犲犗狉犱犲狉犃狀狋犆狅犾狅狀狔犃犾犵狅狉犻狋犺犿犳

3、狅狉犌狉犪狆犺犆狅犾狅狉犻狀犵犘狉狅犫犾犲犿１，２，犇犐犖犌犡犻犪狅犱狅狀犵１，２犣犎犃犖犌犔犻（１．犛犮犺狅狅犾狅犳犕犪狀犪犵犲犿犲狀狋，犝狀犻狏犲狉狊犻狋狔狅犳犛犺犪狀犵犺犪犻犳狅狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犛犺犪狀犵犺犪犻２０００９３，犆犺犻狀犪；２．犃犻狉犜狉犪狀狊狆狅狉狋犇犲狆犪狉狋犿犲狀狋，犛犺犪狀犵犺犪犻犝狀犻狏犲狉狊犻狋狔狅犳犈狀犵犻狀犲犲狉犻狀犵犛犮犻犲狀犮犲，犛犺犪狀犵犺犪犻２０１６２０，犆犺犻狀犪）犃犫狊狋狉犪犮狋：犅犪狊犲犱狅狀狋犺犲狋狉犪犱犻狋犻狅狀犪犾狉犲狏犲狉狊犲狅狉犱犲狉犻狀犵犵狉

4、犪狆犺犮狅犾狅狉犻狀犵犪犾犵狅狉犻狋犺犿犪狀犱犮狅犿犫犻狀犻狀犵狑犻狋犺狊犲犪狉犮犺犻狀犵犿犲犮犺犪狀犻狊犿狅犳犪狀狋犪犾犵狅狉犻狋犺犿，犪狉犲狏犲狉狊犲狅狉犱犲狉犪狀狋犮狅犾狅狔犮狅犾狅狉犻狀犵犪犾犵狅狉犻狋犺犿狑犪狊狆狉狅狆狅狊犲犱狋狅狉犲狊狅犾狏犲犵狉犪狆犺犮狅犾狅狉犻狀犵狆狉狅犫犾犲犿狊．犐狀狋犺犲犪犾犵狅狉犻狋犺犿犪犮犮狅狉犱犻狀犵狋狅狋犺犲犮狅犾狅狉狆狉狅犵狉犲狊狊犪狀犱狋犺犲犪犱犼犪犮犲狀狋狆狅犻狀狋狊犱犲犵狉犲犲，狋犺犲犱狔狀犪犿犻犮狉犲狏犲狉狊犲狋狉犪狀狊犳犲狉狉犻狀犵犮狅犾狅狉狊犲狇狌犲狀犮犲犮犪狀犵犻狏犲狋犺

5、犲犪犾犵狅狉犻狋犺犿狊狋狉狅狀犵犪犫犻犾犻狋狔狋狅狊犲犪狉犮犺狋犺犲犵犾狅犫犪犾狅狆狋犻犿犪犾狊狅犾狌狋犻狅狀．犃犾犪狉犵犲狀狌犿犫犲狉狅犳狉犪狀犱狅犿犵狉犪狆犺犮狅犾狅狉犻狀犵犲狓狆犲狉犻犿犲狀狋狊狊犺狅狑狋犺犲犪犱狏犪狀狋犪犵犲狊狅犳狋犺犲狀犲狑犪犾犵狅狉犻狋犺犿．犜犺犲犪犾犵狅狉犻狋犺犿犮犪狀犻犿狆狉狅狏犲狋犺犲狇狌犪犾犻狋狔狅犳狊狅犾狌狋犻狅狀犪狀犱犿犪犽犲狋犺犲犮狅狀狏犲狉犵犲狀犮犲犳犪狊狋犲狉．犃狀犻犿狆狉狅狏犲犿犲狀狋狅犳狋犺犲犲犳犳犻犮犻犲狀犮狔狅犳狋犺犲犪犾犵狅狉犻狋犺犿犪犾狊狅犲狀狊狌狉犲狊狋犺犪狋犻狋犮犪狀犫

6、犲犪狆狆犾犻犲犱狋狅狊狅犾狏犲犾犪狉犵犲狊犮犪犾犲犮狅犾狅狉犻狀犵狆狉狅犫犾犲犿狊．犐狀犪犱犱犻狋犻狅狀，狋犺狉狅狌犵犺狊犲狉犻犲狊狅犳犮狅犿狆狌狋犲狉狋犲狊狋，狉犲犪狊狅狀犪犫犾犲狏犪犾狌犲狉犪狀犵犲狊狅犳犽犲狔狆犪狉犪犿犲狋犲狉狊狑犲狉犲狏犪犾犻犱犪狋犲犱．犓犲狔狑狅狉犱狊：犵狉犪狆犺犮狅犾狅狉犻狀犵狆狉狅犫犾犲犿；狉犲狏犲狉狊犲狅狉犱犲狉犮狅犾狅狉犻狀犵犪犾犵狅狉犻狋犺犿；狉犲狏犲狉狊犲狅狉犱犲狉犪狀狋犮狅犾狅狀狔犮狅犾狅狉犻狀犵犪犾犵狅狉犻狋犺犿图着色问题（犵狉犪狆犺犮狅犾狅狉犻狀犵狆狉狅犫犾犲犿，犌犆犘）是现代图论中重

7、要课题之一，在存储分配、电路布线、收稿日期：２０１３－０９－１１基金项目：上海市一流学科建设资助项目（犛１２０１犢犔犡犓）；上海市教委科研创新资助项目（１２犢犛１２９）第一作者：张丽（１９８０－），女，博士研究生．研究方向：智能优化．犈犿犪犻犾：狕犺犪狀犵犾犻狊狌犲狊＠１６３．犮狅犿通讯作者：丁晓东（１９６３－），男，教授．研究方向：不确定系统分析与优化．犈犿犪犻犾：狓犱犱犻狀犵＠狌狊狊狋．犲犱狌．犮狅犿４８４上海理工大学学报２０１４年第３６卷机场停机位分配等问题中也有广泛的应用．图着色颜色对尚未着色的点重复前一步，直到所有的

8、点都的内容包括点着色、边着色、组合地图的面着色等，着上颜色为止．边着色和面着色都可转化为点着色问题．逆序着色算法的步骤为：图着色问题是组合优化中一个很活跃的课题，步骤１取顶点狏１，犱犲犵（狏１）＝犿犪狓｛犱犲犵（狏犻）｜国内外研究人员进行过许多研究