(57)【要約】【課題】高速に劣モジュラ最大化問題の近似解を所望の精度で求めることができる。【解決手段】探索部が、受け付けた近似精度を表すパラメータαと、集合Ｕ、劣モジュラ関数、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを入力として、コスト制約を満たす部分集合Ｓの集合Ｆのうち、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された部分集合Ｓｍａｘのスコアの比が、近似精度を表すパラメータα以上となったときの部分集合Ｓｍａｘを、劣モジュラ最大化問題の近似解として出力する。【選択図】図５
2019079237.tif 000002
【特許請求の範囲】
【請求項１】
要素の集合から非冗長な部分集合を探索する劣モジュラ最大化問題において、
近似精度を表すパラメータαと、前記劣モジュラ最大化問題の要素の各々を含む集合Ｕ、前記集合Ｕの部分集合に対するスコアを定義する劣モジュラ関数、前記要素の各々についてのコストｃＵ、及び前記コストの上限Ｂとを入力として受け付ける入力部と、
前記コストの上限Ｂに基づくコスト制約を満たす部分集合Ｓの集合Ｆのうち、前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと前記近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された前記部分集合Ｓｍａｘのスコアの比が、前記近似精度を表すパラメータα以上となったときの前記部分集合Ｓｍａｘを、前記劣モジュラ最大化問題の近似解として出力する探索部と、
を含む最適化装置。
【請求項２】
前記探索部は、新たに探索された前記部分集合Ｓｍａｘについて、前記部分集合Ｓｍａｘのスコアと、前記部分集合Ｓｍａｘについてのヒューリスティック関数の値と、前記近似精度を表すパラメータαとを用いて値ｆを計算し、
前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索する際には、前記値ｆが最大となる前記部分集合Ｓｍａｘを包含し、かつ、コスト制約を満たす部分集合Ｓから、前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索する請求項１記載の最適化装置。
【請求項３】
前記ヒューリスティック関数の値は、以下（１）式により計算する請求項２に記載の最適化装置。
【数１】
2019079237.tif 000015
・・・（１）
ただし、Ｘ１：ｋは、前記探索部において任意のｉ∈［ｋ］に対しｉ番目の探索までに追加した要素からなる集合であり、
【数２】
2019079237.tif 000016
2019079237.tif 000017
2019079237.tif 000018
であり、ＸｉはＸ１：ｋのｉ番目の要素であり、ｇｓ（・）＝ｇ（・｜Ｓ）は劣モジュラ関数であり、~ｇは任意の集合関数
【数３】
2019079237.tif 000019
であり、Ｖは集合Ｕについての任意の部分集合Ｖ∈Ｕであり、ＶＳはコスト制約を満たす部分集合Ｓにおける任意の部分集合であり、ｌは前記探索部の計算において予め定められた要素数であり、ｍは前記ＶＳの要素数である。
【請求項４】
前記部分集合の包含関係に基づいて前記コスト制約を満たす前記部分集合を表す頂点を有向枝で結合した状態空間木を構築する構築部を更に含み、
前記探索部は、前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返す際に、前記状態空間木を用いて、前記スコアが最大となる部分集合Ｓｍａｘを探索する請求項１〜３の何れか１項に記載の最適化装置。
【請求項５】
要素の集合から非冗長な部分集合を探索する劣モジュラ最大化問題において、
入力部が、近似精度を表すパラメータαと、前記劣モジュラ最大化問題の要素の各々を含む集合Ｕ、前記集合Ｕの部分集合に対するスコアを定義する劣モジュラ関数、前記要素の各々についてのコストｃＵ、及び前記コストの上限Ｂとを入力として受け付けるステップと、
探索部が、前記コストの上限Ｂに基づくコスト制約を満たす部分集合Ｓの集合Ｆのうち、前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと前記近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された前記部分集合Ｓｍａｘのスコアの比が、前記近似精度を表すパラメータα以上となったときの前記部分集合Ｓｍａｘを、前記劣モジュラ最大化問題の近似解として出力するステップと、
を含む最適化方法。
【請求項６】
コンピュータを、請求項１〜請求項４のいずれか１項に記載の最適化装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、方法、及びプログラムに係り、特に、劣モジュラ最大化問題を解くための最適化装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
劣モジュラ最大化問題は、「ある集合から非冗長な部分集合を選ぶ」という文脈で頻繁に現れる問題である。例えば、屋内にセンサーを複数配置することによって気温等の情報を集めたいという状況を考える。センサーを配置できる候補箇所（例えば、電源の差し込み口付近など）はあらかじめ決められているとする。この問題は、候補箇所の集合の中からいくつかの箇所（部分集合）を選び、センサーの配置箇所を決める問題となっている。この問題において、センサーを密集させて配置してしまうと、いくつかのセンサーからはほぼ同様な情報が得られると思われるため、冗長であると言える。劣モジュラ関数はそのような冗長性を表現した関数であり、劣モジュラ関数で表されるスコアを最大化するようにセンサーを配置する箇所を選ぶことで、観測対象範囲を満遍なくカバーするような、非冗長なセンサー配置を実現できる。
【０００３】
このような劣モジュラ関数最大化に対しては非特許文献１のような貪欲法によって、
【０００４】
【数１】
2019079237.tif 000003
【０００５】
近似保証を持つ解を得ることができる（ただしｅはネイピア数）。また、貪欲法よりも長い計算時間を費やすことを許すならば、非特許文献２のような方法で任意のα∈[0,1]に対して近似保証を持つ解を得ることができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41-43, 2004.
【非特許文献２】W. Chen, Y. Chen, K. Weinberger. Filtered search for submodular maximization with controllable approximation bounds. 18th International Conference on Articial Intelligence and Statistics, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述の非特許文献１にあるように、劣モジュラ最大化の１−１/ｅ近似解は貪欲法によって効率的に計算できる。しかし、多くの現実問題では１−１/ｅ近似保証では精度として不十分である。例えば、上述のセンサ配置問題の場合、非常に高額なセンサーを用いて重要な情報を集めるような状況では、可能な限り最適解に近いと保証された解に従ってセンサーを配置するのが望ましい。非特許文献２の方法は任意のαに対してα近似解を計算できるが、解の探索時に用いる技術の一部が劣モジュラ最大化問題に適しておらず、結果として膨大な計算時間を要することが多い。
【０００８】
本発明は、上記問題点を解決するために成されたものであり、高速に劣モジュラ最大化問題の近似解を所望の精度で求めることができる最適化装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明に係る最適化装置は、要素の集合から非冗長な部分集合を探索する劣モジュラ最大化問題において、近似精度を表すパラメータαと、前記劣モジュラ最大化問題の要素の各々を含む集合Ｕ、前記集合Ｕの部分集合に対するスコアを定義する劣モジュラ関数、前記要素の各々についてのコストｃＵ、及び前記コストの上限Ｂとを入力として受け付ける入力部と、前記コストの上限Ｂに基づくコスト制約を満たす部分集合Ｓの集合Ｆのうち、前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと前記近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された前記部分集合Ｓｍａｘのスコアの比が、前記近似精度を表すパラメータα以上となったときの前記部分集合Ｓｍａｘを、前記劣モジュラ最大化問題の近似解として出力する探索部と、を含んで構成されている。
【００１０】
本発明に係る最適化方法は、要素の集合から非冗長な部分集合を探索する劣モジュラ最大化問題において、入力部が、近似精度を表すパラメータαと、前記劣モジュラ最大化問題の要素の各々を含む集合Ｕ、前記集合Ｕの部分集合に対するスコアを定義する劣モジュラ関数、前記要素の各々についてのコストｃＵ、及び前記コストの上限Ｂとを入力として受け付けるステップと、探索部が、前記コストの上限Ｂに基づくコスト制約を満たす部分集合Ｓの集合Ｆのうち、前記スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと前記近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された前記部分集合Ｓｍａｘのスコアの比が、前記近似精度を表すパラメータα以上となったときの前記部分集合Ｓｍａｘを、前記劣モジュラ最大化問題の近似解として出力するステップと、を含んで実行することを特徴とする。
【００１１】
また、本発明のプログラムは、コンピュータを、上記の最適化装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１２】
本発明の最適化装置、方法、及びプログラムによれば、受け付けた近似精度を表すパラメータαと、集合Ｕ、劣モジュラ関数、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを入力として、コストの上限Ｂに基づくコスト制約を満たす部分集合Ｓの集合Ｆのうち、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された部分集合Ｓｍａｘのスコアの比が、近似精度を表すパラメータα以上となったときの部分集合Ｓｍａｘを、劣モジュラ最大化問題の近似解として出力することにより、高速に劣モジュラ最大化問題の近似解を所望の精度で求めることができる、という効果が得られる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態で構築する状態空間木の一例を示す図である。
【図２】本発明の実施の形態で用いるAlgorithm1において示されるBFSTCの一例を示す図である。
【図３】Algorithm1において呼び出されるAlgorithm2の一例を示す図である。
【図４】Algorithm2において呼び出されるAlgorithm3の一例を示す図である。
【図５】本発明の実施の形態に係る最適化装置の構成を示すブロック図である。
【図６】探索部の構成を示すブロック図である。
【図７】本発明の実施の形態に係る最適化装置における最適化処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１５】
＜本発明の実施の形態に係る概要＞
【００１６】
まず、本発明の実施の形態における概要を説明する。
【００１７】
本発明では、[非特許文献２] の技術を改善することにより、既存法よりも大幅に高速化された劣モジュラ最大化装置を提案する。非特許文献２では、劣モジュラ最大化問題の分野において広く知られた最良優先探索(Best-First Search、以下BFSと記載)に基づく手法を用いている。後述のように、BFSはヒューリスティック関数と呼ばれる関数値によって優先度を定めつつ探索を進めるアルゴリズムである。本発明では、この劣モジュラ最大化に対するBFSに以下の３点の改良を加えることで、より効率化されたBFS（後述のBFSTC）を提案する。第１に、探索を行う空間を状態空間木と呼ばれる構造で表現し、必要なメモリを削減する。第２に、探索の途中で 近似が達成されたことを検出する技術を導入し、冗長な探索を省く。第３に、劣モジュラ最大化に適したヒューリスッティック関数を設計し、より効率的に探索を行う。
【００１８】
＜本発明の実施の形態に係る原理＞
【００１９】
次に、本発明の実施の形態における原理を説明する。
【００２０】
任意の正整数ｋに対し、[ｋ]＝{１,２,...,ｋ}とし、今、Ｕ＝[ｎ]とし、ｎ要素の集合Ｕの上での劣モジュラ最大化を考える。Ｕの上で定義される関数
【００２１】
【数２】
2019079237.tif 000004
は、任意のＸ,Ｙ⊆Ｕに対してｇ(Ｘ)＋ｇ(Ｙ)≧ｇ(Ｘ∪Ｙ)＋ｇ(Ｘ∩Ｙ)を満たすとき、劣モジュラ関数であると言われる（２ＵはＵの冪集合）。また、任意のＸ⊆Ｙ⊆Ｕに対してｇ(Ｘ)≦ｇ(Ｙ)が成り立つとき、gは単調であるという。
【００２２】
以下ではｇ(φ)＝０であるような単調劣モジュラ関数について考える。各アイテムｖ∈Ｕに対し、非負のコストｃｖが割り当てられているとし、ｃＸ＝{ｃｖ:ｖ∈Ｘ}、ｃ(Ｘ)＝Σｖ∈Ｘｃｖと定義する。本発明の実施の形態では、劣モジュラ最大化の中でも最も一般的な問題の一つである、以下のようなナップサック制約付き単調劣モジュラ最大化について考える。
【００２３】
【数３】
2019079237.tif 000005
・・・（１）
【００２４】
ただし、Ｂ＞０は事前に決められたコストの上限である。以下、この問題をSubmodular Knapsack Problemを略してSKPと呼び、その最適解をＸ＊と書くことにする。また、この問題のコスト制約を満たす実行可能な部分集合の集まりを、Ｆ＝{Ｘ⊆Ｕ:ｃ(Ｘ)≦Ｂ}と書く。以下では任意のＸ,Ｙ⊆Ｕに対し、
【００２５】
【数４】
2019079237.tif 000006
【００２６】
と定義する。
【００２７】
以下、任意のα∈[０,１]に対しα近似解Ｘ(すなわち、ｇ(Ｘ)≧αｇ(Ｘ＊)であるような解Ｘ）を出力する装置を想定して説明する。以下において想定する装置の大枠は基本的に非特許文献２で説明されているBFSの手順に基づいている。本発明の改良点に対応する部分については、現れる都度明記する。
【００２８】
次に、本実施の形態で用いる状態空間木について説明する。準備として、状態空間木Ｇ＝(Ｆ,Ｅ)を定義する。Ｇはφ∈Ｆを根とする木構造であり、Ｆは頂点集合、Ｅは有向枝集合である。２つの頂点Ｘ,Ｙ∈Ｆは、Ｘ＝Ｙ−ｍａｘＹであるような時、有向枝(Ｘ,Ｙ)∈Ｅによって結ばれている。ただし、ｍａｘＹはＹ[ｎ]に含まれる要素のうち、最も番号の大きな要素を表す。Ｇの例を図１に示す。図１ではＵ＝[３],ｃ１＝ｃ２＝ｃ３＝１,Ｂ＝２として、ｃ(Ｘ)≦２であるようなＵの部分集合Ｘたちを頂点に持つ状態空間木Ｇが示されている。例えば、{１}と{１,３}の間には、{１}＝{１,３}−ｍａｘ{１,３}が成立しているため、有向枝({１},{１,３})が存在している。非特許文献２では状態空間木の代わりに状態空間グラフと呼ばれる構造を用い、各Ｓ∈Ｆがすでに探索されたか否かをclosed listと呼ばれるデータ構造によって管理していたが、実用上closed listは膨大なメモリを要することが多い。本発明の実施の形態では、上記のような状態空間木を用いることでclosed listの使用を避け、探索時に使用するメモリを削減する。
【００２９】
次に、本発明の実施の形態において提案するBFS with Termination Condition(以下、BFSTCと記載）の詳細について説明する。本発明の実施の形態では、図２のAlgorithm1において示すBFSTCを用いて、上記で定義された状態空間木の上で探索を行うことで、α近似解を発見する。
【００３０】
BFSTCでは、この分野において広く知られているMaxHeapと呼ばれるデータ構造を用いる。MaxHeapはＳ∈Ｆと、Ｓに対して計算される値
【００３１】
【数５】
2019079237.tif 000007
【００３２】
の組<Ｓ,ｆ(Ｓ)>たちを保存するデータ構造である。MaxHeap.push<Ｓ,ｆ(Ｓ)>によって新たな組<Ｓ,ｆ(Ｓ)>をMaxHeapに追加することができる。また、MaxHeap.pop()によってMaxHeapに保存されている組の中でfの値が最大となる組<Ｓ,ｆ(Ｓ)>のＳを取り出すことができる。また、ＴはMaxHeapに保存されている組のうち、ｆの値が最大となる組の頂点である。ここで、ｆ(Ｓ)はｆ(Ｓ)＝ｇ(Ｓ)＋αｈ(Ｓ)という式で計算される値であり、ｈ(Ｓ)はヒューリスッティック関数と呼ばれる関数の値である。ヒューリスッティック関数の値の計算式については後述する。Algorithm1のGreedySK(Ｖ,~ｇ(・),ｃＶ,Ｃ)は任意のＶ⊆Ｕ、Ｃ≧０に対して、与えられた劣モジュラ関数
【００３３】
【数６】
2019079237.tif 000008
【００３４】
を最大化する問題ｍａｘＸ⊆Ｖ:ｃ(Ｘ)≦Ｃ~ｇ(Ｘ)を近似的に解く貪欲法であり、その詳細は図３に示すAlgorithm2、及び図４に示すAlgorithm3に記載された通りである。ただし、任意の集合関数
【００３５】
【数７】
2019079237.tif 000009
【００３６】
とＸ,Ｙ⊆Ｖに対し、~ｇ(Ｘ|Ｙ)＝~g(Ｘ＋Ｙ)−~ｇ(Ｙ)と定義する。また、任意の与えられたＳ∈Ｆに対し、ＢＳ＝Ｂ−ｃ(Ｓ),ＶＳ＝{ｖ∈Ｕ:ｃＶ≦ＢＳ},ｇＳ(・)＝ｇ(・|Ｓ)とする。
【００３７】
ここで、Algorithm2及びAlgorithm3について説明する。Algorithm2は、Algorithm1のStep12において呼び出され、(Ｖ,~ｇ(・),ｃＶ,Ｃ)を入力として、Ｙ∈(ｖmax,Ｙ)のうち最大となる~ｇ(Ｙ)を求めることで、＾Ｓの解を得る。＾Ｓは貪欲法が発見した最適なＳである。また、Algorithm2のStep1において、Ｘを求めるためにAlgorithm3のGreedyAddを呼び出し、(Ｖ,~ｇ(・),ｃＶ,Ｃ)を入力として、Ｃ以下のコスト制約を満たす中で最大と成るＸを求める。
【００３８】
本発明の実施の形態におけるBFSの改良点の一つは、Algorithm1のStep12-16に記載された停止条件（Termination Condition）である。具体的には、Algorithm1のStep14の停止条件が満たされれば、Ｓｍａｘ∈Ｆが所望のα近似解であることが保証されるため、Ｓｍａｘを出力し探索を終了することで、実行時間の短縮が可能となる。Ｓｍａｘは探索に最も最適なＳである。また、BFSTCでは、本手法で提案する以下のヒューリスティック関数を用いることで、探索を効率化している。現在の解Ｓ∈Ｆが与えられたもとで、Algorithm1のStep17で必要となるｈ(Ｓ)の値を計算する方法を示す。
【００３９】
ここでAlgorithm3の関数
【数８】
2019079237.tif 000010
【００４０】
が出力した解をＸ１:ｋと記述する。ただし、任意のｉ∈[ｋ]に対し、Ｘ１:ｉはAlgorithm3のGreedyAddがｉ番目までにStep5で追加した要素からなる集合とし、最終的にGreedyAddが出力した解が含む要素の数がｋであるとする（ｉ＜１ならばＸ１:ｉ＝φ）。また、ＸｉはＸ１:ｋのｉ番目の要素とする、ここで、β１:ｋを以下のように定義する。
【００４１】
【数９】
2019079237.tif 000011
【００４２】
ただし、ｉ∈[ｋ]に対し、
【００４３】
【数１０】
2019079237.tif 000012
【００４４】
とする。ｕmod(Ｘ１:ｉ)については後述する。以上を用い、ヒューリスティック関数の値は以下（２）式により計算される。
【００４５】
【数１１】
2019079237.tif 000013
・・・（２）
【００４６】
このｈ(Ｓ)を用いてｆ(Ｓ)の値を計算するためAlgorithm1のStep14の停止条件が記述可能になり、劣モジュラ最大化問題を解くのに適した計算が行える。以下では、与えられたＳ∈ＦとＹ⊆ＶＳに対し、ｕmod(Ｙ)を計算する手順を述べる。まずＶＳの要素をｒｖ＝ｇＳ(ｖ|Ｙ)/ｃｖの値が大きい順にソートする(ｖ∈ＶＳ)。
【００４７】
こうして得られた順序付きの集合をＶ１:ｍと記述する。ただしｍはＶＳの要素数であり、Ｖ１:ｉはＶ１:ｍの先頭ｉ個の要素からなる集合、ＶｉはＶ１:ｍのｉ番目の要素を表すものとする(ｉ＜１ならばＶ１:ｉ＝φ)。さらにｌ＝max{ｉ∈[ｍ]:ｃ(Ｖ１:ｉ)≦ＢＳ}とする。この時ｕmod(Ｙ)は以下のように計算される。
【００４８】
【数１２】
2019079237.tif 000014
【００４９】
以上の手続きにより、BFSTCの実行中に得られた任意のＳ∈Ｆに対して、ｈ(Ｓ)の値を計算することができる。
【００５０】
＜本発明の実施の形態に係る最適化装置の構成＞
【００５１】
次に、本発明の実施の形態に係る最適化装置の構成について説明する。図５に示すように、本発明の実施の形態に係る最適化装置１００は、ＣＰＵと、ＲＡＭと、後述する最適化処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この最適化装置１００は、機能的には図５に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００５２】
入力部１０は、近似精度を表すパラメータαと、劣モジュラ最大化問題の要素の各々を含む集合Ｕ、集合Ｕの部分集合に対するスコアを定義する劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを入力として受け付ける。
【００５３】
演算部２０は、主制御部３０と、計算部３８とを含んで構成されている。
【００５４】
主制御部３０は、構築部３２と、状態空間木３４と、探索部３６とを含んで構成されている。
【００５５】
構築部３２は、劣モジュラ最大化問題の要素の各々を含む集合Ｕ、要素の各々についてのコストｃＵ、及びコストの上限Ｂに基づいて、部分集合の包含関係に基づいてコスト制約を満たす部分集合を表す頂点Ｆを有向枝Ｅで結合したＧ＝(Ｆ,Ｅ)を状態空間木３４として構築する。なお、探索部３６の逐次探索に応じて、部分集合の包含関係に基づいてコスト制約を満たす部分集合を表す頂点Ｆを有向枝Ｅで結合したＧ＝(Ｆ,Ｅ)を状態空間木３４として逐次的に構築するようにしてもよい。例えば、図２のAlgorithm1の計算において必要になった部分についての状態空間木３４を構築するようにしてもよい。
【００５６】
探索部３６は、入力部１０で受け付けた近似精度を表すパラメータαと、集合Ｕ、劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを入力として、コストの上限Ｂに基づくコスト制約を満たす部分集合Ｓの集合Ｆのうち、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと近似精度を表すパラメータαとを用いて定められるスコアの上限ｇupperに対する、新たに探索された部分集合Ｓｍａｘのスコアの比が、近似精度を表すパラメータα以上となったときの部分集合Ｓｍａｘを、劣モジュラ最大化問題の近似解として出力する。
【００５７】
探索部３６は、図６に示すように、逐次実行部４０と、停止条件判定部４２とを含んで構成されている。
【００５８】
逐次実行部４０は、コスト制約を満たす部分集合Ｓの集合Ｆのうち、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返す。逐次実行部４０の処理は上記図２のAlgorithm1によって実行される。
【００５９】
逐次実行部４０では、新たに探索された部分集合Ｓｍａｘについて、部分集合Ｓｍａｘのスコアと、部分集合Ｓｍａｘについてのヒューリスティック関数の値ｈ(Ｓ)と、近似精度を表すパラメータαとを用いて値ｆ(Ｓ)を計算する（上記図２のAlgorithm1におけるStep17）。ヒューリスティック関数の値ｈ(Ｓ)は、計算部３８を呼び出することにより、上記（２）式に従って計算される。
【００６０】
また、逐次実行部４０は、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索する際に、ｆの初期値ｆ（φ）又は計算した値ｆ（Ｓ）が最大となる部分集合Ｓｍａｘを包含し、かつ、コスト制約を満たす貪欲法が見つけた最適な部分集合＾Ｓから、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索する（上記図２のAlgorithm1におけるStep11-19）。貪欲法を用いた探索は、計算部３８を呼び出することにより行われる（上記図３のAlgorithm2、図４のAlgorithm3）。
【００６１】
停止条件判定部４２は、既に探索された部分集合Ｓｍａｘのスコアと近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された部分集合Ｓｍａｘのスコアの比が、近似精度を表すパラメータα以上となるか否かを判定し、スコアの比が、近似精度を表すパラメータα以上である場合に、当該新たに探索された部分集合Ｓｍａｘを近似解として出力する（上記図２のAlgorithm1におけるStep14-15）。
【００６２】
また、停止条件判定部４２は、値ｆ（Ｓ）が最大となる部分集合Ｓｍａｘについてのヒューリスティック関数の値が０である場合に、当該値ｆ（Ｓ）が最大となる部分集合Ｓｍａｘを近似解として出力する（上記図２のAlgorithm1におけるStep7-8）。
【００６３】
計算部３８は、集合Ｕ、劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂを入力として、主制御部３０の逐次実行部４０の初期値であるＳｍａｘ、ヒューリスティック関数の初期値ｈ（φ）を計算する。また、計算部３８は、残りのコストＣ、残りのコストＣ以下の要素からなる部分集合Ｖ、部分集合Ｓに対して要素を追加したときのスコアの追加分を出力するモジュラ関数ｇS(・)、部分集合ＶについてのコストｃＶを入力として、逐次求めるコスト制約を満たす貪欲法が見つけた最適な部分集合＾Ｓ、及びヒューリスティック関数の値ｈ（Ｓ）を求める。計算部３８の処理は、上記図３のAlgorithm2及び図４のAlgorithm3により、逐次実行部４０から呼び出されて逐次実行される。
【００６４】
＜本発明の実施の形態に係る最適化装置の作用＞
【００６５】
次に、本発明の実施の形態に係る最適化装置１００の作用について説明する。入力部１０において近似精度を表すパラメータαと、劣モジュラ最大化問題の要素の各々を含む集合Ｕ、集合Ｕの部分集合に対するスコアを定義する劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを受け付けると、最適化装置１００は、図７に示す最適化処理ルーチンを実行する。
【００６６】
まず、ステップＳ１００では、主制御部３０が、入力部１０において受け付けたパラメータαと、集合Ｕ、劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを取得する。
【００６７】
ステップＳ１０２では、主制御部３０が、部分集合の包含関係に基づいてコスト制約を満たす部分集合を表す頂点Ｆを有向枝Ｅで結合したＧ＝(Ｆ,Ｅ)を状態空間木３４として構築する。
【００６８】
次に、ステップＳ１０４では、計算部３８が、劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂを入力として、初期値であるＳｍａｘ、ヒューリスティック関数の初期値ｈ（φ）を計算する。
【００６９】
ステップＳ１０６では、主制御部３０が、停止条件を満たすまで、計算部３８を呼び出しながら、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて繰り返し探索することにより、近似解である部分集合を求める。なお、停止条件は、上記図２のAlgorithm1におけるStep14において、既に探索された部分集合Ｓｍａｘのスコアと近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された部分集合Ｓｍａｘのスコアの比が、近似精度を表すパラメータα以上となるか否か、又はStep7においてｈ(Ｔ)＝０か否かとする。なお、Ｔが返されるのは、α＝１を設定した場合等、これ以上探索を行ってもよい解が見つからないとわかった場合（全ての探索を終えた場合）である。
【００７０】
ステップＳ１０８では、主制御部３０が、ステップＳ１０６で得られた解（Ｔ、又はＳｍａｘ）を出力して処理を終了する。
【００７１】
以上説明したように、本発明の実施の形態に係る最適化装置によれば、入力部１０で受け付けた近似精度を表すパラメータαと、集合Ｕ、劣モジュラ関数ｇ（・）、要素の各々についてのコストｃＵ、及びコストの上限Ｂとを入力として、コスト制約を満たす部分集合Ｓの集合Ｆのうち、スコアが最大となる部分集合Ｓｍａｘを、貪欲法を用いて探索することを繰り返し、既に探索された部分集合Ｓｍａｘのスコアと近似精度を表すパラメータαとを用いて定められるスコアの上限に対する、新たに探索された部分集合Ｓｍａｘのスコアの比が、近似精度を表すパラメータα以上となったときの部分集合Ｓｍａｘを、劣モジュラ最大化問題の近似解として出力することにより、高速に劣モジュラ最大化問題を解くことができる。
【００７２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００７３】
１０   入力部
２０   演算部
３０   主制御部
３２   構築部
３４   状態空間木
３６   探索部
３８   計算部
４０   逐次実行部
４２   停止条件判定部
５０   出力部
１００ 最適化装置
【図１】
2019079237.tif 000020
【図２】
2019079237.tif 000021
【図３】
2019079237.tif 000022
【図４】
2019079237.tif 000023
【図５】
2019079237.tif 000024
【図６】
2019079237.tif 000025
【図７】
2019079237.tif 000026