実数値遺伝的アルゴリズム実装ざっくり説明

はじめに

以前の記事で実数値GAのざっくり説明を行いました。
次はPythonで実装した実数値GAを、ざっくり説明したいと思います。
実装コードはこちら

注意

• 計算効率は考慮していません
  • クラス化するよりnumpyのarrayで個体群を表現したが早いです¹
• 評価関数(クラス)などを追加すればそれなりに柔軟に使えるのではないかと思います²
• クラスの命名などは社会の縮図っぽくしてみました
  • 個体(indivisual)が社会に属し、社会がもつ評価で評価され、社会による選択をされ…うーん、社会の縮図

想定読者

• 最適化問題に興味がある
• 実数値GAの実装と動作ってどんなもんよ？という方

実装

ファイル構成などはREADME.mdを参照下さい。
原理は単純で、

1. 評価関数を決める
   • 遺伝子長(次元数)
   • 評価関数の種類
2. 個体のリスト(集団)を生成
   • 集団の個体数を決める
   • 初期個体を生成する
3. 最適解を見つけるまで、などといった条件で以下を繰り返す
   1. 親個体を集団から選択
   2. 選択した親個体から子個体を生成
   3. 次世代に残す個体を集団に追加、残さない個体を集団から削除する

上記に関して、コアとなる実装部をざっくり説明していきます。

実装説明の前に

実数値GAでは、以下の組み合わせにより、性能が変わります。

• 親の選択
• 交叉方法
• 次世代に残す個体
  そのため、demoでは使っていませんが、それぞれ2パターンくらい実装しています

個体表現

個体はIndividual クラスで表現しています。
Individualに実数値のリスト(遺伝子)_geneとその評価値evaluate_valueを持っています。
_evaluatorは遺伝子の評価を行うEvaluator内で設定しているため、先にEvaluatorのインスタンス化が必要になっています。

Individual.pyの一部

class Individual(object):

    _evaluator = None

    def __init__(self, gene):
        # 遺伝子を表す
        self._gene = np.array(gene)

        # 遺伝子を評価した値
        self._evaluate_value = Individual._evaluator.evaluate(self)

交叉

交叉はBLX_alphaとSimplexの2種類を作成しています。
詳細な式は以下を参照頂ければ。
http://www.sist.ac.jp/~kanakubo/research/evolutionary_computing/lbx_spx.html

ざっくりとした説明をすると以下の様な交叉方法になります。

• BLX_alpha
  • 親として2個体を選択して子個体を生成
  • 生成範囲はSimplexよりも広い傾向
• Simplex
  • 親として(遺伝子長+1)個体を生成して個体を生成
  • BLX_alphaに比べて親個体に近い範囲で子個体を生成

交叉によって生成される子個体の分布はsample_plot.pyのコメントアウトを外してpython sample_plot.pyと実行すれば3次元空間プロットが表示されます(要matplotlib)。

以下に親個体と子個体の遺伝子の分布の画像を示します。
親個体を赤、子個体を青として3次元空間でプロットしています。

BLX_alpha

Simplex

交叉の分布を見て頂ければ、それぞれ親個体の分布よりも広い範囲に子個体が生成されている事がわかります。そのため、実数値GAでは突然変異を明示的に実装する必要がない、とされている様です(事実、突然変異を実装する事なく大域最適解を発見できます)。

選択

個体の選択には以下の2種類があり、それぞれ2パターンずつ作っています。

• 親となる個体(=交叉として使用する個体)の選択 (individual_selector.pyに定義)
  • 評価値を考慮した割合で選択するルーレット選択(RouletteSelector)
  • 評価値の良い個体から選択するエリート選択　EliteSelector
• 次世代に残す個体の選択(generation_selector.pyに定義)
  • 親となった個体+生成した子個体からエリート選択+ルーレット選択した個体を入れ替え(MGG)
  • 親となった個体と、生成した子個体からエリート選択した個体を入れ替え(JGG)

次世代に残す個体の選択ですが、JGGでは評価値の良い個体を選択するため、収束しやすい半面、局所解に陥る可能性があります。

実行コード

実数値GAを実行するコア部分を表示します。
設定は以下の様になっています。

• 遺伝子長(次元数):30
• 個体数(集団数)：300 (次元数 * 10)
• 世代数(交叉回数)：1000

sample_main.pyの一部

def demo_1():
    # 遺伝子長
    dimension = 30

    # 集団数
    individual_num = 300

    # 世代数の最大
    generation_loop = 1000

    # 評価関数
    evaluator = Sphere()

	# ここで集団(society)の設定を行う。引数は以下
	# 評価関数. 交叉方法, 親の選択方法, 次世代に残す方法
    society = Society(
        evaluator,
        Simplex(dimension * 10),           # 生成する子個体の数を引数とする
        RouletteSelector(dimension + 1),   # 選択する親子体の数を引数とする
        JGG())

	# 個体の初期化を行うクラス。遺伝子の上限、下限、遺伝子長を引数とする
    generator = Generator(10., -10., dimension)

    # 初期個体の生成
    society.generate_individuals(individual_num, generator)

    # 遺伝的操作を行う
	# change_generationは内部的には以下の流れを行う
	# 1. RouletteSelectorで親を選択
	# 2. Simplexで子個体を生成
	# 3. JGGで親と入れ替える子個体を選択
	# 4. 親となった個体と選択された子個体を入れ替える
    for i in range(generation_loop):
        society.change_generation()

デモ

デモとして以下3パターン用意しました。
sample_main.pyのコメントアウトを外してpython sample_main.pyと実行すれば動作をします。

デモはそれぞれの以下の様になっています。

• demo_1
  • Sphere関数に対してSimplex+JGGの組み合わせで実行
• demo_2
  • Rosenbrock関数に対してSimplex+JGGの組み合わせで実行
• demo_3
  • Rosenbrock関数に対してBLX_alpha+JGG,Simplex+JGGの組み合わせで実行

demo_1、demo_2を実行すると、評価値の推移と遺伝子の推移を見ることができます。
demo_3を実行すると、BLX_alphaとSimplexの評価値の推移を見ることができます。

demo_2に関して、世代と遺伝子の分布の変化を示します。世代が進むにつれ、遺伝子の値が0(最適解)に近づいていく動きを見ることができます。

最後に

実数値GAについてサンプルコードを実装してざっくり説明をしました。
実数値GAは選択と交叉の組み合わせ、また交叉そのものに性能が左右されるため、実数値GAを使って最適化問題を解くときは注意が必要です。

また、生物の進化云々ということで、Individualに性差など追加しても研究としては面白いのではないかと思います。³

---

参考文献

https://www.jstage.jst.go.jp/article/tjsai/16/1/16_1_147/_pdf
http://sysplan.nams.kyushu-u.ac.jp/gen/edu/Algorithms/RGA_JGGandREX/RGA_JGG_REX.pdf

---

1. そもそもダックタイプできるからクラス化する必要もないですし ↩

2. 作ったあと調べた所、C#実装ですが実数値GAを含む数値最適化のライブラリがありました(^p^): https://github.com/tomitomi3/LibOptimization ↩

3. そういった研究(?)を学生の時にしていましたが、全然結果でなかったのはいい思い出(ﾎﾛﾘ ↩