Regresar a la pagina principal  

Centro de Investigación y de Estudios Avanzados del I.P.N.

 


Apéndice

Introducción a la Computación Evolutiva

  La Computación Evolutiva en el Contexto de la Inteligencia Artificial.   

Introducción

Vida y Evolución    

En la naturaleza todos los seres vivos se enfrentan a problemas que deben resolver con éxito

El origen de la vida y el programa Tierra

La selección natural no es propiamente una selección

¿Evolución egoísta, programas egoístas?

En la evolución se combinan egoísmo y altruismo

Genes y músicos de rock

Buenos, pero no tontos

Computación Evolutiva

Opciones de un Algoritmo Evolutivo

Algoritmos jerárquicos

El problema más difícil

En un problema complicado, los valores de los genes no son intrínsecamente buenos ni malos

Referencias sobre Vida Artificial

Referencias sobre Computación Evolutiva y aprendizaje

Referencias sobre Darwinismo, Genética, y Evolución

Referencias sobre Redes Neuronales

Otras referencias

Programas autoconfigurables

Introducción a los Algoritmos Genéticos

Orígenes

Definición

Funcionamiento de un Algoritmo Genético Simple

Inversión

Ambientes de Programación

Areas de Investigación

Conclusiones

Referencias

Repositorios

Laboratorios

Investigadores

Empresas

 

 

 

 

 

La Computación Evolutiva en el Contexto de la Inteligencia Artificial.

Carlos A. Coello Coello* 

Indudablemente, la Inteligencia Artificial (IA) es una de las áreas que más expectación han causado no sólo dentro de las Ciencias de la Computación, sino para la sociedad en general. La búsqueda para comprender los mecanismos de la inteligencia ha resultado ser la piedra filosofal de muchos científicos a lo largo de los años. De entre las áreas principales de la Inteligencia Artificial, una de las que ha atraído más investigadores ha sido el aprendizaje de máquina. Michalski definió "aprendizaje" como: "la cons-trucción o modificación de representaciones de lo que se experimenta". Esta definición se concentra en una representación interna que el sistema de aprendizaje construye (ya sea una persona o un programa de computadora) y modifica en base a su entorno (típicamente, lo que el sistema de aprendizaje experimenta es su entorno, o al menos cierta parte de él). Indudablemente, resulta vital en el proceso de emular comportamientos "inteligentes", que un sistema pueda mejorar su comportamiento sobre la base de la experiencia que colecte al efectuar la misma tarea en repetidas ocasiones, y que además desarrolle algún tipo de noción de lo que es un error, y cómo evitarlo. La escuela clásica dentro de la IA, utiliza representaciones simbólicas basadas en un número finito de primitivas y de reglas para la manipulación de símbolos. El período simbólico de la IA se considera aproximadamente comprendido entre 1962 y 1975, seguido por un período dominado por los sistemas basados en el conocimiento de 1976 a 1988. Sin embargo, en este segundo período las representaciones simbólicas (por ejemplo, redes semánticas, lógica de predicados, etc.) siguieron siendo parte central de dichos sistemas. En la actualidad, la IA empieza a extender sus áreas de investigación en diversas direcciones y trata de integrar diferentes métodos en sistemas a gran escala, en su afán por explotar al máximo las ventajas de cada esquema.

Curiosamente, el primer período de la Inteligencia Artificial, llamado sub-simbólico, data de aproximadamente 1950 a 1965. Este período utilizó representaciones numéricas (o sub-simbólicas) del conocimiento. Aunque la mayor parte de los libros de IA sólo enfatizan el trabajo realizado por Rosenblatt y Widrow con redes neuronales durante este período, la realidad es que otra importante escuela sub-simbólica se fraguó también en la misma época: los algoritmos evolutivos.

En 1932, Cannon visualizó la evolución natural como un proceso de aprendizaje. Alan Turing reconoció, en 1950, que "debe haber una cone-xión obvia entre el aprendizaje de máquina y la evolución", y señaló que se podrían desarrollar programas para jugar ajedrez usando esta técnica. Campbell conjeturó en 1960 que "en todos los procesos que llevan a la expansión del conocimiento, se involucra un proceso ciego de variación y supervivencia selectiva". Los primeros intentos de aplicar de manera formal la teoría de la evolución, a problemas prácticos de ingeniería, apareció en las áreas de control de procesos estadísticos, aprendizaje de máquina y optimización de funciones. Tal vez el primer intento serio de este tipo se dio en el trabajo que realizaron Box y sus colegas en 1957, en el desarrollo de una técnica que denominaron "operación evolutiva", la cual se aplicó a una planta de manufactura para manejarla, y que se implanto sobre la base de los votos de un comité de jefes técnicos. Bajo este esquema, la planta se veía como a una especie en evolución. La calidad del producto avanzaba a través de mutaciones aleatorias y la selección era determinada por el comité.

Por su parte, Friedberg intentó, en 1958, hacer que un programa en lenguaje máquina se mejorara a sí mismo, seleccionando instrucciones que se asociaran más frecuentemente con un resultado exitoso. Aunque Friedberg nunca mencionó explícitamente estar simulando la evolución natural, esa es la interpretación más comúnmente aceptada de su trabajo, y a pesar de que tuvo cierto éxito evolucionando manipuladores de bits y determinando las interconexiones de una caja negra de 1400 terminales, la comunidad de IA de la época prestó poca atención a su trabajo, y en algunas ocasiones lo atacó despiadadamente. Por ejemplo, Minsky lo criticó duramente, argumentando que una búsqueda puramente aleatoria era mucho mejor que el algoritmo de Friedberg (este argumento aún es es-grimido infundadamente por algunos miembros de la comunidad científica en contra de los algoritmos genéticos).

Apendice

El trabajo de Bremermann, en 1958, se enfocó más a la optimización, introduciendo el importante manejo de un valor de aptitud, y definiendo a un individuo como una cadena de símbolos binarios (unos y ceros). Bremermann advirtió, acertadamente, que la mutación jugaba un papel importante en la evolución, pues impedía el estancamiento en mínimos locales. Aunque muchas de sus ideas se usan hoy en día, Bremer-mann cometió el error de tratar de optimizar funciones lineales y convexas, obteniendo resultados decepcionantes, pues sus algoritmos evolutivos tenían que ser complementados con otras heurísticas para converger en una solución. Hoy sabemos que los algoritmos evolutivos difícilmente pueden competir con las técnicas tradicionales de optimización en esos dominios.

Barricelli ofreció, en 1954, una de las primeras simulaciones que usaba principios evolutivos, utilizando los mismos procedimientos generales que se usan hoy en día en la disciplina conocida como vida artificial. Sin embargo, en este trabajo, así como el que Reed realizó posteriormente en 1967, se concluyó que la cruza no parecía mejorar la velocidad de la adaptación selectiva, y el operador primordial era la mutación. Fue Fogel el que introdujo la primera técnica evolutiva que realmente funcionó más o menos dentro de los lineamientos actuales de la computación evolutiva. Su programación evolutiva consistía en hacer evolucionar autómatas de estados finitos por medio de mutaciones. Fogel introdujo los importantes conceptos de población y selección, y aunque las revisiones iniciales de su trabajo fueron favorables, algunos investigadores, como Solomonoff, en-fatizaron que "el método de Fogel no debía verse en su estado actual (en 1966) como algo particularmente útil para resolver problemas, a excepción de los más simples posibles". Solo-monoff vio a la programación evolutiva como una especie de búsqueda escalando la colina modelada mediante autómatas, y otros investigadores como Holland, Kieras, Rada y Lenat compartieron esa opinión. Algunos investigadores fueron más duros en sus críticas. Lindsay, por ejemplo, llegó a decir que la técnica de Fogel no era mejor que una búsqueda completamente aleatoria, y que "temía que los sicólogos lo usaran para alienarse del importante trabajo que se estaba haciendo en Inteligencia Artificial".

Otra técnica evolutiva dirigida particularmente a la optimización de funciones continuas de alta complejidad se desarrolló en Alemania, en 1965, por Rechenberg y Schwefel. Esta técnica, llamada estrategia evolutiva, se utilizó inicialmente para resolver problemas ingenieriles que desafiaban a los métodos de optimización tradicionales, como el gradiente conjugado, y se basa en la modificación sistemática de un vector de números reales (representando las variables de decisión del problema) mediante operadores probabilísticos, usando ciertos criterios para decidir en qué dirección dirigir la búsqueda. La estrategia evolutiva utiliza como operador principal a la mutación, y en su versión más reciente usa la cruza como operador secundario.

Aunque el australiano Fraser propuso, desde fines de los 50, un proce-dimiento muy similar al que John Holland llamó planes evolutivos a fines de los 60, es al segundo al que se le suele atribuir la creación de la técnica que se conoce como algoritmo genético, a raíz de que Holland publicara el libro "Adaptation in Natural and Artificial Systems" en 1975. La principal diferencia del algoritmo genético con las técnicas antes mencionadas, es que utiliza la cruza como operador principal y a la mutación como operador secundario (e incluso opcional). El algoritmo genético, al igual que las redes neuronales, funciona como una caja negra que recibe ciertas entradas y produce (tras una cantidad de tiempo indeterminada) las salidas deseadas. Sin embargo, a diferencia de éstas, los algoritmos genéticos no necesitan entrenarse con ejemplos de ningún tipo, sino que son capaces de generar sus propios ejemplos y contra-ejemplos que guíen la evolución a partir de poblaciones iniciales totalmente aleatorias. Los mecanismos de selección del más apto y de reproducción sexual del algoritmo genético, son los encargados de preservar las características más adecuadas de cada individuo a fin de hacer converger a la población en soluciones óptimas. Los algoritmos genéticos se distinguen también por no quedar atrapados fácilmente en mínimos locales, como la mayor parte de las técnicas de búsqueda clásicas, además de usar operadores probabilísticos más robustos que los operadores determinísticos, que las otras técnicas suelen usar. No obstante, siendo una heurística, tampoco pueden garantizar encontrar siempre la solución óptima, si bien la experiencia acumulada hasta la fecha parece demostrar que, cuando se utilizan apropiadamente, pueden proporcionar soluciones muy aceptables y, en la mayoría de los casos, superiores a las encontradas con otras técnicas de búsqueda y optimización. Aunque aún atacados por algunos sectores de la comunidad de IA, los algoritmos genéticos, al igual que las redes neuronales, se han ido ganando poco a poco, y sobre la base de la efectividad de sus resultados en aplicaciones prácticas, el reconocimiento de los investigadores como una técnica efectiva en problemas de gran complejidad, como lo demuestra un número creciente de conferencias y publicaciones especializadas alrededor del mundo, en los últimos años. Probablemente, y de manera análoga a como lo hace la Naturaleza, sólo el tiempo podrá determinar el verdadero lugar que le correspode a los algoritmos evolutivos dentro de las Ciencias de la Computación.

