Algoritmos genéticos - Introducción
El algoritmo genético (GA) es una técnica de optimización basada en búsquedas basada en los principios de Genetics and Natural Selection. Se utiliza con frecuencia para encontrar soluciones óptimas o casi óptimas a problemas difíciles que, de otro modo, llevaría toda una vida resolverlos. Se utiliza con frecuencia para resolver problemas de optimización, en investigación y en aprendizaje automático.
Introducción a la optimización
La optimización es el proceso de making something better. En cualquier proceso, tenemos un conjunto de entradas y un conjunto de salidas como se muestra en la siguiente figura.
La optimización se refiere a encontrar los valores de las entradas de tal manera que obtengamos los "mejores" valores de salida. La definición de "mejor" varía de un problema a otro, pero en términos matemáticos, se refiere a maximizar o minimizar una o más funciones objetivas, variando los parámetros de entrada.
El conjunto de todas las posibles soluciones o valores que pueden tomar las entradas conforma el espacio de búsqueda. En este espacio de búsqueda, se encuentra un punto o un conjunto de puntos que dan la solución óptima. El objetivo de la optimización es encontrar ese punto o conjunto de puntos en el espacio de búsqueda.
¿Qué son los algoritmos genéticos?
La naturaleza siempre ha sido una gran fuente de inspiración para toda la humanidad. Los algoritmos genéticos (GA) son algoritmos basados en búsquedas que se basan en los conceptos de selección natural y genética. Los GA son un subconjunto de una rama mucho mayor de la computación conocida comoEvolutionary Computation.
Los GA fueron desarrollados por John Holland y sus estudiantes y colegas de la Universidad de Michigan, sobre todo David E. Goldberg y desde entonces se han probado en varios problemas de optimización con un alto grado de éxito.
En GA, tenemos un pool or a population of possible solutionsal problema dado. Estas soluciones luego se someten a recombinación y mutación (como en la genética natural), produciendo nuevos hijos, y el proceso se repite durante varias generaciones. A cada individuo (o solución candidata) se le asigna un valor de aptitud (basado en su valor de función objetivo) y los individuos más aptos tienen una mayor probabilidad de aparearse y producir más individuos “más aptos”. Esto está en consonancia con la teoría darwiniana de la "supervivencia del más apto".
De esta manera, seguimos “evolucionando” mejores personas o soluciones a lo largo de generaciones, hasta alcanzar un criterio de parada.
Los algoritmos genéticos son de naturaleza suficientemente aleatoria, pero funcionan mucho mejor que la búsqueda local aleatoria (en la que solo probamos varias soluciones aleatorias, realizando un seguimiento de las mejores hasta ahora), ya que también explotan información histórica.
Ventajas de los GA
Los GA tienen varias ventajas que los han hecho inmensamente populares. Estos incluyen:
No requiere ninguna información derivada (que puede no estar disponible para muchos problemas del mundo real).
Es más rápido y eficiente en comparación con los métodos tradicionales.
Tiene muy buenas capacidades en paralelo.
Optimiza tanto funciones continuas como discretas y también problemas multiobjetivo.
Proporciona una lista de "buenas" soluciones y no una única solución.
Siempre obtiene una respuesta al problema, que mejora con el tiempo.
Útil cuando el espacio de búsqueda es muy grande y hay una gran cantidad de parámetros involucrados.
Limitaciones de los GA
Como cualquier técnica, los AG también adolecen de algunas limitaciones. Estos incluyen:
Los GA no son adecuados para todos los problemas, especialmente los problemas que son simples y para los que se dispone de información derivada.
El valor de aptitud se calcula repetidamente, lo que puede resultar computacionalmente costoso para algunos problemas.
Al ser estocástico, no existen garantías sobre la optimalidad o la calidad de la solución.
Si no se implementa correctamente, es posible que la GA no converja hacia la solución óptima.
GA - Motivación
Los algoritmos genéticos tienen la capacidad de ofrecer una solución "suficientemente buena" y "suficientemente rápida". Esto hace que los algoritmos genéticos sean atractivos para su uso en la resolución de problemas de optimización. Las razones por las que se necesitan AG son las siguientes:
Resolver problemas difíciles
En informática, existe un gran conjunto de problemas, que son NP-Hard. Lo que esto significa esencialmente es que, incluso los sistemas informáticos más potentes, tardan mucho tiempo (¡incluso años!) En resolver ese problema. En tal escenario, los GA demuestran ser una herramienta eficiente para proporcionarusable near-optimal solutions en poco tiempo.
Fracaso de los métodos basados en gradientes
Los métodos tradicionales basados en cálculo funcionan comenzando en un punto aleatorio y moviéndose en la dirección del gradiente, hasta llegar a la cima de la colina. Esta técnica es eficiente y funciona muy bien para funciones de objetivo de un solo pico como la función de costo en regresión lineal. Pero, en la mayoría de las situaciones del mundo real, tenemos un problema muy complejo llamado paisajes, que están formados por muchos picos y muchos valles, lo que hace que esos métodos fallen, ya que sufren una tendencia inherente a quedarse atascados en los óptimos locales. como se muestra en la siguiente figura.
Obtener una buena solución rápidamente
Algunos problemas difíciles, como el problema del vendedor ambulante (TSP), tienen aplicaciones del mundo real, como la búsqueda de rutas y el diseño VLSI. Ahora imagine que está utilizando su sistema de navegación GPS y que se necesitan unos minutos (o incluso algunas horas) para calcular la ruta "óptima" desde el origen hasta el destino. El retraso en tales aplicaciones del mundo real no es aceptable y, por lo tanto, lo que se requiere es una solución "suficientemente buena", que se entregue "rápido".