実験計画法における多目的遺伝的アルゴリズムの利用（NSGA-II）

はじめに
実験計画法から多目的最適化へ
多目的遺伝的アルゴリズム(NSGA-II)の流れ
- ①適応度評価と②適者生存
- ③親選択と④突然変異
参考書
具体例
- NSGA-IIの実装
まとめ

はじめに

目的変数が複数あり「すべての目的変数を最適化するような要因の値（水準、パラメータ）を見つける」必要があるシチュエーションがあります。それを多目的最適化と言います。

本記事では、この多目的最適化を実行する方法の一つである、多目的遺伝的アルゴリズムNSGA-IIについてまとめました。

実験計画法から多目的最適化へ

簡単に状況を説明させてください。図1に示すように、要因A,B,C,....からなる実験を行い、その結果から目的変数Y1, Y2, Y3を予測するためのモデル（数式）を構築します。

今注目しているのは、モデルを作った後、これらの複数の目的変数を最適化するための要因(A,B,C,...)の値はいくつか？ということです。目的変数によっては最大化だけでなく、最小化や、ある値に近づけるなど別々の最適化が必要な場合もあります。

図1 実験計画法から多目的最適化。※実験は別に実験計画法でなくてもいいし、モデルは数式で示されるようなものでなくても、AIのようなブラックボックスの関数でもいい。

さらに厄介なのが、複数の目的変数間にトレードオフの関係がある場合です（図2）。このような場合、Y1を大きくするための組(A1,B1,C1,...)とY2を大きくするための組(A2,B2,C2,...)が異なるため、同時に2つの目的変数を最大化する唯一の解(A,B,C,...)はありません。

そのため、図2の青線がY1とY2の両方をできるだけ最大化する解の集団となり、これをパレート解と呼びます。このパレート解を求める1つの手段が、多目的遺伝的アルゴリズムというわけです。

多目的遺伝的アルゴリズム(NSGA-II)の流れ

多目的遺伝的アルゴリズムと言っても色々あるようですが、ここではよく使用されているNSGA-IIという手法を説明します。図3にアルゴリズムの概要を示しました。

大まかな流れとしては、

⓪ 水準値の組をたくさん生成します（初期集団生成）

① 各水準の良し悪しを評価し（適応度評価）

② 優れている解のみを残します（適者生存）

③ 残った解からランダムにペアを作り（親選択）

④ 新たな点を生成します（子生成）

①から④の操作を、パレート解の変化が小さくなるまで繰り返します。上の図3左に示したのは2つの目的変数Y1, Y2を両方最大化する場合で、世代を更新していくことでパレート解が右上に上がっていく様子を示しています。

①適応度評価と②適者生存

①適応度評価と②適者生存についてもう少し説明しましょう。①適応度評価はある時点での集団に対して行います（前世代の親とその子集団です）。ある点が他の点より目的変数Y1, Y2の値に関して優れているかどうかで、下の図4のようにランキング（1,2,3,...）を付けます。図4の各点は、ある水準（Ai, Bi, Ci, ...）であり、その水準におけるY1, Y2の値は実験結果から作ったモデル式で予測します。

また、②適者生存ではランキング上位の点を残し、下位の点を除外します。このとき、次の世代に渡す個体数には数に限りがあるので、ぎりぎり足切のラインにいる個体たちは、条件的に近い点が残らないように、混雑距離（近接点との距離）が小さな距離を除外するようにします。

③親選択と④突然変異

③親選択は適者生存で残った個体からランダムに親を決めることを意味します。④交叉・突然変異はその親同士の中間的な個体を作ることを意味します。

参考書

さらに詳しく知りたい方は以下の参考書を読んでみてください！Amazon kindle unlimitedなら0円です（笑）。すごい時代ですね...

ゼロから始める多目的設計最適化 0 多目的設計最適化とは？

kindle

ゼロから始める多目的設計最適化 1 多目的設計最適化問題を解く

kindle

ゼロから始める多目的設計最適化 2 基本となる設計最適化手法

kindle

ゼロから始める多目的設計最適化 3 進化アルゴリズム

kindle

ゼロから始める多目的設計最適化４多目的進化アルゴリズム（１）

kindle

具体例

図6のシチュエーションを想定します。

実験結果から立てた目的変数Y1とY2が、要因A,Bを使って以下のモデル式で表されるとしましょう。

Y₁=2+A+B

Y₂=4−A−B

上式で、A+Bが大きくなるほどY1は大きくなるのに対し、Y2は小さくなるので、Y1とY2にはトレードオフの関係があります。では、Y1とY2の両方をできるだけ大きくするためには(A,B)の水準値はどうすればよいでしょうか？

NSGA-IIの実装

NSGA-IIを使ってこの問題を解きます。多目的最適化はPythonのPlatypusというライブラリで行うことが出来ます。以下にコード例を示します。

from platypus import NSGAII, Problem, Real, nondominated

#y1とy2を返す関数
def func(x):
    A = x[0]
    B = x[1]
    y1=2+A+B
    y2=4-A-B
    return [y1, y2]

problem = Problem(2, 2) #説明変数が2個(A,B), 目的変数が2個(y1, y2)
A = Real(-1, 1)　#説明変数の定義 -1 < A < 1  
B = Real(-1, 1)
problem.types[:] = [A,B] #説明変数の指定 
problem.function = func
problem.directions[:] = Problem.MAXIMIZE #最大化問題 
algorithm = NSGAII(problem, population_size=20) #1世代の個体数
algorithm.run(1000) #世代数(計算のサイクル数)

以上のコードでNSGA-IIによる最適解の探索が行われます。実行が終わったら、解の図示をしてみましょう。次のコードで実行します。

from matplotlib import pyplot as plt
nondominated_solutions = nondominated(algorithm.result)# 非劣解
fig, ax = plt.subplots(figsize=(6,4))
for i in range(len(nondominated_solutions)):
    x = nondominated_solutions[i].objectives[0]
    y = nondominated_solutions[i].objectives[1]
    ax.scatter(x,y)
    ax.annotate(i, xy=(x,y), size=10)
ax.grid()
ax.set_ylabel("y2")
ax.set_xlabel("y1")
plt.show()

図7には各点に番号を振りました。各点の(A, B)がどうなっているかは次のコードで確かめることができます。

import pandas as pd 
res = pd.DataFrame(columns = ("A", "B", "y1", "y2"))
for i in range(len(nondominated_solutions)):
    A, B = [round(a,2) for a in nondominated_solutions[i].variables[:]]
    res.loc[i] = [A, B, nondominated_solutions[i].objectives[0], nondominated_solutions[i].objectives[1]]
display(res)