はじめよう実験計画

実験を早く終わらせるための技術

実験計画法における多目的遺伝的アルゴリズムの利用(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,...)が異なり、同時にふたつの目的変数を最大化する唯一の解(A,B,C,...)はありません。

そのため、図2の青線上の各点がY1とY2の両方をできるだけ最大化する条件を示す解の集団となり、これをパレート解と呼びます。最適化の目標は、このパレート解をできるだけ右上に持ち上げていくことにあります。

図2 トレードオフの関係とパレート解

図2のようなトレードオフの関係がある場合、ただ一つのベスト解(A,B,C,...)が存在しないため、トレードオフの限界の線(パレート解)を求め、その線上の点から解を選ぶ必要があります。

そして、そのパレート解を求める手段が、多目的遺伝的アルゴリズムというわけです。

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

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

図3 多目的遺伝的アルゴリズムの流れ

大まかな流れとしては、

  • ⓪初期集団生成(A,B,C,...)=(-1, 0, 1,...), (1, -1, 0.5,...) のような水準群
  • ①適応度評価
  • ②適者生存
  • ③親選択
  • ④子生成(交叉・突然変異)

です。まず、⓪で水準値の組をたくさんランダムに作成します。その水準群で、どの点が優れているか①で評価し、②で優れている解のみを残します。③残った点をランダムにペアにして④新たな点を生成します。こうして新しい世代の水準群が得られ、①に戻る。という操作を、パレート解の変化が小さくなるまで、繰り返します。先の図3に示したのは2つの目的変数Y1, Y2を両方最大化する場合です。世代を更新していくことでパレート解が右上に上がっていく様子が分かります。

図3の①適応度評価と②適者生存について、下の図4でもう少し説明します。

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

①適応度評価は前の世代の親と子(水準群)に対して行います。図4のプロットのように、ある点が他の点より目的変数Y1, Y2の値に関して優れているかどうかでランキングを付けます。Y1, Y2がどんな値になるかは実験結果から作ったモデル式で予測します。

次の世代に渡す個体数には数に限りがあるので、ぎりぎり足切りされてしまう個体たちは、混雑距離という考え方で、似たような点が残らないようにします。

 

次に、③親選択と④突然変異の考え方を下の図5にします。

図5 ③親選択と④交叉・突然変異。子は親同士の中間的な水準値になる。

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

詳細を知りたい方は以下の参考書をお読みください。Amazon kindle unlimitedなら0円です。

 

実装例

それでは、具体的に多目的遺伝的アルゴリズムNSGA-IIの実装を行います。ここでは、目的変数Y1とY2が要因A,Bによって以下の式で表されると仮定します。

Y1=2+A+B

Y2=4−A−B

これは、実験結果から立てたモデル式だと思ってください(図6)。A+Bが大きくなるほどY1は大きくなるのに対し、Y2は小さくなるので、Y1とY2にはがっつりトレードオフの関係があります。

では、Y1とY2を両方とも大きくするために(A,B)の水準値はどうすればよいでしょうか?

図6 例

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

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 パレート解の図示

図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)

表1 パレート解の出力

表1と図7を見比べることで、どの(y1, y2)が良いか吟味し、そのときの(A, B)の水準値を知ることができます。

 

NSGA-IIを使う際は、本当は色々なパラメータを調整する必要があるかもしれません。Githubのコードを直接見てみると良いかもです。自分は世代数や個体数等をチョコチョコと変えてみて、解の変化がなければ良しとしてます...怒られそう(笑)。

github.com

 

まとめ

本記事では、実験計画法でモデル式を立てた後、複数の(トレードオフの関係がある)目的変数を最適化するNSGA-IIの紹介をしました。また、パレート解を与える解の水準値の組を出力するところまで実装しました。

もちろん、多目的遺伝的アルゴリズム以外にも、多目的最適化の手段はあります。実験計画法では満足度関数という方法がありますので、いつか説明できればと思います。