米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 富士通株式会社

発明の名称 最適化問題処理装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2003−16421(P2003−16421A)
公開日 平成15年1月17日(2003.1.17)
出願番号 特願2001−203208(P2001−203208)
出願日 平成13年7月4日(2001.7.4)
代理人 【識別番号】100074099
【弁理士】
【氏名又は名称】大菅 義之 (外1名)
発明者 佐藤 眞木彦
要約 課題
遺伝的アルゴリズムの効率を向上させることが課題である。

解決手段
遺伝子統計演算部24は、染色体集団記憶部22に格納された染色体集団の情報に基づいて確率モデルを生成し、確率モデル記憶部25に格納する。染色体発生部26は、確率モデルに基づいて新たな染色体を生成し、染色体選択部27は、染色体集団から確率モデルに基づいて染色体を選択する。GA演算部23は、染色体の評価関数の計算、染色体の選択、交叉、突然変異等の演算を行う。確率モデル制御部29は、確率モデルに関する動作を制御する。
特許請求の範囲
【請求項1】 遺伝的アルゴリズムを用いた最適化問題処理装置であって、個体集団の情報を格納する集団格納手段と、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納するモデル格納手段と、前記確率モデルを参照して新たな個体を生成し、生成した個体を次世代の個体として前記集団格納手段に格納する発生手段と、前記集団格納手段内の個体集団に対して遺伝的アルゴリズムの操作を施す操作手段と操作結果を出力する出力手段とを備えることを特徴とする最適化問題処理装置。
【請求項2】 遺伝的アルゴリズムを用いた最適化問題処理装置であって、個体集団の情報を格納する集団格納手段と、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納するモデル格納手段と、前記確率モデルを参照して前記個体集団から個体を選択し、選択した個体を次世代の個体として前記集団格納手段に格納する選択手段と、前記集団格納手段内の個体集団に対して遺伝的アルゴリズムの操作を施す操作手段と操作結果を出力する出力手段とを備えることを特徴とする最適化問題処理装置。
【請求項3】 遺伝的アルゴリズムを用いた最適化問題処理装置であって、複数の個体集団の情報をそれぞれ格納する複数の集団格納手段と、各個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納する複数のモデル格納手段と、前記確率モデルを参照して、前記複数の個体集団のうちの2つの集団を比較し、該2つの集団の少なくとも一方から個体を選択し、選択した個体を次世代の個体として、対応する集団格納手段に格納する選択手段と、前記複数の集団格納手段内の個体集団に対して、それぞれ遺伝的アルゴリズムの操作を施す複数の操作手段と操作結果を出力する出力手段とを備えることを特徴とする最適化問題処理装置。
【請求項4】 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムであって、個体集団の情報を、前記コンピュータの集団記憶部に格納し、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータのモデル記憶部に格納し、前記確率モデルを参照して新たな個体を生成し、生成した個体を次世代の個体として前記集団記憶部に格納し、前記集団記憶部内の個体集団に対して遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させるためのプログラム。
【請求項5】 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムであって、個体集団の情報を、前記コンピュータの集団記憶部に格納し、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータのモデル記憶部に格納し、前記確率モデルを参照して前記個体集団から個体を選択し、選択した個体を次世代の個体として前記集団記憶部に格納し、前記集団記憶部内の個体集団に対して遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させるためのプログラム。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、最適化問題を解くために、確率モデルに基づいて遺伝的アルゴリズム(Genetic Algorithm ,GA)の操作を行う処理装置に関する。
【0002】
【従来の技術】従来より、スケジューリングやパラメータ・フィッティング等の最適化問題を解くために、コンピュータを利用した様々なシステムが開発されてきた。特に、近年のコンピュータの性能の向上に伴い、従来のエキスパートシステム等で解決が困難であった問題を解決する方法として、シミュレーテッド・アニーリング等の確率的最適化手法が注目をあび、最適化の実用的な方法として研究がなされている。様々な確率的最適化手法の中でも、GAは特に着目されている。
【0003】また、昨今では、コンピュータの低価格化に伴う豊富なCPU(Central Processing Unit )パワーを、問題解決のためにいかに有効に使いこなすかが、課題となっている。GAは、困難な問題をコンピュータ・パワーで乗り切る方法としても有望である。
【0004】
【発明が解決しようとする課題】しかしながら、上述した従来のGAには、次のような問題がある。従来のGAでは、評価関数(適応度)だけを最適化の指標として用いているが、このような枠組は、GAの大きな長所であると同時に欠点ともなりうる。
【0005】GAは局所解にとらわれにくいと言われているが、GAは局所解から抜け出る機構を持ち合わせていない。このため、実用的な問題を解こうとすると、解空間と比較してGAの個体数が小さいため、実際には局所解に束縛される傾向がある。また、GAの性質として、解が局所最適解に陥ると、同じ遺伝子について評価関数の計算を何度も行わなければならず、非常に非能率的な枠組であるという問題がある。
【0006】GAには、1つの染色体集団を操作対象とする単純GAと、複数の染色体集団を操作対象とする並列GAの2種類がある。このうち、単純GAにおいては、解の適応度を用いて個々の染色体(配列)を識別/選択している。このとき、個体間の差異等の情報については特に考慮されておらず、解の適応度は、個体間の類似性の指標として適切ではない。このため、局所最適解から抜け出すのが困難となる。
【0007】また、並列GAにおいては、ある集団を代表する情報として最良の染色体の情報を用い、集団間で最良の染色体同士の適応度やハミング距離等を比較している。しかし、集団全体に関する情報は用いられていない。最良の染色体同士のハミング距離では、個々の配列間の距離の指標とはなっても、集団全体については何も判らない。
【0008】本発明の課題は、より効率の良いGAを用いた最適化問題処理装置を提供することである。
【0009】
【課題を解決するための手段】図1は、本発明の最適化問題処理装置の原理図である。図1の最適化問題処理装置は、集団格納手段11、モデル格納手段12、発生手段13、選択手段14、操作手段15、および出力手段16を備え、GAを用いて最適化問題の解を求める処理を行う。
【0010】本発明の第1の局面において、集団格納手段11は、個体集団の情報を格納し、モデル格納手段12は、個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納する。発生手段13は、確率モデルを参照して新たな個体を生成し、生成した個体を次世代の個体として集団格納手段11に格納する。操作手段15は、集団格納手段11内の個体集団に対してGAの操作を施し、出力手段16は、操作結果を出力する。
【0011】集団格納手段11は、個体集団の各個体(染色体)の配列データを格納し、モデル格納手段12は、個体集団内で、各対立遺伝子が各遺伝子座に出現する確率を、確率モデルのデータとして格納する。発生手段13が確率モデルに基づいて新たな個体を生成することで、それを含む次世代の個体集団が生成される。操作手段15は、こうして生成された個体集団に対して、選択、交叉、突然変異等の操作を施す。そして、所定の終了条件が満たされると、それまでの操作結果が処理結果として、出力手段16から出力される。
【0012】このような処理装置によれば、個体集団内に高い確率で出現する対立遺伝子を用いて、新たな個体を生成し、それを次世代に組み入れることができる。このような個体は良い評価値を有する可能性が高く、かつ、確率モデルの特徴を反映しているので、局所最適解から抜け出して効率の良い探索を行うことが可能となる。
【0013】また、本発明の第2の局面において、集団格納手段11は、個体集団の情報を格納し、モデル格納手段12は、個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納する。選択手段14は、確率モデルを参照して個体集団から個体を選択し、選択した個体を次世代の個体として集団格納手段11に格納する。操作手段15は、集団格納手段11内の個体集団に対してGAの操作を施し、出力手段16は、操作結果を出力する。
【0014】この場合、選択手段14が確率モデルに基づいて個体を選択することで、選択された個体を含む次世代の個体集団が生成される。操作手段15は、こうして生成された個体集団に対して、選択、交叉、突然変異等の操作を施す。そして、所定の終了条件が満たされると、それまでの操作結果が処理結果として、出力手段16から出力される。
【0015】このような処理装置によれば、個体集団内に高い確率で出現する対立遺伝子を多く含む個体を優先的に選択して、それを次世代に組み入れることができる。したがって、第1の局面における処理装置と同様に、局所最適解から抜け出して効率の良い探索を行うことが可能となる。
【0016】また、本発明の第3の局面において、集団格納手段11、モデル格納手段12、および操作手段15は、それぞれ複数個設けられる。複数の集団格納手段11は、複数の個体集団の情報をそれぞれ格納し、複数のモデル格納手段12の各々は、各個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納する。選択手段14は、確率モデルを参照して、複数の個体集団のうちの2つの集団を比較し、それらのうち少なくとも一方から個体を選択し、選択した個体を次世代の個体として、対応する集団格納手段11に格納する。複数の操作手段15は、複数の集団格納手段11内の個体集団に対して、それぞれGAの操作を施し、出力手段16は、操作結果を出力する。
【0017】各モデル格納手段12は、対応する集団格納手段11内の個体集団に関する確率モデルのデータを格納し、各操作手段15は、対応する集団格納手段11内の個体集団を対象として、GAの操作を施す。選択手段14が、各個体集団の確率モデルに基づいて2つの集団を比較し、一方の集団から個体を選択することで、選択された個体を含む次世代の個体集団が生成される。こうして生成された個体集団に対して、対応する操作手段15が、選択、交叉、突然変異等の操作を施す。そして、所定の終了条件が満たされると、それまでの操作結果が処理結果として、出力手段16から出力される。
【0018】このような処理装置によれば、集団全体の情報を反映する確率モデルを用いることで、並列GAにおける2つの個体集団の類似度を正確に判定することができる。また、2つの個体集団が類似している場合に、それらが乖離していくように個体を選択することで、それらの集団を互いに異なる探索領域に振り分けることができる。これにより、並列GAの効率を向上させることが可能となる。
【0019】図1の集団格納手段11は、例えば、後述する図2の染色体集団記憶部22および後述する図9のGA部32に対応する。また、図1のモデル格納手段12は、例えば、図2の確率モデル記憶部25および図9の確率モデル記憶部33に対応する。また、図1の発生手段13は、例えば、図2の染色体発生部26に対応し、図1の選択手段14は、例えば、図2の染色体選択部27および図9の確率モデル間制御部34に対応する。また、図1の操作手段15および出力手段16はいずれも、例えば、図2のGA演算部23および図9のGA部32に対応する。
【0020】
【発明の実施の形態】以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。図2は、単純GA(SingleGA,SGA)を用いた最適化問題処理装置の構成図である。図2の処理装置は、初期染色体発生部21、染色体集団記憶部22、GA演算部23、遺伝子統計演算部24、確率モデル記憶部25、染色体発生部26、染色体選択部27、終了判定部28、および確率モデル制御部29を備える。実線の矢印は、処理データのやり取りを表し、破線の矢印は、制御データのやり取りを表す。
【0021】初期染色体発生部21は、GAの染色体集団の初期化を行って、各染色体の初期値を生成する。染色体集団記憶部22は、染色体集団の情報を記憶し、GA演算部23が使用する記憶領域も含む。GA演算部23は、染色体の評価関数の計算、染色体の選択、交叉、突然変異等のGA演算を行う。
【0022】遺伝子統計演算部24は、染色体集団記憶部22に格納された染色体集団の情報に基づいて統計計算を行って、確率モデルを生成し、確率モデル記憶部25は、生成された確率モデルを記憶する。染色体発生部26は、確率モデルに基づいて新たな染色体を生成し、染色体選択部27は、染色体集団から確率モデルに基づいて染色体を選択する。
【0023】終了判定部28は、GA演算部23による探索を終了するか継続するかを判定し、確率モデル制御部29は、染色体集団記憶部22、GA演算部23、遺伝子統計演算部24、確率モデル記憶部25、染色体発生部26、および染色体選択部27の確率モデルに関する動作を制御する。
【0024】図3は、図2の処理装置によるGA処理のフローチャートである。まず、初期染色体発生部21は、初期の染色体集団を生成し、染色体集団記憶部22に格納する(ステップS1)。次に、GA演算部23は、染色体集団記憶部22の各染色体について評価関数の値を計算し(ステップS2)、確率モデル制御部29は、確率モデル生成のための条件が成立したか否かを判定する(ステップS3)。この条件としては、例えば、GAの所定の世代に到達したことが用いられる。この所定の世代は、あらかじめ決められた世代間隔等を用いて設定される。
【0025】条件が成立しなければ、次に、終了判定部28が、あらかじめ設定された終了条件が成立したか否かを判定する(ステップS4)。この終了条件としては、GAの世代数が一定値に達したこと、最良の染色体の評価関数値(評価値)が一定値に達したこと、ユーザによる終了指示の割り込みが発生したこと等が用いられる。
【0026】終了条件が成立しなければ、次に、GA演算部23は、通常のGAの最適化演算を行う。ここでは、染色体集団記憶部22の染色体集団に選択操作を施し(ステップS9)、交叉操作を施し(ステップS10)、突然変異操作を施して(ステップS11)、ステップS2以降の処理を繰り返す。
【0027】こうしてGA演算が繰り返され、ステップS3において確率モデル生成のための条件が成立すれば、確率モデル制御部29が割り込む。そして、確率モデル制御部29の制御に従って、遺伝子統計演算部24は、染色体集団の確率モデルを生成し、確率モデル記憶部25に格納する(ステップS5)。これにより、あらかじめ決められた世代間隔で、確率モデルが更新される。
【0028】次に、確率モデル制御部29は、染色体の発生と選択のいずれを行うかを決定する(ステップS6)。いずれを行うかは、ユーザからの指示に基づいて決定してもよく、あらかじめ設定された制御情報に基づいて決定してもよい。
【0029】染色体発生の場合、染色体発生部26は、確率モデル記憶部25の確率モデルを用いて新たな染色体を生成し、染色体集団記憶部22の染色体集団に組み入れる(ステップS7)。新たな染色体としては、確率モデルのコンセンサス配列(最も確率の高い配列)や次善のコンセンサス配列等が用いられる。
【0030】また、染色体選択の場合、染色体選択部27は、確率モデルをベースにして各染色体を評価し、比較的良い評価の染色体を選択して、GA演算部23に渡す(ステップS8)。その後、GA演算部23は、ステップS9以降の処理を行い、ステップS4において終了条件が成立すれば、その時点における評価値の良い染色体を処理結果として出力し、処理を終了する。
【0031】次に、図4から図8までを参照しながら、SGAの具体例を説明する。最適化問題として、次式で表される評価関数f(xi )(i=1,2,3,4)を最小化する問題を考える。
【0032】
【数1】

