JPH0812603B2 - データの最適組み合わせ抽出装置 - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、情報処理分野における計画問題や詰め込み
問題などに用いられる最適組み合わせを求めるデータの
最適組み合わせ抽出装置に関するものである。

従来の技術 最近、データの最適組み合わせ抽出方法としては、全
ての解を求めて最適なものを選び出す、全数解チェック
法や、コストを付けて常にコストの低い方に組み合わせ
直す、ダウン・ヒル法などがある。

しかし、全数解チェック法は最適解を求めることがで
きるが時間がかかり、ダウン・ヒル法では最適解が求ま
る保証がないなどの課題がある。

そこで、近年、シミュレーティト・アニーリング法と
呼ばれる方法が用いられるようになってきた。

以下、第３図を参照しながら、従来のシミュレーティ
ト・アニーリング法について説明する。

第３図はシミュレーティト・アニーリング法を示すブ
ロック図である。第３図において、31はデータを記憶す
るデータベースである。32は、データベース31のデータ
の変更を無作為に決めるデータ変更方法決定部である。
33はデータ変更方法決定部32で決めたデータベース31の
データの変更方法を実行した場合に、与えられた制約を
満たすかを調べる制約チェック部である。34はデータ変
更方法決定部32で決めたデータベース31のデータの変更
方法を実行した場合のコストを計算するコスト計算部で
ある。35はデータ変更方法決定部32で決めたデータベー
ス31のデータの変更を実行するルール実行部である。36
はシミュレーティト・アニーリング法で必要な温度と呼
ばれるパラメータを管理・変更する温度管理部である。

以上のような第３図の構成において、以下、その動作
について、第４図に示したフローチャートとともに説明
する。

まず、401ではコスト計算部34を用いて現在のコスト
を計算する。また、402では、温度管理部36で管理され
ている温度と呼ばれるパラメータを初期化する。

次に403ではデータ変更方法決定部32を用いてデータ
ベース31のデータの変更方法を無作為に決める。以下、
このデータ変更方法をルールと呼ぶ。404では、403で作
った変更方法を実行した場合、与えられた制約を満たす
かを制約チェック部33を用いてチェックする。制約を満
たさない時は、408に飛ぶ。制約を満たす時は、405でコ
スト計算部34を用いて403で作ったデータの変更方法を
行った時のコストを計算する。406では、405で計算した
コストと温度管理部36で管理している温度を用いてルー
ルを実行するかを以下の方法で決める。

コストがルール実行後下がるときは、ルールを実行す
る。コストがルール実行後上がる時でも、０以上１未満
の乱数を発生させ、その乱数が exp（−ΔC/T） より、大きいときは実行する。ここで、ΔＣはルール実
行後のコストと現在のコストの差、Ｔは温度管理部36で
管理している温度である。

実行を行うときは、407でルール実行部35を用いて実
行する。

408では温度管理部36で管理している温度を下げる。
そして、三回続けてコストが変更されなかった場合は終
了して現在のデータベース31のデータを結果とする。そ
うでない場合は、403に戻る。

発明が解決しようとする課題 しかし、以上の方法では、データを無作為に変更する
ため、変更した結果がもとに戻ることが頻繁に起こる。
そのため、コストが収束するまでに時間がかかる。

一方、ある程度収束先が分かった段階で、ヒューリス
ティック・ルールを用いることは有効だが、はじめから
ヒューリスティック・ルールを適用すると、局所的な解
に収束してしまう可能性が大きい。

また、全てをヒューリスティック・ルールを用いて行
うとすると、ルールの記述が複雑になるという課題もあ
る。

本発明は上記課題に鑑み、ある程度収束先が分かった
段階でヒューリスティック・ルールを用いることにより
コストの収束を速くして、結果を短時間で求めることを
目的とする。

課題を解決するための手段 本発明は、データを変更するためのヒューリスティッ
ク・ルールを記憶する記憶手段と、データを無作為に変
更するルールを決める無作為ルール決定手段と、データ
の変更状態を表すパラメータに基づき前記ヒューリステ
ィック・ルールを適用するか前記無作為ルール決定手段
により決定されるランダム・ルールを適用するかの選択
を指示するルール選択手段とを備えた構成となってい
る。

作用 本発明は、上記構成により、ある程度収束先が分かっ
た段階で、ヒューリスティック・ルールを用いることに
より、異なる２種類のルールを効率よく組合せて、かつ
簡単なヒューリスティック・ルールの記述により、デー
タの最適な組み合わせを求めるようにしたものである。

実施例 以下、第１図と第２図を参照して本発明の一実施例に
ついて説明する。第１図は、本発明のデータの最適組み
合わせ抽出方法のブロック図である。第１図において、
１はヒューリスティック・ルールを記憶するルールベー
スである。２はデータを記憶するデータベースである。
３は温度や現在のコストなどを参照しながら、ランダム
・ルールを用いるかヒューリスティック・ルールを用い
るかを選択するルール選択部である。４はデータの変更
の仕方を無作為に決めるランダム・ルール選択部であ
る。５はデータベース２のデータや温度やコストなどを
参照しながらルールベース１の中から実行すべきものを
選択するヒューリスティック・ルール選択部である。６
はデータの変更、削除などを行った場合に与えられた制
約を満たすかを調べる制約チェック部である。７は、デ
ータの変更、削除を行った場合のコストを計算するコス
ト計算部である。８はデータの変更を行うかをコストか
ら決めて、ルールを実行し、データを変更するルール実
行部である。９は温度と呼ばれるパラメータを管理する
温度管理部である。

