JP2003016421A - 最適化問題処理装置 - Google Patents
最適化問題処理装置Info
- Publication number
- JP2003016421A JP2003016421A JP2001203208A JP2001203208A JP2003016421A JP 2003016421 A JP2003016421 A JP 2003016421A JP 2001203208 A JP2001203208 A JP 2001203208A JP 2001203208 A JP2001203208 A JP 2001203208A JP 2003016421 A JP2003016421 A JP 2003016421A
- Authority
- JP
- Japan
- Prior art keywords
- individual
- population
- chromosome
- model
- storage unit
- 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.)
- Pending
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】
【課題】 遺伝的アルゴリズムの効率を向上させること
が課題である。 【解決手段】 遺伝子統計演算部２４は、染色体集団記
憶部２２に格納された染色体集団の情報に基づいて確率
モデルを生成し、確率モデル記憶部２５に格納する。染
色体発生部２６は、確率モデルに基づいて新たな染色体
を生成し、染色体選択部２７は、染色体集団から確率モ
デルに基づいて染色体を選択する。ＧＡ演算部２３は、
染色体の評価関数の計算、染色体の選択、交叉、突然変
異等の演算を行う。確率モデル制御部２９は、確率モデ
ルに関する動作を制御する。
が課題である。 【解決手段】 遺伝子統計演算部２４は、染色体集団記
憶部２２に格納された染色体集団の情報に基づいて確率
モデルを生成し、確率モデル記憶部２５に格納する。染
色体発生部２６は、確率モデルに基づいて新たな染色体
を生成し、染色体選択部２７は、染色体集団から確率モ
デルに基づいて染色体を選択する。ＧＡ演算部２３は、
染色体の評価関数の計算、染色体の選択、交叉、突然変
異等の演算を行う。確率モデル制御部２９は、確率モデ
ルに関する動作を制御する。
Description
【０００１】
【発明の属する技術分野】本発明は、最適化問題を解く
ために、確率モデルに基づいて遺伝的アルゴリズム（Ge
netic Algorithm ，ＧＡ）の操作を行う処理装置に関す
る。
ために、確率モデルに基づいて遺伝的アルゴリズム（Ge
netic Algorithm ，ＧＡ）の操作を行う処理装置に関す
る。
【０００２】
【従来の技術】従来より、スケジューリングやパラメー
タ・フィッティング等の最適化問題を解くために、コン
ピュータを利用した様々なシステムが開発されてきた。
特に、近年のコンピュータの性能の向上に伴い、従来の
エキスパートシステム等で解決が困難であった問題を解
決する方法として、シミュレーテッド・アニーリング等
の確率的最適化手法が注目をあび、最適化の実用的な方
法として研究がなされている。様々な確率的最適化手法
の中でも、ＧＡは特に着目されている。
タ・フィッティング等の最適化問題を解くために、コン
ピュータを利用した様々なシステムが開発されてきた。
特に、近年のコンピュータの性能の向上に伴い、従来の
エキスパートシステム等で解決が困難であった問題を解
決する方法として、シミュレーテッド・アニーリング等
の確率的最適化手法が注目をあび、最適化の実用的な方
法として研究がなされている。様々な確率的最適化手法
の中でも、ＧＡは特に着目されている。
【０００３】また、昨今では、コンピュータの低価格化
に伴う豊富なＣＰＵ（Central Processing Unit ）パワ
ーを、問題解決のためにいかに有効に使いこなすかが、
課題となっている。ＧＡは、困難な問題をコンピュータ
・パワーで乗り切る方法としても有望である。
に伴う豊富なＣＰＵ（Central Processing Unit ）パワ
ーを、問題解決のためにいかに有効に使いこなすかが、
課題となっている。ＧＡは、困難な問題をコンピュータ
・パワーで乗り切る方法としても有望である。
【０００４】
【発明が解決しようとする課題】しかしながら、上述し
た従来のＧＡには、次のような問題がある。従来のＧＡ
では、評価関数（適応度）だけを最適化の指標として用
いているが、このような枠組は、ＧＡの大きな長所であ
ると同時に欠点ともなりうる。
た従来のＧＡには、次のような問題がある。従来のＧＡ
では、評価関数（適応度）だけを最適化の指標として用
いているが、このような枠組は、ＧＡの大きな長所であ
ると同時に欠点ともなりうる。
【０００５】ＧＡは局所解にとらわれにくいと言われて
いるが、ＧＡは局所解から抜け出る機構を持ち合わせて
いない。このため、実用的な問題を解こうとすると、解
空間と比較してＧＡの個体数が小さいため、実際には局
所解に束縛される傾向がある。また、ＧＡの性質とし
て、解が局所最適解に陥ると、同じ遺伝子について評価
関数の計算を何度も行わなければならず、非常に非能率
的な枠組であるという問題がある。
いるが、ＧＡは局所解から抜け出る機構を持ち合わせて
いない。このため、実用的な問題を解こうとすると、解
空間と比較してＧＡの個体数が小さいため、実際には局
所解に束縛される傾向がある。また、ＧＡの性質とし
て、解が局所最適解に陥ると、同じ遺伝子について評価
関数の計算を何度も行わなければならず、非常に非能率
的な枠組であるという問題がある。
【０００６】ＧＡには、１つの染色体集団を操作対象と
する単純ＧＡと、複数の染色体集団を操作対象とする並
列ＧＡの２種類がある。このうち、単純ＧＡにおいて
は、解の適応度を用いて個々の染色体（配列）を識別／
選択している。このとき、個体間の差異等の情報につい
ては特に考慮されておらず、解の適応度は、個体間の類
似性の指標として適切ではない。このため、局所最適解
から抜け出すのが困難となる。
する単純ＧＡと、複数の染色体集団を操作対象とする並
列ＧＡの２種類がある。このうち、単純ＧＡにおいて
は、解の適応度を用いて個々の染色体（配列）を識別／
選択している。このとき、個体間の差異等の情報につい
ては特に考慮されておらず、解の適応度は、個体間の類
似性の指標として適切ではない。このため、局所最適解
から抜け出すのが困難となる。
【０００７】また、並列ＧＡにおいては、ある集団を代
表する情報として最良の染色体の情報を用い、集団間で
最良の染色体同士の適応度やハミング距離等を比較して
いる。しかし、集団全体に関する情報は用いられていな
い。最良の染色体同士のハミング距離では、個々の配列
間の距離の指標とはなっても、集団全体については何も
判らない。
表する情報として最良の染色体の情報を用い、集団間で
最良の染色体同士の適応度やハミング距離等を比較して
いる。しかし、集団全体に関する情報は用いられていな
い。最良の染色体同士のハミング距離では、個々の配列
間の距離の指標とはなっても、集団全体については何も
判らない。
【０００８】本発明の課題は、より効率の良いＧＡを用
いた最適化問題処理装置を提供することである。
いた最適化問題処理装置を提供することである。
【０００９】
【課題を解決するための手段】図１は、本発明の最適化
問題処理装置の原理図である。図１の最適化問題処理装
置は、集団格納手段１１、モデル格納手段１２、発生手
段１３、選択手段１４、操作手段１５、および出力手段
１６を備え、ＧＡを用いて最適化問題の解を求める処理
を行う。
問題処理装置の原理図である。図１の最適化問題処理装
置は、集団格納手段１１、モデル格納手段１２、発生手
段１３、選択手段１４、操作手段１５、および出力手段
１６を備え、ＧＡを用いて最適化問題の解を求める処理
を行う。
【００１０】本発明の第１の局面において、集団格納手
段１１は、個体集団の情報を格納し、モデル格納手段１
２は、個体集団の対立遺伝子の出現確率を表す確率モデ
ルの情報を格納する。発生手段１３は、確率モデルを参
照して新たな個体を生成し、生成した個体を次世代の個
体として集団格納手段１１に格納する。操作手段１５
は、集団格納手段１１内の個体集団に対してＧＡの操作
を施し、出力手段１６は、操作結果を出力する。
段１１は、個体集団の情報を格納し、モデル格納手段１
２は、個体集団の対立遺伝子の出現確率を表す確率モデ
ルの情報を格納する。発生手段１３は、確率モデルを参
照して新たな個体を生成し、生成した個体を次世代の個
体として集団格納手段１１に格納する。操作手段１５
は、集団格納手段１１内の個体集団に対してＧＡの操作
を施し、出力手段１６は、操作結果を出力する。
【００１１】集団格納手段１１は、個体集団の各個体
（染色体）の配列データを格納し、モデル格納手段１２
は、個体集団内で、各対立遺伝子が各遺伝子座に出現す
る確率を、確率モデルのデータとして格納する。発生手
段１３が確率モデルに基づいて新たな個体を生成するこ
とで、それを含む次世代の個体集団が生成される。操作
手段１５は、こうして生成された個体集団に対して、選
択、交叉、突然変異等の操作を施す。そして、所定の終
了条件が満たされると、それまでの操作結果が処理結果
として、出力手段１６から出力される。
（染色体）の配列データを格納し、モデル格納手段１２
は、個体集団内で、各対立遺伝子が各遺伝子座に出現す
る確率を、確率モデルのデータとして格納する。発生手
段１３が確率モデルに基づいて新たな個体を生成するこ
とで、それを含む次世代の個体集団が生成される。操作
手段１５は、こうして生成された個体集団に対して、選
択、交叉、突然変異等の操作を施す。そして、所定の終
了条件が満たされると、それまでの操作結果が処理結果
として、出力手段１６から出力される。
【００１２】このような処理装置によれば、個体集団内
に高い確率で出現する対立遺伝子を用いて、新たな個体
を生成し、それを次世代に組み入れることができる。こ
のような個体は良い評価値を有する可能性が高く、か
つ、確率モデルの特徴を反映しているので、局所最適解
から抜け出して効率の良い探索を行うことが可能とな
る。
に高い確率で出現する対立遺伝子を用いて、新たな個体
を生成し、それを次世代に組み入れることができる。こ
のような個体は良い評価値を有する可能性が高く、か
つ、確率モデルの特徴を反映しているので、局所最適解
から抜け出して効率の良い探索を行うことが可能とな
る。
【００１３】また、本発明の第２の局面において、集団
格納手段１１は、個体集団の情報を格納し、モデル格納
手段１２は、個体集団の対立遺伝子の出現確率を表す確
率モデルの情報を格納する。選択手段１４は、確率モデ
ルを参照して個体集団から個体を選択し、選択した個体
を次世代の個体として集団格納手段１１に格納する。操
作手段１５は、集団格納手段１１内の個体集団に対して
ＧＡの操作を施し、出力手段１６は、操作結果を出力す
る。
格納手段１１は、個体集団の情報を格納し、モデル格納
手段１２は、個体集団の対立遺伝子の出現確率を表す確
率モデルの情報を格納する。選択手段１４は、確率モデ
ルを参照して個体集団から個体を選択し、選択した個体
を次世代の個体として集団格納手段１１に格納する。操
作手段１５は、集団格納手段１１内の個体集団に対して
ＧＡの操作を施し、出力手段１６は、操作結果を出力す
る。
【００１４】この場合、選択手段１４が確率モデルに基
づいて個体を選択することで、選択された個体を含む次
世代の個体集団が生成される。操作手段１５は、こうし
て生成された個体集団に対して、選択、交叉、突然変異
等の操作を施す。そして、所定の終了条件が満たされる
と、それまでの操作結果が処理結果として、出力手段１
６から出力される。
づいて個体を選択することで、選択された個体を含む次
世代の個体集団が生成される。操作手段１５は、こうし
て生成された個体集団に対して、選択、交叉、突然変異
等の操作を施す。そして、所定の終了条件が満たされる
と、それまでの操作結果が処理結果として、出力手段１
６から出力される。
【００１５】このような処理装置によれば、個体集団内
に高い確率で出現する対立遺伝子を多く含む個体を優先
的に選択して、それを次世代に組み入れることができ
る。したがって、第１の局面における処理装置と同様
に、局所最適解から抜け出して効率の良い探索を行うこ
とが可能となる。
に高い確率で出現する対立遺伝子を多く含む個体を優先
的に選択して、それを次世代に組み入れることができ
る。したがって、第１の局面における処理装置と同様
に、局所最適解から抜け出して効率の良い探索を行うこ
とが可能となる。
【００１６】また、本発明の第３の局面において、集団
格納手段１１、モデル格納手段１２、および操作手段１
５は、それぞれ複数個設けられる。複数の集団格納手段
１１は、複数の個体集団の情報をそれぞれ格納し、複数
のモデル格納手段１２の各々は、各個体集団の対立遺伝
子の出現確率を表す確率モデルの情報を格納する。選択
手段１４は、確率モデルを参照して、複数の個体集団の
うちの２つの集団を比較し、それらのうち少なくとも一
方から個体を選択し、選択した個体を次世代の個体とし
て、対応する集団格納手段１１に格納する。複数の操作
手段１５は、複数の集団格納手段１１内の個体集団に対
して、それぞれＧＡの操作を施し、出力手段１６は、操
作結果を出力する。
格納手段１１、モデル格納手段１２、および操作手段１
５は、それぞれ複数個設けられる。複数の集団格納手段
１１は、複数の個体集団の情報をそれぞれ格納し、複数
のモデル格納手段１２の各々は、各個体集団の対立遺伝
子の出現確率を表す確率モデルの情報を格納する。選択
手段１４は、確率モデルを参照して、複数の個体集団の
うちの２つの集団を比較し、それらのうち少なくとも一
方から個体を選択し、選択した個体を次世代の個体とし
て、対応する集団格納手段１１に格納する。複数の操作
手段１５は、複数の集団格納手段１１内の個体集団に対
して、それぞれＧＡの操作を施し、出力手段１６は、操
作結果を出力する。
【００１７】各モデル格納手段１２は、対応する集団格
納手段１１内の個体集団に関する確率モデルのデータを
格納し、各操作手段１５は、対応する集団格納手段１１
内の個体集団を対象として、ＧＡの操作を施す。選択手
段１４が、各個体集団の確率モデルに基づいて２つの集
団を比較し、一方の集団から個体を選択することで、選
択された個体を含む次世代の個体集団が生成される。こ
うして生成された個体集団に対して、対応する操作手段
１５が、選択、交叉、突然変異等の操作を施す。そし
て、所定の終了条件が満たされると、それまでの操作結
果が処理結果として、出力手段１６から出力される。
納手段１１内の個体集団に関する確率モデルのデータを
格納し、各操作手段１５は、対応する集団格納手段１１
内の個体集団を対象として、ＧＡの操作を施す。選択手
段１４が、各個体集団の確率モデルに基づいて２つの集
団を比較し、一方の集団から個体を選択することで、選
択された個体を含む次世代の個体集団が生成される。こ
うして生成された個体集団に対して、対応する操作手段
１５が、選択、交叉、突然変異等の操作を施す。そし
て、所定の終了条件が満たされると、それまでの操作結
果が処理結果として、出力手段１６から出力される。
【００１８】このような処理装置によれば、集団全体の
情報を反映する確率モデルを用いることで、並列ＧＡに
おける２つの個体集団の類似度を正確に判定することが
できる。また、２つの個体集団が類似している場合に、
それらが乖離していくように個体を選択することで、そ
れらの集団を互いに異なる探索領域に振り分けることが
できる。これにより、並列ＧＡの効率を向上させること
が可能となる。
情報を反映する確率モデルを用いることで、並列ＧＡに
おける２つの個体集団の類似度を正確に判定することが
できる。また、２つの個体集団が類似している場合に、
それらが乖離していくように個体を選択することで、そ
れらの集団を互いに異なる探索領域に振り分けることが
できる。これにより、並列ＧＡの効率を向上させること
が可能となる。
【００１９】図１の集団格納手段１１は、例えば、後述
する図２の染色体集団記憶部２２および後述する図９の
ＧＡ部３２に対応する。また、図１のモデル格納手段１
２は、例えば、図２の確率モデル記憶部２５および図９
の確率モデル記憶部３３に対応する。また、図１の発生
手段１３は、例えば、図２の染色体発生部２６に対応
し、図１の選択手段１４は、例えば、図２の染色体選択
部２７および図９の確率モデル間制御部３４に対応す
る。また、図１の操作手段１５および出力手段１６はい
ずれも、例えば、図２のＧＡ演算部２３および図９のＧ
Ａ部３２に対応する。
する図２の染色体集団記憶部２２および後述する図９の
ＧＡ部３２に対応する。また、図１のモデル格納手段１
２は、例えば、図２の確率モデル記憶部２５および図９
の確率モデル記憶部３３に対応する。また、図１の発生
手段１３は、例えば、図２の染色体発生部２６に対応
し、図１の選択手段１４は、例えば、図２の染色体選択
部２７および図９の確率モデル間制御部３４に対応す
る。また、図１の操作手段１５および出力手段１６はい
ずれも、例えば、図２のＧＡ演算部２３および図９のＧ
Ａ部３２に対応する。
【００２０】
【発明の実施の形態】以下、図面を参照しながら、本発
明の実施の形態を詳細に説明する。図２は、単純ＧＡ
（SingleＧＡ，ＳＧＡ）を用いた最適化問題処理装置の
構成図である。図２の処理装置は、初期染色体発生部２
１、染色体集団記憶部２２、ＧＡ演算部２３、遺伝子統
計演算部２４、確率モデル記憶部２５、染色体発生部２
６、染色体選択部２７、終了判定部２８、および確率モ
デル制御部２９を備える。実線の矢印は、処理データの
やり取りを表し、破線の矢印は、制御データのやり取り
を表す。
明の実施の形態を詳細に説明する。図２は、単純ＧＡ
（SingleＧＡ，ＳＧＡ）を用いた最適化問題処理装置の
構成図である。図２の処理装置は、初期染色体発生部２
１、染色体集団記憶部２２、ＧＡ演算部２３、遺伝子統
計演算部２４、確率モデル記憶部２５、染色体発生部２
６、染色体選択部２７、終了判定部２８、および確率モ
デル制御部２９を備える。実線の矢印は、処理データの
やり取りを表し、破線の矢印は、制御データのやり取り
を表す。
【００２１】初期染色体発生部２１は、ＧＡの染色体集
団の初期化を行って、各染色体の初期値を生成する。染
色体集団記憶部２２は、染色体集団の情報を記憶し、Ｇ
Ａ演算部２３が使用する記憶領域も含む。ＧＡ演算部２
３は、染色体の評価関数の計算、染色体の選択、交叉、
突然変異等のＧＡ演算を行う。
団の初期化を行って、各染色体の初期値を生成する。染
色体集団記憶部２２は、染色体集団の情報を記憶し、Ｇ
Ａ演算部２３が使用する記憶領域も含む。ＧＡ演算部２
３は、染色体の評価関数の計算、染色体の選択、交叉、
突然変異等のＧＡ演算を行う。
【００２２】遺伝子統計演算部２４は、染色体集団記憶
部２２に格納された染色体集団の情報に基づいて統計計
算を行って、確率モデルを生成し、確率モデル記憶部２
５は、生成された確率モデルを記憶する。染色体発生部
２６は、確率モデルに基づいて新たな染色体を生成し、
染色体選択部２７は、染色体集団から確率モデルに基づ
いて染色体を選択する。
部２２に格納された染色体集団の情報に基づいて統計計
算を行って、確率モデルを生成し、確率モデル記憶部２
５は、生成された確率モデルを記憶する。染色体発生部
２６は、確率モデルに基づいて新たな染色体を生成し、
染色体選択部２７は、染色体集団から確率モデルに基づ
いて染色体を選択する。
【００２３】終了判定部２８は、ＧＡ演算部２３による
探索を終了するか継続するかを判定し、確率モデル制御
部２９は、染色体集団記憶部２２、ＧＡ演算部２３、遺
伝子統計演算部２４、確率モデル記憶部２５、染色体発
生部２６、および染色体選択部２７の確率モデルに関す
る動作を制御する。
探索を終了するか継続するかを判定し、確率モデル制御
部２９は、染色体集団記憶部２２、ＧＡ演算部２３、遺
伝子統計演算部２４、確率モデル記憶部２５、染色体発
生部２６、および染色体選択部２７の確率モデルに関す
る動作を制御する。
【００２４】図３は、図２の処理装置によるＧＡ処理の
フローチャートである。まず、初期染色体発生部２１
は、初期の染色体集団を生成し、染色体集団記憶部２２
に格納する（ステップＳ１）。次に、ＧＡ演算部２３
は、染色体集団記憶部２２の各染色体について評価関数
の値を計算し（ステップＳ２）、確率モデル制御部２９
は、確率モデル生成のための条件が成立したか否かを判
定する（ステップＳ３）。この条件としては、例えば、
ＧＡの所定の世代に到達したことが用いられる。この所
定の世代は、あらかじめ決められた世代間隔等を用いて
設定される。
フローチャートである。まず、初期染色体発生部２１
は、初期の染色体集団を生成し、染色体集団記憶部２２
に格納する（ステップＳ１）。次に、ＧＡ演算部２３
は、染色体集団記憶部２２の各染色体について評価関数
の値を計算し（ステップＳ２）、確率モデル制御部２９
は、確率モデル生成のための条件が成立したか否かを判
定する（ステップＳ３）。この条件としては、例えば、
ＧＡの所定の世代に到達したことが用いられる。この所
定の世代は、あらかじめ決められた世代間隔等を用いて
設定される。
【００２５】条件が成立しなければ、次に、終了判定部
２８が、あらかじめ設定された終了条件が成立したか否
かを判定する（ステップＳ４）。この終了条件として
は、ＧＡの世代数が一定値に達したこと、最良の染色体
の評価関数値（評価値）が一定値に達したこと、ユーザ
による終了指示の割り込みが発生したこと等が用いられ
る。
２８が、あらかじめ設定された終了条件が成立したか否
かを判定する（ステップＳ４）。この終了条件として
は、ＧＡの世代数が一定値に達したこと、最良の染色体
の評価関数値（評価値）が一定値に達したこと、ユーザ
による終了指示の割り込みが発生したこと等が用いられ
る。
【００２６】終了条件が成立しなければ、次に、ＧＡ演
算部２３は、通常のＧＡの最適化演算を行う。ここで
は、染色体集団記憶部２２の染色体集団に選択操作を施
し（ステップＳ９）、交叉操作を施し（ステップＳ１
０）、突然変異操作を施して（ステップＳ１１）、ステ
ップＳ２以降の処理を繰り返す。
算部２３は、通常のＧＡの最適化演算を行う。ここで
は、染色体集団記憶部２２の染色体集団に選択操作を施
し（ステップＳ９）、交叉操作を施し（ステップＳ１
０）、突然変異操作を施して（ステップＳ１１）、ステ
ップＳ２以降の処理を繰り返す。
【００２７】こうしてＧＡ演算が繰り返され、ステップ
Ｓ３において確率モデル生成のための条件が成立すれ
ば、確率モデル制御部２９が割り込む。そして、確率モ
デル制御部２９の制御に従って、遺伝子統計演算部２４
は、染色体集団の確率モデルを生成し、確率モデル記憶
部２５に格納する（ステップＳ５）。これにより、あら
かじめ決められた世代間隔で、確率モデルが更新され
る。
Ｓ３において確率モデル生成のための条件が成立すれ
ば、確率モデル制御部２９が割り込む。そして、確率モ
デル制御部２９の制御に従って、遺伝子統計演算部２４
は、染色体集団の確率モデルを生成し、確率モデル記憶
部２５に格納する（ステップＳ５）。これにより、あら
かじめ決められた世代間隔で、確率モデルが更新され
る。
【００２８】次に、確率モデル制御部２９は、染色体の
発生と選択のいずれを行うかを決定する（ステップＳ
６）。いずれを行うかは、ユーザからの指示に基づいて
決定してもよく、あらかじめ設定された制御情報に基づ
いて決定してもよい。
発生と選択のいずれを行うかを決定する（ステップＳ
６）。いずれを行うかは、ユーザからの指示に基づいて
決定してもよく、あらかじめ設定された制御情報に基づ
いて決定してもよい。
【００２９】染色体発生の場合、染色体発生部２６は、
確率モデル記憶部２５の確率モデルを用いて新たな染色
体を生成し、染色体集団記憶部２２の染色体集団に組み
入れる（ステップＳ７）。新たな染色体としては、確率
モデルのコンセンサス配列（最も確率の高い配列）や次
善のコンセンサス配列等が用いられる。
確率モデル記憶部２５の確率モデルを用いて新たな染色
体を生成し、染色体集団記憶部２２の染色体集団に組み
入れる（ステップＳ７）。新たな染色体としては、確率
モデルのコンセンサス配列（最も確率の高い配列）や次
善のコンセンサス配列等が用いられる。
【００３０】また、染色体選択の場合、染色体選択部２
７は、確率モデルをベースにして各染色体を評価し、比
較的良い評価の染色体を選択して、ＧＡ演算部２３に渡
す（ステップＳ８）。その後、ＧＡ演算部２３は、ステ
ップＳ９以降の処理を行い、ステップＳ４において終了
条件が成立すれば、その時点における評価値の良い染色
体を処理結果として出力し、処理を終了する。
７は、確率モデルをベースにして各染色体を評価し、比
較的良い評価の染色体を選択して、ＧＡ演算部２３に渡
す（ステップＳ８）。その後、ＧＡ演算部２３は、ステ
ップＳ９以降の処理を行い、ステップＳ４において終了
条件が成立すれば、その時点における評価値の良い染色
体を処理結果として出力し、処理を終了する。
【００３１】次に、図４から図８までを参照しながら、
ＳＧＡの具体例を説明する。最適化問題として、次式で
表される評価関数ｆ（ｘi ）（ｉ＝１，２，３，４）を
最小化する問題を考える。
ＳＧＡの具体例を説明する。最適化問題として、次式で
表される評価関数ｆ（ｘi ）（ｉ＝１，２，３，４）を
最小化する問題を考える。
【００３２】
【数１】
【００３３】ここで、ｘi の取り得る値の範囲は０≦ｘ
i ≦３の整数である。この評価関数ｆ（ｘi ）は、各ｉ
について、ｘi ＝１で最小値０になる。この問題を解く
ために、ｘi を遺伝子（gene）とし、対立遺伝子を０〜
３の整数とする。このとき、各染色体の配列は、［０，
１，２，３］∈ｘ1 ，ｘ2 ，ｘ 3 ，ｘ4 の４つの整数の
組（ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ）で表される。個体数を５
に設定した染色体集団を乱数で初期化して、最適化演算
を行った結果、ある世代での染色体集団とそれに対応す
る評価関数値が、図４のようになったものとする。この
染色体集団からは、図５に示すような確率モデルが生成
される。
i ≦３の整数である。この評価関数ｆ（ｘi ）は、各ｉ
について、ｘi ＝１で最小値０になる。この問題を解く
ために、ｘi を遺伝子（gene）とし、対立遺伝子を０〜
３の整数とする。このとき、各染色体の配列は、［０，
１，２，３］∈ｘ1 ，ｘ2 ，ｘ 3 ，ｘ4 の４つの整数の
組（ｘ1 ，ｘ2 ，ｘ3 ，ｘ4 ）で表される。個体数を５
に設定した染色体集団を乱数で初期化して、最適化演算
を行った結果、ある世代での染色体集団とそれに対応す
る評価関数値が、図４のようになったものとする。この
染色体集団からは、図５に示すような確率モデルが生成
される。
【００３４】図５の確率モデルは、各遺伝子座における
各対立遺伝子の出現確率を表している。例えば、ｘ1 に
ついては、図４の染色体１〜５のうち、染色体２のみが
対立遺伝子“０”を持つ。したがって、ｘ1 における対
立遺伝子“０”の出現確率は、１／５＝０．２となる。
また、ｘ1 ＝１となるものは、染色体１と染色体４の２
つである。したがって、ｘ1 における対立遺伝子“１”
の出現確率は、２／５＝０．４となる。
各対立遺伝子の出現確率を表している。例えば、ｘ1 に
ついては、図４の染色体１〜５のうち、染色体２のみが
対立遺伝子“０”を持つ。したがって、ｘ1 における対
立遺伝子“０”の出現確率は、１／５＝０．２となる。
また、ｘ1 ＝１となるものは、染色体１と染色体４の２
つである。したがって、ｘ1 における対立遺伝子“１”
の出現確率は、２／５＝０．４となる。
【００３５】同様にして、ｘ1 における対立遺伝子
“２”および“３”の出現確率は、それぞれ０．４およ
び０．０となり、ｘ1 におけるすべての対立遺伝子の出
現確率の和は１となる。他の遺伝子座における出現確率
についても同様である。
“２”および“３”の出現確率は、それぞれ０．４およ
び０．０となり、ｘ1 におけるすべての対立遺伝子の出
現確率の和は１となる。他の遺伝子座における出現確率
についても同様である。
【００３６】染色体発生部２６は、この確率モデルを参
照して、高い出現確率を有する対立遺伝子同士を組み合
わせた新たな染色体（コンセンサス配列）を生成する。
ここでは、各遺伝子座において最高の出現確率（０．４
または０．６）の対立遺伝子を選択することで、図６の
ようなコンセンサス配列が生成される。
照して、高い出現確率を有する対立遺伝子同士を組み合
わせた新たな染色体（コンセンサス配列）を生成する。
ここでは、各遺伝子座において最高の出現確率（０．４
または０．６）の対立遺伝子を選択することで、図６の
ようなコンセンサス配列が生成される。
【００３７】図６において、各染色体の出現確率は、図
５に示した対立遺伝子の出現確率を、すべての遺伝子座
について乗算した結果に対応する。また、ｌｏｇ−ｏｄ
ｄｓは、対数オッズ比と呼ばれ、次式により定義され
る。
５に示した対立遺伝子の出現確率を、すべての遺伝子座
について乗算した結果に対応する。また、ｌｏｇ−ｏｄ
ｄｓは、対数オッズ比と呼ばれ、次式により定義され
る。
【００３８】
【数２】
【００３９】一般に、対数オッズ比の対数の底は任意で
あるが、図６の計算では底として２を用いている。ま
た、（２）式の右辺のＰi は、ｘi における対立遺伝子
の出現確率を表し、総和はｉ＝１〜４について行われ
る。
あるが、図６の計算では底として２を用いている。ま
た、（２）式の右辺のＰi は、ｘi における対立遺伝子
の出現確率を表し、総和はｉ＝１〜４について行われ
る。
【００４０】この対数オッズ比は、バックグラウンドの
確率モデルと対比した、対象とする確率モデルにおける
各個体の適合度を表すスコアであり、このスコアを参照
することで、各個体が対象とする確率モデルにフィット
しているか否かを判定することができる。ここでは、対
立遺伝子が４つあり、等確率のバックグラウンドの確率
モデルを想定しているため、（２）式の右辺にｌｏｇ
（１／４）が現れている。
確率モデルと対比した、対象とする確率モデルにおける
各個体の適合度を表すスコアであり、このスコアを参照
することで、各個体が対象とする確率モデルにフィット
しているか否かを判定することができる。ここでは、対
立遺伝子が４つあり、等確率のバックグラウンドの確率
モデルを想定しているため、（２）式の右辺にｌｏｇ
（１／４）が現れている。
【００４１】染色体発生部２６は、これらのコンセンサ
ス配列のうち、評価値の良い染色体を元の染色体集団に
戻す。この場合、コンセンサス配列の数が集団の個体数
よリ多いため、最良（最小）の評価値の配列“１１１
０”を戻せばよい。また、この例では、同じ確率のコン
センサス配列が８個生成されたが、通常は、確率最大の
コンセンサス配列の数は集団の個体数よりも小さくな
る。
ス配列のうち、評価値の良い染色体を元の染色体集団に
戻す。この場合、コンセンサス配列の数が集団の個体数
よリ多いため、最良（最小）の評価値の配列“１１１
０”を戻せばよい。また、この例では、同じ確率のコン
センサス配列が８個生成されたが、通常は、確率最大の
コンセンサス配列の数は集団の個体数よりも小さくな
る。
【００４２】図４の染色体集団と最良のコンセンサス配
列について、図５の確率モデルに基づき出現確率と対数
オッズ比を計算すると、図７のようになる。染色体１〜
５のうち、評価値が最悪のものは染色体２、３、５の３
つであるから、これらのうちのいずれかとコンセンサス
配列“１１１０”を入れ換えることで、確率モデルを加
味した新たな染色体集団が生成される。
列について、図５の確率モデルに基づき出現確率と対数
オッズ比を計算すると、図７のようになる。染色体１〜
５のうち、評価値が最悪のものは染色体２、３、５の３
つであるから、これらのうちのいずれかとコンセンサス
配列“１１１０”を入れ換えることで、確率モデルを加
味した新たな染色体集団が生成される。
【００４３】このように、染色体集団から作成した確率
モデルを用いて、評価値の高い新たな染色体を作成する
ことが可能になる。確率モデルで作成した染色体は、元
の集団のビルディング・ブロックを保持しているため、
これから生成される新しい染色体は、さらに良い解を与
えると考えられる。
モデルを用いて、評価値の高い新たな染色体を作成する
ことが可能になる。確率モデルで作成した染色体は、元
の集団のビルディング・ブロックを保持しているため、
これから生成される新しい染色体は、さらに良い解を与
えると考えられる。
【００４４】また、（１）式の評価関数ｆ（ｘi ）に対
して、対数オッズ比を加味した実効評価関数ｆｅ
（ｘi ）は、例えば、次式により定義される。 ｆｅ（ｘi ）＝｛１／（ｆ（ｘi ）＋０．０１）｝ ＊ｌｏｇ−ｏｄｄｓ （３） これにより、ｆ（ｘi ）の最小化問題がｆｅ（ｘi ）の
最大化問題に置き換えられ、ｌｏｇ−ｏｄｄｓの値を乗
算することで、確率モデルに基づく評価が加味される。
して、対数オッズ比を加味した実効評価関数ｆｅ
（ｘi ）は、例えば、次式により定義される。 ｆｅ（ｘi ）＝｛１／（ｆ（ｘi ）＋０．０１）｝ ＊ｌｏｇ−ｏｄｄｓ （３） これにより、ｆ（ｘi ）の最小化問題がｆｅ（ｘi ）の
最大化問題に置き換えられ、ｌｏｇ−ｏｄｄｓの値を乗
算することで、確率モデルに基づく評価が加味される。
【００４５】染色体選択部２７は、染色体集団の中から
実効評価関数値が高い所定数の染色体を選択して、ＧＡ
演算部２３に渡す。このとき、集団内の染色体を実効評
価関数値が高い順にソートして、上位から所定数のもの
を選択する。
実効評価関数値が高い所定数の染色体を選択して、ＧＡ
演算部２３に渡す。このとき、集団内の染色体を実効評
価関数値が高い順にソートして、上位から所定数のもの
を選択する。
【００４６】図７に示した各染色体について、（３）式
の実効評価関数値を計算すると、図８のようになる。例
えば、染色体２と染色体３を比較すると、元の評価関数
値は同じであるが、実効評価関数値は異なっている。こ
の場合、実効評価関数値に従って選択を行うことで、よ
り出現確率が高い個体が優先的に選択されるようにな
る。
の実効評価関数値を計算すると、図８のようになる。例
えば、染色体２と染色体３を比較すると、元の評価関数
値は同じであるが、実効評価関数値は異なっている。こ
の場合、実効評価関数値に従って選択を行うことで、よ
り出現確率が高い個体が優先的に選択されるようにな
る。
【００４７】このように、確率モデルに基づく対数オッ
ズ比の評価とＧＡの評価関数を組み合わせた実効評価関
数を用いることで、ＧＡに確率モデルを付加することが
でき、より良い染色体の評価が可能となる。
ズ比の評価とＧＡの評価関数を組み合わせた実効評価関
数を用いることで、ＧＡに確率モデルを付加することが
でき、より良い染色体の評価が可能となる。
【００４８】次に、図９は、並列ＧＡ（ParallelＧＡ，
ＰＧＡ）を用いた最適化問題処理装置の構成図である。
図９の処理装置は、ＧＡ間制御部３１、ＧＡ部３２、確
率モデル記憶部３３、確率モデル間制御部３４、および
距離計算部３５を備える。ここでは、ＧＡ部３２と確率
モデル記憶部３３が３つずつ示されているが、実際に
は、並列に処理される染色体集団の数（任意）だけ設け
られる。
ＰＧＡ）を用いた最適化問題処理装置の構成図である。
図９の処理装置は、ＧＡ間制御部３１、ＧＡ部３２、確
率モデル記憶部３３、確率モデル間制御部３４、および
距離計算部３５を備える。ここでは、ＧＡ部３２と確率
モデル記憶部３３が３つずつ示されているが、実際に
は、並列に処理される染色体集団の数（任意）だけ設け
られる。
【００４９】各ＧＡ部３２は、図２の初期染色体発生部
２１、染色体集団記憶部２２、ＧＡ演算部２３、および
終了判定部２８に対応し、ＧＡを用いた最適化を行う。
ＧＡ間制御部３１は、通常の並列ＧＡと同様に、ＧＡ部
３２の間の制御（初期化、世代の進歩、終了判定等）を
行う。
２１、染色体集団記憶部２２、ＧＡ演算部２３、および
終了判定部２８に対応し、ＧＡを用いた最適化を行う。
ＧＡ間制御部３１は、通常の並列ＧＡと同様に、ＧＡ部
３２の間の制御（初期化、世代の進歩、終了判定等）を
行う。
【００５０】各確率モデル記憶部３３は、対応するＧＡ
部３２の染色体集団の確率モデルを記憶し、確率モデル
の生成や演算等に使用される記憶領域も含む。確率モデ
ル間制御部３４は、確率モデルの生成と確率モデル間の
演算／制御を行い、距離計算部３５は、確率モデル間の
距離計算（類似度計算）を行う。ＧＡ間制御部３１と確
率モデル間制御部３４は、互いに連携しながら制御を行
う。
部３２の染色体集団の確率モデルを記憶し、確率モデル
の生成や演算等に使用される記憶領域も含む。確率モデ
ル間制御部３４は、確率モデルの生成と確率モデル間の
演算／制御を行い、距離計算部３５は、確率モデル間の
距離計算（類似度計算）を行う。ＧＡ間制御部３１と確
率モデル間制御部３４は、互いに連携しながら制御を行
う。
【００５１】図１０は、図９の処理装置によるＧＡ処理
のフローチャートである。まず、ＧＡ部３２は、初期の
染色体集団を生成し（ステップＳ１１）、並列に１世代
の最適化演算を行う（ステップＳ１２）。次に、確率モ
デル間制御部３４は、確率モデル生成のための条件が成
立したか否かを判定する（ステップＳ３）。この条件に
ついては、図２の処理装置の場合と同様である。
のフローチャートである。まず、ＧＡ部３２は、初期の
染色体集団を生成し（ステップＳ１１）、並列に１世代
の最適化演算を行う（ステップＳ１２）。次に、確率モ
デル間制御部３４は、確率モデル生成のための条件が成
立したか否かを判定する（ステップＳ３）。この条件に
ついては、図２の処理装置の場合と同様である。
【００５２】条件が成立しなければ、次に、各ＧＡ部３
２が、あらかじめ設定された終了条件が成立したか否か
を判定する（ステップＳ１４）。この終了条件について
も、図２の処理装置の場合と同様である。
２が、あらかじめ設定された終了条件が成立したか否か
を判定する（ステップＳ１４）。この終了条件について
も、図２の処理装置の場合と同様である。
【００５３】終了条件が成立しなければ、ＧＡ部３２
は、ステップＳ１２以降の処理を繰り返し、ステップＳ
１３において確率モデル生成のための条件が成立すれ
ば、確率モデル間制御部３４が割り込む。そして、各Ｇ
Ａ部３２の染色体集団について遺伝子統計演算を行っ
て、各染色体集団の確率モデルを生成し、確率モデル記
憶部３３に格納する（ステップＳ１５）。
は、ステップＳ１２以降の処理を繰り返し、ステップＳ
１３において確率モデル生成のための条件が成立すれ
ば、確率モデル間制御部３４が割り込む。そして、各Ｇ
Ａ部３２の染色体集団について遺伝子統計演算を行っ
て、各染色体集団の確率モデルを生成し、確率モデル記
憶部３３に格納する（ステップＳ１５）。
【００５４】次に、距離計算部３５は、確率モデル間制
御部３４の指示に従って、確率モデル間の相関等（距
離）を計算する（ステップＳ１６）。そして、確率モデ
ル間制御部３４は、距離計算の結果に基づいて各染色体
集団の実効評価関数（実効適応度）を設定し、実効評価
関数を用いて各染色体を評価する。そして、各染色体集
団から比較的良い評価の染色体を選択し、各ＧＡ部３２
に渡す（ステップＳ１７）。
御部３４の指示に従って、確率モデル間の相関等（距
離）を計算する（ステップＳ１６）。そして、確率モデ
ル間制御部３４は、距離計算の結果に基づいて各染色体
集団の実効評価関数（実効適応度）を設定し、実効評価
関数を用いて各染色体を評価する。そして、各染色体集
団から比較的良い評価の染色体を選択し、各ＧＡ部３２
に渡す（ステップＳ１７）。
【００５５】その後、ＧＡ部３２は、ステップＳ１２以
降の処理を行い、ステップＳ１４において終了条件が成
立すれば、処理を終了する。そして、ＧＡ間制御部３１
は、その時点における評価値の良い染色体を各ＧＡ部３
２から収集して、処理結果として出力する。
降の処理を行い、ステップＳ１４において終了条件が成
立すれば、処理を終了する。そして、ＧＡ間制御部３１
は、その時点における評価値の良い染色体を各ＧＡ部３
２から収集して、処理結果として出力する。
【００５６】ここで、ＰＧＡの具体例として、次式で表
される評価関数ｆ（ｘi ）（ｉ＝１，２，３，４）を最
小化する問題を考える。
される評価関数ｆ（ｘi ）（ｉ＝１，２，３，４）を最
小化する問題を考える。
【００５７】
【数３】
【００５８】ｘi の取り得る値の範囲は０≦ｘi ≦３の
整数である。この評価関数ｆ（ｘi）は、各ｉについ
て、ｘi ＝０、ｘi ＝１、またはｘi ＝２で最小値０に
なる。このとき、並列ＧＡは、例えば、以下のように動
作する。
整数である。この評価関数ｆ（ｘi）は、各ｉについ
て、ｘi ＝０、ｘi ＝１、またはｘi ＝２で最小値０に
なる。このとき、並列ＧＡは、例えば、以下のように動
作する。
【００５９】各ＧＡ部３２は、並列に最適化演算を行
い、ＧＡ間制御部３１が、適宜、各染色体集団の初期化
を行い、設定された世代間隔で割り込み、適応度の比較
等を行う。また、確率モデル間制御部３４は、設定され
た世代間隔で割り込み、各染色体集団の確率モデルを生
成する。
い、ＧＡ間制御部３１が、適宜、各染色体集団の初期化
を行い、設定された世代間隔で割り込み、適応度の比較
等を行う。また、確率モデル間制御部３４は、設定され
た世代間隔で割り込み、各染色体集団の確率モデルを生
成する。
【００６０】例えば、３つの染色体集団を用いたＰＧＡ
において、図１１のような３つの確率モデルＰ１、Ｐ
２、Ｐ３が生成されたものとする。このとき、距離計算
部３５は、確率モデル間制御部３４の指示に従って、確
率モデル間の距離として、次のような相対エントロピー
（Kullback-Leibler divergence ）を計算する。
において、図１１のような３つの確率モデルＰ１、Ｐ
２、Ｐ３が生成されたものとする。このとき、距離計算
部３５は、確率モデル間制御部３４の指示に従って、確
率モデル間の距離として、次のような相対エントロピー
（Kullback-Leibler divergence ）を計算する。
【００６１】
【数４】
【００６２】ここで、ＰおよびＱは、比較される２つの
確率モデルを表し、Ｈ（Ｐ‖Ｑ）は、ＰとＱの相対エン
トロピーを表す。（５）式の右辺の総和は、ｉ＝１〜４
およびｘi ＝０〜３について行われる。例えば、図１１
の確率モデルＰ１とＰ２の相対エントロピーは、次のよ
うに計算される。 Ｈ（Ｐ１‖Ｐ２） ＝０．２ｌｏｇ（０．２／０．４）＋０．４ｌｏｇ（０．４／０．４） ＋０．４ｌｏｇ（０．４／０．２）＋０．４ｌｏｇ（０．４／０．４） ＋０．２ｌｏｇ（０．２／０．４）＋０．４ｌｏｇ（０．４／０．２） ＋０．４ｌｏｇ（０．４／０．２）＋０．４ｌｏｇ（０．４／０．４） ＋０．２ｌｏｇ（０．２／０．２）＋０．４ｌｏｇ（０．４／０．２） ＋０．２ｌｏｇ（０．２／０．４）＋０．２ｌｏｇ（０．２／０．２） ＋０．２ｌｏｇ（０．２／０．２） ＝０．２ｌｏｇ（１／２）＋０．４ｌｏｇ（２）＋０．２ｌｏｇ（１／２） ＋０．４ｌｏｇ（２）＋０．４ｌｏｇ（２）＋０．４ｌｏｇ（２） ＋０．２ｌｏｇ（１／２） ＝ｌｏｇ（２） （６） この相対エントロピーは、２つの確率モデルが等しけれ
ば０になり、違いが大きければ値が大きくなる。２つの
確率モデルの類似度は、対応する染色体集団の間の類似
度を反映しているため、相対エントロピーを用いて集団
間の類似度を判定することができる。
確率モデルを表し、Ｈ（Ｐ‖Ｑ）は、ＰとＱの相対エン
トロピーを表す。（５）式の右辺の総和は、ｉ＝１〜４
およびｘi ＝０〜３について行われる。例えば、図１１
の確率モデルＰ１とＰ２の相対エントロピーは、次のよ
うに計算される。 Ｈ（Ｐ１‖Ｐ２） ＝０．２ｌｏｇ（０．２／０．４）＋０．４ｌｏｇ（０．４／０．４） ＋０．４ｌｏｇ（０．４／０．２）＋０．４ｌｏｇ（０．４／０．４） ＋０．２ｌｏｇ（０．２／０．４）＋０．４ｌｏｇ（０．４／０．２） ＋０．４ｌｏｇ（０．４／０．２）＋０．４ｌｏｇ（０．４／０．４） ＋０．２ｌｏｇ（０．２／０．２）＋０．４ｌｏｇ（０．４／０．２） ＋０．２ｌｏｇ（０．２／０．４）＋０．２ｌｏｇ（０．２／０．２） ＋０．２ｌｏｇ（０．２／０．２） ＝０．２ｌｏｇ（１／２）＋０．４ｌｏｇ（２）＋０．２ｌｏｇ（１／２） ＋０．４ｌｏｇ（２）＋０．４ｌｏｇ（２）＋０．４ｌｏｇ（２） ＋０．２ｌｏｇ（１／２） ＝ｌｏｇ（２） （６） この相対エントロピーは、２つの確率モデルが等しけれ
ば０になり、違いが大きければ値が大きくなる。２つの
確率モデルの類似度は、対応する染色体集団の間の類似
度を反映しているため、相対エントロピーを用いて集団
間の類似度を判定することができる。
【００６３】確率モデル間制御部３４は、例えば、相対
エントロピーが所定のしきい値より小さければ、２つの
集団が類似していると判定し、それが所定のしきい値以
上であれば、２つの集団は類似していないと判定する。
エントロピーが所定のしきい値より小さければ、２つの
集団が類似していると判定し、それが所定のしきい値以
上であれば、２つの集団は類似していないと判定する。
【００６４】２つの集団が互いに類似している場合、そ
の一方の集団の評価関数を、他方の集団に基づく対数オ
ッズ比をペナルティとして用いて変更することで、前者
の集団を類似性がない領域に誘導することが可能であ
る。
の一方の集団の評価関数を、他方の集団に基づく対数オ
ッズ比をペナルティとして用いて変更することで、前者
の集団を類似性がない領域に誘導することが可能であ
る。
【００６５】ここで、図１２に示すような染色体集団を
用いて、ペナルティの計算方法の例を説明する。図１２
は、染色体集団と（４）式の評価関数ｆ（ｘi ）の計算
結果を示している。この染色体集団の確率モデルは、図
１１の確率モデルＰ１に一致している。確率モデルＰ１
とＰ２が類似しているとき、各染色体について、（２）
式の対数オッズ比を確率モデルＰ２に基づいて計算する
と、以下のようになる。 染色体１（１１３０） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．４）＋ｌｏｇ（０．４）＋ｌｏｇ（０．２） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝０．７１２２８７ 染色体２（０３１２） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．４）＋ｌｏｇ（０．２）＋ｌｏｇ（０．４） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝０．７１２２８７ 染色体３（２１０３） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．２）＋ｌｏｇ（０．４）＋ｌｏｇ（０．２） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝−０．２８７７１３ 染色体４（１２１０） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．４）＋ｌｏｇ（０．４）＋ｌｏｇ（０．４） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝１．７１２２８７ 染色体５（２３０１） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．２）＋ｌｏｇ（０．２）＋ｌｏｇ（０．２） ＋ｌｏｇ（０．４）−４ｌｏｇ（１／４） ＝−０．２８７７１３ これらの対数オッズ比は、各個体の確率モデルＰ２に対
する適合度を表しており、その値が大きいほど確率モデ
ルＰ２にフィットしていることを意味する。そこで、対
数オッズ比が大きい個体の評価を低くするために、評価
関数ｆ（ｘi ）に対して、次式のような実効評価関数ｆ
ｅ（ｘi ）を定義する。 ｆｅ（ｘi ）＝ｆ（ｘi ）＋α＊ｌｏｇ−ｏｄｄｓ （７） ここで、αは定数である。確率モデル間制御部３４は、
このｆｅ（ｘi ）を用いて各染色体を評価し、評価値の
良い所定数の染色体を選択して、対応するＧＡ部３２に
渡す。この場合、確率モデルＰ２にフィットしている個
体のｆｅ（ｘi）は、ｆ（ｘi ）より大きくなり、評価
値が悪くなる。このため、結果として、対応するＧＡ部
３２は、確率モデルＰ２から乖離した他の探索点をより
多く探索するようになる。
用いて、ペナルティの計算方法の例を説明する。図１２
は、染色体集団と（４）式の評価関数ｆ（ｘi ）の計算
結果を示している。この染色体集団の確率モデルは、図
１１の確率モデルＰ１に一致している。確率モデルＰ１
とＰ２が類似しているとき、各染色体について、（２）
式の対数オッズ比を確率モデルＰ２に基づいて計算する
と、以下のようになる。 染色体１（１１３０） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．４）＋ｌｏｇ（０．４）＋ｌｏｇ（０．２） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝０．７１２２８７ 染色体２（０３１２） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．４）＋ｌｏｇ（０．２）＋ｌｏｇ（０．４） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝０．７１２２８７ 染色体３（２１０３） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．２）＋ｌｏｇ（０．４）＋ｌｏｇ（０．２） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝−０．２８７７１３ 染色体４（１２１０） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．４）＋ｌｏｇ（０．４）＋ｌｏｇ（０．４） ＋ｌｏｇ（０．２）−４ｌｏｇ（１／４） ＝１．７１２２８７ 染色体５（２３０１） ｌｏｇ−ｏｄｄｓ＝ｌｏｇ（０．２）＋ｌｏｇ（０．２）＋ｌｏｇ（０．２） ＋ｌｏｇ（０．４）−４ｌｏｇ（１／４） ＝−０．２８７７１３ これらの対数オッズ比は、各個体の確率モデルＰ２に対
する適合度を表しており、その値が大きいほど確率モデ
ルＰ２にフィットしていることを意味する。そこで、対
数オッズ比が大きい個体の評価を低くするために、評価
関数ｆ（ｘi ）に対して、次式のような実効評価関数ｆ
ｅ（ｘi ）を定義する。 ｆｅ（ｘi ）＝ｆ（ｘi ）＋α＊ｌｏｇ−ｏｄｄｓ （７） ここで、αは定数である。確率モデル間制御部３４は、
このｆｅ（ｘi ）を用いて各染色体を評価し、評価値の
良い所定数の染色体を選択して、対応するＧＡ部３２に
渡す。この場合、確率モデルＰ２にフィットしている個
体のｆｅ（ｘi）は、ｆ（ｘi ）より大きくなり、評価
値が悪くなる。このため、結果として、対応するＧＡ部
３２は、確率モデルＰ２から乖離した他の探索点をより
多く探索するようになる。
【００６６】α＝１０．０とおいて、図１２の各染色体
について（７）式の実効評価関数値を計算すると、図１
３のようになる。また、図１１の確率モデルＰ２の分布
からは、この確率モデルの集団が 外１ を最小にする
点の付近に存在することが読
について（７）式の実効評価関数値を計算すると、図１
３のようになる。また、図１１の確率モデルＰ２の分布
からは、この確率モデルの集団が 外１ を最小にする
点の付近に存在することが読
【００６７】
【外１】
【００６８】み取れる。図１３では、最も良い評価関数
値の染色体４は、この付近にある個体であり、その対数
オッズ比は最も大きくなっている。したがって、実効評
価関数値による評価は大幅に悪くなっている。
値の染色体４は、この付近にある個体であり、その対数
オッズ比は最も大きくなっている。したがって、実効評
価関数値による評価は大幅に悪くなっている。
【００６９】一方、確率モデルＰ２から乖離した領域に
ある染色体３および染色体５は、対数オッズ比が小さい
ため、実効評価関数値による評価は良くなっている。こ
のように、（７）式の実効評価関数を用いることで、あ
る集団の探索範囲から他の集団の近傍を排除する効果が
ある。
ある染色体３および染色体５は、対数オッズ比が小さい
ため、実効評価関数値による評価は良くなっている。こ
のように、（７）式の実効評価関数を用いることで、あ
る集団の探索範囲から他の集団の近傍を排除する効果が
ある。
【００７０】以上説明したように、複数の染色体集団を
有するＰＧＡにおいて、確率モデルを用いて集団同士を
比較し、比較結果に基づいて探索領域の競合を調整する
ことで、これらの集団を互いに異なる探索領域に振り分
けることができる。したがって、全体としての探索効率
が向上する。
有するＰＧＡにおいて、確率モデルを用いて集団同士を
比較し、比較結果に基づいて探索領域の競合を調整する
ことで、これらの集団を互いに異なる探索領域に振り分
けることができる。したがって、全体としての探索効率
が向上する。
【００７１】次に、図１４から図１７までを参照しなが
ら、図２および図９の処理装置が航空ダイヤのスケジュ
ーリングを行う場合の処理を説明する。図１４は、この
場合のＧＡ演算部２３およびＧＡ部３２が評価関数（適
応度）を計算するための構成を示している。図１４のフ
ライトオブジェクト４１とフライトスケジュール管理部
４２は、先願の「オブジェクト指向遺伝的アルゴリズム
を用いた最適化方法及び装置」（特開平１１−５３３３
７）に示されているように、オブジェクト指向プログラ
ミングによりプログラムされる。
ら、図２および図９の処理装置が航空ダイヤのスケジュ
ーリングを行う場合の処理を説明する。図１４は、この
場合のＧＡ演算部２３およびＧＡ部３２が評価関数（適
応度）を計算するための構成を示している。図１４のフ
ライトオブジェクト４１とフライトスケジュール管理部
４２は、先願の「オブジェクト指向遺伝的アルゴリズム
を用いた最適化方法及び装置」（特開平１１−５３３３
７）に示されているように、オブジェクト指向プログラ
ミングによりプログラムされる。
【００７２】フライトスケジュール管理部４２は、与え
られた染色体データをデコードしてスケジューリングの
パラメータを求め、得られたパラメータに基づくシミュ
レーションを指示するメッセージをフライトオブジェク
ト４１に送る。
られた染色体データをデコードしてスケジューリングの
パラメータを求め、得られたパラメータに基づくシミュ
レーションを指示するメッセージをフライトオブジェク
ト４１に送る。
【００７３】フライトオブジェクト２１は、空港やスポ
ットのデータを保持しており、渡されたパラメータに基
づいてフライトシミュレーションを行って、得られたシ
ミュレーション結果をフライトスケジュール管理部４２
に返す。
ットのデータを保持しており、渡されたパラメータに基
づいてフライトシミュレーションを行って、得られたシ
ミュレーション結果をフライトスケジュール管理部４２
に返す。
【００７４】フライトスケジュール管理部４２は、返さ
れたシミュレーション結果から所定のアルゴリズムによ
り適応度を計算し、それを出力する。また、終了条件が
満たされると、その時点で最高の適応度を持つ染色体を
デコードし、得られたパラメータにより記述される航空
ダイヤをスケジュール結果として出力する。
れたシミュレーション結果から所定のアルゴリズムによ
り適応度を計算し、それを出力する。また、終了条件が
満たされると、その時点で最高の適応度を持つ染色体を
デコードし、得られたパラメータにより記述される航空
ダイヤをスケジュール結果として出力する。
【００７５】航空ダイヤに含まれる各便の便データは、
例えば、図１５に示すように、便名（Flight-ID ）、希
望出発時刻（Depart-time ）、時間幅（Time-Window
）、および割当可能機種（Available-Ship-Type ）の
情報により指定される。ここでは、便名は＃３であり、
希望出発時刻は１０：００であり、時間幅は−２０分お
よび＋１０分である。これは、＃３便の出発時刻が９：
４０〜１０：１０の間に制限されることを意味してい
る。また、割当可能機種（Ship-Type ）はＢ−７４７、
Ｂ−７７７、およびＢ−７６７に制限される。
例えば、図１５に示すように、便名（Flight-ID ）、希
望出発時刻（Depart-time ）、時間幅（Time-Window
）、および割当可能機種（Available-Ship-Type ）の
情報により指定される。ここでは、便名は＃３であり、
希望出発時刻は１０：００であり、時間幅は−２０分お
よび＋１０分である。これは、＃３便の出発時刻が９：
４０〜１０：１０の間に制限されることを意味してい
る。また、割当可能機種（Ship-Type ）はＢ−７４７、
Ｂ−７７７、およびＢ−７６７に制限される。
【００７６】この場合、これらの制限を守りながら、割
当不能な便が発生しないように、すべての便の出発時刻
と機種を決定することがスケジューリングの目的とな
る。今、航空ダイヤに含まれる便の便名が＃１，＃２，
＃３，．．．，＃ｌａｓｔであるとすると、この問題を
扱うための染色体データは、例えば、図１６に示すよう
にコーディングされる。
当不能な便が発生しないように、すべての便の出発時刻
と機種を決定することがスケジューリングの目的とな
る。今、航空ダイヤに含まれる便の便名が＃１，＃２，
＃３，．．．，＃ｌａｓｔであるとすると、この問題を
扱うための染色体データは、例えば、図１６に示すよう
にコーディングされる。
【００７７】図１６の染色体において、各便のデータは
ＴｉｍｅおよびＳｈｉｐ−Ｔｙｐｅの２つの遺伝子座を
有し、それらの対立遺伝子は０〜２５５であるものとす
る。ここで、Ｔｉｍｅの遺伝子の値をｔとし、Ｓｈｉｐ
−Ｔｙｐｅの遺伝子の値をｓとすると、＃３便の出発時
刻および機種は次式により与えられる。 出発時刻＝（ｔ％７）に対応する時刻 （８） 機種＝（ｓ％３）に対応する機種 （９） “％”は剰余演算を表し、例えば、ｔ％７はｔを７で割
ったときの剰余（０，１，２，３，４，５，６）に対応
する。ｓ％３についても同様である。また、得られた剰
余の値と時刻／機種との対応関係は、図１７に示すよう
になる。図１７では、出発時刻の候補として、９：４０
〜１０：１０を５分間隔で区切って得られる７つの時刻
が用いられており、それぞれの時刻に対して１つの剰余
の値が対応付けられている。また、３つの割当可能機種
Ｂ−７４７、Ｂ−７７７、およびＢ−７６７のそれぞれ
に対して、１つの剰余の値が対応付けられている。
ＴｉｍｅおよびＳｈｉｐ−Ｔｙｐｅの２つの遺伝子座を
有し、それらの対立遺伝子は０〜２５５であるものとす
る。ここで、Ｔｉｍｅの遺伝子の値をｔとし、Ｓｈｉｐ
−Ｔｙｐｅの遺伝子の値をｓとすると、＃３便の出発時
刻および機種は次式により与えられる。 出発時刻＝（ｔ％７）に対応する時刻 （８） 機種＝（ｓ％３）に対応する機種 （９） “％”は剰余演算を表し、例えば、ｔ％７はｔを７で割
ったときの剰余（０，１，２，３，４，５，６）に対応
する。ｓ％３についても同様である。また、得られた剰
余の値と時刻／機種との対応関係は、図１７に示すよう
になる。図１７では、出発時刻の候補として、９：４０
〜１０：１０を５分間隔で区切って得られる７つの時刻
が用いられており、それぞれの時刻に対して１つの剰余
の値が対応付けられている。また、３つの割当可能機種
Ｂ−７４７、Ｂ−７７７、およびＢ−７６７のそれぞれ
に対して、１つの剰余の値が対応付けられている。
【００７８】このような対応関係を＃１〜＃ｌａｓｔの
すべての便に対して定義すれば、（８）、（９）式と同
様の剰余演算により、染色体データをデコードすること
ができる。フライトスケジュール管理部４２は、こうし
て得られたすべての便の出発時刻、割当機種等のパラメ
ータをフライトオブジェクト４１に渡し、フライトオブ
ジェクト４１は、それらのパラメータにより記述される
航空ダイヤのシミュレーションを行う。適応度は、得ら
れたシミュレーション結果に応じて動的に計算される。
すべての便に対して定義すれば、（８）、（９）式と同
様の剰余演算により、染色体データをデコードすること
ができる。フライトスケジュール管理部４２は、こうし
て得られたすべての便の出発時刻、割当機種等のパラメ
ータをフライトオブジェクト４１に渡し、フライトオブ
ジェクト４１は、それらのパラメータにより記述される
航空ダイヤのシミュレーションを行う。適応度は、得ら
れたシミュレーション結果に応じて動的に計算される。
【００７９】このような航空ダイヤのスケジューリング
以外にも、配送計画問題、人員配置問題、工場等におけ
るショップスケジューリング等の様々な最適化問題に対
して、本発明を適用することができる。
以外にも、配送計画問題、人員配置問題、工場等におけ
るショップスケジューリング等の様々な最適化問題に対
して、本発明を適用することができる。
【００８０】ところで、図２および図９の処理装置は、
例えば、図１８に示すような情報処理装置（コンピュー
タ）を用いて構成することができる。図１８の情報処理
装置は、ＣＰＵ（中央処理装置）５１、メモリ５２、入
力装置５３、出力装置５４、外部記憶装置５５、媒体駆
動装置５６、およびネットワーク接続装置５７を備え、
それらはバス５８により互いに接続されている。
例えば、図１８に示すような情報処理装置（コンピュー
タ）を用いて構成することができる。図１８の情報処理
装置は、ＣＰＵ（中央処理装置）５１、メモリ５２、入
力装置５３、出力装置５４、外部記憶装置５５、媒体駆
動装置５６、およびネットワーク接続装置５７を備え、
それらはバス５８により互いに接続されている。
【００８１】メモリ５２は、例えば、ＲＯＭ（read onl
y memory）、ＲＡＭ（random access memory）等を含
み、処理に用いられるプログラムとデータを格納する。
ＣＰＵ５１は、メモリ５２を利用してプログラムを実行
することにより、必要な処理を行う。
y memory）、ＲＡＭ（random access memory）等を含
み、処理に用いられるプログラムとデータを格納する。
ＣＰＵ５１は、メモリ５２を利用してプログラムを実行
することにより、必要な処理を行う。
【００８２】例えば、図２の初期染色体発生部２１、Ｇ
Ａ演算部２３、遺伝子統計演算部２４、染色体発生部２
６、染色体選択部２７、終了判定部２８、および確率モ
デル制御部２９と、図９のＧＡ間制御部３１、ＧＡ部３
２、確率モデル間制御部３４、および距離計算部３５
は、プログラムにより記述されたソフトウェアコンポー
ネントとして、メモリ５２の特定のプログラムコードセ
グメントに格納される。
Ａ演算部２３、遺伝子統計演算部２４、染色体発生部２
６、染色体選択部２７、終了判定部２８、および確率モ
デル制御部２９と、図９のＧＡ間制御部３１、ＧＡ部３
２、確率モデル間制御部３４、および距離計算部３５
は、プログラムにより記述されたソフトウェアコンポー
ネントとして、メモリ５２の特定のプログラムコードセ
グメントに格納される。
【００８３】また、図２の染色体集団記憶部２２および
確率モデル記憶部２５と、図９の確率モデル記憶部３３
は、メモリ５２の特定の記憶領域に対応する。図９に示
した並列ＧＡの場合、複数のＧＡ部３２は、マルチタス
ク処理により、並行して最適化演算を行う。
確率モデル記憶部２５と、図９の確率モデル記憶部３３
は、メモリ５２の特定の記憶領域に対応する。図９に示
した並列ＧＡの場合、複数のＧＡ部３２は、マルチタス
ク処理により、並行して最適化演算を行う。
【００８４】入力装置５３は、例えば、キーボード、ポ
インティングデバイス、タッチパネル等であり、ユーザ
からの指示や情報の入力に用いられる。出力装置５４
は、例えば、ディスプレイ、プリンタ、スピーカ等であ
り、ユーザへの問い合わせや処理結果の出力に用いられ
る。
インティングデバイス、タッチパネル等であり、ユーザ
からの指示や情報の入力に用いられる。出力装置５４
は、例えば、ディスプレイ、プリンタ、スピーカ等であ
り、ユーザへの問い合わせや処理結果の出力に用いられ
る。
【００８５】外部記憶装置５５は、例えば、磁気ディス
ク装置、光ディスク装置、光磁気ディスク装置、テープ
装置等である。情報処理装置は、この外部記憶装置５５
に、上述のプログラムとデータを保存しておき、必要に
応じて、それらをメモリ５２にロードして使用する。
ク装置、光ディスク装置、光磁気ディスク装置、テープ
装置等である。情報処理装置は、この外部記憶装置５５
に、上述のプログラムとデータを保存しておき、必要に
応じて、それらをメモリ５２にロードして使用する。
【００８６】媒体駆動装置５６は、可搬記録媒体５９を
駆動し、その記録内容にアクセスする。可搬記録媒体５
９としては、メモリカード、フロッピー（登録商標）デ
ィスク、ＣＤ−ＲＯＭ（compact disk read only memor
y ）、光ディスク、光磁気ディスク等、任意のコンピュ
ータ読み取り可能な記録媒体が用いられる。ユーザは、
この可搬記録媒体５９に上述のプログラムとデータを格
納しておき、必要に応じて、それらをメモリ５２にロー
ドして使用する。
駆動し、その記録内容にアクセスする。可搬記録媒体５
９としては、メモリカード、フロッピー（登録商標）デ
ィスク、ＣＤ−ＲＯＭ（compact disk read only memor
y ）、光ディスク、光磁気ディスク等、任意のコンピュ
ータ読み取り可能な記録媒体が用いられる。ユーザは、
この可搬記録媒体５９に上述のプログラムとデータを格
納しておき、必要に応じて、それらをメモリ５２にロー
ドして使用する。
【００８７】ネットワーク接続装置５７は、ＬＡＮ（lo
cal area network）等の任意の通信ネットワークに接続
され、通信に伴うデータ変換を行う。また、情報処理装
置は、上述のプログラムとデータをネットワーク接続装
置５７を介して他の装置から受け取り、必要に応じて、
それらをメモリ５２にロードして使用する。
cal area network）等の任意の通信ネットワークに接続
され、通信に伴うデータ変換を行う。また、情報処理装
置は、上述のプログラムとデータをネットワーク接続装
置５７を介して他の装置から受け取り、必要に応じて、
それらをメモリ５２にロードして使用する。
【００８８】図１９は、図１８の情報処理装置にプログ
ラムとデータを供給することのできるコンピュータ読み
取り可能な記録媒体を示している。可搬記録媒体５９や
サーバ６０のデータベース６１に保存されたプログラム
とデータは、メモリ５２にロードされる。このとき、サ
ーバ６０は、プログラムとデータを搬送する搬送信号を
生成し、ネットワーク上の任意の伝送媒体を介して情報
処理装置に送信する。そして、ＣＰＵ５１は、そのデー
タを用いてそのプログラムを実行し、必要な処理を行
う。
ラムとデータを供給することのできるコンピュータ読み
取り可能な記録媒体を示している。可搬記録媒体５９や
サーバ６０のデータベース６１に保存されたプログラム
とデータは、メモリ５２にロードされる。このとき、サ
ーバ６０は、プログラムとデータを搬送する搬送信号を
生成し、ネットワーク上の任意の伝送媒体を介して情報
処理装置に送信する。そして、ＣＰＵ５１は、そのデー
タを用いてそのプログラムを実行し、必要な処理を行
う。
【００８９】また、図９の最適化問題処理装置は、図１
８のような情報処理装置以外にも、複数のプロセッシン
グエレメント（ＰＥ）を搭載した並列計算機により実現
することができる。この場合、各ＰＥが各ＧＡ部３２の
プログラムを実行することで、並列処理が行われる。
８のような情報処理装置以外にも、複数のプロセッシン
グエレメント（ＰＥ）を搭載した並列計算機により実現
することができる。この場合、各ＰＥが各ＧＡ部３２の
プログラムを実行することで、並列処理が行われる。
【００９０】（付記１） 遺伝的アルゴリズムを用いた
最適化問題処理装置であって、個体集団の情報を格納す
る集団格納手段と、前記個体集団の対立遺伝子の出現確
率を表す確率モデルの情報を格納するモデル格納手段
と、前記確率モデルを参照して新たな個体を生成し、生
成した個体を次世代の個体として前記集団格納手段に格
納する発生手段と、前記集団格納手段内の個体集団に対
して遺伝的アルゴリズムの操作を施す操作手段と操作結
果を出力する出力手段とを備えることを特徴とする最適
化問題処理装置。 （付記２） 前記発生手段は、１つの個体の複数の遺伝
子座について、高い出現確率を有する対立遺伝子同士を
組み合わせることで、前記新たな個体を生成することを
特徴とする付記１記載の最適化問題処理装置。 （付記３） 遺伝的アルゴリズムを用いた最適化問題処
理装置であって、個体集団の情報を格納する集団格納手
段と、前記個体集団の対立遺伝子の出現確率を表す確率
モデルの情報を格納するモデル格納手段と、前記確率モ
デルを参照して前記個体集団から個体を選択し、選択し
た個体を次世代の個体として前記集団格納手段に格納す
る選択手段と、前記集団格納手段内の個体集団に対して
遺伝的アルゴリズムの操作を施す操作手段と操作結果を
出力する出力手段とを備えることを特徴とする最適化問
題処理装置。 （付記４） 前記選択手段は、前記確率モデルに基づく
実効評価関数を用いて前記個体集団の個体を評価し、評
価の良い順に所定数の個体を選択することを特徴とする
付記３記載の最適化問題処理装置。 （付記５） 遺伝的アルゴリズムを用いた最適化問題処
理装置であって、複数の個体集団の情報をそれぞれ格納
する複数の集団格納手段と、各個体集団の対立遺伝子の
出現確率を表す確率モデルの情報を格納する複数のモデ
ル格納手段と、前記確率モデルを参照して、前記複数の
個体集団のうちの２つの集団を比較し、該２つの集団の
少なくとも一方から個体を選択し、選択した個体を次世
代の個体として、対応する集団格納手段に格納する選択
手段と、前記複数の集団格納手段内の個体集団に対し
て、それぞれ遺伝的アルゴリズムの操作を施す複数の操
作手段と操作結果を出力する出力手段とを備えることを
特徴とする最適化問題処理装置。 （付記６） 前記選択手段は、前記２つの集団のうち一
方の集団の確率モデルに基づく実効評価関数を用いて、
該２つの集団のうち他方の集団の個体を評価し、該他方
の集団から評価の良い順に所定数の個体を選択すること
を特徴とする付記５記載の最適化問題処理装置。 （付記７） 遺伝的アルゴリズムを用いて最適化問題を
処理するコンピュータのためのプログラムであって、個
体集団の情報を、前記コンピュータの集団記憶部に格納
し、前記個体集団の対立遺伝子の出現確率を表す確率モ
デルの情報を、前記コンピュータのモデル記憶部に格納
し、前記確率モデルを参照して新たな個体を生成し、生
成した個体を次世代の個体として前記集団記憶部に格納
し、前記集団記憶部内の個体集団に対して遺伝的アルゴ
リズムの操作を施し、操作結果を出力する処理を前記コ
ンピュータに実行させるためのプログラム。 （付記８） 遺伝的アルゴリズムを用いて最適化問題を
処理するコンピュータのためのプログラムであって、個
体集団の情報を、前記コンピュータの集団記憶部に格納
し、前記個体集団の対立遺伝子の出現確率を表す確率モ
デルの情報を、前記コンピュータのモデル記憶部に格納
し、前記確率モデルを参照して前記個体集団から個体を
選択し、選択した個体を次世代の個体として前記集団記
憶部に格納し、前記集団記憶部内の個体集団に対して遺
伝的アルゴリズムの操作を施し、操作結果を出力する処
理を前記コンピュータに実行させるためのプログラム。 （付記９） 遺伝的アルゴリズムを用いて最適化問題を
処理するコンピュータのためのプログラムであって、複
数の個体集団の情報を、前記コンピュータの複数の集団
記憶部にそれぞれ格納し、各個体集団の対立遺伝子の出
現確率を表す確率モデルの情報を、前記コンピュータの
複数のモデル格納手段に格納し、前記確率モデルを参照
して、前記複数の個体集団のうちの２つの集団の確率モ
デルを比較し、該２つの集団の少なくとも一方から個体
を選択し、選択した個体を次世代の個体として、対応す
る集団記憶部に格納し、前記複数の集団記憶部内の個体
集団に対して、それぞれ遺伝的アルゴリズムの操作を施
し、操作結果を出力する処理を前記コンピュータに実行
させるためのプログラム。 （付記１０） 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムを記録した
記録媒体であって、該プログラムは、個体集団の情報
を、前記コンピュータの集団記憶部に格納し、前記個体
集団の対立遺伝子の出現確率を表す確率モデルの情報
を、前記コンピュータのモデル記憶部に格納し、前記確
率モデルを参照して新たな個体を生成し、生成した個体
を次世代の個体として前記集団記憶部に格納し、前記集
団記憶部内の個体集団に対して遺伝的アルゴリズムの操
作を施し、操作結果を出力する処理を前記コンピュータ
に実行させることを特徴とするコンピュータ読み取り可
能な記録媒体。 （付記１１） 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムを記録した
記録媒体であって、該プログラムは、個体集団の情報
を、前記コンピュータの集団記憶部に格納し、前記個体
集団の対立遺伝子の出現確率を表す確率モデルの情報
を、前記コンピュータのモデル記憶部に格納し、前記確
率モデルを参照して前記個体集団から個体を選択し、選
択した個体を次世代の個体として前記集団記憶部に格納
し、前記集団記憶部内の個体集団に対して遺伝的アルゴ
リズムの操作を施し、操作結果を出力する処理を前記コ
ンピュータに実行させることを特徴とするコンピュータ
読み取り可能な記録媒体。 （付記１２） 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムを記録した
記録媒体であって、該プログラムは、複数の個体集団の
情報を、前記コンピュータの複数の集団記憶部にそれぞ
れ格納し、各個体集団の対立遺伝子の出現確率を表す確
率モデルの情報を、前記コンピュータの複数のモデル格
納手段に格納し、前記確率モデルを参照して、前記複数
の個体集団のうちの２つの集団の確率モデルを比較し、
該２つの集団の少なくとも一方から個体を選択し、選択
した個体を次世代の個体として、対応する集団記憶部に
格納し、前記複数の集団記憶部内の個体集団に対して、
それぞれ遺伝的アルゴリズムの操作を施し、操作結果を
出力する処理を前記コンピュータに実行させることを特
徴とするコンピュータ読み取り可能な記録媒体。
最適化問題処理装置であって、個体集団の情報を格納す
る集団格納手段と、前記個体集団の対立遺伝子の出現確
率を表す確率モデルの情報を格納するモデル格納手段
と、前記確率モデルを参照して新たな個体を生成し、生
成した個体を次世代の個体として前記集団格納手段に格
納する発生手段と、前記集団格納手段内の個体集団に対
して遺伝的アルゴリズムの操作を施す操作手段と操作結
果を出力する出力手段とを備えることを特徴とする最適
化問題処理装置。 （付記２） 前記発生手段は、１つの個体の複数の遺伝
子座について、高い出現確率を有する対立遺伝子同士を
組み合わせることで、前記新たな個体を生成することを
特徴とする付記１記載の最適化問題処理装置。 （付記３） 遺伝的アルゴリズムを用いた最適化問題処
理装置であって、個体集団の情報を格納する集団格納手
段と、前記個体集団の対立遺伝子の出現確率を表す確率
モデルの情報を格納するモデル格納手段と、前記確率モ
デルを参照して前記個体集団から個体を選択し、選択し
た個体を次世代の個体として前記集団格納手段に格納す
る選択手段と、前記集団格納手段内の個体集団に対して
遺伝的アルゴリズムの操作を施す操作手段と操作結果を
出力する出力手段とを備えることを特徴とする最適化問
題処理装置。 （付記４） 前記選択手段は、前記確率モデルに基づく
実効評価関数を用いて前記個体集団の個体を評価し、評
価の良い順に所定数の個体を選択することを特徴とする
付記３記載の最適化問題処理装置。 （付記５） 遺伝的アルゴリズムを用いた最適化問題処
理装置であって、複数の個体集団の情報をそれぞれ格納
する複数の集団格納手段と、各個体集団の対立遺伝子の
出現確率を表す確率モデルの情報を格納する複数のモデ
ル格納手段と、前記確率モデルを参照して、前記複数の
個体集団のうちの２つの集団を比較し、該２つの集団の
少なくとも一方から個体を選択し、選択した個体を次世
代の個体として、対応する集団格納手段に格納する選択
手段と、前記複数の集団格納手段内の個体集団に対し
て、それぞれ遺伝的アルゴリズムの操作を施す複数の操
作手段と操作結果を出力する出力手段とを備えることを
特徴とする最適化問題処理装置。 （付記６） 前記選択手段は、前記２つの集団のうち一
方の集団の確率モデルに基づく実効評価関数を用いて、
該２つの集団のうち他方の集団の個体を評価し、該他方
の集団から評価の良い順に所定数の個体を選択すること
を特徴とする付記５記載の最適化問題処理装置。 （付記７） 遺伝的アルゴリズムを用いて最適化問題を
処理するコンピュータのためのプログラムであって、個
体集団の情報を、前記コンピュータの集団記憶部に格納
し、前記個体集団の対立遺伝子の出現確率を表す確率モ
デルの情報を、前記コンピュータのモデル記憶部に格納
し、前記確率モデルを参照して新たな個体を生成し、生
成した個体を次世代の個体として前記集団記憶部に格納
し、前記集団記憶部内の個体集団に対して遺伝的アルゴ
リズムの操作を施し、操作結果を出力する処理を前記コ
ンピュータに実行させるためのプログラム。 （付記８） 遺伝的アルゴリズムを用いて最適化問題を
処理するコンピュータのためのプログラムであって、個
体集団の情報を、前記コンピュータの集団記憶部に格納
し、前記個体集団の対立遺伝子の出現確率を表す確率モ
デルの情報を、前記コンピュータのモデル記憶部に格納
し、前記確率モデルを参照して前記個体集団から個体を
選択し、選択した個体を次世代の個体として前記集団記
憶部に格納し、前記集団記憶部内の個体集団に対して遺
伝的アルゴリズムの操作を施し、操作結果を出力する処
理を前記コンピュータに実行させるためのプログラム。 （付記９） 遺伝的アルゴリズムを用いて最適化問題を
処理するコンピュータのためのプログラムであって、複
数の個体集団の情報を、前記コンピュータの複数の集団
記憶部にそれぞれ格納し、各個体集団の対立遺伝子の出
現確率を表す確率モデルの情報を、前記コンピュータの
複数のモデル格納手段に格納し、前記確率モデルを参照
して、前記複数の個体集団のうちの２つの集団の確率モ
デルを比較し、該２つの集団の少なくとも一方から個体
を選択し、選択した個体を次世代の個体として、対応す
る集団記憶部に格納し、前記複数の集団記憶部内の個体
集団に対して、それぞれ遺伝的アルゴリズムの操作を施
し、操作結果を出力する処理を前記コンピュータに実行
させるためのプログラム。 （付記１０） 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムを記録した
記録媒体であって、該プログラムは、個体集団の情報
を、前記コンピュータの集団記憶部に格納し、前記個体
集団の対立遺伝子の出現確率を表す確率モデルの情報
を、前記コンピュータのモデル記憶部に格納し、前記確
率モデルを参照して新たな個体を生成し、生成した個体
を次世代の個体として前記集団記憶部に格納し、前記集
団記憶部内の個体集団に対して遺伝的アルゴリズムの操
作を施し、操作結果を出力する処理を前記コンピュータ
に実行させることを特徴とするコンピュータ読み取り可
能な記録媒体。 （付記１１） 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムを記録した
記録媒体であって、該プログラムは、個体集団の情報
を、前記コンピュータの集団記憶部に格納し、前記個体
集団の対立遺伝子の出現確率を表す確率モデルの情報
を、前記コンピュータのモデル記憶部に格納し、前記確
率モデルを参照して前記個体集団から個体を選択し、選
択した個体を次世代の個体として前記集団記憶部に格納
し、前記集団記憶部内の個体集団に対して遺伝的アルゴ
リズムの操作を施し、操作結果を出力する処理を前記コ
ンピュータに実行させることを特徴とするコンピュータ
読み取り可能な記録媒体。 （付記１２） 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムを記録した
記録媒体であって、該プログラムは、複数の個体集団の
情報を、前記コンピュータの複数の集団記憶部にそれぞ
れ格納し、各個体集団の対立遺伝子の出現確率を表す確
率モデルの情報を、前記コンピュータの複数のモデル格
納手段に格納し、前記確率モデルを参照して、前記複数
の個体集団のうちの２つの集団の確率モデルを比較し、
該２つの集団の少なくとも一方から個体を選択し、選択
した個体を次世代の個体として、対応する集団記憶部に
格納し、前記複数の集団記憶部内の個体集団に対して、
それぞれ遺伝的アルゴリズムの操作を施し、操作結果を
出力する処理を前記コンピュータに実行させることを特
徴とするコンピュータ読み取り可能な記録媒体。
【００９１】
【発明の効果】本発明によれば、ＧＡの染色体集団から
生成した確率モデルを用いて、ＧＡ操作を効率化するよ
うな染色体を次世代に組み入れることが可能となる。し
たがって、確率モデルを用いない場合より解の探索効率
が向上する。
生成した確率モデルを用いて、ＧＡ操作を効率化するよ
うな染色体を次世代に組み入れることが可能となる。し
たがって、確率モデルを用いない場合より解の探索効率
が向上する。
【００９２】また、並列ＧＡの各染色体集団の確率モデ
ルを用いて集団間の差異を評価することで、これらの集
団を異なる領域に分散させることが可能となる。したが
って、並列ＧＡの探索効率が向上する。
ルを用いて集団間の差異を評価することで、これらの集
団を異なる領域に分散させることが可能となる。したが
って、並列ＧＡの探索効率が向上する。
【図１】本発明の最適化問題処理装置の原理図である。
【図２】第１の処理装置の構成図である。
【図３】第１のＧＡ処理のフローチャートである。
【図４】第１の染色体集団と評価関数値を示す図であ
る。
る。
【図５】単純ＧＡの確率モデルを示す図である。
【図６】コンセンサス配列を示す図である。
【図７】染色体集団とコンセンサス配列の比較を示す図
である。
である。
【図８】第１の実効評価関数値を示す図である。
【図９】第２の処理装置の構成図である。
【図１０】第２のＧＡ処理のフローチャートである。
【図１１】並列ＧＡの確率モデルを示す図である。
【図１２】第２の染色体集団と評価関数値を示す図であ
る。
る。
【図１３】第２の実効評価関数値を示す図である。
【図１４】ＧＡ演算部およびＧＡ部の例を示す図であ
る。
る。
【図１５】便データの指定例を示す図である。
【図１６】染色体データを示す図である。
【図１７】デコードのための対応関係を示す図である。
【図１８】情報処理装置の構成図である。
【図１９】記録媒体を示す図である。
１１ 集団格納手段
１２ モデル格納手段
１３ 発生手段
１４ 選択手段
１５ 操作手段
１６ 出力手段
２１ 初期染色体発生部
２２ 染色体集団記憶部
２３ ＧＡ演算部
２４ 遺伝子統計演算部
２５、３３ 確率モデル記憶部
２６ 染色体発生部
２７ 染色体選択部
２８ 終了判定部
２９ 確率モデル制御部
３１ ＧＡ間制御部
３２ ＧＡ部
３４ 確率モデル間制御部
３５ 距離計算部
４１ フライトオブジェクト
４２ フライトスケジュール管理部
５１ ＣＰＵ
５２ メモリ
５３ 入力装置
５４ 出力装置
５５ 外部記憶装置
５６ 媒体駆動装置
５７ ネットワーク接続装置
５８ バス
５９ 可搬記録媒体
６０ サーバ
６１ データベース
Claims (5)
- 【請求項１】 遺伝的アルゴリズムを用いた最適化問題
処理装置であって、 個体集団の情報を格納する集団格納手段と、 前記個体集団の対立遺伝子の出現確率を表す確率モデル
の情報を格納するモデル格納手段と、 前記確率モデルを参照して新たな個体を生成し、生成し
た個体を次世代の個体として前記集団格納手段に格納す
る発生手段と、 前記集団格納手段内の個体集団に対して遺伝的アルゴリ
ズムの操作を施す操作手段と操作結果を出力する出力手
段とを備えることを特徴とする最適化問題処理装置。 - 【請求項２】 遺伝的アルゴリズムを用いた最適化問題
処理装置であって、 個体集団の情報を格納する集団格納手段と、 前記個体集団の対立遺伝子の出現確率を表す確率モデル
の情報を格納するモデル格納手段と、 前記確率モデルを参照して前記個体集団から個体を選択
し、選択した個体を次世代の個体として前記集団格納手
段に格納する選択手段と、 前記集団格納手段内の個体集団に対して遺伝的アルゴリ
ズムの操作を施す操作手段と操作結果を出力する出力手
段とを備えることを特徴とする最適化問題処理装置。 - 【請求項３】 遺伝的アルゴリズムを用いた最適化問題
処理装置であって、 複数の個体集団の情報をそれぞれ格納する複数の集団格
納手段と、 各個体集団の対立遺伝子の出現確率を表す確率モデルの
情報を格納する複数のモデル格納手段と、 前記確率モデルを参照して、前記複数の個体集団のうち
の２つの集団を比較し、該２つの集団の少なくとも一方
から個体を選択し、選択した個体を次世代の個体とし
て、対応する集団格納手段に格納する選択手段と、 前記複数の集団格納手段内の個体集団に対して、それぞ
れ遺伝的アルゴリズムの操作を施す複数の操作手段と操
作結果を出力する出力手段とを備えることを特徴とする
最適化問題処理装置。 - 【請求項４】 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムであって、 個体集団の情報を、前記コンピュータの集団記憶部に格
納し、 前記個体集団の対立遺伝子の出現確率を表す確率モデル
の情報を、前記コンピュータのモデル記憶部に格納し、 前記確率モデルを参照して新たな個体を生成し、 生成した個体を次世代の個体として前記集団記憶部に格
納し、 前記集団記憶部内の個体集団に対して遺伝的アルゴリズ
ムの操作を施し、 操作結果を出力する処理を前記コンピュータに実行させ
るためのプログラム。 - 【請求項５】 遺伝的アルゴリズムを用いて最適化問題
を処理するコンピュータのためのプログラムであって、 個体集団の情報を、前記コンピュータの集団記憶部に格
納し、 前記個体集団の対立遺伝子の出現確率を表す確率モデル
の情報を、前記コンピュータのモデル記憶部に格納し、 前記確率モデルを参照して前記個体集団から個体を選択
し、 選択した個体を次世代の個体として前記集団記憶部に格
納し、 前記集団記憶部内の個体集団に対して遺伝的アルゴリズ
ムの操作を施し、 操作結果を出力する処理を前記コンピュータに実行させ
るためのプログラム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001203208A JP2003016421A (ja) | 2001-07-04 | 2001-07-04 | 最適化問題処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2001203208A JP2003016421A (ja) | 2001-07-04 | 2001-07-04 | 最適化問題処理装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2003016421A true JP2003016421A (ja) | 2003-01-17 |
Family
ID=19039886
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001203208A Pending JP2003016421A (ja) | 2001-07-04 | 2001-07-04 | 最適化問題処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2003016421A (ja) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005056421A (ja) * | 2003-08-05 | 2005-03-03 | Mitsubishi Electric Research Laboratories Inc | 複数の要素および複数の値を含む組合せ最適化問題を解く方法 |
| JP2005202960A (ja) * | 2004-01-12 | 2005-07-28 | Honda Research Inst Europe Gmbh | 最適化方法及び最適化プログラム |
| US8250007B2 (en) | 2009-10-07 | 2012-08-21 | King Fahd University Of Petroleum & Minerals | Method of generating precedence-preserving crossover and mutation operations in genetic algorithms |
| KR101522306B1 (ko) * | 2013-05-09 | 2015-05-26 | 서울대학교산학협력단 | 유사도 특성을 이용한 메타휴리스틱 알고리즘에 기반한 시스템 및 그 제어방법 |
| CN110806737A (zh) * | 2019-11-26 | 2020-02-18 | 北京工业大学 | 一种基于最小能耗及最小时间的生产线设备数量优化方法 |
-
2001
- 2001-07-04 JP JP2001203208A patent/JP2003016421A/ja active Pending
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005056421A (ja) * | 2003-08-05 | 2005-03-03 | Mitsubishi Electric Research Laboratories Inc | 複数の要素および複数の値を含む組合せ最適化問題を解く方法 |
| JP2005202960A (ja) * | 2004-01-12 | 2005-07-28 | Honda Research Inst Europe Gmbh | 最適化方法及び最適化プログラム |
| US8250007B2 (en) | 2009-10-07 | 2012-08-21 | King Fahd University Of Petroleum & Minerals | Method of generating precedence-preserving crossover and mutation operations in genetic algorithms |
| KR101522306B1 (ko) * | 2013-05-09 | 2015-05-26 | 서울대학교산학협력단 | 유사도 특성을 이용한 메타휴리스틱 알고리즘에 기반한 시스템 및 그 제어방법 |
| CN110806737A (zh) * | 2019-11-26 | 2020-02-18 | 北京工业大学 | 一种基于最小能耗及最小时间的生产线设备数量优化方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Umam et al. | A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem | |
| CN110632907B (zh) | 一种分布式装配式置换流水车间调度优化方法及系统 | |
| CN114741955B (zh) | 一种基于安全云的多目标优化任务调度方法 | |
| Ahmadizar et al. | A novel hybrid genetic algorithm for the open shop scheduling problem | |
| Faliszewski et al. | Multiwinner voting in genetic algorithms | |
| Shao et al. | Estimation of distribution algorithm with path relinking for the blocking flow-shop scheduling problem | |
| Glass et al. | A comparison of local search methods for flow shop scheduling | |
| Kumar et al. | Performance analysis of proposed mutation operator of genetic algorithm under scheduling problem | |
| Khuri et al. | Genetic algorithms for solving open shop scheduling problems | |
| Tayeb et al. | Research on permutation flow-shop scheduling problem based on improved genetic immune algorithm with vaccinated offspring | |
| Zhou et al. | A game-theory approach for job scheduling in networked manufacturing | |
| CN119690678A (zh) | 一种基于遗传算法解决算力资源利用率的方法 | |
| Pongchairerks et al. | A particle swarm optimization algorithm on job-shop scheduling problems with multi-purpose machines | |
| Mhasawade et al. | A survey of hybrid metaheuristics to minimize makespan of job shop scheduling problem | |
| Du et al. | Genetic crossover operator with staged crossover strategy for the capacitated vehicle routing problem | |
| Kumar et al. | An integrated real time optimization approach (IRTO) for physical programming based redundancy allocation problem | |
| JP3866453B2 (ja) | タブー探索装置 | |
| CN108256694A (zh) | 基于重复遗传算法的模糊时间序列预测系统、方法及装置 | |
| CN115054913B (zh) | 云游戏调度方法、系统与计算机可读存储介质 | |
| Krömer et al. | Traditional and self-adaptive differential evolution for the p-median problem | |
| Wei et al. | A new approach to the traveling salesman problem using genetic algorithms with priority encoding | |
| CN113141272A (zh) | 基于迭代优化rbf神经网络的网络安全态势分析方法 | |
| Xu et al. | Adapted Genetic Algorithm for Orienteering Problem | |
| CN118586679B (zh) | 基于改进多种群遗传算法的多机器人任务分配方法 | |
| CN119168337B (zh) | 一种无人机飞行任务调度方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050301 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050414 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20051108 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20060228 |