解析講座はじめての最適化(第1回)

目次

最適化アルゴリズム

定式化した最適化問題において最適解を求める手法が最適化アルゴリズムです。最適化アルゴリズムは世の中に数多く提案されていますが、あらゆる問題に対して万能な最適化アルゴリズムはありません。そこで対象となる最適化問題の特徴にあわせ、適切なアルゴリズムを選択する必要があります。ここでは代表例として次の4つの手法の基本的な処理の流れについて説明します。

まず単一目的最適化手法において局所解を探索することを得意とする手法として逐次2次計画法、大域解を探索することを得意とする手法として遺伝的アルゴリズムの概要を説明します。また、多目的最適化手法として遺伝的アルゴリズムをベースとした手法について説明し、最後に近年注目されている逐次近似最適化手法について説明します。

これらの最適化手法はそれぞれ異なる戦略に基づき設計変数の値を変化させながら、繰り返し計算によって最適解を探索します。

逐次2次計画法

逐次2次計画法は目的関数の勾配の情報を利用し、解空間においてその曲面を下る方向へと計算が進み、最終的に解空間の谷となる点を探索します。(最小化問題の場合)この手法の一般的な特徴は次のとおりです。

@ 計算のスタート地点となる初期値近傍の局所解を探索することを得意とします。(結果的に局所解/大域解のどちらが得られるかは、初期値に大きく依存します)

A 得られる最適解は比較的高い計算精度で得ることができます。(理論的な最適解が明らかであれば)

B 大域的な最適化手法と比較して、少ない計算量で最適解を得ることができます。但し、得られる最適解が局所解の可能性もあります。また、多数の設計変数を扱 う大規模問題においてはこの限りではありません。

従って逐次2次計画法は、勾配の算出が可能な連続値の設計変数で、比較的複雑でない応答や小規模な問題に向いた手法です。

この手法のアルゴリズムの概要は以下のとおりです(図11)。


図11 逐次2次計画法(イメージ)
  • 計算のスタート地点となる初期値を与えます。
  • 現在の計算点における解空間の勾配を算出します。
  • 勾配情報をもとに探索すべき方向を決定します。
  • 決定した探索方向に対して、現在の計算点よりも目的関数が改善し、なおかつ制約条件を満足する点を探索します。
  • 得られた計算点へ移動します。
  • ii 〜vを、終了条件を満たすまで繰り返します。

一般的に繰り返し計算に対して、次のような終了条件が利用されます。

@ 繰り返し計算の回数が指定した回数に達したとき(その時点で最適解が得られているかにかかわらず強制的に終了します)

A 繰り返し計算において目的関数が改善しなくなったとき(最適解に収束したと判断します)

B 数学的な最適性の条件を満足したとき(Karush-Kuhn-Tucker条件)

遺伝的アルゴリズム

遺伝的アルゴリズムは、その名から想像できるように生物の進化の過程を模倣したアルゴリズムです。生物の進化においては多様な個体が生成される中で、その環境に適した個体が生き残り、次の世代の子孫を残します。このとき生き残った個体のもつ遺伝子はその環境に適した遺伝子の情報を持つため、その子孫も確率的に環境へ適した個体が生成されます。これにより世代を重ねるごとにその種が環境に適していくことになります。

遺伝的アルゴリズムはこのような進化の過程を模倣するため、次のような特殊な用語が使用されます。

個体 :設計空間上の計算点

遺伝子 :個体が持つ設計変数の情報

世代 :1つの世代は複数の個体で構成される

適合度 :各個体の環境への適合具合で、目的関数の良し悪しで表現

選択 :1つの世代から適合度の高い個体を次世代の親個体として選び出す操作

交叉 :親個体同士の遺伝子を組み替えることにより、次世代の個体を生成

突然変異 :遺伝子の情報を確率的に変化させ、個体の多様性をもたせる仕組み

遺伝的アルゴリズムの一般的な特徴は次のとおりです。

@ 初期値に依存することなく、多峰性の問題においても大域解を探索することを得意とします。

A 局所的な最適化手法と比較して、設計空間を広く探索するため、計算量が増加します。

従って遺伝的アルゴリズムは、複雑な応答や大規模な問題に向いた手法です。また、勾配情報が不要なため、離散値の設計変数を扱うことも可能です。

