采用染色划分改进的RLS算法及性能分析

• 作者: 卢昕玮 张雁 焦方正 黄永宣
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 局部搜索算法 最大团问题 染色 吸收态马尔可夫链
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 2305-2316
• 分类号: TP18
• 字数: 8674字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03969

摘要

利用最大团问题解空间特殊的结构特征,提出一种基于染色划分构建高维约束指导局部搜索移动方向的改进RLS算法——RLS-Ⅱ算法,该算法提高了局部搜索向最优解靠近的概率.基于吸收态Markov链理论,建立了RLS和RLS-Ⅱ算法求解最大团问题的数学模型,分析了两种算法的吸收时间,并在77个标准测试算例上对分析结果进行了实验验证.理论分析及实验结果都表明,染色划分过滤确实能够有效改善RLS算法的性能,且平均染色组长度越大,性能改进的概率和幅度就越大.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄永宣	西安交通大学系统工程研究所	97	1109	19.0	28.0
2	张雁	西安交通大学系统工程研究所	8	54	4.0	7.0
4	卢昕玮	长安大学经济与管理学院	11	12	2.0	3.0
7	焦方正	西安交通大学系统工程研究所	1	2	1.0	1.0