Algoritmos genéticos - Temas avanzados
En esta sección, presentamos algunos temas avanzados en algoritmos genéticos. Un lector que busque solo una introducción a los GA puede optar por saltarse esta sección.
Problemas de optimización restringida
Los problemas de optimización restringida son aquellos problemas de optimización en los que tenemos que maximizar o minimizar un valor de función objetivo dado que está sujeto a ciertas restricciones. Por lo tanto, no todos los resultados en el espacio de la solución son factibles y el espacio de la solución contiene regiones factibles como se muestra en la siguiente imagen.
En tal escenario, los operadores de cruce y mutación podrían darnos soluciones que son inviables. Por lo tanto, se deben emplear mecanismos adicionales en el GA cuando se trata de problemas de optimización restringidos.
Algunos de los métodos más comunes son:
Utilizando penalty functions lo que reduce la idoneidad de las soluciones inviables, preferiblemente de modo que la idoneidad se reduzca en proporción al número de restricciones violadas o la distancia de la región factible.
Utilizando repair functions que toman una solución inviable y la modifican para que se satisfagan las restricciones violadas.
Not allowing infeasible solutions entrar en la población en absoluto.
Utilizar una special representation or decoder functions que asegura la viabilidad de las soluciones.
Antecedentes teóricos básicos
En esta sección, analizaremos el teorema del esquema y la NFL junto con la hipótesis de los bloques de construcción.
Teorema del esquema
Los investigadores han estado tratando de descubrir las matemáticas detrás del funcionamiento de los algoritmos genéticos, y el teorema del esquema de Holland es un paso en esa dirección. Durante el año, se han realizado varias mejoras y sugerencias al Teorema del esquema para hacerlo más general.
En esta sección, no profundizamos en las matemáticas del Teorema de esquema, sino que intentamos desarrollar una comprensión básica de qué es el Teorema de esquema. La terminología básica que debe conocer es la siguiente:
UNA Schemaes una "plantilla". Formalmente, es una cadena sobre el alfabeto = {0,1, *},
donde * es no importa y puede tomar cualquier valor.
Por lo tanto, * 10 * 1 podría significar 01001, 01011, 11001 o 11011
Geométricamente, un esquema es un hiperplano en el espacio de búsqueda de soluciones.
Order de un esquema es el número de posiciones fijas especificadas en un gen.
Defining length es la distancia entre los dos símbolos fijos más lejanos del gen.
El teorema del esquema establece que este esquema con aptitud superior a la media, longitud de definición corta y orden inferior tiene más probabilidades de sobrevivir al cruce y la mutación.
Hipótesis de bloques de construcción
Los Building Blocks son esquemas de longitud de baja definición y orden bajo con la aptitud promedio dada anteriormente. La hipótesis de los bloques de construcción dice que dichos bloques de construcción sirven como base para el éxito y la adaptación de los AG a medida que avanza identificando y recombinando sucesivamente dichos "bloques de construcción".
Teorema de no almuerzo gratis (NFL)
Wolpert y Macready en 1997 publicaron un artículo titulado "No hay teoremas de almuerzo gratis para la optimización". Básicamente, establece que si promediamos el espacio de todos los problemas posibles, entonces todos los algoritmos de caja negra que no revisen exhibirán el mismo rendimiento.
Significa que cuanto más entendemos un problema, nuestra GA se vuelve más específica del problema y ofrece un mejor rendimiento, pero lo compensa con un mal rendimiento para otros problemas.
Aprendizaje automático basado en GA
Los algoritmos genéticos también encuentran aplicación en el aprendizaje automático. Classifier systems son una forma de genetics-based machine learning(GBML) que se utilizan con frecuencia en el campo del aprendizaje automático. Los métodos GBML son un enfoque de nicho para el aprendizaje automático.
Hay dos categorías de sistemas GBML:
The Pittsburg Approach - En este enfoque, un cromosoma codifica una solución, por lo que se asigna aptitud a las soluciones.
The Michigan Approach - una solución suele estar representada por muchos cromosomas y, por tanto, se asigna aptitud a las soluciones parciales.
Debe tenerse en cuenta que el tema estándar como crossover, mutación, lamarckiano o darwiniano, etc. también está presente en los sistemas GBML.