Diese Seite wurde mithilfe maschineller Übersetzung übersetzt. Klicken Sie hier, um die neueste Version auf Englisch zu sehen.

Nichtlineare Constraint-Solver-Algorithmen für genetische Algorithmen

Erweiterter Lagrangescher genetischer Algorithmus

Standardmäßig verwendet der genetische Algorithmus den Augmented Lagrangian Genetic Algorithm (ALGA), um nichtlineare Beschränkungsprobleme ohne ganzzahlige Beschränkungen zu lösen. Das vom ALGA-Algorithmus gelöste Optimierungsproblem ist

$$\underset{x}{\min }f(x)$$

so dass

$$\begin{array}{c}{\text{ineqnonlin}}_i(x)\le 0,i=1\dots m\\ {\text{eqnonlin}}_i(x)=0,\text{}i=m+1\dots mt\\ A\cdot x\le b\\ \text{Aeq}\cdot x=\text{beq}\\ \text{lb}\le x\le \text{ub},\end{array}$$

wobei c(x) die nichtlinearen Ungleichheitsbeschränkungen darstellt, ceq(x) die Gleichheitsbeschränkungen darstellt, m die Anzahl der nichtlinearen Ungleichheitsbeschränkungen ist und mt die Gesamtzahl der nichtlinearen Beschränkungen ist.

Der Augmented Lagrangian Genetic Algorithm (ALGA) versucht, ein nichtlineares Optimierungsproblem mit nichtlinearen Einschränkungen, linearen Einschränkungen und Grenzen zu lösen. Bei diesem Ansatz werden Grenzen und lineare Einschränkungen getrennt von nichtlinearen Einschränkungen behandelt. Ein Unterproblem wird durch die Kombination der Fitnessfunktion und der nichtlinearen Einschränkungsfunktion unter Verwendung der Lagrange- und der Strafparameter formuliert. Eine Folge solcher Optimierungsprobleme wird mithilfe des genetischen Algorithmus näherungsweise minimiert, sodass die linearen Einschränkungen und Grenzen eingehalten werden.

Eine Teilproblemformulierung wird definiert als

$$\begin{array}{c}\Theta (x,\lambda ,s,\rho )=f(x)-{\displaystyle \sum _{i=1}^m{\lambda }_i}{s}_i\log (s_i-{\text{ineqnonlin}}_i(x))\mathrm{...}\\ +{\displaystyle \sum _{i=m+1}^{mt}{\lambda }_i}{\text{eqnonlin}}_i(x)+\frac{\rho }{2}{\displaystyle \sum _{i=m+1}^{mt}{\text{eqnonlin}}_i}{(}^x,\end{array}$$

wobei

• Die Komponenten λ_i des Vektors λ sind nicht negativ und werden als Lagrange-Multiplikatorschätzungen bezeichnet.

• Die Elemente s_i des Vektors s sind nichtnegative Verschiebungen

• ρ ist der positive Strafparameter.

Der Algorithmus beginnt mit der Verwendung eines Anfangswerts für den Strafparameter (InitialPenalty).

Der genetische Algorithmus minimiert eine Folge von Teilproblemen, von denen jedes eine Annäherung an das ursprüngliche Problem darstellt. Jedes Teilproblem hat einen festen Wert von λ, s und ρ. Wenn das Teilproblem auf die erforderliche Genauigkeit minimiert ist und die Machbarkeitsbedingungen erfüllt, werden die Lagrange-Schätzungen aktualisiert. Andernfalls wird der Strafparameter um einen Straffaktor (PenaltyFactor) erhöht. Dies führt zu einer neuen Teilproblemformulierung und einem neuen Minimierungsproblem. Diese Schritte werden wiederholt, bis die Abbruchkriterien erfüllt sind.

Jede Teilproblemlösung stellt eine Generation dar. Daher ist die Anzahl der Funktionsauswertungen pro Generation bei der Verwendung nichtlinearer Einschränkungen viel höher als sonst.

Wählen Sie den erweiterten Lagrange-Algorithmus, indem Sie die Option NonlinearConstraintAlgorithm mit optimoptions auf 'auglag' setzen.

Eine vollständige Beschreibung des Algorithmus finden Sie in den folgenden Referenzen:

Referenzen

[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.

Strafalgorithmus

Der Strafalgorithmus ähnelt dem Integer ga Algorithm. Bei der Bewertung der Fitness einer Person berechnet ga einen Strafwert wie folgt:

• Wenn das Individuum machbar ist, ist die Straffunktion die Fitnessfunktion.

• Wenn das Individuum nicht durchführbar ist, ist die Straffunktion die maximale Fitnessfunktion unter den durchführbaren Mitgliedern der Population plus der Summe der Beschränkungsverletzungen des (nicht durchführbaren) Individuums.

Einzelheiten zur Straffunktion finden Sie unter Deb [1].

Wählen Sie den Strafalgorithmus, indem Sie die Option NonlinearConstraintAlgorithm mit optimoptions auf 'penalty' setzen. Wenn Sie diese Wahl treffen, löst ga das Problem der eingeschränkten Optimierung wie folgt.

1. ga verwendet standardmäßig die @gacreationnonlinearfeasible-Erstellungsfunktion. Diese Funktion versucht, eine realisierbare Population unter Berücksichtigung aller Einschränkungen zu erstellen. ga erstellt genügend Individuen, um der Option PopulationSize zu entsprechen. Einzelheiten finden Sie unter Penalty Algorithm.

2. ga überschreibt Ihre Wahl der Auswahlfunktion und verwendet @selectiontournament mit zwei Einzelpersonen pro Turnier.

3. ga verfährt analog zu So funktioniert der genetische Algorithmus und verwendet dabei die Straffunktion als Fitnessmaß.

Referenzen

[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.

Siehe auch

Themen

• Terminologie genetischer Algorithmen
• So funktioniert der genetische Algorithmus