Amit Patel (Univ. de Stanford)-Traducción y breves aportes de CvdB
algoritmos genéticos como búsqueda ciega
Definición:
Los algoritmos genéticos permiten explorar mediante un apreciable número de candidatos a ser soluciones, un espacio de parámetros desde un nodo de inicio hasta un nodo meta, para encontrar el mejor candidato que satisface una "función de idoneidad (fitness)".
Son una buena opción para los problemas en los cuales no está claro cómo encontrar una solución. Son también una buena técnica a utilizar con poca información disponible, sobre qué clases de parámetros son buenos para dicha solución. Los algoritmos genéticos son esencialmente una búsqueda ciega realizada sobre un espacio, con cierta realimentación que nos diga si nos estamos acercando al nodo meta. Sin embargo, si sabemos algo sobre el espacio de parámetros, muchas veces podemos solucionar mejor el caso en lugar de usar una búsqueda ciega. Esto es, si ya sabemos de antemano en qué dirección nos conviene viajar, será cierto en el caso general que seguir usando una búsqueda ciega nos ha de retrasar, aunque no en casos particulares. Conseguiremos ir más rápido si ya sabemos hacia adónde ir. Para encontrar nuestra trayectoria, podemos reconocer cuáles algoritmos pueden ayudarnos a encontrar un buen camino. ¿Para qué, entonces, buscar con muchos candidatos los caminos al azar y evaluarlos? La cosa varía se ya tenemos hecho el programa de algoritmo genético, porque con todas las pruebas que efectúa, abandona las soluciones incorrectas y se concentra, con suerte variable, en otras no tan malas. Y con tiempo logra resolver el caso, dependiendo mucho de dejar o eliminar los aportes personales que le introduzcamos a la lógica de búsqueda. Los ensayos con programación genética andan bien si no sabemos de antemano de la existencia de algún programa específico para el campo de juego donde debemos operar. Los seres humanos, al razonar, tendemos a hacer ensayos mejores que los basados en el azar y en las equivocaciones hechas ("prueba al azar y error", "búsqueda ciega y logro de la solución más apta"). John Koza en Stanford me ha mostrado los programas genéticos que hacen un buen trabajo para algunos problemas, pero no alcanzan a manejar todos los casos; tampoco son los más simples o más rápidos que pueden hacer la tarea. Si usted es un estudioso de la evolución, reconoce que la naturaleza no siempre ha producido las mejores soluciones; a veces se ha conformado con las "bastante buenas". El razonamiento humano puede mostrar a menudo aciertos mejores que la búsqueda ciega de la evolución. La naturaleza no salió al encuentro de la rueda, ni de encender y controlar el fuego, ni de curar la poliomielitis. Por otra parte, los algoritmos genéticos y la programación genética pueden salir bien parados con soluciones en las cuales los seres humanos apenas habían pensado antes o no lo habían hecho nunca, especialmente en los problemas que desafían la lógica. No obstante, encontrar buenas trayectorias son tema que se ha estudiado extensamente y tenemos buenos algoritmos que lo hacen. En general, los algoritmos genéticos resultan muy satisfactorios en problemas para los cuales no hemos encontrado buenas soluciones clásicas.
¿A qué se deben los tipos de búsquedas (explotación o exploración) que vemos que se efectúan? No son consecuencia de decisiones del operador, sino del "ambiente o del dominio del sistema genético" (esto es, la diversidad de la población de candidatos) donde se efectúa la trayectoria. Además, diseñan a los operadores genéticos simples como métodos de uso general de búsqueda (los métodos de búsqueda "dominio-independientes"); realizan esencialmente una búsqueda ciega y no podrían garantizar el logro de un descendiente realmente idóneo.La programación genética toma un paso más adelante con respecto a lo que se proponen los algoritmos genéticos. Trata programas como los parámetros. Por ejemplo, podemos estar incubando diversos algoritmos buscadores de trayectorias, cada uno con otros operadores de entrecruzamiento. A medida que van apareciendo soluciones con apreciable "idoneidad", el operador de entrecruzamiento (crossover) que entrecruza fragmentos de mensajes entre los diversos candidatos en competencia para generar descendientes, proporciona un buen recurso para la exploración en la vecindad de cada una de dichos candidatos. La función de idoneidad creada dirá qué calificación comparativa merece cada algoritmo basado en cuán idóneo fué su resultado.
10.may.2002
Pulsar tecla de vuelta
Vuelta a Portada
Glosario de Bioingeniería del Conocimiento - Carlos von der Becke.
