(57)【要約】【課題】複数の目的を持つ最適化問題を処理する最適化処理装置に関し、特に初期解を高速に求める手法とパレート最適解を求める遺伝的アルゴリズムとの２段階の処理構成によって計算コストを低減させた最適化処理装置を提供する。【解決手段】複数の目的を持つ最適化問題として定式化できる問題を処理する最適化処理装置は、初期解を高速に求める手法により、初期パレート解を探索する初期パレート解探索部と、遺伝的アルゴリズム手法により、探索された前記初期パレート解を用いてパレート最適解集合を探索するパレート解集合探索部と、前記問題が入力されると前記初期パレート解探索部及び前記パレート解集合探索部の各々を制御して、探索された前記パレート最適解集合を出力する制御部と、で構成される。【選択図】　　　図４
2004030413.tif 000002
【特許請求の範囲】
【請求項１】
複数の目的を持つ最適化問題として定式化できる問題を処理する最適化処理装置であって、
初期解を高速に求める手法により、初期パレート解を探索する初期パレート解探索部と、
遺伝的アルゴリズム手法により、探索された前記初期パレート解を用いてパレート最適解集合を探索するパレート解集合探索部と、
前記問題が入力されると前記初期パレート解探索部及び前記パレート解集合探索部の各々を制御して、探索された前記パレート最適解集合を出力する制御部と、により構成することを特徴とする最適化処理装置。
【請求項２】
前記初期パレート解探索部は、前記初期解を高速に求める手法として焼きなまし手法を用いる、請求項１記載の装置。
【請求項３】
前記初期パレート解探索部は、前記焼きなまし手法を複数回実行して初期解を複数個生成し、それらの集合を前記初期パレート解とする、請求項２記載の装置。
【請求項４】
前記初期パレート解探索部は、前記初期解を高速に求める手法として集団サイズを制限した遺伝的アルゴリズム手法を用いる、請求項１記載の装置。
【請求項５】
複数の目的を持つ最適化問題として定式化できる問題を処理する最適化処理機能であって、
初期解を高速に求める手法により、初期パレート解を探索する初期パレート解探機能と、
遺伝的アルゴリズム手法により、探索された前記初期パレート解を用いてパレート最適解集合を探索するパレート解集合探索機能と、
前記問題が入力されると前記初期パレート解探索機能び前記パレート解集合探索機能の各々を制御して、探索された前記パレート最適解集合を出力する制御機能と、によりコンピュータを作動させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数の目的を持つ最適化問題を処理する最適化処理装置に関し、特にスケジューリングや工程管理等の多目的問題を遺伝的アルゴリズム（ＧＡ；　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ）を用いて効率的に処理する最適化処理装置に関するものである。
【０００２】
【従来の技術】
複数の目的を持つ最適化問題は多目的問題と呼ばれ、その解法は通常パレート最適解集合を探索する。パレート解集合は複数個のパレート解の集まりであり、１つの解を求める解法と比べて一般に計算コスト（計算時間）が大きくなる。
【０００３】
問題固有知識（ヒューリスティックス）等の効率的な探索を実現するのに助けとなる適切な手段の無いような難しい問題では現時点の解から改善された解を探すということを繰り返す手法がしばしば用いられる。そのような手法として、例えば遺伝的アルゴリズム（ＧＡ）が用いられる。遺伝的アルゴリズムは、探索空間が大きく制約条件が多くて線形計画法などの従来手法では困難な問題、探索空間の勾配情報や連続性などを仮定できない問題、さらには組み合わせが多すぎてその処理が困難な問題、等に適用される。
【０００４】
図１には、従来手法による２目的最小化問題の一例を模式的に示している。
図１において、２目的最小化問題の各目的関数値をｘ、ｙ軸にとり、その組み合わせが１つの解を示す。ここでは、ある初期解集合（折れ線で結んで表示）から出発してその解集合（同様に、折れ線で結んで表示）を少しずつ改善していく様子を示している。この場合、図中の矢印（時間ｔ）で示すように右上方のパレート解集合が徐々に改善されていき、最終的には左下方のパレート解集合に至るように探索していく。
【０００５】
図２は、図１の２目的最小化問題に遺伝的アルゴリズム（ＧＡ）を用いた場合の解集合の探索例を示したものである。
図２の（ａ）には複数個の解を白丸で示しており、その内の２つ（黒丸で示す）をランダムに選択する。図２の（ｂ）には、このように選択した解（親個体）から交叉や変異などの遺伝子操作により生成された解（子個体）について、所定の制御可能性を評価して残った子集団を示している（複数の黒丸で示す）。図２の（ｃ）では残った子個体と元の解（（ａ）に示された解）とを合せた集合に対して非パレート解淘汰を施すことにより新たな解集合に更新する（複数の白丸で示す）。非パレート解淘汰とは、他の解に優越されてしまう解を淘汰（消去）することを示す。
【０００６】
【発明が解決しようとする課題】
上記では２目的問題の簡単な例を示したが、多数のパレート解を扱わなければならない多目的問題では、扱うパレート解の個数が多くなるほどその計算コストは増大する。前述した遺伝的アルゴリズム（ＧＡ）は、パレート解集合をＧＡ集団の中に含ませることでパレート解集合を１回の試行で得ることができる特長を有している。
【０００７】
しかしながら、遺伝的アルゴリズムのように効率的に解集合を扱うことのできる手法であっても多目的問題に対しては計算コストが急激に増大し、その探索速度の向上が問題となってきている。
【０００８】
そこで本発明の目的は、上記問題点に鑑み、多目的最適化問題の最適解集合を求める最適化処理装置において、最終的なパレート最適解集合に近くなる段階までは計算コストが少ない手法を用い、その後の最終段階におけるパレート最適解集合を求める探索には本来のパレート解探索手段を用いる２段階の処理構成とすることで、多目的最適化問題における探索処理の高速化を実現した最適化処理装置を提供することにある。
【０００９】
【課題を解決するための手段】
本発明によれば、複数の目的を持つ最適化問題として定式化できる問題を処理する最適化処理装置であって、初期解を高速に求める手法により、初期パレート解を探索する初期パレート解探索部と、遺伝的アルゴリズム手法により、探索された前記初期パレート解を用いてパレート最適解集合を探索するパレート解集合探索部と、前記問題が入力されると前記初期パレート解探索部及び前記パレート解集合探索部の各々を制御して、探索された前記パレート最適解集合を出力する制御部と、により構成する最適化処理装置が提供される。
【００１０】
前記初期パレート解探索部は、前記初期解を高速に求める手法として焼きなまし手法を用いる。また、前記焼きなまし手法を複数回実行して初期解を複数個生成し、それらの集合を前記初期パレート解としてもよい。さらに、前記初期解を高速に求める手法として集団サイズを制限した遺伝的アルゴリズム手法を用いてもよい。
【００１１】
また、本発明によれば、複数の目的を持つ最適化問題として定式化できる問題を処理する最適化処理機能であって、初期解を高速に求める手法により、初期パレート解を探索する初期パレート解探機能と、遺伝的アルゴリズム手法により、探索された前記初期パレート解を用いてパレート最適解集合を探索するパレート解集合探索機能と、前記問題が入力されると前記初期パレート解探索機能び前記パレート解集合探索機能の各々を制御して、探索された前記パレート最適解集合を出力する制御機能と、によってコンピュータを作動させるプログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【００１２】
【発明の実施の形態】
図３は、本発明の最適化処理装置において、多目的問題の最適解集合を求めるための原理手法を模式的にあらわしたものである。
本発明では、多目的最適化問題に対し、前段階（時間ｔ１）では最終的なパレート最適解集合に近くなるまで計算コストが少ない手法（１点探索の手法等）を用い、それに続く後段階（時間ｔ２）では本来のパレート解探索手法を用いて最適解集合を探索する。
【００１３】
図１及び２で説明したように、パレート解集合を改善することを繰り返して探索を進める遺伝的アルゴリズム等の既存の解法においては、探索が進行するにつれて、ある時点でのパレート解集合内の解はそれより後の時点のパレート解集合内の解によって優越されていく場合が多い。
【００１４】
そのため、本発明では、最終的に求まるパレート最適解集合から程遠い解集合しか得られていない探索序盤の前段階（時間ｔ１）においては解の生成数を減らして計算コストを低減させる。そのような解の生成数を減らす最も極端な場合は、パレート解集合の大きさは１である。
【００１５】
この場合、探索点が１個であることから、対象となる問題の特性に合った様々な従来手法が利用できる可能性が高くなる。後で説明するように、本発明の実施例では前段階（時間ｔ１）で１点探索手法の一つである焼きなまし法（ＳＡ；Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ）を使用し、そして続く後段階（時間ｔ２）では既存の遺伝的アルゴリズム（ＧＡ）を使用している。
【００１６】
なお、問題の内容にも依存するが、例えば前段階の手法で探す解が近似解（制約を完全に充足していない解や元々の問題を近似化した近似問題の解、等）でよいような場合には、解の生成数をさらに減らして前段階にかかる計算コストをより一層低減させることができる。
【００１７】
図４は、本発明による最適化処理装置の基本構成を示したものである。また、図５には本発明による最適化処理装置の基本処理フローを示している。
本発明による最適化処理装置１０において、初期パレート解探索部１２は初期パレート解を探索する（Ｓ２２）。また、パレート解集合探索部１３は、初期パレート解探索部１２によって求められた初期パレート解（Ｓ２３）を用いてパレート最適解集合を探索する（Ｓ２４）。そして、制御部１１は、問題が入力されると（Ｓ２１）、前記初期パレート解探索部１２及びパレート解集合探索部１３の各部を制御してその結果としてパレート最適解集合を出力する（Ｓ２５）。
【００１８】
図６は、初期パレート解探索部１２の制御フローの一例を示したものである。本例の初期パレート解探索部１２は、焼きなまし法（ＳＡ）の手法に基づいて構成されている。焼きなまし法は、探索空間に勾配情報や連続性などを仮定できない問題、探索空間が大きく制約条件が多くて線形計画法などの従来手法では困難な問題、等に適用される手法である。なお、焼きなまし法によって得られる解と同様な解を与える別な手法を用いることも可能である。
【００１９】
焼きなまし法を、ｍ整数変数のｎ目的最小化問題を例として簡単に説明すると、変数ＸをＸ＝（ｘ１，　ｘ２，　…，　ｘｍ）、目的関数ＦをＦ＝（Ｆ１，　Ｆ２，　…，　Ｆｎ）、Ｆ１＝Ｆ１（Ｘ）、Ｆ２＝Ｆ２（Ｘ）、…、Ｆｎ＝Ｆｎ（Ｘ）と書く。ＳＡを用いる場合、ＳＡの評価関数としてはスカラー関数でなければならない。このために多目的問題の複数個の目的関数を何らかの方法でスカラー化する必要がある。
【００２０】
例えば、ある個体ｒから別な個体ｓに遷移する確率ｐが
ｐ＝ｅｘｐ（−Ｑ／Ｔ）
で与えられるとする（ｍｅｔｒｏｐｏｌｉｓ法）。ここで、Ｔは温度、
Ｑ＝ｗ１＊ΔＦ１＋ｗ２＊ΔＦ２＋…＋ｗｎ＊ΔＦｎ
ΔＦｊ＝Ｆｊ（ｓ）−ΔＦｊ（ｒ）、ｉｆＦｊ（ｓ）＞ΔＦｊ（ｒ）
ｏｔｈｅｒｗｉｓｅ　０、ｊ＝１、２、…、ｎ
ｗ１、ｗ２、…、ｗｎは正定数
である。
【００２１】
なお、このスカラー化による近似化のために、本来の多目的問題のパレート最適解に到達できない恐れがある。しかし、本発明ではこのＳＡが本来の多目的問題を解くＧＡの初期パレート解を得る手段として用いられ、最終的なパレート解集合はＧＡにより探索されるので近似化の影響は消され問題とならない。
【００２２】
図６では、前記状態変数Ｘによる摂動によって最小化すべきＱ値を評価する。この評価では例えば摂動後のＱ’値が摂動前のＱ値よりも減少方向にあるか否かが判断され、その結果に従って目的関数Ｆが再計算される（Ｓ３１〜３４及び３７〜４０）。次に、前記遷移確率ｐを用いて摂動後の状態へ遷移すべきか否かが判断され、遷移条件を満足する場合には摂動後の状態に遷移する（Ｓ３５及び３７）。この処理は、所定の繰り返し回数、計算時間、又は解の改善、が一定回数の間見られなかった場合に終了する（Ｓ３６）。
【００２３】
図７は、パレート解集合探索部１３の制御フローの一例を示したものである。本例のパレート解集合探索部１３は、遺伝的アルゴリズム（ＧＡ）に基づいて構成される。この問題を解くＧＡは、例えば、以下のように構成される。個体の染色体表現は、各変数をそれぞれ座位とし、座位上の対立遺伝子を変数値とするような表現をとる。なお、このような表現自体は本願発明にとって重要ではない。
【００２４】
ＧＡの典型的動作は、図７に示すように「初期化（Ｓ５１）」→「評価（Ｓ５２）」→「終了判定（Ｓ５３）」→「選択（Ｓ５４）」→「交叉・変異（Ｓ５５）」→「評価に戻る（Ｓ５２）」となる。この繰り返しの部分は世代と呼ばれる。世代を繰り返すことで、集団内の解が次第に改善され（Ｓ５７及び５８）、最終的な解集合（Ｓ５６）が得られる。
【００２５】
ＧＡの構成の仕方によっては上記と異なる場合が生じるが、その構成自体は本発明にとって重要ではない。従って、以下の各ステップの説明ではＧＡ手法の詳細な説明を省略している。
【００２６】
ステップＳ５１の初期化では、図６の焼きなまし法（ＳＡ）によって初期解を用意する。この初期集団サイズは１となる。もし、解が１つで不十分な場合には複数回ＳＡを実施してそれらの解を初期集団とすればよい。
【００２７】
ステップＳ５２の評価では、各個体それぞれについて、個体の染色体上の変数値Ｘ＝（ｘ１，　ｘ２，　…，　ｘｍ）を用いて目的関数値Ｆ＝（Ｆ１，　Ｆ２，　…，　Ｆｎ）を求める。次のステップＳ５３の終了判定では、所定の繰り返し回数、計算時間に達したとき、又は解の改善が一定世代の間見られなかったとき、に計算を終了する。
【００２８】
ステップＳ５４の選択では、種々の選択方法が考案検討されているが（例えば、システム制御情報学会編「遺伝アルゴリズムと最適化」朝倉書店１９９８）、一例として集団内の各個体の目的関数値を相互に比較して、ある個体　ｉ　が集団内のほかのＮｉ個の個体に優越されるときに、Ｎｉの大きな個体を消去してＮｉの少ない個体を増やす（複写する）。ただし、Ｎｉ＝０の個体（すなわちパレート解）は常に残す（消去しない）。これにより集団サイズは一般に変動する。
【００２９】
ステップＳ５５の交叉では、集団内から個体（親個体）をいくつか選び、それらの染色体上の対立遺伝子を交換することにより（子）個体を作る操作を行なう。簡単な例では、２個の親個体をランダムに選びそれらの染色体の座位上の対立遺伝子のビット列をランダムに入れ換えることで子個体が得られる。
【００３０】
同ステップＳ５５の変異では、集団内の各個体の染色体上の対立遺伝子を所定の小さい確率でほかの値に変化させる操作を行なう。簡単な例では、個体の染色体の座位上の対立遺伝子のビット列をランダムに入れ換える。
【００３１】
次に、初期パレート解探を求めるＳＡとパレート解集合を求めるＧＡとの計算コスト比較のために、各々の計算コストを簡単に見積もる。対象とする具体的問題の内容にも依存するが、計算時間の多くは個体の評価に費やされる。ここでは１個の個体の評価コスト（計算コスト）をＤと書く。
【００３２】
初期パレート解を求めるＳＡでは、１世代に１個体の遷移が起きるため、その計算コストはＤである。一方、パレート解集合を求めるＧＡでは、解集合が数十個から数百個に及ぶ例があり、そのような場合にＧＡ単独の探索では集合の大きさにほぼ比例した計算時間を要する。この場合の集団サイズをＰとすると計算コストはＰ＊Ｄである。
【００３３】
ここでは、Ｐ＝１００　程度でＳＡ探索がＧＡ探索に比べて同じ品質の解レベルに到達するのに、世代数で数えて１０倍遅いとする。この場合、全体としてのＳＡの計算コストはＧＡの計算コストよりも（Ｄ＊１０）／（Ｐ＊Ｄ）＝１／１０と１桁小さく、従ってＳＡの方がＧＡよりも計算速度は１０倍ほど速い。これから、従来のＧＡのみで探索する場合と比べて、本発明のようにＳＡで初期パレート解を求める方が１０倍ほど高速にパレート最適解集合を求めることが可能となる。
【００３４】
図８及び９は、本発明の一実施例を示したものであり、ここでは航空会社の航空機乗務員の勤務計画問題を扱っている。図８にはその適用要件を、そして図９には本発明の最適化処理装置によるデータｄ１の計算結果を示している。また、図１０には従来手法によるデータｄ１の計算結果を図９との比較のために示してある。なお、この勤務計画問題は、乗務時間の平準化（分散最小化）、勤務時間の平準化（分散最小化）、希望休暇充足化（未充足平均最小化）の３目的問題である。
【００３５】
図８において、データｄ１は繁忙期大規模の問題、データｄ２は繁忙期中規模の問題、そしてデータｄ３は閑散期大規模の問題のそれぞれの適用条件を示している。図９には、データｄ１を、初期解探索段階では焼きなまし法（ＳＡ）により、後の解集合探索段階では遺伝的アルゴリズム（ＧＡ）により解いた典型的な１試行について、評価関数である乗務時間分散（Ｖｆ）及び勤務時間分散（Ｖｗ）をＸ軸及びＹ軸にして、制約充足後のＳＡ解の遷移軌跡とその後のＧＡ探索解とを併せてプロットしている。
【００３６】
一方、図１０には、同じデータｄ１を、図９と同じ計算時間で従来手法による遺伝的アルゴリズム（ＧＡ）だけを使用したＧＡ探索解をプロットしている。図９の本発明手法による計算時間は、初期解探索段階のＳＡの計算に約２４分（約１２分でほぼ収束）、解集合探索段階のＧＡの計算に約３０分かかり、全体では約５４分を要している。結果として、図９の初期解探索手段を用いる場合と図１０のそれを用いない場合とでは、同じ品質の解集合を得る計算時間で約２２倍の差が見られた。
【００３７】
ところで、本実施例でも述べたようにＳＡの実行を複数回実施し、それによりＳＡの確率的探索に起因するバラツキを一層低減することができる。また複数回実施する際には、前述したＱ値の計算に用いる係数ｗｊの値を各々の実行毎に少しずつ変えることで、係数値の設定の恣意性による最終的な解集合のバラツキを低減させるようにしてもよい。
【００３８】
これにより、探索空間の多峰性に対してもロバスト　（ｒｏｂｕｓｔ）　性を持たせることができる。複数回実行することにより計算コストはかかるが、問題の難易度に応じて実行回数を適宜設定することで、全体としての計算コストを下げることが可能である。
【００３９】
前述した航空機の乗務員計画の実施例においては、ＳＡの１試行約９分を１０回試行し、その後に１０個のＳＡ解を初期解集合とするＧＡによって最適解集合を探索（約３０分）させた結果、図示はしていないが同じ計算時間２時間での比較においてＳＡを複数回実行させる手法がより品質の良い解集合を探索した。
【００４０】
また、本実施例の別の態様として、初期解探索段階及び解集合探索段階のいずれも同じ遺伝的アルゴリズム（ＧＡ）を使用し、前者の初期解探索段階ではＧＡの集団サイズを制限したＧＡを用いるように構成してもよい。例えば、後の解集合探索段階のＧＡでは数１００個の集団サイズを用いるのに対して、初期解探索段階のＧＡでは集団サイズ（上限）を数１０個に限定する。この場合の集団サイズは必ずしも固定する必要がなく、世代数とともに増減させるようにしてもよい。
【００４１】
なお、多目的最適化問題にＧＡを適用する場合に、解集合が特定領域に集中しないように集団のバラツキを制御する機構が従来から検討されている。この機構では集団サイズを制限する場合もあるが、探索空間内での解集合のバラツキを制御するのが目的である。
【００４２】
例えば、目的値空間を等間隔の区画に区切り、各区画に入る解の個数上限を設定するものである。しかしながら、本態様例は最適解集合から遠く離れた探索序盤（若い世代）での計算コストの削減を目的として世代数に基づく集団サイズを制限するものである。従って、両者の目的及び作用効果は明確に相違している。
【００４３】
【発明の効果】
以上説明したように、本発明によれば、遺伝的アルゴリズム（ＧＡ）とは別な初期解探索手法によりパレート解の初期値を高速に求めることで、全体としての計算コストを短縮することが可能となる。初期解探索手法により求める解は個数が少なくてもよく、個数が少ないことによって計算コストが減らすことができる。また、初期解探索手法による解は本来の多目的問題に対する近似解であってもよく、必要十分な近似解によって効率的な手法を採用することが可能となる。
【００４４】
初期解探索手法として用いる焼きなまし法（ＳＡ）は、確率的な１点探索法であって変数組に対する評価関数が与えられれば探索を行わせることが可能であり、効率的な計算が可能である。また、焼きなまし法は、評価関数の勾配等の補助情報が不要であり、非線形な問題や組み合わせ問題等にも応用できる利点がある。
【００４５】
この場合、焼きなまし法は確率的な探索法のために実行結果にバラツキが生じ得る。そのため、複数回の実行によってこの影響を低減させ、さらにはＳＡ探索におけるパラメタ設定の恣意性を低減させることができる。
【００４６】
また、初期解探索手法の別の手法として遺伝的アルゴリズム（ＧＡ）の集団サイズを小さくしたＧＡを用いることができ、それによって１世代あたりの計算コストを低減することが可能である。
【図面の簡単な説明】
【図１】従来手法による２目的最小化問題の一例を模式的に示した図である。
【図２】図１に遺伝的アルゴリズムを用いた場合の解集合の探索例を示した図である。
【図３】本発明の手法により多目的問題の最適解集合を求める原理を模式的にあらわした図である。
【図４】本発明による最適化処理装置の基本構成を示した図である。
【図５】本発明による最適化処理装置の基本処理フローを示した図である。
【図６】初期パレート解探索部の制御フロー例を示した図である。
【図７】パレート解集合探索部の制御フロー例を示した図である。
【図８】本発明の実施例における適用要件の例を示した図である。
【図９】本発明の最適化処理装置によるデータｄ１の計算結果を示した図である。
【図１０】従来手法によるデータｄ１の計算結果を示した図である。
【符号の説明】
１０…最適化処理装置
１１…制御部
１２…初期パレート解探索部
１３…パレート解集合探索部
【図１】
2004030413.tif 000003
【図２】
2004030413.tif 000004
【図３】
2004030413.tif 000005
【図４】
2004030413.tif 000006
【図５】
2004030413.tif 000007
【図６】
2004030413.tif 000008
【図７】
2004030413.tif 000009
【図８】
2004030413.tif 000010
【図９】
2004030413.tif 000011
【図１０】
2004030413.tif 000012