静岡理工科大学 菅沼ホーム SE目次 索引

システムの最適化

− はじめに −

  システムの最適化に関する話題を以下に述べるように分類してみます.まず,最適化の対象とするシステムを,静的システム(時間を陽に含まないシステム)と動的システム(時間を陽に含むシステム)に分類します.

  1. 静的システムの最適化

      時間的な変化があり得るシステムであっても,ある固定した時刻におけるシステムの最適化を試みる場合は,静的システムの最適化とみなすことができます.一般的に記述すれば,以下に示すような問題になります.

    静的システムの最適化:目的関数,

    y = f(x)   (1)

    を,制約条件,

    gj(x) ≧ 0,  j=1,2,・・・,m   (2)

    のもとで,最大にする.

    最小にする問題も,目的関数の符号を変えれば最大にする問題となりますので,基本的に同じです.静的システムの最適化手法は,対象とするシステムの性質により,以下のように分類されます.

    1. 線形計画法(LP : Linear Programming)
        f(x) 及び gj(x) がすべて線形である場合.

    2. 非線形計画法(NP : Nonlinear Programming)
        f(x) または gj(x) に,非線形の式が含まれる場合.

    3. 組み合わせ最適化(Combinattorial Optimization)
        x の値として,離散的な値だけをとるような式が含まれる場合.似たような問題,または,異なる表現方法として,離散的最適化(Discrete Optimization),組み合わせ計画法(Combinattorial Programming),離散的計画法(Discrete Programming)のようなものがあります.

    4. 遺伝的アルゴリズム(GA : Genetic Algorithm)
        幅広い最適化問題に適用可能な方法です.遺伝的アルゴリズムは,最適化問題だけに使用される方法ではありません.また,その他の面からも,上記 3 つの手法と並列的に並べるには問題がありますが,ここではあえて最適化手法の一つとして話します.

  2. 動的システムの最適化

      システムの時間的な変化を考慮して最適化を行います.例えば,A から B へ向かう飛行機の最短時間経路,燃料を最小にする経路等を求めるような問題が相当します.本来,「制御理論」の範疇で扱われる問題が多くなりますが,ここでは,「制御理論」そのものには言及せず,動的計画法(DP : Dynamic Programming)だけを取り上げます.動的計画法は,必ずしも時間的変化があるシステムの最適化だけを対象にしているわけではありません.かなり幅広い問題に対して適用可能です.詳細に関しては,動的計画法の章を参照してください.

静岡理工科大学 菅沼ホーム SE目次 索引