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

在審

• 申請號: 202110188961.X
• 申請日: 2021-02-19
• 公開（公告）號: CN113312831A
• 公開（公告）日: 2021-08-27
• 發明（設計）人: 島田大地
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F30/27
• 分類號: G06F30/27;G06Q10/04;G06F111/04;G06F111/06
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 唐京橋;崔俊紅

本申請公開了優化設備、優化方法和優化程序。一種信息處理設備，用于將多個項目分配給多個分配位置，每個項目具有第一屬性值和第二屬性值，每個分配位置具有關于第一屬性的最大限制；基于第一屬性值和第二屬性值執行計算多個項目中的每一個項目的評估值；按評估值的降序將盡可能多的未分配項目分配給單個分配位置；從分配給單個分配位置的項目中選擇一個或更多個項目以創建副本，然后將副本添加至未分配項目；從分配位置刪除副本和用于副本創建的項目，從而針對留下而未被刪除的項目固定分配；以及執行元啟發式算法以分配多個項目中的尚未固定分配的項目。

技術領域

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

背景技術

多背包問題是組合優化中的問題。在多背包問題中，將各自具有給定重量和給定值的多個項目打包到各自具有重量容量限制的多個背包中，使得總重量小于或等于該限制。通過尋找使分配給多個背包的項目的值的總和最大化的背包和項目的組合來獲得多背包問題的解。

在組合優化問題中，搜索空間維數的增加導致變量的組合的數目的爆炸性增加。在這種情況下，使用計算所有可能的組合的窮舉搜索需要很長的計算時間，這實際上是不可行的。因此，代替尋找真正的最優解，可以使用基于啟發式方法的通用近似算法(即，元啟發式算法)，或者可以使用在實際可行的計算時間內獲得良好的近似解的近似算法。

如果給定足夠長的計算時間，則元啟發式算法可以通過從初始狀態開始的狀態轉換以搜索連續獲得目標函數的較小值的解來獲得最優解或足夠接近最優解的解。然而，在實際可行的計算時間內，并不總是容易獲得足夠接近最優解的解。

貪婪算法是可以在可行的計算時間內獲得良好的近似解的近似算法之一。在貪婪算法中，例如，將通過將值除以重量而獲得的評估值給予每個項目，并且將項目按評估值的降序打包到背包中。利用這種布置，可以高速獲得背包和項目的所有組合中的獲得相對較大的評估值的總和的組合。然而，該解的精度低于元啟發式算法的情況。

為了在可行的計算時間內獲得足夠接近最優解的解，可以想到首先使用貪婪算法來固定一些項目的分配，并且然后針對剩余項目應用元啟發式算法。在這種情況下，貪婪算法可以在使用元啟發式算法之前的預處理階段充分減小組合優化問題的大小，這可以使得能夠在可行的計算時間內獲得高質量的解。

在這樣做時，即使在通過貪婪算法固定了一些項目的分配之后，仍然應當獲得接近最優解的高質量解。考慮到這一點，需要在所有對中僅固定合適的對，每個對包括背包和分配給其的項目。

因此，在多背包問題中使用元啟發式算法之前，當使用貪婪算法來固定項目的分配時，會期望選擇適合于固定分配的項目。

[相關技術文獻]

[專利文獻]

[專利文獻1]日本公開特許公報第2019-046031號。

[專利文獻2]日本公開特許公報第2011-100303號。

發明內容