Algoritmos genéticos de programación y búsqueda

Question

¿La programación genética actualmente es capaz de evolucionar un tipo de algoritmo de búsqueda a otro? Por ejemplo, cualquier experimento que alguna vez haya creado/mutado BubbleSort de QuickSort (vea http://en.wikipedia.org/wiki/Sorting_algorithm)

Answer 1

No conozco ninguno, y la dirección particular que está sugiriendo en su ejemplo parece improbable; tomaría una especie de función de aptitud perversa, ya que el ordenamiento de burbujas es en la mayoría de las medidas peor que en el orden rápido. No es inconcebible que esto pueda suceder, pero en general una vez que tienes un algoritmo bien entendido, ya está bastante en forma; ir a otro probablemente requiera pasar por algunas decisiones peores.

Estar atrapado en los mínimos locales no es un problema desconocido para la mayoría de las estrategias de búsqueda.

Answer 2

No hay ninguna razón por la que GP no pueda evolucionar, p. cualquier tipo de algoritmo. No estoy seguro de que realmente tenga sentido pensar en evolucionar uno "hacia" el otro. GP simplemente desarrollará un programa que se acerca cada vez más a una función de acondicionamiento físico que usted defina.

Si su función de acondicionamiento físico solo tiene en cuenta la corrección de clasificación (y suponiendo que tiene los componentes adecuados para su GP), podría evolucionar tanto BubbleSort como QuickSort. Si también incluye la eficiencia como una medida de la aptitud, entonces eso podría influir en cuál de estos se determinaría como una mejor solución.

Puede sembrar el GP con p. Ej. QuickSort y si tuvieras una función de acondicionamiento físico adecuada, con el tiempo podría surgir BubbleSort, pero podría aparecer con cualquier otra cosa que sea más adecuada que QuickSort.

Ahora el tiempo que tarda el motor GP de hacer esta evolución es otra cuestión ...

Answer 3

Es posible que desee ver en la obra de W. Daniel Hillis de los años 80. Pasó una gran cantidad de tiempo creando redes de clasificación mediante programación genética. Si bien estaba más interesado en resolver el problema de clasificar una cantidad constante de objetos (las redes de clasificación de 16 objetos habían sido un gran problema académico durante casi una década), sería una buena idea familiarizarse con su trabajo si realmente interesado en algoritmos de clasificación genética.

En la evolución de un algoritmo para ordenar una lista de longitud arbitraria, es posible que también desee familiarizarse con el concepto de coevolución. He construido un sistema coevolutivo antes de que el punto fuera tener un algoritmo genético que desarrollara algoritmos de clasificación, mientras que otro GA desarrolla listas de números sin clasificar. La idoneidad del clasificador es su precisión (más una bonificación para menos comparaciones si es 100% exacto) y la idoneidad del generador de listas es la cantidad de errores que los algoritmos de ordenación hacen al clasificar su lista.

Para responder a su pregunta específica de si la burbuja se ha desarrollado alguna vez de rápida, tendría que decir que la pondría seriamente en duda, a menos que la función de aptitud del programador fuera a la vez muy específica y desacertada. Sí, la burbuja es muy simple, así que tal vez un médico de cabecera cuya función de acondicionamiento físico era la precisión más el tamaño del programa eventualmente encontraría burbujas. Sin embargo, ¿por qué un programador seleccionaría el tamaño en lugar del número de comparaciones como una función de aptitud física cuando es el último el que determina el tiempo de ejecución?

Al preguntar si GP puede evolucionar un algoritmo a otro, me pregunto si está completamente seguro de qué GP es. Idealmente, cada cromosoma único define un tipo único. Una población de 200 cromosomas representa 200 algoritmos diferentes. Sí, rápido y burbuja puede estar allí en alguna parte, pero también lo son otros 198 métodos, posiblemente sin nombre.