1. Introducción
1.1. Antecedentes
El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de Darwin, que ha cobrado tremenda popularidad en todo el mundo durante los últimos años. Se presentarán aquí los conceptos básicos que se requieren para abordarla, así como unos sencillos ejemplos que permitan a los lectores comprender cómo aplicarla al problema de su elección.
En los últimos años, la comunidad científica internacional ha mostrado un creciente interés en una nueva técnica de búsqueda basada en la teoría de la evolución y que se conoce como el algoritmo genético. Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse más fácilmente a los cambios que se producen en su entorno. Hoy en día se sabe que estos cambios se efectúan en los genes de un individuo (unidad básica de codificación de cada uno de los atributos de un ser vivo), y que sus atributos más deseables (i.e., los que le permiten adaptarse mejor a su entorno) se transmiten a sus descendientes cuando éste se reproduce sexualmente.
Un investigador de la Universidad de Michigan llamado John Holland era consciente de la importancia de la selección natural, y a fines de los 60s desarrolló una técnica que permitió incorporarla a un programa. Su objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica que inventó Holland se le llamó originalmente "planes reproductivos", pero se hizo popular bajo el nombre "algoritmo genético" tras la publicación de su libro en 1975.
Una definición bastante completa de un algoritmo genético es la propuesta por John Koza:
"Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud. "
1.2. Definición
Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.
Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuales de ellos deben generar descendencia para la nueva generación.
Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que directamente toma a la especie (el total de los ejemplares) y crea una nueva generación que reemplaza a la antigua una cantidad de veces determinada por su propio diseño. Una de sus características principales es la de ir perfeccionando su propia heurística en el proceso de ejecución, por lo que no requiere largos períodos de entrenamiento especializado por parte del ser humano, principal defecto de otros métodos para solucionar problemas, como los Sistemas Expertos.
1.3. Problemática
Los principios básicos de los Algoritmos Genéticos fueron establecidos por Holland, y se encuentran bien descritos en varios textos . Goldberg, Davis, Michalewicz, Reeves.
En la naturaleza los individuos de una población compiten entre sí en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de un compañero. Aquellos individuos que tienen más éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran número de descendientes. Por el contrario individuos poco dotados producirán un menor número de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagarán en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes ancestros, puede a veces producir descendientes "superindividuos", cuya adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas características cada vez mejor adaptadas al entorno en el que viven.
Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos . descendientes de los anteriores . los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones.
De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Así a lo largo de las generaciones las buenas características se propagan a través de la población. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras del espacio de búsqueda. Si el Algoritmo Genético ha sido bien diseñado, la, población convergerá hacia una solución óptima del problema.
1.4. Ventajas y Desventajas
No necesitan conocimientos específicos sobre el problema que intentan resolver.
• Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.
• Cuando se usan para problemas de optimización maximizar una función objetivo- resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales.
• Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente paralelas.
• Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.
• Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc.-.
• Pueden converger prematuramente debido a una serie de problemas de diversa índole.
1.5. Limitaciones
El poder de los Algoritmos Genéticos proviene del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el Algoritmo Genético encuentre la solución óptima, del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los Algoritmos Genéticos.
1.6. Como Saber si es Posible usar un Algoritmo Genético
La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:
• Su espacio de búsqueda (i.e., sus posibles soluciones) debe estar delimitado dentro de un cierto rango.
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.
El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.
La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que tiene ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.
La codificación más común de las soluciones es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar.
1.7. Marco de Desarrollo
Antes de continuar ahondando en la técnica de los Algoritmos Genéticos sería interesante dejarla situada dentro de un marco más amplio. Nos referimos a la rama de la Inteligencia Artificial que se ha denominado Computación Evolutiva.
El término Computación Evolutiva se refiere al estudio de los fundamentos y aplicaciones de ciertas técnicas heurísticas de búsqueda basadas en los principios naturales de la evolución. Una gran variedad de algoritmos evolutivos han sido propuestos pero principalmente pueden clasificarse en: Algoritmos Genéticos, Programación Evolutiva, Estrategias Evolutivas, Sistemas Clasificadores y Programación Genética. Esta clasificación se basa sobre todo en detalles de desarrollo histórico más que en el hecho de un funcionamiento realmente diferente, de hecho las bases biológicas en las que se apoyan son esencialmente las mismas. Las diferencias entre ellos se centra en los operadores que se usan en cada caso y en general en la forma de implementar la selección, reproducción y sustitución de individuos en una población.
Aunque los detalles de la evolución no han sido completamente comprendidos, incluso hoy en día, existen algunos puntos en los que se fundamentan:
• La evolución es un proceso que opera a nivel de cromosomas, y no a nivel de individuos. Cada individuo es codificado como un conjunto de cromosomas.
• La selección natural es el mecanismo mediante el cual los individuos mejor adaptados son los que tienen mayores posibilidades de reproducirse.
• El proceso evolutivo tiene lugar en la etapa de la reproducción. Es en esta etapa donde se producen la mutación, que es la causante de que los cromosomas de los hijos puedan ser diferentes a los de los padres, y el cruce, que combina los cromosomas de los padres para que los hijos tengan cromosomas diferentes.
De forma breve, pasamos a comentar cada una de los algoritmos mencionados anteriormente, para que el lector pueda tener una idea de las similitudes y diferencias entre ellos.
Los Algoritmos Genéticos resuelven los problemas generando poblaciones sucesivas a las que se aplican los operadores de mutación y cruce. Cada individuo representa una solución al problema, y se trata de encontrar al individuo que represente a la mejor solución.
La Programación Genética funciona igual que la técnica anterior pero se centra en el estudio de problemas cuya solución es un programa. De manera que los individuos de la población son programas que se acercan más o menos a realizar una tarea que es la solución.
La Programación Evolutiva es otro enfoque de los algoritmos genéticos, en este caso el estudio se centra en conseguir operadores genéticos que imiten lo mejor posible a la naturaleza, en cada caso, más que en la relación de los padres con su descendencia. En este caso no se utiliza el operador de cruce, tomando la máxima importancia el operador de mutación.
Estrategias Evolutivas se centran en el estudio de problemas de optimización e incluyen una visión del aprendizaje en dos niveles: a nivel de genotipo, y a nivel de fenotipo. Y por último los Sistemas Clasificadores engloban el estudio de problemas en los que la solución buscada se corresponde con toda una población.
Para finalizar se muestra un esquema en el que se sitúan las técnicas mencionadas con respecto a otros procedimientos de búsqueda conocidos.
1.8 Comparación con otros métodos de optimización
Algoritmos Genéticos y Matemáticos
Existen problemas de optimización que pueden ser resueltos por la implementación de un algoritmo tradicional. En este caso lo más conveniente es utilizarlo.
Por ejemplo: Si tenemos la función "Es el doble de" , ésta puede ser interpretada como :
Ecuación 1
Esto también es válido para funciones booleanas (retornan un valor de Verdadero o Falso ). Por ejemplo la función "Es mayor que" , puede ser interpretada como
Ecuación 2
Sin embargo , éstos no son aplicables a problemas que posean algunas de estas características:
• La función representativa del problema no es continua. En este caso el mismo no es computable. Los algoritmos genéticos pueden trabajar con todo tipo de funciones ya que encontrarán un mínimo aceptable si no es posible encontrar el óptimo.
• La función representativa es dinámica: La relación entre las variable cambia dependiendo de los valores que tomen las mismas. Esta relación puede ser advertida o no. Las reglas del tipo
"X es igual a Y si el valor de X es chico;
X es 1.5 de y si el valor de X es grande
no se sabe que pasa para valores medios de X"
no pueden ser convertidas en un algoritmo algebraico ya que existen valores que se desconocen. A diferencia de un algoritmo tradicional , un algoritmo genético puede ser diseñado para trabajar bajo estas condiciones.
Algoritmos Genéticos y Métodos Enumerativos
Existe la posibilidad teórica de encontrar soluciones a problemas a optimización enumerando todas las soluciones posibles para todos los casos y posteriormente buscando la misma en la base de datos resultante. Los problemas se limitan entonces a un sistema de búsqueda eficiente del caso concreto. Por ejemplo los libros con tablas de logaritmos tradicionales constan de una larga serie de cálculos para todos los valores usuales. La solución consiste simplemente en buscar en la lista el número decimal y retornar el logaritmo dado.
La memorización de las tablas de multiplicar que se enseñan a los niños es otro ejemplo usual. Se espera que ante la pregunta ¿Cuánto es siete por cinco? los niños respondan instantáneamente "35" sin tener que estar calculando mentalmente la multiplicación.
Este método es factible siempre que el número de valores sea manejable. De otra manera el simple cálculo de los mismos se vuelve imposible. Ejemplo: Generar una tabla que contenga todas las movidas de todos los partidos posibles de un juego de damas resultaría imposible de hacer en la práctica.
La " memorización " de una serie de datos no es otra cosa que la construcción en la memoria del equivalente a una base de datos en donde se busca la pregunta y se encuentra automáticamente la respuesta.
Los algoritmos genéticos usan heurística para la resolución de problemas , lo cual limita drásticamente el número de datos a utilizar.
Algoritmos Genéticos y Sistemas Expertos
Un Sistema Experto es un programa de computadora que encuentra soluciones a problemas del tipo condicional con la estructura:
Si ocurren los hechos A,B,C,D , cual sería el valor del suceso E
Ejemplo: Si un análisis médico detecta los síntomas A , B , C y D en un paciente , ¿Cual será la enfermedad del sujeto?
Ejemplo: Si el análisis geológico de una capa de suelo detecta la presencia de los compuestos químicos A , B , C y D ¿Es factible que exista petróleo en la misma?.
Si bien existen en la literatura ejemplos de la utilidad de ésta técnica , las reglas deben ser provistas por un especialista ( o varios ) en el tema. Por ende , se requiere que los conocimientos estén disponibles, que sean estructurados o factibles de ser estructurados ( convertidos a reglas heurísticas ) y que los hechos de la realidad sean relativamente estáticos , es decir que las causas para arribar a una determinada conclusión no cambien , ya que cada vez que esto sucede , los expertos deben reelaborrar las reglas , lo cual dificulta y retarda considerablemente la operatoria del sistema.
Las condiciones básicas necesarias para la implementación efectiva de un sistema experto pueden observarse en el cuadro GA005.
Los Sistemas Expertos tuvieron su apogeo en la década de los 80`s , aproximadamente de 1979 a 1985. En esa época se los llegó a considerar verdaderas panaceas que resolverían muchos de los problemas cotidianos del hombre. Incluso se formaron en ese entonces varias compañías con el objeto específico de realizarlos y comercializarlos. Algunos fueron exitosos y funcionaron bien , pero las dificultades planteadas anteriormente no tardaron en aparecer. En particular:
• Existen temas en los cuales el conocimiento no es estático , sino que la aparición de nueva información altera las pautas o reglas de inferencia de los resultados. La necesidad permanentes de reevaluar las reglas por medio de expertos humanos lleva al sistema a una operatoria lenta y burocrática. Cada conocimiento nuevo implica reentrenar manualmente el sistema. Los Sistemas Expertos demostraron no ser útiles en este campo.
• Existen temas en los cuales la interrelación de ciertas variables no es conocida. Si la información disponible de cierto asunto es limitada , y no se conoce el comportamiento de algunas de sus variables , el Sistema experto tendrá grandes dificultades de programarse ya que sus reglas serán imprecisas.
El Cuadro GA5 muestra las condiciones básicas necesarias para la implementación efectiva de un sistema experto
Condiciones básicas necesarias para la implementación efectiva de un sistema experto
• Los expertos no siempre estructuran su conocimiento. Existen numerosas personas que razonan por métodos empíricos. Esto hace que les resulte muy difícil traducir sus pensamientos o su método deductivo a reglas que la computadora pueda interpretar. Un Sistema experto no podrá llegar a resultados valederos cuando los especialistas en un tema no puedan tener estructurados sus pensamientos. Por ejemplo: supóngase que se quiera programar un sistema experto para calificar obras de arte. Difícilmente se encontrará un crítico de arte que pueda estructurar las razones por las cuales considera "buena" o "mala" a una obra de arte. En general las palabras que pueda decir resultarán a los oídos del programador del Sistema como una serie de subjetividades imposibles de sistematizar.
Luego de observar todo esto, se empezó a considerar a los Sistemas expertos como aptos solamente para entornos reducidos y con condiciones de ejecución acotadas. La idea del Sistema Experto como " resolvedor universal de problemas " quedó sepultada.
Si bien la investigación básica de los algoritmos genéticos es contemporánea a la de los sistemas expertos , la renovada importancia que se les dio en el ámbito científico se produjo en paralelo a la desvalorización que sufrieron estos últimos.
Los algoritmos genéticos se revalorizaron ya que poseen las siguientes ventajas competitivas:
• Solo necesitan asesoramiento del experto cuando se agregan o suprimen variables al modelo. Los Sistemas Expertos requieren la presencia del mismo ante cada modificación del entorno.
• Los algoritmos genéticos solo requieren el asesoramiento del experto para identificar las variables pertinentes , aunque no es necesario que éstos definan sus valores ni sus relaciones (las reglas) iniciales o finales. Los Sistemas Expertos solo trabajan con las reglas y valores que les dictan los seres humanos.
Algoritmos Genéticos y Redes Neuronales
Una red neuronal es el intento de poder realizar una simulación computacional del comportamiento de partes del cerebro humano mediante la réplica en pequeña escala de los patrones que éste desempeña para la formación de resultados a partir de los sucesos percibidos. El cerebro consta de unidades llamadas neuronas, las cuales están conectadas entre si formando una red (de ahí la denominación " red neuronal ")
Concretamente, se trata de poder analizar y reproducir el mecanismo de aprendizaje de sucesos que poseen los animales más evolucionados.
La red simula grupos de neuronas , llamados " capas " las cuales están relacionadas unas con otras. Los datos se introducen en la primera capa , llamada "capa de entradas" Cada capa transfiere la información a sus vecinas., teniendo un peso o ponderación para los valores , lo que va modificando los mismos en su paso a través de la red
Cuando los datos llegan a la última de las capas , llamada " capa de salida " el valor resultante es tomado como el resultado de la red. La red puede ser entrenada para diversos usos , entre ellos como mecanismo de optimización. En este sentido, se puede expresar que serían un modelo alternativo competitivo con los algoritmos genéticos , si se las programara para este fin. En rigor de verdades , la literatura sugiere que se podrían hacer modelos mixtos o híbridos en donde se combinen las ventajas de las redes neuronales y los algoritmos genéticos , aunque hay muy poco material disponible en este campo. Tal vez esto se deba al hecho que los GA y el estudio de las redes forman dos ramas o escuelas separadas dentro de la inteligencia artificial , por lo que existe una preferencia en los investigadores en perfeccionar alguno de los dos modelos antes que tratar de unirlos.
