Esta página se ha traducido mediante traducción automática. Haga clic aquí para ver la última versión en inglés.

Algoritmos de resolución de restricciones no lineales para algoritmos genéticos

Algoritmo genético lagrangiano aumentado

De forma predeterminada, el algoritmo genético utiliza el Algoritmo Genético Lagrangiano Aumentado (ALGA) para resolver problemas de restricciones no lineales sin restricciones de números enteros. El problema de optimización resuelto por el algoritmo ALGA es

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

de forma 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}$$

donde c(x) representa las restricciones de desigualdad no lineal, ceq(x) representa las restricciones de igualdad, m es el número de restricciones de desigualdad no lineal y mt es el número total de restricciones no lineales.

El algoritmo genético lagrangiano aumentado (ALGA) intenta resolver un problema de optimización no lineal con restricciones no lineales, restricciones lineales y límites. En este enfoque, los límites y las restricciones lineales se manejan por separado de las restricciones no lineales. Se formula un subproblema combinando la función de aptitud y la función de restricción no lineal utilizando el lagrangiano y los parámetros de penalización. Una secuencia de tales problemas de optimización se minimiza aproximadamente utilizando el algoritmo genético de modo que se satisfacen las restricciones y límites lineales.

Una formulación de subproblema se define como

$$\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,$$

donde

• Los componentes λ_i del vector λ no son negativos y se conocen como estimaciones del multiplicador de Lagrange.

• Los elementos s_i del vector s son desplazamientos no negativos

• ρ es el parámetro de penalización positiva.

El algoritmo comienza utilizando un valor inicial para el parámetro de penalización (InitialPenalty).

El algoritmo genético minimiza una secuencia de subproblemas, cada uno de los cuales es una aproximación del problema original. Cada subproblema tiene un valor fijo de λ, s y ρ. Cuando el subproblema se minimiza a una precisión requerida y satisface las condiciones de viabilidad, se actualizan las estimaciones lagrangianas. De lo contrario, el parámetro de penalización se incrementa en un factor de penalización (PenaltyFactor). Esto da como resultado una nueva formulación de subproblema y un problema de minimización. Estos pasos se repiten hasta que se cumplan los criterios de detención.

Cada solución de subproblema representa una generación. Por lo tanto, el número de evaluaciones de funciones por generación es mucho mayor cuando se utilizan restricciones no lineales que en otros casos.

Elija el algoritmo Lagrangiano aumentado estableciendo la opción NonlinearConstraintAlgorithm en 'auglag' usando optimoptions.

Para una descripción completa del algoritmo, consulte las siguientes referencias:

Referencias

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

Algoritmo de penalización

El algoritmo de penalización es similar al Integer ga Algorithm. En su evaluación de la aptitud de un individuo, ga calcula un valor de penalización de la siguiente manera:

• Si el individuo es factible, la función de penalización es la función de aptitud.

• Si el individuo es inviable, la función de penalización es la función de aptitud máxima entre los miembros factibles de la población, más una suma de las violaciones de las restricciones del individuo (inviable).

Para obtener detalles de la función de penalización, consulte Deb [1].

Elija el algoritmo de penalización estableciendo la opción NonlinearConstraintAlgorithm en 'penalty' usando optimoptions . Al realizar esta elección, ga resuelve el problema de optimización restringida de la siguiente manera.

1. ga tiene como valor predeterminado la función de creación @gacreationnonlinearfeasible. Esta función intenta crear una población factible con respecto a todas las restricciones. ga crea suficientes individuos para que coincidan con la opción PopulationSize. Para obtener más detalles, consulte Penalty Algorithm.

2. ga anula su elección de función de selección y utiliza @selectiontournament con dos personas por torneo.

3. ga procede de acuerdo con Cómo funciona el algoritmo genético, utilizando la función de penalización como medida de aptitud.

Referencias

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

Consulte también

Temas

• Terminología de algoritmos genéticos
• Cómo funciona el algoritmo genético