Apendice

* Investigador Titular del LANIA.

http://delta.cs.cinvestav.mx/~ccoello/bibgen.html                                                            

http://hipernexos.escom.ipn.mx/coello.htm                                         

                                                                                                                                          http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html

 

Introducción

¿Qué tienen estas simulaciones de fantástico? Podemos sentirnos una especie de dios, observando y modificando a nuestro antojo un mundo poblado por seres virtuales [A1]. También es interesante jugar con la idea de que nosotros mismos somos las "hormigas", viviendo bajo los designios de El Programador [E1] [E2] [E3]. Pero no se trata sólo de eso. Se trata de que la Vida Artificial ofrece una nueva perspectiva sobre los problemas que afectan a cualquier grupo, como por ejemplo, la humanidad.

Este artículo completa la serie de los artículos aparecidos en los números 36, 37 y 38 de la revista "Solo Programadores", y contiene la bibliografía correspondiente a los temas que se han abordado. Voy a profundizar en algunos aspectos prácticos de la Computación Evolutiva como método de resolución de problemas, pero empezaré por introducir la evolución en su forma más general. Si aún no has podido ejecutar alguna de estas simulaciones y tienes un PC, en el CD-ROM que viene con la revista o en la página de download de Gaia encontrarás el código fuente completo en Visual Basic 5.0 y el programa de instalación para Windows de "Ejemplos de Vida", con varios de estos mundos.

Apendice

Vida y Evolución 

La Vida Artificial consiste en observar la vida natural e imitarla en un ordenador [A2] [A6]. La Computación Evolutiva [B11] interpreta la naturaleza como una inmensa máquina de resolver problemas y trata de encontrar el origen de dicha potencialidad para utilizarla en nuestros programas [B4] [B6]. Efectivamente, en la naturaleza todos los seres vivos se enfrentan a problemas que deben resolver con éxito, como conseguir más luz del sol, o cazar una mosca. Un programador con espíritu práctico no envidia la capacidad de la naturaleza para resolver problemas: la imita [B1].

En la naturaleza todos los seres vivos se enfrentan a problemas que deben resolver con éxito

El origen de esta capacidad está en la evolución, producida por la selección natural, que favorece la perpetuación de los individuos más adaptados a su entorno. Esto es lo que tenemos que simular. La principal diferencia conceptual entre la selección natural (o que se produce sin intervención del hombre), y la selección artificial que nosotros establecemos nuestras granjas o en nuestros programas, es que la selección natural no es propiamente una selección [C7]. Nosotros podemos seleccionar para la reproducción los seres que más nos interesan, ya sean las vacas más lecheras o los agentes software que mejor resuelven un problema. En cambio, en la naturaleza no existe -en principio- una inteligencia exterior que determine la dirección de la evolución. Y sin embargo la evolución sí se produce. Si efectivamente, no existe algo o alguien que controle la evolución de la vida en nuestro planeta, entonces nosotros mismos seríamos el ejemplo de un principio básico y universal: que la vida, la inteligencia, la consciencia y quién sabe qué otros tipos de complejidad en el futuro, son sucesos inherentes, inevitables y espontáneos de nuestro universo. A esto también se le ha llamado Darwinismo Universal [C1], y supone que toda vida, en cualquier lugar, habría evolucionado por medios darwinianos.

 

Apendice

El origen de la vida y el programa Tierra

El programa Tierra [A1] es un ejemplo de cómo agentes software pueden evolucionar sin que sea necesaria una selección dirigida por una entidad externa. Tanto en este programa como en otros, existe una serie de componentes software de algún tipo capaces de reproducirse y sufrir mutaciones. En un Algoritmo Genético, los agentes deben resolver un problema particular, pero en Tierra los agentes hacen poco más que reproducirse. El espacio de memoria limitado produce una selección natural, ya que sólo las mejores entidades podrán dejar descendencia en él. La existencia de pequeñas mutaciones aleatorias basta para generar agentes con características muy complejas, capaces de invadir o cooperar con otros agentes. Después de estudiar una de estas simulaciones, parece lógico suponer que en nuestro planeta haya podido suceder algo parecido. Está bastante extendida la idea de que las primeras entidades replicantes surgieron al azar, a partir de la combinación de elementos, y que la selección hizo el resto. Sin embargo Thomas Ray decidió que su programa comenzara con un primer agente capaz de copiarse a sí mismo, sin pretender que esta autocopia se produjera espontáneamente, como hizo Steen Rasmussen. Se plantea la cuestión de sí la probabilidad de aparición de los componentes básicos de la vida es demasiado baja para un solo planeta. Fred Hoyle [C4] sugiere la existencia de un bombardeo de material genético del exterior, -ya sea con o sin entidad consciente detrás de ello-, lo que daría un mayor margen, al haber podido surgir este "primer replicante" en cualquier otro mundo. Además, esto solucionaría algunos otros problemas, como los aparentes "saltos de complejidad" evolutivos. Es sorprendente la aparición de órganos complejos como los ojos, que difícilmente han podido surgir de una evolución gradual si no proporcionan ninguna ventaja al individuo hasta que no se encuentran formados por completo. El lamarkismo, es decir, la transmisión genética de los caracteres adquiridos, está resucitando[C7], y Máximo Sandín [C9] ofrece otra interesante explicación a todas estas cuestiones mediante infecciones de tipo vírico capaces de afectar rápidamente a gran parte de la población.  

Apendice

 

La selección natural no es propiamente una selección

En mi opinión, la cuestión más apasionante de las difícilmente explicadas por el darwinismo es la de la aparición de sentimientos de placer y dolor en los seres vivos. Nosotros podemos asignar a cada agente una variable con un número llamada placer o dolor, pero no es necesario que la entidad tenga realmente esas sensaciones para que se comporte como si las tuviera. Tal vez podamos construir algún día robots que se comporten como seres humanos, pero ¿podremos hacer que sientan? No importa ahora la respuesta a esta pregunta. La cuestión es: aunque pudiésemos, ¿Por qué hacerlo? ¿Por qué lo ha hecho la naturaleza con nosotros? Una cosa es la vida artificial como imitación de los procesos propios de la vida, y otra muy distinta es la recreación de su esencia.

Desde el punto de vista reduccionista, podemos pensar que "la recreación de su esencia" no es posible precisamente porque dicha esencia no existe, y la vida no es más que sus procesos. Tal como comentaba cierto día mi amigo Vicent Castellar "¿Que diferencia existe entre sumar uno más uno y simular que se suma uno más uno?". Ciertamente, es difícil de ver la diferencia. Si el universo fuese susceptible de ser descompuesto en unidades mínimas de espacio y tiempo, todo el universo podría considerarse como un gran sistema formal. ¿Que diferencia habría entre el universo real y otro universo copia del primero? ¿Que diferencia habría entre materia e información? ¿No sería lo mismo tener una unidad mínima de materia en cierta posición, que tener "algo" que se comportase como si fuera una unidad mínima de materia, en la misma posición? Lo mismo podemos aplicar a un cuerpo humano, cerebro incluido. ¿Que diferencia habría entre dos cuerpos así? (Además de la obvia: que ambas copias a pesar de ser idénticas, o bien no ocupan el mismo lugan del espacio, o bien no se encuentran en el mismo tiempo) ¿Serían dos personas o una?

Sin embargo, sí existe una gran diferencia entre "me duele el estómago" y "simular que me duele el estómago". Aquí aparece un componente cuya simulación no puede considerarse equivalente. Hay algo que no se puede simular: el sentir. ¿Tiene el sentimiento un origen evolutivo? Un árbol no tiene capacidad de sentir sensaciones (vamos a suponer esto), y en cambio una rana sí. El placer, el dolor, etc. parecen muy buenos mecanismos de supervivencia, pero realmente no hacen falta si el ser vivo es capaz de comportarse "como si" los tuviera. La rana busca la comida, como el árbol la luz; ambos realizan las acciones correctas gracias a siglos de evolución, aunque la rana sí siente hambre y el árbol no. ¿Por qué ha ocurrido esto con los animales? Los sentimientos probablemente sean mecanismos adicionales y potentes creados por y para los seres más complejos, que se deben enfrentar con problemas muy distintos, por ejemplo, por el hecho de ser móviles. Pero ¿realmente le resulta más fácil y económico a la naturaleza crear seres que realmente sienten, que seres que actúan como si sintieran?

En fin, las teorías sobre la vida y la evolución son difícilmente demostrables, y el debate es intenso. Podría parecer que estas cuestiones sólo atañen a los biólogos y filósofos, pero no es así. Recordemos que se trata de crear inteligencia en nuestros ordenadores imitando la forma en que lo hizo la naturaleza en nuestro planeta. Sin embargo, no podemos hacerlo sin más. Debemos captar al máximo la esencia de todo el proceso para evitar que nuestro ordenador tarde también millones de años.