【0033】ここで、xi の取り得る値の範囲は0≦xi ≦3の整数である。この評価関数f(xi )は、各iについて、xi =1で最小値0になる。この問題を解くために、xi を遺伝子(gene)とし、対立遺伝子を0〜3の整数とする。このとき、各染色体の配列は、[0,1,2,3]∈x1 ,x2 ,x3 ,x4 の4つの整数の組(x1 ,x2 ,x3 ,x4 )で表される。個体数を5に設定した染色体集団を乱数で初期化して、最適化演算を行った結果、ある世代での染色体集団とそれに対応する評価関数値が、図4のようになったものとする。この染色体集団からは、図5に示すような確率モデルが生成される。
【0034】図5の確率モデルは、各遺伝子座における各対立遺伝子の出現確率を表している。例えば、x1 については、図4の染色体1〜5のうち、染色体2のみが対立遺伝子“0”を持つ。したがって、x1 における対立遺伝子“0”の出現確率は、1/5=0.2となる。また、x1 =1となるものは、染色体1と染色体4の2つである。したがって、x1 における対立遺伝子“1”の出現確率は、2/5=0.4となる。
【0035】同様にして、x1 における対立遺伝子“2”および“3”の出現確率は、それぞれ0.4および0.0となり、x1 におけるすべての対立遺伝子の出現確率の和は1となる。他の遺伝子座における出現確率についても同様である。
【0036】染色体発生部26は、この確率モデルを参照して、高い出現確率を有する対立遺伝子同士を組み合わせた新たな染色体(コンセンサス配列)を生成する。ここでは、各遺伝子座において最高の出現確率(0.4または0.6)の対立遺伝子を選択することで、図6のようなコンセンサス配列が生成される。
【0037】図6において、各染色体の出現確率は、図5に示した対立遺伝子の出現確率を、すべての遺伝子座について乗算した結果に対応する。また、log−oddsは、対数オッズ比と呼ばれ、次式により定義される。
【0038】
【数2】

