Saltar al contenido
07/13/2020 / José Quintás Alonso

Red neuronal diseña algoritmo

“El aprendizaje automático con redes de neuronas artificiales se puede usar para optimizar algoritmos, la llamada inducción neuronal de programas. Se publica en arXiv un algoritmo de ordenación diseñado mediante aprendizaje con refuerzo que parece ser más eficiente que el algoritmo quicksort de C. A. R. Hoare; por supuesto, su complejidad computacional es la misma, O(n log n) operaciones, pero en los experimentos realizados con 100 secuencias aleatorias de 100 000 números el nuevo algoritmo requiere ~ 92 % del tiempo de ejecución de quicksort (el experimento exigió más de 3 días de tiempo computacional). Siendo más rápido en la práctica, el nuevo algoritmo parece un gran éxito en la generación automática de algoritmos.

Sin embargo, hay un pero. Por desgracia, no se puede demostrar matemáticamente que el nuevo algoritmo funcione de forma correcta (los autores prometen intentarlo en el futuro). La opción obvia para demostrarlo, enumerar todos los posibles casos por fuerza bruta, es inviable. Así, el algoritmo quicksort sigue reinando entre los algoritmos de ordenación. La red de neuronas artificiales fue entrenada para imitar los pasos del algoritmo quicksort (también los algoritmos de burbuja y por inserción) usando 100 conjuntos de entre 5 y 1000 números; luego se usó dicho algoritmo para ordenador 100 conjuntos de 10 000 y otros 100 de 100 000 números. Que los resultados sean correctos en estos experimentos computacionales no garantiza que el nuevo algoritmo funcione siempre de forma correcta. Se requiere una demostración independiente, labor que no es nada fácil, aunque tampoco parece imposible”

La entrada Una red de neuronas artificiales diseña un algoritmo de ordenación que parece más rápido que el quicksort de Hoare fue escrita en La Ciencia de la Mula Francis.

 

A %d blogueros les gusta esto: