Red neuronal artificial - Algoritmo genético
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 más grande del cálculo conocida comoEvolutionary Computation.
El GA fue desarrollado por John Holland y sus estudiantes y colegas de la Universidad de Michigan, sobre todo David E. Goldberg, y desde entonces se ha probado en varios problemas de optimización con un alto grado de éxito.
En los GA, tenemos un grupo o una población de posibles soluciones al 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 que alcanzamos un criterio de parada.
Los algoritmos genéticos son de naturaleza suficientemente aleatoria; sin embargo, 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 funciones continuas y discretas, así como 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 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 Gas sea atractivo 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, hay 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. Sin embargo, en la mayoría de las situaciones del mundo real, tenemos un problema muy complejo llamado paisajes, formado por muchos picos y muchos valles, que hace que estos 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. La demora 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 entrega "rápido".
¿Cómo utilizar GA para problemas de optimización?
Ya sabemos que la optimización es una acción para hacer que algo como el diseño, la situación, los recursos y el sistema sean lo más efectivos posible. El proceso de optimización se muestra en el siguiente diagrama.
Etapas del mecanismo de GA para el proceso de optimización
Las siguientes son las etapas del mecanismo GA cuando se utiliza para la optimización de problemas.
Genere la población inicial al azar.
Seleccione la solución inicial con los mejores valores de aptitud.
Recombina las soluciones seleccionadas utilizando operadores de mutación y cruzamiento.
Inserta descendencia en la población.
Ahora, si se cumple la condición de detención, devuelva la solución con su mejor valor de aptitud. De lo contrario, vaya al paso 2.