Por lo que entiendo, los algoritmos genéticos prueban múltiples variaciones y evalúan la idoneidad de cada variación. Luego seleccionan las mejores variaciones, las cambian un poco y continúan el proceso con la próxima generación.
Pero, ¿qué pasa si tenemos recursos informáticos ilimitados? ¿Podemos entonces probar todas las variaciones posibles y evaluar su estado físico sin recurrir al complejo proceso de criar nuevas generaciones? En otras palabras, ¿solo se necesitan algoritmos genéticos cuando el cálculo es costoso y cuando un método de fuerza bruta es imposible? ¿O añaden también otros beneficios?
genetic-algorithms
Eugene
fuente
fuente
Respuestas:
Los algoritmos genéticos son básicamente una metodología guiada de prueba y error. La única ventaja que se me ocurre para un GA sobre una búsqueda exhaustiva es que, dado que GA optimiza una función de forma física por pasos, es posible que obtenga una solución óptima más rápido, porque el GA favorecerá soluciones que sean incrementalmente mejores. Una búsqueda exhaustiva que garantice encontrar una solución podría ser de gran ayuda.
Si "recursos de cómputo" significa CPU pero no memoria, entonces el conjunto de genes GA podría tener una huella de memoria menor, requiriendo menos memoria.
Por otro lado, debido a la escalada, una GA podría quedar atrapada en un máximo local y cualquier mutación podría no ser suficiente para soltarla.
Además, el tiempo de búsqueda de GA aumenta exponencialmente con el tamaño de la entrada, por lo que una búsqueda exhaustiva puede terminar siendo más rápida después de todo, dependiendo del tamaño del espacio que está buscando y si puede restringir el tamaño del espacio excluyendo posibilidades.
...
Últimamente he estado pensando en GA en términos de "entropía por segundo" y midiendo el progreso de mi GA como una medida de cuántas posibilidades distintas atraviesa por segundo. Entonces puedo comparar eso con la entropía total del espacio del problema. Si una búsqueda de fuerza bruta puede superar esa entropía por segundo con paralelización o procesadores rápidos, entonces el "mejor puntaje" de un GA no es mejor que un "mejor puntaje" descubierto.
Pero acabo de decir eso; Todavía no he instrumentado un GA de esa manera.
(La entropía es
ln(N)para N estados posibles, oln(N) - sum(n * ln(n) for all n) / Ndóndenestán las formas posibles de lograr un resultado de N resultados posibles).Interesante pregunta :)
fuente
Sí, si el cómputo fuera gratis, entonces no necesitarías algoritmos genéticos en absoluto. ¡Pero recuerda que este es un enorme "enorme" si ninguno de nosotros vivirá para verlo!
Aún así, ya que está preguntando ... si el cálculo fue infinitamente rápido, no habría razón alguna para no aplicar el martillo combinatorio de generación y prueba de fuerza bruta más simple a un problema. Cada pregunta que pueda responderse con un conjunto finito de información (es decir, un problema de satisfacción de restricciones en el sentido más amplio posible de ese término, que es bastante laxo) podría resolverse instantáneamente; escalada, heurística y todas las simplificaciones inteligentes que ahora utilizamos para construir, por ejemplo, un motor de ajedrez de clase mundial simplemente no sería necesario.
Dicho de otra manera, si el cálculo se aproxima a la velocidad infinita, la decisión sobre qué enfoque utilizar se basa en lo difícil que es escribir el programa de computadora que se ejecutará, no en cuánto tiempo se tarda en ejecutarlo; y eso significa que simplemente no vale la pena inventar un algoritmo más complicado cuando el más simple posible también funcionará y se ejecutará al mismo tiempo.
Podría decirse que la computación realmente se ha estado moviendo en esta dirección, pero nuevamente, recuerde, que todavía no estamos allí, y probablemente nunca lo estaremos. (A menos que la computadora cuántica se perfeccione, por supuesto).
fuente
El problema con los cálculos infinitamente rápidos es que cubren infinitamente un espacio de estado que es más grande que el límite de información de nuestro universo conocido. Usted mencionó "fuerza bruta", sin embargo, considere que el ajedrez de fuerza bruta, por ejemplo, puede producir una salida que excede en tamaño el número de átomos en el universo.
Llevando el ejemplo del ajedrez más allá, a medida que el ajedrez de fuerza bruta, tienes que reducir la cantidad de combinaciones de tablero de ajedrez que consideras y tendrás que tomar una decisión sobre qué estados mantener y qué estados descartar, por lo tanto, algoritmos selectivos, como los algoritmos genéticos, siempre serán necesarios.
fuente
Si por "recursos de cómputo ilimitados" quiere decir que su algoritmo tardaría 0 veces y que la memoria es ilimitada y la electricidad no es una preocupación, diría que el único algoritmo a utilizar sería un algoritmo de fuerza bruta que intente todas las entradas posibles y esté garantizado para encontrar el mejor. Si se refiere a memoria ilimitada pero se requiere una posible diferencia de tiempo, entonces un algoritmo genético podría ser preferible porque podría llegar a una solución más rápida que un algoritmo de fuerza bruta. Pero la solución del algoritmo genético puede no ser óptima, por lo que, dependiendo del contexto y sus requisitos, es posible que prefiera el método de fuerza bruta.
Dado que los recursos de cómputo ilimitados no son posibles, la pregunta al principio parecía una especulación inactiva. Pero a medida que obtenemos más y más potencia computacional, la pregunta se vuelve más relevante porque es posible que no necesitemos algoritmos genéticos en una era de enormes supercomputadoras. Sin embargo, he notado que incluso a medida que las computadoras se vuelven más poderosas, seguimos pidiéndoles que hagan cálculos cada vez más difíciles con cada vez más datos. Entonces, al final, creo que los algoritmos genéticos estarán con nosotros en el futuro previsible y se usarán incluso cuando haya mucha potencia informática disponible.
Sin embargo, si los recursos de cómputo verdaderamente ilimitados alguna vez estuvieran disponibles, cambiaría mucho más que usar o no algoritmos genéticos.
fuente