[發明專利]優化設備、優化程序和優化方法

在審

• 申請號: 202010942054.5
• 申請日: 2020-09-09
• 公開（公告）號: CN112487345A
• 公開（公告）日: 2021-03-12
• 發明（設計）人: 覺幸典弘;宮澤俊之
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F17/11
• 分類號: G06F17/11
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 劉雯鑫;姚文杰

本發明涉及優化設備、優化程序和優化方法。一種優化設備，包括：搜索單元，用于通過使用第一方法來執行對解的搜索，通過該第一方法，包括約束的目標函數的值被概率性地改善；以及生成單元，用于生成第一狀態，所述第一狀態處于距由搜索單元獲得的先前的解超過預定距離處，以及用于通過使用第二方法來獲得局部解，通過該第二方法，執行從第一狀態開始的狀態轉變，以滿足約束并且與通過第一方法相比以更高的概率改善目標函數的值，然后輸出局部解作為初始狀態，其中，生成單元輸出初始狀態的處理和搜索單元基于第一方法從初始狀態執行對解的搜索的處理被迭代地執行。

技術領域

本文中的公開內容涉及優化設備、優化程序和優化方法。

背景技術

諸如計算機的算術設備通過各種數據操作進行信息處理以產生有意義的輸出，從而使得能夠在現代社會的各個領域中進行預測、確定、控制等。優化處理是信息處理的分支。優化問題是找到屬于搜索空間的、使搜索空間中限定的目標函數的值最小化(或最大化)的點(即，解)的問題。優化問題可以大致分為線性規劃問題和離散優化問題。在離散優化問題的情況下，搜索空間維數的增加導致變量的組合的數目爆炸性增長。在這種情況下，使用計算所有可能的組合的窮舉搜索需要很長的計算時間，這實際上是不可行的。

大規模多元離散優化問題可以通過下述方式來解決：通過基于近似解方法或啟發式方法在現實可行的計算時間內找到良好的近似解而不是找到精確的最優解。基于啟發式方法并且適用于各種問題的通用近似算法(元啟發式算法)包括隨機游走搜索算法、模擬退火算法、遺傳算法、隨機進化算法等。用于執行模擬退火的機制的示例包括使用伊辛能量函數的伊辛機(即，玻爾茲曼機)。在伊辛機中，將要解決的問題轉化為表示磁性材料的自旋行為的伊辛模型，并且然后計算該問題的解。

上述近似算法被設計成使得將概率元素引入從初始狀態——即，起點——執行的狀態轉變中，以搜索獲得目標函數的連續較小值的解，從而使得狀態能夠收斂于接近最優解而不會陷入不利的局部最小值。仔細設計的概率元素的控制和足夠長的計算時間的使用允許狀態收斂于最優解或足夠接近最優解的解。然而，在實際可行的計算時間內，并不總是容易獲得足夠接近最優解的解。對于每個優化問題，也難以設計對概率元素的適當控制。

為了減少搜索解所需的時間，例如，可以隨機地設置初始狀態，并且可以從不同的初始狀態多次重復對解的搜索。即使在其中從給定初始狀態開始的對解的搜索陷入目標函數的值不足夠小的局部最小值的情況下，這種對解的搜索也可以在適當的時間終止，然后從不同的初始狀態開始新的對解的搜索。這種安排使得能夠從局部解中逃離，并且減少了獲得最優解所需的時間，而不會在從初始狀態開始的搜索中浪費時間以致陷入不利的局部解而結束或者在達到最優解之前需要很長的時間。

如在施加了約束條件的情況下，當問題的難度由于大量的局部解而高時，在不增加從局部解逃離的發生次數的情況下，即，在不增加從新的初始狀態進行對解的搜索的次數的情況下，即使如上所述從不同初始狀態迭代地執行對解的搜索，可能也無法獲得令人滿意的解。此外，隨著越來越多地逃離局部解，隨機生成的初始狀態接近已經通過先前搜索找到的局部解的概率增加。在這種情況下，可能執行第二次收斂于該局部解的不必要的搜索。

因此，可以期望提供在從不同的初始狀態重復對解的搜索時通過其設置適當的初始狀態的機制。

[專利文獻1]日本未審查專利申請公開第2014-178717號

[專利文獻2]日本公開特許公報第2009-48353號

發明內容