软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2011年
10期
2305-2316
,共12页
张雁%焦方正%卢昕玮%黄永宣
張雁%焦方正%盧昕瑋%黃永宣
장안%초방정%로흔위%황영선
局部搜索算法%最大团问题%染色%吸收态马尔可夫链
跼部搜索算法%最大糰問題%染色%吸收態馬爾可伕鏈
국부수색산법%최대단문제%염색%흡수태마이가부련
利用最大团问题解空间特殊的结构特征,提出一种基于染色划分构建高维约束指导局部搜索移动方向的改进RLS算法——RLS-Ⅱ算法,该算法提高了局部搜索向最优解靠近的概率.基于吸收态Markov链理论,建立了RLS和RLS-Ⅱ算法求解最大团问题的数学模型,分析了两种算法的吸收时间,并在77个标准测试算例上对分析结果进行了实验验证.理论分析及实验结果都表明,染色划分过滤确实能够有效改善RLS算法的性能,且平均染色组长度越大,性能改进的概率和幅度就越大.
利用最大糰問題解空間特殊的結構特徵,提齣一種基于染色劃分構建高維約束指導跼部搜索移動方嚮的改進RLS算法——RLS-Ⅱ算法,該算法提高瞭跼部搜索嚮最優解靠近的概率.基于吸收態Markov鏈理論,建立瞭RLS和RLS-Ⅱ算法求解最大糰問題的數學模型,分析瞭兩種算法的吸收時間,併在77箇標準測試算例上對分析結果進行瞭實驗驗證.理論分析及實驗結果都錶明,染色劃分過濾確實能夠有效改善RLS算法的性能,且平均染色組長度越大,性能改進的概率和幅度就越大.
이용최대단문제해공간특수적결구특정,제출일충기우염색화분구건고유약속지도국부수색이동방향적개진RLS산법——RLS-Ⅱ산법,해산법제고료국부수색향최우해고근적개솔.기우흡수태Markov련이론,건립료RLS화RLS-Ⅱ산법구해최대단문제적수학모형,분석료량충산법적흡수시간,병재77개표준측시산례상대분석결과진행료실험험증.이론분석급실험결과도표명,염색화분과려학실능구유효개선RLS산법적성능,차평균염색조장도월대,성능개진적개솔화폭도취월대.