Apendice

 

¿Evolución egoísta, programas egoístas?

La teoría de la evolución puede llevarse directamente a su extremo lógico en forma de darwinismo social suponiendo que la lucha por la vida y la supervivencia del más apto son la única vía de todo progreso humano. También se puede tomar la postura de Pedro Kropotkin [C5] y defender el apoyo mutuo como otro factor de evolución. En los humanos se encuentran comportamientos muy distintos. Desde cierto punto de vista, se puede argumentar que cuando un individuo coopera, es porque, egoístamente, ha evaluado que esto le ayuda a conseguir sus objetivos, y por tanto sólo existe el egoísmo. Esta aparente paradoja no es mas que una confusión de términos. Para tratar la cuestión adecuadamente es preciso no tener en cuenta motivaciones, sino sólo actos. Un comportamiento altruista será aquel que contribuya al bienestar ajeno a expensas del propio; uno egoísta sería exactamente lo contrario [C1]. Voy a llamar cooperación a las diferentes formas de acuerdo que se encuentran oscilando en el límite entre altruismo y egoísmo.

Apendice

 

En la evolución se combinan egoísmo y altruismo

Antes de continuar quiero aclarar que no estoy discutiendo la ética de estos comportamientos, sino analizando por qué algunos o una combinación de ellos son seleccionados en la evolución. Para saber cuáles son los seleccionados, basta con mirar a nuestro alrededor, ya que nosotros y el resto de los seres vivos somos producto de ella. Aún así no debemos olvidar que el proceso evolutivo es algo dinámico. Hoy se selecciona una cosa, mañana otra. El hombre seguirá evolucionando, no sabemos hacia dónde. Tal vez sea lo suficientemente diferente como para dar un giro radical al proceso, tal vez no. En mi opinión, y en contra de la de muchos otros, el autor que mejor trata este tema es Richard Dawkins [C1] [C3]. Para él somos máquinas de supervivencia construidas por nuestros genes para su propia perpetuación. Venimos de los genes egoístas, moléculas autorreplicantes que en cierto momento "decidieron" que la creación de una máquina como nosotros, con una capacidad de razonamiento flexible, era lo más adecuado para sus fines. Hay idealistas que rechazan impulsivamente la idea de una naturaleza basada en genes egoístas y hay quienes sólo ven en ella egoísmo y destrucción. Si bien es cierto que demasiadas veces la naturaleza no es madre, sino más bien cruel suegra, fuera de nuestra óptica, la naturaleza es simplemente indiferente. En cualquier caso, Dawkins habla de genes egoístas, no de individuos egoístas. Y lo que es más importante: con la teoría de Dawkins, la cooperación e incluso el altruismo (reales) entre individuos pueden ser explicados por el "egoísmo" (metafórico) de los genes.

Vamos a verlo. En todas las células de nuestro cuerpo existe la misma información genética: una larga cadena de ADN idéntica en el interior de cada célula. Existen muchas definiciones de gen. Para Dawkins, "el gen egoísta no es sólo una porción física de ADN: es todas las réplicas de una porción de ADN, distribuidas por el mundo". Es decir, el mismo alelo o valor en las mismas posiciones dentro de la cadena de ADN, es el mismo gen egoísta, ya se encuentre en uno o en distintos individuos. Un gen egoísta de los que habla Dawkins no sólo está simultáneamente en todas las células de nuestro cuerpo. Está simultáneamente en varios individuos. Esta abstracción de Dawkins sirve para expresar la siguiente idea: los genes tienen el objetivo de reproducirse a sí mismos, a costa de lo que sea, pero no a costa de otro segmento de ADN idéntico, ya que ambos son el mismo gen. Podemos decir que las células de nuestro cuerpo cooperan, e incluso que se comportan de forma altruista, ya que no intentan reproducirse a costa de sus vecinas, sino que producen un crecimiento ordenado, formando un cuerpo, tal como conviene a los genes egoístas. A nivel de individuo, cuando un individuo coopera con otro y ambos comparten genes (y dos miembros de la misma especie suelen compartir más del 90% de ellos), podemos decir que en realidad lo que ocurre es que los genes egoístas se están ayudando a sí mismos. Cuando dos individuos de la misma especie compiten, lo hacen por propagar su 10% diferencial. Es lógico que si dos individuos comparten el mismo nicho (por ejemplo, por ser de la misma especie), existirá una mayor competencia entre ellos. Pero en general, los individuos cooperarán con otros en función del número de genes en que coincidan. El apoyo mutuo entre los individuos es, efectivamente, un factor de evolución [C5], pero está basado en el egoísmo de los genes.

Apendice

 

Genes y músicos de rock

Dawkins ha sido acusado de tratar los genes como unidad de selección [C8] [C9]. Aunque la selección actúa sobre individuos, es evidente que la selección de individuos modifica el conjunto genético de la población, lo que indirecta y estadísticamente produce una selección de genes. ˇTambién podríamos criticar a casi todos los biólogos por tratar a los individuos como unidad de reproducción! Puede parecer asombroso, pero los animales no nos reproducimos, al menos, no directamente. No producimos copias de nosotros mismos: producimos copias de nuestros genes y éstos, combinados tal vez con los de otro individuo, y afectados por el entorno, producirán un nuevo ser. La cuestión crucial es hasta que punto la selección de individuos afecta a la selección de genes. Usando una metáfora, los integrantes de un grupo de rock (genes) forman un conjunto musical (cadena de ADN, genotipo) que se desarrolla componiendo canciones (fenotipo, ser vivo) que se escuchan en la radio (entorno) junto con otras canciones. La selección actúa sobre las canciones (fenotipo), pero es de suponer que la selección de canciones produce, en definitiva, una selección de músicos (genes).

Apendice

 

Buenos, pero no tontos

Para Fernando Savater, aspectos éticos como el respeto hacia los demás son actitudes cuyo origen es en última instancia la búsqueda inteligente del beneficio propio [E7]. Las simulaciones por ordenador parecen darle la razón. En juegos como El dilema del prisionero [A6] [B8], se observa que el altruismo es perjudicial para el que convive con individuos egoístas, pero el egoísmo necesita a quien explotar a largo plazo, por lo que ambas son estrategias destinadas a desaparecer. Son los pactos propios de la cooperación los que ofrecen los mejores resultados. La ética y las leyes son en realidad manifestaciones de estos pactos de cooperación que la evolución selecciona como útiles para nuestra propia supervivencia.

Apendice

Computación Evolutiva

Espero haber presentado una visión aceptable del mecanismo de la evolución. Es el momento de pasar estas ideas a nuestros programas. ¿Por donde empezar? ¿Qué tipos de Computación Evolutiva existen? Las nuevas ciencias siempre pasan por una fase inicial de desconcierto e inconsistencia hasta llegar a unas convenciones aceptadas por todos. Más o menos la clasificación aceptada en nuestros días es la de la figura siguiente.

 

El enfoque subsimbólico de la IA se caracteriza por crear sistemas con capacidad de aprendizaje. Éste se puede obtener a nivel de individuo imitando el cerebro (Redes Neuronales), o a nivel de especie, imitando la evolución, lo que se ha denominado Computación Evolutiva (CE), término relativamente nuevo que intenta agrupar un batiburrillo de paradigmas muy relacionados cuyas competencias no están aún muy definidas. Hasta hace poco era común hablar de Algoritmos Genéticos (AG) en general, en vez de identificar diferentes tipos de CE, ya que el resto de los algoritmos se pueden interpretar como variaciones o mejoras de los AG, más conocidos. En un AG los elementos de las cadenas (genes) son típicamente bits, y en ciertos casos, valores numéricos o strings. En la Programación Genética, los genes son instrucciones en un lenguaje de programación, y en las Estrategias Evolutivas, valores reales. Las Estrategias Evolutivas surgieron inicialmente para resolver problemas de optimización paramétrica; con el paso del tiempo fueron incorporando procedimientos propios de la computación evolutiva, con lo que han llegado a convertirse en una disciplina más. La agregación simulada (Simulated Annealing) se puede considerar una simplificación de los AG cuyo origen está en los procedimientos físicos de solidificación controlada. Los Clasificadores Genéticos solucionan problemas de reconocimiento de patrones mediante un entrenamiento basado en ejemplos, almacenando en las cadenas información que relacione los datos de entrada y la salida deseada. Finalmente, a mí me gusta considerar la Vida Artificial como un superconjunto de todas estas técnicas [B11].

Apendice

 

Opciones de un Algoritmo Evolutivo

Aunque existen otros esquemas [B6], por lo general, estos programas comienzan con una fase de inicialización de las entidades y su entorno, y seguidamente ejecutan repetidamente ciclos dentro de los cuales podemos distinguir tres etapas:

 

Los aspectos de tipo individuo pueden probarse introduciéndolos como si fueran nuevos genes, a continuación de los que ya existen. La tasa de mutación, aunque suele ser igual para toda la población, y hemos visto que podría ser incluso diferente para cada gen, podría también ser distinta para cada individuo, de forma que los hijos de ciertos agentes tengan mayor probabilidad de poseer mutaciones. Por ejemplo, en el tres en raya, una entidad estará compuesta por un conjunto de reglas más una probabilidad de mutación. Este valor se podrá heredar y mutar, y si es útil, se verá seleccionado, igual que una regla cualquiera. Antes hemos hablado de asignar una prioridad a cada regla. La prioridad asociada a cada regla es un aspecto de tipo gen, pero la decisión de asociar o no prioridades a las reglas es un aspecto de tipo individuo, que debe afectar obligatoriamente a todas sus reglas.

