このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。
paretosearch
アルゴリズム
paretosearch
アルゴリズムの概要
paretosearch
アルゴリズムは、一連のポイントに対してパターン検索を使用して、非優勢ポイントを繰り返し検索します。多目的用語を参照してください。パターン検索は、各反復ですべての境界と線形制約を満たします。
理論的には、アルゴリズムは真のパレート最適解に近い点に収束します。収束についての議論と証明については、Custòdio et al. [1] を参照してください。この証明は、Lipschitz 連続目的関数と制約条件を持つ問題に適用されます。
paretosearch
アルゴリズムの定義
paretosearch
は、アルゴリズム内でいくつかの中間量と許容値を使用します。
量 | 定義 |
---|---|
ランク | ポイントのランクには反復的な定義があります。
|
ボリューム | 目的関数空間内の点の集合pの超体積は、すべてのインデックスjに対して不等式を満たす。 fi(j) < pi < Mi, ここで、fi(j) はパレート集合内の j 番目の目的関数値の i 番目の要素であり、Mi はパレート集合内のすべての点の i 番目の要素の上限です。この図では、M は参照点と呼ばれます。図の灰色の陰影は、一部の計算アルゴリズムが包含除外計算の一部として使用する体積の部分を示しています。 詳細については、Fleischer [3] を参照してください。
ボリュームの変化はアルゴリズムを停止する要因の 1 つです。詳細については、停止条件 を参照してください。 |
距離 | 距離は、個体とその最も近い隣人との近さを測る尺度です。 アルゴリズムは、極端な位置にある個体間の距離を
アルゴリズムは各次元を個別にソートするため、neighbors という用語は各次元の近隣を意味します。 同じランクでも距離が大きい個体は選択される可能性が高くなります (距離が大きいほど良い)。 距離は、停止基準の一部であるスプレッドの計算における要素の 1 つです。詳細については、停止条件 を参照してください。 |
拡散 | スプレッドはパレート集合の動きを表す尺度です。広がりを計算するために、
極端な目的関数の値が反復間であまり変化しない (つまり、μ が小さい) 場合、およびパレート フロント上の点が均等に分散している (つまり、σ が小さい) 場合、分散は小さくなります。
|
ParetoSetChangeTolerance | 検索の停止条件。paretosearch は、反復ウィンドウ内でボリューム、広がり、または距離が ParetoSetChangeTolerance 以上変化しない場合に停止します。詳細については、停止条件 を参照してください。 |
MinPollFraction | 反復中にポーリングする場所の最小割合。 このオプションは、 |
paretosearch
アルゴリズムのスケッチ
検索を初期化
初期のポイント セットを作成するために、paretosearch
はデフォルトで、問題の範囲に基づいて準ランダム サンプルから options.ParetoSetSize
ポイントを生成します。詳細については、Bratley と Fox [2] を参照してください。問題の次元が 500 を超える場合、paretosearch
は ラテン ハイパーキューブ サンプリング を使用して初期ポイントを生成します。
コンポーネントに境界がない場合、paretosearch
は人工的な下限値 -10
と人工的な上限値 10
を使用します。
コンポーネントに境界が 1 つしかない場合、paretosearch
はその境界を幅 20 + 2*abs(bound)
の間隔の終点として使用します。たとえば、コンポーネントに上限がなく、下限が 15 の場合、paretosearch
は 20 + 2*15 = 55 の間隔幅を使用するため、15 + 55 = 70 という人工的な上限を使用します。
options.InitialPoints
でいくつかの初期ポイントを渡すと、paretosearch
はそれらのポイントを初期ポイントとして使用します。paretosearch
は、必要に応じてさらにポイントを生成し、少なくとも options.ParetoSetSize
個の初期ポイントを取得します。
次に、paretosearch
は初期点をチェックして、境界と線形制約に関して実行可能であることを確認します。必要に応じて、paretosearch
は線形計画問題を解くことによって、初期点を線形実行可能点の線形部分空間に投影します。このプロセスにより、いくつかのポイントが一致する可能性があります。その場合、paretosearch
は重複するポイントを削除します。paretosearch
は、人工的な境界の初期ポイントを変更せず、指定された境界と線形制約に対してのみ変更します。
線形制約を満たすように点を移動した後、必要に応じて、paretosearch
は点が非線形制約を満たしているかどうかを確認します。paretosearch
は、すべての非線形制約を満たしていない点に Inf
のペナルティ値を与えます。次に、paretosearch
は残りの実行可能なポイントの欠落している目的関数値を計算します。
メモ
現在、paretosearch
は非線形等式制約 ceq(x) = 0
をサポートしていません。
アーカイブと現職者の作成
paretosearch
は 2 つのポイント セットを維持します。
archive
—options.MeshTolerance
未満のメッシュ サイズに関連付けられ、options.ConstraintTolerance
内のすべての制約を満たす非優勢ポイントを含む構造。archive
構造には2*options.ParetoSetSize
ポイントしか含まれず、最初は空です。archive
の各ポイントには、ポイントが生成されたメッシュ サイズである関連付けられたメッシュ サイズが含まれています。iterates
— 非支配点と、より大きなメッシュ サイズまたは実行不可能性に関連付けられたいくつかの支配点を含む構造。iterates
の各ポイントには、関連付けられたメッシュ サイズが含まれます。iterates
には、最大options.ParetoSetSize
個のポイントが含まれます。
より良いポイントを見つけるための投票
paretosearch
は iterates
からポイントをポーリングし、ポーリングされたポイントは iterates
のポイントから関連するメッシュ サイズを継承します。paretosearch
アルゴリズムは、境界とすべての線形制約に関して実現可能性を維持するポーリングを使用します。
問題に非線形制約がある場合、paretosearch
は各投票ポイントの実現可能性を計算します。paretosearch
は、実行不可能なポイントのスコアを実行可能なポイントのスコアとは別に保持します。実行可能なポイントのスコアは、そのポイントの目的関数値のベクトルです。実行不可能な点のスコアは、非線形実行不可能性の合計です。
paretosearch
は、 iterates
内の各ポイントに対して、少なくとも MinPollFraction
*(パターン内のポイント数) の位置をポーリングします。投票されたポイントが、現職(元の)ポイントに対して少なくとも 1 つの非優位ポイントを与える場合、投票は成功と見なされます。それ以外の場合、paretosearch
は、非優勢ポイントが見つかるか、パターン内のポイントがなくなるまでポーリングを続けます。paretosearch
がポイントを使い果たし、非優位ポイントを生成しない場合、paretosearch
は投票が失敗したと宣言し、メッシュ サイズを半分にします。
ポーリングによって非優勢ポイントが見つかった場合、paretosearch
は、拡張によって優勢ポイントが生成されるまで、成功した方向にポーリングを繰り返し拡張し、そのたびにメッシュ サイズを 2 倍にします。この拡張中に、メッシュ サイズが options.MaxMeshSize
(デフォルト値: Inf
) を超えると、ポーリングは停止します。目的関数の値が -Inf
まで減少すると、paretosearch
は問題が無制限であると宣言して停止します。
archive
と iterates
構造を更新
iterates
内のすべてのポイントをポーリングした後、アルゴリズムは新しいポイントを iterates
および archive
構造内のポイントと一緒に調べます。paretosearch
は各ポイントの順位、つまりパレート最前線の数を計算し、次の操作を実行します。
archive
でランク 1 ではないすべてのポイントを削除対象としてマークします。iterates
に挿入する新しいランク1
ポイントをマークします。iterates
内で、関連付けられたメッシュ サイズがoptions.MeshTolerance
より小さい実行可能なポイントをマークし、archive
に転送します。iterates
内の支配点が、iterates
への新しい非支配点の追加を妨げる場合にのみ、削除対象としてマークします。
次に、paretosearch
は各ポイントの体積と距離の測定値を計算します。マークされたポイントが含まれる結果として archive
がオーバーフローする場合は、最も大きなボリュームを持つポイントが archive
を占有し、他のポイントは残ります。同様に、iterates
に追加されるようにマークされた新しいポイントは、体積の順に iterates
に入ります。
iterates
がいっぱいで支配点がない場合、paretosearch
は iterates
に点を追加せず、反復が失敗したと宣言します。paretosearch
は iterates
のメッシュ サイズを 1/2 倍にします。
停止条件
目的関数が 3 つ以下の場合、paretosearch
は停止手段としてボリュームとスプレッドを使用します。4 つ以上の目標の場合、paretosearch
は距離と拡散を停止手段として使用します。この説明の残りの部分では、paretosearch
が使用する 2 つの尺度を 適用可能な 尺度と呼びます。
アルゴリズムは、適用可能な測定値の最後の 8 つの値のベクトルを維持します。8 回の反復の後、アルゴリズムは各反復の開始時に 2 つの適用可能な測定値をチェックします。ここで、tol = options.ParetoSetChangeTolerance
は次のようになります。
spreadConverged = abs(spread(end - 1) - spread(end)) <= tol*max(1,spread(end - 1));
volumeConverged = abs(volume(end - 1) - volume(end)) <= tol*max(1,volume(end - 1));
distanceConverged = abs(distance(end - 1) - distance(end)) <= tol*max(1,distance(end - 1));
いずれかの適用可能なテストが true
の場合、アルゴリズムは停止します。それ以外の場合、アルゴリズムは、適用可能な測定値のフーリエ変換の二乗項の最大値から最初の項を引いた値を計算します。次に、アルゴリズムは最大値を削除された項 (変換の DC 成分) と比較します。削除されたいずれかの項が 100*tol*(max of all other terms)
より大きい場合、アルゴリズムは停止します。このテストは基本的に、測定値のシーケンスが変動しておらず、したがって収束していることを判定します。
さらに、プロット関数または出力関数によってアルゴリズムが停止したり、時間制限または関数評価制限を超えたためにアルゴリズムが停止したりすることがあります。
返される値
アルゴリズムは、次のようにパレート面上の点を返します。
paretosearch
は、archive
とiterates
のポイントを 1 つのセットに結合します。目的関数が 3 つ以下の場合、
paretosearch
は最大ボリュームから最小ボリュームまでのポイントを最大ParetoSetSize
ポイントまで返します。目的関数が 4 つ以上ある場合、
paretosearch
は最大距離から最小距離までのポイントを最大ParetoSetSize
ポイントまで返します。
並列計算とベクトル化関数評価のための変更
paretosearch
が目的関数の値を並列またはベクトル化された形式で計算する場合 (UseParallel
は true
または UseVectorized
は true
です)、アルゴリズムにいくつかの変更が加えられます。
UseVectorized
がtrue
の場合、paretosearch
はMinPollFraction
オプションを無視し、パターン内のすべてのポーリング ポイントを評価します。並列計算を行う場合、
paretosearch
はiterates
内の各ポイントを順番に調べ、各ポイントから並列ポーリングを実行します。MinPollFraction
の投票ポイントの割合を返した後、paretosearch
はいずれかの投票ポイントがベース ポイントを支配しているかどうかを判断します。そうであれば、投票は成功したとみなされ、他の並行評価は停止します。そうでない場合は、優勢なポイントが表示されるか投票が終了するまで投票が続行されます。paretosearch
は、ワーカー上またはベクトル化された形式のいずれかで目的関数の評価を実行しますが、両方を実行することはありません。UseParallel
とUseVectorized
の両方をtrue
に設定すると、paretosearch
はワーカー上で目的関数の値を並列に計算しますが、ベクトル化されることはありません。この場合、paretosearch
はMinPollFraction
オプションを無視し、パターン内のすべてのポーリング ポイントを評価します。
paretosearch
を素早く実行する
paretosearch
を実行する最も速い方法は、いくつかの要因によって異なります。
目的関数の評価が遅い場合は、通常、並列コンピューティングを使用するのが最も高速です。目的関数の評価が高速な場合、並列コンピューティングのオーバーヘッドは大きくなる可能性がありますが、目的関数の評価が低速な場合は、通常、より多くのコンピューティング能力を使用するのが最適です。
メモ
並列コンピューティングには Parallel Computing Toolbox™ ライセンスが必要です。
目的関数の評価にそれほど時間がかからない場合は、通常、ベクトル化された評価を使用するのが最も高速です。ただし、ベクトル化された計算ではパターン全体が評価されるのに対し、シリアル評価ではパターンのごく一部のみが評価されるため、常にそうであるとは限りません。特に高次元では、この評価の削減により、一部の問題ではシリアル評価が高速化される可能性があります。
ベクトル化されたコンピューティングを使用するには、目的関数が任意の数の行を持つ行列を受け入れる必要があります。各行は評価する 1 つのポイントを表します。目的関数は、受け入れる行数と同じ行数を持ち、各目的関数ごとに 1 つの列を持つ目的関数値の行列を返す必要があります。単一目的の議論については、適応度関数をベクトル化する (
ga
) または ベクトル化された目的関数 (patternsearch
) を参照してください。
参照
[1] Custòdio, A. L., J. F. A. Madeira, A. I. F. Vaz, and L. N. Vicente. Direct Multisearch for Multiobjective Optimization. SIAM J. Optim., 21(3), 2011, pp. 1109–1140. Preprint available at https://www.researchgate.net/publication/220133323_Direct_Multisearch_for_Multiobjective_Optimization.
[2] Bratley, P., and B. L. Fox. Algorithm 659: Implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Software 14, 1988, pp. 88–100.
[3] Fleischer, M. The Measure of Pareto Optima: Applications to Multi-Objective Metaheuristics. In "Proceedings of the Second International Conference on Evolutionary Multi-Criterion Optimization—EMO" April 2003 in Faro, Portugal. Published by Springer-Verlag in the Lecture Notes in Computer Science series, Vol. 2632, pp. 519–533. Preprint available at https://api.drum.lib.umd.edu/server/api/core/bitstreams/4241d9c0-f514-4a41-bd58-07ac2538d918/content.