置信傳播和模擬退火相結(jié)合求解約束滿足問題
摘要:約束滿足問題是人工智能領(lǐng)域的一個(gè)重要問題。針對一個(gè)具有精確相變現(xiàn)象和能產(chǎn)生大量難解實(shí)例的隨機(jī)約束滿足問題,提出了置信傳播和模擬退火相結(jié)合的求解算法。這種算法先通過置信傳播方程收斂后得到變量取值的邊際概率分布,分別采用最大概率和最小分量熵的策略產(chǎn)生一組啟發(fā)式的初始賦值,再用模擬退火對這組賦值進(jìn)行修正。實(shí)驗(yàn)結(jié)果表明,該算法大大提高了初始賦值向最優(yōu)解收斂的速度,表現(xiàn)出了顯著優(yōu)越于模擬退火算法的求解性能。
注: 保護(hù)知識產(chǎn)權(quán),如需閱讀全文請聯(lián)系計(jì)算機(jī)應(yīng)用研究雜志社