主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张雁,焦方正,卢昕玮,黄永宣.采用染色划分改进的RLS 算法及性能分析.软件学报,2011,22(10):2305-2316
采用染色划分改进的RLS 算法及性能分析
Improved RLS Algorithm with Color-Partition and Performance Analysis
投稿时间:2010-03-13  修订日期:2010-07-28
DOI:10.3724/SP.J.1001.2011.03969
中文关键词:  局部搜索算法  最大团问题  染色  吸收态马尔可夫链
英文关键词:local search algorithm  maximum clique problem  coloring  absorbing Markov chain
基金项目:
作者单位E-mail
张雁 西安交通大学 系统工程研究所,陕西 西安 710049
陕西电力信通公司 运行管理部,陕西 西安 710048 
nowed@stu.xjtu.edu.cn 
焦方正 西安交通大学 系统工程研究所,陕西 西安 710049  
卢昕玮 长安大学 经济与管理学院,陕西 西安 710064  
黄永宣 西安交通大学 系统工程研究所,陕西 西安 710049  
摘要点击次数: 2872
全文下载次数: 2935
中文摘要:
      利用最大团问题解空间特殊的结构特征,提出一种基于染色划分构建高维约束指导局部搜索移动方向的改进RLS 算法——RLS-II 算法,该算法提高了局部搜索向最优解靠近的概率.基于吸收态Markov 链理论,建立了RLS 和RLS-II 算法求解最大团问题的数学模型,分析了两种算法的吸收时间,并在77 个标准测试算例上对分析结果进行了实验验证.理论分析及实验结果都表明,染色划分过滤确实能够有效改善RLS 算法的性能,且平均染色组长度越大,性能改进的概率和幅度就越大.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利