Probar e implementar aspectos de tipo isla va a ser más complicado. Por ejemplo, supongamos que queremos comprobar que ocurriría si permitimos a nuestros bichos compartir su conocimiento, es decir, transmitirse información genética en forma de infección vírica, tal como relata Máximo Sandín [C9]. Podríamos crear varias islas o sub-grupos de agentes con distintas opciones, manteniéndolos separados por una barrera de algún tipo que no permita el contacto de unos con otros. Más tarde podríamos comparar el conocimiento obtenido en cada isla o incluso juntar de vez en cuando a algunos o a los mejores de cada grupo para la reproducción [B2]. Las opciones de tipo isla pueden ser evaluadas automáticamente sin modificar mucho el algoritmo, ya que es de esperar que los grupos con peores opciones se extingan. La idea general es que tanto para grupos como para individuos o genes, lo bueno sobrevive y lo malo perece. Para crear barreras, podemos definir tipos de especies distintas que sólo son capaces de reproducirse entre sí, poseyendo cada una de ellas, por ejemplo, distintos métodos de recombinación de genes, con uno, dos o más puntos de corte en el cruzamiento, o incluso concibiendo de forma distinta los puntos de comienzo y fin de las unidades mínimas que se recombinan (genes). Curiosamente, en este caso, el propio método de implementación de las barreras (tipos de reproducción incompatibles) es precisamente aquello que estamos probando. Para implementarlo podemos añadir un gen especial a cada agente de forma que sólo los agentes con el mismo valor en dicho gen sean capaces de recombinarse entre sí. Cada valor corresponderá con una opción diferente. Para probar más de una deberemos poner varios de estos genes, y obligar a una coincidencia en todos ellos.

Las opciones de tipo población sólo pueden probarse ejecutando algoritmos en paralelo. Estas opciones son las más generales, como el número total de agentes o el número de reglas que tiene cada individuo. Otro ejemplo de tipo población es el hecho de ajustar los pesos de los agentes, de forma que si ya existe otro agente parecido al que acaba de nacer, se disminuye el peso del nuevo agente. Esta opción no puede ser aplicada sólo a una parte la población, ya que se vería en obvia desventaja. Evaluar opciones de tipo población es lo más complicado. Deberemos crear algoritmos independientes y compararlos, por ejemplo, en el tres en raya, provocando una partida entre las mejores entidades de cada una de las simulaciones, es decir, creando otro plano superior de juego.

Apendice

 

Algoritmos jerárquicos

Voy a cambiar de punto de vista para analizar las jerarquías dentro de los algoritmos evolutivos. En un algoritmo genético como el de las palabras y frases del CD-ROM [B4], la reproducción, selección, mutaciones, asignación de pesos, etc. se desarrollan a un sólo nivel o plano. Sin embargo, en el caso del tres en raya [B6], existen varios planos.

En el plano más elevado, juegan el ordenador contra el hombre. Este juego puede interpretarse como un algoritmo evolutivo reducido a su mínima expresión, con una población de dos individuos, donde el algoritmo termina al finalizar la partida. En este tipo de problemas tienen bastante éxito los paradigmas en los que el ordenador trata de aprender observando el juego humano, pero no es este el caso. Para aprender, el ordenador crea un segundo nivel de juego, donde muchas entidades jugarán por parejas. Aquella entidad que más partidas gane será la que represente al ordenador en el juego contra el hombre. Pero todavía se puede hablar de un tercer nivel, ya que dentro de un mismo agente, cada una de las reglas puede poseer también un peso, y aunque las reglas no se reproducen combinando sus elementos (podrían hacerlo), es posible sustituir algunas cada cierto tiempo.

Ya que la entidad de nivel superior ha creado un sub-mundo o plano donde juegan varias sub-entidades, gracias a las cuales es capaz de aprender por su cuenta antes de jugar contra el hombre, estas sub-entidades podrían a su vez crear otros planos que les proporcionasen conocimiento, hasta que llegue el momento de jugar "de verdad". Es decir, una entidad, al igual que jugar, o reproducirse, podría también tener una acción que podríamos llamar "pensar" y que consistiera en experimentar partidas hipotéticas (hipotéticas para la entidad superior; a la inferior le parecerán las suyas tan reales como a cualquier otra), creando "mundos virtuales", de la misma forma que las personas imaginamos o creamos hipótesis para prever los acontecimientos. En la figura siguiente se ilustra esta posibilidad.

Este sería además un esquema donde implementar el algoritmo minimax típico de los juegos, donde el agente evalúa posibles movimientos propios y del contrario a varios niveles de profundidad. Podemos combinar este tipo de jerarquías con las relativas a la elección de opciones de tipo población. Es decir, mientras buscamos la solución a nuestro problema inicial en los algoritmos o planos inferiores, podemos experimentar en un plano superior algunas opciones, las cuales pueden a su vez tener subopciones, tal como ilustra la figura siguiente.

Apendice

 

El problema más difícil

Una cadena de un algoritmo evolutivo tiene varios elementos (genes) que corresponden con variables del problema a resolver. Puede haber genes cuyos valores sean intrínsecamente buenos o malos, es decir, buenos o malos independientemente de los valores del resto de la cadena. Vamos a darles un nombre a este tipo de genes, por ejemplo, genes no-vinculados. Consecuentemente, un gen cuya bondad o maldad dependa de los valores de algunos de los otros genes será vinculado.

La propiedad de ser o no vinculado puede aplicarse también a un conjunto de elementos de la cadena, si tienen en cuenta todos ellos juntos, como un único gen, sin requerir que sean contiguos. Imaginemos un problema en el que todos los genes fueran no-vinculados: ˇNo sería necesario un algoritmo evolutivo! Para encontrar los valores óptimos de las variables, bastaría con analizar independientemente todos los posibles valores de cada gen, manteniendo constante el resto de la cadena con cualquier valor. Imaginemos ahora que todos los segmentos son vinculados, menos dos, es decir, todos los genes son intrínsecamente buenos o malos, excepto dos, que dependen de otros. Sí, pero ¿de cuáles? ¿El uno del otro? ¿Ambos de todos los restantes? Si la bondad de cada uno de estos dos segmentos sólo dependiera de sí mismo y del valor del otro podrían ser tratados en conjunto como un único gen no-vinculado, y aplicar el mismo proceso. Si la bondad de los genes vinculados dependiera de todos los demás podremos utilizar el mismo método, teniendo la precaución de calcular primero los valores de los segmentos no-vinculados.

Imaginemos ahora el caso extremo de que todos los genes sean vinculados, y sus efectos siempre dependan del valor de todos los demás genes. Este no sería un problema irresoluble, pero sí el peor que nos podríamos encontrar, no sólo para las técnicas evolutivas, sino para cualquier otro método. Sería algo así como buscar un objeto con los ojos cerrados, y la mejor forma de tratarlo sería, lógicamente, una búsqueda secuencial. En cualquier caso, lo que más nos interesa es buscar segmentos y grupos de segmentos no-vinculados, aunque sean grandes, ya que si podemos dividir la cadena en varios segmentos no-vinculados podremos aplicar un algoritmo independiente para cada segmento, en el que el resto de la cadena sea siempre fijo, con un valor cualquiera, y obtener la solución mucho más rápido.

Apendice

 

En un problema complicado, los valores de los genes no son intrínsecamente buenos ni malos

La existencia de fuertes vinculaciones (también llamadas "interacciones") entre los genes se ha denominado "el problema de la epístasis" o "el problema de la ausencia de bloques constructores". Los problemas con poca epístasis son triviales, y se pueden solucionar con un simple método de escalada. Para saber si un elemento (o un conjunto de elementos) es no-vinculado podríamos fijar valores al azar para el resto de la cadena, evaluar las cadenas que resulten de todas las posibles combinaciones de valores para el conjunto de elementos elegido y almacenar el orden de las cadenas ordenadas según su peso. Si repitiendo el proceso utilizando distintos valores en el resto de la cadena, siempre obtenemos las cadenas en el mismo orden, entonces estaremos ante un segmento no-vinculado. Otra forma sería comprobar estadísticamente si en distintos ciclos del algoritmo, los mismos valores para un segmento producen posiciones relativas parecidas dentro de la lista de agentes ordenados por peso. Por ejemplo, si una variable puede tomar valores de 1 a 10, podemos almacenar, para cada valor, cuál es la posición media que ocupa la cadena que la contiene, dentro de la lista de cadenas ordenadas por pesos, en cada uno de los ciclos.

Otra forma de encontrar las vinculaciónes sería definirlas al azar y actuar como si de hecho existiesen, comprobando si de esta forma se obtienen mejores resultados. Por último, voy a presentar la que me parece la forma más fácil de todas. Para el algoritmo es mucho más sencillo encontrar los valores óptimos de los segmentos no-vinculados que los de los vinculados. Por tanto, después de unos cuantos ciclos, los genes de valores más homogéneos tendrán una mayor probabilidad de ser más no-vinculados que el resto. Los genes vinculados se comportan en realidad como un único gen, por lo que se ha de evitar su división. Se me ocurre que podríamos obtener alguna ventaja si obligamos a que exista una especie de cohesión entre los genes vinculados, es decir, entre los segmentos de valores más heterogéneos, de forma que se hereden y muten juntos, simultáneamente, con una mayor probabilidad.

Apendice

Referencias sobre Vida Artificial

[A1] "Jugué a ser Dios y creé la vida en mi computadora". Ray, Thomas S. Emocionante relato que describe una de las primeras simulaciones de vida por ordenador. http://www.hip.atr.co.jp/~ray/pubs/spanish/spanish.html

[A2] "Vida Artificial". Prata, Stephen. 1993. Ed. Anaya. Buen libro para iniciarse en el tema.

