基于禁忌搜索算法的图着色研究与实现
|
摘要
禁忌搜索(Tabu Search, TS)是一种较新的智能优化算法,与遗传算法(GA)、粒子群优化算法(PSO)、蚁群算法(ACS)等一样,都包括在自然计算(Natural Computation)的范围内。该算法利用其较为通用的算法框架、灵活的存储结构及相应的禁忌准则可以尽可能避免算法陷入循环搜索,在解决组合优化问题及函数优化领域内引起了不少学者的重视。随着计算机科学的不断发展,图与人类的生活越来越密切,在现实社会中的很多问题都可以归结为点与线组成的图形问题,不少学者引入图论来解决工程应用领域中的很多问题。近年来在工程领域中对图的研究和应用也越来越受到人们的重视,因此,禁忌搜索算法解决图着色问题的研究是十分有意义的。
本文在理解基本禁忌算法理论框架的基础上,重点研究了禁忌搜索算法在图着色问题中的应用。本文将禁忌搜索算法与图顶点着色问题结合,建立算法框架与图顶点着色问题的解空间的映射,应用传统禁忌搜索算法解决了图的顶点着色问题,分析仿真实验结果,评估算法的时间复杂性。另外,本文还分析了传统禁忌搜索算法不足,对传统的禁忌搜索算法进行改进,利用改进后的混合禁忌搜索算法来解决图顶点着色问题,再进行仿真实验,实验效果显著。论文主要工作及创新点可以归纳为如下几点：
(1)阐述并分析了禁忌搜索算法的操作参数,结合禁忌搜索算法的理论框架与图顶点着色问题的约束条件,首先用传统禁忌搜索算法来解决典型的图顶点着色问题,建立了一种利用禁忌搜索算法来解决图顶点着色问题的算法模型。
(2)进一步地研究禁忌搜索算法,分析传统禁忌搜索算法在理论上和实际应用上体现出来的不足,比如初始解对待解决问题的依赖性强,搜索迭代的串行性等,本文针对其不足,结合SEQ算法,提出了一种改进禁忌搜索算法解决图顶点着色问题的较优方案,实验仿真结果证明,改进算法效果更好。
(3)基于上述对传统禁忌搜索算法与改进禁忌搜索算法的应用研究,本文对其作了分析与总结,针对传统禁忌搜索算法在应用中体现出来的缺点,提出算法的改进方案,并在理论上对其应用前景进行了展望。
Tabu Search (Tabu Search or Taboo Search, TS) is a relatively new intelligent optimization algorithm. It is the same as genetic algorithm (GA), particle swarm optimization (PSO), ant colony algorithm (ACS), and so on, included in natural computation (Natural Computation). Tabu search algorithm, its more general algorithm framework, flexible storage structure and the corresponding tabu criteria could avoid its searching process into a cycle. Because of this point, tabu search algorithm causes widespread attention by many scholars. As the continuous development of computer science, graph and human lives are closely linked. In reality, many problems can be attributed to the composition of points and lines like graph problems. So, many scholars introduced graph into engineering application area and to simplify some problems using graph model. Therefore, in recent years, more and more people pay attention to the graph applications and have been attracted to study it in engineering application area. It is very meaningful to solve graph coloring problem using tabu search algorithm.
Based on comprehension of the theoretical framework of tabu search algorithm, in this paper, it is the key to research the application of tabu search algorithm to solve the graph coloring problem. In this paper, it connects with tabu search algorithm and graph coloring problem, established a map for the algorithm framework and the solution space of the problem, using traditional tabu search algorithm to solve the problem, and do simulation experiments, and then analysis the result of simulation experiment, and at last evaluate the time complexity. In addition, in this paper, it improves the traditional tabu search algorithm and using the mixed tabu search algorithm for simulating experiment to solve the graph vertex coloring problem. The experimental result proved that it is considerable. In this paper, the main work and creative points could be summarized as follows:
(1) Deeply understand the basic theory of tabu search algorithm in this paper, and explain and analysis the operating parameters of tabu search algorithm, in this paper, it Combines the theoretical framework of tabu search algorithm with the constraints of the graph vertex coloring problem, using tabu search algorithm to solve the classical graph vertex coloring problem. According to the constraints of solving the graph vertex coloring problem, at first, it establishes a model to work out the graph vertex coloring problem, taking advantage of tabu search algorithm.
(2) Further study of traditional tabu search algorithm and analysis of its disadvantage in practical application theoretically, it proposed an improved tabu search algorithm to solve graph vertex coloring problem. Traditional tabu search algorithm is not very perfect, and has some disadvantages, such as its initial solution strongly dependent to the problem, and the serial search characteristic of itself. Point to these shortages of traditional tabu search algorithm, in this paper, it connects the SEQ algorithm, and puts forward a much better way to solve graph vertex coloring problem. The experimental result proved that this new way could get better effects.
(3) Based on the applications of traditional and the improved tabu search algorithm, in this paper, it gives the analysis and summary. And according to the disadvantages reflected in these applications, in this paper, it raises some improved methods, and discusses the prospect of its application in theory.
本文在理解基本禁忌算法理论框架的基础上,重点研究了禁忌搜索算法在图着色问题中的应用。本文将禁忌搜索算法与图顶点着色问题结合,建立算法框架与图顶点着色问题的解空间的映射,应用传统禁忌搜索算法解决了图的顶点着色问题,分析仿真实验结果,评估算法的时间复杂性。另外,本文还分析了传统禁忌搜索算法不足,对传统的禁忌搜索算法进行改进,利用改进后的混合禁忌搜索算法来解决图顶点着色问题,再进行仿真实验,实验效果显著。论文主要工作及创新点可以归纳为如下几点：
(1)阐述并分析了禁忌搜索算法的操作参数,结合禁忌搜索算法的理论框架与图顶点着色问题的约束条件,首先用传统禁忌搜索算法来解决典型的图顶点着色问题,建立了一种利用禁忌搜索算法来解决图顶点着色问题的算法模型。
(2)进一步地研究禁忌搜索算法,分析传统禁忌搜索算法在理论上和实际应用上体现出来的不足,比如初始解对待解决问题的依赖性强,搜索迭代的串行性等,本文针对其不足,结合SEQ算法,提出了一种改进禁忌搜索算法解决图顶点着色问题的较优方案,实验仿真结果证明,改进算法效果更好。
(3)基于上述对传统禁忌搜索算法与改进禁忌搜索算法的应用研究,本文对其作了分析与总结,针对传统禁忌搜索算法在应用中体现出来的缺点,提出算法的改进方案,并在理论上对其应用前景进行了展望。
Tabu Search (Tabu Search or Taboo Search, TS) is a relatively new intelligent optimization algorithm. It is the same as genetic algorithm (GA), particle swarm optimization (PSO), ant colony algorithm (ACS), and so on, included in natural computation (Natural Computation). Tabu search algorithm, its more general algorithm framework, flexible storage structure and the corresponding tabu criteria could avoid its searching process into a cycle. Because of this point, tabu search algorithm causes widespread attention by many scholars. As the continuous development of computer science, graph and human lives are closely linked. In reality, many problems can be attributed to the composition of points and lines like graph problems. So, many scholars introduced graph into engineering application area and to simplify some problems using graph model. Therefore, in recent years, more and more people pay attention to the graph applications and have been attracted to study it in engineering application area. It is very meaningful to solve graph coloring problem using tabu search algorithm.
Based on comprehension of the theoretical framework of tabu search algorithm, in this paper, it is the key to research the application of tabu search algorithm to solve the graph coloring problem. In this paper, it connects with tabu search algorithm and graph coloring problem, established a map for the algorithm framework and the solution space of the problem, using traditional tabu search algorithm to solve the problem, and do simulation experiments, and then analysis the result of simulation experiment, and at last evaluate the time complexity. In addition, in this paper, it improves the traditional tabu search algorithm and using the mixed tabu search algorithm for simulating experiment to solve the graph vertex coloring problem. The experimental result proved that it is considerable. In this paper, the main work and creative points could be summarized as follows:
(1) Deeply understand the basic theory of tabu search algorithm in this paper, and explain and analysis the operating parameters of tabu search algorithm, in this paper, it Combines the theoretical framework of tabu search algorithm with the constraints of the graph vertex coloring problem, using tabu search algorithm to solve the classical graph vertex coloring problem. According to the constraints of solving the graph vertex coloring problem, at first, it establishes a model to work out the graph vertex coloring problem, taking advantage of tabu search algorithm.
(2) Further study of traditional tabu search algorithm and analysis of its disadvantage in practical application theoretically, it proposed an improved tabu search algorithm to solve graph vertex coloring problem. Traditional tabu search algorithm is not very perfect, and has some disadvantages, such as its initial solution strongly dependent to the problem, and the serial search characteristic of itself. Point to these shortages of traditional tabu search algorithm, in this paper, it connects the SEQ algorithm, and puts forward a much better way to solve graph vertex coloring problem. The experimental result proved that this new way could get better effects.
(3) Based on the applications of traditional and the improved tabu search algorithm, in this paper, it gives the analysis and summary. And according to the disadvantages reflected in these applications, in this paper, it raises some improved methods, and discusses the prospect of its application in theory.
引文
[1]王凌.智能优化算法及其应用[M].北京；清华大学出版社.2003,62-78.
[2]刑文训,谢金星.现代优化计算方法[M].北京；清华大学出版社.1999,53-88.
[3]汪定伟,王俊伟,王洪峰等.智能优化方法[M].北京；高等教育出版社.2007,81-113.
[4]Aljaber N, Baek W, Chen C L. A tabu search approach to the cell formation problem [J]. Computers & industrial engineering,1997,32(1):169-185.
[5]Riaz T, Wang Y, Li K B. Multiple sequence alignment using tabu search, F,2004 [C]. Australian Computer Society, Inc.
[6]彭超.禁忌搜索求解排课问题的应用研究[D].西安；西安电子科技大学,2007,15-26.
[7]朱向阳.基于改进禁忌搜索算法的配电网电压无功优化控制[J].继电器,2006,34(14)：35-37.
[8]张忠会,李曼丽,熊宁等.基于改进禁忌搜索的配电网重构[J].继电器,2007,35(10)：41-44.
[9]张昊,陶然,李志勇等.基于KNN算法及禁忌搜索算法的特征选择方法在入侵检测中的应用研究[J].电子学报,2009,37(7)：1628-1632.
[10]叶碧虾.基于遗传和禁忌搜索算法的排课系统研究与实现[D].厦门；厦门大学,2009,16-22.
[11]Yang S N J S. A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling [J]. Springer Science+Business Media,2010.
[12]左春荣,王海燕.基于禁忌搜索算法测地卫星任务调度研究[J].计算机工程与应用,2010,46(1)：215-217.
[13]文军,李冰,王清蓉等.机场停机位分配问题的图着色模型及其算法[J].系统工程理论方法应用,2005,14(2)：136-140.
[14]王训斌,陆慧娟,张火明.物流动态车辆调度问题的混合禁忌搜索算法[J].计算机工程与应用,2010,46(8)：228-231.
[15]王东平,李绍荣.模糊禁忌搜索算法用于求解分配问题[J].计算机科学,2003,30(7)：167-169.
[16]宋晓宇,孟秋宏,曹阳.求解Job Shop调度问题的改进禁忌搜索算法[J].系统工程与电子技术,2008,30(1)：93-96.
[17]戚海英,邱占芝.用禁忌搜索技术解决无等待流水调度问题[J].大连交通大学学报,2008,29(1)：73-75.
[18]马华伟,杨善林.可选时间窗车辆调度问题的改进禁忌搜索算法[J].系统仿真学报,2008,20(16)：4454-4457.
[19]林灼强.带交通流的联盟运输调度问题禁忌搜索算法研究[D].广东；广东工业大学,2007.
[20]李霄峰,史金飞,阎威武.混合流水车间调度的变邻域禁忌搜索算法[J].计算机工程,2008,34(21)：10-12.
[21]陈锋,刘宗田,石振国等.基于禁忌搜索算法的网格任务调度[J].计算机工程,2007,33(21)：75-77.
[22]Zcan U, Toklu B. A tabu search algorithm for two-sided assembly line balancing [J]. The International Journal of Advanced Manufacturing Technology,2009,43(7): 822-829.
[23]Nowicki E, Smutnicki C. A fast taboo search algorithm for the job shop problem [J]. Management Science,1996,797-813.
[24]Pezzella F, Merelli E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem [J]. European Journal of Operational Research,2000,120(2): 297-310.
[25]张铁柱,郝慧馨.禁忌搜索算法在系统可靠性最优级分配中的应用[J].哈尔滨理工大学学报,2002,7(5)：115-117.
[26]邹德莉,郝应光,陈晓卉.基于禁忌搜索的负载均衡组播路由算法[J].系统仿真学报,2006,18(2)：844-850.
[27]吴圣宁,李思昆.遗传算法和关键事件禁忌搜索相融合的ARM/Thumb处理器指令选择[J].计算机学报,2007,30(4)：680-685.
[28]刘兴,贺国光.车辆路径问题的禁忌搜索算法研究[J].计算机工程与应用,2007,43(24)：179-181.
[29]常政威,谢晓娜,熊光泽.求解二次分配问题的改进禁忌搜索算法[J].微电子学与计算机,2008,25(2)：21-24.
[30]贺一,邱玉辉,刘光远等.多维背包问题的禁忌搜索求解[J].计算机科学,2006,33(9)：169-172.
[31]康雁,黄文奇.基于禁忌搜索的启发式算法求解圆形packing问题[J].计算机研究与发展,2004,41(9)：1554-1558.
[32]王伟,余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用研究, 2007,27(11)：2873-2876.
[33]Burke E K, Kendall G, Soubeiga E. A tabu-search hyperheuristic for timetabling and rostering [J]. Journal of Heuristics,2003,9(6):451-470.
[34]董宏光,秦立民,王涛等.基于自适应并行禁忌搜索的精馏分离序列优化综合[J].化工学报,2004,55(10)：1669-1673.
[35]张先迪,李正良.图论及其应用[M].北京；高等教育出版社.2005,147-185.
[36]He K, Huang W Q. A quasi-human algorithm for solving the three-dimensional rectangular packing problem [J]. SCIENCE CHINA Information Sciences,2010, 53(12):2389-2398.
[37]周子康,杨衡,唐万生.基于分层抽样的模拟禁忌混合智能优化算法TSⅡ[J].计算机工程,2006,32(9)：175-177.
[38]王林川,李漫,张木子等.基于蚁群禁忌搜索混合算法的配电网重构[J].吉林电力,2010,38(5)：34-36.
[39]任晓莉,程红丽,刘健.基于禁忌搜索算法的变电站电压无功优化控制[J].继电器,2008,36(8)：31-34.
[40]徐明亮,苏晓萍,须文波.基于禁忌搜索的option自动构造[J].系统仿真学报,2009,21(23)：7479-7482.
[41]林俊龙,何晨.基于集合覆盖和禁忌搜索算法的WCDMA基站布局[J].上海交通大学学报,2007,41(6)：924-928.
[42]熊宁,陈恳.改进禁忌算法在无功优化中的应用[J].江西电力,2006,30(6)：24-30.
[43]贺一.禁忌搜索及其并行化研究[D].中国·重庆；西南大学,2006,1-16.
[44]贺一,刘光远,雷开友等.多层前向神经网络的自适应禁忌搜索训练[J].计算机科学,2005,32(6)：118-120.
[45]肖丽,刘光远,贺一等.基于禁忌搜索的模糊神经网络结构优化[J].计算机科学,2006,33(7)：217-219.
[46]王淑玲,李振涛,邢棉.一种优化神经网络结构的遗传禁忌算法[J].计算机应用,2007,27(6)：1426-1429.
[47]王民生.禁忌搜索算法及其混合策略的应用研究[D]；大连交通大学,2005,17-36
[48]Glover F, Hanafi S. Tabu search and finite convergence* 1 [J]. Discrete Applied Mathematics,2002,119(1-2):3-36.
[49]强小利.图顶点着色DNA计算模型及实验研究[D].武汉；华中科技大学, 2008,1-12.
[50]韩云,郭庆胜,章莉萍等.行政区划图自动着色的混合遗传算法[J].武汉大学学报·信息科学版,2007,32(8)：748-751.
[51]别文群,李拥军.配送中心多车辆集散货物路线的禁忌搜索研究[J].计算机工程与应用,2010,46(4)：216-218.
[52]韩丽霞,王宇平,兰绍江.基于有序划分编码的图着色算法[J].电子学报,2010,38(1)：146-150.
[53]E.K.BURKE G K A E S. A Tabu-Search Hyperheuristic for Timetabling and Rostering [J]. Journal of Heuristics,2003,9(6):451-470.
[54]刘铝,常炳国.回溯算法在制丝生产线自动排产中的应用[J].计算机系统应用,2011,20(2)：186-188.
[55]张丽,马良,石丽娜.图着色问题的蚂蚁算法研究[J].上海工程技术大学学报,2009,23(4)：328-332.
[56]王秀宏,赵胜敏.利用蚂蚁算法求解图的着色问题[J].内蒙古农业大学学报,2005,26(3)：79-82.
[57]金迅婴,刘光武,潘林强.图着色问题的表面DNA算法[J].交通与计算机,2003,21(110)：6-8.
[58]孙川,朱翔鸥,刘文斌等.图的顶点着色问题的一种DNA算法[J].计算机工程与应用,2006,58-67.
[59]韩丽霞,王宇平,兰绍江.图着色问题的新遗传算法[J].西安电子科技大学学报(自然科学版),2008,35(2)：309-313.
[60]陈卫东.求图着色问题的新算法[J].微计算机应用,2004,25(4)：391-395.
[61]徐雪慧.射频识别技术中防冲突算法研究[D].上海；华中师范大学,2006,45-56.
[62]汤浪平.基于混合智能算法的组卷研究[D].长沙；中南大学,2009,16-29.
[2]刑文训,谢金星.现代优化计算方法[M].北京；清华大学出版社.1999,53-88.
[3]汪定伟,王俊伟,王洪峰等.智能优化方法[M].北京；高等教育出版社.2007,81-113.
[4]Aljaber N, Baek W, Chen C L. A tabu search approach to the cell formation problem [J]. Computers & industrial engineering,1997,32(1):169-185.
[5]Riaz T, Wang Y, Li K B. Multiple sequence alignment using tabu search, F,2004 [C]. Australian Computer Society, Inc.
[6]彭超.禁忌搜索求解排课问题的应用研究[D].西安；西安电子科技大学,2007,15-26.
[7]朱向阳.基于改进禁忌搜索算法的配电网电压无功优化控制[J].继电器,2006,34(14)：35-37.
[8]张忠会,李曼丽,熊宁等.基于改进禁忌搜索的配电网重构[J].继电器,2007,35(10)：41-44.
[9]张昊,陶然,李志勇等.基于KNN算法及禁忌搜索算法的特征选择方法在入侵检测中的应用研究[J].电子学报,2009,37(7)：1628-1632.
[10]叶碧虾.基于遗传和禁忌搜索算法的排课系统研究与实现[D].厦门；厦门大学,2009,16-22.
[11]Yang S N J S. A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling [J]. Springer Science+Business Media,2010.
[12]左春荣,王海燕.基于禁忌搜索算法测地卫星任务调度研究[J].计算机工程与应用,2010,46(1)：215-217.
[13]文军,李冰,王清蓉等.机场停机位分配问题的图着色模型及其算法[J].系统工程理论方法应用,2005,14(2)：136-140.
[14]王训斌,陆慧娟,张火明.物流动态车辆调度问题的混合禁忌搜索算法[J].计算机工程与应用,2010,46(8)：228-231.
[15]王东平,李绍荣.模糊禁忌搜索算法用于求解分配问题[J].计算机科学,2003,30(7)：167-169.
[16]宋晓宇,孟秋宏,曹阳.求解Job Shop调度问题的改进禁忌搜索算法[J].系统工程与电子技术,2008,30(1)：93-96.
[17]戚海英,邱占芝.用禁忌搜索技术解决无等待流水调度问题[J].大连交通大学学报,2008,29(1)：73-75.
[18]马华伟,杨善林.可选时间窗车辆调度问题的改进禁忌搜索算法[J].系统仿真学报,2008,20(16)：4454-4457.
[19]林灼强.带交通流的联盟运输调度问题禁忌搜索算法研究[D].广东；广东工业大学,2007.
[20]李霄峰,史金飞,阎威武.混合流水车间调度的变邻域禁忌搜索算法[J].计算机工程,2008,34(21)：10-12.
[21]陈锋,刘宗田,石振国等.基于禁忌搜索算法的网格任务调度[J].计算机工程,2007,33(21)：75-77.
[22]Zcan U, Toklu B. A tabu search algorithm for two-sided assembly line balancing [J]. The International Journal of Advanced Manufacturing Technology,2009,43(7): 822-829.
[23]Nowicki E, Smutnicki C. A fast taboo search algorithm for the job shop problem [J]. Management Science,1996,797-813.
[24]Pezzella F, Merelli E. A tabu search method guided by shifting bottleneck for the job shop scheduling problem [J]. European Journal of Operational Research,2000,120(2): 297-310.
[25]张铁柱,郝慧馨.禁忌搜索算法在系统可靠性最优级分配中的应用[J].哈尔滨理工大学学报,2002,7(5)：115-117.
[26]邹德莉,郝应光,陈晓卉.基于禁忌搜索的负载均衡组播路由算法[J].系统仿真学报,2006,18(2)：844-850.
[27]吴圣宁,李思昆.遗传算法和关键事件禁忌搜索相融合的ARM/Thumb处理器指令选择[J].计算机学报,2007,30(4)：680-685.
[28]刘兴,贺国光.车辆路径问题的禁忌搜索算法研究[J].计算机工程与应用,2007,43(24)：179-181.
[29]常政威,谢晓娜,熊光泽.求解二次分配问题的改进禁忌搜索算法[J].微电子学与计算机,2008,25(2)：21-24.
[30]贺一,邱玉辉,刘光远等.多维背包问题的禁忌搜索求解[J].计算机科学,2006,33(9)：169-172.
[31]康雁,黄文奇.基于禁忌搜索的启发式算法求解圆形packing问题[J].计算机研究与发展,2004,41(9)：1554-1558.
[32]王伟,余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用研究, 2007,27(11)：2873-2876.
[33]Burke E K, Kendall G, Soubeiga E. A tabu-search hyperheuristic for timetabling and rostering [J]. Journal of Heuristics,2003,9(6):451-470.
[34]董宏光,秦立民,王涛等.基于自适应并行禁忌搜索的精馏分离序列优化综合[J].化工学报,2004,55(10)：1669-1673.
[35]张先迪,李正良.图论及其应用[M].北京；高等教育出版社.2005,147-185.
[36]He K, Huang W Q. A quasi-human algorithm for solving the three-dimensional rectangular packing problem [J]. SCIENCE CHINA Information Sciences,2010, 53(12):2389-2398.
[37]周子康,杨衡,唐万生.基于分层抽样的模拟禁忌混合智能优化算法TSⅡ[J].计算机工程,2006,32(9)：175-177.
[38]王林川,李漫,张木子等.基于蚁群禁忌搜索混合算法的配电网重构[J].吉林电力,2010,38(5)：34-36.
[39]任晓莉,程红丽,刘健.基于禁忌搜索算法的变电站电压无功优化控制[J].继电器,2008,36(8)：31-34.
[40]徐明亮,苏晓萍,须文波.基于禁忌搜索的option自动构造[J].系统仿真学报,2009,21(23)：7479-7482.
[41]林俊龙,何晨.基于集合覆盖和禁忌搜索算法的WCDMA基站布局[J].上海交通大学学报,2007,41(6)：924-928.
[42]熊宁,陈恳.改进禁忌算法在无功优化中的应用[J].江西电力,2006,30(6)：24-30.
[43]贺一.禁忌搜索及其并行化研究[D].中国·重庆；西南大学,2006,1-16.
[44]贺一,刘光远,雷开友等.多层前向神经网络的自适应禁忌搜索训练[J].计算机科学,2005,32(6)：118-120.
[45]肖丽,刘光远,贺一等.基于禁忌搜索的模糊神经网络结构优化[J].计算机科学,2006,33(7)：217-219.
[46]王淑玲,李振涛,邢棉.一种优化神经网络结构的遗传禁忌算法[J].计算机应用,2007,27(6)：1426-1429.
[47]王民生.禁忌搜索算法及其混合策略的应用研究[D]；大连交通大学,2005,17-36
[48]Glover F, Hanafi S. Tabu search and finite convergence* 1 [J]. Discrete Applied Mathematics,2002,119(1-2):3-36.
[49]强小利.图顶点着色DNA计算模型及实验研究[D].武汉；华中科技大学, 2008,1-12.
[50]韩云,郭庆胜,章莉萍等.行政区划图自动着色的混合遗传算法[J].武汉大学学报·信息科学版,2007,32(8)：748-751.
[51]别文群,李拥军.配送中心多车辆集散货物路线的禁忌搜索研究[J].计算机工程与应用,2010,46(4)：216-218.
[52]韩丽霞,王宇平,兰绍江.基于有序划分编码的图着色算法[J].电子学报,2010,38(1)：146-150.
[53]E.K.BURKE G K A E S. A Tabu-Search Hyperheuristic for Timetabling and Rostering [J]. Journal of Heuristics,2003,9(6):451-470.
[54]刘铝,常炳国.回溯算法在制丝生产线自动排产中的应用[J].计算机系统应用,2011,20(2)：186-188.
[55]张丽,马良,石丽娜.图着色问题的蚂蚁算法研究[J].上海工程技术大学学报,2009,23(4)：328-332.
[56]王秀宏,赵胜敏.利用蚂蚁算法求解图的着色问题[J].内蒙古农业大学学报,2005,26(3)：79-82.
[57]金迅婴,刘光武,潘林强.图着色问题的表面DNA算法[J].交通与计算机,2003,21(110)：6-8.
[58]孙川,朱翔鸥,刘文斌等.图的顶点着色问题的一种DNA算法[J].计算机工程与应用,2006,58-67.
[59]韩丽霞,王宇平,兰绍江.图着色问题的新遗传算法[J].西安电子科技大学学报(自然科学版),2008,35(2)：309-313.
[60]陈卫东.求图着色问题的新算法[J].微计算机应用,2004,25(4)：391-395.
[61]徐雪慧.射频识别技术中防冲突算法研究[D].上海；华中师范大学,2006,45-56.
[62]汤浪平.基于混合智能算法的组卷研究[D].长沙；中南大学,2009,16-29.