【0039】一般に、対数オッズ比の対数の底は任意であるが、図6の計算では底として2を用いている。また、(2)式の右辺のPi は、xi における対立遺伝子の出現確率を表し、総和はi=1〜4について行われる。
【0040】この対数オッズ比は、バックグラウンドの確率モデルと対比した、対象とする確率モデルにおける各個体の適合度を表すスコアであり、このスコアを参照することで、各個体が対象とする確率モデルにフィットしているか否かを判定することができる。ここでは、対立遺伝子が4つあり、等確率のバックグラウンドの確率モデルを想定しているため、(2)式の右辺にlog(1/4)が現れている。
【0041】染色体発生部26は、これらのコンセンサス配列のうち、評価値の良い染色体を元の染色体集団に戻す。この場合、コンセンサス配列の数が集団の個体数よリ多いため、最良(最小)の評価値の配列“1110”を戻せばよい。また、この例では、同じ確率のコンセンサス配列が8個生成されたが、通常は、確率最大のコンセンサス配列の数は集団の個体数よりも小さくなる。
【0042】図4の染色体集団と最良のコンセンサス配列について、図5の確率モデルに基づき出現確率と対数オッズ比を計算すると、図7のようになる。染色体1〜5のうち、評価値が最悪のものは染色体2、3、5の3つであるから、これらのうちのいずれかとコンセンサス配列“1110”を入れ換えることで、確率モデルを加味した新たな染色体集団が生成される。
【0043】このように、染色体集団から作成した確率モデルを用いて、評価値の高い新たな染色体を作成することが可能になる。確率モデルで作成した染色体は、元の集団のビルディング・ブロックを保持しているため、これから生成される新しい染色体は、さらに良い解を与えると考えられる。
【0044】また、(1)式の評価関数f(xi )に対して、対数オッズ比を加味した実効評価関数fe(xi )は、例えば、次式により定義される。
fe(xi )={1/(f(xi )+0.01)}
*log−odds (3)
これにより、f(xi )の最小化問題がfe(xi )の最大化問題に置き換えられ、log−oddsの値を乗算することで、確率モデルに基づく評価が加味される。
【0045】染色体選択部27は、染色体集団の中から実効評価関数値が高い所定数の染色体を選択して、GA演算部23に渡す。このとき、集団内の染色体を実効評価関数値が高い順にソートして、上位から所定数のものを選択する。
【0046】図7に示した各染色体について、(3)式の実効評価関数値を計算すると、図8のようになる。例えば、染色体2と染色体3を比較すると、元の評価関数値は同じであるが、実効評価関数値は異なっている。この場合、実効評価関数値に従って選択を行うことで、より出現確率が高い個体が優先的に選択されるようになる。
【0047】このように、確率モデルに基づく対数オッズ比の評価とGAの評価関数を組み合わせた実効評価関数を用いることで、GAに確率モデルを付加することができ、より良い染色体の評価が可能となる。
【0048】次に、図9は、並列GA(ParallelGA,PGA)を用いた最適化問題処理装置の構成図である。図9の処理装置は、GA間制御部31、GA部32、確率モデル記憶部33、確率モデル間制御部34、および距離計算部35を備える。ここでは、GA部32と確率モデル記憶部33が3つずつ示されているが、実際には、並列に処理される染色体集団の数(任意)だけ設けられる。
【0049】各GA部32は、図2の初期染色体発生部21、染色体集団記憶部22、GA演算部23、および終了判定部28に対応し、GAを用いた最適化を行う。GA間制御部31は、通常の並列GAと同様に、GA部32の間の制御(初期化、世代の進歩、終了判定等)を行う。
【0050】各確率モデル記憶部33は、対応するGA部32の染色体集団の確率モデルを記憶し、確率モデルの生成や演算等に使用される記憶領域も含む。確率モデル間制御部34は、確率モデルの生成と確率モデル間の演算/制御を行い、距離計算部35は、確率モデル間の距離計算(類似度計算)を行う。GA間制御部31と確率モデル間制御部34は、互いに連携しながら制御を行う。
【0051】図10は、図9の処理装置によるGA処理のフローチャートである。まず、GA部32は、初期の染色体集団を生成し(ステップS11)、並列に1世代の最適化演算を行う(ステップS12)。次に、確率モデル間制御部34は、確率モデル生成のための条件が成立したか否かを判定する(ステップS3)。この条件については、図2の処理装置の場合と同様である。
【0052】条件が成立しなければ、次に、各GA部32が、あらかじめ設定された終了条件が成立したか否かを判定する(ステップS14)。この終了条件についても、図2の処理装置の場合と同様である。
【0053】終了条件が成立しなければ、GA部32は、ステップS12以降の処理を繰り返し、ステップS13において確率モデル生成のための条件が成立すれば、確率モデル間制御部34が割り込む。そして、各GA部32の染色体集団について遺伝子統計演算を行って、各染色体集団の確率モデルを生成し、確率モデル記憶部33に格納する(ステップS15)。
【0054】次に、距離計算部35は、確率モデル間制御部34の指示に従って、確率モデル間の相関等(距離)を計算する(ステップS16)。そして、確率モデル間制御部34は、距離計算の結果に基づいて各染色体集団の実効評価関数(実効適応度)を設定し、実効評価関数を用いて各染色体を評価する。そして、各染色体集団から比較的良い評価の染色体を選択し、各GA部32に渡す(ステップS17)。
【0055】その後、GA部32は、ステップS12以降の処理を行い、ステップS14において終了条件が成立すれば、処理を終了する。そして、GA間制御部31は、その時点における評価値の良い染色体を各GA部32から収集して、処理結果として出力する。
【0056】ここで、PGAの具体例として、次式で表される評価関数f(xi )(i=1,2,3,4)を最小化する問題を考える。
【0057】
【数3】

