ぜぜ日記

ブログです

遺伝的アルゴリズムと多目的最適化

講義メモ.考察は字数制限があるのでムリヤリ感あり.無駄に時間使った・・・

概要

池田心先生


・最適化とは
・遺伝アルゴリズムとは
・多目的最適化
・どういった目的があるか
・どうやってやるか
・事例


最適化とは.
探索空間Xがあり,x∈Xに対して目的関数f(x)があるとき,f(x)を最大にするような解x*∈xを求めることを最適化問題と呼ぶ.
関数を最大化することや最小化することがメインである.
TSP(巡回セールス問題)などが有名である.


単純な場合は微分や全数探索で最適解を求められるが,問題は往々にして複雑で人間に理解不可能なカタチであるため最適解を求めるに様々な手法が考案されている.
例えば,50ノードの巡回セールスマン問題で全数探索しようとすると50!必要となってしまう.


局所探索という手法は,近傍f'(x)が改善される方向にxをシフトさせるという単純なもので一定の成果を出しているが,求まる最適解は局所最適解でしかなく,大域最適解である保証はない.
おおまかに精度と時間はトレードオフである.
タブサーチや焼き鈍し法など,よく使われる
手法も提案されている.


ここでは,遺伝的アルゴリズム(GA)という,生物の進化を模した手法を紹介する.
これは生物の進化においての個体を解とし,解同士の交叉で新しい解を生み出す.そして世代交代・淘汰により良い解を残していく多点探索の手法である.大域最適解の保証はないが効率が良く,局所最適解にとらわれにくいためさまざまな分野で使用されている.
具体的な例:スケジューリング問題,レンズ系設計,下水道制御,N700系の形状設計に使用されたことでも有名である.


最適化問題として扱える問題には,探索空間,目的関数が定められるものである必要がある.[政策->幸せ]などあいまいなものに対しては対応できない.パラメータが式に落とし込めるかが重要である.
やりたいことははっきりしていても何を解にしていいかわからない場合,つまり解を表現できない場合は難しい.例えば,ロボットの二足歩行や囲碁アルゴリズム,高速で燃費のいい車をつくるなどである.
これらの課題は,評価を得るためのコストや,いつも同じf(x)が得られるかわからないノイズが主である.(ノイズの問題は複数回評価により,回避可能である)
システムの満足度など,どうやってf(x)として数値化するのか,という問題もある.


そこで,多目的性の最適化を使うことになる.
これは評価に複数の指標を用い,それらのバランスの取れた解を得る手法である.唯一の最適解を求めることはできない2つ以上の対立する評価基準を
よりよく満たす,ものを得る.例えば,コストと性能,リスクとリターンである.
無理矢理重み付けして単一評価することもあるが,複数の解候補を,視覚的に表すことが望まれている.これはコンピュータの性能の向上や手法の発達で可能になってきた.


ここで基本となる概念としてpareto戦略がある.これはどの評価基準でもBがCに勝るのであれば,Cは不要ということである.これはBはCをdominateするという.どの解にもdominateされないものをpareto最適解という.つまり2つの基本戦略,(1)dominateされない解を優遇.(2)密集している部分は間引く.というものがある.NSGA-II[Peb2000]など標準ができている.
目標はpareto最適解集合を得ることである.これには複数の探索点を持つGAの親和性が高い.生物の進化は壮大な多目的最適化であるとも言える.


注意点として,以下のものがある.
・交叉オペレータがうまく働かない場合もある(虎とメダカの子供は想像できない・・).
・Pareto解の中には現実に不要な極端な解もある.
・多くの評価回数が必要になる傾向があり,一つの解を得るのにコストがかかるものである場合は,現実的ではない.
・pareto解集合の中から「最終的にどれを選ぶか」が利用者に任されている.多数の目的であれば難しい.


さまざまな分野での電子制御の発達により,適応可能なものは増えて
いる.
例:自動車の制御,マルチエレベータ.など.

〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

大林茂先生


東大工出身.航空宇宙を専門.NASAイムズ研究所,上席研究員を経て東北大学に.


空力学を多目的最適化により設計している.
東北大学鳥人間コンテストの顧問として優勝に導く.
テーマは環境に優しい超音速機.
コンコルドなど,超音速機は140dbもの騒音が出るが,ソニックブームのない複葉超高速を設計している.(ソニックブームの騒音は,雷と同じである.空気を押しのけ,それが音になる)


ちなみにマッハ1で飛ぶのは難しい,これは翼に沿って風が加速することで不安定な衝撃波が発生するためである.


超音速機を低騒音でつくるためには,飛行機を細長くすることや機首を丸くすること,複葉にすることが提案されている.MISORA


また,安全に飛行機を飛ばす研究もしている.特に離着陸で問題となる後方乱気流を計測融合シミュレーションにより分析している.


航空宇宙産業について.


B787の,三菱重工が作成した部品に欠陥があったのは,もとの設計に欠陥があったからである.


HondaJetが2003年に初飛行したり,アメリカではSpaceShipOneなどのベンチャーが飛行機の設計を行うなど,従来のように伝統的で大規模な会社(おもに軍需産業)のみが飛行機を作っているわけではなくなっている.


日本国内でも旅客輸送は増えている.輸送をいかに増やすかということで,小型機への需要がある.
ちなみに世界でもっとも旅客の多い航路は東京-札幌間で2位は東京-大阪間である.


航空,宇宙,民航,防衛産業
航空が11,000億ドル
民間がここ3,4年で伸びていて6600億ドル
防衛が4600億ドル↓
宇宙が2000億ドル→


