このページは機械翻訳を使用して翻訳されました。最新版の英語を参照するには、ここをクリックします。

遺伝的アルゴリズムのための非線形制約ソルバーアルゴリズム

拡張ラグランジュ遺伝的アルゴリズム

デフォルトでは、遺伝的アルゴリズムは拡張ラグランジュ遺伝的アルゴリズム (ALGA) を使用して、整数制約のない非線形制約問題を解決します。ALGAアルゴリズムによって解決される最適化問題は

minxf(x)

条件

ci(x)≤0,  i=1…mceqi(x)=0,  ​i=m+1…mtA⋅x≤bAeq⋅x=beqlb≤x≤ub,

ここで、c(x) は非線形不等式制約を表し、ceq(x) は等式制約を表し、m は非線形不等式制約の数、mt は非線形制約の合計数です。

拡張ラグランジュ遺伝的アルゴリズム (ALGA) は、非線形制約、線形制約、および境界を持つ非線形最適化問題を解決しようとします。このアプローチでは、境界と線形制約は非線形制約とは別に処理されます。ラグランジュとペナルティパラメーターを使用して、適応度関数と非線形制約関数を組み合わせることによってサブ問題が定式化されます。このような一連の最適化問題は、線形制約と境界が満たされるように遺伝的アルゴリズムを使用して近似的に最小化されます。

部分問題の定式化は次のように定義される。

Θ(x,λ,s,ρ)=f(x)−∑i=1mλisilog(si−ci(x))+∑i=m+1mtλiceqi(x)+ρ2∑i=m+1mtceqi(x)2,

ここで、

  • ベクトルλの成分λiは非負であり、ラグランジュ乗数推定値として知られている。

  • ベクトルsの要素siは非負のシフトである

  • ρ は正のペナルティパラメーターです。

アルゴリズムは、ペナルティパラメーター(InitialPenalty) の初期値を使用して開始されます。

遺伝的アルゴリズムは、一連のサブ問題（それぞれが元の問題の近似値）を最小化します。各サブ問題には、λ、s、および ρ の固定値があります。サブ問題が必要な精度まで最小化され、実現可能性条件を満たすと、ラグランジュ推定値が更新されます。それ以外の場合、ペナルティパラメーターはペナルティ係数 (PenaltyFactor) によって増加されます。これにより、新しいサブ問題の定式化と最小化問題が生じます。停止基準が満たされるまでこれらの手順が繰り返されます。

各サブ問題の解決は 1 つの世代を表します。したがって、非線形制約を使用する場合、世代ごとの関数評価の回数は、そうでない場合よりもはるかに多くなります。

optimoptions を使用して NonlinearConstraintAlgorithm オプションを 'auglag' に設定して、拡張ラグランジュアルゴリズムを選択します。

アルゴリズムの詳細な説明については、次の参考資料を参照してください。

参照

[1] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. “A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds,” SIAM Journal on Numerical Analysis, Volume 28, Number 2, pages 545–572, 1991.

[2] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. “A Globally Convergent Augmented Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds,” Mathematics of Computation, Volume 66, Number 217, pages 261–288, 1997.

ペナルティアルゴリズム

ペナルティ アルゴリズムは 整数gaアルゴリズム に似ています。ga は、個体の適応度を評価する際に、次のようにペナルティ値を計算します。

  • 個体が実行可能である場合、ペナルティ関数は適応度関数です。

  • 個体が実行不可能な場合、ペナルティ関数は、母集団の実行可能なメンバー間の最大適応度関数と、（実行不可能な）個体の制約違反の合計になります。

ペナルティ関数の詳細については、Deb [1] を参照してください。

optimoptions を使用して NonlinearConstraintAlgorithm オプションを 'penalty' に設定して、ペナルティ アルゴリズムを選択します。この選択を行うと、ga は制約付き最適化問題を次のように解決します。

  1. ga はデフォルトで @gacreationnonlinearfeasible 作成関数になります。この関数は、すべての制約を考慮して実現可能な母集団を作成しようとします。ga は、PopulationSize オプションに一致するのに十分な個体を作成します。詳細は、ペナルティアルゴリズムを参照してください。

  2. ga は選択機能の選択を無効にし、トーナメントごとに 2 つの個体で @selectiontournament を使用します。

  3. ga は、ペナルティ関数を適応度尺度として使用して、遺伝的アルゴリズムの仕組み に従って進行します。

参照

[1] Deb, Kalyanmoy. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2–4), pp. 311–338, 2000.

参考

トピック