サロゲートアシスタントモデルによる人工免疫アルゴリズム Opt-IA の改善
阪中裕子

1(指導教員：Aubert-Kato Nathanael)

はじめに

3.4

本研究では人工免疫アルゴリズム Opt-IA 内で使われる評価関数呼び出し回数を削減し, 早い段階で最適解に到達することを目指す. 4 つの手法を検討したが, 本
稿では主にサロゲートアシスタントを適用した Opt-IAについての提案手法とその効果についてのベンチマー
クテスト及び検討を示す.

2

Opt-IA の概要と問題点

Opt-IA は脊椎動物の免疫細胞の一つである B 細胞を参考に構築されており, 各個体は B 細胞をモデルとした振る舞いをする. そのため Opt-IA では解の候補である各個体を B 細胞と呼び, B 細胞は適応する問題に対する解の候補, 年齢, 評価値をパラメータとして持つ. B 細胞の集合体に対して各世代において生成,クローン, 超突然変異, エイジング, 選択のサイクルを繰り返すことによって, 解の候補を最適解に近づける.
Opt-IA については, 先行研究 Cuttelo ら [1] や Corus
ら [2] によって示されており, 本研究では Corus らによるハイブリッドエイジングを使用した Opt-IA[2] を参考に, 従来型 Opt-IA を定義する. ただし FCM は使用しない.
Opt-IA は同時に複数の解を保持できることや, エイジングにより多様性を維持し, 局所解脱出の可能性を高める利点があるが, 計算量の多い評価関数の呼び出しが個体数に応じて増加するという問題点がある。世代あたりの評価関数呼び出し回数を k とした場合, 総呼
び出し回数は k × t × P opSize となり個体数に比例して呼び出し回数が増加する。また, ベンチマークテス
トの結果, 他アルゴリズムに比べて局所解脱出能力が十分とは言えず改善の余地があると考えられた。

3

提案手法

3.1

ResetAge 型: Best 個体年齢のリセット

図 1. サロゲートアシスタントを使用した Opt-IA の流れ. 赤部分が提案手法による変更部分

まずサロゲート関数を使用して評価値を予測する. B細胞 x に対する評価関数による評価値を feval (x), サロゲート関数に対する予測値を fsrg (x), 予測偏差を d としたとき, d < γ ∧ fsrg (x) < f (xbest ) を満たす場合にfsrg (x) を採用する. また実験の終了条件に有限性を持たせるため t > 50000 以降はサロゲート関数による予測値を使用しない. 条件を満たさない場合には評価関数を呼び出し実測値を得る. 得られた実測値は配列に保存しサロゲート関数の再トレーニングに使用する.

従来型 Opt-IA では Best 個体の年齢が増加した場合に Best 個体が廃棄され, 解が後退してしまうことがあった. Best 個体のみ毎世代年齢を 0 にリセットすることで解の後退を防ぐ.

3.2

Surrogate 型: サロゲートアシスタントの導入

計算量の多い評価関数の呼び出し回数を減らすために, 計算量の少ないサロゲート関数 (代理関数) を用意し, 可能な限りサロゲート関数を使用することで全体の計算量を減らす. 解の候補が生成または変異したときのみ評価関数が呼び出されることを前提とすると, 評価関数が呼び出されるのは初期個体生成, 超突然変異, 及び選択の個体集団の個数が少なかった場合である.
本研究の提案手法では超突然変異と選択においてサロゲートアシスタントを導入する. サロゲート関数には
skikit-learn ライブラリよりガウス過程による教師あり機械学習関数 Gaussian Processes を使用し, 既に呼び出された評価関数による評価値を使ってサロゲート関数をトレーニングし, 計算結果を評価関数に近づける.
適切なトレーニングのため, 初期個体の生成には sobol型を併用し, トレーニングは超突然変異集団の評価前に行なうこととする. 評価関数が呼ばれた場合,

Sobol 型: Sobol 列の使用

初期個体はランダムで生成されるが偏りが出てしまう可能性は否めない. 一様分布列の一つである sobol列を用いて初期個体の生成を行い, 初期世代時点での個体の偏りを無くし, 局所解に陥る可能性を減らす.

3.3

Search 型: 履歴による未探索空間の探索

Opt-IA における世代数が上昇すると解の最適化が進み個体の多様性に減少傾向が見られる. 探索済み空間の履歴を保存し, Best 解の更新が一定世代行われずかつ未探索空間があるなどの条件を満たす場合には未探索空間の個体を追加する.

