[發(fā)明專利]優(yōu)化設(shè)備、優(yōu)化方法和記錄優(yōu)化程序的記錄介質(zhì)

在審

• 申請?zhí)枺?/td>: 202110183715.5
• 申請日: 2021-02-10
• 公開（公告）號: CN113537551A
• 公開（公告）日: 2021-10-22
• 發(fā)明（設(shè)計）人: 松浦聰
• 申請（專利權(quán)）人: 富士通株式會社
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F17/18
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 康建峰;王曉芬

提供了優(yōu)化設(shè)備、優(yōu)化方法和記錄優(yōu)化程序的記錄介質(zhì)。優(yōu)化設(shè)備包括：溫度控制單元，控制溫度值；能量變化量計算單元，計算能量變化量；確定單元，其根據(jù)能量變化量與閾值之間的關(guān)系隨機確定是否接受狀態(tài)轉(zhuǎn)變；期望值保存單元，保存每個狀態(tài)的期望值；期望值比較單元，比較期望值與對應狀態(tài)值，提取不相等狀態(tài)變量；確認單元，選擇由期望值比較單元提取的狀態(tài)變量并改變所選狀態(tài)變量的狀態(tài)直至狀態(tài)值均等于期望值，以及在狀態(tài)值一旦等于期望值后選擇被確定單元接受的狀態(tài)轉(zhuǎn)變的狀態(tài)變量并改變所選狀態(tài)變量的狀態(tài)；能量計算單元，其計算狀態(tài)被改變后的轉(zhuǎn)變后能量；以及搜索單元，在轉(zhuǎn)變后能量小于最低能量的情況下將轉(zhuǎn)變后能量設(shè)置為最低能量。

技術(shù)領(lǐng)域

本文討論的實施方式涉及優(yōu)化設(shè)備、優(yōu)化方法和優(yōu)化程序。

背景技術(shù)

在我們的社會中，存在許多“組合優(yōu)化問題”，例如對災難恢復過程的優(yōu)化以及對遞送路線的優(yōu)化，這些組合優(yōu)化問題中的每一個都在諸如有限人力資源和有限時間的約束下從許多要素的組合之中選擇最優(yōu)組合。作為搜索組合優(yōu)化問題的最優(yōu)解的方法之一，存在應用了被稱為模擬退火方法的一種蒙特卡洛(Monte Carlo)方法的伊辛(Ising)計算裝置。模擬退火方法是通過使用隨機數(shù)值來隨機獲得解的方法。

伊辛計算裝置是搜索使由預定評價公式表示的伊辛模型的能量最小化的變量的組合的計算裝置。在一些情況下，該變量被稱為自旋，變量的值被稱為自旋狀態(tài)，并且自旋狀態(tài)的轉(zhuǎn)變被稱為反轉(zhuǎn)。

伊辛計算裝置基于反轉(zhuǎn)確定公式確定是否反轉(zhuǎn)每個自旋，并且通過依次轉(zhuǎn)變狀態(tài)來搜索最低能量。將實際問題各自公式化到伊辛模型的能量公式中，并且利用伊辛計算裝置搜索使能量最小化的自旋狀態(tài)的組合，使得可以求解各種類型的組合優(yōu)化問題。

將簡要描述模擬退火方法中的最低能量搜索方法。伊辛計算裝置從初始狀態(tài)開始搜索，在初始狀態(tài)中，將0或1代入表示要求解的問題的評價函數(shù)中的每個變量。伊辛計算裝置選擇與變量組合的當前狀態(tài)接近的狀態(tài)并且考慮向接近狀態(tài)進行轉(zhuǎn)變。與當前狀態(tài)接近的狀態(tài)是例如其中一個變量的狀態(tài)被改變的狀態(tài)。接下來，伊辛計算裝置計算隨著向所選擇的狀態(tài)轉(zhuǎn)變的能量變化量，并且根據(jù)所計算的值隨機地選擇是接受該狀態(tài)轉(zhuǎn)變還是拒絕該狀態(tài)轉(zhuǎn)變并維持當前狀態(tài)。當將針對能量減小的情況的接受概率設(shè)置為高于針對能量增大的情況的接受概率時，沿能量平均減小的方向發(fā)生狀態(tài)變化，并且伊辛計算裝置最終能夠達到最優(yōu)解處的能量或接近最優(yōu)解處的能量。如果在能量減小的情況下確定地接受狀態(tài)轉(zhuǎn)變并且在能量增大的情況下拒絕狀態(tài)轉(zhuǎn)變，則從廣義上講能量的變化將隨時間單調(diào)減小。然而，當達到局部解時，不會發(fā)生其他狀態(tài)轉(zhuǎn)變，并且難以期望達到最優(yōu)解。因此，在針對組合優(yōu)化問題的搜索中，隨機地確定是否接受狀態(tài)轉(zhuǎn)變很重要。

在退火方法中，通過確定例如將1和e^-(ΔE/T)中較小的值用作狀態(tài)轉(zhuǎn)變的接受概率，證明了狀態(tài)在無限次數(shù)的極限內(nèi)被優(yōu)化。此處，T是被稱為溫度的參數(shù)。伊辛計算裝置將T設(shè)置為足夠高作為初始溫度并且根據(jù)搜索的迭代次數(shù)來降低T。在通過使用遵循上述公式設(shè)置的接受概率在足夠大迭代次數(shù)之后達到穩(wěn)態(tài)的情況下，每種狀態(tài)所占的概率在力學中的熱平衡下遵循玻爾茲曼分布。因此，當溫度從高溫逐漸降低時，低能量狀態(tài)的占有率增大。出于這個原因，當溫度充分降低時，伊辛計算裝置能夠獲得接近最優(yōu)解的低能量狀態(tài)。

伊辛計算裝置從初始狀態(tài)開始、迭代上述處理并在完成特定次數(shù)迭代時結(jié)束操作，在初始狀態(tài)中，適當?shù)卦O(shè)置自旋狀態(tài)的初始值、局部字段(local field)的初始值以及可根據(jù)自旋狀態(tài)的初始值計算的能量。伊辛計算裝置此時保持的最低能量值和自旋狀態(tài)的組即為搜索結(jié)果。

近年來，出于解決具有較大規(guī)模并且難度較高的問題的原因以及其他原因，已經(jīng)提出了通過伊辛計算裝置與軟件協(xié)作來搜索最低能量而不是單獨通過伊辛計算裝置來搜索最低能量的方法。在這樣的方法中，軟件通過預處理預先確定用于開始計算的自旋狀態(tài)或者在計算過程中取出伊辛計算裝置的結(jié)果、更改某些自旋狀態(tài)并且然后將所得自旋狀態(tài)再次返回給伊辛計算裝置以繼續(xù)搜索。