|
|||||
|
|
| 图着色问题的逆序蚁群算法研究 | |
| 作者姓名： | 张丽 丁晓东 |
| 作者单位： | 上海理工大学 管理学院,上海 200093; 上海工程技术大学 航空运输学院,上海 201620 |
| 基金项目： | 上海市一流学科建设项目资助(S1201YLXK);上海理工大学“系统管理与系统分析”交叉学科研究生创新培育项目 |
| 摘 要： | 针对经典的图着色问题,依据传统图着色算法中逆序图着色的着色思想,结合蚁群算法的搜索机制,给出了逆序蚁群着色算法.根据着色进度和未着色点的相邻点度数随机动态逆序选择新的着色点,使得算法具有较强的搜索全局最优解的能力.利用计算机生产大量随机图作为测试实例,对比逆序着色算法和逆序蚁群算法,实验结果说明逆序蚁群着色算法提高了求解质量,加快了收敛速度,证明了其优良特性.同时算法效率的提高,也保证了该算法可适用于较大规模的着色问题求解.此外,还进行了一系列对比试验,得出了关键参数的合理取值范围. |
| 关 键 词： | 图着色问题 逆序着色算法 逆序蚁群着色算法 |
| 收稿时间： | 2013-09-11 |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《上海理工大学学报》浏览原始摘要信息 | |
| 点击此处可从《上海理工大学学报》下载全文 | |