[A3] Swarm: multi-agent simulation of complex systems. Plataforma de desarrollo de vida artificial para Unix Linux GNU. http://www.santafe.edu/projects/swarm/

[A4] Vida Artificial en español. J. J. Merelo. Universidad de Granada. http://kal-el.ugr.es/VidArt/VidaArti.html

[A5] Linux Alife. Vida Artificial y recursos para Linux. http://aisun0.ai.uga.edu/~jae/ai.html

[A6] "Vamos a Crear Vida en un PC". Herrán, Manuel de la. Revista Solo Programadores nş 36 Agosto 1997.

[A7] "Emergent Computation: Self Organizing, Collective, and Cooperative Phenomena in Natural and Artificial Computing Networks". Forrest, Stephanie (Ed.) Revista Artificial Intelligence nş 60. 1993.

[A8] "Agent Oriented Programming". Shoham, Yoar. Revista Artificial Intelligence nş 60. 1993.

[A9] "Vida Artificial". Fernandez Ostolaza, Julio, y Moreno Bergareche, Alvaro. 1992. Ed. Eudema. Epistemología de la Vida Artificial, pasa revista a la historia de la Vida Artificial.

[A10] Gaia. Algoritmos Genéticos, Vida Artificial y Aprendizaje. Proyecto de una plataforma de Vida Artificial. gaiaweb.dhs.org/

Apendice

Referencias sobre Computación Evolutiva y aprendizaje

[B1] "Algoritmos Genéticos". Holland, John H. Revista Investigación y Ciencia, Septiembre 1992. Fantástico resumen del "padre" de los algoritmos genéticos.

[B2] Matemáticas Aplicadas: Vida Artificial y Algoritmos Genéticos. Blanca Cases y Pedro Larrañaga. Universidad del País Vasco. Muy interesante. http://www.geocities.com/CapeCanaveral/9802/

[B3] "Sistemas expertos en contabilidad y administración de empresas". Sierra Molina, Guillermo, y otros. 1995. Editorial Ra-Ma. Algorimos Genéticos, Redes Neuronales y otras técnicas de resolución de problemas, explicado de una forma clara y sencilla.

[B4] "Algoritmos Genéticos Avanzados". Herrán, Manuel de la. Revista Solo Programadores nş 37 Septiembre 1997.

[B5] "Made Up Minds". Drescher, Gary L. 1991. MIT Press. Fantástico libro sobre el aprendizaje automático.

[B6] "Aprendizaje Automático y Vida Artificial". Herrán, Manuel de la. Revista Solo Programadores nş 38 Octubre 1997.

[B7] "Adpatation in Natural and Artificial Systems". Holland, John H. University of Michigan Press. 1975.

[B8] "Temas Metamágicos". Hofstadter, Douglas R. Revista Investigación y ciencia, Agosto 1983.

[B9] "Agentes Autodidactas ¿Futuro o Realidad?". Herrán, Manuel de la. Revista BASE nş 30 Noviembre 1996.

[B10] "El ordenador cerebral". Jáuregui, José Antonio. 1990. Editorial Labor. Un punto de vista muy original acerca del ser humano, la inteligencia y el darwinismo.

[B11] Guía del Autoestopista de la Computación Evolutiva ("The Hitch-Hiker's Guide to Evolutionary Computation") Heitkötter, Jörg and Beasley, David, eds. FAQ de comp.ai.genetic con definiciones y clasificaciones de los términos más comunes en Computación Evolutiva. http://www.etsimo.uniovi.es/ftp/pub/EC/FAQ/www/top.htm

[B12] Ph.D. dissertation, U.Mich. Rosenberg. 1967.

[B13] "Handbook of Evolutionary Computation". Baeck, Thomas; Fogel, David B. (eds.) 1997. Oxford, NY.

[B14] "Evolutionary Computation: Toward a New Philosophy of Machine Intelligence". Fogel, David B. 1995. IEEE Press.

Apendice

Referencias sobre Darwinismo, Genética, y Evolución

[C1] "El gen egoísta". Dawkins, Richard. 1994. Salvat Ciencia.

[C2] Introducción en "El Origen de las especies" de Charles Darwin. Leakey, Richard E.1994. Ediciones del Serbal - Reseña. Exposición sencilla y muy acertada del darwinismo.

[C3] "¿Tiene sentido la vida fuera de sí misma?". Dawkins, Richard. Revista Investigación y ciencia, Enero 1996.

[C4] "El universo inteligente". Hoyle, Fred. 1983. Ed. Grijalbo. Una valiente crítica al darwinismo.

[C5] "El apoyo mutuo". Kropotkin, Pedro. 1970. Ediciones Madre Terra. Trata el darwinismo y la cooperación.

[C6] "La evolución sin Darwin: La biología ultramontana", en la revista "Revista de Libros", número 9 (septiembre de 1997). Castrodeza, Carlos. 1997. Ed. fundación Caja Madrid.

[C7] "Un siglo después de Darwin 1. La Evolución". Barnett y Otros. 1962. Alianza Editorial.

[C8] "El pulgar del panda" Gould, Stephen Jay. Ed. Hermann Blume.

[C9] "Lamarck y los mensajeros. La función de los virus en la evolución". Sandín, Máximo. 1995. Ed. Istmo.

Apendice

Referencias sobre Redes Neuronales

[D1] Capítulo "Perceptrones" en Dewney, A. K. "Aventuras Informáticas". Ed Labor, 1990. Los perceptrones corresponden con el nacimiento de las redes neuronales, y suponen una versión simplificada de éstas.

[D2] Capítulo "Redes Neuronales" en Sierra Molina, Guillermo, y otros. "Sistemas expertos en contabilidad y administración de empresas". Ed. Ra-Ma, 1995. Explica el funcionamiento más básico de redes neuronales.

[D3] "Redes Neuronales". Luna, Raúl. Solo Programadores 1994.

[D4] "Redes Neuronales". Obiol, Pablo. Jumping. Julio 1997.

[D5] Capítulos "Aprendizaje y Generalización" y "Redes Borrosas y Evolutivas". En Ignacio Olmeda y S. Barba. "Redes Neuronales Artificiales: fundamentos y aplicaciones". 1993.

[D6] "Chaos, artificial neural networks and the predictability of stock market returns". Olmeda, Ignacio y Pérez, Joaquín. 1994.

[D7] "Neural networks forecasts of intra-day futures and cash returns". Isasi, Pedro; Olmeda, Ignacio; Fernández, Eugenio, y Fernández, Camino.

Apendice

Otras referencias

[E1] "Guía del Autoestopista Galáctico". Adams, Douglas. 1983. Editorial Anagrama. Ciencia-ficción, relato de humor. Presenta el planeta Tierra como un super-ordenador biológico.

[E2] "Visitantes Milagrosos". Watson, Ian. 1987. Ed. grupo zeta. Estados alterados de conciencia, fenómeno ovni, ecología, enseñanzas sufíes, mecánica cuántica y teorema de Gödel. Único.

[E3] "El misterio de la isla de Tökland". Gisbert, Joan Manuel. 1981. Ed. Espasa-Calpe.

[E4] "Las nueve Revelaciones". Redfield, James. 1997. Ediciones B, S.A. Evolución, Teilhard de Chardin y Gestalt.

[E5] "Las voces del desierto". (Muttant Message Down Under). Morgan, Marlo. 1996. Ediciones B.

[E6] "El problema de la consciencia". Chalmers, David J. Revista Investigación y ciencia. Febrero 1996.

[E7] "Ética para amador" Savater, Fernando. 1996. Ed Ariel.

 


 

Sobre el documento


Publicado en marzo de 1998 en la revista "Solo Programadores" (nş 43) y revisado en abril de 1999 por el autor.





Sobre el autor


Manuel de la Herrán nació en Bilbao en 1971. Es ingeniero informático y ha trabajado en varias empresas desarrollando tecnología en Internet y dirigiendo sus departamentos técnicos (Okté, Cocotero, EnLaPrensa). Ha escrito numerosos artículos sobre Evolución, Computación Evolutiva, Algoritmos Genéticos, Inteligencia Artificial, OLAP y Bases de Datos Multidimensionales, Bases de datos Oracle y Programación en Internet. Ha sido profesor de la Universidad de Deusto y es el creador de webs como Gaia (finalista iBest 2000), REDcientífica (Premio Nacional Sociedad de la Información), REDhumana.com, iieh.com, y MUNDO.ENk3.com.


 

  • Evaluación: se trata de asignar un valor de peso o fitness a cada individuo, en función de lo bien que resuelve el problema.
  • Selección: ahora debemos clasificar a los agentes en cuatro tipos, según sobrevivan o no, y según se reproduzcan o no, en función de los pesos.
  • Reproducción: se generan los nuevos individuos, produciéndose algunas mutaciones en los nacimientos.

 

En realidad las dos primeras fases se pueden fundir en una, ya que no es estrictamente necesario asignar a cada entidad un peso, sino simplemente saber cuáles son mejores que otras, pero asignar pesos suele ser lo más cómodo. También podemos combinar la segunda y la tercera generando las nuevas entidades únicamente en la zona de memoria donde se encuentran los agentes a eliminar, y mantener así la población constante. En cualquier caso, siempre existirá alguna forma de evaluación, selección y reproducción. Cada uno de estos procesos se puede realizar de muchas formas distintas, independientemente del problema que se esté resolviendo.

