適応的重みを有する多目的最適化のための分散遺伝的アルゴリズム

全文

(1)数理モデル化と問題解決 42−３. （２００２．１１．２８）. 適応的重みを有する多目的最適化のための分散遺伝的アルゴリズム †. 廣安知之三木光範. †. 上渡. 浦邉. 二真. 郎†† 也††. 分散遺伝的アルゴリズム（ DGA ）では，母集団は複数のサブ母集団によって構成される．これまでの研究の結果，DGA は単一目的最適化においては母集団を分割しない GA よりも高い解探索能力を有する一方で，多目的最適化においては母集団を分割しない他の進化的手法に劣ることがわかっている．これは，DGA ではサブ母集団内の個体数が少なくなることにより，多目的最適化において重要である多様性の保持を適切に行うことができないためである．このため，本論文では，各サブ母集団に異なった重みベクトルを与えることによってそれぞれのサブ母集団内での探索範囲を限定しつつ，母集団全体としての多様性の保持を行う多目的最適化に適した DGA のモデルとして，重み適応型遺伝的アルゴリズム（ Adaptive Weighted Genetic Algorithm: AWGA ）を提案する．AWGA は，近年の研究によって多目的最適化を行う際の有効性が示されている複数の機構を採用している．複数のテスト関数において AWGA を SPEA2，NSGA-II の 2 手法と比較した結果として，AWGA は SPEA2，NSGA-II よりも広範囲に分布する非劣解集合を得ることを示す．. Multi-Objective Distributed Genetic Algorithm with Weight Adaptation Tomoyuki Hiroyasu † ,Jiro Kamiura †† ,Mitsunori Miki and Shinya Watanabe ††. †. In Distributed Genetic Algorithms (DGAs), a population is divided into sub populations. In previous studies, DGA shows the superior result to the canonical GA in single objective optimizations. However, compared with other evolutionary algorithms, DGA shows an inferior result in multiple objective optimizations. Because the size of the sub populations is small, the diversity of the solutions is an important factor in solving multiple objective optimization problems (MOPs) and cannot be preserved. In this paper, an improved DGA for multiple objective optimization named “Adaptive Weighted Genetic Algorithm (AWGA)”is proposed. In AWGA, each sub-population has a different weight vector and searches for a different region. Therefore, AWGA preserves the diversity of the solutions appropriately. AWGA provides several mechanisms that are effective indicators for solving MOPs in former studies. From comparing the result of AWGA with SPEA2 and NSGA-II using different test problems, AWGA yields more widespread non-dominated solutions than SPEA2 and NSGA-II.. 研究はほとんどが単一目的最適化におけるものであ. 1. はじめに. り，多目的最適化において有効な並列進化的計算の研. 遺伝的アルゴリズム（ Genetic Algorithm : GA ）を. 究は少ない．本研究では，多目的最適化のための並. 用いて多目的最適化を行うアプローチは，Shaffer らの. 列 GA として，重み適応型 GA（ Adaptive Weighted. 1). ．そ. GA: AWGA ）の提案を行う．AWGA は，Tanese の. の中でも Zitzler らの SPEA22) と，Deb らの NSGA-. 分散 GA（ Distributed GA : DGA ）5) を，Kaneko. II3) は，特に良質な非劣解を得ることができると報告されている．GA は潜在的に並列処理に適した特徴を持っているため，これまでに GA の並列化に関する研究が行われてきた 4) ．しかしながら，これらの. らの環境分散スキーム. VEGA. 以降，盛んに研究が行われている. 2),3). 6). の考え方を用いて拡張した. もので，サブ母集団ごとに異なる重みベクトルを持つ．また，AWGA は近年の研究によって多目的最適化を行う際の有効性が示されている複数の機構を採用している．本論文では，複数のテスト関数において. † 同志社大学工学部 Faculty of Engineering, Doshisha University †† 同志社大学大学院 Graduate School of Engineering, Doshisha University. AWGA を SPEA2，NSGA-II の 2 手法と比較することで，AWGA の解探索能力を検討する．. −9−.

