構造最適設計CAEソフトウェア OPTISHAPE-TS の
機能や使い方について紹介しているブログです.

OPTISHAPE-TSの製品に関する情報はこちら

2015年06月10日

OPTISHAPE-TS の理論 第3回「ノンパラメトリック最適化の難しさ(その2)」

OPTISHAPE-TS の理論
第3回「ノンパラメトリック最適化の難しさ(その2:時間計算量)」

前回までに,ノンパラメトリック最適化とは数学的には関数を対象とした最適化で,実際には有限要素モデルの規模(節点数,要素数)と同程度の数の設計変数を求める問題になることを説明しました.この記事では,そのような問題を解くための最適化アルゴリズムについて解説します.

まず,時間計算量という概念を導入しましょう.時間計算量はO(・)という表記を使います.これを使って計算時間がデータの数に対してどのように増加するのかを表します.コンピュータープログラミングを勉強した方は分かると思いますが,データの並べ替えを行うアルゴリズムであるクイックソートアルゴリズムの時間計算量は平均的に O(N logN) であると言われます.一方,同じデータの並べ替えを行うアルゴリズムでもバブルソートアルゴリズムの時間計算量は O(N2) であると言われます.これは,クイックソートの計算時間はデータ数 N の増加に対して N logN 倍で増加するのに対して,バブルソートは N2 倍で増加する,ということを表しています.増加の度合いはクイックソートの方が穏やかです.もし,あるデータ数においてクイックソートとバブルソートが同程度の計算時間,あるいはバブルソートの方が速かったとしても,データ数が十分に大きくなるとクイックソートが必ず有利になる,ということが時間計算量から予測できます.

最適化問題を解いて最適解を求めるためのアルゴリズムが最適化アルゴリズムです.最適化アルゴリズムでは多数の試行を行いながら,設計変数を最適解に近づけていったり,最適解を得るための情報を収集したりします.構造最適化の場合,その試行を行う度に有限要素解析を実行する必要があり,通常はこの計算時間が全体の解析時間の大半を占めます.従って,なるべく少ない試行で最適解に辿り着く最適化アルゴリズムが重要です.ノンパラメトリック最適化の場合,試行回数が求めるべき設計変数の数 N(=探索すべき空間の次元の大きさ)に対してなるべく大きくならないアルゴリズムが求められます.さらに言えば N に依存しない時間計算量 O(1) のアルゴリズムが理想的です.

続きを読む
posted by 株式会社くいんと at 12:00| OPTISHAPE-TS の理論 | 更新情報をチェックする
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。