En la siguiente tabla se resumen algunas opciones de un algoritmo evolutivo. Podemos idear muchas más. En general se trata de distintas formas de producir, o bien una convergencia más rápida hacia una solución, o bien una exploración más a fondo del espacio de búsqueda. Ambas cosas son deseables y contradictorias, por lo que se ha de llegar a un compromiso. Este compromiso es lo que antes he llamado cooperación. Por supuesto que todo esto no son más que metáforas. Se requiere de una fuerza conservadora (explotación-egoísmo), que beneficie a los mejores agentes, es decir, a los que mejor resuelvan nuestro problema. Esto es evidente, pero no basta. También es necesaria una fuerza innovadora (exploración-altruismo), que permita la existencia de agentes muy distintos, aún cuando su peso sea menor. Así se puede obtener la variedad suficiente para evitar una población estancada en un máximo local, y permitir la resolución de problemas cambiantes o con varios máximos. Esto ocurre de forma espontánea en la naturaleza por ser algo inherente a cada entidad, que puede ser seleccionado, pero resulta más cómodo programarlo de forma externa, es decir, haremos que nuestro programa seleccione para la reproducción "los agentes buenos", pero también "unos cuantos de los malos" para mantener la variedad.

Apendice

 

  • Opciones Generales
    • Número de entidades.
    • Número de elementos (genes, reglas) por cada agente.
  • Método de Evaluación: Asignar un peso
    • Desordenar las entidades antes de evaluarlas
    • Diferentes formas de modificación de los pesos después de la evaluación. Por ejemplo, el peso de una entidad se puede calcular independientemente de las demás entidades, o se puede modificar posteriormente este valor, disminuyendo el peso si existe otra entidad muy parecida, analizando para ello un cierto subconjunto de la población vecina.
  • Método de Selección: ¿Quién muere? ¿Quién se reproduce?
    • Con o sin reemplazamiento
    • Método de la ruleta
    • Método de los torneos
    • Seleccionar el n% mejor y el m% peor
  • Método de Reproducción: Generar y mutar nuevos hijos
    • Los padres pueden tomarse por parejas o en grupos más numerosos, elegidos al azar o en orden de pesos
    • En el caso de detectar que los progenitores son muy parecidos, se puede realizar una acción especial, como incrementar la probabilidad de mutación
    • Las entidades pueden comunicar a otras su conocimiento, ya sea a toda o a una parte de la población, directamente o a través de una pizarra, (una especie de tablón de anuncios)
    • Método de recombinación de genes: se puede tomar genes de uno u otro progenitor al azar, en un cierto orden, con uno, dos o más puntos de corte, etc.
    • Tasa de mutación variable
    • Fijar una tasa de mutación diferente para cada individuo o incluso para cada gen
    • Hacer que sea más probable que se produzca una mutación en un gen si en su vecino ya se ha producido [B4]
    • Sustituir por mutaciones genes sin utilidad, como reglas incorrectas o repetidas
    • Tipos de mutaciones

 

Los tipos de mutaciones requieren de una mayor explicación. Cuando los genes son bits, una mutación consiste en invertir un bit, pero ¿cómo mutar genes cuando cada gen puede tomar mas de dos valores? Supongamos que tenemos un problema con tres variables de 8 bits cada una. Tendríamos cadenas como:

 

  10001000-0101011111-11101110  

 

Vamos a suponer que es probable que existan zonas de valores buenas y malas; es decir, que si el 7 es un buen valor y el 200 malo, será probable que también el 8 sea bueno y el 199 malo. Sería interesante que las mutaciones nos permitiesen movernos (cambiar de valor) lentamente y con exactitud si estamos en la zona buena, pero también rápida y bruscamente por si acaso nos encontráramos en la mala. Esto lo podemos conseguir precisamente cambiando un bit al azar, ya que nos movemos lentamente cambiando bits de la parte derecha, y rápidamente con los de la izquierda. En cambio, si la mutación consistiera en cambiar el valor de toda una variable por otro cualquiera, teniendo todos la misma probabilidad, podremos movernos rápidamente, pero no lentamente (al menos, con una probabilidad baja), con lo que perderíamos valores interesantes. Si las mutaciones consistieran en incrementar o restar uno de forma circular, podríamos movernos lentamente, pero no rápidamente, con lo que costaría mucho salir de la zona mala. En definitiva se trata de, dado un valor, definir la probabilidad de pasar a cada uno de los valores restantes.

Hemos supuesto que existen zonas de valores buenas y malas. Si esto no se cumpliera podríamos simplemente "incrementar uno" de forma circular, para recorrer todos los valores cuanto antes. En general se observa que las mutaciones a nivel de bit son las más adecuadas, aunque no siempre ocurre así. En cualquier caso, cuando combinemos dos cadenas deberemos actuar a nivel de variable, y combinar variables completas. De lo contrario estaríamos generando multitud de mutaciones simultáneas, rompiendo por cualquier lugar valores que pueden ser valiosos.

Apendice

Programas autoconfigurables

¿Qué opciones son las buenas? Tal vez sea posible determinar a simple vista si una elección es adecuada, pero en la mayoría de los casos será necesario un tedioso proceso de prueba, ya que la bondad de unas puede depender de la elección de otras. Si algo se aprende programando algoritmos evolutivos es que las ideas geniales no siempre lo son. Es muy corriente la existencia de parámetros que aunque disminuyen el número de ciclos necesarios para llegar al tipo de entidad que buscamos, en la práctica no son rentables dado el incremento de la duración de los ciclos.

Ejecutar todas las posibles combinaciones de opciones es inconcebible ¿No será posible analizar varias en un único algoritmo, en diferentes momentos? ¿Y que tal analizar varias opciones simultáneamente, en fracciones separadas de la población? Es decir, ¿Podemos crear algoritmos evolutivos autoconfigurables? Para responder a estas preguntas es interesante agrupar todos los aspectos y opciones en cuatro categorías, según la siguiente figura.

 

  • Tipo gen
    Los aspectos de tipo gen serán aquellos que, como los genes, son diferentes dentro de un mismo individuo.
  • Tipo individuo
    Los aspectos de tipo individuo son aquellos que se mantienen iguales en un mismo individuo, pero difieren de unos agentes a otros.
  • Tipo isla
    Los aspectos de tipo isla son aquellos que son iguales para un subconjunto de individuos; de más de uno, pero sin llegar al total.
  • Tipo población
    Los aspectos de tipo población son los que deben ser iguales para toda la población.

 

Las opciones o aspectos de tipo gen pueden probarse introduciéndolos como parte de cada uno de los genes, dentro de cada uno de los genes. Si se quiere, se puede pensar en una matriz de dos dimensiones más que en una cadena de genes. Vamos a verlo en el caso de un programa que aprende a jugar al tres en raya [B6] como el que aparece en el CD-ROM. Cada uno de los genes es una regla que dice cómo jugar ante determinada situación. Antes de realizar un movimiento, el agente comprueba qué reglas puede usar y elige una de ellas. ¿Cómo elegirla? Podríamos pensar en asociar inicialmente a cada regla una prioridad arbitraria fija, y elegir la de mayor prioridad. Otra forma sería asignar a cada regla un peso que se incrementase cada vez que dicha regla fuera usada en una partida ganada, y aplicar la regla que en más victorias haya participado hasta el momento. Para llevar a la practica cualquiera o las dos opciones combinadas, bastará con incluir la información como parte de cada gen. Si antes cada gen era una regla, ahora cada gen será una regla, más un valor de prioridad, más un peso. Otra opción de tipo gen sería asignar una probabilidad de mutación distinta para cada elemento de la cadena, de forma que los genes, después de ser heredados, tengan diferentes probabilidades de mutarse [B12] [B13] [B14]. Si en un determinado momento, cierto valor de un gen se muestra como muy útil, puede ser interesante que su probabilidad de mutación disminuya, y viceversa.

http://geneura.ugr.es/~jmerelo/DegaX/GenAlg.html

Apendice

Introducción a los Algoritmos Genéticos

Carlos A. Coello Coello

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 alrededor del mundo durante los últimos años. Se presentarán aquí los conceptos básicos que se requieren para abordarla, así como un sencillo ejemplo que permita a los lectores comprender cómo aplicarla al problema de su elección. Adicionalmente, se hablará acerca de los diversos ambientes de programación actuales basados en algoritmos genéticos y de las áreas abiertas de investigación.

Apendice

 

Orígenes

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 (unidad básica de codificación de cada uno de los atributos de un ser vivo) de un individuo, y que los atributos más deseables (i.e., los que le permiten a un individuo adaptarse mejor a su entorno) del mismo se transmiten a sus descendientes, cuando éste se reproduce sexualmente.

Un investigador de la Universidad de Michigan llamado John Holland estaba consciente de la importancia de la selección natural, y a fines de los 60s desarrolló una técnica que permitió incorporarla en un programa de computadora. 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 1975.

Apendice

 

Definición

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.

¿Cómo saber si es posible usar el 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 debe 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 respuestas 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.

Apendice

 

Funcionamiento de un Algoritmo Genético Simple

La operación de un algoritmo genético simple puede ilustrarse con el generar población inicial, G(0);

evaluar G(0);

t:=0;

repetir

t:=t+1;

generar G(t) usando G(t-1);

evaluar G(t);

hasta encontrar una solución;

Primero, se genera aleatoriamente la población inicial, que estará constituída por un conjunto de cromosomas, o cadenas de caracteres que representan las soluciones posibles del problema. A cada uno de los cromosomas de esta población se le aplicará la función de aptitud a fin de saber qué tan buena es la solución que está codificando.

Sabiendo la aptitud de cada cromosoma, se procede a la selección de los que se cruzarán en la siguiente generación (presumiblemente, se escogerá a los "mejores"). Dos son los métodos de selección más comunes:

es muy simple, y consiste en crear una ruleta en la que cada cromosoma tiene asignada una fracción proporcional a su aptitud. Sin que nos refiramos a una función de aptitud en particular, supongamos que se tiene una población de 5 cromosomas cuyas aptitudes están dadas por los valores mostrados en la Tabla 1.

Cromosoma No.

Cadena

Aptitud

% del Total

1

11010110

254

24.5

2

10100111

47

4.5

3

