特許ウォッチ

公開番号2025150836
公報種別公開特許公報(A)
公開日2025-10-09
出願番号2024051965
出願日2024-03-27
発明の名称プログラム、データ処理装置及びデータ処理方法
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類G06N 99/00 20190101AFI20251002BHJP(計算;計数)
要約【課題】短期間で適切なタブー期間を得る。
【解決手段】処理部12は、複数の状態変数の値の組合せで表される組合せ最適化問題の解を、値が変化した状態変数の値を固定するタブー期間を所定期間ごとに変えた第1タブーサーチにより探索する。処理部12は、上記所定期間に値が変化した状態変数の数を、タブー期間ごとに記憶部11に記憶する。処理部12は、タブー期間の変化に対する上記数の変化の傾きに基づいて、状態変数の値を固定する第1タブー期間を決定し、上記解を、決定した第1タブー期間を用いた第2タブーサーチにより探索する。
【選択図】図1
特許請求の範囲【請求項１】
複数の状態変数の値の組合せで表される組合せ最適化問題の解を、値が変化した状態変数の値を固定するタブー期間を所定期間ごとに変えた第１タブーサーチにより探索し、
前記所定期間に値が変化した前記状態変数の数を、前記タブー期間ごとに記憶部に記憶し、
前記タブー期間の変化に対する前記数の変化の傾きに基づいて、前記状態変数の値を固定する第１タブー期間を決定し、
前記解を、決定した前記第１タブー期間を用いた第２タブーサーチにより探索する、
処理をコンピュータに実行させるプログラム。
続きを表示（約 1,500 文字）【請求項２】
前記第１タブー期間は、前記傾きが最大となるときの前記タブー期間である、請求項１に記載のプログラム。
【請求項３】
前記タブー期間を、前記所定期間ごとに長くしていき、前記所定期間ごとに前記傾きの微分を算出し、
前記傾きの微分の値が正から負に変化したときに、前回の前記所定期間に用いられた前記タブー期間を前記第１タブー期間として決定する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項４】
前記所定期間に値が変化した前記状態変数の前記数が、前記複数の状態変数の総数の７０％を超えるとき、前回の前記所定期間に用いられた前記タブー期間を前記第１タブー期間として決定する、
処理を前記コンピュータに実行させる請求項３に記載のプログラム。
【請求項５】
前記第１タブー期間を探索する前記タブー期間の範囲を第１範囲と第２範囲に２分割し、
前記第１範囲と前記第２範囲のうち、前記傾きの大きい方を、新たな前記範囲として２分割する処理を繰り返すことで、前記第１タブー期間を探索する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項６】
前記第１範囲の前記傾きは、前記範囲の下限値を用いた前記第１タブーサーチにより、前記所定期間に値が変化した前記状態変数の第１数と、前記範囲の中間値を用いた前記第１タブーサーチにより、前記所定期間に値が変化した前記状態変数の第２数との差により算出され、
前記第２範囲の前記傾きは、前記第２数と、前記範囲の上限値を用いた前記第１タブーサーチにより、前記所定期間に値が変化した前記状態変数の第３数との差により算出される、
請求項５に記載のプログラム。
【請求項７】
前記第１タブー期間の決定後、前記所定期間において値が変化した前記状態変数の前記数が、前記複数の状態変数の総数の３０％以上７０％以下の範囲外、または前記第１タブー期間を決定したときの値に対して、閾値％外れたと判定した場合に、前記第１タブーサーチによる探索を再開し、前記第１タブー期間を再決定する、
処理を前記コンピュータに実行させる請求項１に記載のプログラム。
【請求項８】
前記タブー期間を変える刻み幅は、前記タブー期間が長くなるほど大きい、請求項１に記載のプログラム。
【請求項９】
記憶部と、
複数の状態変数の値の組合せで表される組合せ最適化問題の解を、値が変化した状態変数の値を固定するタブー期間を所定期間ごとに変えた第１タブーサーチにより探索し、前記所定期間に値が変化した前記状態変数の数を、前記タブー期間ごとに前記記憶部に記憶し、前記タブー期間の変化に対する前記数の変化の傾きに基づいて、前記状態変数の値を固定する第１タブー期間を決定し、前記解を、決定した前記第１タブー期間を用いた第２タブーサーチにより探索する処理部と、
を有するデータ処理装置。
【請求項１０】
コンピュータが、
複数の状態変数の値の組合せで表される組合せ最適化問題の解を、値が変化した状態変数の値を固定するタブー期間を所定期間ごとに変えた第１タブーサーチにより探索し、
前記所定期間に値が変化した前記状態変数の数を、前記タブー期間ごとに記憶部に記憶し、
前記タブー期間の変化に対する前記数の変化の傾きに基づいて、前記状態変数の値を固定する第１タブー期間を決定し、
前記解を、決定した前記第１タブー期間を用いた第２タブーサーチにより探索する、
データ処理方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、プログラム、データ処理装置及びデータ処理方法に関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
組合せ最適化問題の解を探索する手法の１つに、タブーサーチがある（たとえば、特許文献１－３、非特許文献１－３参照）。組合せ最適化問題の解は、複数の状態変数の値の組合せで表される。タブーサーチでは、複数の状態変数のうち、一度値が変更された状態変数が一定期間、固定される。これにより、解が同じ局所解に何度も陥ることが抑制され、広い解空間の探索が実現される。状態変数を固定する上記の期間は、タブー期間（Tabu tenure）と呼ばれる。
【先行技術文献】
【特許文献】
【０００３】
国際公開第２００６／１１８１９３号
米国特許出願公開第２０２３／０１６９３５３号明細書
米国特許出願公開第２０１６／００４２２９４号明細書
【非特許文献】
【０００４】
Nilgun Fescioglu-Unver, Mieczyslaw M. Kokar, “Self Controlling Tabu Search algorithm for the Quadratic Assignment Problem”, Computers & Industrial Engineering, 2011, vol.60, pp.310-319
Roberto Battiti, Giampietro Tecchiolli, “The Reactive Tabu Search”, ORSA Journal on Computing, 1994, Vol.6, No.2, pp.126-140
E. Taillard, “Robust taboo search for the quadratic assignment problem”, Parallel computing, 1991, Vol.17, pp.443-455
【発明の概要】
【発明が解決しようとする課題】
【０００５】
問題によって適切なタブー期間は異なる。このため、異なる問題に対して、予め決められた共通のタブー期間を用いてタブーサーチを行っても、問題によっては高い求解性能が得られない可能性がある。このため、多くの場合、問題に応じて作業者が手作業でタブー期間を設定していた。しかし、タブー期間として設定可能な値は、状態変数の総数と同数であり得るため、試行錯誤で適切なタブー期間を決定するには時間がかかる。
【０００６】
１つの側面では、短期間で適切なタブー期間を得ることを目的とする。
【課題を解決するための手段】
【０００７】
１つの実施態様では、複数の状態変数の値の組合せで表される組合せ最適化問題の解を、値が変化した状態変数の値を固定するタブー期間を所定期間ごとに変えた第１タブーサーチにより探索し、前記所定期間に値が変化した前記状態変数の数を、前記タブー期間ごとに記憶部に記憶し、前記タブー期間の変化に対する前記数の変化の傾きに基づいて、前記状態変数の値を固定する第１タブー期間を決定し、前記解を、決定した前記第１タブー期間を用いた第２タブーサーチにより探索する、処理をコンピュータに実行させるプログラムが提供される。
【０００８】
また、１つの実施態様ではデータ処理装置が提供される。
また、１つの実施態様ではデータ処理方法が提供される。
【発明の効果】
【０００９】
１つの側面では、短期間で適切なタブー期間が得られる。
【図面の簡単な説明】
【００１０】
第１の実施の形態のデータ処理装置とその処理手順の一例を示す図である。
タブー期間に対する、所定期間において値が変化した状態変数の種類数と評価関数の値の関係を示す図である。
第２の実施の形態のデータ処理装置のハードウェア例を示すブロック図である。
データ処理装置の機能例を示すブロック図である。
タブー期間段階リストの作成例を示す図である。
データ処理装置の処理手順の第１の例を示すフローチャートである。
タブー期間調整処理の処理手順の第１の例を示すフローチャートである。
タブー期間調整処理の処理手順の第２の例を示すフローチャートである。
データ処理装置の処理手順の第２の例を示すフローチャートである。
第２の例におけるタブー期間調整処理の処理手順を示すフローチャートである。
データ処理装置の処理手順の第３の例を示すフローチャートである。
１８種の組合せ最適化問題を用いた評価実験の結果を示す図である。
データ処理装置の他の例を示す図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許