(57)【要約】【課題】全数探索または動的計画法よりも大幅に平均探索時間と最悪探索時間を短くすることができ、かつ、解なしの判断を確実に行う消込処理装置、消込処理方法および消込処理プログラムを提供する。【解決手段】ＧＡを用いた消込処理装置１は、ＧＡを用いた消込処理部２１と、知識データを格納する知識データベース２２とを有する。ＧＡを用いた消込処理部２１は、各請求項目に遺伝子座を対応させ、染色体の定義長は消込処理における全請求件数に一致させ、遺伝子座の遺伝子の値が所定値の場合に入金がされ、入金された請求項目に対応する請求金額の合計を染色体が示す入金金額とし、染色体に対応した請求金額の合計額と入金金額の差額の絶対値が小さいほど遺伝的操作における評価値を高くし、全請求件数に対して、交叉および選択の遺伝的操作を行って評価値の高い個体を次世代に引き継ぐ局所探索を実行し、組合せ解が見つかった場合、消込可能と判定する。【選択図】図１８
2015232795.tif 000002
【特許請求の範囲】
【請求項１】
請求データと入金データとを照合して、入金済みの請求データを逐次消し込んでいく消込処理装置であって、
各請求項目に遺伝子座を対応させ、染色体の定義長を消込処理における全請求件数に一致させ、
前記遺伝子座の遺伝子の値が所定値の場合に入金がされたとし、入金された請求項目に対応する請求金額の合計を前記染色体が示す入金金額とし、
前記染色体に対応した請求金額の合計額と入金金額を差額の絶対値が小さいほど遺伝的操作における評価値を高くし、
全請求件数に対して、交叉および選択の遺伝的操作を行って前記評価値の高い個体を次世代に引き継ぐ局所探索を実行し、
組合せ解が見つかった場合、消込可能と判定する処理部を備えること、
を特徴とする消込処理装置。
【請求項２】
前記処理部は、
同一の入金条件の下、与えられた入金額を満たす複数の組合せ解が存在する場合、複数の組合せ解の中の１つの組合せ解が求まったとき、消込処理終了と判定すること、
を特徴とする請求項１に記載の消込処理装置。
【請求項３】
前記処理部は、
最適解となる入金額と、探索途中の評価値の高い組合せ解の合計金額である準最適解との差が所定値以下の場合、前記準最適解と組合せ件数のほぼ等しい他の組合せを探索する局所探索を実行すること、
を特徴とする請求項１または請求項２に記載の消込処理装置。
【請求項４】
前記処理部は、
遺伝的操作の途中でエリート個体とハミング距離の等しい個体が複数生成された場合、最も評価値の高い個体を次世代に引き継ぐ、ハミング距離を適用した局所探索を実行すること、
を特徴とする請求項１乃至請求項３のいずれか一項に記載の消込処理装置。
【請求項５】
前記処理部は、
全数探索または動的計画法により消込処理を実行する全数探索処理部と、
遺伝的アルゴリズムを用いた消込処理と前記全数探索処理とを所定条件または所定タイミングで切り替える切替部と、をさらに備えること、
を特徴とする請求項１乃至請求項４のいずれか一項に記載の消込処理装置。
【請求項６】
前記処理部は、
所定の打切り時間を設定し、
前記打切り時間内において遺伝的アルゴリズムを用いた消込処理を完了すること、
を特徴とする請求項１乃至請求項５のいずれか一項に記載の消込処理装置。
【請求項７】
前記処理部は、
遺伝的アルゴリズムを用いた消込処理を実行し、所定時間内で組合せ解が解が求まらなかったものに対して、当該消込処理実行により削減された件数で全数探索または動的計画法により消込処理を実行すること、
を特徴とする請求項１乃至請求項６のいずれか一項に記載の消込処理装置。
【請求項８】
前記処理部は、
請求件数と請求に対する探索回数との積に基づいて、遺伝的アルゴリズムを用いた消込処理または動的計画法による消込処理のいずれかを選択し、選択した消込処理により消込処理を実行すること、
を特徴とする請求項１乃至請求項７のいずれか一項に記載の消込処理装置。
【請求項９】
消込処理の件数を削減するための知識データを格納する知識データ格納部を備え、
前記処理部は、
遺伝的アルゴリズムを用いた消込処理を実行し、求めた組合せ解に基づいて前記知識データを更新し、
更新した前記知識データを検索の初期値として用いて、遺伝的アルゴリズムを用いた消込処理、全数探索または動的計画法による消込処理を実行すること、
を特徴とする請求項１乃至請求項８のいずれか一項に記載の消込処理装置。
【請求項１０】
前記選択は、ルーレット選択またはトーナメント選択のいずれか、前記交叉は、一点交叉、二点交叉、または一様交叉のいずれかであること、
を特徴とする請求項１に記載の消込処理装置。
【請求項１１】
請求データと入金データとを照合して、入金済みの請求データを逐次消し込んでいく消込処理装置の消込処理方法であって、
前記消込処理装置の処理部は、
各請求項目に遺伝子座を対応させ、染色体の定義長を消込処理における全請求件数に一致させ、
前記遺伝子座の遺伝子の値が所定値の場合に入金がされたとし、入金された請求項目に対応する請求金額の合計を前記染色体が示す入金金額とし、
前記染色体に対応した請求金額の合計額と入金金額を差額の絶対値が小さいほど遺伝的操作における評価値を高くし、
全請求件数に対して、交叉および選択の遺伝的操作を行って前記評価値の高い個体を次世代に引き継ぐ局所探索を実行し、
組合せ解が見つかった場合、消込可能と判定すること、
を特徴とする、前記消込処理装置の消込処理方法。
【請求項１２】
請求データと入金データとを照合して、入金済みの請求データを逐次消し込んでいく消込処理装置の処理部に対し、
各請求項目に遺伝子座を対応させ、染色体の定義長を消込処理における全請求件数に一致させ、
前記遺伝子座の遺伝子の値が所定値の場合に入金がされたとし、入金された請求項目に対応する請求金額の合計を前記染色体が示す入金金額とし、
前記染色体に対応した請求金額の合計額と入金金額を差額の絶対値が小さいほど遺伝的操作における評価値を高くし、
全請求件数に対して、交叉および選択の遺伝的操作を行って前記評価値の高い個体を次世代に引き継ぐ局所探索を実行し、
組合せ解が見つかった場合、消込可能と判定する処理を実行させること、
を特徴とする、前記消込処理装置を機能させるための消込処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、消込処理装置、消込処理方法および消込処理プログラムに関する。
【背景技術】
【０００２】
売掛金の回収に係る業務の一つとして、請求内容の記載された請求データと、入金内容の記載された入金データとを照合して、入金済みの請求データを逐次消し込んでいく請求データの消込処理が行われている。消込処理とは、売掛金などが入金された時に、明細書と照らし合わせて売掛金リストから対応する項目を消しながら、入金の遅延や売掛残高が適正か否かを確認する処理である。この場合、日付や請求先情報、支払元情報を用いて、消し込みのための突き合わせを行う。
【０００３】
特許文献１には、請求先と入金元が一致する請求明細データや入金明細データ中に含まれる請求額と入金額とに対して、予め決められた幾つかのパターンに従って、金額を合算して消込処理を行う消込処理装置が記載されている。特許文献１に記載の装置では、消込対象となる入金明細データの合計額と、この入金明細データの直近の入金日より以前の特定の期間の請求日付の請求明細データの合計額とを突合する。そして、両合計額が一致、またはその金額の差が予め設定された誤差範囲内であれば消込処理を行う。
【０００４】
請求書１件ごとに入金が行われる場合は、簡単に自動化が可能である。しかし、実際には、請求書および入金は、単純な１対１の対応関係を有していない。実際には、銀行振込手数料を節約する、等の理由から、企業は、複数の請求書の取引を１度にまとめて支払う（銀行口座に入金する）ことが多い。企業間の取引は、振込手数料を抑えるために１００件を超える請求を纏めて入金することが一般的である。この場合、部署や営業担当者により取り纏めの時期が微妙にずれて、請求金額合計額と入金額が不一致となることが少なくない。したがって、消込処理では、入金額を基に対応する請求金額の内訳を求める必要があり、基本的に部分和問題として定義することができる。ここで、部分和問題は、ＮＰ完全問題であることが既に示されており、動的計画法（ＤＰ：Dynamic Programming）を用いて解けることが分かっている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−１８５５８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、ＤＰでは、入金額の大きさに比例した大量のメモリサイズが必要となるので、企業間の取引で扱う高額な入金の場合には、ＤＰ法を適用することができない。また、外貨に関して、ＤＰは一般的に実数を扱うのが苦手である。例えば（$１５．２５など）ドルの場合は、セントの部分は小数点以下で記述され、ＤＰではこのままでは適用することができない。この場合、１００倍して整数に変換してから処理する必要がある。したがって、元々、大きな入金額に対して処理できない場合が多いのに、さらに桁数が増えてしまう問題がある。
以上のことから、全数探索プログラムや複数の経理関係者による人手作業で入金の内訳を探し出す必要が生じている。この場合、全数探索プログラムでは、一晩中プログラムを実行しても解が求まらない場合がある。また、人手作業では、期末などの特定の時期にのみ大きな人的負荷が集中するなどの問題が生じる。
【０００７】
そこで、本発明は、全数探索または動的計画法よりも大幅に平均探索時間と最悪探索時間を短くすることができ、かつ、解なしの判断を確実に行うことができる消込処理装置、消込処理方法および消込処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するため、本発明の消込処理装置は、請求データと入金データとを照合して、入金済みの請求データを逐次消し込んでいく消込処理装置であって、各請求項目に遺伝子座を対応させ、染色体の定義長を消込処理における全請求件数に一致させ、前記遺伝子座の遺伝子の値が所定値の場合に入金がされたとし、入金された請求項目に対応する請求金額の合計を前記染色体が示す入金金額とし、前記染色体に対応した請求金額の合計額と入金金額を差額の絶対値が小さいほど遺伝的操作における評価値を高くし、全請求件数に対して、交叉および選択の遺伝的操作を行って前記評価値の高い個体を次世代に引き継ぐ局所探索を実行し、組合せ解が見つかった場合、消込可能と判定する処理部を備えることを特徴とする。
その他の手段については、発明を実施するための形態のなかで説明する。
【発明の効果】
【０００９】
本発明によれば、全数探索または動的計画法よりも大幅に平均探索時間と最悪探索時間を短くすることができ、かつ、解なしの判断を確実に行うことができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の原理説明の消込処理問題の探索空間形状例を示す図である。
【図２】本発明の原理説明の消込処理問題の探索空間形状例を示す図である。
【図３】本発明の原理説明のハミング距離を考慮した局所探索の例を説明する図である。
【図４】本発明の原理説明の消込処理問題を対象とした染色体の定義の一例を示す図である。
【図５】本発明の原理説明の局所探索を適用した場合のＧＡのフローチャートである
【図６】本発明の原理説明の評価実験の環境を示す図である。
【図７】本発明の原理説明のＧＡの実行パラメータを示す図である。
【図８】本発明の原理説明の請求件数Ｎを変えて全数検索とＧＡの求解までの実行時間を比較した結果をテーブルにして示す図である。
【図９】本発明の原理説明の全請求件数ＮとＧＡの実行時間を比較して示すグラフである。
【図１０】本発明の原理説明のテストデータＡを用いた場合の実行時間と世代数の比較結果を表にして示す図である。
【図１１】本発明の原理説明の世代数と最大評価値を比較して示す図である。
【図１２】本発明の原理説明の局所探索法の違いによる収束性を比較して示す図である。
【図１３】本発明の原理説明のテストデータＢを用いた場合の実行時間と世代数の比較結果を表にして示す図である。
【図１４】本発明の原理説明の世代数と最大評価値を比較して示す図である。
【図１５】本発明の原理説明の局所探索法の違いによる収束性を比較して示す図である。
【図１６】本発明の原理説明の全請求件数Ｎを５０に増やしたテストデータＣを用いた場合の実行時間と世代数の比較結果を表にして示す図である。
【図１７】本発明の原理説明の世代数と最大評価値を比較して示す図である。
【図１８】本発明の実施形態に係るＧＡを用いた消込処理装置の構成を示す図である。
【図１９】本実施形態の債権請求情報マスタの一例を示す図である。
【図２０】本実施形態の入金情報マスタの一例を示す図である。
【図２１】本実施形態の請求入金マッチング処理を示すフローチャートである。
【図２２】本実施形態の検索結果出力画面の一例を示す図である。
【図２３】本実施形態の請求件数Ｎに対する打切り時間（打切り世代数）を設定するフローチャートである。
【図２４】本実施形態のＧＡを用いた消込処理（その１）を示すフローチャートである。
【図２５】本実施形態のＧＡを用いた消込処理（その２）を示すフローチャートである。
【図２６】本実施形態のＧＡを探索の初期値として使用する消込処理を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以降、本発明を実施するための形態（「本実施形態」という）を、図等を参照しながら詳細に説明する。また、本実施形態を説明するための全図において、同一部には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００１２】
（原理説明）
まず、本発明の基本的な考え方について説明する。
本発明者らは、消込処理に遺伝的アルゴリズム（Genetic Algorithm，ＧＡ）などの進化計算を適用することを見出した。部分和問題は、ナップサック問題（Knapsack problem）の特殊な例であり、ＤＰに比べてＧＡは、メモリサイズを抑えることができ、およびＧＰＵ（Graphics Processing Unit）などのメニーコア環境で並列化により高速化が期待できる。特に、大きな金額のやり取りが発生する企業での消込処理にＧＡなどの進化計算が好適に使用できることが分かった。また、本発明は、ＧＡ用いた消込処理に、ハミング距離を考慮した局所探索の併用することで、精度向上を図る。
【００１３】
[消込処理問題へのＧＡ適用]
消込処理における全請求件数（文脈によっては、請求件数という）をＮ、入金件数をｋ、入金金額をＳ、ＧＡの個体数をＰ、一世代あたりの処理時間をＴ１、世代数をＧとし、扱うデータはｉｎｔ型とする。ここで、「世代数」とは、親個体群から遺伝的操作によって子個体群を作成する繰り返し回数をいう。
【００１４】
（１）性能比較
まず、全数探索、ＤＰ、ＧＡに関して実行時間する比較を行う。
全数探索の場合、最悪実行時間ＴＡＬＬは、入金件数ｋが未知数であるため、以下に示す式（１）で示される。
【００１５】
【数１】
2015232795.tif 000003
【００１６】
全数探索の場合の実行時間は、請求件数Ｎの値の増加に従って指数関数的に増加し、Ｎの値によっては丸一日計算機を動かしても解が求まらないこと珍しくない。
ＤＰでは、一つの請求に対しＳ回の探索が必要となり、各請求すべてを探索する必要がある。ＤＰの実行時間ＴＤＰは、式（２）となる。
【００１７】
ＴＤＰ＝Ｎ×Ｓ                          …式（２）
【００１８】
式（１）と式（２）を比較すると、Ｎの値が大きくなるに従って、ＤＰは全数探索法に比べてより高速解を求められることが分かる。一方、実行時間が入金金額Ｓに比例することから、企業間の取引でやり取りされる高額な入金額の場合には却って全数探索よりも性能が低下する場合もある。例えば、Ｎ＝３０、Ｓ＝１０９の場合ＴＡＬＬとＴＤＰの値は、以下の式（３）のようになり、ＤＰは全数探索の３０倍も遅くなってしまう。
【００１９】
【数２】
2015232795.tif 000004
【００２０】
ＧＡでは、最適解が求まる世代数回処理を繰り返す。一世代あたりの処理時間はＴ１とすると、ＧＡの実行時間ＴＧＡは、式（４）となる。
【００２１】
ＴＧＡ＝Ｔ１×Ｐ×Ｇ                      …式（４）
【００２２】
式（４）に示すように、ＧＡの実行時間ＴＧＡは、Ｎの値が大きくなるに従って全数探索法に比べより高速解を求められ、かつＳの値に依存しないことから高額な入金であってもＤＰのように性能が低下しないことが分かる。但し、最適解を求めるために必要なＰやＧの値は、Ｎの値に依存するため、計算機シミュレーョンによる評価も必要である。
【００２３】
（２）メモリサイズの比較
次にプログラムの実行に必要なメモリサイズの比較を行う。
全数探索では、全請求件数分の長さ配列が必要となる。ｉｎｔ型の配列場合は、１マスのメモリ要域は４ビットであるから、４×Ｎビット分のメモリ領域が必要となる。
【００２４】
一方、ＤＰでは、入金金額分の長さの配列が必要となるため、式（５）に示すように、基本的には４×Ｎ×Ｓビット分のメモリ領域を必要とする。ＤＰでは再帰法などを用いた工夫で必要なメモリサイズを４×Ｓビットまで削減できる場合もある。しかし、企業間の取引では、数百億円を超える入金額の場合も存在し、この場合に必要な配列サイズは４０ＧＢを超えるため現実的に実装が困難である。一般的なＣコンパイラのメモリ制限は、２ＧＢであるため、何らかの工夫が必要となる。
【００２５】
４×Ｎ×Ｓ                              …式（５）
【００２６】
すなわち、ＤＰは、限られた範囲のＳおよびＮの値以外には消込処理への適用が困難である。
一方、ＧＡでは、長さＮの配列を、作業用の領域を考えても、２×Ｐ個分用意するだけでよいため、入金額の大きさに依存せず、必要とする記憶容量は式（６）となる。
【００２７】
８×Ｎ×Ｐ                              …式（６）
【００２８】
[ハミング距離を考慮した局所探索]
図１および図２は、消込処理問題の探索空間形状例を示す図であり、図１は、Ｎ＝６，ｋ＝３の場合、図２はＮ＝８，ｋ＝４の場合の例である。横軸は、組合せ種類（ＩＤ番号）を示し、縦軸は、最大値が１．０になるよう正規化した評価値を示している。
各請求金額は、乱数を用いて１０桁から桁から１２桁の整数を生成した。
【００２９】
図１および図２に示すように、本発明者らは、消込処理問題が、複雑な形状を持つ多峰性（剣山状）の探索であること、および全請求件数をＮが増加すると多峰性の山の数が急激に増加して解の探索が極端に難くなる問題であることを見出した。また、与えられた入金額を満す複数の組合せ解が存在する場合もある。
したがって、Niching（永田裕一．均等に個体を分散化する適応的ニッチングGAの提案.人工知能学会誌，24巻1号pp. 92-103，2006参照）などの手法を用いたＧＡの探索精度向上可能性が考えられる。
【００３０】
一方、消込処理では、同一の入金条件の下、与えられた入金額を満たす複数の組合せ解が存在する場合でも、その中の１つの組合せ解が求まればよい。入金額という単なる数字の羅列は、組合せ候補を特定する「この部分のお金」という情報を有さない。したがって、複数存在する組合せの中でどの組合せが正しいかは、入金者に直接聞くしか方法がないからである。ここで、ＧＡの探索精度を向上させるための第一段として、局所探索機能を併用した探索精度向上を考える。特に、消込処理では、最適解（入金額）と探索途中の準最適解（評価値の高い組合せ解の合計金額）との差が大きくない場合には、準最適解の組合せ件数と入金件数がほぼ同等な件数になっている可能性が高いと考え、準最適解と組合せ件数のほぼ等しい他の組合せを探索する局所探索を実現する。
【００３１】
図３は、ハミング距離を考慮した局所探索の例を説明する図である。
ＧＡでは一つの解を一つの個体として扱う。そして、複数の個体からなる個体群を作り、この個体群を基準として探索する。なお、個体群に適用する操作には、交叉、突然変異、および選択の３種の遺伝演算子が用いられる。図３では、解をビット列として表現し、染色体（記号列）は各遺伝子座からなる。「遺伝子座」とは、遺伝子（ここでは２値（１，０））が入る染色体上の場所である。図３では、染色体の各遺伝子座がそれぞれ請求項目に対応している。
【００３２】
図３の符号ａに示すように、交叉、突然変異、または選択の遺伝子操作を行う。そして、図３の符号ｂに示すように、この遺伝的操作の途中でエリート個体とハミング距離の等しい個体を、例えば３個生成する。
図３の符号ｃに示すように、ハミング距離の等しい個体の中で１番評価値の高い個体を次世代個体群に引き継ぐことで、ハミング距離を考慮した局所探索を行う。
なお、ハミング距離以外の距離を局所探索に適用することも可能である。
【００３３】
[消込処理のためのＧＡの設計]
（１）染色体の定義染色体の定義
図４は、消込処理問題を対象とした染色体の定義の一例を示す図である。
図４（ａ）（ｂ）に示すように、各請求項目（「請求１ ￥５００」，「請求２ ￥３００」，…）にそれぞれ異なる遺伝子座を対応させる。染色体の定義長は、全請求件数と一致させる。遺伝子座の値が１になっている部分の請求に対応した入金がされたと考える。図４では、請求項目２の「請求２ ￥３００」、請求項目３の「請求３ ￥２５０」、請求項目５の「請求５ ￥６２０」に対応する遺伝子座の値が「１」になっている。このため、図４（ｃ）に示すように、「請求２ ￥３００」、「請求３ ￥２５０」、「請求５ ￥６２０」にそれぞれ対応した￥３００円、￥２５０円、￥６２０円の金額を合計した￥１１７０円が本染色体の示す入金額となる。
【００３４】
（２）評価関数
遺伝的操作における評価値は、染色体に対応した請求金額の合計額と入金金額との差額の絶対値が小さいほど評価が高いと考えるのが妥当である。一方、単純に請求金額の合計と入金金額の差額の絶対値の逆数を評価値として設定すると、図１および図２に示した探索空間の多峰性の山の起伏が極端に大きくなってしまう場合がある。そこで、例えば０から１の間の値に正規化した式（７）に示す評価関数を定義する。
【００３５】
ｆｅ＝ｆｐ／（ｆｐ＋ｆｓ）                              …式（７）
【００３６】
ここで、ｆｐは、染色体に対応した請求金額の合計である。ｆｓは、ｆｐと入金金額との差の絶対値を示している。ｆｅ＝１になった個体が入金額に対応する個体であり、最適解となる。
【００３７】
（３）選択と交叉方法
本発明者らは、ルーレット選択、トーナメント選択の２種類の選択方法と、一点交叉、二点交叉、一様交叉の３種類の交叉方法の、６種類の組合せに関して、交叉率、突然変異率および全請求件数をパラメータとして予備実験を行った。その結果、ルーレット選択と一様交叉の合せの時に、全請求件数Ｎに依存せず同一の交叉率、突然変異率で安定した収束性が得られた。このため、以下、ルーレット選択と一様交叉の組合せで評価実験を行った。
【００３８】
（４）ハミング距離を考慮した局所探索
図５は、局所探索を適用した場合のＧＡのフローチャートである
図５に示すように、ステップＳ１で遺伝的操作における評価を行い、評価値が所定値以上の場合（ステップＳ１：Ｙｅｓ）、最適解が得られたと判断して本フローを終了する。評価値が所定値より小さい場合（ステップＳ１：Ｎｏ）、通常のＧＡと同じく、交叉、突然変異、および選択の遺伝演算子による遺伝操作を行う（ステップＳ２〜ステップＳ４）。
【００３９】
交叉、突然変異、および選択まで行った後に、ステップＳ５で局所探索を行い（ステップＳ１乃至ステップＳ５参照）、ステップＳ１に戻る。突然変異を施した個体と幾つかの局所探索点中で最大の評価値の個体を次世代の個体として遺伝的操作を行う。
本ハミング距離を考慮した局所探索は、ハミング距離が０の場合の探索と、１の場合の探索の２種類の方法で実験を行い、各請求金額の桁数のばらつきとの関係を調べる。
【００４０】
[評価実験]
（１）評価方法
図６は、評価実験の環境を示す図、図７は、ＧＡの実行パラメータを示す図である。
図７に示すように、ＧＡの実行パラメータは、選択方法や交叉方法を決定する際の予備実験を通して決定している。プログラム言語は、将来的にＧＰＵなどのメニーコア環境を用いた高速化想定してＣ言語を用いて開発した。
【００４１】
ＤＰは、請求件数Ｎと入金金額Ｓの制限があり、企業で消込処理に適用するのは実用上無理がある。このため、ここではまず全数探索とＧＡの求解まで実行時間を比較評価する。また、ハミング距離を考慮した局所探索の効果を調査検討するために、単純ＧＡ、また単純ＧＡに局所探索としてMultiple Offspring Sampling（ＭＯＳ）を追加した場合、さらに単純ＧＡにハミング距離を考慮した場合の求解まで実行時間と世代数の比較を行う。
【００４２】
全数探索とＧＡの比較では、各請求金額の桁数が８〜１６桁までの数値を正規乱数で生成したテストデータを用いて、全請求件数Ｎを１０から５０まで変化させて実験を行う。入金件数ｋは乱数で設定する。
【００４３】
ハミング距離を考慮した局所探索の効果を調査する実験では、テストデータは以下に示す各請求金額の桁数が大体揃っているデータＡと桁数がばらついているデータＢの２種類を準備して評価行う。各請求金額は正規乱数を用いて生成している。
【００４４】
・テストデータＡ
各請求金額：１１〜１２桁
全請求件数：Ｎ＝３０
入金件数：ｋ＝２０
入金額Ｓ：９,９３３,６２４,２６７,５７０
【００４５】
・テストデータＢ
各請求金額：８〜１２桁
全請求件数：Ｎ＝３０
入金件数：ｋ＝２０
入金額Ｓ：３,０３１,００５,４５７,５４６
【００４６】
（２）実験結果
<全数探索とＧＡの比較実験>
図８は、請求件数Ｎを変えて全数検索とＧＡの求解までの実行時間を比較した結果をテーブルにして示す図である。全数探索は、Ｎ＝３０までは１回の実測値、Ｎ＝４０以上はＮ＝３０の時の値を基に前記式（１）から算出した理論上の最悪値である。
【００４７】
図８に示すように、ＧＡは、２０回実行して全最適解に辿り着いており、２０回の平均時間を記録している。Ｎの値が２０に満たない場合には、全数探索の方が早く最適解を求める場合もあるが、ＧＡの場合の実行時間も実用上は問題にならない値である。Ｎが３０を超えると、全数探索の理論上最悪値は、急激に実行時間が増加して、Ｎ＝４０では３５０時間、Ｎ＝５０では３６０万時間必要となる。一方、ＧＡの場合は、Ｎ＝４０では平均２分強、最長７分弱であり、Ｎ＝５０では平均７分弱、最長１３分弱である。すなわち、ＧＡは全数探索に比べてＮ＝４０では約３,０００倍、Ｎ＝５０では約１６８万倍高速に最適解を求める結果となった。
【００４８】
次に、全請求件数Ｎに関する実行時間のオーダ傾向を観測した。
図９は、全請求件数ＮとＧＡの実行時間を比較して示すグラフである。横軸に、請求件数を、縦軸に常用対数を取った処理時間値を示す。図９に示すように、全数探索は、Ｎが大きくなるにつれ指数関数的に実行時間が増加する。これに対し、ＧＡの実行時間は、ほぼＮに比例していることが分かった。
【００４９】
<ハミング距離を考慮した局所探索>
≪テストデータＡを用いた場合≫
図１０は、前記テストデータＡを用いた場合の実行時間と世代数の比較結果を表にして示す図である。なお、世代とは、交叉、突然変異、または選択の遺伝子操作を個体群に一度適用する期間をいう。
【００５０】
図１０は、ＧＡと、ＧＡに局所探索としてＭＯＳを追加した場合（ＧＡ＋ＭＯＳ）と、ＧＡにハミング距離を考慮した局所探索を追加した場合のうちハミング距離を０に設定した場合（ＧＡ＋ＨＭ０）と、ＧＡにハミング距離を考慮した局所探索を追加した場合のうちハミング距離を１に設定した場合（ＧＡ＋ＨＭ１）とのそれぞれにおいて、求解までの平均実行時間（秒）、ワースト実行時間（最大実行時間）（秒）、平均世代数、およびワースト世代数（最大世代数）の比較結果を示している。図１０の表内の数値は、５０回実行した平均を示しており、いずれの場合も全て最適解に辿り着いている。
【００５１】
次に、収束過程を比較するために、世代数と最大評価値の関係について説明する。
図１１は、世代数と最大評価値を比較して示す図である。図１１は、図１０の実行時間と世代数の比較結果を用いている。
前記図１０に示すように、ＧＡに局所探索としてＭＯＳを追加した場合は、平均実行時間で０．９倍、最大実行時間で１．４倍早く解に辿り着いている。また、ハミング距離を考慮し局所探索を追加した場合は、平均実行時間で３．１倍、最大実行時間で３．８倍早く解に辿り着いている。また、図１１に示すように、局所探索を追加することにより解に辿り着くまでの世代数が大きく削減できること分かる。
【００５２】
次に、局所探索法の違いよる収束能力をより詳しく観測するために、局所探索を追加した場合に関してのみ世代数と最大評価値の関係について説明する。
図１２は、局所探索法の違いによる収束性を比較して示す図である。図１２は、前記テストデータＡを用いた場合の例である。
図１２に示すように、ＭＯＳに比べてハミング距離を考慮した局所探索同士の比較では、ハミング距離を０に設定した場合の方が僅かに早く解に辿り着いていることが分かる。
【００５３】
≪テストデータＢを用いた場合≫
図１３は、前記テストデータＢを用いた場合の実行時間と世代数の比較結果を表にして示す図である。
図１３は、ＧＡと、ＧＡに局所探索としてＭＯＳを追加した場合（ＧＡ＋ＭＯＳ）と、ＧＡにハミング距離を考慮した局所探索を追加した場合のうちハミング距離を０に設定した場合（ＧＡ＋ＨＭ０）と、ＧＡにハミング距離を考慮した局所探索を追加した場合のうちハミング距離を１に設定した場合（ＧＡ＋ＨＭ１）とのそれぞれにおいて、求解までの平均実行時間（秒）、ワースト実行時間（最大実行時間）（秒）、平均世代数、およびワースト世代数（最大世代数）の比較結果を示している。図１３の表内の数値は、５０回実行した平均を示しており、いずれの場合も全て最適解に辿り着いている。
【００５４】
次に、収束過程を比較するために、世代数と最大評価値の関係について説明する。
図１４は、世代数と最大評価値を比較して示す図である。図１４は、図１３の実行時間と世代数の比較結果を用いている。
前記図１３に示すように、ＧＡに局所探索としてＭＯＳを追加した場合は、平均実行時間で１．５倍、最大実行時間で１．５倍早く解に辿り着いている。また、ハミング距離を考慮し局所探索を追加した場合は、平均実行時間で４．８倍、最大実行時間で４．３倍早く解に辿り着いている。また、図１４に示すように、局所探索を追加することにより解に辿り着くまでの世代数が大きく削減できる傾向は、テストデータＡの場合（図１０および図１１参照）と同一であった。
【００５５】
また、世代数と最大評価値の関係では、入金金額のオーダを揃えたテストデータＡを用いた場合（図１０および図１１参照）よりも平均実行時間は約１００倍遅くなり、平均世代数も同様に約１００倍大きな値となった。
【００５６】
次に、局所探索法の違いよる収束能力をより詳しく観測するために、局所探索を追加した場合に関してのみ世代数と最大評価値の関係について説明する。
図１５は、局所探索法の違いによる収束性を比較して示す図である。図１５は、前記テストデータＢを用いた場合の例である。
図１５に示すように、ＭＯＳに比べてハミング距離を考慮した局所探索が早く収束する傾向は、テストデータＡの場合（図１０および図１１参照）と同様であるが、立ち上りの早さはＭＯＳの方が優れていた。ハミング距離を考慮した局所探索同士の比較では、逆にハミング距離を１に設定した場合の方が１．９倍早く解に辿り着く結果となった。
【００５７】
（３）考察
上述したように、全数探索の処理時間は、全請求件数Ｎに対して指数関数的に増加していき、ＧＡの処理時間はほぼＮに比例して増加していった。これはＧＡの配列長はＮであるから、Ｎが大きくなると１世代あたりの処理時間がこれに伴って大きくなるためであると考えられる。但し、解にたどり着くまでの世代数も関連するためＮが２倍になっても処理時間は２倍よりも大きくなり、単純にＮには比例しない。また、ＧＡではワースト実行時間と比較すると２〜４倍処理速度に差がでている。しかし、Ｎ＝５０でもＧＡの平均は約７分、ワースト実行時間でも約１０分程度で処理が終了し、全数探索に比べて現実的な処理時間となった。したがって、本発明のＧＡの消込処理問題へ適用は有効であると考えられる。
【００５８】
また、上記実験結果より、ＧＡに局所探索の機能を追加することで、３．８倍程度の高速化が図られ、それが有効であること分かる。また、本発明の一態様であるハミング距離を考慮した局所探索は、ＭＯＳに比べて、テストデータＢでは上がりは遅いものの、３．１倍程度早く最適解に収束している。これは評価値が高くなるに従って、本発明の局所探索の効果が有効に働いているためと考えられる。
ハミング距離を考慮した局所探索同士の比較では、請求金額のオーダがある程度揃っている場合にハミング距離を０に設定した局所探索の効果が高い。
【００５９】
また、評価値の立ち上がりは、通常の局所探索の方が速いが、評価値が高くなるとハミング距離を考慮した局所探索の方が早く収束していることが分かる。評価値が高くなるにつれその世代で解の個体は、最適解に近づいているため、評価の高い個体とハミング距離の小さい個体を次世代に残し考慮することで解に辿り付く世代数が少なくなったと考えられる。
【００６０】
次に、請求金額の桁数がばらついているテストデータＢを用いてハミング距離を考慮した局所探索の効果が、テストデータＡを用いた時ほど顕著でなかった原因を調査する。このため、全請求件数Ｎを５０に増やしたテストデータＣを用いた追加実験を行った。
【００６１】
≪テストデータＣを用いた場合≫
図１６は、全請求件数Ｎを５０に増やしたテストデータＣを用いた場合の実行時間と世代数の比較結果を表にして示す図である。テストデータＣの各請求金額の桁数は、８桁〜１３桁であり、入金件数ｋは１８、入金額Ｓの桁数は１１桁である。ＧＡと局所探索を加えた方式の比較を図１６に、世代数と最大評価値の関係を下記図１７に示す。
【００６２】
図１７は、世代数と最大評価値を比較して示す図である。図１７は、図１６の実行時間と世代数の比較結果を用いている。
図１６および図１７に示すように、ＧＡに局所探索の機能を加えることで収束を早める効果があること、およびＭＯＳに比べて提案するハミング距離を考慮した局所探索が効果的である傾向は変わらず、効果の度合が低下しているのが分かる。この理由として、全請求件数Ｎの値を増やしたことで、探索空間の大きさが指数関数的に増大し、相対的に局所探索の効果が低下したためと考えられる。この対策として、探索点の数を増やすこと、タブーサーチなどとの組合せより局所探索法の効率向上を図ることが考えられる。
【００６３】
また、評価時間の関係からＮ＝５０までに制限し、乱数で生成したテストデータで実験を行った。今後、Ｎが１００を超える場合も含めて実データによる検証が必要である。さらに、全請求件数Ｎが大きな値でも短時間で解を求めるためには、ＧＰＵなどのメニーコア環境での並列高速化が有効と考えられる。
【００６４】
本発明らは、ＧＡを用いた消込処理問題の解法を提案し、全数探索および動的計画法との比較からその有用性を示した。また、ハミング距離を考慮した局所探索法を併用することによる探索精度の向上を提案し、標準的なＧＡおよび標準的なＧＡに単純な局所探索を付加した場合との比較を、各請求金額の桁数が大体揃っているデータと桁数がばらついているデータの２種類を用いて行った。その結果、請求額金桁数がほぼ揃っている場合、あるいは評価値の値がある程度高くなると有効であることが示された。
【００６５】
（実施形態）
以下、上記基本的な考え方に基づいて本発明の実施形態に係るＧＡを用いた消込処理装置について説明する。
【００６６】
[構成]
図１８は、本発明の実施形態に係るＧＡを用いた消込処理装置の構成を示す図である。本実施形態は、合計金額を入金金額と突合し、入金済みの請求データを逐次消し込んでいく請求入金マッチング装置に適用した例である。
図１８に示すように、ＧＡを用いた消込処理装置の構成を説明する。ＧＡを用いた消込処理装置１は、請求データと入金データとを照合して、入金済みの請求データを逐次消し込んでいく消込処理装置である。ＧＡを用いた消込処理装置１は、一般的なコンピュータにより構成され、中央制御装置１１、例えばマウス、キーボードのような入力装置１２、例えばディスプレイのような出力装置１３、主記憶装置１４、補助記憶装置１５および通信装置１６を有している。これらの各装置は、バス１７によって相互に接続されている。ＧＡを用いた消込処理装置１は、ネットワーク４を介して、端末装置３と接続されている。
【００６７】
主記憶装置１４は、ＧＡを用いた消込処理部２１（処理部，全数探索処理部，切替部）と、消込処理の件数を削減するための知識データを格納する知識データベース（ＤＢ）２２（知識データ格納部）とを有する。ＧＡを用いた消込処理部２１はプログラムであり、知識データベース２２は消込処理の知識データを蓄積する。
補助記憶装置１５は、債権請求情報マスタ３１、入金情報マスタ３２、およびテンポラリマスタ３３を備える（いずれも詳細後記）。
【００６８】
本実施形態において、「○○部は」というように主体を記した場合は、中央制御装置１１が、そのプログラムを補助記憶装置１５から主記憶装置１４にロードしたうえで、そのプログラムの機能（詳細後記）を実現するのとする。
端末装置３もまた同様に、相互にバス１７で接続された、中央制御装置、入力装置、出力装置、主記憶装置、補助記憶装置および通信装置（図示せず）を有している。
【００６９】
<ＧＡを用いた消込処理部２１>
ＧＡを用いた消込処理部２１は、各請求項目に遺伝子座を対応させ、染色体の定義長を消込処理における全請求件数に一致させ、遺伝子座の遺伝子の値が所定値（例えば「１」）の場合に入金がされ、入金された請求項目に対応する請求金額の合計を染色体が示す入金金額とし、染色体に対応した請求金額の合計額と入金金額の差額の絶対値が小さいほど遺伝的操作における評価値を高くし、全請求件数に対して、交叉および選択の遺伝的操作を行って評価値の高い個体を次世代に引き継ぐ局所探索を実行し、組合せ解が見つかった場合、消込可能と判定する。ここで、上記選択は、ルーレット選択、トーナメント選択のいずれか、上記交叉は、一点交叉、二点交叉、または一様交叉のいずれかである。
【００７０】
ＧＡを用いた消込処理部２１は、同一の入金条件の下、与えられた入金額を満たす複数の組合せ解が存在する場合、その中の１つの組合せ解が求まったとき、消込処理終了と判定する。
【００７１】
ＧＡを用いた消込処理部２１は、最適解となる入金額と、探索途中の評価値の高い組合せ解の合計金額である準最適解との差が所定値以下の場合、準最適解と組合せ件数のほぼ等しい他の組合せを探索する局所探索を実行する。
【００７２】
ＧＡを用いた消込処理部２１は、遺伝的操作の途中でエリート個体とハミング距離の等しい個体が複数生成された場合、最も評価値の高い個体を次世代に引き継ぐ、ハミング距離を適用した局所探索を実行する。
【００７３】
ＧＡを用いた消込処理部２１は、全数探索または動的計画法により消込処理を実行する全数探索機能と、遺伝的アルゴリズムを用いた消込処理と全数探索処理とを所定条件または所定タイミングで切り替える切替機能と、をさらに備える。
【００７４】
ＧＡを用いた消込処理部２１は、所定の打切り時間を設定し、打切り時間内において遺伝的アルゴリズムを用いた消込処理を完了させる。
【００７５】
ＧＡを用いた消込処理部２１は、遺伝的アルゴリズムを用いた消込処理を実行し、所定時間内で組合せ解が解が求まらなかったものに対して、当該消込処理実行により削減された件数で全数探索またはＤＰにより消込処理を実行する。
【００７６】
ＧＡを用いた消込処理部２１は、請求件数と請求に対する探索回数との積に基づいて、ＧＡを用いた消込処理またはＤＰによる消込処理のいずれかを選択し、選択した消込処理により消込処理を実行する。
【００７７】
ＧＡを用いた消込処理部２１は、遺伝的アルゴリズムを用いた消込処理を実行し、求めた組合せ解に基づいて知識データを更新し、更新した知識データを検索の初期値として用いて、遺伝的アルゴリズムを用いた消込処理、全数探索または動的計画法による消込処理を実行する。
【００７８】
（債権請求情報）
図１９は、本実施形態の債権請求情報マスタの一例を示す図である。
図１９に沿って、債権請求情報マスタ３１を説明する。債権請求情報マスタ３１においては、債権ＩＤ欄１０１に記憶された債権ＩＤに関連付けて、債権発生日欄１０２には債権発生日が、金額欄１０３には債権金額が、請求先欄１０４には請求先が、債権発生原因欄１０５には債権発生原因が、継続性欄１０６には継続性フラグが、入金欄１０７には入金フラグが、請求ＩＤ欄１０８には請求ＩＤが、請求日欄１０９には請求日が、支払期日欄１１０には支払期日が、請求金額欄１１１には請求金額が記憶されている。なお、債権とは、債権者が債務者に対して一定の行為（給付）を請求することを内容とする権利いう。
【００７９】
債権ＩＤ欄１０１の債権ＩＤは、債権を一意に特定する識別子である。
債権発生日欄１０２の債権発生日は、債権が発生した年月日であり、通常は、商品または役務の引渡（提供）があった年月日である。
金額欄１０３の債権金額は、債権の金額である。
請求先欄１０４の請求先は、顧客の名称である。
債権発生原因欄１０５の債権発生原因は、債権が発生する原因となった取引を説明する文言である。
【００８０】
継続性欄１０６の継続性フラグは、同種の取引が反復的に行われることを示す「継続」またはそれ以外であることを示す「スポット」のうちのいずれかである。なお、「継続」債権には、同種かつ同額の債権だけではなく、債権金額自体は毎回変動するものの、提供される商品または役務１単位あたりの金額が固定されている同種の債権（例えば電力料金）が含まれるものとする。
入金欄１０７の入金フラグは、入金が終了したことを示す「済」またはそれ以外であることを示す「未」（初期値）のうちのいずれかである。
【００８１】
請求ＩＤ欄１０８の請求ＩＤは、請求（請求書）を一意に特定する識別子である。
請求日欄１０９の請求日は、請求書１が発行された年月日である。
支払期日欄１１０の支払期日は、請求金額が銀行口座に振り込まれるべき期日を示す年月日である。
請求金額欄１１１の請求金額は、１つの請求書１に記載されている個々の債権の金額の合計金額である。
【００８２】
（入金情報）
図２０は、本実施形態の入金情報マスタの一例を示す図である。
図２０に沿って、入金情報マスタ３２を説明する。入金情報マスタ３２においては、入金ＩＤ欄１２１に記憶された入金ＩＤに関連付けて、入金日欄１２２には入金日が、入金金額欄１２３には入金金額が、入金元欄１２４には入金元が記憶されている。
入金ＩＤ欄１２１の入金ＩＤは、請求書１を発行した企業の銀行口座に対して請求先である顧客から資金が入金される事象（単に「入金」とも呼ぶ）を一意に特定する識別子である。
入金日欄１２２の入金日は、入金があった年月日である。
入金金額欄１２３の入金金額は、入金された資金の金額である。入金金額は、必ずしも１つの債権金額または１つの請求金額に対応しているわけではない。
入金元欄１２４の入金元は、顧客の名称である。
【００８３】
以下、上述のように構成されたＧＡを用いた消込処理装置の動作について説明する。
図２１は、本実施形態の請求入金マッチング処理を示すフローチャートである。図２２は、本実施形態の検索結果出力画面の一例を示す図である。
ステップＳ１１において、ＧＡを用いた消込処理部２１は、債権請求情報マスタ３１から消込対象となる債権請求レコードの請求明細データを抽出する。
ステップＳ１２において、ＧＡを用いた消込処理部２１は、入金情報マスタ３２から消込対象となる入金レコードの入金金額を抽出する。
【００８４】
ステップＳ１３において、ＧＡを用いた消込処理部２１は、請求番号や支払番号等を照合キーとして、該照合キーに対応した債権請求レコードの請求明細データと入金レコードの入金金額を突合し、両者が一致した場合、債権請求レコードと入金レコードを消し込むＧＡを用いた消込処理を行う。ここで、「消し込む」とは、会計上、貸借対照表の借方と貸方とが対応した場合に、その借方と貸方とを対応させて消していく作業である。この場合、消込処理は、ある債権に対応する入金が確認できた場合に、上記債権請求レコードおよび入金レコードに対し、消込フラグを入力する処理である。消込フラグが立っていれば、該当レコードは消込処理がなされたと判断できる。ＧＡを用いた消込処理については、図２２および図２３により後記する。
【００８５】
なお、説明の便宜上、ステップＳ１３では、ＧＡによる消込処理について説明したが、後記するハイブリッド手法のように、ステップＳ１３において、全数探索（またはＤＰ）による消込処理を実行する場合もある。すなわち、ステップＳ１３においては、ＧＡによる消込処理と、全数探索またはＤＰによる消込処理の両方の場合を含んでいる。
【００８６】
ステップＳ１３において、ＧＡを用いた消込処理部２１は、ＧＡを用いた消込処理による解が見つかったか（すなわち、消込処理ができたか）否かを判定する。ＧＡを用いた消込処理による解が見つからない場合（ステップＳ１４“Ｎｏ”）、上記ステップＳ１３に戻る。
【００８７】
ＧＡを用いた消込処理による解が見つかった場合（ステップＳ１４“Ｙｅｓ”）、ステップＳ１５において、ＧＡを用いた消込処理２１は、全ての債権請求レコードと入金レコードに対してＧＡを用いた消込処理が完了したか否かを判定する。ここで、ＧＡを用いた消込処理では、解が見つかった場合、該当レコードについて消込処理ができたと判定できる。全ての債権請求レコードと入金レコードに対してＧＡを用いた消込処理が完了していない場合、上記ステップＳ１１に戻る。
【００８８】
全ての債権請求レコードと入金レコードに対してＧＡを用いた消込処理が完了した場合（ステップＳ１５“Ｙｅｓ”）、ステップＳ１６において、ＧＡを用いた消込処理部２１は、検索結果出力画面５１（図２２）を表示する。具体的には、ＧＡを用いた消込処理部２１は、第１に、出力装置１３に、検索結果出力画面５１を表示する。検索結果出力画面５１は、入金情報欄５２、該当債権欄５３、「この検索結果で確定する」ボタン５４および「他の組合せも検索する」ボタン５５を有する。
【００８９】
ＧＡを用いた消込処理部２１は、第２に、検索対象入金レコードの入金ＩＤ、入金日、入金金額および入金元を、入金情報欄５２に表示する。
ＧＡを用いた消込処理部２１は、第３に、ＧＡを用いた消込処理による「解」が見つかった債権請求情報マスタ３１のレコードを、該当債権欄５３に表示する。図２２では、このような組合せは１つだけ存在し、当該組合せは、４つの債権を含んでいる。ＧＡを用いた消込処理部２１は、そのような組合せごとに、１または複数の債権を分けて表示する。
【００９０】
ステップＳ１７において、ＧＡを用いた消込処理部２１は、検索を継続するか否かを判断する。具体的には、ＧＡを用いた消込処理部２１は、ユーザが「この検索結果で確定する」ボタン５４を押下するのを受け付けた場合（ステップＳ１７“Ｎｏ”）、まず、ユーザが、合計額が同じである複数の組合せのうちから１つを選択するのを受け付ける。次に、当該選択された組合せに含まれるすべての債権ＩＤを取得する。そして、取得した債権ＩＤを検索キーとして、債権請求情報マスタ３１（図１９）を検索し、該当したレコードの入金フラグを「済」として上書き更新し、処理を終了する。
【００９１】
一方、ユーザが「他の組合せも検索する」ボタン５５を押下するのを受け付けた場合（ステップＳ１７“Ｙｅｓ”）、ＧＡを用いた消込処理部２１は、ＧＡパラメータ設定を変更（あるいは、全数探索に移行）して上記ステップＳ１１に戻る。
その後、ＧＡを用いた消込処理部２１は、ステップＳ１１〜Ｓ１６の処理を繰り返す。全ての債権請求レコードと入金レコードに対してＧＡを用いた消込処理が完了した場合、ＧＡを用いた消込処理部２１は、繰り返し処理を抜け出し、処理を終了する。
【００９２】
このように、ＧＡを用いた消込処理は、現運用で使用している方式と比較して大きなメリットがある。例えば、ＧＡを用いた消込処理では、請求件数４０件の場合、全数探索（ワースト値）に比べて約２０，０００倍高速である。また、人手による試行錯誤での検索作業を削減可能である。本実施形態では、ＧＡを用いた消込処理において、下記の方法を導入することでより一層、ＧＡなどのメタヒューリスティック手法を用いた探索の実用性の向上を図る。
【００９３】
次に、ＧＡなどのメタヒューリスティック手法を用いた探索の詳細について説明する。
全数探索（またはＤＰ）は、最短探索時間が短い、時間がかかっても解が必ず見つかる、また複数の解があった場合にそれらの解が全部見つかる、という利点がある。一方で、全数探索（またはＤＰ）は、平均探索時間と最悪探索時間が問題となる。特に、入金金額や請求件数が増えると、平均探索時間と最悪探索時間が非常に長くなり、実用上使用が困難となる。
【００９４】
これに対し、ＧＡなどのメタヒューリスティック手法は、解なしの判断が困難である、また解が全部あることを保証することは困難であるものの、全数探索（またはＤＰ）よりも平均探索時間と最悪探索時間が格段に短いという特徴がある。特に、入金金額や請求件数が増えても、解が数分（長くても１０分程度）で見つかるので、全数探索（またはＤＰ）では代替が効かない程の実用上の利点がある。
【００９５】
本発明者らは、解が必ず見つかる全数探索（またはＤＰ）と、平均探索時間と最悪探索時間が格段に短いＧＡなどのメタヒューリスティック手法の、それぞれの特徴を活かしたハイブリッドシステムに想到した。すなわち、上記図２１のフローで述べたように、ＧＡを用いた消込処理の単独適用でも、現運用で使用している全数探索と比較して大きなメリット（例えば、請求件数４０件の場合、全数探索（ワースト）に比べて約２０，０００倍高速という効果を奏するが、これを下記のようにハイブリッド化することで、ＧＡなどのメタヒューリスティック手法の弱点（解なしの判断の困難）を補う。
【００９６】
<ハイブリッド：手法１>
手法１は、ＧＡなどのメタヒューリスティック手法による探索と全数探索（またはＤＰ）とを並列して運用する。具体的には、図２１のステップＳ１３において、ＧＡを用いた消込処理プログラムと、全数探索（またはＤＰ）による消込処理プログラムとを並列して実行する。ＧＡを用いた消込処理と全数探索（またはＤＰ）による消込処理のうち、いずれか早い方で解が見つかる（すなわち消込完了する）と、解が見つかった消込処理プログラムから他方の消込処理プログラムに完了通知を発行して消込処理を終了する。
【００９７】
本手法１によれば、ＧＡを用いた消込処理と全数探索（またはＤＰ）による消込処理の両者の利点を得ることができる。但し、ＧＡを用いた消込処理と全数探索（またはＤＰ）による消込処理とを同時実行するため、資源（リソース）を要すること、両者の足し合わせ以上の効果が発生するものではないことは留意点である。また、実際の運用面では、入金金額や請求件数が増えると、平均探索時間と最悪探索時間が非常に長くなるという全数探索（またはＤＰ）の不具合が顕在化する（支配的となる）。
【００９８】
<ハイブリッド：手法２>
手法２は、ＧＡなどのメタヒューリスティック手法による探索と全数探索（またはＤＰ）とを切り替える切替手段を有する。ＧＡを用いた消込処理部２１が、上記切替手段を有するものであれば、両者を一方から他方へどのような切替条件（切替タイミング）で切り替えてもよい。
【００９９】
ここで、ＧＡなどのメタヒューリスティック手法による探索と全数探索とＤＰとの選択について述べる。請求件数Ｎ、一つの請求に対する探索回数Ｓとする。Ｎ×Ｓ（特に、Ｓ）が大きな値の場合には、ＧＡが有効である。一方、Ｎ×Ｓ（特に、Ｓ）が小さな値の場合は、ＤＰの方が早く確実に解を求めることができる。ＧＡと全数探索またはＤＰの、いずれの消込処理を実行するかを決める選択の詳細については、図２５で後記する。
【０１００】
本発明者らは、最初にＧＡなどのメタヒューリスティック手法による消込処理を実行し、ある打切り時間内に解が見つからなかったものに対して、全数探索（またはＤＰ）に切り替えて消込処理を実行することで、全数探索（またはＤＰ）で扱う件数（請求件数）を大幅に削減できることを見出した。詳細については、図２３および図２４で後記する。
【０１０１】
本手法２は、下記（１）（２）のハイブリッド処理運用時に好適である。
（１）サーバでの（夜間バッチ）処理：夜間で複数振込の組合せ処理を完了させることを保証しなければならない。つまり、ＧＡで消込処理を行い仕切り時間（打切り時間）で中断する。
（２）クライアント(ユーザ)処理：複数振込の組合せ有無の判断を必ず行う必要がある。
【０１０２】
<ハイブリッド：手法３>（ＧＡの探索の初期値使用）
本手法３は、ＧＡを探索の初期値として使用する手法である。すなわち、本手法３は、上記手法２のようにＧＡを用いた消込処理を、単に全数探索（またはＤＰ）に切り替えるのとは質的に異なり、ＧＡを探索の初期値として知識データベース（ＤＢ）に蓄積し、この知識データベースを用いることで、不確かな知識データを用いた探索および知識を訂正するものである。全数探索（またはＤＰ）において、間違った知識を基に件数を削減すると解なしになる。例えば、請求件数１００件がある場合、知識データベースに基づいて６０件まで削減して処理することができるが、仮に削減した件数のうち一つでも誤りがあると、解がある問題にも拘わらず解なしになる。一方、知識データベースを用いて、件数を削減しないと、探索空間が大きすぎ、探索に時間がかかり過ぎる。
【０１０３】
本手法３は、ＧＡを探索の初期値として使用することで、完全に確かな知識データ以外は件数削減には使用せず、少しでも不安のある知識は（上記メタヒューリスティック手法）探索の初期値として利用する。詳細については、図２６で後記する。
ここで、検索結果を用いた知識データベースの自動更新の場合、知識データに信頼度を付けて更新することが好ましい。
【０１０４】
本手法３は、ＧＡを探索の初期値として使用するだけであるため、誤った知識データを用いても解は必ず見つかる。そして、解が見つかった段階で、誤った知識データがあればその情報を、知識データベースに対してフィードバックをかけることで最初の当該誤りを訂正することができる。二回目以降は、正しい知識データで探索を行うことができる。
【０１０５】
以下、上記手法２および手法３の具体的方法について説明する。
図２３は、請求件数Ｎに対する打切り時間（打切り世代数）を設定するフローチャートであって、上記手法２（その１）の具体的な処理フローである。本フローは、予備実験により予め求めておくものである。
ステップＳ２１において、ＧＡを用いた消込処理部２１は、請求件数Ｎを設定する。請求件数Ｎは、任意に設定できる。ただし、前記図９に示したように、全数探索は、Ｎが大きくなるにつれ指数関数的に実行時間が増加するのに対し、ＧＡの実行時間は、ほぼＮに比例する。したがって、請求件数Ｎが大きい場合、実際の運用上ではＧＡを用いた消込処理を採用することになる。
【０１０６】
ここで、請求件数Ｎを段階的に値を変えて設定するようにすれば、より最適化された打切り時間を設定することができ、無駄な時間を節約することができる。また、請求件数Ｎを十分大きな値とすることで、打切り時間（打切り世代数）（後記）を共通で使用して、設定の手間を省くことができる。
【０１０７】
ステップＳ２２において、ＧＡを用いた消込処理部２１は、請求件数Ｎを基に、ＧＡを用いた消込処理の最大実行時間または最大世代数を決定する。前述したように、世代数とは、親個体群から遺伝的操作によって子個体群を作成する繰り返し回数である。但し、実行時間は、使用するマシンの性能に依存するので、最大世代数で指定した方が好ましい。例えば、前記図１３のテストデータＢの例の場合、打切り世代数は、３,０００,０００世代程度である。
【０１０８】
ステップＳ２３において、ＧＡを用いた消込処理部２１は、決定した最大実行時間または最大世代数に基づいて、ＧＡを最初に実行して全数探索（またはＤＰ）を実行する件数を絞り込む場合のＧＡの打切り時間（「ＧＡ打切り時間」）を設定する。
ステップＳ２４において、ＧＡを用いた消込処理部２１は、設定したＧＡ打切り時間を知識データベース２２（図１８参照）に蓄積して本フローを終了する。
【０１０９】
図２４は、本実施形態のＧＡを用いた消込処理を示すフローチャートであって、上記手法２（その１）の具体的な処理フローである。また、図２４は、図２１のステップＳ１３の詳細フローである。
ステップＳ３１において、ＧＡを用いた消込処理部２１は、ＧＡを探索の初期値として使用するか否かを判別する。
【０１１０】
ＧＡを探索の初期値として使用する場合（ステップＳ３１“Ｙｅｓ”）、ステップＳ４０の「ＧＡの探索の初期値使用（手法３）」（図２６参照）に移行する。
ＧＡを探索の初期値として使用しない場合（ステップＳ３１“Ｎｏ”）、ステップＳ３２において、ＧＡを用いた消込処理部２１は、消込処理においてＧＡを最初に用いたか否かを判別する。
ＧＡを最初に用いていない場合（ステップＳ３２“Ｎｏ”）、ステップＳ５０の「ＧＡと全数探索（またはＤＰ）との並列使用（手法１）」、あるいは「ＧＡの単独使用」に移行する。
ＧＡを最初に用いている場合、ステップＳ３３において、ＧＡを用いた消込処理部２１は、ＧＡによる消込処理を実行する。
【０１１１】
ステップＳ３４において、ＧＡを用いた消込処理部２１は、解が見つかったか否かを判定する。解が見つかっていない場合（ステップＳ３４“Ｎｏ”）、ステップＳ３５においてＧＡを用いた消込処理部２１は、ＧＡの打切り時間を経過したか否かを判定する。この打切り時間は、前記図２３のフローで予め設定しておいた、請求件数Ｎに対する打切り時間である。上述した理由により、打切り時間に代えて打切り世代数を用いてもよい。
ＧＡの打切り時間（打切り世代数）を経過していない場合は（ステップＳ３５“Ｎｏ”）、上記ステップＳ３３に戻る。
【０１１２】
ＧＡの打切り時間（打切り世代数）を経過した場合（ステップＳ３５“Ｙｅｓ”）、ステップＳ３６において、ＧＡを用いた消込処理部２１は、ＧＡによる消込処理から全数探索（またはＤＰ）による消込処理に切り替えて消込処理を実行する。
ステップＳ３７において、ＧＡを用いた消込処理部２１は、解が見つかったか否かを判定する。解が見つかっていない場合は、ステップＳ３８において、ＧＡを用いた消込処理部２１は、全数探索（またはＤＰ）による消込処理が終了か否かを判定する。
全数探索（またはＤＰ）による消込処理が終了でない場合は、上記ステップＳ３６に戻る。
【０１１３】
全数探索（またはＤＰ）による消込処理終了の場合（ステップＳ３８“Ｙｅｓ”）、あるいは上記ステップＳ３４またはステップＳ３７で解が見つかった場合は、ステップＳ３９において、ＧＡを用いた消込処理部２１は、結果を出力して本フローを終了する。結果出力は、例えば検索結果の出力画面の表示／印刷である。また、消込処理が完了したことを示す消込フラグを付ける、また該当レコードを削除するものでもよい。なお、本フローが図２１のステップＳ１３のサブルーチンコールにより起動された場合には、図２１のステップＳ１３に戻り（ＲＥＴＵＲＮ）、ステップＳ１４に進む。
【０１１４】
図２５は、本実施形態のＧＡを用いた消込処理を示すフローチャートであって、上記手法２（その２）の具体的な処理フローである。本フローは、ＧＡと全数探索またはＤＰの、いずれの消込処理を実行するかを選択する処理である。また、図２５は、図２１のステップＳ１３の詳細フローである。
【０１１５】
ステップＳ４１において、ＧＡを用いた消込処理部２１は、請求件数Ｎおよび請求に対する探索回数Ｓを確認する。
ステップＳ４２において、ＧＡを用いた消込処理部２１は、Ｎ×Ｓが所定値以上か否かを判定する。Ｎ×Ｓ（特に、Ｓ）が大きな値の場合には、ＧＡが有効である。一方、Ｎ×Ｓ（特に、Ｓ）が小さな値の場合は、ＤＰの方が早く確実に解を求めることができる。
Ｎ×Ｓが所定値以上の場合（ステップＳ４２“Ｙｅｓ”）、ステップＳ４３において、ＧＡを用いた消込処理部２１は、ＧＡによる消込処理を実行する。
【０１１６】
ステップＳ４４において、ＧＡを用いた消込処理部２１は、解が見つかったか否かを判定する。解が見つかっていない場合（ステップＳ４４“Ｎｏ”）、ステップＳ４５において、ＧＡを用いた消込処理部２１は、探索終了か否かを判定する。
探索終了でない場合（ステップＳ４５“Ｎｏ”）、上記ステップＳ４３に戻る。
【０１１７】
上記ステップＳ４４において、解が見つかった場合（ステップＳ４４“Ｙｅｓ”）または、上記ステップＳ４５において、探索終了する場合（ステップＳ４５“Ｙｅｓ”）は、ステップＳ４９に進む。なお、上記ステップＳ４５の探索終了の判定を省略することも可能であり、上記ステップＳ４４において、解が見つかった場合に、ステップＳ４９に進む態様でもよい。
【０１１８】
一方、上記ステップＳ４２において、Ｎ×Ｓが所定値より小さい場合（ステップＳ４２“Ｎｏ”）、ステップＳ４６において、ＧＡを用いた消込処理部２１は、ＤＰによる消込処理を実行する。
【０１１９】
ステップＳ４７において、ＧＡを用いた消込処理部２１は、解が見つかったか否かを判定する。解が見つかっていない場合（ステップＳ４７“Ｎｏ”）、ステップＳ４８においてＧＡを用いた消込処理部２１は、探索終了か否かを判定する。
探索終了でない場合（ステップＳ４８“Ｎｏ”）、上記ステップＳ４６に戻る。
【０１２０】
上記ステップＳ４７において、解が見つかった場合（ステップＳ４７“Ｙｅｓ”）または、上記ステップＳ４８において、探索終了する場合（ステップＳ４８“Ｙｅｓ”）は、ステップＳ４９に進む。なお、上記ステップＳ４８の探索終了の判定を省略することも可能であり、上記ステップＳ４７において、解が見つかった場合に、ステップＳ４９に進む態様でもよい。
【０１２１】
ステップＳ４９において、ＧＡを用いた消込処理部２１は、結果を出力して本フローを終了する。結果出力は、例えば検索結果の出力画面の表示／印刷である。また、消込処理が完了したことを示す消込フラグを付ける、また該当レコードを削除するものでもよい。なお、本フローが図２１のステップＳ１３のサブルーチンコールにより起動された場合には、図２１のステップＳ１３に戻り（ＲＥＴＵＲＮ）、ステップＳ１４に進む。
【０１２２】
ここで、本実施形態では、図２４の手法２（その１）と図２５の手法２（その２）とを、別フローにしているが、１つのフローにまとめてもよい。例えば、図２４のステップＳ３６ないしステップＳ３９の処理を、図２５のフローに置き換えることで実現できる。
【０１２３】
図２６は、本実施形態のＧＡを探索の初期値として使用する消込処理を示すフローチャートであって、上記手法３の具体的な処理フローである。また、図２４は、図２１のステップＳ１３の詳細フローである。
ステップＳ５１において、ＧＡを用いた消込処理部２１は、二回目以降の正しい知識データによる探索であるか否かを判別する。
【０１２４】
二回目以降の正しい知識データによる探索でない場合（ステップＳ５１“Ｎｏ”）、ＧＡ探索で正しい知識データを取得するため、ステップＳ５２においてＧＡを用いた消込処理部２１は、知識データベース２２（図１８参照）から件数を削減する知識データ（該当するデータの蓄積がなければ、適当なデフォルト値。例えば請求件数１００件に対して４０件削除することで、探索空間を小さくする）を読み出す。
次いで、ステップＳ５３において、ＧＡを用いた消込処理部２１は、削減した件数でＧＡ探索を行う。
【０１２５】
ステップＳ５４において、ＧＡを用いた消込処理部２１は、解が見つかったか否かを判定する。解が見つかっていない場合は（ステップＳ５４“Ｎｏ”）、上記ステップＳ５３に戻る。
解が見つかった場合（ステップＳ５４“Ｙｅｓ”）、ステップＳ５５において、ＧＡを用いた消込処理部２１は、知識データベース２２（図１８参照）を更新して本フローを終了する。
【０１２６】
一方、上記ステップＳ５１において、二回目以降の正しい知識データによる探索である場合（ステップＳ５１“Ｙｅｓ”）、知識データベース２２（図１８参照）に蓄積された知識データが正しいと判断して探索の初期値として使用するため、ステップＳ５６においてＧＡを用いた消込処理部２１は、更新された正しい知識データベースを参照して全数探索（またはＤＰ）による消込処理を実行する。
【０１２７】
ステップＳ５７において、ＧＡを用いた消込処理部２１は、解が見つかったか否かを判定する。解が見つかっていない場合（ステップＳ５７“Ｎｏ”）、上記ステップＳ５６に戻る。
解が見つかった場合（ステップＳ５７“Ｙｅｓ”）、ステップＳ５８において、ＧＡを用いた消込処理部２１は、結果を出力して本フローを終了する。結果出力は、例えば検索結果の出力画面の表示／印刷である。また、消込処理が完了したことを示す消込フラグを付ける、また該当レコードを削除するものでもよい。なお、本フローが図２１のステップＳ１３のサブルーチンコールにより起動された場合には、図２１のステップＳ１３に戻り（ＲＥＴＵＲＮ）、ステップＳ１４に進む。
【０１２８】
以上説明したように、本実施形態に係るＧＡを用いた消込処理装置１は、ＧＡを用いた消込処理部２１と、消込処理の件数を削減するための知識データを格納する知識データベース（ＤＢ）２２とを有する。ＧＡを用いた消込処理部２１は、各請求項目に遺伝子座を対応させ、染色体の定義長は消込処理における全請求件数に一致させ、遺伝子座の遺伝子の値が所定値（例えば「１」）の場合に入金がされ、入金された請求項目に対応する請求金額の合計を染色体が示す入金金額とし、染色体に対応した請求金額の合計額と入金金額の差額の絶対値が小さいほど遺伝的操作における評価値を高くし、全請求件数に対して、交叉および選択の遺伝的操作を行って評価値の高い個体を次世代に引き継ぐ局所探索を実行し、組合せ解が見つかった場合、消込可能と判定する。
【０１２９】
この構成により、全数探索またはＤＰよりも大幅に平均探索時間と最悪探索時間を短くすることができ、かつ、解なしの判断を確実に行うことができる。
【０１３０】
また、ＧＡを用いた消込処理部２１は、同一の入金条件の下、与えられた入金額を満たす複数の組合せ解が存在する場合、その中の１つの組合せ解が求まったとき、消込処理終了と判定するので、必ず、組合せ有無の判断を行う必要があるクライアント（ユーザ）処理、すなわちハイブリッド処理に適する利点がある。
【０１３１】
また、ＧＡを用いた消込処理部２１は、所定の打切り時間を設定し、打切り時間内において遺伝的アルゴリズムを用いた消込処理を完了または中断させることで、夜間で複数振込の組合せ処理を完了させることを保証しなければならない夜間バッチ処理で運用可能になる。
【０１３２】
また、本実施形態では、ＧＡを用いた消込処理部２１が、遺伝的アルゴリズムを用いた消込処理を実行し、所定時間内で組合せ解が解が求まらなかったものに対して、当該消込処理実行により削減された件数で全数探索またはＤＰにより消込処理を実行する。これにより、より一層、平均探索時間と最悪探索時間を短くすることができ、かつ、解なしの判断を確実に行うことができる。
【０１３３】
また、ＧＡを用いた消込処理部２１は、請求件数と請求に対する探索回数との積に基づいて、ＧＡを用いた消込処理またはＤＰによる消込処理のいずれかを選択し、選択した消込処理により消込処理を実行する。これにより、Ｎ×Ｓ（特に、Ｓ）が大きな値の場合にはＧＡが選択され、Ｎ×Ｓ（特に、Ｓ）が小さな値の場合はＤＰが選択されることで、より早く確実に解を求めることができる。また、従来例では、ＤＰを適用しようとすると、入金額の大きさに比例した大量のメモリサイズが必要となるので、企業間の取引で扱う高額な入金の場合（外貨に関しては、整数変換のため特に桁数が増える）には、適用することが困難であった。本実施形態では、ＤＰを適応的に選択できるので、処理速度向上とメモリサイズ削減とを両立させることができる。
【０１３４】
また、本実施形態では、ＧＡを用いた消込処理部２１が、遺伝的アルゴリズムを用いた消込処理を実行し、求めた組合せ解に基づいて知識データを更新し、更新した知識データを検索の初期値として用いて、遺伝的アルゴリズムを用いた消込処理、全数探索またはＤＰによる消込処理を実行する。これにより、ＧＡを探索の初期値として使用することで、解なしを避けつつ、平均探索時間と最悪探索時間を短くすることができる。また、二回目以降は、正しい知識データで探索を行うことができ、平均探索時間と最悪探索時間を短くすることができる。
【０１３５】
なお、本発明は前記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、前記した実施例は、本発明を分かり易く説明するために詳細に説明したものであり、必ずしも説明したすべての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることが可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【０１３６】
また、前記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、前記の各構成、機能
等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。
【０１３７】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしもすべての制御線や情報線を示しているとは限らない。実際には殆どすべての構成が相互に接続されていると考えてもよい。
また、本実施形態に記載した技術的事項を適宜組合せて新たな技術を実現することができる。その他ハードウェア、ソフトウェア、データベース等の具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【０１３８】
１  消込処理装置
１１  中央制御装置
１２  入力装置
１３  出力装置
１４  主記憶装置
１５  補助記憶装置
１６  通信装置
１７  バス
２１  ＧＡを用いた消込処理部（処理部，全数探索処理部，切替部）
２２  知識データベース（ＤＢ）（知識データ格納部）
【図１】
2015232795.tif 000005
【図２】
2015232795.tif 000006
【図３】
2015232795.tif 000007
【図４】
2015232795.tif 000008
【図５】
2015232795.tif 000009
【図６】
2015232795.tif 000010
【図７】
2015232795.tif 000011
【図８】
2015232795.tif 000012
【図９】
2015232795.tif 000013
【図１０】
2015232795.tif 000014
【図１３】
2015232795.tif 000015
【図１６】
2015232795.tif 000016
【図１８】
2015232795.tif 000017
【図１９】
2015232795.tif 000018
【図２０】
2015232795.tif 000019
【図２１】
2015232795.tif 000020
【図２２】
2015232795.tif 000021
【図２３】
2015232795.tif 000022
【図２４】
2015232795.tif 000023
【図２５】
2015232795.tif 000024
【図２６】
2015232795.tif 000025
【図１１】
2015232795.tif 000026
【図１２】
2015232795.tif 000027
【図１４】
2015232795.tif 000028
【図１５】
2015232795.tif 000029
【図１７】
2015232795.tif 000030