00110110

457

44.1

4

01110010

194

18.7

5

11110010

85

8.2

Total

1037

100.0

Tabla 1: Valores de ejemplo para ilustrar la selección mediante ruleta

Apendice

Con los porcentajes mostrados en la cuarta columna de la Tabla 1 podemos elaborar la ruleta de la Figura 1. Esta ruleta se gira 5 veces para determinar qué individuos se seleccionarán. Debido a que a los individuos más aptos se les asignó un área mayor de la ruleta, se espera que sean seleccionados más veces que los menos aptos.

Figura 1: Ruleta que representa los valores de aptitud de la Tabla 1

2) El torneo: La idea de este método es muy simple. Se baraja la población y después se hace competir a los cromosomas que la integran en grupos de tamaño predefinido (normalmente compiten en parejas) en un torneo del que resultarán ganadores aquéllos que tengan valores de aptitud más altos. Si se efectúa un torneo binario (i.e., competencia por parejas), entonces la población se debe barajar 2 veces. Nótese que esta técnica garantiza la obtención de múltiples copias del mejor individuo entre los progenitores de la siguiente generación (si se efectúa un torneo binario, el mejor individuo será seleccionado 2 veces).

Una vez realizada la selección, se procede a la reproducción sexual o cruza de los individuos seleccionados. En esta etapa, los

sobrevivientes intercambiarán material cromosómico y sus descendientes formarán la población de la siguiente generación. Las 2 formas más comunes de reproducción sexual son: uso de un punto único de cruza y uso de 2 puntos de cruza.

Cuando se usa un solo punto de cruza, éste se escoge de forma aleatoria sobre la longitud de la cadena que representa el cromosoma, y a partir de él se realiza el intercambio de material de los 2 individuos, tal y como se muestra en la Figura 2.

Cuando se usan 2 puntos de cruza, se procede de manera similar, pero en este caso el intercambio se realiza en la forma mostrada en la Figura 3.

Normalmente la cruza se maneja dentro de la implementación del algoritmo genético como un porcentaje que indica con qué frecuencia se efectuará. Esto significa que no todas las parejas de cromosomas se cruzarán, sino que habrán algunas que pasarán intactas a la siguiente generación. De hecho existe una técnica desarrollada hace algunos años en la que el individuo más apto a lo largo de las distintas generaciones no se cruza con nadie, y se mantiene intacto hasta que surge otro individuo mejor que él, que lo desplazará. Dicha técnica es llamada elitismo, y no debe sorprendernos el hecho de que haya sido desarrollada en Alemania.

Figura 2: Uso de un solo punto de cruza entre 2 individuos. Observe que cada pareja de cromosomas da origen a 2 descendientes para la siguiente generación. El punto de cruza puede ser cualquiera de los 2 extremos de la cadena, en cuyo caso no se realiza la cruza.

Figura 3: Uso de 2 puntos de cruza entre 2 individuos. Note como en este caso se mantienen los genes de los extremos, y se intercambian los del centro. También aquí existe la posibilidad de que uno o ambos puntos de cruza se encuentren en los extremos de la cadena, en cuyo caso se hará una cruza usando un solo punto, o ninguna cruza, según corresponda.

Además de la selección y la cruza, existe otro operador llamado mutación, el cual realiza un cambio a uno de los genes de un cromosoma elegido aleatoriamente. Cuando se usa una representación binaria, el gene seleccionado se sustituye por su complemento (un cero cambia en uno y viceversa). Este operador permite la introducción de nuevo material cromosómico en la población, tal y como sucede con sus equivalentes biológicos.

Al igual que la cruza, la mutación se maneja como un porcentaje que indica con qué frecuencia se efectuará, aunque se distingue de la primera por ocurrir mucho más esporádicamente (el porcentaje de cruza normalmente es de más del 60%, mientras que el de mutación normalmente nunca supera el 5%).

Si supiéramos la respuesta a la que debemos llegar de antemano, entonces detener el algoritmo genético sería algo trivial. Sin embargo, eso casi nunca es posible, por lo que normalmente se usan 2 criterios principales de detención: correr el algoritmo genético durante un número máximo de generaciones o detenerlo cuando la población se haya estabilizado (i.e., cuando todos o la mayoría de los individuos tengan la misma aptitud).

¿Qué Ventajas y Desventajas tienen con respecto a otras técnicas de búsqueda?

· 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 masivas en paralelo.

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

Un Ejemplo de Uso

Con la finalidad de aclarar mejor los conceptos cubiertos previamente, presentaremos ahora una sencilla aplicación del algoritmo genético a

Un grupo de financieros mexicanos ha resuelto invertir 10 millones de pesos en la nueva marca de vino "Carta Nueva".

Así pues, en 4 ciudades de las principales de México se decide iniciar una vigorosa campaña comercial: México en el centro, Monterrey en el noroeste, Guadalajara en el occidente y Veracruz en el oriente. A esas 4 ciudades van a corresponder las zonas comerciales I, II, III y IV. Un estudio de mercado ha sido realizado en cada una de las zonas citadas y han sido establecidas curvas de ganancias medias en función de las inversiones totales (almacenes, tiendas de venta,

representantes, publicidad, etc.) Estos datos se ilustran en la Tabla 2 y en la Figura 5.

Para simplificar los cálculos, supondremos que las asignaciones de créditos o de inversiones deben hacerse por unidades de 1 millón de pesos. La pregunta es: ¿en dónde se deben de asignar los 10 millones de pesos de los que se dispone para que la ganancia total sea máxima?

1) Representación: Lo primero que necesitamos determinar para poder aplicar el algoritmo genético, es cuál será el esquema a utilizarse para representar las posibles soluciones del problema. En este caso necesitamos 4 bits (24 = 16) para representar cada solución, porque cada una admite 11 valores posibles (de 0 a 10). Como existen 4 valores independientes (uno por cada zona de estudio), se requieren entonces 16 bits (4 x 4) por cada cromosoma. De tal forma, una cadena representativa de un cromosoma será como se muestra en la Figura 4. Es importante hacer notar que se requiere una función de codificación (i.e., que transforme el valor de la inversión a binario) y una de decodificación (i.e., que realice el proceso inverso). Debido a que en este caso los 4 bits utilizados para representar una solución pueden producir más valores de los que se necesitan, se usará una función de ajuste que haga que los resultados producidos siempre se encuentren en el rango válido.

Apendice

 

Inversión

(en millones)

Beneficio I

Beneficio II

Beneficio III

Beneficio IV

0

0

0

0

0

1

0.28

0.25

0.15

0.20

2

0.45

0.41

0.25

0.33

3

0.65

0.55

0.40

0.42

4

0.78

0.65

0.50

0.48

5

0.90

0.75

0.62

0.53

6

1.02

0.80

0.73

0.56

7

1.13

0.85

0.82

0.58

8

1.23

0.88

0.90

0.60

9

1.32

0.90

0.96

0.60

10

1.38

0.90

1.00

0.60

Tabla 2: Datos obtenidos con la investigación de mercado en cada una de las regiones en estudio.

Apendice

2) Función de Aptitud: Dado que el objetivo es obtener las inversiones que sumen 10, y que tengan un beneficio máximo, podemos usar la siguiente función de aptitud penalizada:

donde c1, c2, c3 y c4 son las ganancias por zona, que se calculan de acuerdo a los valores de la Tabla 2, y v es el valor absoluto de la diferencia entre la suma obtenida y 10. Nótese que cuando no se viole ninguna restricción (i.e., cuando la suma de inversiones sea exactamente 10) la función de aptitud no será "castigada".

Figura 4: Cadena representativa de un cromosoma de los utilizados en nuestro ejemplo de optimización. Las cadenas 1, 2, 3 y 4 corresponden a las cantidades invertidas en las zonas económicas respectivas.

3) Operadores: Se usará una cruza de 2 puntos, la cual se efectúa de la forma que se indica en la Figura 3. La probabilidad que se dará a la misma será del 80%. En cuanto a la mutación, se le asignará una del orden del 1%. El tamaño de población manejado para este ejemplo será de 50 cromosomas, y se correrá el algoritmo genético durante 20 generaciones.

4) Resultados: El resultado obtenido en una corrida típica es de $1.81 (en millones de pesos), correspondiente a los valores de C1=4 millones, C2=3 millones, C3=1 millón y C4=2 millones. Esta es la solución óptima, la cual se obtuvo originalmente mediante programación este valor fue de sólo 13 segundos. Debe hacerse notar que, en este caso, si deseáramos analizar inversiones que sumen otra cantidad, y en unidades menores al millón, el algoritmo genético tendría que modificarse de manera mínima, mientras que la programación dinámica requeriría una cantidad tal de trabajo que prácticamente se volvería inoperante.

Figura 5: Gráfica de los valores de la Tabla 2.

Aunque éste es sólo un sencillo ejemplo del uso del algoritmo genético para resolver problemas de optimización con restricciones, puede alcanzar a percibirse el poder de la técnica en comparación con los métodos tradicionales de búsqueda. Para saber más acerca de las múltiples aplicaciones que se les han encontrado a los algoritmos los detalles de implementación elementales, resulta de gran utilidad programa está escrito en Turbo Pascal, aunque también existe una El autor ha proporcionado a los editores de esta revista el código completo en Turbo Pascal 7.0 de un algoritmo genético basado en el SGA de Goldberg, el cual se utilizó para resolver el ejemplo incluído en consta de un módulo único que hace uso de manejo dinámico de memoria, las modificaciones necesarias para incorporar cruza de 2 puntos y selección mediante torneo binario, entre otras cosas. El análisis de este código bien puede ser el punto de partida para los interesados en implementar un algoritmo genético.

Apendice

 

Ambientes de Programación

