フレキシブルシステム設計支援のための並列多目的遺伝的アルゴリズムの開発

廣安　知之

研究期間 平 成 １７年 度 ～ 平 成１９年 度

背景：

フレキシブルシステムはシステムが環境の変化をセンスし，内部パラメータを変化させることにより実行結果を変化させる知的な人工物の一つである．環境の変化に対して内部パラメータもしくは構造を変更することで，ロバスト性を向上し，システムの性能の向上もしくは適用範囲を広げることが可能なシステムを本研究ではフレキシブルシステムと呼ぶ．これまでソフトウエアや制御の分野では多くの開発事例が見られるが，機械構造と制御・回路，ソフトウエアを含めた設計においても近年注目を集めている．


例えば，ディーゼルエンジンの設計について考える．ディーゼルエンジンは燃費の良さや排出する二酸化炭素の少なさで特に商用での利用が広く行われている．その一方，触媒の利用の遅れなどにより排出するNOxやすすの量が問題となっている．ディーゼルエンジンの運転パターンは，従来では静的に決まっており，そのため高速安定走行状況でも坂道走行状況でも基本的には内燃機関内の燃焼は同じであった．これに対して，ディーゼルエンジンをフレキシブルシステムとして設計することができれば，環境の変化に対して燃焼方法を変化させることができ，最適な燃焼方法を決定することが可能となる．これにより，ある走行パターンのときには燃費を重視した走行を行うことができ，ある走行パターンでは排出するNOx値やすすの値を削減した走行を行うことが可能となる．このような機械構造と制御・回路，ソフトウエアといった複合領域でのフレキシブルシステムの設計が要求されるようになってきているのである．

研究目的：

本研究では上記のような背景の下，機械構造と制御・回路，ソフトウエアといった複合領域でのフレキシブルシステムの設計支援を行うシステムを構築する．フレキシブルシステムの設計支援を行う際に検討すべき点として，多目的最適化の問題と実時間内での解候補の決定があげられる．一般に実問題においては，設計の際に目標とすべき項目は複数存在するが，これらは一つを良くすれば他方が悪くなるようなトレードオフ関係である場合が多い．そのため，これらのトレードオフを表現する解集合を求める必要がある．さらに，フレキシブルシステムにそれらの解集合を利用する場合，これらの目的空間だけでなく，設計変数空間の両方で多様な解を探索する必要がある．本研究では，生物の遺伝と進化を模倣した最適化手法である遺伝的アルゴリズムを開発しフレキシブルシステムの設計支援を行う．また，実問題を対象とする場合，非常に多くの計算時間を必要とするため，並列モデルの検討は必須である．そのため，本研究のサブ目的は次の３つとなる．
１） 遺伝的アルゴリズムを利用した強力な多目的最適化手法の開発．
２） 実時間内に解を求めるための並列処理モデルの開発．
３） 多目的遺伝的アルゴリズムを使ったフレキシブルシステムの設計支援システムの開発．

研究成果：

これまでに得られた結果を主要項目に分割して，現時点における本研究の成果を下記にまとめる．

＊パレート解集合のフレキシブル性

フレキシブルシステムとは，対象となる関数の広い範囲を表すことのできる変数を有するシステムのことである．システムがフレキシブル性を有することで，必用な関数の値が変化しても，柔軟に追従することが可能であり，特に動的な変化に対しても対応が可能である．本研究では，多目的最適化問題におけるフレキシブル性について議論を行っている．多目的最適化問題における一つの目標は，トレードオフの関係がある目的関数のパレート解集合を求めることである．そのため，本研究では，パレート解集合のフレキシブル性を議論した．ある変数がパレート解集合に対してフレキシブル性が高いとは，すべての変数を使って得られるパレート解集合の部分集合を，他の変数を固定して着目変数を変化させた時に得られるパレート解集合が高率で含有されていることを意味する．この，パレート解集合のフレキシブル性を判断する具体的な手順は次の通りである．

(1)多目的最適化問題の定式化を行い，一度　対象となるすべての設計変数でパレート解集合を求める．

(2)ある目的関数の値によってこれらのパレート解集合をソートする．

(3)2目的の場合，均等となるように5点を選択する．

(4)選択された5点それぞれに対して，1つの設計変数の値のみを変化させる．この時に他の変数の値は固定する．この操作により，変数の変化に対するパレート解の変動が求められる．これがこの点における対象設計変数のフレキシブル性である．

(5)すべての点においてすべての設計変数に対して同様の操作を行うことで，それぞれのフレキシブル性を把握する．

提案しているパレート解のフレキシブル性については，数値実験を通じて説明され，有効性の議論を行った．さらに，シミュレーションによるディーゼルエンジン設計問題において，本手法を適用させることで実用面においても高い性能を有することを確認した．

＊並列多目的遺伝的アルゴリズムに適した近傍交叉の効果の検討