以上のような第１図の構成において、以下その動作に
ついて、第２図のフローチャートとともに説明する。

まず、201ではコスト計算部７をもちいて現在データ
ベース２に蓄えられているデータのコストを計算する。
また、202では、温度管理部９で管理している温度と起
ばれるパラメータを初期化する。

次に、203では、ルール選択部３でヒューリスティッ
クルールを用いるか、ランダム・ルールを用いるかを選
択する。このとき、温度が高いときはランダム・ルール
が温度が低いときはヒューリスティック・ルールを選択
するようにする。

203でランダム・ルールを選択した場合は、205でラン
ダム・ルール選択部４を用いて、データベース２のデー
タをどのように変更するかを決める。このデータの変更
方法をランダム・ルールと呼ぶ。そして、205で決めた
ランダム・ルールが制約を満たすかどうかを制約チェッ
ク部６を用いてチェックを行う。制約を満たす時はコス
ト計算208に、制約を満たさない時は温度の変更211に飛
ぶ。

ルールの選択203でヒューリスティック・ルールを選
択した場合は、206においてヒューリスティック・ルー
ル選択部５を用いてデータベース２のデータを参照をし
ながらルールベース１のヒューリスティック・ルールの
中から実行するルールを選択する。

208では、コスト計算部を用いて203、あるいは、206
で決めたルールを実行した後のコストを計算する。

そして、ルール実行部８を用いて、208で計算したコ
ストと温度管理部９で管理されている温度から以下の方
法でルールを実行するかどうかを決定する。

コストがルール実行後下がるときは、ルールを実行す
る。コストがルール実行後上がる時でも、０以上１未満
の乱数を発生させ、その乱数が exp（−ΔC/T） より、大きいときは実行する。ここで、ΔＣはルール実
行後のコストと現在のコストの差、Ｔは温度管理部９で
管理している温度である。

実行を行う時は、210でルールの実行を行い、データ
ベース２のデータの変更を行う。

次の温度変更211では、温度管理部９で管理している
温度を下げる。そして、コストが３回続けて変化しない
時はデータベース２のデータを結果として終了する。そ
うでない時は、203に戻る。

以上のように、温度が高いときは、従来のシミュレー
ティット・アニーリング法のように振るまい、温度が下
がり、ある程度収束先が分かったらヒューリスティック
・ルールを用いて一挙にコストを下げることが出来る。

発明の効果 以上のように、本発明は、無作為なデータ変更とヒュ
ーリスティックなデータ変更の両方を用いて、温度が高
いときは従来のシミュレーティット・アニーリング法の
ように振るまい、温度が下がってきたときにヒューリス
ティックなルールを用いて、コストを一挙に下げて収束
を速くすることにより、結果を短時間で求めることがで
きる。

【図面の簡単な説明】

第１図は本発明の一実施例におけるデータの最適組み合
わせ抽出装置のブロック図、第２図は第１図のデータの
最適組み合わせ抽出装置を説明するためのフローチャー
ト、第３図は従来のシミュレーティット・アニーリング
方法のブロック図、第４図は第３図のシミュレーティッ
ト・アニーリング方法を説明するためのフローチャート
である。 １……ルールベース、２……データベース、３……ルー
ル選択部、４……ランダムルール選択部、５……ヒュー
リスティックルール選択部、６……制約チェック部、７
……コスト計算部、８……ルール実行部、９……温度管
理部。

Claims (1)

【特許請求の範囲】
1. 【請求項１】データを記憶する第１の記憶手段と、前記
   第１の記憶手段に記憶されたデータの変更状態を示すパ
   ラメータを前記データに基づき管理するパラメータ管理
   手段と、前記第１の記憶手段に記憶されたデータを変更
   するためのルールを記憶する第２の記憶手段と、前記第
   １の記憶手段に記憶されたデータに基づき前記第２の記
   憶手段に記憶されたルールからルール候補を選択する第
   １のルール選択手段と、前記第１の記憶手段に記憶され
   たデータを無作為に変更するルールを決める無作為ルー
   ル決定手段と、前記無作為ルール決定手段が決定した変
   更を行った場合に、変更後のデータが予め与えられた制
   約を満たすかどうかを確認し、制約を満たすルールを出
   力する制約チェック手段と、前記第１の記憶手段に記憶
   されたデータのコスト、前記第１のルール選択手段によ
   り選択されたルール候補を実行した場合のデータのコス
   ト、及び前記制約を満たすルールを実行した場合のデー
   タのコストを計算するコスト計算手段と、前記コスト計
   算手段により計算されたコストと前記パラメータ管理手
   段で管理されたパラメータに基づきルールを実行するか
   どうかを判定し、判定結果に基づきルールを実行するこ
   とにより前記第１の記憶手段に記憶されたデータを変更
   するルール実行手段と、前記パラメータ管理手段で管理
   されたパラメータに基づき前記第１のルール選択手段か
   前記無作為ルール決定手段かの何れかの起動を選択する
   第２のルール選択手段とを備え、 データの変更状態に基づき適応すべきルールの種類を選
   択し、前記パラメータ管理手段によるパラメータの一定
   回数の変更に対し、コストが変化しない場合、前記第１
   の記憶手段に記憶されているデータを最適なデータの組
   合せ結果とするデータの最適組み合わせ抽出装置。