(2) 2. 多目的遺伝的アルゴリズム. いてはランダムに重みを割り当てる．. 2.1 多目的最適化問題最適化問題において目的関数が複数存在する場合，. 度の高い個体をエリート個体アーカイブに，非劣解. Step 2.. Evaluation 初期個体を評価し，適合. を非劣解アーカイブに加える．適合度 ff it は，適合. その問題は特に多目的最適化問題と呼ばれる．複数の. 度割り当ての対象となる個体集団における目的関数. 目的関数の間にトレードオフの関係がある場合，すべ. るためには，少なくとも他の 1 つの目的関数値を改. Fi の最小値を fimin ，最大値を fimax で表すとき， fk = 1 + (fk − fkmin )/(fkmax − fkmin ) で算出した f と重みベクトルの加重和で与える．非劣解アーカイブの最大格納量を超えた場合，f 空間上の混雑度の高. 悪しなければならないような解」を求める．このよう. い非劣解を超過分だけ削除する．. な解はパレート最適解（ Pareto-optimal solution ）と. Step 3. Selection for reproduction 個体群，エリート個体アーカイブ，非劣解アーカイブから，トーナメント選択によって交叉を行うことが可能な最小量の個体を Mating Pool にコピーする．. ての目的関数を同時に最大化する解は存在しない．このため，多目的最適化では「ある目的関数値を改善す. 呼ばれる．また，パレート最適解には劣るものの，その時点までに探索した他の解には劣らない解は非劣解（ Non-dominated solution ）と呼ばれる．. 2.2 分散遺伝的アルゴリズム遺伝的アルゴリズム (Genetic Algorithm: GA) は進化的計算手法の一つで，多目的最適化問題に適用され成果を挙げている．GA は母集団を複数のサブ母集団（島）に分割し，各島を異なるプロセッサに割り当. Step 4. Neighborhood Migration 世代数があらかじめ設定した移住間隔で割り切れる時，下記の手続きで近傍移住を行い，重みベクトルとトーナメントサイズの適応変化を行う．近傍移住の手続き. てることにより並列化を行うことができる．分散 GA. (1) 各目的関数に対する重みベクトルを基準に島を. （ Distributed GA : DGA ）5) は，この方法による GA. ソートし，各系列においてある島 A の前後となる島. の並列化モデルとして Tanese によって提案されたも. B,C を島 A の近傍島とする． (2) 各島の近傍島の中から 2 島をランダムに選ぶ．近傍島が 1 島の場合，その近傍島とその島自身とする．. のであり，複数のサブ母集団（島）の集合によって母集団を構成する．DGA では，各島内は独立して GA を行いながら，数世代に一度，移住と呼ばれる操作によって島間の探索情報の交換を行う．DGA は，単一目的の最適化においては，母集団が 1 つである GA と比較して有効な解探索を行うことができる 7) 一方で，多目的最適化においては良質な非劣解集合を探索することができない 8) ．多目的最適化では広範囲に分布す. (3) 各島において (2) で選んだ 2 島の Mating Pool 内の個体を 1 個体ずつランダムに選び，新しく Mating Pool を作成する． (4) 各島の Mating Pool を (3) で作成した新しい Mating Pool によって上書きする．適応変化の手続き. る非劣解集合を同時に探索する必要があるが，DGA. (1) 近傍移住の際に定義した近傍島の中から，島 C の目. は島内の個体数が少ないために，効果的な探索ができ. 的関数 i の重みを WiC としたとき，WiA < WiC < WiB. ないためであると考えられる．島内の個体数の減少に. となり，最も WiC に近い重みを持つ島 A, B を選ぶ．. よる探索能力の低下を回避するためのアプローチとし. A あるいは B の島が近傍内に存在しない場合は，島. て，各島が探索する領域を限定することが考えられる．. C は目的関数 i について重み変化しない． (2) 島 A, B, C の目的関数値を FiA ，FiB ，FiC として，FiA ≤ FiC ≤ FiB を満たさない場合も島 C は目的関数 i について重み変化しない．. 本論文では，Kaneko らの環境分散スキーム 6) の考え方を用いて，各島に異なった重みベクトルを与えることにより，各島が探索する領域を限定する．. 3. 重み適応型遺伝的アルゴリズム本論文では，多目的最適化のための並列 GA として重み適応型 GA（ Adaptive Weighted GA: AWGA) を提案する．AWGA の流れを以下に示す．. Step 1. Initialization 各島で，初期個体を生成し，空のアーカイブを作成する．各島には島数を超えない範囲で重みを均等に割り当てた後，残りの島につ. (3) WiA と WiB のうち，WiC との差が大きい方の重みを WiD とし，平均 WiC + α(WiD − WiC )，標準偏差 β(WiD − WiC ) で発生させた正規乱数 WRand (WiA < WRand < WiB ) によって WiC を置き換える． (4) 特に，FiA = FiB を満たす場合には，島 C が探索している非劣解フロントが非凸型であると判断し，島. C のトーナメントサイズ Nt が 1 よりも大きいならば， Nt を 1 減少させる．FiA = FiB の場合には，島 C が. −10−.