【0058】xi の取り得る値の範囲は0≦xi ≦3の整数である。この評価関数f(xi)は、各iについて、xi =0、xi =1、またはxi =2で最小値0になる。このとき、並列GAは、例えば、以下のように動作する。
【0059】各GA部32は、並列に最適化演算を行い、GA間制御部31が、適宜、各染色体集団の初期化を行い、設定された世代間隔で割り込み、適応度の比較等を行う。また、確率モデル間制御部34は、設定された世代間隔で割り込み、各染色体集団の確率モデルを生成する。
【0060】例えば、3つの染色体集団を用いたPGAにおいて、図11のような3つの確率モデルP1、P2、P3が生成されたものとする。このとき、距離計算部35は、確率モデル間制御部34の指示に従って、確率モデル間の距離として、次のような相対エントロピー(Kullback-Leibler divergence )を計算する。
【0061】
【数4】

【0062】ここで、PおよびQは、比較される2つの確率モデルを表し、H(P‖Q)は、PとQの相対エントロピーを表す。(5)式の右辺の総和は、i=1〜4およびxi =0〜3について行われる。例えば、図11の確率モデルP1とP2の相対エントロピーは、次のように計算される。
H(P1‖P2)
=0.2log(0.2/0.4)+0.4log(0.4/0.4)
+0.4log(0.4/0.2)+0.4log(0.4/0.4)
+0.2log(0.2/0.4)+0.4log(0.4/0.2)
+0.4log(0.4/0.2)+0.4log(0.4/0.4)
+0.2log(0.2/0.2)+0.4log(0.4/0.2)
+0.2log(0.2/0.4)+0.2log(0.2/0.2)
+0.2log(0.2/0.2)
=0.2log(1/2)+0.4log(2)+0.2log(1/2)
+0.4log(2)+0.4log(2)+0.4log(2)
+0.2log(1/2)
=log(2) (6)
この相対エントロピーは、2つの確率モデルが等しければ0になり、違いが大きければ値が大きくなる。2つの確率モデルの類似度は、対応する染色体集団の間の類似度を反映しているため、相対エントロピーを用いて集団間の類似度を判定することができる。
【0063】確率モデル間制御部34は、例えば、相対エントロピーが所定のしきい値より小さければ、2つの集団が類似していると判定し、それが所定のしきい値以上であれば、2つの集団は類似していないと判定する。
【0064】2つの集団が互いに類似している場合、その一方の集団の評価関数を、他方の集団に基づく対数オッズ比をペナルティとして用いて変更することで、前者の集団を類似性がない領域に誘導することが可能である。
【0065】ここで、図12に示すような染色体集団を用いて、ペナルティの計算方法の例を説明する。図12は、染色体集団と(4)式の評価関数f(xi )の計算結果を示している。この染色体集団の確率モデルは、図11の確率モデルP1に一致している。確率モデルP1とP2が類似しているとき、各染色体について、(2)式の対数オッズ比を確率モデルP2に基づいて計算すると、以下のようになる。
染色体1(1130)
log−odds=log(0.4)+log(0.4)+log(0.2)
+log(0.2)−4log(1/4)
=0.712287染色体2(0312)
log−odds=log(0.4)+log(0.2)+log(0.4)
+log(0.2)−4log(1/4)
=0.712287染色体3(2103)
log−odds=log(0.2)+log(0.4)+log(0.2)
+log(0.2)−4log(1/4)
=−0.287713染色体4(1210)
log−odds=log(0.4)+log(0.4)+log(0.4)
+log(0.2)−4log(1/4)
=1.712287染色体5(2301)
log−odds=log(0.2)+log(0.2)+log(0.2)
+log(0.4)−4log(1/4)
=−0.287713これらの対数オッズ比は、各個体の確率モデルP2に対する適合度を表しており、その値が大きいほど確率モデルP2にフィットしていることを意味する。そこで、対数オッズ比が大きい個体の評価を低くするために、評価関数f(xi )に対して、次式のような実効評価関数fe(xi )を定義する。
fe(xi )=f(xi )+α*log−odds (7)
ここで、αは定数である。確率モデル間制御部34は、このfe(xi )を用いて各染色体を評価し、評価値の良い所定数の染色体を選択して、対応するGA部32に渡す。この場合、確率モデルP2にフィットしている個体のfe(xi)は、f(xi )より大きくなり、評価値が悪くなる。このため、結果として、対応するGA部32は、確率モデルP2から乖離した他の探索点をより多く探索するようになる。
【0066】α=10.0とおいて、図12の各染色体について(7)式の実効評価関数値を計算すると、図13のようになる。また、図11の確率モデルP2の分布からは、この確率モデルの集団が 外1 を最小にする点の付近に存在することが読【0067】
【外1】

