前回話した遺伝的アルゴリズム(GA)の改良版の一つとして、適応的遺伝的アルゴリズム(AGA)を紹介します。

GAの欠点

いい個体に対しては交差確率を小さくし、保存できるようにし、 一方、悪い個体に対しては変異確率を大きくし、できるだけいい個体を残すことを目標とします。

進化の初期段階では、 最適解に早く到達できるよう、高い交差確率と変異確率が望ましいです。また、後期では小さい確率で、最適解を見つかったら早く収束できるようにしたいです。

なので、変わらない確率がアルゴリズムの効率に高く影響していると考えられます。

AGAとGAの区別

GAの交差確率と変異確率が固定しています。

AGAでは交差確率と変異確率が個体の適応度により変わります。

AGAの中身

収束を検出する方法は世代ごとの最大適応度(Fmax)と平均適応度(Favg)の関係、いわゆるFmax-Favgです。この値が小さいほど、FavgがFmaxに近づきます。最適解に近づくのかもしれません。

例えば、大域最適解が1.0の適応度を持ち、GAが適応度が0.5の局所最適解に収束したとき、Fmax-Favgが減少し、Fmax-FavgがGA収束評価の基準として、交差確率Pcと変異確率Pmの値がそれにより変化します。

局所最適解にたどり着いたら、大域最適解を探すため、PcとPmの値が大きくしなければなりません。

つまり、Fmax-Favgの値とPc,Pmの値が反比例になります。
\begin{cases} pc=k1 \displaystyle\frac{1}{fmax-favg},k1 \leqslant 1.0 \\pm=k2 \displaystyle\frac{1}{fmax-favg},k2 \leqslant 1.0 \end{cases}

上記の式から、確かにPcとPmの値が適応度により変化しますが、まだ二つの問題があります。

• PcとPmはある特定の個体の適応度によるわけではなく、集団全体の平均と集団最大適応度によります。
• Pmの値がFmax-Favgだけでなく、個体の適応度Fにもかかわっています。FがFmaxに近づくほど、Pmの値が小さい。つまり、PmがFmax-Fに等しい。同じく、Pcの値もFmax-F'に等しい(F'は二つ交差する個体のなかに適応度の大きいほう)

なので、式はこうなります
\begin{cases}pc=k1\displaystyle\frac{fmax-f'}{fmax-favg}&,k1 \leqslant&1.0\\pm= k2\displaystyle\frac{fmax-f}{fmax-favg}&,k2 \leqslant&1.0 \end{cases}

最大適応度個体にとって、PcとPmが0、もし一つの個体F'=Favgのなら、Pc=k1、もしF=Favgのなら、Pm=k2。適応度が極めて低い個体(F<<Favg)にとって、PcとPmの値が>1になるかもしれません。PcとPmの値が1を超えないため

以下の制約を設定します。
\begin{cases}pc=&k3,f' \leqslant &favg\\pm=&k4,f \leqslant &favg\\&k3,k4 \leqslant &1.0\end{cases}

したがって、最終の式は
pc=\begin{cases}k1 \displaystyle\frac{fmax-f'}{fmax-favg}&,f' \geqslant&favg \\k3&,f' \leqslant&favg \end{cases}
pm= \begin{cases}k2 \displaystyle\frac{fmax-f}{fmax-favg}&,f'\geqslant&favg \\k4&,f' \leqslant&favg \end{cases}

kの値

上記では、適応度が最も高い個体のPcとPmが両方とも0です。この個体は次世代にコピーされています。こうなると、この個体が母集団で指数関数的に成長し、収束が早まります。この問題を克服するために、AGA（Adaptive Genetic Algorithm）の各個体にデフォルトの突然変異確率値（0.005）を導入しました。

既存の文献では、Pcは0.5<Pc<1.0で、Pmはより小さい値を取ることが望ましいことが明らかにされています0.001<Pm<0.005。これは、一般的な遺伝的アルゴリズム（SGA）の成功に必要な尺度です。Pcの値は、幅広い交差を促進できます。Pmの値は、個体が破壊されるのを防ぐことです。ただし、PcとPmの値が変わらない場合、この方法は有効です。

このアプローチの目標の1つは、GAが局所最適解に陥ることを防ぐことです。このために、平均適応度以下の個体を使って、最適解を含む空間を探索する。この個体のように、完全に乱す必要があり、この目的で、k4の値を0.5にします。Favgの適応度の個体も完全に乱す必要があり、K2も0.5を与えます。

同様の推論に基づいて、K1とK2の値が1.0になるようにします。これにより、Favg以下のすべての個体が交差を行います。交差確率は、適応度（親個体の適応度最大のもの）がFmaxに近づくことにより小さくなります。そしてこの確率は、Fmaxに等しい個体に対して、0.0になります。

まとめ

AGAは交差確率pcと変異確率pmが適応度により変わります。Fmax-Favgがどんどん小さくなり、PcとPmが大きくなります。

個体ごとの交差と変異確率がそのものの適応度により線形的な変化を行います。適応度の高い (FかF') 個体はFmax-F かFmax-F' の値が小さく、いい個体が保存しやすいです。適応度(FかF')の低い個体はFmax-FかFmax-F'の値が大きくなります。

上記で0の場合はいい個体を保存できますが、交差変異確率も0になって、前に保存された個体が指数的に増殖し、早期収束になります。なので、k2=0.5、k4=0.5で適応度が平均値以下の個体で最適解を探索します。ちなみに、k1=1.0、k3=1.0をお勧めします。

参考記事

https://blog.csdn.net/zyqblog/article/details/59109703

中国語で書かれたblogなんですが、勉強して翻訳しました。