特許

J-GLOBAL ID：201103062451526013

状態遷移の概念を導入した問題解決演算装置および方法

発明者： 伊藤 裕康 ,  品川 明雄 ,  西村 利浩 ,  岡田 浩之 ,  安達 統衞 ,  大井 肇
出願人/特許権者： 富士通株式会社
代理人 (2件)： 大菅 義之 ,  久木元 彰
公報種別：特許公報
出願番号（国際出願番号）：特願2003-011357
公開番号（公開出願番号）：特開2003-248809
特許番号：特許第3697446号
出願日： 2003年01月20日
公開日（公表日）： 2003年09月05日
請求項（抜粋）：

【請求項1】 問題に対する解の探索空間を探索して最適解を求める問題解決演算装置であって、 前記問題および探索パラメータ値を入力する入力部と、 入力された問題に対する解候補となる染色体パターンの集団を格納するメモリと、 前記染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または該前世代の2つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施す複製/交叉処理部と、 前記染色体パターンの集団に対して、染色体パターンの指定位置の内容を前記探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す突然変異処理部と、 前記染色体パターンの集団の各染色体パターンの評価値を算出する評価値計算処理部と、 1つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、前記複製/交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が該標準偏差の規定値を下回るという第1の条件、1つの状態における探索実行回数が該探索実行回数の規定値を上回るという第2の条件、および評価値の伸び率が該伸び率の規定値を下回るという第3の条件がそれぞれ成立するか否かを判定する評価観測処理部と、 前記問題解決演算装置が探索を行う複数の状態の1つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、前記第1の条件が成立したとき、または、前記第2の条件と前記第3の条件が成立したときに、該遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を前記複製/交叉処理部および突然変異処理部に出力して該複製/交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで前記問題解決演算装置を該現在の状態から該次の状態へ遷移させて、該現在の状態とは異なる組み合わせの処理を前記染色体パターンの集団に適用する状態遷移を複数回繰り返し、該現在の状態および次の状態に共通する処理に対しては、該現在の状態と該次の状態とでそれぞれ異なる探索パラメータ値を適用する遷移制御処理部と、 探索終了条件が満たされたとき、探索により変更された染色体パターンの集団を出力する出力部とを備えることを特徴とする問題解決演算装置。

IPC (3件)：

G06N 3/00 ,  G06F 17/10 ,  G06N 3/12

FI (3件)：

G06N 3/00 550 C ,  G06F 17/10 Z ,  G06N 3/12