【0068】み取れる。図13では、最も良い評価関数値の染色体4は、この付近にある個体であり、その対数オッズ比は最も大きくなっている。したがって、実効評価関数値による評価は大幅に悪くなっている。
【0069】一方、確率モデルP2から乖離した領域にある染色体3および染色体5は、対数オッズ比が小さいため、実効評価関数値による評価は良くなっている。このように、(7)式の実効評価関数を用いることで、ある集団の探索範囲から他の集団の近傍を排除する効果がある。
【0070】以上説明したように、複数の染色体集団を有するPGAにおいて、確率モデルを用いて集団同士を比較し、比較結果に基づいて探索領域の競合を調整することで、これらの集団を互いに異なる探索領域に振り分けることができる。したがって、全体としての探索効率が向上する。
【0071】次に、図14から図17までを参照しながら、図2および図9の処理装置が航空ダイヤのスケジューリングを行う場合の処理を説明する。図14は、この場合のGA演算部23およびGA部32が評価関数(適応度)を計算するための構成を示している。図14のフライトオブジェクト41とフライトスケジュール管理部42は、先願の「オブジェクト指向遺伝的アルゴリズムを用いた最適化方法及び装置」(特開平11−53337)に示されているように、オブジェクト指向プログラミングによりプログラムされる。
【0072】フライトスケジュール管理部42は、与えられた染色体データをデコードしてスケジューリングのパラメータを求め、得られたパラメータに基づくシミュレーションを指示するメッセージをフライトオブジェクト41に送る。
【0073】フライトオブジェクト21は、空港やスポットのデータを保持しており、渡されたパラメータに基づいてフライトシミュレーションを行って、得られたシミュレーション結果をフライトスケジュール管理部42に返す。
【0074】フライトスケジュール管理部42は、返されたシミュレーション結果から所定のアルゴリズムにより適応度を計算し、それを出力する。また、終了条件が満たされると、その時点で最高の適応度を持つ染色体をデコードし、得られたパラメータにより記述される航空ダイヤをスケジュール結果として出力する。
【0075】航空ダイヤに含まれる各便の便データは、例えば、図15に示すように、便名(Flight-ID )、希望出発時刻(Depart-time )、時間幅(Time-Window )、および割当可能機種(Available-Ship-Type )の情報により指定される。ここでは、便名は#3であり、希望出発時刻は10:00であり、時間幅は−20分および+10分である。これは、#3便の出発時刻が9:40〜10:10の間に制限されることを意味している。また、割当可能機種(Ship-Type )はB−747、B−777、およびB−767に制限される。
【0076】この場合、これらの制限を守りながら、割当不能な便が発生しないように、すべての便の出発時刻と機種を決定することがスケジューリングの目的となる。今、航空ダイヤに含まれる便の便名が#1,#2,#3,...,#lastであるとすると、この問題を扱うための染色体データは、例えば、図16に示すようにコーディングされる。
【0077】図16の染色体において、各便のデータはTimeおよびShip−Typeの2つの遺伝子座を有し、それらの対立遺伝子は0〜255であるものとする。ここで、Timeの遺伝子の値をtとし、Ship−Typeの遺伝子の値をsとすると、#3便の出発時刻および機種は次式により与えられる。
出発時刻=(t%7)に対応する時刻 (8)
機種=(s%3)に対応する機種 (9)
“%”は剰余演算を表し、例えば、t%7はtを7で割ったときの剰余(0,1,2,3,4,5,6)に対応する。s%3についても同様である。また、得られた剰余の値と時刻/機種との対応関係は、図17に示すようになる。図17では、出発時刻の候補として、9:40〜10:10を5分間隔で区切って得られる7つの時刻が用いられており、それぞれの時刻に対して1つの剰余の値が対応付けられている。また、3つの割当可能機種B−747、B−777、およびB−767のそれぞれに対して、1つの剰余の値が対応付けられている。
【0078】このような対応関係を#1〜#lastのすべての便に対して定義すれば、(8)、(9)式と同様の剰余演算により、染色体データをデコードすることができる。フライトスケジュール管理部42は、こうして得られたすべての便の出発時刻、割当機種等のパラメータをフライトオブジェクト41に渡し、フライトオブジェクト41は、それらのパラメータにより記述される航空ダイヤのシミュレーションを行う。適応度は、得られたシミュレーション結果に応じて動的に計算される。
【0079】このような航空ダイヤのスケジューリング以外にも、配送計画問題、人員配置問題、工場等におけるショップスケジューリング等の様々な最適化問題に対して、本発明を適用することができる。
【0080】ところで、図2および図9の処理装置は、例えば、図18に示すような情報処理装置(コンピュータ)を用いて構成することができる。図18の情報処理装置は、CPU(中央処理装置)51、メモリ52、入力装置53、出力装置54、外部記憶装置55、媒体駆動装置56、およびネットワーク接続装置57を備え、それらはバス58により互いに接続されている。
【0081】メモリ52は、例えば、ROM(read only memory)、RAM(random access memory)等を含み、処理に用いられるプログラムとデータを格納する。CPU51は、メモリ52を利用してプログラムを実行することにより、必要な処理を行う。
【0082】例えば、図2の初期染色体発生部21、GA演算部23、遺伝子統計演算部24、染色体発生部26、染色体選択部27、終了判定部28、および確率モデル制御部29と、図9のGA間制御部31、GA部32、確率モデル間制御部34、および距離計算部35は、プログラムにより記述されたソフトウェアコンポーネントとして、メモリ52の特定のプログラムコードセグメントに格納される。
【0083】また、図2の染色体集団記憶部22および確率モデル記憶部25と、図9の確率モデル記憶部33は、メモリ52の特定の記憶領域に対応する。図9に示した並列GAの場合、複数のGA部32は、マルチタスク処理により、並行して最適化演算を行う。
【0084】入力装置53は、例えば、キーボード、ポインティングデバイス、タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力装置54は、例えば、ディスプレイ、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【0085】外部記憶装置55は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。情報処理装置は、この外部記憶装置55に、上述のプログラムとデータを保存しておき、必要に応じて、それらをメモリ52にロードして使用する。
【0086】媒体駆動装置56は、可搬記録媒体59を駆動し、その記録内容にアクセスする。可搬記録媒体59としては、メモリカード、フロッピー(登録商標)ディスク、CD−ROM(compact disk read only memory )、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。ユーザは、この可搬記録媒体59に上述のプログラムとデータを格納しておき、必要に応じて、それらをメモリ52にロードして使用する。
【0087】ネットワーク接続装置57は、LAN(local area network)等の任意の通信ネットワークに接続され、通信に伴うデータ変換を行う。また、情報処理装置は、上述のプログラムとデータをネットワーク接続装置57を介して他の装置から受け取り、必要に応じて、それらをメモリ52にロードして使用する。
【0088】図19は、図18の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。可搬記録媒体59やサーバ60のデータベース61に保存されたプログラムとデータは、メモリ52にロードされる。このとき、サーバ60は、プログラムとデータを搬送する搬送信号を生成し、ネットワーク上の任意の伝送媒体を介して情報処理装置に送信する。そして、CPU51は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【0089】また、図9の最適化問題処理装置は、図18のような情報処理装置以外にも、複数のプロセッシングエレメント(PE)を搭載した並列計算機により実現することができる。この場合、各PEが各GA部32のプログラムを実行することで、並列処理が行われる。
【0090】(付記1) 遺伝的アルゴリズムを用いた最適化問題処理装置であって、個体集団の情報を格納する集団格納手段と、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納するモデル格納手段と、前記確率モデルを参照して新たな個体を生成し、生成した個体を次世代の個体として前記集団格納手段に格納する発生手段と、前記集団格納手段内の個体集団に対して遺伝的アルゴリズムの操作を施す操作手段と操作結果を出力する出力手段とを備えることを特徴とする最適化問題処理装置。
(付記2) 前記発生手段は、1つの個体の複数の遺伝子座について、高い出現確率を有する対立遺伝子同士を組み合わせることで、前記新たな個体を生成することを特徴とする付記1記載の最適化問題処理装置。
(付記3) 遺伝的アルゴリズムを用いた最適化問題処理装置であって、個体集団の情報を格納する集団格納手段と、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納するモデル格納手段と、前記確率モデルを参照して前記個体集団から個体を選択し、選択した個体を次世代の個体として前記集団格納手段に格納する選択手段と、前記集団格納手段内の個体集団に対して遺伝的アルゴリズムの操作を施す操作手段と操作結果を出力する出力手段とを備えることを特徴とする最適化問題処理装置。
(付記4) 前記選択手段は、前記確率モデルに基づく実効評価関数を用いて前記個体集団の個体を評価し、評価の良い順に所定数の個体を選択することを特徴とする付記3記載の最適化問題処理装置。
(付記5) 遺伝的アルゴリズムを用いた最適化問題処理装置であって、複数の個体集団の情報をそれぞれ格納する複数の集団格納手段と、各個体集団の対立遺伝子の出現確率を表す確率モデルの情報を格納する複数のモデル格納手段と、前記確率モデルを参照して、前記複数の個体集団のうちの2つの集団を比較し、該2つの集団の少なくとも一方から個体を選択し、選択した個体を次世代の個体として、対応する集団格納手段に格納する選択手段と、前記複数の集団格納手段内の個体集団に対して、それぞれ遺伝的アルゴリズムの操作を施す複数の操作手段と操作結果を出力する出力手段とを備えることを特徴とする最適化問題処理装置。
(付記6) 前記選択手段は、前記2つの集団のうち一方の集団の確率モデルに基づく実効評価関数を用いて、該2つの集団のうち他方の集団の個体を評価し、該他方の集団から評価の良い順に所定数の個体を選択することを特徴とする付記5記載の最適化問題処理装置。
(付記7) 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムであって、個体集団の情報を、前記コンピュータの集団記憶部に格納し、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータのモデル記憶部に格納し、前記確率モデルを参照して新たな個体を生成し、生成した個体を次世代の個体として前記集団記憶部に格納し、前記集団記憶部内の個体集団に対して遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させるためのプログラム。
(付記8) 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムであって、個体集団の情報を、前記コンピュータの集団記憶部に格納し、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータのモデル記憶部に格納し、前記確率モデルを参照して前記個体集団から個体を選択し、選択した個体を次世代の個体として前記集団記憶部に格納し、前記集団記憶部内の個体集団に対して遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させるためのプログラム。
(付記9) 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムであって、複数の個体集団の情報を、前記コンピュータの複数の集団記憶部にそれぞれ格納し、各個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータの複数のモデル格納手段に格納し、前記確率モデルを参照して、前記複数の個体集団のうちの2つの集団の確率モデルを比較し、該2つの集団の少なくとも一方から個体を選択し、選択した個体を次世代の個体として、対応する集団記憶部に格納し、前記複数の集団記憶部内の個体集団に対して、それぞれ遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させるためのプログラム。
(付記10) 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムを記録した記録媒体であって、該プログラムは、個体集団の情報を、前記コンピュータの集団記憶部に格納し、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータのモデル記憶部に格納し、前記確率モデルを参照して新たな個体を生成し、生成した個体を次世代の個体として前記集団記憶部に格納し、前記集団記憶部内の個体集団に対して遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
(付記11) 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムを記録した記録媒体であって、該プログラムは、個体集団の情報を、前記コンピュータの集団記憶部に格納し、前記個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータのモデル記憶部に格納し、前記確率モデルを参照して前記個体集団から個体を選択し、選択した個体を次世代の個体として前記集団記憶部に格納し、前記集団記憶部内の個体集団に対して遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
(付記12) 遺伝的アルゴリズムを用いて最適化問題を処理するコンピュータのためのプログラムを記録した記録媒体であって、該プログラムは、複数の個体集団の情報を、前記コンピュータの複数の集団記憶部にそれぞれ格納し、各個体集団の対立遺伝子の出現確率を表す確率モデルの情報を、前記コンピュータの複数のモデル格納手段に格納し、前記確率モデルを参照して、前記複数の個体集団のうちの2つの集団の確率モデルを比較し、該2つの集団の少なくとも一方から個体を選択し、選択した個体を次世代の個体として、対応する集団記憶部に格納し、前記複数の集団記憶部内の個体集団に対して、それぞれ遺伝的アルゴリズムの操作を施し、操作結果を出力する処理を前記コンピュータに実行させることを特徴とするコンピュータ読み取り可能な記録媒体。
【0091】
【発明の効果】本発明によれば、GAの染色体集団から生成した確率モデルを用いて、GA操作を効率化するような染色体を次世代に組み入れることが可能となる。したがって、確率モデルを用いない場合より解の探索効率が向上する。
【0092】また、並列GAの各染色体集団の確率モデルを用いて集団間の差異を評価することで、これらの集団を異なる領域に分散させることが可能となる。したがって、並列GAの探索効率が向上する。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013