¿Se necesita un algoritmo genético cuando el cálculo es infinitamente rápido?

8

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?

Eugene
fuente
1
Marqué esto como perteneciente a Stackoverflow, pero en mi opinión pertenece al sitio de Ciencias de la Computación (para el que no hay una opción en el asistente de marcado). (Pero todavía voté; ¡pregunta interesante!)
Patrick M
55
Si tiene memoria infinita y cómputo infinitamente rápido, puede generar todos los estados posibles del sistema, luego evaluar cada estado y elegir los ideales, o concluir que ninguno de los estados posibles es satisfactorio. "Infinito" hace que toda la pregunta sea inútil. Bueno, excepto si el espacio del problema también es infinito, pero estamos muy lejos de cualquier cosa que un "programador" pueda hacer.
hyde

Respuestas:

14

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, o ln(N) - sum(n * ln(n) for all n) / Ndónde nestán las formas posibles de lograr un resultado de N resultados posibles).

Interesante pregunta :)

Robar
fuente
1
¿Esta pregunta de entropía no se reduce básicamente a "los AG a menudo repiten estados y la fuerza bruta nunca lo hace"? La forma en que tiendo a pensarlo es que un algoritmo de búsqueda define y se define por una permutación sobre el espacio de la solución. En resumen, un algoritmo de búsqueda no es más que el orden en que visita los puntos (módulo de algunos gastos generales debido a evaluaciones repetidas). Los teoremas de la NFL tienen perfecto sentido entonces: siempre puedo construir un problema para el cual mi algoritmo encontrará el óptimo antes que el tuyo y viceversa.
deong
1
@deong En muchos casos, los estados mejores, o incluso los estados óptimos, pueden ser rechazados ocasionalmente (por ejemplo, sistemas no deterministas), por lo que puede ser necesario buscar casos repetidamente.
resgh
1
Yo diría que hay algo más que esto; en primer lugar, mientras que la pregunta presupone "recursos de cómputo ilimitados", los GA se usan típicamente donde la búsqueda exhaustiva es completamente inviable (estamos hablando de "esperar a que el universo termine" inviable aquí, al cual te acercas rápidamente con cualquier problema interesante). En segundo lugar, los GA tienen un operador cruzado, además de una mutación antigua simple; para ciertos tipos de problemas (retención de la NFL), esta es una muy buena heurística, y mucho mejor que una búsqueda exhaustiva. El resto, estoy de acuerdo en gran medida.
Daniel B
44
Los GA generalmente no se usan para encontrar soluciones óptimas. Son para encontrar soluciones razonables dado un tiempo limitado.
Cruncher
1
El recocido simulado es una variación del algoritmo genético que aborda el problema local de máximos / mínimos de manera muy efectiva.
recursion.ninja
6

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

Kilian Foth
fuente
3
Incluso si las computadoras cuánticas se perfeccionan, sospechamos (pero aún no sabemos con certeza) que NP-Complete no es un subconjunto de BQP. Si es cierto, esto significa que la clase de problemas que puede resolver una computadora cuántica con alta probabilidad en tiempo polinómico no incluye los problemas de optimización NP-hard para los que generalmente se usaría un GA.
deong
1
Hay una consecuencia mucho mayor con la velocidad de cálculo infinita ... Por ejemplo, todos los problemas reconocibles ahora se vuelven decidibles. Yay por el problema de detención!
Cruncher
3

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.

pregunta al colectivo
fuente
1
Bueno, a menos que la física extraña, como las curvas cerradas parecidas al tiempo (cerca del final), funcionen y puedan explotarse para el cálculo de propósito general.
En realidad, GA no es bueno para el ajedrez. Poda heurística, sí
Konrad Morawski
Me recuerda a esta historia ... La primera vez que la leí, estaba confundido por qué escribir una rutina de búsqueda tomó tanto tiempo, me tomó un tiempo darme cuenta de que el aspecto de "búsqueda" era diferente del aspecto de "simulación". .
pandubear
2

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.

Paul J Abernathy
fuente
En la línea de "no necesitar mejores algoritmos" o lo que tenga en el futuro porque nuestras máquinas son tan potentes: a menudo pienso en pequeñas optimizaciones que se hicieron en las primeras CPU como la canalización. Parece trivial para nosotros ganar algunos ciclos de reloj adicionales hoy en día, pero esos ciclos se suman. Creo que es crucial seguir haciendo estas pequeñas optimizaciones para ayudarnos a impulsarnos hacia computadoras súper rápidas en el futuro. Sin ellos, solo tendríamos computadoras un poco rápidas.
DLeh