计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
5期
1271-1274
,共4页
最大割%组合优化%智能算法%局部搜索%禁忌搜索
最大割%組閤優化%智能算法%跼部搜索%禁忌搜索
최대할%조합우화%지능산법%국부수색%금기수색
maximum cut%combinatorial optimization%intelligent algorithm%local search%tabu search
为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索(MSTS)算法.算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略.算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程.重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解.采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算,并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法.实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量.
為瞭增彊跼部搜索算法在求解最大割問題上的尋優能力,提高解質量,提齣瞭一種多啟動禁忌搜索(MSTS)算法.算法主要包括兩箇重要組件:一是用于搜索高質量跼部優化解的禁忌搜索算法;二是具有全跼搜索能力的重啟策略.算法首先通過禁忌搜索組件穫取跼部優化解;然後應用設計的重啟策略重新生成初始解併重啟禁忌搜索過程.重啟策略基于隨機貪心的思想,綜閤利用瞭“構造”和“擾動”這兩種方法生成新的起始解,來逃離跼部最優的陷阱從而找到更高優度的解.採用瞭國際文獻中公認的21箇算例作為本算法的測試實驗集併進行實算,併與多箇先進算法進行比較,MSTS算法在18箇算例上得到最好解值,高于其他對比算法.實驗結果錶明,MSTS算法具有更彊的尋優能力和更高的解質量.
위료증강국부수색산법재구해최대할문제상적심우능력,제고해질량,제출료일충다계동금기수색(MSTS)산법.산법주요포괄량개중요조건:일시용우수색고질량국부우화해적금기수색산법;이시구유전국수색능력적중계책략.산법수선통과금기수색조건획취국부우화해;연후응용설계적중계책략중신생성초시해병중계금기수색과정.중계책략기우수궤탐심적사상,종합이용료“구조”화“우동”저량충방법생성신적기시해,래도리국부최우적함정종이조도경고우도적해.채용료국제문헌중공인적21개산례작위본산법적측시실험집병진행실산,병여다개선진산법진행비교,MSTS산법재18개산례상득도최호해치,고우기타대비산법.실험결과표명,MSTS산법구유경강적심우능력화경고적해질량.