(3) b) ZDT2. a) ZDT1 1.0. 1.0. 0.8. 0.8 ZDT2 F2. Value 50(ZDTx), 100(KUR), 300(KP750-3) 10(ZDTx, KUR), 30(KP750-3) 50(non-dominated solutions) 5(elite solutions) 5 2 points crossover 5 bit flip 1/(chromosome length) 10 0.01 0.01 50,000(ZDTx), 100,000(KUR) 600,000(KP750-3). ZDT1 F2. 0.6 0.4 0.2. 0.6 0.4. Pareto-optimal front. 0.2 Pareto-optimal front. 0.0. 0.0 0.0. 0.2. 0.4 0.6 ZDT1 F1. 0.8. 1.0. 0.0. 0.2. 0.4 0.6 ZDT2 F1. c) ZDT3. 0.8. 1.0. d) ZDT4. 1.0. 8. 0.5. 6. 探索している非劣解フロントが非凸型ではないと判断. ZDT4 F2. Pareto-optimal front. 0.0 -0.5. し，島 C の Nt が最初に設定した値よりも小さいなら. 4 2. Pareto-optimal front -1.0. ば，Nt を 1 増加させる．. 0 0.0. Step 5. Crossover and Mutation Mating Pool の個体に対して，交叉回数 Nc 回の交叉を行い，. 0.2. 0.4 0.6 ZDT3 F1. 0.8. 1.0. 0.0. 0.2. 0.4 0.6 ZDT4 F1. e) ZDT5 20. ZDT5 F2. Step 6. Evaluation Step 5 で生成した新しい個体を評価し，アーカイブの更新を行う． Step 7. Selection for survival Mating Pool からランダムに 2 個体を復元抽出により選び，個体群の. 1.0. 1.0 0.8. 15. 生成された子個体に対して突然変異を行う．. 0.8. f) ZDT6. ZDT6 F2. init. tournament size crossover method number of crossovers mutation method mutation rate migration interval α (weight change) β (weight change) terminal criterion. 表 1 パラメータ. ZDT3 F2. Parameter population size number of islands archive size. Pareto-optimal front 10 5. 0.6 0.4. Pareto-optimal front. 0.2. 0. 0.0 0. 5. 10. 図1. 15 20 ZDT5 F1. 25. 30. 0.0. 0.2. 0.4 0.6 ZDT6 F1. 0.8. 1.0. Non-dominated solutions (ZDTx). 最も適合度の低い 2 個体を上書きする．. 4.2.2 評価手法. Step 8. Terminal Criterion あらかじめ指定した終了条件を満たした場合に，AWGA を終了する．満たしていない場合は，Step 3 に戻る．. ここでは非劣解集合を図示することによる視覚的な性質 2，性質 3 の評価に加えて，性質 1 を重視しながら，性質 2 についても評価できる評価手法として，Tan. 4. 数値実験. らによって提案された Ratio of Non-dominated Indi-. 4.1 種々のパレート最適フロントへの適用 Zitzler ら 9) によって提案されたパレート最適フロントに異なった特徴を持つテスト問題のセットに対して AWGA を適用した．ZDT5 以外のすべての問題に. viduals (RNI)12) を，2 手法間の比較手法としたものを使用する．以降，これを RNI of Two Sets (RNI-2) と呼ぶ．RNI-2 の手続きを示す． (1) 2 手法 A，B によって得られた非劣解集合 SetA nd. ついて 1 つの設計変数を 20 ビットの Gray コードを. A+B と SetB を作成する． nd をまとめ，集合 Set. 用いて表現し，表 1 のパラメータで 30 試行の実験を. のある問題 (ZDT4, ZDT5) 以外では，パレート最適. (2) SetA+B から非劣解でないものを削除し，非劣解集合 Seta+b nd を作成する．2 手法によって同一の非劣解が得られている場合に限り，非劣解の重複を許す． (3) Seta+b nd のうち，手法 A によって得られた非劣解. フロントの形状によらずにパレート最適フロント上の. の割合を RNI-2(A,B)，手法 B によって得られた非. 解集合を偏りなく得ることができ，また，非劣解フロ. 劣解の割合を RNI-2(B,A) とする．. 行った．図 1 は，得られた非劣解を 30 試行すべて図示したものである．AWGA は非劣解フロントに多峰性. ントに多峰性のある問題でも，試行によってはパレー. RNI-2(A,B) の値が大きいほど，手法 A は手法 B. ト最適フロントに近い非劣解フロント上の解集合を偏. と比べて高精度の，広範囲に分布する非劣解集合を探. りなく得られている．. 索できているといえる．実験では，各手法について複. 4.2 他の手法と AWGA との比較 4.2.1 実験概要本節では，AWGA を SPEA2 と NSGA-II の 2 手法との比較を行う．対象問題は連続関数最適化問題の KUR10) と，組み合わせ最適化問題の 750 荷物 3 目的ナップサック問題 (KP750-311) ) である．. 数回の試行を行うため，2 手法間のすべての試行の組み合わせについて RNI-2 を適用する．. 4.2.3 実験結果表 1 のパラメータを使用して 30 試行の実験を行った．得られた非劣解集合と RNI-2 の結果を図 2，図 3 に示す．AWGA は偏りなく，SPEA2, NSGA-II よりも広い範囲に分布する非劣解集合を得られている．さらに. −11−.

