Comparator#

Layer 2: Compose

Problemは、解の相対的な優劣を判断する処理を、差し替え可能なトップレベルコンポーネントであるComparatorに委ねています。 Problemのcomparator引数で渡します。

Comparatorの役割#

Comparatorには__init__自身を含め、4つの抽象メソッドがあります。

__init__(weights, eps_cv, eps_obj, direction=None): weights/eps_cv/eps_obj/directionを保持します
sort_population(population) -> np.ndarray: 個体群全体を最良から最悪へ並べるインデックス配列を返します
compare_population(population, idx_a, idx_b) -> int: 個体群内の2個体を比較します（-1: aがより良い、1: bがより良い、0: 同等）
compare(fa, cv_a, fb, cv_b) -> int: Populationを経由せず、目的値と制約違反から2点を直接比較する軽量版です

__init__が抽象メソッドである点は、他のコンポーネントと異なります。独自のComparatorを実装するサブクラスは、必ずsuper().__init__(weights, eps_cv, eps_obj, direction=...)を呼び出さなければなりません。

また、f/cvから毎回新しく導出するのではなく、選択をまたいで永続化すべきpopulation相対的なランキング状態のために、3つの具象メソッドを提供します。 get_required_attrsとprepare_populationは既定で空/no-opですが、rank_populationはこの2つを組み合わせるものであり、それ自体はno-opではありません。

get_required_attrs(problem) -> list[PopulationAttribute]: ComparatorがPopulation/Archiveに保持させる必要があるPopulationAttributeを宣言します。既定では空です
prepare_population(population) -> None: 指定された個体群についてそれらの属性を新たに再計算し、書き込みます。既定ではno-opです
rank_population(population) -> np.ndarray: prepare_populationに続けてsort_populationを実行します。新しくマージしたプールでの環境選択では、ランク付け前に永続化状態を新しい集合に対して再計算するため、sort_populationを直接呼ばずにこれを呼び出します

現在ランク付け対象になっている個体群だけから完全なランキングを導出でき、population extractionをまたいで状態を持ち越す必要がないComparatorは、この3つのいずれも必要としません。これはSPEA2Comparatorを除く組み込みComparatorすべてに当てはまります。個体群全体に依存するNSGA2Comparatorの混雑度距離でさえ、与えられたPopulationが現在保持するf/cvの値から毎回新しく再計算されます。 SPEA2Comparatorは、ランキング状態が環境選択を生き延びる必要がある組み込みの例です。次世代の（より小さい）個体群における交配選択が、以前の統合プールで計算された適応度をゼロから再計算するのではなく再利用しなければならないためです。

組み込みComparator#

Class	When to use
`SingleObjectiveComparator`	単一目的問題
`WeightedSumComparator`	重み付き線形結合によるスカラー化。単一目的と多目的の両方に対応
`ParetoComparator`	支配関係だけでランク付け（混雑度などの副次的指標なし）
`NSGA2Comparator`	Paretoランク + 混雑度距離 [3]
`SPEA2Comparator`	個体群全体に依存するSPEA2適応度 [4]
`HypervolumeComparator`	フロントランク + 排他的HV寄与度（SMS-EMOA方式） [5]
`EpsilonDominanceComparator`	ε-dominanceによるランキング [6]
`NSGA3Comparator`	参照点によるニッチの維持 [7]
`RNSGA2Comparator`	ユーザー指定の参照点による選好誘導 [8]

SingleObjectiveComparator(direction=None, *, eps_cv=1e-6, eps_obj=1e-6)はdirectionを省略でき、その場合は最小化として扱います。 WeightedSumComparator(direction, *, eps_cv=1e-6, eps_obj=1e-6)はdirectionが必須で、省略するとTypeErrorになります。このクラスに限り、渡したdirectionがそのままスカラー化の重みとして使われます（score = f @ direction）。符号だけでなく大きさも重みとして機能するため、Problemで述べた「directionは符号のみ、重みの大きさは別の概念」という一般的な役割分担とは異なる、このクラス固有の扱いです。 ParetoComparator(direction=None, *, eps_cv=1e-6, eps_obj=1e-6, sorter=non_dominated_sort, dominator=None)は、支配関係のみで個体群をランク付けします。 NSGA2Comparator/HypervolumeComparator/NSGA3Comparator/RNSGA2Comparator/EpsilonDominanceComparatorの共通基底であり、具象クラスとして単独でも使えます。 dominator引数はDominator、sorter引数はNonDominatedSorterを注入する差し替え点で、互いに独立した軸です。 NSGA2Comparatorは、ParetoComparatorに混雑度距離による副次的な順位付けを加えます。ソート結果はPopulationのキャッシュ（get_cache/set_cache）に保存され、個体群が変更されるまで世代内で使い回されます。

個体群相対的なComparator#

