JPH047638A - データの最適組み合わせ抽出装置 - Google Patents
データの最適組み合わせ抽出装置Info
- Publication number
- JPH047638A JPH047638A JP2107439A JP10743990A JPH047638A JP H047638 A JPH047638 A JP H047638A JP 2107439 A JP2107439 A JP 2107439A JP 10743990 A JP10743990 A JP 10743990A JP H047638 A JPH047638 A JP H047638A
- Authority
- JP
- Japan
- Prior art keywords
- data
- rule
- temperature
- cost
- random
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 43
- 238000002922 simulated annealing Methods 0.000 abstract description 6
- 238000007726 management method Methods 0.000 description 10
- 238000004364 calculation method Methods 0.000 description 8
- 238000010586 diagram Methods 0.000 description 4
- 238000000137 annealing Methods 0.000 description 3
- 230000007423 decrease Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
- 238000002715 modification method Methods 0.000 description 1
- 238000012856 packing Methods 0.000 description 1
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明は、情報処理分野における計画問題や詰め込み問
題などに用いられる最適組み合わせを求めるデータの最
適組み合わせ抽出方法に関するものである。
題などに用いられる最適組み合わせを求めるデータの最
適組み合わせ抽出方法に関するものである。
従来の技術
最近、データの最適組み合わせ抽出方法としては、全て
の解を求めて最適なものを選び出す、全数解チエツク法
や、コストを付けて常にコストの低い方に組み合わせ直
す、ダウン・ヒル法などがある。
の解を求めて最適なものを選び出す、全数解チエツク法
や、コストを付けて常にコストの低い方に組み合わせ直
す、ダウン・ヒル法などがある。
しかし、全数解チエツク法は最適解を求めることができ
るが時間がかかシ、ダウン・ヒル法では最適解が求まる
保証がないなどの課題がある。
るが時間がかかシ、ダウン・ヒル法では最適解が求まる
保証がないなどの課題がある。
そこで、近年、シミュレーティト・アニーリング法と呼
ばれる方法が用いられるようＫなってきた。
ばれる方法が用いられるようＫなってきた。
以下、第３図を参照しながら、従来のシミュレーティト
・アニーリング法について説明する。
・アニーリング法について説明する。
第３図はシミュレーティト・アニーリング法を示すブロ
ック図である。第３図において、３１はデ−タを記憶す
るデータベースである。３２は、データベース３１のデ
ータの変更を無作為に決めるデータ変更方法決定部であ
る。３３はデータ変更方法決定部３２で決めたデータベ
ース３１のデータの変更方法を実行した場合に、与えら
れた制約を満たすかを調べる制約チエツク部である。３
４はデータ変更方法決定部３２で決めたデータベース３
１のデータの変更方法を実行し°た場合のコストを計算
するコスト計算部である。あはデータ変更方法決定部３
２で決めたデータベース３１のデータの変更を実行する
データ変更部である。３６はシミュレーテイト・アニー
リング法で必要な温度と呼ばれるパラメータを管理・変
更する温度管理部である。
ック図である。第３図において、３１はデ−タを記憶す
るデータベースである。３２は、データベース３１のデ
ータの変更を無作為に決めるデータ変更方法決定部であ
る。３３はデータ変更方法決定部３２で決めたデータベ
ース３１のデータの変更方法を実行した場合に、与えら
れた制約を満たすかを調べる制約チエツク部である。３
４はデータ変更方法決定部３２で決めたデータベース３
１のデータの変更方法を実行し°た場合のコストを計算
するコスト計算部である。あはデータ変更方法決定部３
２で決めたデータベース３１のデータの変更を実行する
データ変更部である。３６はシミュレーテイト・アニー
リング法で必要な温度と呼ばれるパラメータを管理・変
更する温度管理部である。
以上のような第３図の構成において、以下、その動作に
ついて、第４図に示したフローチャートとともに説明す
る。
ついて、第４図に示したフローチャートとともに説明す
る。
まず、４０１ではコスト計算部３４を用いて現在のコス
トを計算する。また、４０２では、温度管理部３６で管
理されている温度と呼ばれるパラメータを初期化する。
トを計算する。また、４０２では、温度管理部３６で管
理されている温度と呼ばれるパラメータを初期化する。
次に４０３ではデータ変更方法決定部３２を用いてデー
タベース３】のデータの変更方法を無作為に決める。以
下、このデータ変更方法をルールと呼ぶ。
タベース３】のデータの変更方法を無作為に決める。以
下、このデータ変更方法をルールと呼ぶ。
４０４では、４０３で作った変更方法を実行した場合、
与えられた制約を満たすかを制約チエツク部：３３を用
いてチエツクする。制約を満たさない時は、４０８に飛
ぶ。制約を満たす時は、４０５でコスト計算部あを用い
て４０３で作ったデータの変更方法を行った時のコスト
を計算する。４０６では、４０５で計算したコストと温
度管理部３６で管理している温度を用いてルールを実行
するかを以下の方法で決める。
与えられた制約を満たすかを制約チエツク部：３３を用
いてチエツクする。制約を満たさない時は、４０８に飛
ぶ。制約を満たす時は、４０５でコスト計算部あを用い
て４０３で作ったデータの変更方法を行った時のコスト
を計算する。４０６では、４０５で計算したコストと温
度管理部３６で管理している温度を用いてルールを実行
するかを以下の方法で決める。
コストがデータ変更抜工がるときは、ルールを実行する
。コストがデータ変更抜上がる時でも、０以上１未満の
乱数を発生させ、その乱数がｅｘｐ （−△Ｃ／Ｔ） よシ、大きいときは実行する。ここで、△Ｃはデータ変
更後のコストと現在のコストの差、Ｔは温度管理部面で
管理している温度である。
。コストがデータ変更抜上がる時でも、０以上１未満の
乱数を発生させ、その乱数がｅｘｐ （−△Ｃ／Ｔ） よシ、大きいときは実行する。ここで、△Ｃはデータ変
更後のコストと現在のコストの差、Ｔは温度管理部面で
管理している温度である。
実行を行うときは、４０７でデータ変更部３５を用いて
実行する。
実行する。
４０８では温度管理部３６で管理している温度を下げる
。そして、三回続けてコストが変更されなかった場合は
終了して現在のデータベース３１のデータを結果とする
。そうでない場合は、４０３に戻る。
。そして、三回続けてコストが変更されなかった場合は
終了して現在のデータベース３１のデータを結果とする
。そうでない場合は、４０３に戻る。
発明が解決しようとする課題
しかし、以上の方法では、データを無作為に変更するた
め、変更した結果がもとに戻ることが頻繁に起こる。そ
のため、コストが収束するまでに時間がかかる。
め、変更した結果がもとに戻ることが頻繁に起こる。そ
のため、コストが収束するまでに時間がかかる。
本発明は上記課題に鑑み、コストの収束を速くして、結
果を短時間で求めることを目的とする。
果を短時間で求めることを目的とする。
課題を解決するための手段
本発明は、データを記憶する第１の記憶手段と、ルール
を記憶する第２の記憶手段と、前記第１の記憶手段によ
って記憶されているデータを無作為に変更するデータ変
更手段と、前記第１の記憶手段によって記憶されている
データを前記第２の記憶手段によって記憶されているル
ールを実行して変更するデータ変更手段を設けたもので
ある。
を記憶する第２の記憶手段と、前記第１の記憶手段によ
って記憶されているデータを無作為に変更するデータ変
更手段と、前記第１の記憶手段によって記憶されている
データを前記第２の記憶手段によって記憶されているル
ールを実行して変更するデータ変更手段を設けたもので
ある。
作用
本発明は、上記構成において、第１の記憶手段によって
記憶されているデータを、データ変更手段によって無作
為に変更する方法と、データ変更手段によって第２の記
憶手段によって記憶されているルールを用いて変更する
方法の両方の方法を用いて、データの最適な組み合わせ
を求めるようにしたものである。
記憶されているデータを、データ変更手段によって無作
為に変更する方法と、データ変更手段によって第２の記
憶手段によって記憶されているルールを用いて変更する
方法の両方の方法を用いて、データの最適な組み合わせ
を求めるようにしたものである。
実施例
以下、第１図と第２図を参照して本発明の一実施例につ
いて説明する。第１図は、本発明のデータの最適組み合
わせ抽出方法のブロック図である。
いて説明する。第１図は、本発明のデータの最適組み合
わせ抽出方法のブロック図である。
第１図において、■はヒユーリスティック・ルールを記
憶するルールベースである。２はデータを記憶するデー
タベースである。３は温度や現在のコストなどを参照し
ながら、ランダム・ルールを用いるかヒユーリスティッ
ク・ルールを用いるかを選択するルール選択部である。
憶するルールベースである。２はデータを記憶するデー
タベースである。３は温度や現在のコストなどを参照し
ながら、ランダム・ルールを用いるかヒユーリスティッ
ク・ルールを用いるかを選択するルール選択部である。
４はデータの変更の仕方を無作為に決めるランダム・ル
ール選択部である。５はデータベース２のデータや温度
やコストなどを参照しながらルールベース１の中がら実
行すべきものを選択するヒユーリスティック・ルール選
択部である。６はデータの変更、削除などを行った場合
に与えられた制約を満たすかを調べる制約チエツク部で
ある。７は、データの変更、削除を行った場合のコスト
を計算するコスト計算部である。８はデータの変更を行
うかをコストから決めて、ルールを実行し、データを変
更するデータ変更部である。９は温度と呼ばれるパラメ
ータを管理する温度管理部である。
ール選択部である。５はデータベース２のデータや温度
やコストなどを参照しながらルールベース１の中がら実
行すべきものを選択するヒユーリスティック・ルール選
択部である。６はデータの変更、削除などを行った場合
に与えられた制約を満たすかを調べる制約チエツク部で
ある。７は、データの変更、削除を行った場合のコスト
を計算するコスト計算部である。８はデータの変更を行
うかをコストから決めて、ルールを実行し、データを変
更するデータ変更部である。９は温度と呼ばれるパラメ
ータを管理する温度管理部である。
以上のような第１図の構成において、以下その動作につ
いて、第２図のフローチャートとともに説明する。
いて、第２図のフローチャートとともに説明する。
まず、２０１ではコスト計算部７をもちいて現在データ
ベース２に蓄えられているデータのコストを計算する。
ベース２に蓄えられているデータのコストを計算する。
また、２０２では、温度管理部９で管理している温度と
呼ばれるパラメータを初期化する。
呼ばれるパラメータを初期化する。
次に、２０３では、ルール選択部３でヒユーリスティッ
クルールを用いるか、ランダム・ルールを用いるかを選
択する。このとき、温度が高いときはランダム・ルール
が温度が低いときはヒユーリスティック・ルールを選択
するようにする。
クルールを用いるか、ランダム・ルールを用いるかを選
択する。このとき、温度が高いときはランダム・ルール
が温度が低いときはヒユーリスティック・ルールを選択
するようにする。
２０３でランダム・ルールを選択した場合は、２０５で
ランダム・ルール選択部４を用いて、データベース２の
データをどのように変更するかを決める。
ランダム・ルール選択部４を用いて、データベース２の
データをどのように変更するかを決める。
このデータの変更方法をランダム・ルールと呼ぶ。
そして、２０５で決めたランダム・ルールが制約ヲ満た
すかどうかを制約チエツク部６を用いてヒ一リスティッ
クルールの選択２０７を行う。制約を満たす時はコスト
計算２０８に、制約を満たさない時は温度の変更２１１
に飛ぶ。
すかどうかを制約チエツク部６を用いてヒ一リスティッ
クルールの選択２０７を行う。制約を満たす時はコスト
計算２０８に、制約を満たさない時は温度の変更２１１
に飛ぶ。
ルールの選択２０３でヒユーリスティック・ルールを選
択した場合は、２０６においてヒユーリスティック・ル
ール選択部５を用いてデータベース２のデータを参照を
しながらルールベース１のヒ一すステインク・ルールの
中から実行するルールを選択する。
択した場合は、２０６においてヒユーリスティック・ル
ール選択部５を用いてデータベース２のデータを参照を
しながらルールベース１のヒ一すステインク・ルールの
中から実行するルールを選択する。
２０８では、コスト計算部を用いて２０３、あるいは、
２０６で決めたルールを実行した後のコストを計算する
。
２０６で決めたルールを実行した後のコストを計算する
。
そして、データ変更部８を用いて、２０８で計算したコ
ストと温度管理部９で管理されている温度から以下の方
法でルールを実行するかどうかを決定する。
ストと温度管理部９で管理されている温度から以下の方
法でルールを実行するかどうかを決定する。
コストがデータ変更抜工がるときは、ルールを実行する
。コストがデータ変更抜上がる時でも、０以上１未満の
乱数を発生させ、その乱数がｅｘｐ （−△Ｃ／Ｔ） より、大きいときは実行する。ここで、ΔＣはデータ変
更後のコストと現在のコストの差、Ｔは温度管理部９で
管理している温度である。
。コストがデータ変更抜上がる時でも、０以上１未満の
乱数を発生させ、その乱数がｅｘｐ （−△Ｃ／Ｔ） より、大きいときは実行する。ここで、ΔＣはデータ変
更後のコストと現在のコストの差、Ｔは温度管理部９で
管理している温度である。
実行を行う時は、２１０でルールの実行を行い、データ
ベース２のデータの変更を行う。
ベース２のデータの変更を行う。
次の温度変更２１１では、温度管理部９で管理している
温度を下げる。そして、コストが３回続けて変化しない
時はデータベース２のデータを結果として終了する。そ
うでない時は、２０３に戻る。
温度を下げる。そして、コストが３回続けて変化しない
時はデータベース２のデータを結果として終了する。そ
うでない時は、２０３に戻る。
以上のように、温度が高いときは、従来のシミュレーテ
ィソト・アニーリング法のように振るまい、温度が下が
シ、ある程度収束先が分かったらヒユーリスティック・
ルールを用いて一挙にコストを下げることが出来る。
ィソト・アニーリング法のように振るまい、温度が下が
シ、ある程度収束先が分かったらヒユーリスティック・
ルールを用いて一挙にコストを下げることが出来る。
発明の効果
以上のように、本発明は、無作為なデータ変更とヒユー
リスティックなデータ変更の両方を用いて、温度が高い
ときは従来のシミーレーティソト・アニーリング法のよ
うに振るまい、温度が下がってきたときにヒユーリステ
ィックなルールを用いて、コストを一挙に下げて収束を
速くすることにより、結果を短時間で求めることができ
る。
リスティックなデータ変更の両方を用いて、温度が高い
ときは従来のシミーレーティソト・アニーリング法のよ
うに振るまい、温度が下がってきたときにヒユーリステ
ィックなルールを用いて、コストを一挙に下げて収束を
速くすることにより、結果を短時間で求めることができ
る。
第１図は本発明の一実施例におけるデータの最適組み合
わせ抽出方法のブロック図、第２図は第１図のデータの
最適組み合わせ抽出方法を説明するためのフローチャー
ト、第３図は従来のシミュレーティット・アニーリング
方法のブロック図、第４図は第３図のシミュレーティッ
ト・アニーリング方法を説明するためのフローチャート
である。 １°°°ルールベース、２・・・データベース、３・・
・ルール選択部、４・・・ランダムルール選択部、５
ヒューリスティックルール選択部、６・・・制約チエツ
ク部、７・・・コスト計算部、８・・・データ変更部、
９・・・温度管理部。
わせ抽出方法のブロック図、第２図は第１図のデータの
最適組み合わせ抽出方法を説明するためのフローチャー
ト、第３図は従来のシミュレーティット・アニーリング
方法のブロック図、第４図は第３図のシミュレーティッ
ト・アニーリング方法を説明するためのフローチャート
である。 １°°°ルールベース、２・・・データベース、３・・
・ルール選択部、４・・・ランダムルール選択部、５
ヒューリスティックルール選択部、６・・・制約チエツ
ク部、７・・・コスト計算部、８・・・データ変更部、
９・・・温度管理部。
Claims (1)
- データを記憶するための第１の記憶手段と、前記第１の
記憶手段によって記憶されたデータを変更するためのル
ールを記憶する第２の記憶手段と、前記第１の記憶手段
によつて記憶されているデータを無作為に変更するデー
タ変更手段と、前記第２の記憶手段によって記憶されて
いるルールの中から所定のルールを用いて前記第１の記
憶手段によって記憶されているデータを変更するルール
を選択し、実行するルール実行手段とを具備し、前記第
１の記憶手段によって記憶されているデータを、前記デ
ータ変更手段で無作為に、或いは、前記ルール実行手段
で、前記第２の記憶手段によつて記憶されているルール
を用いて変更することを特徴とするデータの最適組み合
わせ抽出方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10743990A JPH0812603B2 (ja) | 1990-04-25 | 1990-04-25 | データの最適組み合わせ抽出装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10743990A JPH0812603B2 (ja) | 1990-04-25 | 1990-04-25 | データの最適組み合わせ抽出装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH047638A true JPH047638A (ja) | 1992-01-13 |
| JPH0812603B2 JPH0812603B2 (ja) | 1996-02-07 |
Family
ID=14459178
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10743990A Expired - Lifetime JPH0812603B2 (ja) | 1990-04-25 | 1990-04-25 | データの最適組み合わせ抽出装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0812603B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0627866A (ja) * | 1992-07-06 | 1994-02-04 | Iwatsu Electric Co Ltd | 無作為抽出によるデータ処理方法 |
| US20210073438A1 (en) * | 2018-06-05 | 2021-03-11 | Mitsubishi Electric Corporation | Optimization system, optimization method, control circuit and computer readable storage medium |
-
1990
- 1990-04-25 JP JP10743990A patent/JPH0812603B2/ja not_active Expired - Lifetime
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0627866A (ja) * | 1992-07-06 | 1994-02-04 | Iwatsu Electric Co Ltd | 無作為抽出によるデータ処理方法 |
| US20210073438A1 (en) * | 2018-06-05 | 2021-03-11 | Mitsubishi Electric Corporation | Optimization system, optimization method, control circuit and computer readable storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0812603B2 (ja) | 1996-02-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20060003823A1 (en) | Dynamic player groups for interest management in multi-character virtual environments | |
| US10235474B2 (en) | In-memory graph analytics system that allows memory and performance trade-off between graph mutation and graph traversal | |
| JPH02130647A (ja) | 索引木構造の更新方式 | |
| JPH047638A (ja) | データの最適組み合わせ抽出装置 | |
| CN115257697A (zh) | 一种混动车辆能量管理及协同控制方法、系统及应用 | |
| US20070266307A1 (en) | Auto-layout of shapes | |
| WO2018120166A1 (zh) | 一种码垛的方法、装置及机器人 | |
| JPH07319742A (ja) | 論理削除データ物理削除方式 | |
| JP2020190896A (ja) | 情報処理装置、情報処理プログラム及び制御方法 | |
| JPH0744611A (ja) | 多目的最適化問題解決方法 | |
| JP2575664B2 (ja) | 画面制御方法 | |
| JPH01169634A (ja) | 制約関係に基づく変数の値の自動決定方法 | |
| CN119106167A (zh) | 一种聚类地图的异常区域自适应处理方法、设备和介质 | |
| JPH0876951A (ja) | ハイパーメディアのマップ表示システム及びマップ表示方法 | |
| CN114706855A (zh) | 一种兵棋推演场景回放方法、装置、设备及存储介质 | |
| JPS63318605A (ja) | Ｎｃパ−トプログラム生成装置 | |
| Menuet | Fractional Replicator Dynamics | |
| JPH0554082A (ja) | データベースシステム | |
| JPH033045A (ja) | 高速ファイル処理方式 | |
| CN119669189A (zh) | 一种数据迁移方法、装置、设备及介质 | |
| CN120235131A (zh) | 数据处理方法、设备、介质及产品 | |
| KR20220162096A (ko) | 심층신경망의 강화학습 에이전트의 합리적인 행동 결정 유도 방법 | |
| JP2008077331A (ja) | ３次元ｃａｄシステムの投影方法、モデル作成方法及びその装置 | |
| CN114942814A (zh) | 页面组件的聚焦方法、系统、终端设备及介质 | |
| CN118605519A (zh) | 一种仓库路径规划方法、装置和设备 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |