[發(fā)明專利]組合優(yōu)化設(shè)備、組合優(yōu)化方法以及計(jì)算機(jī)可讀記錄介質(zhì)

在審

• 申請?zhí)枺?/td>: 202010580033.3
• 申請日: 2020-06-23
• 公開（公告）號: CN112434398A
• 公開（公告）日: 2021-03-02
• 發(fā)明（設(shè)計(jì)）人: 大島弘敬
• 申請（專利權(quán)）人: 富士通株式會社
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06Q10/04;G06F111/04;G06F111/06
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 高巖;崔俊紅

本發(fā)明提供組合優(yōu)化設(shè)備、組合優(yōu)化方法以及計(jì)算機(jī)可讀記錄介質(zhì)。該組合優(yōu)化設(shè)備包括：存儲單元，其存儲包括在第一能量函數(shù)中的多個(gè)狀態(tài)變量的值，所述第一能量函數(shù)被給出為具有表示針對所述多個(gè)狀態(tài)變量的約束條件的項(xiàng)；以及處理單元，其執(zhí)行對使第一能量函數(shù)的值最小化的多個(gè)狀態(tài)變量的值的搜索，其中，由處理單元執(zhí)行的搜索包括：通過使用所述第一能量函數(shù)執(zhí)行的第一搜索、在第一搜索之后通過使用第二能量函數(shù)執(zhí)行的第二搜索以及在第二搜索之后通過使用第一能量函數(shù)執(zhí)行的第三搜索，所述第二能量函數(shù)是通過從第一能量函數(shù)中移除表示約束條件的項(xiàng)而獲得的。

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

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

背景技術(shù)

組合優(yōu)化問題存在于現(xiàn)代社會的各個(gè)領(lǐng)域。例如，在諸如制造、分配和銷售的領(lǐng)域中搜索用于使成本最小化的元素的組合。然而，組合優(yōu)化問題的計(jì)算時(shí)間隨著與元素相對應(yīng)的變量的數(shù)目的增加而呈指數(shù)增加，并且因此，組合優(yōu)化問題被認(rèn)為是在馮·諾依曼計(jì)算機(jī)中難以求解的問題。

作為求解馮·諾依曼計(jì)算機(jī)不擅長的許多變量的組合優(yōu)化問題的方法，存在通過用伊辛模型代替計(jì)算目標(biāo)的組合優(yōu)化問題來執(zhí)行計(jì)算的方法，其中伊辛模型是表示磁性物質(zhì)的自旋行為的模型。

存在組合優(yōu)化問題包括約束條件的情況。例如，考慮以下方法：在該方法中，通過能量函數(shù)表示組合優(yōu)化問題并使用諸如模擬退火方法的隨機(jī)搜索方法來求解該組合優(yōu)化問題，所述能量函數(shù)由表示最優(yōu)條件的成本項(xiàng)和表示約束條件的約束項(xiàng)之和定義。

在日本公開特許公報(bào)第05-120252號和日本公開特許公報(bào)第2004-110831號中公開了相關(guān)技術(shù)。

發(fā)明內(nèi)容

在能量函數(shù)包括約束項(xiàng)的情況下，將約束違反公式化以增加能量，并且因此由于能量壘而導(dǎo)致向相鄰狀態(tài)的轉(zhuǎn)變延遲。

在一方面，本發(fā)明的目的是提供對由于能量壘而導(dǎo)致向相鄰狀態(tài)的轉(zhuǎn)變被延遲的狀態(tài)進(jìn)行求解的組合優(yōu)化設(shè)備、組合優(yōu)化方法以及組合優(yōu)化程序。

在一方面，提供了一種組合優(yōu)化設(shè)備。該組合優(yōu)化設(shè)備包括存儲單元和處理單元。存儲單元存儲包括在第一能量函數(shù)中的多個(gè)狀態(tài)變量的值，所述第一能量函數(shù)被給出為具有表示針對多個(gè)狀態(tài)變量的約束條件的項(xiàng)。處理單元執(zhí)行對使所述第一能量函數(shù)的值最小化的多個(gè)狀態(tài)變量的值的搜索。由處理單元執(zhí)行的搜索包括：通過使用第一能量函數(shù)執(zhí)行的第一搜索、在第一搜索之后通過使用第二能量函數(shù)執(zhí)行的第二搜索以及在第二搜索之后通過使用第一能量函數(shù)執(zhí)行的第三搜索，所述第二能量函數(shù)是通過從第一能量函數(shù)中移除表示約束條件的項(xiàng)而獲得的。

在一方面，提供了一種組合優(yōu)化方法。

另外，在一方面，提供了一種組合優(yōu)化程序。

根據(jù)一方面，可以對由于能量壘而導(dǎo)致向相鄰狀態(tài)的轉(zhuǎn)變被延遲的狀態(tài)進(jìn)行求解。

附圖說明

圖1是示出根據(jù)第一實(shí)施方式的組合優(yōu)化設(shè)備的示例的圖。

圖2是示出根據(jù)第二實(shí)施方式的組合優(yōu)化設(shè)備的硬件示例的圖。

圖3是示出能量函數(shù)的示例的圖。

圖4是示出問題的公式表示的示例的圖。

圖5是示出問題的公式表示的示例(續(xù))的圖。

圖6是示出組合優(yōu)化設(shè)備的功能示例的圖。

圖7是示出擦除表示約束條件的項(xiàng)的示例的圖。

圖8是示出搜索的示例的流程圖。

圖9是示出搜索的示例的圖。

圖10是示出解的能量的示例的圖。

圖11是示出根據(jù)第三實(shí)施方式的擦除表示約束條件的項(xiàng)的示例的圖。