遺伝的プログラミングによる実数値交叉の性能差を強調する探索空間の生成 白川 真一 † , 矢田 紀子 † , 長尾 智晴 † 横浜国立大学 大学院環境情報学府 † , 1 はじめに 進化計算法に代表されるメタヒューリスティク ス探索法は，これまでに様々な手法やその改良法が 提案され，種々の問題領域に対して有効性を示し ている．特に，実数値関数の最小値または最大値 を求める関数最適化問題に対しては，様々なアプ ローチが試みられている．進化計算法による関数 最適化問題に対する代表的な手法としては，実数 値GA（Real-coded Genetic Algorithm; RCGA）1) ，Covariance Matrix Adaptation Evolution Strategy（CMA-ES）2) ，Particle Swarm Optimization （PSO）3) ，Differencial Evolution（DE）4) な ど が挙げられる．このような進化計算法の探索性 能を評価する際には，典型的なベンチマーク関 数 に 適 用 し ，他 の 手 法 と の 比 較 実 験 に よって そ の 手 法 の 性 能 を 評 価 す る こ と が 多 い ．し か し ， 複数のベンチマーク関数に対する手法の差異が 微 少 で あった 場 合 ，そ の 手 法 に ど の よ う な 特 徴 があるのか理解することは難しい．また，実験 に用いていないベンチマーク関数や他の実問題 に対しての性能は明らかではない．一方で，理 論的に進化計算法の挙動を解析する研究も行わ れているが，複雑な進化計算法を理論的に解析・ 理解する こ と は困難な場合も多く存在する． このような状況に対して，2 つの進化計算法の 性能差を大きくするような探索空間を進化的に 生成する研究が行われている．Oltean は設定を 変えたシンプルな 2 つの (1+1)ES の性能差が大き くなるような1次元の実数値の探索空間の生成 と，ランダムサーチが突然変異だけを用いる進 化計算法よりも性能が高くなるようなバイナ リ の 探 索 空 間 の 生 成 に 成 功 し て い る 5) ．ま た ， Generation of Search Spaces to Emphasize Performance Difference of Real Coded Crossovers Using Genetic Programming † † † Shinichi Shirakawa ([email protected]) Noriko Yata ([email protected]) Tomoharu Nagao ([email protected]) Graduate School of Environment and Information Sciences, Yokohama National University (†) PSO や DE な ど の 性 能 差 を 大 き く す る よ う な 関 数最適化問題を遺伝的プログラミング（Genetic Programming; GP）6, 7) によって生成し，それを 進化計算法の性能解析に応用しようとする研究 が行われている 8) ．この研究では，PSO や DE の 性 能 差 を GP の 評 価 関 数 と し ，{+, −, ×, ÷} の 演 算の組み合わせによって表現される探索空間を 生成する．それによって，ある進化計算法が他の 進化計算法に探索性能が勝る（または劣る）探 索空間の生成に成功している． 本報告では，実数値 GA に着目し，中でも交叉 の違いによる性能差を利用して探索空間の生成 を行う．実数値 GA に対しては様々な交叉が提案 されており，それぞれに特色がある．また，“機 能 分 担 仮 説” や “統 計 量 の 遺 伝” な ど の 設 計 指 針 9, 10, 11) に よ り，世 代 交 代 モ デ ル と 交 叉 の 役 割 が明確である．本報告の実験で行う探索空間の 生 成 に は ，ネット ワ ー ク 構 造 を プ ロ グ ラ ム の 表 現形式とする GP の一つである Cartesian Genetic Programming（CGP）12) を 用 い る ．さ ら に ，探 索空間の生成の際の目的関数を性能差と CGP の ノード数の 2 つに拡張し，多目的進化アルゴリズ ムによって複数の探索空間を同時に生成するこ とを試みる．最後に，ランダムな個体生成法の ほうが実数値交叉より性能が高くなる探索空間 の生成を行う． 2 つの進化計算法間の性能差を強調する探索空 間をGPによって生成することで，アルゴリズムの 違い（本報告では交叉の違い）とその探索への影 響を理解する手助けになることを期待している． 2 実数値交叉の性能差を強調する探索空間 の生成法 本報告では，実数値交叉の性能差を強調する 探 索 空 間 を GP に よって 生 成 す る ．本 報 告 で の 探索空間の生成法の概要図を Fig. 1 に示す．GP の各個体（プログラム）は探索空間を表す関数 （数式）に対応している．実験では交叉を変えた 2 つの実数値 GA の性能差を GP の評価関数とし， Table 1 探索空間の生成実験に使用する CGP の 演算ノード. Mark + − × ÷ Fig. 1 実数値交叉の性能差を強調する探索空間 の生成 法 の 概 要図． | | sin cos 0.0 1.0 10.0 −1.0 π #Arg(s) 2 2 2 2 1 1 1 0 0 0 0 0 Definition x1 + x2 x1 − x2 x1 × x2 x1 ÷ x2 (if x2 = 0.0 return x1 ) |x1 | sin(x1 ) cos(x1 ) Constant value 0.0 Constant value 1.0 Constant value 10.0 Constant value −1.0 Constant value π その性能差を大きくするような探索空間の生成 を行う．このようにして探索空間を GP によって 生成することで，ある実数値交叉がどのような な る が ，接 続 の 状 態 に よって 使 用 さ れ る ノ ー ド 探索空間に対して性能を発揮するのかを調べる （active node）と 使 用 さ れ な い ノ ー ド（inactive ことができる．実験では特に，探索空間の景観 の把握が容易な 2 次元の探索空間の生成を行う． node）が存在するため，表現上はノード数は可 つ ま り，GP の 各 個 体 は 2 つ の 入 力 値 (x, y) か ら ， 変となる．CGP の遺伝操作には通常，突然変異 だ け が 用 い ら れ る 12) ．突 然 変 異 は 突 然 変 異 率 ある適応 度 f を 返す関数を表すことになる． Pm によって遺伝子単位で発生する． ま た ，本 報 告 で は GP の モ デ ル と し て ，ネッ Table 1 に本報告で用いる CGP の演算ノードの トワーク構造をプログラムの表現形式とする 一覧を示す．CGP の演算ノードには四則演算を Cartesian Genetic Programming（CGP）12) を 採 中心に比較的単純なものを用いたが，これらを 用する．CGP の各プログラムはフィードフォワー ド型のネットワーク構造で表現され，入力ノード， 組み合わせることで様々な探索空間を表現する ことができると考えられる． 演 算 ノ ー ド，出 力 ノ ー ド か ら 構 成 さ れ る ．入 力 CGP の各個体の評価の際には，その個体が表 ノードはプログラムへの入力値が対応し，出力 2 つの交叉を用いた実数値 す探索空間に対して， ノ ー ド か ら プ ロ グ ラ ム の 出 力 値 を 得 る ．フィー GA をそれぞれ複数回適用する．その探索結果の ド フォワ ー ド 型 の ネット ワ ー ク 構 造 を 採 用 す る 違いを基に CGP の各個体の評価を行う．本報告 利点としては，ノードの再利用が可能となるこ で用いた CGP の各個体の評価関数 Fcgp は次の式 とが挙げられる．CGP では表現型のネットワー で定義される． ク 構 造 を 遺 伝 子 型 に マッピ ン グ し ，遺 伝 子 型 に 対 し て 遺 伝 操 作 を 行 う．こ こ で ，各 ノ ー ド に は N T 1 g1 (t, n) Fcgp = log , あらかじめ番号が振られているものとし，入力 N g2 (t, n) n=1 t=1 ノード，演算ノード，出力ノードの順に番号が割 ⎧ ⎪ if fi (t, n) < fmin り当てられる．入力元として選択できるノード ⎪ ⎨fmin を，自分のノード番号より小さい番号に制限す (1) gi (t, n) = fmax if fi (t, n) > fmax ⎪ ⎪ ⎩ る こ と で ，フィー ド フォワ ー ド 構 造 を 実 現 し て fi (t, n) otherwize いる．CGP の遺伝子型は各ノードの種類，接続 こ こ で ，N は 各 実 数 値 GA の 総 試 行 回 数 ，T は 元を記述した一次元の文字列で表現される．遺 最大世代数， fi (t, n) は探索の n 回目の試行の t 世 伝子型から表現型に変換する際，ノードの種類 代目における最良評価値である．gi (t, n) の値は によっては接続元の遺伝子が表現型に発現しな [fmin , fmax ] の範囲に制限されており，g1 と g2 は異 い 場 合 も あ る ．CGP の 全 ノ ー ド 数 は あ ら か じ なる設定の実数値 GA1，2 の探索からそれぞれ得 め指定するため，染色体の遺伝子長は固定長に ら れ る 値 で あ る ．実 験 で は ，N = 10，T = 500， Table 2 実験 に用いた CGP の各パラメータ値． Parameter Number of generations Mutation rate Pm Number of arithmetic operation nodes Number of input nodes Number of output nodes Value 15000 0.02 200 2 1 に，このときにも探索点の移動が起こるが，そ の際には適応度計算を省略することができ る ． 3.1.2 実数値 GA の設定 実験では交叉を変えた 2 つの実数値 GA の性能差 を利用して探索空間の生成を行う．実数値交叉とし ては，BLX-α 14) ，単峰性正規分布交叉(Unimodal Normal Distribution Crossover; UNDX) 15) ，シン プレクス交叉（Simplex Crossover; SPX） 16) の 3 つを使用し，6 通りの組み合わせに対して探索空 fmin = 10−8 ，fmax = 10.0 と し た ．こ の 評 価 関 数 間の生成を行う． Fcgp は各世代で得られる 2 つの実数値 GA の最良 BLX-α は ，2 親 に よって 定 ま る 各 変 数 の 区 間 評価値の log 値の差を累積したものである．つま をα倍拡張してできる超直方体内に子個体を一 り，探 索 の 過 程 も 性 能 評 価 の 対 象 と なって い る 様 乱 数 に よって 生 成 す る 交 叉 で あ る ．実 験 で は （より早く良い評価値を得るほうが性能が高いこ BLX-α のパラメータは α = 0.366 とした．UNDX と を 表 す ）．本 報 告 の 実 験 で は ，CGP が 表 現 す は変数間依存性へ対処することを目標に設計さ る探索空間に対してより小さい値を得ることが れた交叉である．UNDX では 3 つの親個体によっ できる変数を実数値 GA は探索することとする． て 決 ま る 正 規 乱 数 を 用 い て 子 個 体 を 生 成 す る ． そのため，gi (t, n) の値が小さいほど実数値 GA の 子個体は 2 つの親個体を結ぶ線分の周辺に正規分 性 能 が 高 い と み な し て い る ．Fcgp の 値 が 大 き い 布 に 従って 生 成 さ れ ，3 番 目 の 親 は 正 規 分 布 の ほど性能差が大きい探索空間であることを表す 標準偏差を決めるために用いられる．実験では （Fcgp の値が大きい程，その探索空間に対して実 UNDX の パ ラ メ ー タ は α = 0.5, β = 0.35 と し た ． 数値 GA1 より実数値 GA2 の性能が高いことを表 SPX は n を次元数としたときに，n + 1 個の親個 し て い る ）．こ の よ う な 評 価 関 数 を 用 い て ，2 体を頂点とする n 次元単体（simplex）に相似な単 つ の 実 数 値 GA の 性 能 の 差 が 大 き く な る よ う に 体内に一様分布に従って子個体を生成する交叉 CGP に よって 探索空間の生成を行う． である．実験では SPX のパラメータである拡張 √ 率 ε を ε = n + 2 とした． 3 実数値交叉の性能差を強調する探索空間 世 代 交 代 モ デ ル に は Minimal Generation Gap の生成実験 （MGG）17) を 使 用 し た ．MGG は 多 様 性 維 持 に 3.1 実験 の 設 定 優れたモデルであり，実数値 GA で広く使用され 3.1.1 CGP の設定 ている．実験で用いる MGG の各世代での手順は 実験で使用した CGP の各パラメータ値を Table 次の通りである． 2 に示す．CGP の世代交代モデルには (1+4)ES を 1. 個体集団から交叉に必要な親個体をランダ 使用し，世代交代の際に最良個体が複数存在し ムに選択する． た場合は，子個体を優先して選択する．CGP で は接続状態によって使用されないノードが存在 2. 交叉によって子個体を nc 個生成する ． す る た め ，遺 伝 操 作 に よって 適 応 度 の 変 化 が 起 3. 親個体 2 個体（交叉が UNDX の場合は主親 2 こらない場合が多く存在する（これは neutrality 個体，SPX の場合はランダムに 2 個体を選択 と呼ばれている 12, 13) ）．最良個体が複数存在し す る ）と 子 個 体 の 中 か ら ，最 良 個 体 と 適 応 た場合は子個体を優先して選択することで，適 度 の ラ ン キ ン グ に よ る ル ー レット 選 択 で 選 応度が上昇しなかった場合でも探索点の移動が 択された 1 個体を個体集団に戻す． 起こりうる．これによって，個体数の少ない単純 な世代交代モデルでも効率的な探索が行えると 実数値 GA のパラメータは各交叉で共通のもの 考えられ，実験的にもその有効性が示されてい を用いることとし，個体数を 30，子個体 生 成 数 る 12) ．さらに，CGP の個体表現と小さな確率の nc = 20，最 大 世 代 数 T = 500 と し た ．CGP の 各 突 然 変 異 を 用 い る こ と で ，active node に 変 更 が 個体が表現する探索空間は 2 次元であるため，こ ない遺伝操作が多く発生する．先に述べたよう のパラメータで十分な探索が行えることを予備 Table 3 10 回の試行で生成された探索空間の平 均評 価 値（括 弧内の数値は標準偏差）． BLX-α UNDX SPX BLX-α – – 7521 (1918) 7411 (2024) UNDX 4778 (1533) – – 2854 (1244) SPX 5463 (1473) 5911 (1284) – – 実験によって確認している．実数値 GA による探 索 範 囲 は [−10, 10] と し ，初 期 個 体 は こ の 範 囲 に 一様乱数によって生成する．また，交叉によって 範囲外に子個体が生成された場合は，境界上に 値を修正することとした．実数値 GA の探索過程 で fmin よ り 小 さ い 評 価 値 が 得 ら れ た 場 合 に は ， その世代で探索を打ち切る．式 (1) で CGP の評価 値を算出するために fmax を設定しているが，実 数 値 GA の 探 索 の 際 に は 適 応 度 に 上 限 を 設 け な い．さらに，各実数値 GA の探索を行う際には， 同一のシードを用いて乱数を初期化する．これ に よって ，同 じ 探 索 空 間 に 対 し て は 毎 回 同 一 の 評価を与えることができるようにしている．実 験は各交叉の組み合わせににつき 10 回の CGP に よる探索 空 間 の生成を行った． 3.2 実験 結 果 と考察 各設 定 で 10 回の試行を行って得られた探索空 間の評価値の平均を Table 3 に示す．表中の数値 は，各行の交叉を用いた実数値 GA が各列の交叉 を用いた実数値 GA よりも性能が高くなる探索空 間 を 生 成 し た 際 の 評 価 値 を 表 し て い る ．ま た ， 括弧内の値は標準偏差である．この表から，全 ての組み合わせに対して，2 つの交叉の性能差が 大きくなる探索空間の生成が行えていることが 確認でき る ． Fig. 2 は各交叉の組み合わせに対して 10 回の試 行で生成された探索空間のうち，最も評価値が 大きかった探索空間の景観を示したものである． 図中の探索空間の横軸は変数 x に，縦軸は変数 y に 対 応 し て い る ．ま た ，Table 4 は Fig. 2 の 探 索 空間に対して各交叉を用いた実数値 GA で 30 回の 探索を行った際の成功回数を示したものである． Fig. 2(a)，(b) は ，BLX-α が UNDX と SPX に そ れぞれ勝る探索空間の例である．どちらも多峰 性 の 探 索 空 間 で あ り，x の 値 だ け に よって 評 価 Table 4 Fig. 2 の探索空間に各交叉を用いた実数 値 GA を適用した際の成功回数（試行回数：30）． Fig.2 Fig.2 Fig.2 Fig.2 Fig.2 Fig.2 (a) (b) (c) (d) (e) (f) BLX-α 30 30 16 21 14 25 UNDX 11 17 27 30 28 19 SPX 9 20 15 26 24 24 値 が ほ ぼ 定 め ら れ る ．Fig. 2(a) の 探 索 空 間 で は x = 0 の付近で最小値を取り，(b) の探索空間では x が π の倍数の付近で最小値をとる．BLX-α は変 数間依存性がある探索空間で性能が悪化すると されているため，BLX-α が性能を発揮できる探 索空間として Fig. 2(a)，(b) のような変数間依存 性がない探索空間が生成されたと考えられ る ． Fig. 2(c) は UNDX が BLX-α に 勝 る 探 索 空 間 の 例である．この探索空間では評価値を大きく改 善するためには x と y の両方の変数を変化させね ばならず，変数間依存性がある探索空間 で あ る といえる．また，x ≈ −10 の付近で最小値を取る が，x = −10 では大きな値を取る．このため，境 界外に個体を生成し x = −10 の値を得ても最小値 を獲得することはできない．この探索空間で最 小 値 を 得 る た め に は ，x = −10 の 近 辺 に 個 体 を 生成する必要がある．そのため，変数間依存性 に 対 処 で き ，正 規 乱 数 に よって 個 体 を 生 成 す る UNDX の性能が高くなる探索空間であると考え ら れ る ．実 際 に 探 索 の 過 程 を 解 析 し た と こ ろ ， BLX-α を 用 い た 場 合 で は x = −10 の 境 界 上 に 多 くの個体が生成されてしまい，最小値を得るこ とができていなかった． Fig. 2(d) は UNDX が SPX に 勝 る 探 索 空 間 の 例 で あ る ．こ の 探 索 空 間 は 多 峰 性 で あ り， (x, y) = (−10, 10) で最小値となる． Fig. 2(e) は SPX が BLX-α に 勝 る 探 索 空 間 の 例 である．Fig. 2(e) では変数の範囲が [9, 10] の景観 を示している（x = y の直線から離れると値が大 きくなりすぎるため）．この探索空間は変数間依 存性があり，x = y で最小値となる． Fig. 2(f) は SPX が UNDX に勝る探索空間の例で ある．この探索空間では y = 0 付近に最小値を取 る領域が存在するが，一方その近傍には大きな 値の領域が存在している．また探索空間全体と (a) BLX-α performs better than UNDX (b) BLX-α performs better than SPX (c) UNDX performs better than BLX-α (d) UNDX performs better than SPX (e) SPX performs better than BLX-α (f) SPX performs better than UNDX Fig. 2 各 交叉間の性能差を強調する探索空間の例（横軸は変数 x，縦軸は変数 y を表す）． しては y の値が大きくなるほど小さな値を取る． 次に，生成された探索空間を表す関数につい て述 べ る ．Fig. 2(b) に示した探索空間の関数は 次の通り で あ る． f (x, y) = sin | sin(x)| − 10 (9 + sin(sin(10))) sin (sin(sin(10))) cos(y) +10 | sin(x)| (10 + cos(x)) + 10 − cos (10(10 + cos(x))) (2) ま た ，Fig. 2(f) に 示 し た 探 索 空 間 の 関 数 は 次 の 通りである． cos(x) + |10 + y| − y (3) f (x, y) = 20π − 8 + y このように，CGP によって生成された関数は複雑 なものもあれば，構成される要素の数が比較的少 ないものまで様々である．本節の実験では評価式 (1) を最大化するような関数の生成を行ったため， 一見理解が困難な関数が生成される場合もあっ た．次節では，関数を構成するノード数を目的 関数に追加し，多目的最適化を行うことで，様々 な探索空 間 を 一度の探索で得ることを試みる． 4 Table 5 多目的進化アルゴリズムによって生成 された非劣解の例． Function f = 10 − y f = |y − x| f = |y − x|0.25 f = |x(y − x)|0.25 f = |(y − x)(cos(x2 ) + x2 )| f = |(y − x)(cos(x2 ) + x2 )|0.25 多目的進化アルゴリズムによる探索空間 の生成実験 前節の実験では式 (1) だけを評価関数として探 索空間の生成を行った．そのため，複雑な関数が 生成される傾向が見受けられた．複雑な関数に なるほど性能差が拡大する探索空間が表現でき るようになるが，探索空間の特徴を理解するこ とが難しくなると考えられる．そこで本節では， CGP の評価関数にプログラム中で実際に使用さ れているノード数を加え，2 目的問題に問題を拡 張する．評価関数の一つ目には式 (1) を，二つ目 にはプログラムで実際に使用されているノード数 を用いる．つまり，式 (1) を最大化，プログラムで 実際に使用されているノード数を最小化するこ とを目的とする．最適化には多目的進化アルゴ リズムの Strength Pareto Evolutionary Algorithm 2（SPEA2）18) を用いる．SPEA2 では個体の支 配関係と密集度を用いて各個体の適応度を決定 する．また，アーカイブに優良個体を保持する ことで，エリートの保存を行う．CGP の各パラ メ ー タ 値 は Table 2 に 示 し た 値 を 用 い ，実 数 値 GA の各パラメータ値も 3.1 節で説明した値を使 用する．SPEA2 のパラメータとしては，個体数 を 5，ア ー カ イ ブ サ イ ズ を 20 と し た ．交 叉 に は BLX-α と UNDX を 使 用 し ，UNDX が BLX-α よ り 性能が高 く な る探索空間の生成を行う． Table 5 に多目的進化アルゴリズムによって得 られた非劣解が表す関数を示す．表から確認でき る よ う に ，ノ ー ド 数 が 多 く な る に 従って 性 能 差 が大きくなる．また，各関数には共通の要素が 含まれているのが確認できる．Fig. 3 に使用され ているノード数が 6，7，10 の場合の探索空間の 景観をそれぞれ示す．これらの探索空間は x = y で最小値 を と り，変数間依存性がある探索空間 で あ る と い え る ．ノ ー ド 数 が 多 く な る に 従 い ， x = 0 の付近に値の小さな領域が形成されていく のが確認できる．このように多目的最適化によっ て一度の探索で複数の非劣解を得ることで，ど のような要素が加えられると 2 つの実数値 GA の 性能が大きくなるのかを確認することができる． 5 # node 4 5 6 7 9 10 Fitness 37 2286 2640 4268 6092 7144 ランダムな個体生成法との性能差を強調 する探索空間の生成 本節では，ランダムな個体生成法を用いたほ うが交叉を用いた場合より性能が高くなる探索 空間の生成を試みる．ここで，ランダムな個体 生 成 法 と は ，定 義 域 内 に 一 様 乱 数 に よって 個 体 を生成する方法を指すこととする．ランダムな 個体生成法を用いる場合にも世代交代モデルに MGG を使用し，2 親から子個体を生成する際に ランダムに個体を生成する．その他の実験の設 定は 3.1 節と同様である． 探索空間の生成を行った結果，どの交叉に対し てもランダムな個体生成法のほうが性能が高くな る探索空間の生成が行えた．Fig. 4 にランダムな 個体生成法がBLX-α より高い性能を示す探索空間 の例を示す．この探索空間は大域的には x の値が 小さいほど良い評価値が得られる．しかし実際 は，x の値が 9 から 10 の付近に最小値となる領域 が存在する．この探索空間はいわゆる騙し問題 に属すると考えられる．このような探索空間に 対して，BLX-α を用いて探索を行うと，x の値が 小 さ な 領 域 に 集 団 が 集 まって し ま い ，探 索 に 失 敗することがある．このような状況では交叉を 用いて個体を生成するより，ランダムに探 索 を 行ったほうが最適解を発見する確率が高いと考 えられる．UNDX や SPX よりランダムな個体生 成法のほうが性能が高くなる探索空間も，Fig. 4 と同様な傾向をもつものが生成されていた．Fig. 4 のような探索空間は進化計算法が探索に失敗す る典型的な問題であるといえるが，そのような 探索空間が今回の方法によって生成することが できたことも成果の一つであると考えられる． f = |y − x|0.25 f = |x(y − x)|0.25 f = |(y − x)(cos(x2 ) + x2 )|0.25 Fig. 3 多目的進化アルゴリズムによって生成された探索空間の例． ズムの性能差を利用して探索空間の生成を行う ことも考えられる．今回の実験では 2 次元の探索 空間を生成したが，より高次元の探索空間を生 成することも挙げられる．最後に，今回のよう な方法で生成された探索空間を解析することで， 進化計算法の特徴や挙動の理解に繋がることを 期待している． 参考文献 1) 小 林 重 信：実 数 値 GA の フ ロ ン ティア，人 工 知 能 学 会 論 文 誌 ，Vol.24, No.1, pp.147–162 (2009) 2) N. Hansen and A. Ostermeier: Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, Vol.9, No.2, pp.159–195 (2001) Fig. 4 ランダムな個体生成法が BLX-α より高い 性能を示 す 探 索空間の例． 6 まとめ 本報告では，実数値交叉の性能差を強調する 探索空間の生成を行った．実験では 3 種類の交叉 （BLX-α，UNDX，SPX）を用いて探索空間の生 成を行った．その結果，全ての交叉の組み合わせ に対して，一方の交叉を用いた実数値 GA が他方 の交叉を用いた実数値 GA を上回る探索空間の生 成に成功した．その後，目的関数にノード数を加 え，多目的進化アルゴリズムによって複数の探索 空間を同時に生成した．さらに，ランダムな個体 生成法を用いたほうが交叉を用いるより性能が 高くなる探索空間が生成できることを確認した． 今後は，交叉の違いだけでなく世代交代モデ ルや各パラメータの違いによる性能差を強調す る探索空間の生成を行う予定である．また，実 数値 GA 以外の進化計算法や多目的進化アルゴリ 3) J. F. Kennedy and R. C. Eberhart: Particle Swarm Optimization, in Proceedings of the IEEE International Conference on Neural Networks, Vol. IV, Perth, Australia, pp.1942–1948 (1995) 4) R. Storn and K. Price: Differential Evolution –A Simple and Efficient Heuristic for Global Optimization Over Continuous Space, Journal of Global Optimization, Vol.11, No.4, pp.341–359 (1997) 5) M. Oltean: Searching for a Practical Evidence for the No Free Lunch Theorems, in Biologically Inspired Approaches to Advanced Information Technology: First International Workshop, BioADIT 2004, Vol.3141 of LNCS, pp.472–483, SpringerVerlag (2004) 6) J. R. Koza: Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press (1992) 7) R. Poli, W. B. Langdon and N. F. McPhee: A Field Guide to Genetic Programming, Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk (2008), (With contributions by J. R. Koza) 8) W. B. Langdon and R. Poli: Evolving Problems to Learn About Particle Swarm Optimizers and Other Search Algorithms, IEEE Transactions on Evolutionary Computation, Vol.11, No.5, pp.561– 578 (2007) 9) 喜多 一，山村 雅幸：機能分担仮説に基づく GA の 設計指針，計測と制御，Vol.38, No.10, pp.612–617 (1999) 10) 喜 多 一 ，小 野 功 ，小 林 重 信：実 数 値 GA の た め の正規分布交叉に関する理論的考察，計測自動制 御学会論文集，Vol.35, No.11, pp.1333–1339 (1999) 11) H. Kita and M. Yamamura: A Function Specialization Hypothesis for Designing Genetic Algorithms, in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC ’99), pp.579–584, (1999) 12) J. F. Miller and P. Thomson: Cartesian Genetic Programming, in Genetic Programming, Proceedings of EuroGP’2000, Vol.1802 of LNCS, pp.121– 132, Springer-Verlag (2000) 13) T. Yu and J. F. Miller: Neutrality and the Evolvability of Boolean Function Landscape, in Genetic Programming, Proceedings of EuroGP’2001, Vol.2038 of LNCS, pp.204–217, Springer-Verlag (2001) 14) L. J. Eshelman and J.D. Schaffer: Real Coded Genetic Algorithms and Interval-Schemata, in Foundations of Genetic Algorithms 2, Morgan Kaufmann Publishers, pp.187–202 (1993) 15) 小野 功，佐藤 浩，小林 重信：単峰性正規分布交 叉 UNDX を用いた実数値 GA による関数最適化，人 工 知 能 学 会 誌 ，Vol.14, No.6, pp.1146–1155 (1999) 16) 樋 口 隆 英 ，筒 井 茂 義 ，山 村 雅 幸：実 数 値 GA に おけるシンプレクス交叉の提案，人工知能学会論 文 誌 ，Vol.16, No.1, pp.147–155 (2001) 17) 佐藤 浩，小野 功，小林 重信：遺伝的アルゴリズ ムにおける世代交代モデルの提案と評価，人工知 能 学 会 誌 ，Vol.12, No.5, pp.734–744 (1997) 18) E. Zitzler and L. Thiele: SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization, Technical report, Swiss Federal Institute of Technology (2002)
© Copyright 2024 ExpyDoc