図 2. サロゲートアシスタント導入方法

4

実験結果と考察ベンチマークプラットフォーム COCO[3] を使用して従来型 Opt-IA を Normal とし, Normal, Sobol, 及51

他手法を下回る結果となった.

び Sobol 併用の, ResetAge, Search, Surrogate 型の比較実験を行なった. ただし Search は 2D まで. Trap
function を含む 24 種類の目的関数に対し最小値探索を行ない, 1 関数につき 15 試行した. 評価関数の呼び出
し回数上限値は budget × dimension であり, budget =50000 としトレーニングのための実測値の保存はメモリの都合上 500 までとした.

4.1

全体の結果

図 3 は 24 種類の全ての関数に対する結果を次元ごとに, 102 ∼ 10−8 間の 51 の標本値について ECDF(経験累積分布関数) グラフで表したものである. 横軸 10 ∼104 あたりで僅かに Surrogate が上回っているが全体的にはそれほど差はない結果となった. 前半から横軸 4付近までは Surrogate の優位が見られ, その後失速している. トレーニングのための実測値の保存を 500 で制限したことや, 初期個体数が 20 であることからサロゲート関数のトレーニングに十分なサンプルが得られなかった事による問題があると考えられる.

図 5. 7:Step-elipsoid(上), 19:Griewank-Rosenbrock F8F2(下)関数での関数ごとの結果. (左)2D, (右)3D

4.4

その他手法優位

図 6 は ResetAge と Search について優位性が見られた関数別の結果である. (左)Elipsoid separable に対する結果では最終的に ResetAge が優位性を示す可能性が, (右)Lunacek bi-Rastrigin に対する結果ではSearch が最終的に優位性を示す可能性がある.

図 3. 全 24 関数での結果. (左)2D, (右)3D. 横軸は評価関数の呼び出し回数を次元で割ったものを底 10 の対数表記で表したもの. 縦軸が精度を表しており 0.2 ならば 20%問題が解けている.

4.2

図 6. 3D, 19:Elipsoid separable(左), 2D, 24:Lunacek biRastrigin(右) ごとの結果.

サロゲート優位

図 4 は関数ごとの結果のうち Surrogate が優位となった Sphere や Linear Slope 関数についての結果である.
少ない評価関数呼び出しで最適解に到達できるというサロゲートアシスタント導入の効果を確認できた.
Sphere や Linear Slope においてより良い結果が得られたのはこの 2 関数が他の関数に比べ単純構造であることも要因の一つとして推測される.2D, 3D 共に, 従
来型 Opt-IA や他の手法に比べて Surrogate が速く最適解に迫っていることがわかる.

5

サロゲートアシスタントモデルを含む複数の手法を人工免疫アルゴリズム Opt-IA に適用し, 従来型 OptIA と比較検討した. ベンチマークテストの結果特定の関数に対してサロゲートアシスタントの効果が見られた. 今回 budget = 50000 として, 2D の場合は 100000呼び出しまでの結果しか得られていないので, より確たる結果を得るためには 500000 < budget の実験が必要である. 今後は評価関数の呼び出し回数上限を増やしての実験や, 多目的関数, 高次元でのベンチマークテ
スト, 個体数などの各種パラメータの調整, サロゲート関数の改良を行なってより効果の高いモデルを探りた
い. また, 数値的ベンチマークテストでは他アルゴリズムを凌駕する結果を得られなかったが, Opt-IA は同時に多様な解を保持できることから, より複雑な現実的問題に対して効果がある可能性があるため, 今後はそのような問題に対しても適用し, 提案手法の効果を検討していきたい.
参考文献

図 4. 1:Sphere(上), 5:Linear Slope(下) での関数ごとの結果.
(左)2D, (右)3D

4.3

まとめと今後の課題[1] V Cutello, G Narzisi, G Nicosia, and M Pavone. In International Conference on Artificial Immune Systems, pages
13–28. Springer, 2005.
[2] D Corus, P S Oliveto, and D Yazdani. In Proceedings of theGenetic and Evolutionary Computation Conference, pages
83–90. ACM, 2017.
[3] N. Hansen, A. Auger, O. Mersmann, T. Tušar, andD. Brockhoﬀ. ArXiv e-prints, arXiv:1603.08785, 2016.

サロゲート劣位

図 5 は関数ごとの結果のうち Surrogate が劣位となったものの一部を抜粋した結果である. スタートから 104あたりまでは僅かに上回っているが, その後従来型や52