【產(chǎn)通社，3月21日訊】中國科學院（Chinese Academy of Sciences）官網(wǎng)消息，軟件研究所計算機科學國家重點實驗室博士研究生劉明昊針對人工智能和理論計算機科學中的基礎問題之一——最大可滿足性問題（MaxSAT），提出了一種基于圖神經(jīng)網(wǎng)絡的深度學習系統(tǒng)，在求解大規(guī)模的困難MaxSAT實例時可以快速獲得更高質量的解。

最大可滿足性問題即給定一個命題邏輯公式，要求找到滿足最多數(shù)量布爾約束的解。該問題在理論計算機科學、知識推理、電子設計自動化和組合優(yōu)化等領域有重要應用。傳統(tǒng)的MaxSAT求解算法主要基于人工設計的高效啟發(fā)式搜索策略，難以有效遷移到不同分布的問題實例上。該研究創(chuàng)新性地提出了一種圖神經(jīng)網(wǎng)絡模型，能夠從小規(guī)模的簡單實例中學習出有效的解生成策略，并泛化到同分布的較大規(guī)模實例上。實驗結果表明，該模型在兩種不同分布的實例集上均能夠學習至收斂，在包含1600個變量的困難測試實例上相較于最先進的傳統(tǒng)算法可以產(chǎn)生更優(yōu)的解，且求解階段用時顯著低于傳統(tǒng)算法。該研究揭示了將深度學習與符號推理兩類人工智能方法進行更深入結合的價值。 

相關研究成果以Can graph neural networks learn to solve the MaxSAT problem為題，發(fā)表在人工智能領域國際頂級會議AAAI 2023的學生摘要軌道，并獲大會最佳學生摘要提名獎（Honorable Mention）。

查詢進一步信息，請訪問官方網(wǎng)站http://www.cas.cn/syky/202303/t20230313_4879885.shtml。（張嘉汐，產(chǎn)通發(fā)布）    （完）