(57)【特許請求の範囲】
【請求項１】
与えられた問題の解の候補を表す個体データと該個体データの適応度を格納する個体格納手段と、
前記個体格納手段に格納された個体データに対して、適応度がより高い個体データをより高い確率で選択する選択操作を含む遺伝的操作を施して、新たな個体データを生成し、生成された個体データと該個体データの適応度を該個体格納手段に格納する操作手段と、
比較的高い適応度を持つ個体データと該個体データの適応度の情報を含むテーブルを、タブー情報として格納するタブー格納手段と、
前記生成された個体データの適応度を計算する計算手段と、
前記生成された個体データを前記タブー情報の個体データと比較し、該生成された個体データのうち該タブー情報の個体データと同じかまたは類似する個体データに含まれる複数の値の中で、第１の乱数により決められた位置の値を、第２の乱数により決められた値に変更する処理を行って、前記個体格納手段に格納された解の候補を変更するとともに、該生成された個体データのうち該タブー情報の個体データよりも高い適応度を持つ個体データを該タブー情報に追加するタブー処理手段と
を備えることを特徴とする探索装置。
【請求項２】
前記タブー処理手段は、前記生成された個体データと前記タブー情報の個体データの類似度を計算し、一定値以上の類似度が得られたとき、該生成された個体データが該タブー情報の個体データと同じかまたは類似すると判定することを特徴とする請求項１記載の探索装置。
【請求項３】
与えられた問題の解の候補を表す個体データと該個体データの適応度を格納する個体格納手段と、
前記個体格納手段に格納された個体データに対して、適応度がより高い個体データをより高い確率で選択する選択操作を含む遺伝的操作を施して、新たな個体データを生成し、生成された個体データと該個体データの適応度を該個体格納手段に格納する操作手段と、
比較的高い適応度を持つ個体データと該個体データの適応度の情報を含むテーブルを、タブー情報として格納するタブー格納手段と、
前記生成された個体データの適応度を計算する計算手段と、
前記生成された個体データを前記タブー情報の個体データと比較し、該生成された個体データのうち該タブー情報の個体データと同じかまたは類似する個体データに含まれる複数の値の中で、第１の乱数により決められた位置の値を、第２の乱数により決められた値に変更する処理を行って、前記個体格納手段に格納された解の候補を変更するとともに、該生成された個体データのうち該タブー情報の個体データよりも高い適応度を持つ個体データを該タブー情報に追加するタブー処理手段として、
コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４】
前記タブー処理手段は、前記生成された個体データと前記タブー情報の個体データの類似度を計算し、一定値以上の類似度が得られたとき、該生成された個体データが該タブー情報の個体データと同じかまたは類似すると判定することを特徴とする請求項３記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、遺伝的アルゴリズムのような確率的最適化手法とタブー探索を組み合わせて最適解の探索を行う探索装置およびその方法に関する。
【０００２】
【従来の技術】
近年のコンピュータの性能向上に伴い、従来のエキスパートシステム等で解決が困難であった問題を解決する方法として、遺伝的アルゴリズム（ＧＡ）、シミュレーテッド・アニーリング等の確率的最適化手法が注目を浴びており、最適化問題の実用的な解法として研究されている。現在研究されている様々な確率的最適化手法の中でも、ＧＡは特に注目されている手法である。
【０００３】
また、昨今のコンピュータの低価格化に伴い、問題解決のために豊富なＣＰＵ（中央処理装置）パワーをいかに有効に使いこなすかが課題となっている。この観点においても、ＧＡは、困難な問題を豊富なコンピュータ・パワーで乗り切る手法として有望である。
【０００４】
【発明が解決しようとする課題】
しかしながら、従来のＧＡを利用した問題解決方法には、次のような問題がある。
【０００５】
従来のＧＡでは、評価関数により計算される各個体の適応度を最適化の指標として用い、個体集団に遺伝的操作を施しながら、適応度が最適となる個体を探索している。このように評価関数のみを最適化の指標として用いる枠組みは、ＧＡの大きな長所であるが、それと同時に欠点ともなり得る。
【０００６】
ＧＡは、一般に、局所最適解に捕われにくい手法と言われているが、局所最適解から抜け出る機構は持ち合わせていない。そのため、解空間が大きな実用的問題を解こうとすると、解空間と比較してＧＡの個体数が小さいため、実際には局所最適解に束縛される傾向がある。
【０００７】
また、ＧＡの性質として、解が局所最適解に陥ると同じ遺伝子について評価関数の計算を繰り返し行うというような、非常に非能率な枠組みが見受けられた。本発明の課題は、このようなＧＡの枠組みを改良して、より効率的な最適解の探索を行う探索装置を提供することである。
【０００８】
【課題を解決するための手段】
図１は、本発明の探索装置の原理図である。
本発明の第１の局面において、探索装置は、個体格納手段１、操作手段２、タブー格納手段３、およびタブー処理手段４を備える。
【０００９】
個体格納手段１は、与えられた問題の解の候補を表す個体データを格納し、操作手段２は、個体格納手段１に格納された個体データに遺伝的操作を施して新たな個体データを生成し、生成された個体データを個体格納手段１に格納する。タブー格納手段３は、タブー情報を格納し、タブー処理手段４は、生成された個体データがタブー情報に対応するか否かをチェックし、それがタブー情報に対応するとき、タブー探索（taboo search）のための所定の処理を行う。
【００１０】
個体格納手段１には、与えられた問題に応じてコーディングされた個体データの集団が格納され、操作手段２は、それらの個体データに選択、交叉、突然変異等の遺伝的操作を施して次の世代の個体集団を生成する。
【００１１】
また、タブー格納手段３には、例えば、比較的高い適応度を持つ個体データの情報がタブー情報として格納され、タブー処理手段４は、個体格納手段１の個体データがタブー情報の個体データに対応するか否かをチェックする。そして、これらの個体データが同じまたは類似しているとき、前者が後者に対応すると判定し、タブー探索のための処理を行う。
【００１２】
タブー探索は、近傍探索にある種の制約を課して、探索の行き詰まりを打開するような手順を生成する探索方法である。タブー処理手段４は、例えば、タブー情報に対応する個体データの一部を変更したり、その適応度を変更したりして、その個体データが次の世代に残る可能性を低下させる。
【００１３】
このようなタブー探索のための処理を行いながら遺伝的操作を繰り返せば、タブー情報として登録された個体データの生成が抑制される。したがって、局所最適解に対応する個体データをタブー情報として登録していくことで、局所最適解からの脱出が容易になり、探索が効率化される。
【００１４】
また、本発明の第２の局面において、探索装置は、個体格納手段１、操作手段２、およびタブー処理手段４を備える。
個体格納手段１は、与えられた問題の解の候補を表す個体データを格納し、操作手段２は、個体格納手段１に格納された個体データに遺伝的操作を施して新たな個体データを生成し、生成された個体データを個体格納手段１に格納する。タブー処理手段４は、個体格納手段１に格納された個体データにタブー探索の制約条件を適用し、その制約条件に基づく処理を行う。
【００１５】
タブー探索の制約条件は、例えば、局所最適解に対応する個体データを避けるというような条件であり、タブー処理手段４は、その制約条件に従って、局所最適解に対応する個体データの一部を変更したり、その適応度を変更したりして、その個体データが次の世代に残る可能性を低下させる。
【００１６】
このような制約条件に基づく処理を行いながら遺伝的操作を繰り返せば、局所最適解に対応する個体データの生成が抑制される。したがって、局所最適解からの脱出が容易になり、探索が効率化される。
【００１７】
また、本発明の第３の局面において、探索装置は、タブー処理手段４、候補格納手段５、および探索手段６を備える。
候補格納手段５は、与えられた問題の解の候補を表す候補データを格納し、探索手段６は、候補格納手段５に格納された候補データを用いて確率的最適化手法に基づく計算を行い、与えられた問題の解を探索する。タブー処理手段４は、候補格納手段５に格納された候補データにタブー探索の制約条件を適用し、その制約条件に基づく処理を行う。
【００１８】
候補格納手段５には、ＧＡやシミュレーテッド・アニーリングのような確率的最適化手法における解の候補を表す候補データが格納され、探索手段６は、対応する確率的最適化手法を用いて最適解を探索する。
【００１９】
タブー探索の制約条件は、例えば、局所最適解に対応する候補データを避けるというような条件であり、タブー処理手段４は、その制約条件に従って、局所最適解に対応する候補データが残る可能性を低下させるような処理を行う。
【００２０】
このような制約条件に基づく処理を行いながら探索を続ければ、局所最適解に収束することが防止される。したがって、局所最適解からの脱出が容易になり、探索が効率化される。
【００２１】
また、本発明の別の探索装置は、個体格納手段１、操作手段２、タブー格納手段３、タブー処理手段４、および計算手段を備える。個体格納手段１は、与えられた問題の解の候補を表す個体データとその個体データの適応度を格納する。操作手段２は、個体格納手段１に格納された個体データに対して、適応度がより高い個体データをより高い確率で選択する選択操作を含む遺伝的操作を施して、新たな個体データを生成し、生成された個体データとその個体データの適応度を個体格納手段１に格納する。タブー格納手段３は、比較的高い適応度を持つ個体データとその個体データの適応度の情報を含むテーブルを、タブー情報として格納する。計算手段は、生成された個体データの適応度を計算する。タブー処理手段４は、生成された個体データをタブー情報の個体データと比較し、生成された個体データのうちタブー情報の個体データと同じかまたは類似する個体データに含まれる複数の値の中で、第１の乱数により決められた位置の値を、第２の乱数により決められた値に変更する処理を行って、個体格納手段１に格納された解の候補を変更するとともに、生成された個体データのうちタブー情報の個体データよりも高い適応度を持つ個体データをタブー情報に追加する。
例えば、図１の個体格納手段１および候補格納手段５は、後述する図１７のメモリ３２に対応し、図１の操作手段２および探索手段６は、後述する図２の選択部１２、交叉部１３、および突然変異部１４に対応する。また、例えば、図１のタブー格納手段３は、図２のタブーリスト１６に対応し、図１のタブー処理手段４は、図２のタブーフィルタ１５に対応する。
【００２２】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態では、ＧＡによる最適化の枠組みの中に、新たにタブー探索の概念を導入して、ＧＡと組み合わせる。タブー探索は、近傍探索にある種の制約を課して、探索の行き詰まりを打開するような手順を生成する探索方法である。この制約としては、例えば、解空間における特定の候補または領域をタブーとして除外する方法が用いられる（上田晴康，Jeremy Bowman ，「タブー探索の拡張：タブーツリーアルゴリズム」，人工知能学会全国大会第１２回予稿集，１９９８年）。
【００２３】
このタブー探索をＧＡと組み合わせた場合、局所最適解またはその解に至る経路をタブー情報として登録し、そのような解に対応する個体があまり生成されないように処理を変更することで、局所最適解から抜け出すことが容易になる。
【００２４】
図２は、このようなアルゴリズムを実装したコンピュータを含む探索装置の構成図である。図２の探索装置は、適応度計算部１１、選択部１２、交叉部１３、突然変異部１４、タブーフィルタ１５、およびタブーリスト１６を備える。
【００２５】
このうち、適応度計算部１１、選択部１２、交叉部１３、および突然変異部１４は、一般的なＧＡと同様に、複数の染色体を個体集団として扱い、遺伝的操作により個体集団を変化させる。タブーフィルタ１５は、適応度計算部１１と選択部１２の間に設けられ、タブーリスト１６に蓄積されたタブー情報を参照しながら、タブー探索のための処理を行う。
【００２６】
図３は、図２の探索装置による最適解の探索処理のフローチャートである。探索装置は、まず、与えられた最適化問題のモデルデータを読み込み（ステップＳ１）、ＧＡのためのデータ構造を構築する（ステップＳ２）。このとき、乱数を発生させることで初期集団の各染色体（個体）のデータを生成し、この初期集団を適応度計算部１１に入力する。
【００２７】
次に、適応度計算部１１は、与えられた集団の各個体の解としての評価値を評価関数を用いて計算し、その値を各個体の適応度（fitness ）として記憶して（ステップＳ３）、あらかじめ決められた終了条件の判定を行う（ステップＳ４）。この終了条件としては、個体の適応度や遺伝的操作の繰り返し回数等に関する一定の条件が用いられる。
【００２８】
ここで、終了条件が満たされなければ、次に、タブーフィルタ１５は、タブーリスト１６を参照しながら、与えられた集団のフィルタリングを行う（ステップＳ５）。タブーリスト１６には、例えば、局所最適解のように、比較的高い適応度を持つ個体のデータがタブー情報として登録される。
【００２９】
タブーフィルタ１５は、与えられた各個体のデータをタブーリスト１６に登録されたタブー情報と比較し、登録されている個体よりも高い適応度を持つ個体のデータを、新たにタブー情報としてタブーリスト１６に登録する。また、タブーリスト１６に登録された個体と同じ適応度を持つ個体については、そのデータに変更を加えるか、またはその個体の評価を変更して適応度を変化させる。
【００３０】
次に、選択部１２は、与えられた集団の各個体の適応度をもとに選択操作（selection ）を行い、親となる個体を選択する（ステップＳ６）。次に、交叉部１３は、選択された親の交叉操作（crossover ）を行う（ステップＳ７）。次に、突然変異部１４は、決められた突然変異率に応じた突然変異操作（mutation）を行い（ステップＳ８）、得られた個体集団を適応度計算部１１に入力する。
【００３１】
こうして、選択、交叉、および突然変異の遺伝的操作により、親の個体集団から子の個体集団が生成され、次世代の集団として適応度計算部１１に与えられる。探索装置は、このような処理を複数の世代に渡って繰り返し、ステップＳ４において終了条件が満たされると、処理を終了する。
【００３２】
このように、ＧＡとタブー探索を組み合わせれば、ＧＡの局所最適解に陥った個体を避けて次世代の個体集団を生成することが可能になり、探索の効率化および局所最適解からの脱出が促進される。
【００３３】
図４は、図３のステップＳ３の適応度計算における各個体の処理のフローチャートである。適応度計算部１１は、まず、与えられた個体に対応する染色体データをデコードし（ステップＳ１１）、問題を記述するパラメータを計算する（ステップＳ１２）。そして、そのパラメータを用いて適応度を計算し（ステップＳ１３）、処理を終了する。
【００３４】
図５は、図３のステップＳ５のフィルタリングにおける各個体の処理のフローチャートである。タブーフィルタ１５は、まず、与えられた個体に対応する染色体データをタブーリスト１６の染色体データと比較し、その個体と同じ染色体がタブーリスト１６に登録されているか否かをチェックする（ステップＳ２１）。
【００３５】
同じ染色体がタブーリスト１６に登録されていれば、与えられた個体の染色体を変更し（ステップＳ２２）、処理を終了する。また、同じ染色体がタブーリスト１６に登録されていなければ、その個体の染色体を変更せずに、処理を終了する。
【００３６】
ステップＳ２２においては、まず、１つまたは複数の乱数を発生させ、与えられた個体の染色体上で値（遺伝子）を変更すべき遺伝子座の位置を、それらの乱数により決定する。そして、別の乱数により決められた値で、それらの遺伝子座の値を入れ換えて、新たな染色体を生成する。
【００３７】
このように、タブーリスト１６に登録された個体と同じ個体については、その遺伝子を別の値に積極的に置き換えていくことで、同じ個体の再計算を避けることができる。したがって、局所最適解からの脱出が促進され、探索が効率化される。
【００３８】
また、図６は、図３のステップＳ５のフィルタリングにおける別の処理のフローチャートである。図６のステップＳ３１の処理は、図５のステップＳ２１の処理と同様である。ステップＳ３２において、タブーフィルタ１５は、与えられた個体の適応度に適当な変更率を乗算して新たな適応度を求め、与えられた個体の適応度を変更する。
【００３９】
このように、タブーリスト１６に登録された個体と同じ個体については、その評価を変更して適応度を積極的に置き換えていくことで、同じ個体の再計算が行われにくくなる。したがって、局所最適解からの脱出が促進され、探索が効率化される。
【００４０】
図５および図６においては、タブーリスト１６に登録された個体と同じ個体の染色体データ／適応度を変更しているが、登録された個体と類似した個体についても同様の変更を行うことができる。この場合、タブーフィルタ１５は、与えられた個体と登録された個体の間の類似度を計算し、一定値以上の類似度が得られたとき、与えられた個体の染色体データ／適応度を変更する。このように、同じ個体のみならず、類似した個体についても変更を行うことにより、局所最適解からの脱出がさらに促進される。
【００４１】
次に、図７から図１２までを参照しながら、探索処理の具体例について説明する。ここでは、非常に単純化された系として、図７のようなバイナリ・コーディングによりコーディングされた系を考える。
【００４２】
図７において、４ビット・バイナリコードは、ＧＡの各個体に対応する染色体データを表し、Ｃは、染色体データに対応する十進数を表す。ここでは、１つの染色体は４つの遺伝子座を有し、各遺伝子座の遺伝子が取り得る値（対立遺伝子，allele）は“０”または“１”であるものとする。また、ｘは、個体の値に対応する表現型を表し、Ｃを次式によりデコードすることで得られる。
ｘ＝Ｃ／５      （０≦Ｃ≦１５）                              （１）
このｘは、図４のステップＳ１２のパラメータに対応する。また、ｆ（ｘ）は、適応度を表し、その関数形は次式により与えられる。
ｆ（ｘ）＝（ｘ−１）2       （０≦ｘ≦３）                    （２）
図７のＣとｆ（ｘ）の関係をグラフにすると、図８のようになる。このグラフは、０≦Ｃ≦１５の区間における放物線に対応する。ここで、ｆ（ｘ）が大きいほど最適解に近いものとすると、Ｃ＝１５（ｘ＝３）に最適解があり、Ｃ＝０（ｘ＝０）に局所最適解があることが分かる。
【００４３】
このような系において、個体数４の集団を生成して最適解を探索する場合、例えば、図９から図１１までに示すような処理が行われる。
図９は、第１世代の個体集団を生成する処理を示している。まず、適応度計算部１１は、乱数により初期解の集団を生成し、各個体について適応度を計算する。ここでは、“００１０”、“０００１”、“００１１”、および“００００”の４つの個体が生成され、それらの適応度は、それぞれ、０．３６、０．６４、０．１６、および１．００となる。
【００４４】
次に、タブーフィルタ１５は、タブーリスト１６を参照するが、初期状態ではタブーリスト１６にタブー情報が登録されていない。そこで、与えられた４つの個体についての変更は行わず、これらの中で最高の適応度を持つ個体“００００”をタブー情報としてタブーリスト１６に登録する。このとき、個体“００００”の染色体データそのものを登録してもよく、その識別情報やアドレス情報等を登録してもよい。
【００４５】
次に、選択部１２は、通常のＧＡと同様に、適応度がより高い個体がより多く親として選ばれるような選択確率を用いて、４つの個体から親となる個体の対を選択する。その結果、“００００”と“０００１”の対と、“００００”と“００１０”の対が選択される。
【００４６】
例えば、ｉ番目の個体の適応度をｆｉとすると、ｉ番目の個体が選択される確率Ｐｉ（ｉ＝１，２，３，４）を次式のように定義することができる。
Ｐｉ＝ｆｉ／（ｆ１＋ｆ２＋ｆ３＋ｆ４）                        （３）
このような選択確率によれば、適応度がより高い個体ほど親として選択される確率が高くなる。
【００４７】
次に、交叉部１３は、記号“｜”で示すように、各個体対について交叉する位置を乱数で決定し、親である２つの個体を交叉して子となる２つの個体を生成する。ここでは、交叉の前後で各遺伝子の値が変化しておらず、親と同じデータを持つ子の個体が生成されている。
【００４８】
次に、突然変異部１４は、得られた４つの個体に所定の確率で突然変異を加える。その結果、記号“＊”で示すように、“０００１”の２番目の遺伝子座の値が“０”から“１”に変化し、“０１０１”という新たな個体が生成される。
【００４９】
次に、図１０は、第２世代の個体集団を生成する処理を示している。まず、適応度計算部１１は、図９の処理により生成された第１世代の各個体について適応度を計算する。ここで、“００００”、“０１０１”、“００００”、および“００１０”の４つの個体の適応度は、それぞれ、１．００、０．００、１．００、および０．３６となる。
【００５０】
次に、タブーフィルタ１５は、タブーリスト１６を参照する。このとき、タブーリスト１６には、与えられた集団に含まれている個体と同じ“００００”が登録されている。そこで、図６のフィルタリング処理に基づいて、選択部１２における“００００”の選択確率が低くなるように適応度を変更する。
【００５１】
例えば、図６のステップＳ３２における変更率を０．６とした場合、“００００”の適応度は１．００から０．６０に変更される。これに対して、タブーリスト１６に登録されていない“０１０１”と“００１０”の適応度は変更されない。
【００５２】
また、タブーフィルタ１５は、４つの個体からタブーリスト１６に登録されていないものを選び、選ばれた個体の中で最高の適応度を持つ個体“００１０”をタブーリスト１６に追加登録する。
【００５３】
次に、選択部１２は、変更された適応度に基づく選択確率を用いて、４つの個体から親となる個体の対を選択する。その結果、“０１０１”と“００１０”の対と、“００１０”と“００００”の対が選択される。
【００５４】
次に、交叉部１３は、親である２つの個体を交叉して、子となる２つの個体を生成する。その結果、“０１０１”と“００１０”の対から“０１００”と“００１１”が生成され、“００１０”と“００００”の対から“００００”と“００１０”が生成される。
【００５５】
次に、突然変異部１４は、得られた４つの個体に所定の確率で突然変異を加える。その結果、記号“＊”で示すように、“００１１”の１番目の遺伝子座の値が“０”から“１”に変化し、“１０１１”という新たな個体が生成される。
【００５６】
次に、図１１は、第３世代の個体集団を生成する処理を示している。まず、適応度計算部１１は、図１０の処理により生成された第２世代の各個体について適応度を計算する。ここで、“０１００”、“１０１１”、“００００”、および“００１０”の４つの個体の適応度は、それぞれ、０．０４、１．４４、１．００、および０．３６となる。
【００５７】
次に、タブーフィルタ１５は、タブーリスト１６を参照する。このとき、タブーリスト１６には、与えられた集団に含まれている個体と同じ“００００”および“００１０”が登録されている。そこで、選択部１２におけるこれらの個体の選択確率が低くなるように適応度を変更する。
【００５８】
上述したように、図６のステップＳ３２における変更率を０．６とした場合、“００００”の適応度は１．００から０．６０に変更され、“００１０”の適応度は０．３６から０．２１６に変更される。これに対して、タブーリスト１６に登録されていない“０１００”と“１０１１”の適応度は変更されない。
【００５９】
また、タブーフィルタ１５は、４つの個体からタブーリスト１６に登録されていないものを選び、選ばれた個体の中で最高の適応度を持つ個体“１０１１”をタブーリスト１６に追加登録する。
【００６０】
次に、選択部１２は、変更された適応度に基づく選択確率を用いて、４つの個体から親となる個体の対を選択する。その結果、“１０１１”と“０１００”の対と、“１０１１”と“００１０”の対が選択される。
【００６１】
次に、交叉部１３は、親である２つの個体を交叉して、子となる２つの個体を生成する。その結果、“１０１１”と“０１００”の対から“００１１”と“１１００”が生成され、“１０１１”と“００１０”の対から“１０１０”と“００１１”が生成される。
【００６２】
次に、突然変異部１４は、得られた４つの個体に所定の確率で突然変異を加える。その結果、記号“＊”で示すように、“１１００”の３番目の遺伝子座の値が“０”から“１”に変化し、“１１１０”という新たな個体が生成される。
【００６３】
次に、適応度計算部１１は、生成された第３世代の各個体について適応度を計算する。ここで、“００１１”、“１１１０”、“１０１０”、および“００１１”の４つの個体の適応度は、それぞれ、０．１６、３．２４、１．００、および０．１６となる。
【００６４】
ここで、終了条件が満たされて処理が終了すると、得られた４つの個体の中で最高の適応度を持つ“１１１０”（適応度３．２４）が準最適解として採用され、この個体に対応するｘ＝２．８が探索結果として出力される。
【００６５】
この例では、図１０および図１１において、タブーフィルタ１５がタブーリスト１６に登録されたものと同じ個体の適応度を変更することで、探索が効率化されている。これに対して、タブーフィルタ１５がタブーリスト１６に登録されたものと同じ個体の遺伝子の値を変更する場合も、同様にして、探索が効率化される。
【００６６】
図１２は、図１１におけるタブーリスト１６の詳細なデータ構造を示している。タブーリスト１６は、染色体データ、適応度、および登録世代数の情報を含み、例えば、テーブル形式で構成される。各個体の情報はあらかじめ決められたアクセス方法に応じてソートされており、ここでは、適応度の高い順にソートされている。また、染色体データに高速にアクセスするために、ハッシュ法等の仕組みを付加することもある。
【００６７】
タブーリスト１６の登録情報を削除するアルゴリズムとしては、様々なものが考えられる。例えば、格納領域が溢れたら、適応度の低いものまたは登録世代番号の小さい（古い）ものから順に削除してもよく、所定数の世代が経過した後、同様の削除を行ってもよい。
【００６８】
次に、図１３から図１６までを参照しながら、航空ダイヤのスケジューリングに本発明を適用した場合の処理を説明する。
図１３は、この場合の適応度計算部１１の構成を示している。図１３の適応度計算部は、先願の「オブジェクト指向遺伝的アルゴリズムを用いた最適化方法及び装置」（特開平１１−５３３３７）に示されているようにオブジェクト指向プログラミングによりプログラムされ、フライトオブジェクト２１とフライトスケジュール管理部２２を備える。
【００６９】
フライトスケジュール管理部２２は、与えられた染色体データをデコードしてスケジューリングのパラメータを求め、得られたパラメータに基づくシミュレーションを指示するメッセージをフライトオブジェクト２１に送る。
【００７０】
フライトオブジェクト２１は、空港やスポットのデータを保持しており、渡されたパラメータに基づいてフライトシミュレーションを行って、得られたシミュレーション結果をフライトスケジュール管理部２２に返す。
【００７１】
フライトスケジュール管理部２２は、返されたシミュレーション結果から所定のアルゴリズムにより適応度を計算し、それを出力する。また、終了条件が満たされると、その時点で最高の適応度を持つ染色体をデコードし、得られたパラメータにより記述される航空ダイヤをスケジュール結果として出力する。
【００７２】
航空ダイヤに含まれる各便の便データは、例えば、図１４に示すように、便名（Flight-ID ）、希望出発時刻（Depart-time ）、時間幅（Time-Window ）、および割当可能機種（Available-Ship-Type ）の情報により指定される。ここでは、便名は＃３であり、希望出発時刻は１０：００であり、時間幅は−２０分および＋１０分である。これは、＃３便の出発時刻が９：４０〜１０：１０の間に制限されることを意味している。また、割当可能機種（Ship-Type ）はＢ−７４７、Ｂ−７７７、およびＢ−７６７に制限される。
【００７３】
この場合、これらの制限を守りながら、割当不能な便が発生しないように、すべての便の出発時刻と機種を決定することがスケジューリングの目的となる。今、航空ダイヤに含まれる便の便名が＃１，＃２，＃３，．．．，＃ｌａｓｔであるとすると、この問題を扱うための染色体データは、例えば、図１５に示すようにコーディングされる。
【００７４】
図１５の染色体において、各便のデータはＴｉｍｅおよびＳｈｉｐ−Ｔｙｐｅの２つの遺伝子座を有し、それらの対立遺伝子は０〜２５５であるものとする。ここで、Ｔｉｍｅの遺伝子の値をｔとし、Ｓｈｉｐ−Ｔｙｐｅの遺伝子の値をｓとすると、＃３便の出発時刻および機種は次式により与えられる。
出発時刻＝（ｔ％７）に対応する時刻                            （４）
機種＝（ｓ％３）に対応する機種                                （５）
“％”は剰余演算を表し、例えば、ｔ％７はｔを７で割ったときの剰余（０，１，２，３，４，５，６）に対応する。ｓ％３についても同様である。また、得られた剰余の値と時刻／機種との対応関係は、図１６に示すようになる。図１６では、出発時刻の候補として、９：４０〜１０：１０を５分間隔で区切って得られる７つの時刻が用いられており、それぞれの時刻に対して１つの剰余の値が対応付けられている。また、３つの割当可能機種Ｂ−７４７、Ｂ−７７７、およびＢ−７６７のそれぞれに対して、１つの剰余の値が対応付けられている。
【００７５】
このような対応関係を＃１〜＃ｌａｓｔのすべての便に対して定義すれば、（４）、（５）式と同様の剰余演算により、染色体データをデコードすることができる。フライトスケジュール管理部２２は、こうして得られたすべての便の出発時刻、割当機種等のパラメータをフライトオブジェクト２１に渡し、フライトオブジェクト２１は、それらのパラメータにより記述される航空ダイヤのシミュレーションを行う。適応度は、得られたシミュレーション結果に応じて動的に計算される。
【００７６】
このような航空ダイヤのスケジューリング以外にも、配送計画問題、人員配置問題、工場等におけるショップスケジューリング等の様々な最適化問題に対して、本発明を適用することができる。
【００７７】
以上説明した実施形態においては、最適解に近づくほど大きくなる評価値を用いて、各個体の解としての適応度を評価しているが、逆に、最適解に近づくほど小さくなる評価値を用いて適応度を評価してもよい。この場合、最小の評価値を持つ個体が最高の適応度を持つことになる。
【００７８】
また、上述の実施形態では、ＧＡとタブー探索を組み合わせて最適解を探索しているが、同様にして、シミュレーテッド・アニーリング等の他の確率的最適化手法とタブー探索を組み合わせてもよい。この場合も、局所最適解からの脱出が促進され、最適解の探索が効率化される。
【００７９】
ところで、図２の探索装置は、図１７に示すような情報処理装置（コンピュータ）を用いて構成することができる。図１７の情報処理装置は、ＣＰＵ（中央処理装置）３１、メモリ３２、入力装置３３、出力装置３４、外部記憶装置３５、媒体駆動装置３６、およびネットワーク接続装置３７を備え、それらはバス３８により互いに接続されている。
【００８０】
メモリ３２は、例えば、ＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含み、処理に用いられるプログラムとデータを格納する。ＣＰＵ３１は、メモリ３２を利用してプログラムを実行することにより、必要な処理を行う。
【００８１】
例えば、図２の適応度計算部１１、選択部１２、交叉部１３、突然変異部１４、およびタブーフィルタ１５は、メモリ３２に格納されたプログラムにより実現されるソフトウェアコンポーネントに対応する。また、図２のタブーリスト１６は、メモリ３２上に保持されたデータ構造に対応する。
【００８２】
入力装置３３は、例えば、キーボード、ポインティングデバイス、タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力装置３４は、例えば、ディスプレイ、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【００８３】
外部記憶装置３５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク（magneto-optical disk）装置等である。情報処理装置は、この外部記憶装置３５に、上述のプログラムとデータを保存しておき、必要に応じて、それらをメモリ３２にロードして使用することができる。
【００８４】
媒体駆動装置３６は、可搬記録媒体３９を駆動し、その記録内容にアクセスする。可搬記録媒体３９としては、メモリカード、フロッピーディスク、ＣＤ−ＲＯＭ（compact disk read only memory ）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。ユーザは、この可搬記録媒体３９に上述のプログラムとデータを格納しておき、必要に応じて、それらをメモリ３２にロードして使用することができる。
【００８５】
ネットワーク接続装置３７は、任意のネットワーク（回線）を介して外部の装置と通信し、通信に伴うデータ変換を行う。情報処理装置は、必要に応じて、ネットワーク接続装置３７を介して上述のプログラムとデータを外部の装置から受け取り、それらをメモリ３２にロードして使用することができる。
【００８６】
図１８は、図１７の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。可搬記録媒体３９や外部のデータベース４０に保存されたプログラムとデータは、メモリ３２にロードされる。そして、ＣＰＵ３１は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【００８７】
【発明の効果】
本発明によれば、遺伝的アルゴリズムのような確率的最適化手法を用いて最適化問題の解を求める際に、タブー探索の仕組みを利用することで、結果的に無駄な再計算を行う可能性が低くなり、探索が効率化される。また、局所最適解からの脱出が容易になり、最適解の近傍を探索することができるようになる。
【図面の簡単な説明】
【図１】本発明の探索装置の原理図である。
【図２】探索装置の構成図である。
【図３】探索処理のフローチャートである。
【図４】適応度計算処理のフローチャートである。
【図５】第１のフィルタリング処理のフローチャートである。
【図６】第２のフィルタリング処理のフローチャートである。
【図７】コーディングの例を示す図である。
【図８】適応度の分布を示す図である。
【図９】第１世代を示す図である。
【図１０】第２世代を示す図である。
【図１１】第３世代を示す図である。
【図１２】タブーリストを示す図である。
【図１３】適応度計算部の例を示す図である。
【図１４】便データの指定例を示す図である。
【図１５】染色体データを示す図である。
【図１６】デコードのための対応関係を示す図である。
【図１７】情報処理装置の構成図である。
【図１８】記録媒体を示す図である。
【符号の説明】
１  個体格納手段
２  操作手段
３  タブー格納手段
４  タブー処理手段
５  候補格納手段
６  探索手段
１１  適応度計算部
１２  選択部
１３  交叉部
１４  突然変異部
１５  タブーフィルタ
１６  タブーリスト
２１  フライトオブジェクト
２２  フライトスケジュール管理部
３１  ＣＰＵ
３２  メモリ
３４  出力装置
３５  外部記憶装置
３６  媒体駆動装置
３７  ネットワーク接続装置
３８  バス
３９  可搬記録媒体
４０  データベース
【図１】
0003866453.tif 000002
【図２】
0003866453.tif 000003
【図３】
0003866453.tif 000004
【図４】
0003866453.tif 000005
【図５】
0003866453.tif 000006
【図６】
0003866453.tif 000007
【図７】
0003866453.tif 000008
【図８】
0003866453.tif 000009
【図９】
0003866453.tif 000010
【図１０】
0003866453.tif 000011
【図１１】
0003866453.tif 000012
【図１２】
0003866453.tif 000013
【図１３】
0003866453.tif 000014
【図１４】
0003866453.tif 000015
【図１５】
0003866453.tif 000016
【図１６】
0003866453.tif 000017
【図１７】
0003866453.tif 000018
【図１８】
0003866453.tif 000019