计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2009年
3期
42-44,54
,共4页
SAT问题%蚁群算法%最大最小蚂蚁系统%启发式信息值
SAT問題%蟻群算法%最大最小螞蟻繫統%啟髮式信息值
SAT문제%의군산법%최대최소마의계통%계발식신식치
可满足问题(SAT)是一个NP-hard问题,将SAT问题转换为无约束的离散优化(最小值)问题.并根据M Dorigo提出的蚁群算法,给出了一种求解SAT问题的新方法:改进的最大最小蚁群系统(MMAS-SAT).在改进的算法中,给出了sAT问题的构造图,指出了启发式信息值的求法,对衰变系数进行了动态调整.测试问题的数值实验表明,采用MMAS-SAT的结果优于Gwsat、Walksat、Novelty等局部搜索算法,因此该算法是求解SAT问题的一种可行高效的算法.
可滿足問題(SAT)是一箇NP-hard問題,將SAT問題轉換為無約束的離散優化(最小值)問題.併根據M Dorigo提齣的蟻群算法,給齣瞭一種求解SAT問題的新方法:改進的最大最小蟻群繫統(MMAS-SAT).在改進的算法中,給齣瞭sAT問題的構造圖,指齣瞭啟髮式信息值的求法,對衰變繫數進行瞭動態調整.測試問題的數值實驗錶明,採用MMAS-SAT的結果優于Gwsat、Walksat、Novelty等跼部搜索算法,因此該算法是求解SAT問題的一種可行高效的算法.
가만족문제(SAT)시일개NP-hard문제,장SAT문제전환위무약속적리산우화(최소치)문제.병근거M Dorigo제출적의군산법,급출료일충구해SAT문제적신방법:개진적최대최소의군계통(MMAS-SAT).재개진적산법중,급출료sAT문제적구조도,지출료계발식신식치적구법,대쇠변계수진행료동태조정.측시문제적수치실험표명,채용MMAS-SAT적결과우우Gwsat、Walksat、Novelty등국부수색산법,인차해산법시구해SAT문제적일충가행고효적산법.
