节点文献

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

Improved RLS Algorithm with Color-Partition and Performance Analysis

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具,请取消加速工具后下载。

【作者】 张雁焦方正卢昕玮黄永宣

【Author】 ZHANG Yan 1,2,JIAO Fang-Zheng 1,LU Xin-Wei 3,HUANG Yong-Xuan 1 1(Systems Engineering Institute,Xi’an Jiaotong University,Xi’an 710049,China) 2(Department of Operation and Management,Shaanxi Power Information and Communication Corporation,Xi’an 710048,China) 3(School of Economics and Management,Chang’an University,Xi’an 710064,China)

【机构】 西安交通大学系统工程研究所陕西电力信通公司运行管理部长安大学经济与管理学院

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

【Abstract】 By exploiting the special structure in the solution space of the maximum clique problem(MCP) ,an improved RLS method,the RLS-II method,is has been created where the neighborhood-moving direction of the local search is guided by the multivariate constraints constructed by the dying partitioning. Therefore,the probability of the local search approaching the optimal solution is increased. Using the absorbing Markov chain theory as a reference,the mathematical models of the RLS and RLS-II algorithms in solving maximum clique problem are constructed and the absorbing time of the two algorithms is analyzed. Moreover,the analytical results are experimentally demonstrated on 77 Benchmark instances. Both the theoretical analysis and simulation results show that the dying partitioning filter can effectively improve the performance of the RLS algorithm. Furthermore,the longer average length of the dying group,the higher probability and amplitude of the performance improvement.

  • 【文献出处】 软件学报 ,Journal of Software , 编辑部邮箱 ,2011年10期
  • 【分类号】TP18
  • 【被引频次】2
  • 【下载频次】133
节点文献中: 

本文链接的文献网络图示:

本文的引文网络