多目的遺伝的的アルゴリズムは，生物の遺伝と進化を模擬した手法である遺伝的アルゴリズムを多目的最適化問題に適用した手法である．確率的探索と多点探索が特徴である．この遺伝的アルゴリズムを並列処理で行う場合，複数存在する探索点をそれぞれ並列で処理することがこのましい．しかしながら，探索点を個別に探索させるのでは，アルゴリズムが持つ探索能力を低下させてしまう可能性がある．ここでは，遺伝的的アルゴリズムの遺伝的操作の一つである遺伝的交叉において並列処理が容易な交叉である近傍交叉を提案し，その探索能力を検討した．

近傍交叉は目的関数空間において近接している個体同士で交叉を行う．並列多目的遺伝的アルゴリズムでは，これらの交叉を行う個体を各並列計算ノードに送信し，子個体生成および評価を行うことで効率的な並列化が期待される．また，生成する個体数を調整することで，グリッド計算環境のような各計算ノードが不均一な環境にも適用可能となる．しかしながら，このような交叉が解探索性能を低下させてしまってはならない．そのため，近傍交叉の解探索性能を検討し，非常に効率的な交叉手法であることを確認し，並列計算環境に適していることを検討した．

近傍交叉の探索能力が示されたため，これらを並列計算環境で処理を行う際の検討も行った．特に，グリッド上で稼動させることを対象として各計算資源が不均一な状況での計算モデルの検討を行った．提案したモデルは，近傍交叉を利用して，各計算ノードに合わせて動的に計算量を調整するモデルである．計算機実験により，非常に高い稼働率をかせぐことができ，良好な多目的遺伝的アルゴリズムの並列モデルが提案できたものと考えられる．

＊評価部分の計算コストが高い場合への対応

遺伝的アルゴリズムは目的関数や制約条件の評価を多数要求し，繰り返し計算を行うために，非常に計算コストが高い手法である．実問題などを対象とする場合，ＰＣクラスタなどの並列計算機を利用しても実時間内に計算シミュレーションが終了しない問題も存在する．そのため，遺伝的アルゴリズムが必要とする評価の回数を削減することが必要となる．これらの検討として，

（１）応答局面法を利用した評価関数の近似の検討

（２）ネットワークインバージョンを利用することにより，少ない個体数でも多様性を維持できる仕組みの検討

を行った．応答局面法を利用する際には，リファレンスポイントの選択が問題となり，パレート解集合付近のみの情報だけではうまく近似できないことが明らかとなった．また，多目的最適化では，目的関数空間でのパレート解集合がまず重要であり，必要な場所に探索点を設置するためには，ネットワークインバージョンなどを利用した逆解析が必要となる．

＊ＰＣクラスタの構築

多目的遺伝的アルゴリズムのシミュレーションは，繰り返し計算が膨大に必要となるため計算コストが非常に高い．このために，進化的計算を行うための大規模PCクラスタの構築を行った．これまで，PCクラスタのOSとしてはLinuxを中心に利用してきたが，WindowsのOS利用の検討も開始し，高い計算性能を有することが明らかとなった．

プロジェクト関連論文

査読有りの学術論文および国際会議：

  1. Comparison Study of SPEA2+, SPEA2, and NSGA-II in Diesel Engine Emissions and Fuel Economy Problem, Tomoyuki HIROYASU, Mitsunori MIKI and Seiichi NAKAYAMA, IEEE Congress on Evolutionary Computation 2005 (CEC 2005), pp.236-242, (2005)
  2. 目的関数空間と設計変数空間におけるパレート最適解の多様性を維持するアーカイブメカニズム， 金　美和， 廣安　知之， 三木　光範， 情報処理学会 論文誌：数理モデル化と応用，Vol. 46, No. SIG 17(TOM13)， pp.102-113， (2005)
  3. Multi-Objective Optimization of Diesel Engine Emissions and Fuel Economy Using SPEA2+, Tomoyuki HIROYASU, Mitsunori MIKI, Seiichi NAKAYAMA and Yoshiko HANADA, ACM Proceedings of 2005 Genetic and Evolutionary Computation Conference, pp.2195-2196, (2005)
  4. Effectiveness of Neighborhood Crossover in Multiobjective Genetic Algorithm, Kengo YOSHII, Tomoyuki HIROYASU and Mitsunori MIKI, IASTED Proceedings of the Second IASTED International Conference on Computational Intelligence (CI 2006), pp.218-223, (2006)
  5. マスタースレーブGAおける最適プロセス数の導出， 廣安　知之， 吉井健吾， 三木　光範， 同志社大学 理工学研究報告, Vol,47, No1， pp.10-17， (2006)
  6. 多目的遺伝的アルゴリズムにおける近傍交叉の効果， 吉井　健吾， 廣安　知之， 三木　光範， 情報処理学会 論文誌：数理モデル化と応用，Vol. 48, No.SIG2(TOM 16)， pp.40-48， (2007)
  7. Discussion of Parallel Model of Multi-Objective Genetic Algorithms on Heterogeneous Computational Resources, Kengo Yoshii, Tomoyuki HIROYASU and Mitsunori MIKI, 4th International Conference, EMO 2007, Late Breaking Papers Proceedings, pp.30-35, (2007)
  8. Mechanism of Multi-Objective Genetic Algorithm for maintaining the solution diversity using Neural Network, Kobayashi Kenji, Tomoyuki HIROYASU and Mitsunori MIKI, 4th International Conference, EMO 2007 Proceedings, pp.216-226, (2007)
  9. Discussion of Clustering and Network Inversion for Multi-Objective Genetic Algorithms, Kenji Kobayashi, Tomoyuki Hiroyasu and Mitsunori Miki, The 7th International Conference on Optimization: Techniques and Applications(ICOTA7), CD-ROM, (2007)
  10. Flexibility of Design Variables to Pareto-Optimal Solutions in Multi Objective Optimization Problems, Tomoyuki HIROYASU, Shinpei　CHINO and Mitsunori MIKI, IEEE Proceedings of 2007 Congress on Evolutionary Computation (CEC2007), pp.4462-4468, (2007)
  11. Discussion of Parallel Model of Multi-Objective Genetic Algorithm on Heterogeneous Computational Resources, Tomoyuki HIROYASU, Kengo YOSHII and Mitsunori MIKI, Genetic and Evolutionary Computation Conference (GECCO 2007) Vol.2, pp.904-904, (2007)
  12. ネットワークインバージョンを利用した多目的遺伝的アルゴリズムのための多様性維持メカニズム， 小林　賢二， 廣安　知之， 三木　光範， 情報処理学会 論文誌：数理モデル化と応用(TOM)，採録決定