民航は輸出が5000億で,輸入超過である.


がんばれMRJ(三菱リージョナルジェット)


〜〜ここまでが前置き〜〜


最適化と可視化


最適化とは最適設計のこと?
象を触るようなものである.例えば,しっぽだけさわれば細いですね,足を触ればゴツゴツしてますね,牙ではつるつるしてますね,となる.全容が把握できないものを相手にしている.それをいかに見えるようにし,設計するか.


飛行機を作る場合,Aerodynamics(空力学),Propulsion(推力,エンジン),Structure(構造)の問題の整合性,バランスが大切であるが,すべてがわかる設計者はいない.


最適化はパレート解を改善していく過程であるが,パレート面の形状や次元により難易度は変わってくる.極限パレート解では意味がないこともある.
3objectiveの場合は2次元に射影できるが,それ以上に目的が増えるとわからなくなってしまう.


それを見えるように可視化する手段を模索する.


レイノルズ数により流体の動きを記述した流体力学の有名なレイノルズの実験では,透明のパイプ,インクの使用により可視化実験により相似則を発見している.


(済州島のカルマン渦なども可視化の一例だ)


そこで,Self Organized Map,自己組織化マップを使用する.
ニューラルネットを基本とするコホネンによる記憶モデルであり,多次元データを二次元のマップに配置するものである.
座標や距離のない地図で,データ一つ一つがニューロンベクトルである.SOMは設計空間を可視化する重要な設計ツールである.


(図がないとわかりにくいが,色分けした地図に落とし込んでいる.何種類かの,目的を表した地図,例えばコスト地図,速度地図)


カラーマップが大域的な構造を可視化し,すべての目的関数が改善される領域があれば個々が設計空間のスイートスポットである.もしスイートスポットクラスターがあればここを決定木やラフ集合などのツールにより詳細に解析する.
この過程は,まさに見える化であり,SOMを専門としない人にも容易にトレードオフの関係が認識できる.


MRJの翼の,エンジン位置の設計に利用されて,競合機より燃費を26%改善したことに貢献している.(エンジンと,材料と機体設計で3分の1ずつ・)
もともとMRJのエンジンは機体につけることになっていたが,設計変更で主翼につけることになり,どうするかという経緯があった.


30設計変数で,巡航抵抗と支える構造,衝撃波の改善を主目的としている.実験にはラテン超方角法を用い,ナセル流路の最適化をデータマイニング手法により実行した.


順序は,データの準備,数値データの離散化,縮約,ルールの生成,フィルタリング,ルールの解釈.という流れで実行される.
離散化や縮約はパラメータを減らし,計算しやすくするためである.


これによってMRJの設計をおこなった.


他の産業でも使われ始めている.
日立の社会人ドクターの杉浦さんによる家電開発への応用を例として説明する.
いままでは概念設計から基本,詳細設計を目的ごとにおこない,試作,生産の繰り返しであり,歩留まりが低下していた.
最適設計導入後は,家電に求められる目的間の最適化を行い,可視的に選択することで,効率良く,ノウハウが残る設計ができるようになる.


これが多目的ロバスト設計探索である.


〜〜〜
空へ,宇宙へ


設計する,要求を実現する,形状を探す.これは一種の逆問題である.
富山哲男


アブダクション,創造的洞察である.
設計に役立つ仮説を思いつくような仕掛けが必要.
これには設計空間の構造化と可視化が必要だ.


単なる最適化は役に立たない.
MODE(Multi Objective Design Exploration)
最適化+データマイニングにより,


このサイクルを利用することでより,効率的な設計ができるようになるであろう.

考察

遺伝的アルゴリズムやSOMによる多目的最適化は非常に興味深かった.
遺伝的アルゴリズムに対しては,以下の疑問が残る.
(1)交叉のプロセス・・新しい解を生み出す場合に,単純に新しい解を生み出せるのかどうか.ほとんどが価値のない解となり,有用なものは一握りしかないのではないか.
(2)ノイズがあり,一定の入力に対して一定の解がでない場合,何度も実行するとコストがかかるのではないだろうか.
(3)ハードウェア問題で一つの解の評価値を計算する場合に時間とコストがかかる場合,現実的に実行できるのかどうか.
(4)以上に関して,適切な枝刈りができればよいだろうが,GAの技術だけでなく対象分野の知識も必要だろう.


コンピュータリソースがあればいくらでも実験できるソフトウェアに関わる問題では成果がだせると思う(人工知能レインなどではやっている)
ゲームの戦略などでは,人間が思いも寄らなかった手法を編み出すなどもあるらしい.


評価が一定の関数でなく,人間による評価を評価値とするインタラクティブな場合にGAの考え方を適用すれば,よりソフトな問題への一つの解法となるかもしれない.


設計を見える化し,比較可能な状態にすることで,技術者の知見,ノウハウにもつながるということは,すばらしいと思う.
答えを得るだけでなく,その過程を,直感でなく,可視的に人間の脳に理解可能なように落とし込む.世界が広がる.


バランスをとる最適化により,飛行機の設計など複雑でさまざまな要素が絡み合ってる事象をつくることも十分にすごいことではあるが,より複雑で変化しやすい社会のシステム,メカニズムデザインに適応するにはどうしたらよいだろうか?


先生もおっしゃっていたように,モデル化,パラメータの設定がいちばん難しいだろう.狭い,システムを低コストで可変させられる領域があれば実現できるかもしれない.