NonDominatedSorter#

Layer 2: Compose

ParetoComparator系のComparator（NSGA2Comparator/HypervolumeComparator/NSGA3Comparator/RNSGA2Comparator/EpsilonDominanceComparator）は、個体群をフロントへ振り分ける処理をsorterという差し替え可能な引数に委ねています。Dominatorが「2点間の支配関係の定義」を担うのに対し、sorterは「その支配関係を使ってどうフロントに割り振るか」というもう1つの独立した差し替え軸です。

NonDominatedSorterの役割#

NonDominatedSorterは、抽象基底クラスではなくProtocol（構造的部分型）として定義されています。__call__(f, direction=None, *, dominator=None) -> tuple[ranks, fronts]というシグネチャを満たす呼び出し可能オブジェクトであれば、クラスを継承しなくてもsorterとして渡せます。

ranksは各個体のフロント番号（0が最良）を表す配列、frontsはfronts[i]がフロントiに属する個体のインデックスリストであるという契約を満たします。

組み込みNonDominatedSorter#

non_dominated_sort/dda_non_dominated_sortはいずれも、上記の(ranks, fronts)契約を満たす関数です（クラスとしての階層は持たない）。

関数

アルゴリズム

non_dominated_sort

[3]の非劣ソート。フロントを1つずつ取り除く方式

dda_non_dominated_sort

支配度アプローチ（Zhou et al., 2017が支配度行列を、Mishra & Senwar, 2020がDDA-ENSのフロント割り当てを提案）

non_dominated_sortの計算量はO(MN²)ですが、支配行列をNumPyでベクトル化して構築するため実測では高速に動作します。dda_non_dominated_sortは、non_dominated_sortと完全に同一の(ranks, fronts)を返すことが保証されているそのまま置き換え可能な代替関数であり、個体数Nや目的数Mが大きい場合（M > 100）のスケーラビリティ向けに用意されています。

両者とも、NaNを含む行の扱いは共通しています。NaNを含む行は、通常のフロント分割から除外され、最終フロントの後にセンチネルフロントとして1個体ずつ追加されます。

sorterとdominatorは独立した差し替え軸です。non_dominated_sort/dda_non_dominated_sortはどちらも、内部でdominator.dominance_matrix()を呼ぶだけで、支配関係の定義自体には関与しません。dominatorを省略するとParetoDominatorが既定として使われます。

補助関数#

Pareto系Comparatorの内部実装で使われる補助関数も、公開APIとして単体で利用できます。

crowding_distance(f_front)：単一フロント内の混雑度距離を計算します。NSGA2Comparatorが使います。境界解（各目的の最小値と最大値を取る解）にはinfが割り当てられます。

crowding_distance_all_fronts(f, fronts)：non_dominated_sortが返す全フロントに対してcrowding_distanceを適用します。

spea2_fitness(f, direction=None, dominator=None)：SPEA2Comparatorが使う適応度計算[4]。強度（支配する個体数）、生の適応度（それを支配する個体の強度の総和）、密度（\(k\)近傍距離の逆数）の3要素から算出します。

警告

spea2_fitnessの戻り値は「低いほど良い」という規約であり、saealib全体の「高いほど良い」というスコア規約とは逆です。他のComparatorへそのまま渡さないよう注意してください。

NonDominatedSorterの拡張方法#

NonDominatedSorterはProtocolであるため、(ranks, fronts)契約を満たす関数を1つ書くだけで独自実装として使えます。基底クラスを継承する必要はありません。

import numpy as np
from saealib import non_dominated_sort


def logged_non_dominated_sort(f, direction=None, *, dominator=None):
    """The minimal function satisfying the Protocol, simply adding pre-processing to the existing implementation."""
    print(f"sorting {len(f)} individuals")
    return non_dominated_sort(f, direction, dominator=dominator)

ParetoComparator(sorter=logged_non_dominated_sort, ...)のように渡せば、既存のComparator実装を変更せずにソート方式を差し替えられます。

関連コンポーネント#

  • Dominator：sorterと対になる、2点間の支配関係の定義

  • Comparator：sorter引数を持つParetoComparator系のComparator

参照#