Cette page a été traduite par traduction automatique. Cliquez ici pour voir la dernière version en anglais.

Algorithmes de résolution de contraintes non linéaires pour algorithmes génétiques

Algorithme génétique lagrangien augmenté

Par défaut, l'algorithme génétique utilise l'algorithme génétique lagrangien augmenté (ALGA) pour résoudre les problèmes de contraintes non linéaires sans contraintes entières. Le problème d'optimisation résolu par l'algorithme ALGA est

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

tel que

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

où c(x) représente les contraintes d'inégalité non linéaire, ceq(x) représente les contraintes d'égalité, m est le nombre de contraintes d'inégalité non linéaire et mt est le nombre total de contraintes non linéaires.

L'algorithme génétique lagrangien augmenté (ALGA) tente de résoudre un problème d'optimisation non linéaire avec des contraintes non linéaires, des contraintes linéaires et des limites. Dans cette approche, les limites et les contraintes linéaires sont traitées séparément des contraintes non linéaires. Un sous-problème est formulé en combinant la fonction fitness et la fonction de contrainte non linéaire en utilisant le lagrangien et les paramètres de pénalité. Une séquence de tels problèmes d'optimisation est approximativement minimisée à l'aide de l'algorithme génétique de telle sorte que les contraintes et les limites linéaires soient satisfaites.

Une formulation de sous-problème est définie comme

$$\Theta (x,\lambda ,s,\rho )=f(x)-{\displaystyle \sum _{i=1}^m{\lambda }_i}{s}_i\log (s_i-c_i(x))+{\displaystyle \sum _{i=m+1}^{mt}{\lambda }_i}ce{q}_i(x)+\frac{\rho }{2}{\displaystyle \sum _{i=m+1}^{mt}ce{q}_i}{(x)}^2,$$

où

• Les composantes λ_i du vecteur λ sont non négatives et sont appelées estimations du multiplicateur de Lagrange

• Les éléments s_i du vecteur s sont des décalages non négatifs

• ρ est le paramètre de pénalité positive.

L'algorithme commence par utiliser une valeur initiale pour le paramètre de pénalité (InitialPenalty).

L'algorithme génétique minimise une séquence de sous-problèmes, chacun étant une approximation du problème d'origine. Chaque sous-problème a une valeur fixe de λ, s et ρ. Lorsque le sous-problème est minimisé à une précision requise et satisfait les conditions de faisabilité, les estimations lagrangiennes sont mises à jour. Dans le cas contraire, le paramètre de pénalité est augmenté d’un facteur de pénalité (PenaltyFactor). Cela donne lieu à une nouvelle formulation de sous-problème et à un problème de minimisation. Ces étapes sont répétées jusqu’à ce que les critères d’arrêt soient remplis.

Chaque solution de sous-problème représente une génération. Le nombre d'évaluations de fonctions par génération est donc beaucoup plus élevé lors de l'utilisation de contraintes non linéaires que dans le cas contraire.

Choisissez l'algorithme Lagrangien augmenté en définissant l'option NonlinearConstraintAlgorithm sur 'auglag' à l'aide de optimoptions.

Pour une description complète de l'algorithme, voir les références suivantes :

Références

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

Algorithme de pénalité

L'algorithme de pénalité est similaire à Integer ga Algorithm. Dans son évaluation de l'aptitude d'un individu, ga calcule une valeur de pénalité comme suit :

• Si l’individu est faisable, la fonction de pénalité est la fonction fitness.

• Si l'individu est irréalisable, la fonction de pénalité est la fonction fitness maximale parmi les membres réalisables de la population, plus une somme des violations de contraintes de l'individu (irréalisable).

Pour plus de détails sur la fonction de pénalité, voir Deb [1].

Choisissez l'algorithme de pénalité en définissant l'option NonlinearConstraintAlgorithm sur 'penalty' en utilisant optimoptions. Lorsque vous faites ce choix, ga résout le problème d’optimisation sous contrainte comme suit.

1. ga utilise par défaut la fonction de création @gacreationnonlinearfeasible. Cette fonction tente de créer une population réalisable par rapport à toutes les contraintes. ga crée suffisamment d'individus pour correspondre à l'option PopulationSize. Pour plus de détails, voir Penalty Algorithm.

2. ga remplace votre choix de fonction de sélection et utilise @selectiontournament avec deux individus par tournoi.

3. ga procède selon Comment fonctionne l'algorithme génétique, en utilisant la fonction de pénalité comme mesure de fitness.

Références

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

Voir aussi

Rubriques

• Genetic Algorithm Terminology
• Comment fonctionne l'algorithme génétique