(4) せるため，非凸型のパレート最適フロントを持つ. KUR では精度においても優れた結果を示し，RNI-2. 問題に対しても非劣解集合を得ることができる． • AWGA は広範囲に分布する非劣解集合を探索することができる．. でも多くの試行において SPEA2，NSGA-II を完全に優越している．KP750-3 では SPEA2, NSGA-II に劣る結果となっている．これは AWGA の探索が広く非劣解フロントを進める力が弱いためと考えられる．. AWGA は解探索範囲が広いため，探索の早い段階においては精度の面で他手法に劣る場合がある．しか. AWGA. KP750-3. 30000. しながら，非劣解フロントを広げるためには精度を上. 28000. げるよりも多くの探索を行う必要があると考えられる. KUR F2. -100. 26000 -200. KP750-3 F3. KUR 0. ため，探索の早い段階から広い範囲に分布する非劣解. 24000. 集合を得ることができる AWGA は有効な多目的最適. -300. 24000 26000 KP 750 28000 -3 F2 30000. -400 -1000. -900. -800 KUR F1. -700. -600. 24000 26000 F2 28000 -3 50 30000 7 KP. 化アルゴリズムであるといえる．. NSGA-II KUR. 28000. -100. 26000 -200. KP750-3 F3. KP750-3. KUR F2. 参考. 30000. 0. 24000 -300. 24000 26000 KP 750 28000 -3 F2 30000. -400 -1000. -900. -800 KUR F1. -700. -600. 24000 26000 F2 28000 -3 50 30000 7 KP. SPEA2 KUR KP750-3. 28000. KUR F2. -100. 26000 -200. KP750-3 F3. 30000. 0. 24000 -300. 24000 26000 KP 750 28000 -3 F2 30000. -400 -1000. -900. -800 KUR F1. -700. -600. 24000 26000 F2 28000 3 030000 75 KP. 図 2 Non-dominated solutions (KUR, KP750-3) KUR. KUR. KP750-3. KP750-3. NSGA-II. SPEA2. NSGA-II. SPEA2. Evaluation value of RNI-2. 1.0 0.8 0.6 0.4 0.2 0.0 AWGA. 図3. 5. 結. RNI(AWGA,{NSGA-II,SPEA2}). 論. 本論文では多目的最適化のための並列 GA として重み適応型 GA（ Adaptive Weighted GA: AWGA ）を提案した．AWGA では，各島に異なる重みベクトルを割り当て，各島では単一目的最適化を行いながら，全体では多目的最適化を行う．AWGA は，近傍移住，重み変化，エリート個体と非劣解のアーカイブ，などの機構を備えている．AWGA を，複数の連続問題と組み合わせ問題に適用した結果，以下のことがわかった．. • AWGA はトーナメントサイズを適応的に変化さ. 文. 献. 1) Schaffer, J. D.: Multiple objective optimization with vector evaluated genetic algorithms, Proc. ICGA’85 , pp. 93–100 (1985). 2) Zitzler, E., Laumanns, M. and Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm, Technical Report 103, Computer Engineering and Communication Networks Lab (TIK) (2001). 3) Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T.: A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II, KanGAL report 200001, Indian Institute of Technology, Kanpur, India (2000). 4) Cant´ u-Paz, E.: Migration Policies, Selection Pressure, and Parallel Evolutionary Algorithms, IlliGAL Report, No. 99015 (1999). 5) Tanese, R.: Distributed Genetic Algorithms, Proc. ICGA’89 , pp. 434–439 (1989). 6) Kaneko, M., Hiroyasu, T. and Miki, M.: A Parallel Genetic Algorithm with Distributed Environment Scheme, Proc. PDPTA, Vol. 2, pp. 619–625 (2000). 7) 廣安知之, 三木光範, 上浦二郎: 実験計画法を用いた分散遺伝的アルゴリズムのパラメータ推定, 情報処理学会数理モデル化と問題解決研究会進化的計算特集号 (2002). 投稿中. 8) Quagliarella, D. and Vicini, A.: Sub-population policies for a parallel multiobjective genetic algorithm with applications to wing design, Proc. SMC , pp. 3142–3147 (1998). 9) Zitzler, E., Deb, K. and Thiele, L.: Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, EC , Vol. 8(2), pp. 173–195 (2000). 10) Kursawe, F.: A Variant of Evolution Strategies for Vector Optimization, Proc. PPSN I , Vol. 496, pp. 193–197 (1991). 11) Zitzler, E. and Laumanns, M.: Test Problems for Multiobjective Optimizers, Technical report, Computer Engineering and Communication Networks Lab (TIK) (2001). http://www.tik.ee.ethz.ch/˜zitzler/testdata.html. 12) Tan, K. C., T.H.Lee and E.F.Khor: Incrementing Multi-Objective Evolutionary Algorithms: Performance Studies and Comparisons, Proc. EMO’01 , pp. 111–125 (2001).. −12−.

(5)