講演：

  1. 多並列計算環境における並列多目的遺伝的アルゴリズムの検討， 吉井 健吾， 廣安　知之， 三木　光範， 計算科学シンポジウム(MPSシンポジウム2005) 計算科学シンポジウム論文集「相互作用の計算科学」， pp.255-262， (2005)
  2. 多目的遺伝的アルゴリズムにおける並列化モデルの検討， 吉井 健吾， 廣安　知之， 三木　光範， 第15回設計工学・システム部門講演会－真のゆたかさを実現する設計とシステム- 第15回設計工学・システム部門講演会－真のゆたかさを実現する設計とシステム-　講演論文集， pp.37-38， (2005)
  3. 応答曲面を利用した多目的遺伝的アルゴリズムの検討， 廣安知之， 三木光範， 鈴木和徳， 日本機械学会 第18回計算力学講演会講演論文集， pp.757-758， (2005)
  4. 多目的遺伝的アルゴリズムにおける応答曲面の利用の検討， 鈴木和徳， 廣安知之， 三木光範， 情報処理学会 研究報告　2006-MPS-58， pp.11-14， (2006)
  5. Ninf-Gを用いたディーゼルエンジン燃料噴射スケジューリング問題の最適化システム， 千野晋平， 廣安知之， 三木光範， 情報処理学会 先進的基盤システムシンポジウム（SACSIS2005)論文集， pp.262-263， (2006)
  6. ニューラルネットワークの利用による多様性維持メカニズムを有する遺伝的アルゴリズム， 小林賢二， 廣安知之， 三木光範， 情報処理学会 研究報告　2006-MPS-59， pp.13-16， (2006)
  7. ニューラルネットワークの利用による多様性維持メカニズムを有する多目的遺伝的アルゴリズム， 小林賢二， 廣安　知之， 三木　光範， 情報処理学会 研究報告　2006-MPS-61， pp.41-44， (2006)
  8. グリッド環境における並列多目的遺伝的アルゴリズムの検討， 吉井健吾， 廣安知之， 三木光範， 情報処理学会 研究報告　2006-HPC-107， pp.227-232， (2006)
  9. 多目的最適化のための分散協力型スキームの検討， 西岡雅史， 廣安　知之， 三木　光範， 情報処理学会 研究報告　2007-MPS-63， pp.101-104， (2007)
  10. 多目的GAによるクラスタリングの検討 -初期化アルゴリズムの検討-， 廣安知之， 三木　光範， 千田智治， 情報処理学会 第69回全国大会講演論文集， pp.215-216， (2007)
  11. 意思決定者の選好情報を利用した多目的遺伝的アルゴリズム（～高次元目的関数空間における効率的な探索手法の検討～）， 廣安　知之， 三木　光範， 石田裕幸， 計測自動制御学会 第34回知能システムシンポジウム， pp.161-166， (2007)
  12. 多目的遺伝的アルゴリズムのためのクラスタリングとネットワークインバージョンの検討， 小林　賢二， 廣安　知之， 三木　光範， 日本機械学会 第20回計算力学講演会講演論文集 No.07-36， pp.368-369， (2007)
  13. パレート解集合の精度と幅広さを考慮する多目的遺伝的アルゴリズムの探索戦略， 西岡雅史， 廣安知之， 三木光範， 日本機械学会 第20回計算力学講演会講演論文集 No.07-36， pp.339-340， (2007)
  14. 多目的 GA を用いたクラスタリングの検討 -大規模データのための初期化アルゴリズム-， 千田 智治， 廣安 知之， 三木 光範， 日本機械学会 第20回計算力学講演会講演論文集 No.07-36， pp.317-318， (2007)

本：

キーワード

謝辞

本プロジェクトは平 成 １７年 度 ～ 平 成１９年 度の間，科学研究費補助金（課題番号 34310404）の補助を受けた．