(57)【要約】      （修正有）【課題】組合せ問題の場合、優先順位アルゴリズムは、通常、良好な解を発見する。しかし、多くの場合、より良好な解が「その近傍」にある。本発明は、こういったより良好な解を見つける自然かつ汎用的な手法を提供する。【解決手段】本方法は、複数の要素および値を含む組合せ最適化問題を解く。順序付け関数が組合せ最適問題のインスタンスに適用され、要素の順序付けが生成される。要素の順序付けが反復的に変更され、要素が再順序付けされる。終了条件に達し、最良解が選択されるまで、再順序付けされた要素それぞれに配置関数が適用され、組合せ最適化問題の解が得られる。【選択図】図２
2005056421.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素および複数の値を含む組合せ最適化問題を解く方法であって、
前記組合せ最適化問題のインスタンスに順序付け関数を適用することによって前記要素の順序付けを生成すること、
前記要素の前記順序付けを変更することによって前記要素の再順序付けを生成すること、
配置関数を適用することによって値を前記再順序付けの前記対応する要素にマッピングすること、
すべての要素が配置されて、前記組合せ最適化問題の解を得るまで、前記変更することおよび前記適用することを繰り返すこと
を含む複数の要素および複数の値を含む組合せ最適化問題を解く方法。
【請求項２】
優先順位アルゴリズムは固定である、
請求項１記載の方法。
【請求項３】
優先順位アルゴリズムは動的である、
請求項１記載の方法。
【請求項４】
前記再順序付けは前記順序付けの所定距離内である、
請求項１記載の方法。
【請求項５】
前記距離はKendall-tau距離である、
請求項４記載の方法。
【請求項６】
前記再順序付けは決定ベクトルを使用し、前記決定ベクトルは前記順序の各要素に１つのフィールドを有し、各フィールドは前記再順序付けにおける前記要素の新しい順序を決定する、
請求項１記載の方法。
【請求項７】
前記再順序付けは確率的である、
請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的に、組合せ最適化問題に関し、特に、最適解を見つける探索技法に関する。
【背景技術】
【０００２】
組合せ問題は、複数の要素、たとえば、アイテムまたはタスクを様々な順序で組合せる、または実行することができるアプリケーションに対応するものである。要素の数、および可能な順序付けが大きい場合、これら問題は解くことが極めて難しくなる。
【０００３】
周知の組合せ問題としては、巡回セールスマン問題および配送トラック問題、輸送スケジューリング（エアライン、列車、バス）、ジョブショップスケジューリング、クラス・生徒スケジューリング、ユーティリティ管理（電力、ガス、水、下水）、電力および通信網における負荷平衡化、携帯電話基地局の最良場所探索、ならびに大半の箱詰めまたはレイアウト問題が挙げられる。
【０００４】
多くの組合せ最適化問題では、最適な最良解を求めてかなり多数の可能解を探索する必要がある。あるタイプの探索は欲張り探索（greedy search）である。欲張り探索は、通常、ある問題に対して最適解または大域解を見つけるが、他の問題のいくつかの場合には最適とは言えない解を見つけることがある。
【０００５】
欲張り探索のサブクラスは、従来、優先順位アルゴリズムとして知られている。Angelopoulos等著「On the Power of Priority Algorithms for Facility Location and Set Cover」APPROX, pp.26-39, 2002およびBorodin等著「(Incremental) Priority Algorithms」SODA, pp.752-761, 2002を参照のこと。優先順位アルゴリズムは、組合せ箱詰め問題およびスケジューリング問題を解くために特に有効である。優先順位アルゴリズムはまた、実施が高速かつ容易である。
【０００６】
優先順位アルゴリズムは、固定または動的に分類することができる。固定優先順位アルゴリズムは、すべての優先順位を設計時に割り当て、優先順位は一定のままである。すなわち、固定優先順位アルゴリズムでは、問題インスタンス中のすべての要素の順序付けが必要である。このアルゴリズムは欲張りである。これは、ｘｉに割り当てられた値が、前に割り当てられた要素のみの関数であり、要素の値は決定後、固定であることを意味する。固定優先順位アルゴリズムは、実施が最も簡易である傾向を有する。
【０００７】
動的優先順位アルゴリズムは、実行パラメータに基づいて優先順位を実行時に割り当てる。動的優先順位アルゴリズムでは、残りの要素は、要素が配置された後に、実行時のダイナミクスに従って再順序付けされる。従来技術による優先順位アルゴリズムの一般的な特徴として、最高優先順位の要素が常に各ステップに配置される。本発明が示すように、これはすべてのクラスでは望ましくない場合がある。
【０００８】
図１に示すように、最適化問題１０１の典型的な優先順位アルゴリズム１００は、問題のインスタンスＩ１０２から出発する。順序付け関数ｏ１１０が要素１０３の順序リストを生成する。配置関数ｆ１２０が、順序付けされた要素を１つずつとり、解Ｓ１０４を生成する。配置関数は、部分解および要素をその要素の優先順位値にマッピングする。優先順位関数が動的である場合、要素配置後、ステップ１１０が繰り返される。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、さらに良好な解が、優先順位アルゴリズムによって見つけられる良好な解の「近く」に存在することが可能である。したがって、こういったより良好な解を探索するように優先順位アルゴリズムを改良することが望ましい。
【課題を解決するための手段】
【００１０】
組合せ問題の場合、優先順位アルゴリズムは、通常、良好な解を発見する。しかし、多くの場合、より良好な解が「その近傍」にある。本発明は、こういったより良好な解を見つける自然かつ汎用的な手法を提供する。
【００１１】
本発明による優先順位アルゴリズムでは、順序付け関数が問題インスタンスの順序付けを生成する。次に、順序付けは、初期順序付けに「近い」さらなる順序付けを生成する特別な方法で変更される。再順序付けプロセスおよび近接度距離メトリックが提供される。次に、優先順位アルゴリズムの配置関数が、変更された順序付けに適用され、より良好な解が見つけられる。具体的には、近接度の測定にKendall-tau距離を使用する。他の距離メトリックを使用してもよい。
【００１２】
本発明による方法は、包括的なまたはランダムな変更を用いることができる。利点として、従来の優先順位アルゴリズムの特定の順序付けおよび配置関数は、通常、特定のアプリケーションドメインに有効であるように構築されるが、本発明による順序付けの変更はアプリケーションドメインから独立している。
【００１３】
本発明は、ドメイン固有の知識の追加をいずれも必要としない。本発明の一般的な実施は、優先順位アルゴリズムの構成要素をブラックボックスとして取り扱う。したがって、本発明は、優先順位アルゴリズムを使用するいずれのアプリケーションにも、たとえば、矩形条片箱詰め（rectangular strip packing）、ジョブショップスケジューリング、エッジクロス（edge crossing）、および分割数問題に適用することが可能である。
【発明の効果】
【００１４】
本発明は、より良好な解が優先順位アルゴリズムの順序付け近傍に存在することが多いことを利用する。配置関数および大半の優先順位アルゴリズムの順序付けは、問題を解くために、有価値なドメイン固有の知識をコード化する。しかし、配置関数を順序付けのみに適用するだけでは、この知識は完全には利用されない。
【００１５】
本発明は優先順位関数の知識を利用する。本発明による探索は、いずれの優先順位アルゴリズムにも拡張することが可能である。多くの実際の問題では、本発明による探索は、少数のみの再順序付けを評価した後、劇的に、優先順位アルゴリズムにより見つけられる解を大幅に改良することができる。具体的には、ランダム探索の平均結果は、ある問題に対して従来技術によるアルゴリズムにより得られた平均結果よりも２０％も良好であることができる。この結果は、探索がさらなる順序付けを評価すると改良され続ける。
【発明を実施するための最良の形態】
【００１６】
優先順位アルゴリズム
図２に示すように、本発明による優先順位アルゴリズム２００では、組合せ最適化問題２０１は要素Ｅの母集団Ｕおよび値の母集団Ｖによって特徴付けられる。
【００１７】
問題インスタンスＩ２０２は、要素の部分集合Ｅ⊆Ｕを含む。解はＥ中の要素からＶ中の値へのマッピングである。問題定義は、解における、結合を有する全順序付けも含む。Ｅ中の要素の部分集合のみが値を有し得るため、部分解が存在する。
【００１８】
順序付け関数ｏ２１０は、問題インスタンスＩ２０２をＩ中の順序付き要素シーケンスｘ１，・・・，ｘｎ２０３にマッピングする。
【００１９】
要素の順序付けは、以下さらに詳細に述べるように変更される（２２０）。シーケンス２０４は近傍順序付けと呼ぶことができる。再順序付けの効果は、従来技術の場合のように最高優先順位要素が必ずしも最初に配置されないことである。
【００２０】
配置関数ｆ２３０が再順序付け後の要素ｘ’１，・・・，ｘ’ｎ２０４に適用され、解Ｓｎ２０５が生成される。配置関数は、部分解および要素をその要素の優先順位値にマッピングする。
【００２１】
次に、終了条件２４０を満たすまで、たとえば最良解Ｓｂ２０６が選択されるまで、または所定の反復数に達するまで、変更ステップおよび配置ステップが、同じ順序付け２０３であるが、異なる近傍再順序付け２０４に対して繰り返される（２５０）。
【００２２】
変更された順序付け
順序付け関数２１０により提供される順序付け２０３を使用する代わりに、本発明による優先順位アルゴリズムは、再順序リスト２０４を生成するように変更する（２２０）。再順序リストは、配置に必ずしも最高優先順位要素をリストの最初の要素として有するわけではなく、配置関数は再順序付け後にのみ適用される。
【００２３】
上に述べたように、より良好な解は「近傍」にあることが多い。変更ステップ２２０は、このような近傍解を提供する。このような解は、順序付け２０３に近い再順序付けから得られる。
【００２４】
Kendall-tau距離
再順序リストの「近接度」を把握するために、距離メトリック、好ましくはKendall-tauまたは「bubble-sort」距離が提供される（Stuart Kendall's tau, Kotz等編集、「Encyclopedia of Statistical Sciences」Volume 4, pp.367-369, John Wiley & Sons, 1983を参照のこと）。スピアマンの階数相関係数、グッドマン−クラスカルのガンマ係数、およびユールのＱ等、他の距離メトリックを使用してもよい。
【００２５】
形式上、Kendall-tau距離は以下のように定義される。基となる集合｛ｘ１，；ｘｎ｝の２つの順序付けπおよびσを考える。π（ｉ）が順序付け中のｘｉの位置にある場合、Kendall-tau距離は、
【００２６】
【数１】
2005056421.tif 000003
【００２７】
である。ここで、Ｉ［ｚ］は、表現ｚが真の場合１であり、その他の場合０である。非公式では、Kendall-tau距離は、順序付けπを順序付けσに変換するために必要な移項の最小数である。
【００２８】
変更方法
変更は複数の異なる方法で行うことができる。１つの方法は、順序付けをランダム化して近傍順序付けを取得し、それから順序付け２０３と近傍順序付けの間の距離を測定して、いずれか許容できるものがあるか否かを確かめるというものである。しかし、このプロセスでは追加の作業が行われる場合がある。
【００２９】
決定ベクトル
好ましい実施の形態では、変更ステップ２２０は決定ベクトルａ２２１を要素ｘ１，・・・，ｘｎの順序付けπ２０３に適用し、このような値｜ａ−１ｎ｜がπと再順序付けσ２０４の間のKendall-tau距離である。但し、ノルムはＬ１距離であり、１ｎはすべて１のベクトル（１，１，・・・，１）である。利点として、決定ベクトルは距離メトリックに合うように予め求めることができる。言い換えれば、再順序付けは被制御様式で行われる。
【００３０】
さらに、フィールド（ａ１，ａ２，・・・，ａｎ）を有する決定ベクトルにより、変更を固定および動的両方の優先順位アルゴリズムに汎用化することができる。フィールドａｊは、再順序付け中の選択ステップにおいて考える残りの要素を表す。フィールドａｊ＝ｋの場合、ｋ番目に最も高い優先順位の要素がステップｊに配置される。
【００３１】
本発明を使用する文脈の中で上記定義を用いると、優先順位アルゴリズムは、本発明の文脈の中で、評価する決定ベクトルをどのように選択するかにより特徴付けることができる。たとえば、固定および動的の優先順位アルゴリズムは、すべて１の決定ベクトル１ｎ＝（１，１，・・・、１）に対応する単一の順序付けを評価する。すなわち、変更ステップはヌル操作である。
【００３２】
随時（anytime）優先順位アルゴリズム
さらに、本発明は、新しいクラスの優先順位アルゴリズム、すなわち「随時」優先順位アルゴリズムを可能にする。一般にコンピュータ処理では、随時プロセスは、任意の数の反復後に停止し、それでもなお有効な結果を生成することが可能である。
【００３３】
随時優先順位アルゴリズムは、固定または動的な優先順位アルゴリズムを拡張したものである。名称が示すように、随時アルゴリズムは、任意の数の反復後に停止し、それまでに評価した最良解を返すことができる。これは、常に完了しなければならない従来技術による優先順位アルゴリズムとは対照的である。
【００３４】
随時優先順位アルゴリズムは、配置関数をランダムな順序付けに適用する。決定ベクトルに関しては、これは、［１，ｎ−ｉ＋１］からランダムに独立して、かつ均等に各要素ａiを選択することに相当する。完全にランダムな随時優先順位アルゴリズムは、終了するまで配置関数を問題要素の新しい順序付けに適用し続ける。
【００３５】
包括的な優先順位アルゴリズム
「包括的」な随時優先順位アルゴリズムは、最終的に考えられるすべてのｎ！決定ベクトル（１≦＿ａi≦ｎ−ｉ＋１）を考慮する。このベクトルの集合は、再順序付けＯｎを生成する。すべてのｎ！決定ベクトルを考慮することは実際的ではない。したがって、決定ベクトルが評価された順序は実行に重要である。本発明は、Ｏｎに対する総順序付けを、
｜ａ−１ｎ｜＜｜ｂ−１ｎ｜の場合、ａ＜ｂ
として定義し、｜ａ−１ｎ｜＝｜ｂ−１ｎ｜の場合、ａ＜ｂは、ベクトルの辞書式順序付けにおいてｂよりも前にくる場合にのみ真である。決定ベクトルに対するこの総順序付けの直観は、固定優先順位アルゴリズムから導き出される。言い換えれば、本発明は、Kendall-tau距離が広がるに従って順序付けから外側に向けて探索する。たとえば、隣接する各要素対を移項し、それから１つ離れた要素を移項し、それから２つ離れた要素を移項する、といったようにする。
【００３６】
確率的優先順位アルゴリズム
問題によっては、要素順序付けに対する小さな摂動が、解の品質にごくわずかな差を生じさせる傾向を有するものがある。この場合、摂動が大きいほど影響が大きくなり得る。これは確率的探索ストラテジの動機となる。このストラテジは、ある確率分布に従って各ステップにおいて決定ベクトルをランダムに選択する。
【００３７】
決定ベクトルに関して、決定ベクトルａはある関数ｇのｇ（｜ａ−１ｎ｜）、たとえばあるパラメータｐの関数（１−ｐ）｜ａ−１ｎ｜に比例する確率で選択される。これにより、ランダムに選択される順序付けが順序付けのどの程度近くにある傾向があるかが決まる。固定優先順位アルゴリズムの場合、これは以下の解釈を有する。
【００３８】
τが順序付けである場合、各ステップにおいて、順序付けσが（１−ｐ）ｄＫｅｎ（τ，σ）に比例する確率で選択される。上記分布に従って決定ベクトルを選択するために、各ａｉが以下のように求められる。最初、ｑは０である。以下を繰り返す：確率ｐで選択し、終了してａｉ＝ｑ＋１を出力し、選択されない場合、ｎ−ｉ＋１を法としてｑを１増分する。
【００３９】
言い換えれば、順序付け２０３の最初の要素ｘ１が、確率ｐを有する近傍順序付けの最初の要素ｘ’１であるように選択される。要素が選択されない場合、次の要素が試みられ、順序付けの最後の要素に達するまで以下同様に試みられ、それから、順序付けのすべての要素が近傍順序付けに移動するまで上からの確率的選択を繰り返す。ここで、確率の値は再順序付けが順序付けにどの程度近いかを制御する。
【００４０】
包括的および確率的アルゴリズムは両方とも等しく良好に動的優先順位アルゴリズムに適用される。順序付けは要素が配置されるときに変更されるため、固定優先順位アルゴリズムの場合のように順序付け間のKendall-tau距離に直接結び付けることはできない。
【００４１】
他の変形としては以下が挙げられる。関数を通して探索が循環する、またはいくつかの順序付け関数を並列に適用する、いくつかの順序付け関数があってよい。また、いくつかの配置関数があってもよい。
【００４２】
ある定数ｋについて、包括的探索が最初のｎ−ｋ個のフィールドのみに対して行われるように、決定ベクトルの最後のｋ個のフィールドを切り捨てることができる。あるいは、最後のｋ個のフィールドのみについて考えられるすべての値を考慮してもよい。これは、対応するフィールドをゼロに設定することにより行うことができる。
【００４３】
さらに、順序付け２０３は、対応する再順序リストが順序付けを置換することができるよりも、特定の再順序付けが良好な解につながる場合、置換する（２６０）ことができる。次に、決定ベクトルが新しい順序付けから適用される。包括的探索について、この場合、決定ベクトルはすべて１のベクトルから再開される。
【００４４】
本発明を好ましい実施の形態の例として説明したが、他の様々な適合および変更を本発明の精神および範囲内で行うことができることを理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内にあるこのような変形および変更をすべて含むことにある。
【図面の簡単な説明】
【００４５】
【図１】従来技術による優先順位アルゴリズムの流れ図である。
【図２】本発明による優先順位アルゴリズムの流れ図である。
【図１】
2005056421.tif 000004
【図２】
2005056421.tif 000005
【外国語明細書】
2005056421.tif 000006
2005056421.tif 000007
2005056421.tif 000008
2005056421.tif 000009
2005056421.tif 000010
2005056421.tif 000011
2005056421.tif 000012
2005056421.tif 000013
2005056421.tif 000014
2005056421.tif 000015
2005056421.tif 000016