SPEA2ComparatorとHypervolumeComparatorは、いずれもcompare()を呼ぶとNotImplementedErrorを送出します。 SPEA2のfitnessも排他的HV寄与度も、個体群全体に依存する指標であり、2点だけからは計算できないためです。これはバグではなく意図した設計であり、is_population_relative=Trueというクラス属性がその旨を示すマーカーになっています。 PSOのpbest更新やPairwiseComparisonSetのように、2点だけの比較（compare()）が必要な場面でこれらのComparatorは使えません。そのような場面では代わりにParetoComparatorを使います。 compare_population()（個体群のインデックスを介した比較）はどちらのクラスでも定義されているため、トーナメント選択などはそのまま使えます。 SPEA2Comparatorはさらに、前述のget_required_attrs/prepare_populationの組を使います。get_required_attrsが永続的なspea2_fitness属性を宣言し、prepare_populationが与えられた個体群に対して\(S(i)\)/\(R(i)\)/\(D(i)\)/\(F(i)\)を再計算してそこに書き込みます。環境選択（rank_populationを呼ぶTruncationSelection）は、個体群と子個体を統合したプール全体に対して適応度を新しく再計算します。打ち切りを生き残った個体はその適応度の値を保持したまま次世代に持ち越されるため、次世代の交配選択におけるcompare_population()呼び出しは、サイズの異なる集合に対して再計算するのではなく、永続化された値をそのまま再利用します。 HypervolumeComparatorのHV計算は、フロントごとにO(N)回のleave-one-out評価を行います。目的数が多い問題では、この計算コストが大きくなります。

注釈

HypervolumeComparatorの内部実装とは別に、公開関数saealib.hypervolume(f, reference_point)があります。これは最適化後の結果を評価する性能指標として単独で使え、HypervolumeComparatorとは関係ありません。詳細はUtilsを参照してください。

参照点を使うComparator#

NSGA3Comparator(reference_points, direction=None, *, ...)は、reference_points（shape (n_ref, n_obj)、単体シンプレックス上の点）が必須引数です。通常はsaealib.utils.weight_vectors.uniform_weight_vectors(n_obj, n_divisions)で一様に生成したものを渡します。 rngプロパティは遅延生成され、Optimizer実行時はRunnerがctx.rngからspawnした乱数生成器を注入します。この内部rngはチェックポイントの保存対象に含まれず、再開時は新しくspawnし直されます。 NSGA3Comparatorとは異なり、RNSGA2Comparator(reference_points, epsilon=0.001, direction=None, *, ...)は参照点が単体シンプレックス上にある必要はなく、ユーザーが望む目的関数値（aspiration point）をそのまま指定できます。 epsilonは、同じ参照点に近い解同士を間引くε-clearingの半径です。 EpsilonDominanceComparator(eps, mode="additive", direction=None, *, ...)は、ParetoComparatorのdominatorをEpsilonDominatorに差し替えるだけの薄いラッパーです。 DecompositionComparatorは、MOEA/D風のスカラー化によるランク付けを行うComparatorです。詳細はそちらのページで扱います。

独自Comparatorの実装方法#

独自のランキング方式が必要な場合は、Comparatorをサブクラス化し、4つの抽象メソッドすべてを実装します。 __init__は必ずsuper().__init__(weights, eps_cv, eps_obj, direction=...)を呼び出さなければなりません。

import numpy as np
from saealib import Comparator


class RandomComparator(Comparator):
    """A simple example that always considers only feasibility."""

    def __init__(self, direction=None, *, eps_cv=1e-6, eps_obj=1e-6):
        super().__init__(np.empty(0), eps_cv, eps_obj, direction=direction)

    def sort_population(self, population):
        cv = population.get_array("cv")
        return np.argsort(cv)

    def compare_population(self, population, idx_a, idx_b):
        cv = population.get_array("cv")
        return self.compare(None, cv[idx_a], None, cv[idx_b])

    def compare(self, fa, cv_a, fb, cv_b):
        if cv_a > self.eps_cv and cv_b <= self.eps_cv:
            return 1
        if cv_b > self.eps_cv and cv_a <= self.eps_cv:
            return -1
        return 0

クラス属性is_population_relative = Trueを設定し、指標のペア単位の順序を孤立した2つの目的値/CVタプルから本当に定義できない場合には、その理由を説明するNotImplementedErrorをcompare()から送出させます。SPEA2のfitnessや排他的HV寄与度がこれに該当します。単に指標が個体群全体に依存するという理由だけでは該当しません（NSGA2Comparatorの混雑度距離も個体群全体に依存しますが、compare()は通常のPareto支配によって定義できます）。別途、その指標をより小さい個体群へ引き継ぐ必要もある場合（SPEA2のfitnessは、次世代の交配選択で有効であり続けるために打ち切り後も保持する必要があります）は、get_required_attrsをオーバーライドして保存先を宣言し、prepare_populationをオーバーライドして新しく再計算します。そうしないと、後の読み取りでサイズの異なる個体群に対して計算された値を参照することになります。