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

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

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

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

$\min_{x} f (x)$

条件

$\begin{matrix} c_{i} (x) \leq 0, i = 1 \dots m \\ c e q_{i} (x) = 0, i = m + 1 \dots m t \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b, \end{matrix}$

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

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

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

$Θ (x, λ, s, ρ) = f (x) - \sum_{i = 1}^{m} λ_{i} s_{i} \log (s_{i} - c_{i} (x)) + \sum_{i = m + 1}^{m t} λ_{i} c e q_{i} (x) + \frac{ρ}{2} \sum_{i = m + 1}^{m t} c e q_{i} {(x)}^{2},$

ここで、

ベクトルλの成分λ_iは非負であり、ラグランジュ乗数推定値として知られている。
ベクトルsの要素s_iは非負のシフトである
ρ は正のペナルティパラメータです。

アルゴリズムは、ペナルティパラメータ (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 は制約付き最適化問題を次のように解決します。

ga はデフォルトで @gacreationnonlinearfeasible 作成関数になります。この関数は、すべての制約に関して実現可能な集団を作成しようとします。ga は、PopulationSize オプションに一致する十分な個体を作成します。詳細については、ペナルティアルゴリズムを参照してください。
ga は選択機能の選択を無効にし、トーナメントごとに 2 人の個人で @selectiontournament を使用します。
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.