📂最適化理論

遺伝的アルゴリズムにおける自然選択とは何ですか？

定義

유전 알고리즘での 自然選択^{natural selection}、あるいは単に 選択 とは 目的函数 の値がより良い個体を選ぶ操作を指す。

説明 ¹

遺伝的アルゴリズムは適者生存から着想を得た手法であるため、自然選択は進化そのものの原動力であり最適化の性能に直接影響を与える。ここでの選択とは我々が最大化したい目的函数 $f$ 自体が「環境」となり、$f$ に適合する個体が生存して「選択」されることを意味する。

自然選択の典型的実装は ルーレットホイール^{roulette wheel} 方式で、各個体 $\mathbf{x}_{k}$ ごとに適合度 $f \left( \mathbf{x}_{k} \right)$ を計算して適合度が高いほど選ばれる確率が高くなるようにする。個体ごとに適合度に基づく期待値^{expected value} $E_{k}$ という重みを与え、非復元抽出で一部だけサンプリングして次世代へ渡し、残りは淘汰する。

ボルツマン選択

解集合の基数が $N$ だとしよう。

ソフトマックス関数の定義: $\mathbf{x} := (x_{1} , \cdots , x_{n}) \in \mathbb{R}^{n}$ としよう。$\displaystyle \sigma_{j} ( \mathbf{x} ) = {{ e^{x_{j}} } \over {\sum_{i=1}^{n} e^{x_{i}} }}$ に対して $\sigma ( \mathbf{x} ) := \left( \sigma_{1} (\mathbf{x}) , \cdots , \sigma_{n} (\mathbf{x} ) \right)$ のように定義された $\sigma : \mathbb{R}^{n} \to (0,1)^{n}$ を ソフトマックス^softmax と呼ぶ。

$$ E_{k} = {\frac{ e^{ f ( \mathbf{x}_{k} ) / T } }{ \sum_{i=1}^{N} e^{ f ( \mathbf{x}_{i} ) / T } }} \qquad , k = 1, \cdots , N $$ 基本的に $f : X \to \mathbb{R}$ は負になることもあるので、これらを正にする最も簡単なアイデアはソフトマックスを取ることだ。元のソフトマックスと異なる点はハイパーパラメータ $T > 0$ が追加されていることで、これは 温度^temperature と呼ばれ選択圧^{selection pressure}を調整する役割を果たす。これは2020年代以降に注目されたLLM^{Large Language Model}であるChatGPTにも見られるアイデアで、温度 $T$ が高くなるほど $\exp \left( f \left( x_{k} \right) / T \right) \to 1$ になり一様にサンプリングが行われ、適合度そのものよりハイパーパラメータの影響を強く受ける。逆に温度 $T$ が低ければ適合度の影響力が大きくなる。

このようにソフトマックスと温度を導入した選択方式を ボルツマン選択^{Boltzmann selection} と呼び、その名前は明らかにボルツマン分布から取られている。選択法としてルーレットホイールを使うなら、最も常識的で無難な方法だ。

ランク選択

ランク選択^{rank selection}とは適合度のランク、すなわち順位を通じて期待値を与える方式だ。この方式は直接的に適合度を使わずハイパーパラメータも特にないため $f$ に関してよくわからなくても一貫して適用可能だ。例えば最適化すべき $f$ 自体が多数ある場合に有用だったり、母集団における適合度の両極化をある程度緩和する効果があるかもしれない。