[發明專利]優化裝置及優化方法

在審

• 申請號: 202010542694.7
• 申請日: 2020-06-15
• 公開（公告）號: CN112100799A
• 公開（公告）日: 2020-12-18
• 發明（設計）人: 田村泰孝;此島真喜子
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06Q10/04;G06F111/04;G06F111/06
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 高巖;楊林森

提供了優化裝置及優化方法。優化裝置包括：狀態保持單元，其保持在表示能量的評價函數中包括的多個狀態變量的值以及針對狀態變量的每個集合的權重值；能量變化計算單元，其在多個狀態變量的任何值改變的情況下，基于多個狀態變量的值和權重值計算在多個狀態變量的值中的每個值被設置為下一變化候選時的能量變化值；懲罰加法單元，其通過將根據違反不等式約束的超出量的懲罰值與針對多個狀態變量計算出的多個能量變化值中的每個能量變化值相加來計算總能量變化值，該超出量是基于耦合系數以及閾值來計算的；以及更新控制單元，其基于設置溫度值、隨機數值和多個總能量變化值來改變在狀態保持單元中保持的多個狀態變量的任何值。

技術領域

實施方式涉及優化裝置及優化方法。

背景技術

作為求解諾伊曼型(Neumann-type)計算機不容易處理的各種變量的優化問題的方法，存在使用伊辛型(Ising-type)能量函數(也被稱為評價函數或目標函數)的優化裝置(也稱為伊辛機(Ising machine)或玻爾茲曼機(Boltzmann machine))。優化裝置通過用伊辛模型代替計算對象的問題來對該問題進行計算，該伊辛模型是表示磁性材料的自旋(spin)行為的模型。

還可以通過使用例如神經網絡來對優化裝置進行建模。在這種情況下，與伊辛模型函數中包括的多個自旋相對應的多個狀態變量中的每一個作為神經元，該神經元根據另一狀態變量的值以及指示另一狀態變量與它自身的狀態變量之間的相互作用的大小的權重系數來輸出0或1。優化裝置通過使用隨機搜索方法例如模擬退火獲得相應狀態變量的值的如下組合作為解：根據所述組合獲得以上所描述的能量函數(下文中稱為能量)的最小值。

此處，提出了一種通過使用例如數字電路執行模擬退火來計算具有最小能量的每個狀態變量的值的組合的優化裝置。另外，提出了一種包括對伊辛模型中的相應自旋之間的相互作用進行模擬的伊辛芯片和控制該伊辛芯片的信息處理單元的信息處理裝置。

提出了一種優化系統，該優化系統通過將二進制二次規劃問題簡化為半正定規劃問題、得到半正定規劃問題的解并將所得到的半正定規劃問題的解轉換成二進制二次規劃問題的解來得出最優解。

在日本公開特許公報第2018-41351號、國際公布小冊子第WO2017/017807號和國際公布小冊子第WO 2017/056366號中公開了相關技術。

發明內容

以上所描述的優化裝置使由狀態變量的二次形式表示的評價函數最小化。同時，在優化問題中，可以施加由不等式表示(例如針對某些量(例如，裝載量或預算)提供上限或下限來表示)的約束條件(不等式約束)。然而，通過優化裝置可能難以求解將不等式約束公式化為狀態變量的二次形式的問題。

在一方面，本發明的目的是提供有效地求解包括不等式約束的問題的優化裝置和優化方法。

在一方面，提供了一種優化裝置。該優化裝置包括狀態保持單元、能量變化計算單元、懲罰加法單元和更新控制單元。狀態保持單元保持在表示能量的評價函數中包括的多個狀態變量的值以及針對狀態變量的每個集合的權重值。能量變化計算單元在多個狀態變量的任何值改變的情況下基于多個狀態變量的值和權重值計算在多個狀態變量的值中的每個值被設置為下一變化候選時的能量變化值。懲罰加法單元通過將根據違反不等式約束的超出量的懲罰值與針對多個狀態變量計算出的多個能量變化值中的每個能量變化值相加來計算總能量變化值，該超出量是基于指示不等式約束中的多個狀態變量中的每個狀態變量的權重的耦合系數以及閾值來計算的。更新控制單元基于設置溫度值、隨機數值和多個總能量變化值來改變保持在狀態保持單元中的多個狀態變量的任何值。

此外，在一方面，提供了一種優化方法。

[本發明的有利效果]

在一方面，可以有效地求解包括不等式約束的問題。

附圖說明