(57)【要約】【課題】効率的に局所解から脱出する組合せ最適化問題の解析装置を提供する。【解決手段】初期の組合せ状態から始め隣接状態と定義された組合せ状態から評価関数により遷移すべき状態を決定し順次遷移を繰返し探索し評価関数を最小又は最大化する最適組合せ状態を求めるため探索した中で評価関数値が最良の組合せ状態の最良解と現在状態の評価関数値を比較し現在状態がよい時にこれを最良解とする手段、現在状態がその評価関数値が全ての隣接状態の評価関数値よりよい局所解の時に局所解よりも何れか１個の部分評価関数値がよいことである部分評価関数改善条件を設定する手段、条件設定中は現在状態の隣接状態の中で前記条件を満たす隣接状態だけを探索対象とする手段、局所解より評価関数がよい状態に遷移できると前記条件を解除する手段、条件設定中に現在状態が局所解になると前記条件を設定した局所解に現在状態を戻し探索を継続する手段を有す。【選択図】図２
2006072820.tif 000002
【特許請求の範囲】
【請求項１】
初期の組合せ状態から出発し、隣の状態と定義された組合せ状態の中から評価関数を用いて遷移すべき状態を決定し、順次この遷移先への遷移を繰り返す探索を行うことにより、評価関数を最小化または最大化する最適な組合せ状態を求めるコンピュータを用いた組合せ最適化問題の解析装置であって、
前記評価関数が複数の部分評価関数値による関数として表現され、すべての部分評価値の領域においてすべての部分評価関数値が増加すると評価関数値が増加または変化しないことが保証されており、
探索した中で評価関数値が最もよい組合せ状態である最良解と現在の組合せ状態である現在状態の評価関数値を比較し、現在状態の評価関数値の方がよい場合に現在状態を最良解とする最良解更新手段と、
現在状態がその評価関数値がすべての隣接状態の評価関数値よりもよい局所解である場合に、局所解よりも何れか１個の部分評価関数値がよいことである部分評価関数改善条件を設定する部分評価関数改善条件設定手段と、
部分評価関数改善条件が設定されている場合は、現在状態の隣接状態の中で部分評価関数改善条件を満足する隣接状態だけを探索の対象とする探索範囲限定手段と、
局所解よりも評価関数がよい状態に遷移できた際に部分評価関数改善条件を解除する部分評価関数改善条件解除手段と、
部分評価関数改善条件が設定されている場合に現在状態が局所解になった場合に、部分評価関数改善条件を設定した局所解に現在状態を戻して探索を継続する局所解再探索手段と、
を有することを特徴とする組合せ最適化問題の解析装置。
【請求項２】
部分評価関数改善条件が設定されている場合に現在状態が局所解になった時は、局所解の数が１より大きい所定個以下であれば、新たな局所解に対する部分評価関数改善条件を設定して探索を継続し、部分評価関数改善条件を局所解ごとに管理することを特徴とする請求項１に記載の組合せ最適化問題の解折装置。
【請求項３】
評価関数を部分評価関数値の和とすることを特徴とする請求項２に記載の組合せ最適化問題の解析装置。
【請求項４】
部分評価関数改善条件として複数の部分評価関数値の和が局所解よりもよいという条件も使用することを特徴とする請求項３に記載の組合せ最適化問題の解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば１つ１つの組合せの状態の集まりである電力供給状態における様々な状態の組合せの中から最も良い組合せを評価関数を用いて解析して求める組合せ最適化問題の解析装置に関する。
【背景技術】
【０００２】
従来、この種の組合せ最適化問題の解法として、シミュレーテッドアニーリング法(Simulated Annealing:SA)という、物理系における焼きなまし(annealing)過程を模擬した方法に基づくものがある。焼きなましとは、固体に熱を加えて溶融し、それを徐々に冷やすことにより結晶を生成するプロセスである。固体にエネルギーを加えて温度を上げ、溶融状態にすれば粒子はランダムな配置となる。その状態からゆっくりと温度を下げることにより、最も内部エネルギーの小さい基底状態となり、このときの粒子は規則正しい配置、すなわち結晶となる。ＳＡ法は、このような粒子の挙動を組合せ最適化問題の決定変数に対応させ、焼きなまし過程を計算機上で模擬するものである。
【０００３】
最小化の場合のＳＡ法では、まず組合せ状態を表すｘと温度を表すＴの初期値を設定し、ｘの隣の状態である近接解ｙを生成してｙとｘの目的関数(評価関数)の変化量ΔＥを計算し、ΔＥが負(ｙの方がｘより良い解)ならｘをｙに更新する(ｘをｙに遷移させる)。またΔＥが非負なら所定区間の一様乱数γを発生させ、Ｅｘｐ(−ΔＥ／Ｔ)＞γが成立するか否かの判定をして(成立する確率はΔＥが小さく(ｘに比べたｙの解の悪化度合いが小さく)温度Ｔが大きい程大きい)、成立する場合には解の悪化を許容しｙを採用し、成立しない場合にはｘの更新は行わない。そして平衡状態(多数回この判定を行ってもｘに変化がない状態)か否かの判定をして、平衡状態でなければ次の隣の状態である近接解ｙを生成して同様な処理を繰り返し、平衡状態なら温度Ｔを下げるためにＴをρ(０＜ρ＜１)倍する。そして基底状態(充分に温度Ｔが低い状態)になったか否かの判定を行い、基底状態ならその時点のｘを最適解として処理終了とし、基底状態でなければ次の隣の状態である近接解ｙを生成して同様な処理を繰り返えす(非特許文献１参照)。このような方法では、より悪い状態への遷移が確率的に許されており、ｘが極小解に到達しても、極小解に捕まらずに遷移を継続することが可能となり、より良い解を見つけ出すことができる。なお、評価関数の最小化を目的とする場合の極小解、または最大化の場合の最大解を、局所解と呼ぶ。
【０００４】
【非特許文献１】櫻井良文他著、「新しい電力システム計画手法」電気学会技術報告、第６４７号、pp５１〜５２、１９９７年８月
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このような従来の組合せ最適化問題の解析装置において状態の組合せ最適化問題を解く上での最大の技術課題は、いかに局所解から脱出し探索を継続するかにあり、従来から様々な方法が提案されている。これらを大きく分類すると下記となる。
(１)ある確率でより悪い状態への遷移を許す(上述の方法)。
(２)許される遷移の中で最良の状態への遷移を繰り返す(局所解においては評価関数値が悪化する遷移が発生する)こととし、遷移に伴い組合せの内容に変化のあった部分に関しては、ある期間、逆向きの変化を禁止することにより、通過した局所解へ戻ることを抑制する。
(３)許される遷移の中で最良の状態への遷移を繰り返す(局所解においては評価関数値が悪化する遷移が発生する)こととし、通過した局所解の評価関数値には以降下駄を履かせて評価を悪化させて評価することとし、通過した局所解へ戻ることを抑制する。
【０００６】
この発明は、組合せ最適化問題を解く上での最大の技術課題である「いかに局所解から脱出し探索を継続するか」に関して、より効率的な方法で探索を継続するようにした組合せ最適化問題の解析装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明は、初期の組合せ状態から出発し、隣の状態と定義された組合せ状態の中から評価関数を用いて遷移すべき状態を決定し、順次この遷移先への遷移を繰り返す探索を行うことにより、評価関数を最小化または最大化する最適な組合せ状態を求めるコンピュータを用いた組合せ最適化問題の解析装置であって、前記評価関数が複数の部分評価関数値による関数として表現され、すべての部分評価値の領域においてすべての部分評価関数値が増加すると評価関数値が増加または変化しないことが保証されており、探索した中で評価関数値が最もよい組合せ状態である最良解と現在の組合せ状態である現在状態の評価関数値を比較し、現在状態の評価関数値の方がよい場合に現在状態を最良解とする最良解更新手段と、現在状態がその評価関数値がすべての隣接状態の評価関数値よりもよい局所解である場合に、局所解よりも何れか１個の部分評価関数値がよいことである部分評価関数改善条件を設定する部分評価関数改善条件設定手段と、部分評価関数改善条件が設定されている場合は、現在状態の隣接状態の中で部分評価関数改善条件を満足する隣接状態だけを探索の対象とする探索範囲限定手段と、局所解よりも評価関数がよい状態に遷移できた際に部分評価関数改善条件を解除する部分評価関数改善条件解除手段と、部分評価関数改善条件が設定されている場合に現在状態が局所解になった場合に、部分評価関数改善条件を設定した局所解に現在状態を戻して探索を継続する局所解再探索手段と、を有することを特徴とする組合せ最適化問題の解析装置にある。
【発明の効果】
【０００８】
この発明によれば、局所解脱出にあたって改善するべき部分評価関数を予め定めて、脱出用の探索を行うため、確率的な局所解脱出等、無目的な脱出方法よりも効率的な局所解脱出が可能となる。
【発明を実施するための最良の形態】
【０００９】
この発明によれば、局所解に陥った場合には、評価関数の構成要素である部分評価関数が、局所解よりも改善する状態だけに絞って探索を行うことにより局所解から脱出する、すなわち、局所解よりも評価関数値の小さな状態まで探索を進める。局所解脱出までの基本的な流れは、(１)まず、局所解よりも改善するべき部分評価関数Ａを定め、(２)局所解脱出のための探索開始時点では、部分評価関数Ａの改善に伴い、部分評価関数Ａ以外の部分評価関数Ｂは一時悪化するが、(３)局所解脱出のための探索を継続することにより、悪化した部分評価関数Ｂが改善され、(４)現在状態の評価関数値が局所解の評価関数値よりも小さくなった時点で、局所解脱出を完了とする。以下この発明を実施の形態に従って説明する。
【００１０】
実施の形態１．
図１はこの発明の一実施の形態による組合せ最適化問題の解析装置の構成を示す図である。この装置はコンピュータで構成され、本体部１にはＣＰＵ１１、ＣＰＵ１１で使用するプロクラム、データをそれぞれ格納したプログラム部１２ａ、データ部１２ｂを含むメモリ１２が設けられている。そして例えばデータ及び演算処理指示の入力を行う入力装置２等からの設定指示入力に従い、ＣＰＵ１１がメモリ１２のプログラム部１２ａのアルゴリズムを記述したプログラムに従いデータ部１２ｂの被解析データを処理して、例えば、１つ１つの組合せの状態の集まりである電力供給状態における様々な状態の組合せの中から最も良い組合せを求める最適化処理のための組合せ最適化問題の解析を行う。解析演算処理途中のデータや解析結果はデータ部１２ｂに格納されまたこれらは表示装置３でモニタすることができる。なお、プログラム及びデータはメモリ１２の代わりにディスク等(図示省略)に格納されていてもよい。
【００１１】
そして図２〜図３は、この発明による組合せ最適化問題の解析装置の動作を示すフローチャートであり、評価関数を最小化する場合のものである。以下図に従って動作を説明すると、まず入力装置２から現在状態が初期設定されると、これに対する評価関数値および部分評価関数値を算出する(ステップＳ１)。ここで、評価関数は、複数の部分評価関数の総和であることを想定している。次に現在状態を最良解としてデータ部１２ｂに保存する(ステップＳ２)。なお最良解とは、それまでの探索で求まった評価関数が最適な解をいう。
【００１２】
次に、極小解段数を０とする(ステップＳ３)。この例では、極小解から脱出するための探索を実施する過程で、さらに極小解に陥った場合に、最初の極小解を１段、次の極小解を２段とし、予め定めた最大の段数までは極小解のデータ部１２ｂへの保存を行う処理構成としている。極小解段数が０は、まだ極小解に陥っていないことを意味する。
【００１３】
次に、現在状態の全ての隣の状態に順次着目し(ステップＳ４)、隣の状態の評価関数値および部分評価関数値を算出する(ステップＳ５)。
【００１４】
次に、極小解段数毎の部分評価関数改善条件を満たすかどうかを判定し(ステップＳ６)、満たしていればステップＳ７に進み、満たしていなければ着目している隣の状態を、現在状態の遷移対象からは外して、次の隣の状態に着目すべく、ステップＳ９へ進む。なお、極小解段数が０の場合は、すべての隣の状態が部分評価関数改善条件を満足するものとする。
【００１５】
極小解段数毎の部分評価関数改善条件について説明すると、本発明では、極小解から脱出するにあたり、脱出のために定めた部分評価関数値もしくは複数の部分評価関数値の合計値が極小解よりも改善される状態のみに絞りこんで探索を行うが、この絞込み条件を、その極小解の部分評価関数改善条件とする。例えば、部分評価関数Ａ１に対する部分評価関数改善条件では、部分評価関数Ａ１の値が極小解での値よりも小さいことが必要になる。部分評価関数Ａ１と部分評価関数Ａ２の合計に対する部分評価関数改善条件では、部分評価関数Ａ１と部分評価関数Ａ２の和が極小解での値よりも小さいことが必要であり、部分評価関数Ａ１または部分評価関数Ａ２のどちらかが極小解での値よりも大きくなってもよい。なお、複数の部分評価関数値の合計値に対する部分評価関数改善条件は、評価関数が部分評価関数値の和である場合だけ使用する。本例では複数段の極小解にわたって状態の絞込みを行うため、現在の極小解段数以下の全ての極小解についての極小解脱出のための部分評価関数改善条件を満たす必要があり、これを、極小解段数毎の部分評価関数改善条件と記述している。
【００１６】
次に、極小解脱出用隣接状態の候補を選出する(ステップＳ７)。この処理は、現在状態が極小解と判定された場合の極小解脱出用隣接状態の保存に備えて、予めその候補を選出しておく処理である。現在状態よりも隣の状態の方が値の良い部分評価関数についてのみ、部分評価関数値の改善量を合計し、これが所定値よりも大きければ極小解脱出用隣接状態の候補とする。
【００１７】
次に、評価関数値の最も良い隣の状態をデータ部１２ｂに保存する(ステップＳ８)。次にステップＳ９では、全ての隣の状態に着目したかどうかを判定し、着目済みであれば図３のステップＳ１０へ進み、そうでなければステップＳ４へ戻って次の隣の状態に着目する。
【００１８】
次に、ステップＳ１０では、評価関数値の最も良い隣の状態よりも現在状態の方が評価関数値が良いか同じであれば、現在状態を極小解と判定し、ステップＳ１１へ進む。現在状態が極小解でなければ、ステップＳ１９へ進む。ステップＳ１１では、極小解段数が既に最大値に達しているかどうかを判定し、最大に達していなければステップＳ１２へ進み、最大に達していればステップＳ１３へ進む。
【００１９】
ステップＳ１２では、極小解段数をカウントアップし、カウントアップ後の極小解段数での、極小解、極小解の評価関数値、極小解の各部分評価関数値、極小解脱出用隣接状態をデータ部１２ｂに保存する。極小解脱出用隣接状態は、ステップＳ７で選出した極小解脱出用隣接状態の候補から、評価関数値の良い順に例えば上位５つの隣の状態を選出し、カウントアップ後の極小解段数からの脱出用隣接状態としてデータ部１２ｂに保存する。ステップＳ１２の実行後は、ステップＳ１７に進む。
【００２０】
ステップＳ１３では、現在の段数の極小解に現在状態を戻し、着目している極小解脱出用隣接状態を削除する。ステップＳ１４では、次に着目する極小解脱出用隣接状態があるかどうかをチェックする。ステップＳ１４で極小解脱出用隣接状態が無い場合、ステップＳ１５で現在の極小解段数が１か否かを判断し、１であれば、すなわち極小解段数１段の極小解脱出用隣接状態が１つもなくなった場合に探索を終了し、そうでない場合にはステップＳ１６に進んで極小解段数をカウントダウンしステップＳ１３に戻る。ステップＳ１４で極小解脱出用隣接状態が有る場合は、ステップＳ１７に進む。
【００２１】
次にステップＳ１７では、現在の極小解段数から脱出するために、次に着目する極小解脱出用隣接状態を決定する。決定のための優先順位はステップＳ１２において既に決めてあるため、これに従う。
【００２２】
次にステップＳ１８では、現在状態を着目した極小解脱出用隣接状態に遷移させ、この遷移に伴い改善した部分評価関数を、現在の極小解段数に対する改善対象部分評価関数とする。この改善対象部分評価関数は、現在の段数の極小解から脱出、すなわち極小解段数のカウントダウンを行うまで、探索の対象となる状態を選択する条件となる。
【００２３】
次にステップＳ１９では、現在状態を評価関数値が最も良い隣の状態に遷移させる。次にステップＳ２０では、現在状態の評価関数値および部分評価関数値を算出する。次にステップＳ２１では、現在状態の評価関数値が最良解より良ければ現在状態を最良解としてデータ部１２ｂに更新保存する。次にステップＳ２２では、探索を所定回数実施済みであれば探索を終了し、そうでなければステップＳ２３へ進む。
【００２４】
そしてステップＳ２３では、極小解段数解除処理を行い、図２のステップＳ４へ戻る。極小解段数解除処理は、現在状態の評価関数値が、現在の極小解段数の極小解の評価関数値よりも良ければ、現在の段数の極小解を脱出したと判定し、極小解段数をカウントダウンする。一度で複数段の極小解脱出が可能な場合もあるため、極小解段数解除処理は、現在の極小解段数から０段に向かって、可能な限りカウントダウンを行う。
【００２５】
なお、これらの解析演算処理途中のデータや解析結果は表示装置３に表示することでモニタすることができる。
【００２６】
また上記実施の形態において、評価関数および部分評価関数は評価関数値が小さいものを評価がよいとしているが、評価関数値が大きいものを評価がよいとする評価関数および部分評価関数を使用してもよく、さらに評価関数および部分評価関数の符号を反転させれば、最大化の組合せ問題が最小化の組合せ問題に、また最小化の組合せ問題が最大化の組合せ問題に逆転し、いずれの場合においても本願発明は実施可能である。
また評価関数は部分評価関数の和だけでなく、すべての部分評価値の領域において、すべての部分評価関数値が増加すると評価関数値が増加または変化しないことが保証されている部分評価関数値の合成関数であればよい。この条件は、評価関数の最小化でも最大化でも同じである。
【図面の簡単な説明】
【００２７】
【図１】この発明の一実施の形態による組合せ最適化問題の解析装置の構成を示す図である。
【図２】この発明による組合せ最適化問題の解析装置の動作を示すフローチャートである。
【図３】図２に続く動作を示すフローチャートである。
【符号の説明】
【００２８】
１  本体部、２  入力装置、３  表示装置、１１  ＣＰＵ、１２  メモリ、１２ａ  プログラム部、１２ｂ  データ部。
【図１】
2006072820.tif 000003
【図２】
2006072820.tif 000004
【図３】
2006072820.tif 000005