この手法のアルゴリズムの概要は以下のとおりです(図12)。


図12 遺伝的アルゴリズム(イメージ)
  • 初期世代として複数の個体を設計空間に広く生成します。
  • 各個体の適合度を評価します。
  • 適合度の高い個体を親個体としていくつか選択します。
  • 親個体の遺伝子を用いて、交叉、突然変異により次世代の個体を生成します。
  • ii 〜ivを、終了条件を満たすまで繰り返します。

一般的な終了条件としては、逐次2次計画法で挙げた@Aが利用されます。

多目的最適化手法

多目的最適化手法では、一般的に前述の逐次2次計画法や遺伝的アルゴリズムなどが内部の計算に使用されますが、複数の競合する目的関数を扱うための処理が施されています。ここでは遺伝的アルゴリズムをベースとした多目的最適化手法の概要を説明します。

遺伝的アルゴリズムをベースとした多目的最適化手法の特徴は次のとおりです。

@ 遺伝的アルゴリズムをベースとしているため、古典的な重み付け法などで解くことが困難な、パレートフロンティアが非凸型や不連続となる複雑な問題に対しても、適用することができます。

A 遺伝的アルゴリズムによる最適化により、複数のパレート解を同時に探索するため、古典的な手法と比較して、少ない計算量で解を得ることができます。重み付け法などの場合、パレート解1つ1つに対して目的関数の重みを変化させた最適化問題を反復的に最適化するため、全体の計算量が増加します。

この手法のアルゴリズムの概要は以下のとおりです(図13)。単一目的の場合と適合度の評価の点が異なります。


図13 多目的最適化手法(イメージ)
  • 初期世代として複数の個体を設計空間に広く生成します。
  • 各個体の適合度を評価します。このとき複数の競合する目的関数を扱うため、各個体同士をそれぞれ比較します。他の個体に対して各目的関数が劣っていない個体を非劣解としてグループ化します。
  • 非劣解グループからお互いに離れた個体を親個体としていくつか選択します。
  • 親個体の遺伝子を用いて、交叉、突然変異により次世代の個体を生成します。
  • ii 〜ivを、終了条件を満たすまで繰り返します。

最終的に非劣解となった個体がパレート解となります。一般的な終了条件としては、繰り返し計算の回数や指定した数のパレート解が得られとき、計算を終了します。

逐次近似最適化手法

CAEを利用した最適化では、1回の計算時間が長い解析を扱う場合、充分な繰り返し計算が困難な場合があります。そこで近年注目されている手法が逐次近似最適化手法です。この手法ではその名のとおり、CAEの繰り返し計算で得られたデータから逐次、近似式を作成/更新し、最適化に併用します。これによりCAEによる計算量を低減し、最適化計算の効率化を図ります。ここでは逐次近似最適化手法の代表例として、Efficient Global Optimization(EGO) について説明します。

この手法のアルゴリズムの概要は以下のとおりです(図14)。


図14 逐次近似最適化(イメージ)
  • 実験計画法(ラテン超方格法)により設計空間全体をサンプリングします。
  • 得られたデータから近似式( 応答曲面モデル:Kriging手法)を作成/更新します。
  • 近似式を使った最適化計算を実施します。
  • 近似式における最適解の精度が悪ければ、サンプリングデータを追加します。このときのサンプリング点は、近似式における最適解周辺、またはサンプリングデータが少なく近似式の精度が悪い領域に追加されます。
  • ii 〜ivを、終了条件を満たすまで繰り返します。

一般的な終了条件としては、逐次2次計画法で挙げた@Aが利用されます。

このような手法を利用することで、一般的な遺伝的アルゴリズムと比較して、繰り返し計算の回数を1/10程度まで削減できることがあります。(適用する問題によって効果は異なります)

第1回は最適化問題の定義とその分類に加え、最適解を探索するための代表的なアルゴリズムについて説明しました。次回は対象の設計空間を分析するための各種手法およびバラツキを考慮するための、ロバスト性・信頼性の評価について説明します。

(CAEのあるものづくり2012年17号掲載)

セミナー情報

最適化関連セミナー

適用事例

最適化

その他の記事

こちらのリンクより、その他の記事の情報をご覧いただけます。

1 2 3

CONTACT US

ご購入・レンタル価格のお見積り、業務委託についてはこちら。

お問い合わせ

ページトップへ