paretosearch アルゴリズム

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

`paretosearch` アルゴリズム

`paretosearch` アルゴリズムの概要

paretosearch アルゴリズムは、一連のポイントに対してパターン検索を使用して、非優勢ポイントを繰り返し検索します。多目的用語を参照してください。パターン検索は、各反復ですべての境界と線形制約を満たします。

理論的には、アルゴリズムは真のパレート最適解に近い点に収束します。収束についての議論と証明については、Custòdio et al. [1] を参照してください。この証明は、Lipschitz 連続目的関数と制約条件を持つ問題に適用されます。

`paretosearch` アルゴリズムの定義

paretosearch は、アルゴリズム内でいくつかの中間量と許容値を使用します。

量	定義
ランク	ポイントのランクには反復的な定義があります。非優越点のランクは 1 です。任意の整数 `k` > 1 について、その点を支配する唯一の点の順位が `k` より厳密に小さい場合、その点は順位 `k` を持ちます。
ボリューム	目的関数空間内の点の集合pの超体積は、すべてのインデックスjに対して不等式を満たす。 f_i(j) < p_i < M_i, ここで、f_i(j) はパレート集合内の j 番目の目的関数値の i 番目の要素であり、M_i はパレート集合内のすべての点の i 番目の要素の上限です。この図では、M は参照点と呼ばれます。図の灰色の陰影は、一部の計算アルゴリズムが包含除外計算の一部として使用する体積の部分を示しています。詳細については、Fleischer [3] を参照してください。 `paretosearch` は、非優勢点の数が目的点の数を超える場合にのみ体積を計算します。`paretosearch` は参照点 M = `max(pts,[],1) + 1` を使用します。ここで、`pts` は行が点である行列です。ボリュームの変化はアルゴリズムを停止する要因の 1 つです。詳細については、停止条件を参照してください。
距離	距離は、個体とその最も近い隣人との近さを測る尺度です。`paretosearch` アルゴリズムは、同じランクの個体間の距離を測定します。このアルゴリズムは目的関数空間で距離を測定します。アルゴリズムは、極端な位置にある個体間の距離を `Inf` に設定します。残りの個体については、アルゴリズムは、個体のソートされた近隣個体間の正規化された絶対距離の次元の合計として距離を計算します。つまり、次元 `m` とソートされスケールされた個々の `i` の場合: `distance(i) = sum_m(x(m,i+1) - x(m,i-1))`. アルゴリズムは各次元を個別にソートするため、neighbors という用語は各次元の近隣を意味します。同じランクでも距離が大きい個体は選択される可能性が高くなります (距離が大きいほど良い)。距離は、停止基準の一部であるスプレッドの計算における要素の 1 つです。詳細については、停止条件を参照してください。
拡散	スプレッドはパレート集合の動きを表す尺度です。広がりを計算するために、`paretosearch` アルゴリズムはまず、有限距離のパレートフロント上の点の混雑距離の標準偏差である σ を評価します。Q はこれらの点の数、d はこれらの点間の平均距離です。次に、アルゴリズムは、そのインデックスの現在の最小値のパレート点と、前の反復におけるそのインデックスの最小点との差のノルムの `k` 目的関数インデックスの合計である μ を評価します。スプレッドは `spread` = (μ + σ)/(μ + Qd). 極端な目的関数の値が反復間であまり変化しない (つまり、μ が小さい) 場合、およびパレートフロント上の点が均等に分散している (つまり、σ が小さい) 場合、分散は小さくなります。 `paretosearch` は停止条件でスプレッドを使用します。スプレッドがあまり変化しない場合は反復が停止します。詳細については、停止条件を参照してください。
`ParetoSetChangeTolerance`	検索の停止条件。`paretosearch` は、反復ウィンドウ内でボリューム、広がり、または距離が `ParetoSetChangeTolerance` 以上変化しない場合に停止します。詳細については、停止条件を参照してください。
`MinPollFraction`	反復中にポーリングする場所の最小割合。`paretosearch` は少なくとも `MinPollFraction`*(パターン内のポイント数) の場所をポーリングします。投票されたポイントの数によって非優勢ポイントが得られた場合には、投票は成功とみなされます。それ以外の場合、`paretosearch` は、非優勢ポイントが見つかるか、パターン内のポイントがなくなるまでポーリングを続けます。このオプションは、`UseVectorized` オプションが `true` の場合には適用されません。その場合、`paretosearch` はすべてのパターンポイントをポーリングします。

`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.