En la actualidad existe un gran número de ambientes de programación disponibles en el mercado para experimentar con los algoritmos distinguirse 3 clases de ambientes de programación:

1) Sistemas Orientados a las aplicaciones: Son esencialmente "cajas negras" para el usuario, pues ocultan todos los detalles de implementación. Sus usuarios -normalmente neófitos en el área- los utilizan para un cierto rango de aplicaciones diversas, pero no se interesan en conocer la forma en qué éstos operan. Ejemplos de este tipo de sistemas son: Evolver (Axcelis, Inc.) y XpertRule GenAsys (Attar Software).

2) Sistemas Orientados a los algoritmos: Soportan algoritmos genéticos específicos, y suelen subdividirse en:

· Sistemas de uso específico: Contienen un solo algoritmo genético, y se dirigen a una aplicación en particular. Algunos ejemplos son: Escapade (Frank Hoffmeister), GAGA (Jon Crowcroft) y Genesis (John Grefenstette).

· Bibliotecas: Agrupan varios tipos de algoritmos genéticos, y diversos operadores (e.g. distintas formas de realizar la cruza y la selección). Evolution Machine (H. M. Voigt y J. Born) y OOGA (Lawrence Davis) constituyen 2 ejemplos representativos de este grupo.

En estos sistemas se proporciona el código fuente para que el usuario -normalmente un programador- pueda incluir el algoritmo genético en sus propias aplicaciones.

3) Cajas de Herramientas: Proporcionan muchas herramientas de programación, algoritmos y operadores genéticos que pueden aplicarse en una enorme gama de problemas. Normalmente se subdividen en:

· Sistemas Educativos: Ayudan a los usuarios novatos a introducirse de forma amigable a los conceptos de los algoritmos genéticos. GA Workbench (Mark Hughes) es un buen ejemplo de este tipo de ambiente.

· Sistemas de Propósito General: Proporcionan un conjunto de herramientas para programar cualquier algoritmo genético y desarrollar cualquier aplicación. Tal vez el sistema más conocido de este tipo es Splicer (NASA).

Apendice

 

Areas de Investigación

Durante los últimos años una gran parte de la investigación en esta área se ha concentrado en el desarrollo de mejoras al desempeño de los algoritmos genéticos. Se han propuesto nuevas técnicas de

representación, selección y cruza, con resultados muy alentadores. Por ejemplo, el uso de los códigos de Gray y la codificación dinámica han superado algunos de los problemas asociados con la representación de valores reales mediante cadenas binarias. También se han propuesto técnicas adaptativas que varían dinámicamente los parámetros de control (porcentajes de mutación y cruza), en contraposición con el esquema estático tradicional. Otras innovaciones notables son los algoritmos genéticos distribuidos y los algoritmos genéticos paralelos. Una buena recopilación de este trabajo puede encontrarse en

Por otra parte, el fundamento matemático de los algoritmos genéticos sigue siendo otra área abierta de investigación. Resulta de especial interés el desarrollo de modelos de la dinámica de los algoritmos genéticos, el análisis de problemas que resultan difíciles para la técnica, pruebas de convergencia y en general, el tratar de comprender mejor cómo funcionan. Para los interesados en saber qué se ha logrado

Probablemente uno de los trabajos de investigación más notables en el área sea el realizado por John Koza, que desarrolló una técnica de cruza que permite evolucionar expresiones-S de un programa en LISP. Esta innovadora forma de programación automática puede aplicarse a un enorme número de problemas, y por tal razón Koza -que por cierto fue discípulo de Holland, al igual que Goldberg- se apresuró a patentar prueba muy populares entre los expertos en computación. Su obra incluye código en Common LISP para que los interesados puedan experimentar con lo que ha dado en llamarse Programación Genética. Yendo todavía más lejos, John Koza nos muestra en un libro de más problemas de mayor complejidad, y da testimonio de implementaciones realizadas en lenguajes procedurales como C y C++, rompiendo así el mito de que sólo un lenguaje de las características propias de LISP podría utilizarse para la programación genética. La propuesta de Koza ha sido acogida con beneplácito por un gran número de investigadores alrededor del mundo, sobre todo en el área de aprendizaje máquina.

Apendice

 

Conclusiones

Se ha tratado de proporcionar de forma breve y concisa un panorama general de lo que son los algoritmos genéticos y su utilidad, sin que se llegara a profundizar mucho en ninguno de sus aspectos en particular. Las referencias bibliográficas proporcionadas deberán servir para que el lector interesado pueda averiguar más detalles por su cuenta. De cualquier forma, se recomienda a todo aquel interesado sólida base matemática de la técnica, y el segundo ahonda en los detalles de implementación, y explica muchos aspectos de su funcionamiento de una manera sencilla y agradable.

El éxito actual de los algoritmos genéticos se refleja en tres conferencias bianuales, una nueva revista internacional dedicada al tema y un sinnúmero de publicaciones alrededor del mundo. Este interés se ha visto ya reflejado en nuestro país, puesto que centros de investigación como LANIA (Laboratorios Nacionales de Informática Avanzada), así como científicos independientes han publicado varios trabajos sobre el tema. Es de esperarse que en los años siguientes más gente se sentirá atraída por esta novedosa técnica, por lo que tal vez lo más conveniente resulte saber aunque sea lo mínimo necesario sobre ella. De esa forma no nos sentiremos tan fuera de sitio en la siguiente charla que tengamos con otros profesionales de la computación.

Apendice

 

Referencias

University of Michigan Press, 1975, 211 p.

Computers by Means of Natural Selection", The MIT Press, 1992, 819 p.

Computer Society Press, 1992, 109 p.

and Machine Learning", Addison-Wesley Publishing Company, 1989, 412 p.

Systems and Genetic Algorithms", en Artificial Intelligence, 40, 1989, pp. 235-282.

Nostrand Reinhold, 1991, 385 p.

Selection Applied to Computation", en Science, Vol. 261, No. 5123, Agosto 13 de 1993, pp. 872-878.

: A C-language Implementation of a Simple Genetic Algorithm", TCGA Report No. 91002, The Clearinghouse for Genetic Algorithms, The University of Alabama, Mayo 14 de 1991.

"Genetic-Algorithm Programming Environments", en IEEE Computer, Junio de 1994, pp. 28-43.

en IEEE Computer, Junio de 1994, pp. 17-26.

Algorithms", Morgan Kaufmann Publishers, 1991, 341 p.

2", Morgan Kaufmann Publishers, 1993, 322 p.

Operaciones", Segunda Edición, CECSA, México, 1977, 311 p.

Software Tools for the Professional Programmer, Vol. 13, No. 3, 1988, pp. 60-3.

Reusable Programs", The MIT Press, 1992, 746 p.

Lecturas Adicionales

· Holland, John H. "Genetic Algorithms", en Scientific American 267, Julio de 1992, pp. 66-72.

· Michalewicz, Zbigniew. "Genetic Algorithms + Data Structures = Evolution Programs", Springer-Verlag, 1992, 250 p.

Denning, Peter J. "Genetic Algorithms", en American Scientist, Volume 80, January-February 1992, pp. 12-14.

Apendice

 

www.redcientifica.com/doc/doc199904260011.html

www.lania.mx/~ccoello/columnas/

www.lania.mx/~ccoello/papers.html

 

Repositorios

www.cs.cinvestav.mx/~EVOCINV/

Apendice

 

 

 

Laboratorios

 

Centro de Investigación en Computación

(CIC)

Centro Nacional de Investigación y Desarrollo Tecnológico

(CENIDET)

Centro de Investigación en Matemáticas

(CIMAT)

Centro de Investigación y Estudios Avanzados

(CINVESTAV)

Instituto Nacional de Astrofísica, Optica y Electrónica

(INAOE)

Instituto Tecnológico Autónomo de México

(ITAM)

Instituto Tecnológico y de Estudios Superiores de Monterrey

(Campus, Edo. Mex, Morelos y Monterrey)

Laboratorio Nacional de Informática Avanzada A.C.

(LANIA)

Universidad Autónoma de Sinaloa

(UAS)

Universidad Tecnológica 

De la Mixteca

(UTM)

Universidad de las Américas

(UDLA)

Centro de Investigación y Computación de Ensenada

(CICESE)

Universidad Nacional Autónoma de México

(UNAM)

http://www.inegi.gob.mx/informatica/espanol/pim/programa/programas/conacyt/RDII2000.HTML

 

Apendice

 

Investigadores

    CINVESTAV

Dr. Carlos A. Coello Coello .

     http://cacic2003.info.unlp.edu.ar/curriemoo.pdf

Dr. Guillermo Morales Luna.

Dr.  Oscar Olmedo.

Dra. Xiaoou Li.

 

http://www.cs.cinvestav.mx/Lineas/Fundamentos.html

     Universidad de Malaga

Enrique Alba Torres

Carlos Cotta Porras

     Universidad de Granada

Francisco Herrera

 

http://polaris.lcc.uma.es/~ccottap/wceta97/wceta97.html

     CITEDI-IPN

Dr. Alfonso Angeles Valencia

Dr. Konstantin Starkov Evguenievich

M.C. David Jaime Saucedo Martínez

M.C. Oscar Humberto Montiel Ross

Dr. Leonardo Acho Zuppa

Dr. Sergio A. Herrera García

Dr. Luis Arturo González Hernández

M.C. Andrés Calvillo Téllez

Dr. Miguel A. Alvarez Cabanillas

Dr. Sergio A. Herrera García

 

http://www.citedi.net/docs/proy_ipncgpiinv.htm

Apendice

 

EMPRESAS

 

http://www.redcientifica.com/gaia/


http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html


http://opeal.sourceforge.net/tindex.html


http://mx.google.yahoo.com/bin/query_mx?p=Empresas+en+Computaci%f3n+Evolutiva&hc=0&hs=3

Apendice