Algoritmos genéticos y computación evolutiva

7/18/2019 Algoritmos genéticos y computación evolutiva

http://slidepdf.com/reader/full/algoritmos-geneticos-y-computacion-evolutiva 1/80

Algoritmos genéticos y computación

evolutiva

Adam Marczyk 2004

Resumen:

Los creacionistas afirman a menudo que el proceso evolutivo no puede crearinformación nueva, o que la evolución no posee beneficios prácticos. Esteartículo refuta esas afirmaciones describiendo el crecimiento explosivo y lasextensas aplicaciones de los algoritmos genéticos, una técnica de computación basada en los principios de la evolución biológica.

Introducción

De vez en cuando, los creacionistas acusan a la evolución de que carece deutilidad como teoría científica porque no produce beneficios prácticos y no tienerelevancia en la vida diaria. Sin embargo, tan sólo la evidencia de la biologíademuestra que esta afirmación es falsa. Hay numerosos fenómenos naturales paralos que la evolución nos ofrece un sólido fundamento teórico. Por nombrar uno,el desarrollo observado de la resistencia -a los insecticidas en las plagas de

cultivos, a los antibióticos en las bacterias, a la quimioterapia en las célulascancerosas, y a los fármacos antiretrovirales en virus como el VIH- es unaconsecuencia abierta de las leyes de la mutación y la selección, y comprenderestos principios nos ha ayudado a desarrollar estrategias para enfrentarnos a estosnocivos organismos. El postulado evolutivo de la descendencia común haayudado al desarrollo de nuevos medicamentos y técnicas, al proporcionar a losinvestigadores una buena idea de con qué organismos deben experimentar paraobtener resultados que probablemente serán relevantes para los seres humanos.Finalmente, el hombre ha utilizado con grandes resultados el principio de críaselectiva para crear organismos personalizados, distintos a cualquiera que se

pueda encontrar en la naturaleza, para beneficio propio. El ejemplo canónico, porsupuesto, es la diversidad de variedades de perros domésticos (razas tan diversascomo los bulldogs, chihuahuas y dachshunds han sido producidas a partir delobos en sólo unos pocos miles de años), pero ejemplos menos conocidosincluyen al maíz cultivado (muy diferente de sus parientes salvajes, que carecende las familiares `òrejas'' del maíz cultivado), a los peces de colores (como los perros, hemos criado variedades cuyo aspecto es drásticamente distinto al del tipo



salvaje), y a las vacas lecheras (con ubres inmensas, mucho mayores que lasnecesarias para alimentar a una cría).

Los críticos pueden argumentar que los creacionistas pueden explicar estas cosassin recurrir a la evolución. Por ejemplo, a menudo los creacionistas explican el

desarrollo de la resistencia a los agentes antibióticos en las bacterias, o loscambios forjados en los animales domésticos por selección artificial, asumiendoque Dios decidió crear a los organismos en grupos fijos, llamados ``tipos'' o baramins. Aunque la microevolución natural o la selección artificial dirigida porhumanos pueden producir diferentes variedades dentro de los ``tipo-perro'',``tipo-vaca'' o ̀ `tipo-bacteria'' (!) creados originalmente, ninguna cantidad detiempo o cambio genético puede transformar un ``tipo'' en otro. Sin embargo,nunca se explica cómo determinan los creacionistas lo que es un ``tipo'', o quémecanismo impide a los seres vivos evolucionar más allá de sus límites.

Pero en las últimas décadas, el continuo avance de la tecnología moderna ha producido algo nuevo. Ahora la evolución está produciendo beneficios prácticosen un campo muy distinto y, esta vez, los creacionistas no pueden afirmar que suexplicación se adapte a los hechos igual de bien. Este campo es la informática, ylos beneficios provienen de una estrategia de programación llamada algoritmosgenéticos. Este ensayo explicará qué son los algoritmos genéticos y mostrará dequé manera son relevantes en el debate evolución/creacionismo.

¿Qué es un algoritmo genético?

Expuesto concisamente, un algoritmo genético (o AG para abreviar) es unatécnica de programación que imita a la evolución biológica como estrategia pararesolver problemas. Dado un problema específico a resolver, la entrada del AG esun conjunto de soluciones potenciales a ese problema, codificadas de algunamanera, y una métrica llamada función de aptitud que permite evaluarcuantitativamente a cada candidata. Estas candidatas pueden ser soluciones queya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelengenerar aleatoriamente.

Luego el AG evalúa cada candidata de acuerdo con la función de aptitud. En unacervo de candidatas generadas aleatoriamente, por supuesto, la mayoría nofuncionarán en absoluto, y serán eliminadas. Sin embargo, por puro azar, unas pocas pueden ser prometedoras -pueden mostrar actividad, aunque sólo seaactividad débil e imperfecta, hacia la solución del problema.



Estas candidatas prometedoras se conservan y se les permite reproducirse. Serealizan múltiples copias de ellas, pero las copias no son perfectas; se introducencambios aleatorios durante el proceso de copia. Luego, esta descendencia digital prosigue con la siguiente generación, formando un nuevo acervo de solucionescandidatas, y son sometidas a una ronda de evaluación de aptitud. Las candidatas

que han empeorado o no han mejorado con los cambios en su código soneliminadas de nuevo; pero, de nuevo, por puro azar, las variaciones aleatoriasintroducidas en la población pueden haber mejorado a algunos individuos,convirtiéndolos en mejores soluciones del problema, más completas o máseficientes. De nuevo, se selecionan y copian estos individuos vencedores hacia lasiguiente generación con cambios aleatorios, y el proceso se repite. Lasexpectativas son que la aptitud media de la población se incrementará en cadaronda y, por tanto, repitiendo este proceso cientos o miles de rondas, puedendescubrirse soluciones muy buenas del problema.

Aunque a algunos les puede parecer asombroso y antiintuitivo, los algoritmosgenéticos han demostrado ser una estrategia enormemente poderosa y exitosa para resolver problemas, demostrando de manera espectacular el poder de los principios evolutivos. Se han utilizado algoritmos genéticos en una ampliavariedad de campos para desarrollar soluciones a problemas tan difíciles o másdifíciles que los abordados por los diseñadores humanos. Además, las solucionesque consiguen son a menudo más eficientes, más elegantes o más complejas quenada que un ingeniero humano produciría. ¡En algunos casos, los algoritmosgenéticos han producido soluciones que dejan perplejos a los programadores queescribieron los algoritmos en primera instancia!

Métodos de representación

Antes de que un algoritmo genético pueda ponerse a trabajar en un problema, senecesita un método para codificar las soluciones potenciales del problema deforma que una computadora pueda procesarlas. Un enfoque común es codificarlas soluciones como cadenas binarias: secuencias de 1s y 0s, donde el dígito decada posición representa el valor de algún aspecto de la solución. Otro métodosimilar consiste en codificar las soluciones como cadenas de enteros o números

decimales, donde cada posición, de nuevo, representa algún aspecto particular dela solución. Este método permite una mayor precisión y complejidad que elmétodo comparativamente restringido de utilizar sólo números binarios, y amenudo ̀ èstá intuitivamente más cerca del espacio de problemas'' (Fleming yPurshouse 2002[3], p 1.228).

http://the-geek.org/docs/algen/algen.html#key-3






Esta técnica se utilizó, por ejemplo, en el trabajo de Steffen Schulze-Kremer, queescribió un algoritmo genético para predecir la estructura tridimensional de una proteína, basándose en la secuencia de aminoácidos que la componen (Mitchell1996[47], p. 62). El AG de Schulze-Kremer utilizaba números reales pararepresentar los famosos ``ángulos de torsión'' entre los enlaces peptídicos que

conectan a los aminoácidos. (Una proteína está formada por una secuencia de bloques básicos llamados aminoácidos, que se conectan como los eslabones deuna cadena. Una vez que todos los aminoácidos están enlazados, la proteína sedobla formando una compleja estructura tridimensional, basada en cuálesaminoácidos se atraen entre ellos y cuáles se repelen. La forma de una proteínadetermina su función). Los algoritmos genéticos para entrenar a las redesneuronales también utilizan a menudo este método de codificación.

Un tercer método consiste en representar a los individuos de un AG comocadenas de letras, donde cada letra, de nuevo, representa un aspecto específico dela solución. Un ejemplo de esta técnica es el método basado en ``codificacióngramática'' de Hiroaki Kitano, en el que a un AG se le encargó la tarea deevolucionar un sencillo conjunto de reglas llamadas gramática libre de contexto,que a su vez se utilizaban para generar redes neuronales para una variedad de problemas (Mitchell 1996[47], p. 74).

La virtud de estos tres métodos es que facilitan la definición de operadores quecausen los cambios aleatorios en las candidatas seleccionadas: cambiar un 0 porun 1 o viceversa, sumar o restar al valor de un número una cantidad elegida alazar, o cambiar una letra por otra. (Ver la sección sobre los métodos de cambio para más detalles acerca de los operadores genéticos). Otra estrategia,desarrollada principalmente por John Koza, de la Universidad de Stanford, ydenominada programación genética, representa a los programas como estructurasde datos ramificadas llamadas árboles (Koza et al. 2003[42], p. 35). En estemétodo, los cambios aleatorios pueden generarse cambiado el operador oalterando el valor de un cierto nodo del árbol, o sustituyendo un subárbol porotro.















Figure: Tres sencillos árboles de programa del tipo utilizado normalmente en la programación genética. Debajo se proporciona la expresión matemática que representa cada

uno.

Es importante señalar que los algoritmos evolutivos no necesitan representar las

soluciones candidatas como cadenas de datos de una longitud fija. Algunos lasrepresentan de esta manera, pero otros no; por ejemplo, la ``codificacióngramatical'' de Kitano, explicada arriba, puede escalarse eficientemente paracrear redes neuronales grandes y complejas, y los árboles de programacióngenética de Koza pueden crecer arbitrariamente tanto como sea necesario pararesolver cualquier problema que se les pida.

Métodos de selección

Un algoritmo genético puede utilizar muchas técnicas diferentes para seleccionara los individuos que deben copiarse hacia la siguiente generación, pero abajo selistan algunos de los más comunes. Algunos de estos métodos son mutuamenteexclusivos, pero otros pueden utilizarse en combinación, algo que se hace amenudo.

Selección elitista: se garantiza la selección de los miembros más aptos decada generación. (La mayoría de los AGs no utilizan elitismo puro, sinoque usan una forma modificada por la que el individuo mejor, o algunos delos mejores, son copiados hacia la siguiente generación en caso de que nosurja nada mejor).

Selección proporcional a la aptitud: los individuos más aptos tienen más probabilidad de ser seleccionados, pero no la certeza.

Selección por rueda de ruleta: una forma de selección proporcional a laaptitud en la que la probabilidad de que un individuo sea seleccionado es proporcional a la diferencia entre su aptitud y la de sus competidores.(Conceptualmente, esto puede representarse como un juego de ruleta -cadaindividuo obtiene una sección de la ruleta, pero los más aptos obtienen



secciones mayores que las de los menos aptos. Luego la ruleta se hacegirar, y en cada vez se elige al individuo que ``posea'' la sección en la quese pare la ruleta).

Selección escalada: al incrementarse la aptitud media de la población, lafuerza de la presión selectiva también aumenta y la función de aptitud se

hace más discriminadora. Este método puede ser útil para seleccionar mástarde, cuando todos los individuos tengan una aptitud relativamente alta ysólo les distingan pequeñas diferencias en la aptitud.

Selección por torneo: se eligen subgrupos de individuos de la población, ylos miembros de cada subgrupo compiten entre ellos. Sólo se elige a unindividuo de cada subgrupo para la reproducción.

Selección por rango: a cada individuo de la población se le asigna unrango numérico basado en su aptitud, y la selección se basa en esteranking, en lugar de las diferencias absolutas en aptitud. La ventaja de estemétodo es que puede evitar que individuos muy aptos ganen dominancia al principio a expensas de los menos aptos, lo que reduciría la diversidadgenética de la población y podría obstaculizar la búsqueda de una soluciónaceptable.

Selección generacional: la descendencia de los individuos seleccionadosen cada generación se convierte en toda la siguiente generación. No seconservan individuos entre las generaciones.

Selección por estado estacionario: la descendencia de los individuosseleccionados en cada generación vuelven al acervo genético preexistente,reemplazando a algunos de los miembros menos aptos de la siguiente

generación. Se conservan algunos individuos entre generaciones. Selección jerárquica: los individuos atraviesan múltiples rondas deselección en cada generación. Las evaluaciones de los primeros nivelesson más rápidas y menos discriminatorias, mientras que los quesobreviven hasta niveles más altos son evaluados más rigurosamente. Laventaja de este método es que reduce el tiempo total de cálculo al utilizaruna evaluación más rápida y menos selectiva para eliminar a la mayoría delos individuos que se muestran poco o nada prometedores, y sometiendo auna evaluación de aptitud más rigurosa y computacionalmente más costosasólo a los que sobreviven a esta prueba inicial.

Métodos de cambio

Una vez que la selección ha elegido a los individuos aptos, éstos deben seralterados aleatoriamente con la esperanza de mejorar su aptitud para la siguientegeneración. Existen dos estrategias básicas para llevar esto a cabo. La primera y



más sencilla se llama mutación. Al igual que una mutación en los seres vivoscambia un gen por otro, una mutación en un algoritmo genético también causa pequeñas alteraciones en puntos concretos del código de un idividuo.

El segundo método se llama cruzamiento, e implica elegir a dos individuos para

que intercambien segmentos de su código, produciendo una ̀ `descendencia''artificial cuyos individuos son combinaciones de sus padres. Este proceso pretende simular el proceso análogo de la recombinación que se da en loscromosomas durante la reproducción sexual. Las formas comunes decruzamiento incluyen al cruzamiento de un punto, en el que se establece un puntode intercambio en un lugar aleatorio del genoma de los dos individuos, y uno delos individuos contribuye todo su código anterior a ese punto y el otro individuocontribuye todo su código a partir de ese punto para producir una descendencia, yal cruzamiento uniforme, en el que el valor de una posición dada en el genoma dela descendencia corresponde al valor en esa posición del genoma de uno de los padres o al valor en esa posición del genoma del otro padre, elegido con un 50%de probabilidad.

Figure: Cruzamiento y mutación. El diagrama de arriba ilustra el efecto de estos dosoperadores genéticos en los individuos de una población de cadenas de 8 bits. El diagramasuperior muestra a dos individuos llevando a cabo un cruzamiento de un punto; el punto de

intercambio se establece entre las posiciones quinta y sexta del genoma, produciendo unnuevo individuo que es híbrido de sus progenitores. El segundo diagrama muestra a un

individuo sufriendo una mutación en la posición 4, cambiando el 0 de esa posición de sugenoma por un 1.

Otras técnicas de resolución de problemas

Con el auge de la informática de inteligencia artificial y el desarrollo de losmétodos heurísticos, han emergido otras técnicas de resolución computerizada de problemas que en algunos aspectos son similares a los algoritmos genéticos. Estasección explica algunas de estas técnicas, en qué se parecen a los AGs y en quése diferencian.



Redes neuronales

Una red neuronal es un método de resolución de problemas basado en un modeloinformático de la manera en que están conectadas las neuronas del cerebro. Una

red neuronal consiste en capas de unidades procesadoras, llamadas nodos, unidas por conexiones direccionales: una capa de entrada, una capa de salida y cero omás capas ocultas enmedio. Se le presenta un patrón inicial de entrada a la capade entrada, y luego los nodos que se estimulan transmiten una señal a los nodosde la siguiente capa a la que están conectados. Si la suma de todas las entradasque entran en una de estas neuronas virtuales es mayor que el famoso umbral deactivación de la neurona, esa neurona se activa, y transmite su propia señal a lasneuronas de la siguiente capa. El patrón de activación, por tanto, se propaga haciadelante hasta que alcanza a la capa de salida, donde es devuelto como solución ala entrada presentada. Al igual que en el sistema nervioso de los organismos biológicos, las redes neuronales aprenden y afinan su rendimiento a lo largo deltiempo, mediante la repetición de rondas en las que se ajustan sus umbrales, hastaque la salida real coincide con la salida deseada para cualquier entrada dada. Este proceso puede ser supervisado por un experimentador humano, o puede correrautomáticamente utilizando un algoritmo de aprendizaje (Mitchell 1996[47], p.52). Se han utilizado algoritmos genéticos para construir y entrenar a redesneuronales.

Figure: Una sencilla red neuronal anticipativa (feedforward), con una capa consistente encuatro neuronas, una capa oculta consistente en tres neuronas y una capa de salida

consistente en cuatro neuronas. El número de cada neurona representa su umbral deactivación: sólo se excitará si recibe al menos esa cantidad de entradas. El diagramamuestra cómo la red neuronal recibe una cadena de entrada y cómo la activación se

extiende por la red hasta producir una salida.







Ascenso a colina (Hill Climbing)

Similares a los algoritmos genéticos, aunque más sistemáticos y menosaleatorios. Un algoritmo de ascenso a colina comienza con una solución al problema a mano, normalmente elegida al azar. Luego, la cadena se muta, y si la

mutación proporciona una solución con mayor aptitud que la solución anterior, seconserva la nueva solución; en caso contrario, se conserva la solución actual.Luego el algoritmo se repite hasta que no se pueda encontrar una mutación que provoque un incremento en la aptitud de la solución actual, y esta solución sedevuelve como resultado (Koza et al. 2003[42], p. 59). (Para entender de dóndeviene el nombre de esta técnica, imagine que el espacio de todas las soluciones posibles de un cierto problema se representa como un paisaje tridimensional. Unconjunto de coordenadas en ese paisaje representa una solución particular. Lassoluciones mejores están a mayor altitud, formando colinas y picos; las que son peores están a menor altitud, formando valles. Un ``trepacolinas'' es, por tanto, unalgoritmo que comienza en un punto dado del paisaje y se mueveinexorablemente colina arriba). El algoritmo de ascenso a colina es lo que seconoce como algoritmo voraz, lo que significa que siempre hace la mejorelección disponible en cada paso, con la esperanza de que de esta manera se puede obtener el mejor resultado global. En contraste, los métodos como losalgoritmos genéticos y el recocido simulado, discutido abajo, no son voraces; aveces, estos métodos hacen elecciones menos óptimas al principio con laesperanza de que conducirán hacia una solución mejor más adelante.

Recocido simulado (simulated annealing)

Otra técnica de optimización similar a los algoritmos evolutivos se conoce comorecocido simulado. La idea toma prestado su nombre del proceso industrial en elque un material se calienta por encima de su punto de fusión y luego se enfríagradualmente para eliminar defectos en su estructura cristalina, produciendo unentramado de átomos más estable y regular (Haupt y Haupt 1998[34], p. 16). Enel recocido simulado, como en los algoritmos genéticos, existe una función deaptitud que define un paisaje adaptativo; sin embargo, en lugar de una poblaciónde candidatas como en los AGs, sólo existe una solución candidata. El recocidosimulado también añade el concepto de ``temperatura'', una cantidad numéricaglobal que disminuye gradualmente en el tiempo. En cada paso del algoritmo, lasolución muta (lo que es equivalente a moverse hacia un punto adyacente en el paisaje adaptativo). Luego, la aptitud de la nueva solución se compara con laaptitud de la solución anterior; si es mayor, se conserva la nueva solución. Encaso contrario, el algoritmo toma la decisión de conservarla o descartarla en basea la temperatura. Si la temperatura es alta, como lo es al principio, puedenconservarse incluso cambios que causan decrementos significativos en la aptitud,











y utilizarse como base para la siguiente ronda del algoritmo, pero al irdisminuyendo la temperatura, el algoritmo se va haciendo más y más propenso aaceptar sólo los cambios que aumentan la aptitud. Finalmente, la temperaturaalzanca el cero y el sistema se ``congela''; cualquiera que sea la configuraciónque exista en ese punto se convierte en la solución. El recocido simulado tiene a

menudo aplicaciones en la ingeniería del diseño, como determinar la disposiciónfísica de los componentes en un chip informático (Kirkpatrick, Gelatt y Vecchi1983[40]).

Una breve historia de los AGs

Los primeros ejemplos de lo que hoy podríamos llamar algoritmos genéticosaparecieron a finales de los 50 y principios de los 60, programados encomputadoras por biólogos evolutivos que buscaban explícitamente realizar

modelos de aspectos de la evolución natural. A ninguno de ellos se le ocurrió queesta estrategia podría aplicarse de manera más general a los problemasartificiales, pero ese reconocimiento no tardaría en llegar: ̀ `La computaciónevolutiva estaba definitivamente en el aire en los días formativos de lacomputadora electrónica'' (Mitchell 1996[47], p.2). En 1962, investigadorescomo G.E.P. Box, G.J. Friedman, W.W. Bledsoe y H.J. Bremermann habíandesarrollado independientemente algoritmos inspirados en la evolución paraoptimización de funciones y aprendizaje automático, pero sus trabajos generaron poca reacción. En 1965 surgió un desarrollo más exitoso, cuando IngoRechenberg, entonces de la Universidad Técnica de Berlín, introdujo una técnica

que llamó estrategia evolutiva, aunque se parecía más a los trepacolinas que a losalgoritmos genéticos. En esta técnica no había población ni cruzamiento; un padre mutaba para producir un descendiente, y se conservaba el mejor de los dos,convirtiéndose en el padre de la siguiente ronda de mutación (Haupt y Haupt1998[34], p.146). Versiones posteriores introdujeron la idea de población. Lasestrategias evolutivas todavía se emplean hoy en día por ingenieros y científicos,sobre todo en Alemania.

El siguiente desarrollo importante en el campo vino en 1966, cuando L.J. Fogel,A.J. Owens y M.J. Walsh introdujeron en América una técnica que llamaron

programación evolutiva. En este método, las soluciones candidatas para los problemas se representaban como máquinas de estado finito sencillas; al igualque en la estrategia evolutiva de Rechenberg, su algoritmo funcionaba mutandoaleatoriamente una de estas máquinas simuladas y conservando la mejor de lasdos (Mitchell 1996[47], p.2; Goldberg 1989[29], p.105). También al igual que lasestrategias evolutivas, hoy en día existe una formulación más amplia de latécnica de programación evolutiva que todavía es un área de investigación en























curso. Sin embargo, lo que todavía faltaba en estas dos metodologías era elreconocimiento de la importancia del cruzamiento.

En una fecha tan temprana como 1962, el trabajo de John Holland sobre sistemasadaptativos estableció las bases para desarrollos posteriores; y lo que es más

importante, Holland fue también el primero en proponer explícitamente elcruzamiento y otros operadores de recombinación. Sin embargo, el trabajofundamental en el campo de los algoritmos genéticos apareció en 1975, con la publicación del libro `Àdaptación en Sistemas Naturales y Artificiales''. Basadoen investigaciones y papers anteriores del propio Holland y de colegas de laUniversidad de Michigan, este libro fue el primero en presentar sistemática yrigurosamente el concepto de sistemas digitales adaptativos utilizando lamutación, la selección y el cruzamiento, simulando el proceso de la evolución biológica como estrategia para resolver problemas. El libro también intentócolocar los algoritmos genéticos sobre una base teórica firme introduciendo elconcepto de esquema (Mitchell 1996[47], p.3; Haupt y Haupt 1998[34], p.147).Ese mismo año, la importante tesis de Kenneth De Jong estableció el potencial delos AGs demostrando que podían desenvolverse bien en una gran variedad defunciones de prueba, incluyendo paisajes de búsqueda ruidosos, discontinuos ymultimodales (Goldberg 1989[29], p.107).

Estos trabajos fundacionales establecieron un interés más generalizado en lacomputación evolutiva. Entre principios y mediados de los 80, los algoritmosgenéticos se estaban aplicando en una amplia variedad de áreas, desde problemasmatemáticos abstractos como el ``problema de la mochila'' (bin-packing) y lacoloración de grafos hasta asuntos tangibles de ingeniería como el control deflujo en una línea de ensamble, reconocimiento y clasificación de patrones yoptimización estructural (Goldberg 1989[29], p.128).

Al principio, estas aplicaciones eran principalmente teóricas. Sin embargo, alseguir proliferando la investigación, los algoritmos genéticos migraron hacia elsector comercial, al cobrar importancia con el crecimiento exponencial de la potencia de computación y el desarrollo de Internet. Hoy en día, la computaciónevolutiva es un campo floreciente, y los algoritmos genéticos están ``resolviendo problemas de interés cotidiano'' (Haupt y Haupt 1998[34], p.147) en áreas deestudio tan diversas como la predicción en la bolsa y la planificación de la carterade valores, ingeniería aeroespacial, diseño de microchips, bioquímica y biologíamolecular, y diseño de horarios en aeropuertos y líneas de montaje. La potenciade la evolución ha tocado virtualmente cualquier campo que uno pueda nombrar,modelando invisiblemente el mundo que nos rodea de incontables maneras, ysiguen descubriéndose nuevos usos mientras la investigación sigue su curso. Y enel corazón de todo esto se halla nada más que la simple y poderosa idea de






















Charles Darwin: que el azar en la variación, junto con la ley de la selección, esuna técnica de resolución de problemas de inmenso poder y de aplicación casiilimitada.

¿Cuáles son las ventajas de los AGs? El primer y más importante punto es que los algoritmos genéticos son

intrínsecamente paralelos. La mayoría de los otros algoritmos son en seriey sólo pueden explorar el espacio de soluciones hacia una solución en unadirección al mismo tiempo, y si la solución que descubren resultasubóptima, no se puede hacer otra cosa que abandonar todo el trabajohecho y empezar de nuevo. Sin embargo, ya que los AGs tienendescendencia múltiple, pueden explorar el espacio de soluciones enmúltiples direcciones a la vez. Si un camino resulta ser un callejón sin

salida, pueden eliminarlo fácilmente y continuar el tabajo en avenidas más prometedoras, dándoles una mayor probabilidad en cada ejecución deencontrar la solución.

Sin embargo, la ventaja del paralelismo va más allá de esto. Considere losiguiente: todas las cadenas binarias (cadenas de ceros y unos) de 8 dígitosforman un espacio de búsqueda, que puede representarse como ********(donde * significa `ò 0 o 1''). La cadena 01101010 es un miembro de esteespacio. Sin embargo, también es un miembro del espacio 0*******, delespacio 01******, del espacio 0******0, del espacio 0*1*1*1*, del

espacio 10*01**0, etcétera. Evaluando la aptitud de esta cadena particular,un algoritmo genético estaría sondeando cada uno de los espacios a los que pertenece. Tras muchas evaluaciones, iría obteniendo un valor cada vezmás preciso de la aptitud media de cada uno de estos espacios, cada uno delos cuales contiene muchos miembros. Por tanto, un AG que evalúeexplícitamente un número pequeño de individuos está evaluandoimplícitamente un grupo de individuos mucho más grande -de la mismamanera que un encuestador que le hace preguntas a un cierto miembro deun grupo étnico, religioso o social espera aprender algo acerca de lasopiniones de todos los miembros de ese grupo, y por tanto puede predecircon fiabilidad la opinión nacional sondeando sólo un pequeño porcentajede la población. De la misma manera, el AG puede dirigirse hacia elespacio con los individuos más aptos y encontrar el mejor de ese grupo. Enel contexto de los algoritmos evolutivos, esto se conoce como teorema delesquema, y es la ventaja principal de los AGs sobre otros métodos deresolución de problemas (Holland 1992[36], p. 68; Mitchell 1996[47], p.28-29; Goldberg 1989[29], p. 20).














Debido al paralelismo que les permite evaluar implícitamente muchosesquemas a la vez, los algoritmos genéticos funcionan particularmente bien resolviendo problemas cuyo espacio de soluciones potenciales esrealmente grande -demasiado vasto para hacer una búsqueda exhaustiva enun tiempo razonable. La mayoría de los problemas que caen en esta

categoría se conocen como ``no lineales''. En un problema lineal, la aptitudde cada componente es independiente, por lo que cualquier mejora enalguna parte dará como resultado una mejora en el sistema completo. Noes necesario decir que hay pocos problemas como éste en la vida real. Lano linealidad es la norma, donde cambiar un componente puede tenerefectos en cadena en todo el sistema, y donde cambios múltiples que,individualmente, son perjudiciales, en combinación pueden conducir haciamejoras en la aptitud mucho mayores. La no linealidad produce unaexplosión combinatoria: el espacio de cadenas binarias de 1.000 dígitos puede examinarse exhaustivamente evaluando sólo 2.000 posibilidades siel problema es lineal, mientras que si no es lineal, una búsquedaexhaustiva requiere evaluar 21.000 posibilidades -un número que, escrito,ocuparía más de 300 dígitos.

Afortunadamente, el paralelismo implícito de los AGs les permite superarincluso este enorme número de posibilidades, y encontrar con éxitoresultados óptimos o muy buenos en un corto periodo de tiempo, trasmuestrear directamente sólo regiones pequeñas del vasto paisajeadaptativo (Forrest 1993[24], p. 877). Por ejemplo, un algoritmo genético

desarrollado en común por ingenieros de General Electric y el RensselaerPolytechnic Institute produjo el diseño de la turbina de un motor areacción de altas prestaciones que era tres veces mejor que laconfiguración diseñada por humanos, y un 50% mejor que unaconfiguración diseñada por un sistema experto que recorrió con éxito unespacio de soluciones que contenía más de 10.387 posibilidades. Losmétodos convencionales para diseñar estas turbinas son una partefundamental de proyectos de ingeniería que pueden durar hasta cinco añosy costar más de 2.000 millones de dólares; el algoritmo genético descubrióesta solución en dos días, en una estación de trabajo de escritorio típica en

ingeniería (Holland 1992[36], p. 72). Otra ventaja notable de los algoritmos genéticos es que se desenvuelven

bien en problemas con un paisaje adaptativo complejo -aquéllos en los quela función de aptitud es discontinua, ruidosa, cambia con el tiempo, o tienemuchos óptimos locales. La mayoría de los problemas prácticos tienen unespacio de soluciones enorme, imposible de explorar exhaustivamente; elreto se convierte entonces en cómo evitar los óptimos locales -soluciones











que son mejores que todas las que son similares a ella, pero que no sonmejores que otras soluciones distintas situadas en algún otro lugar delespacio de soluciones. Muchos algoritmos de búsqueda pueden quedaratrapados en los óptimos locales: si llegan a lo alto de una colina del paisaje adaptativo, descubrirán que no existen soluciones mejores en las

cercanías y concluirán que han alcanzado la mejor de todas, aunqueexistan picos más altos en algún otro lugar del mapa.

Los algoritmos evolutivos, por otro lado, han demostrado su efectividad alescapar de los óptimos locales y descubrir el óptimo global incluso en paisajes adaptativos muy escabrosos y complejos. (Debe decirse que, en larealidad, a menudo no hay manera de decir si una cierta solución a un problema es el óptimo global o sólo un óptimo local muy alto. Sinembargo, aunque un AG no devuelva siempre una solución perfecta ydemostrable a un problema, casi siempre puede devolver al menos unamuy buena solución). Todos los cuatro componentes principales de losAGs -paralelismo, selección, mutación y cruzamiento- trabajan juntos paraconseguir esto. Al principio, el AG genera una población inicial diversa,lanzando una ``red'' sobre el paisaje adaptativo. (Koza 2003[42], p. 506)compara esto con un ejército de paracaidistas cayendo sobre el paisaje delespacio de búsqueda de un problema, cada uno de ellos con órdenes de buscar el pico más alto). Pequeñas mutaciones permiten a cada individuoexplorar sus proximidades, mientras que la selección enfoca el progreso,guiando a la descendencia del algoritmo cuesta arriba hacia zonas más

prometedoras del espacio de soluciones (Holland 1992[36], p. 68).Sin embargo, el cruzamiento es el elemento clave que distingue a losalgoritmos genéticos de los otros métodos como los trepacolinas y elrecocido simulado. Sin el cruzamiento, cada solución individual va por sucuenta, explorando el espacio de búsqueda en sus inmediaciones sinreferencia de lo que el resto de individuos puedan haber descubierto. Sinembargo, con el cruzamiento en juego, hay una transferencia deinformación entre los candidatos prósperos -los individuos pueden beneficiarse de lo que otros han aprendido, y los esquemas pueden

mezclarse y combinarse, con el potencial de producir una descendenciaque tenga las virtudes de sus dos padres y ninguna de sus debilidades. Este punto está ilustrado en Koza et al. 1999[41], p. 486, donde los autoresanalizan el problema de sintetizar un filtro de paso bajo utilizando programación genética. En una generación se seleccionaron dos circuitos progenitores para llevar a cabo el cruzamiento; un padre tenía una buenatopología (componentes como inductores y condensadores colocados en el














sitio correcto) pero malos tamaños (valores demasiado bajos deinductancia y capacidad para los componentes). El otro padre tenía malatopología pero buenos tamaños. El resultado de aparearlos mediantecruzamiento fue una descendencia con la buena topología de un padre ylos buenos tamaños del otro, dando como resultado una mejora sustancial

de la aptitud sobre sus dos padres.

El problema de encontrar el óptimo global en un espacio con muchosóptimos locales también se conoce como el dilema de la exploraciónversus explotación, `ùn problema clásico de todos los sistemas que pueden adaptarse y aprender'' (Holland 1992[36], p. 69). Una vez que unalgoritmo (o un diseñador humano) ha encontrado una estrategia pararesolver problemas que parece funcionar satisfactoriamente, ¿deberíacentrarse en hacer el mejor uso de esa estrategia, o buscar otras?Abandonar una estrategia de probada solvencia para buscar otras nuevascasi garantiza que supondrá una pérdida y degradación del rendimiento, almenos a corto plazo. Pero si uno se queda con una estrategia particularexcluyendo a todas las demás, corre el riesgo de no descubrir estrategiasmejores que existen pero no se han encontrado. De nuevo, los algoritmosgenéticos han demostrado ser muy buenos en dar con este equilibrio ydescubrir buenas soluciones en un tiempo y esfuerzo computacionalrazonables.

Otro área en el que destacan los algoritmos genéticos es su habilidad paramanipular muchos parámetros simultáneamente (Forrest 1993[24], p. 874).

Muchos problemas de la vida real no pueden definirse en términos de unúnico valor que hay que minimizar o maximizar, sino que debenexpresarse en términos de múltiples objetivos, a menudo involucrandocontrapartidas: uno sólo puede mejorar a expensas de otro. Los AGs sonmuy buenos resolviendo estos problemas: en particular, su uso del paralelismo les permite producir múltiples soluciones, igualmente buenas,al mismo problema, donde posiblemente una solución candidata optimizaun parámetro y otra candidata optimiza uno distinto (Haupt y Haupt1998[34], p. 17), y luego un supervisor humano puede seleccionar una deesas candidatas para su utilización. Si una solución particular a un

problema con múltiples objetivos optimiza un parámetro hasta el punto enel que ese parámetro no puede mejorarse más sin causar unacorrespondiente pérdida de calidad en algún otro parámetro, esa soluciónse llama óptimo paretiano o no dominada (Coello 2000[18], p. 112).

Finalmente, una de las cualidades de los algoritmos genéticos que, a primera vista, puede parecer un desastre, resulta ser una de sus ventajas: asaber, los AGs no saben nada de los problemas que deben resolver. En

















lugar de utilizar información específica conocida a priori para guiar cada paso y realizar cambios con un ojo puesto en el mejoramiento, como hacenlos diseñadores humanos, son ``relojeros ciegos'' (Dawkins 1996[20]);realizan cambios aleatorios en sus soluciones candidatas y luego utilizan lafunción de aptitud para determinar si esos cambios producen una mejora.

La virtud de esta técnica es que permite a los algoritmos genéticoscomenzar con una mente abierta, por así decirlo. Como sus decisionesestán basadas en la aleatoriedad, todos los caminos de búsqueda posiblesestán abiertos teóricamente a un AG; en contraste, cualquier estrategia deresolución de problemas que dependa de un conocimiento previo, debeinevitablemente comenzar descartando muchos caminos a priori, perdiendo así cualquier solución novedosa que pueda existir (Koza et al.1999[41], p. 547). Los AGs, al carecer de ideas preconcebidas basadas encreencias establecidas sobre ``cómo deben hacerse las cosas'' o sobre loque ``de ninguna manera podría funcionar'', los AGs no tienen este problema. De manera similar, cualquier técnica que dependa deconocimiento previo fracasará cuando no esté disponible tal conocimiento, pero, de nuevo, los AGs no se ven afectados negativamente por laignorancia (Goldberg 1989[29], p. 23). Mediante sus componentes de paralelismo, cruzamiento y mutación, pueden viajar extensamente por el paisaje adaptativo, explorando regiones que algoritmos producidos coninteligencia podrían no haber tenido en cuenta, y revelando potencialmentesoluciones de asombrosa e inesperada creatividad que podrían no

habérseles ocurrido nunca a los diseñadores humanos. Un ejemplo muygráfico de esto es el redescubrimiento, mediante la programación genética,del concepto de retroalimentación negativa -un principio crucial paramuchos componentes electrónicos importantes de hoy en día, pero unconcepto que, cuando fue descubierto en primera instancia, se le denegóuna patente de nueve años porque el concepto era demasiado contrario alas creencias establecidas (Koza et al. 2003[42], p. 413). Por supuesto, losalgoritmos evolutivos no están enterados ni preocupados de si unasolución va en contra de las creencias establecidas -sólo de si funciona.

¿Cuáles son las limitaciones de los AGs?Aunque los algoritmos genéticos han demostrado su eficiencia y potencia comoestrategia de resolución de problemas, no son la panacea. Los AGs tienen ciertaslimitaciones; sin embargo, se demostrará que todas ellas pueden superarse y queninguna de ellas afecta a la validez de la evolución biológica.


















La primera y más importante consideración al crear un algoritmo genéticoes definir una representación del problema. El lenguaje utilizado paraespecificar soluciones candidatas debe ser robusto; es decir, debe ser capazde tolerar cambios aleatorios que no produzcan constantemente erroresfatales o resultados sin sentido.

Hay dos maneras principales para conseguir esto. La primera, utilizada porla mayoría de los algoritmos genéticos, es definir a los individuos comolistas de números -binarios, enteros o reales- donde cada númerorepresenta algún aspecto de la solución candidata. Si los individuos soncadenas binarias, un 0 o 1 podría significar la ausencia o presencia de unacierta característica. Si son listas de números, estos números podríanrepresentar muchas cosas distintas: los pesos de las conexiones en una redneuronal, el orden de las ciudades visitadas en un recorrido dado, lasituación espacial de componentes electrónicos, los valores con los que sealimenta a un controlador, los ángulos de torsión de los enlaces péptidosde una proteína, etcétera. Así, la mutación implica cambiar estos números,cambiar bits o sumar o restar valores aleatorios. En este caso, el propiocódigo del programa no cambia; el código es lo que dirige la simulación yhace un seguimiento de los individuos, evaluando sus aptitudes y quizáasegurando que sólo se producen valores realistas y posibles para el problema dado.

En otro método, la programación genética, el propio código del

programa sí cambia. Como ya se dijo en la sección ``Métodos derepresentación'', la PG representa a los individuos como árboles de códigoejecutables que pueden mutar cambiando o intercambiando subárboles.Ambos méetodos producen representaciones robustas ante la mutación, y pueden representar muchos tipos diferentes de problemas y, como se diceen la sección `Àlgunos ejemplos específicos'', ambas han tenido un éxitoconsiderable.

El problema de representar a las soluciones candidatas de manera robustano surge en la naturaleza, porque el método de representación utilizado por

la evolución, a saber, el código genético, es inherentemente robusto: conmuy pocas excepciones, como una cadena de codones de parada, no existeuna secuencia de bases de ADN que no pueda traducirse en una proteína.Por lo tanto, virtualmente, cualquier cambio en los genes de un individuosiempre producirá un resultado inteligible, y por tanto las mutaciones en laevolución tienen mayor probabilidad de producir una mejora. Esto entra encontraste con los lenguajes creados por el hombre como el inglés, donde el



número de palabras con significado es pequeño comparado con el númerototal de formas en las que se pueden combinar las letras del alfabeto, y portanto, es probable que un cambio aleatorio en una frase en inglés produzcaun sinsentido.

El problema de cómo escribir la función de aptitud debe considerarse

cuidadosamente para que se pueda alcanzar una mayor aptitud yverdaderamente signifique una solución mejor para el problema dado. Sise elige mal una función de aptitud o se define de manera inexacta, puedeque el algoritmo genético sea incapaz de encontrar una solución al problema, o puede acabar resolviendo el problema equivocado. (Estaúltima situación se describe a veces como la tendencia del AG a`èngañar'', aunque en realidad lo que está pasando es que el AG estáhaciendo lo que se le pidió hacer, no lo que sus creadores pretendían quehiciera). Se puede encontrar un ejemplo de esto en Graham-Rowe2002[30], donde unos investigadores utilizaron un algoritmo evolutivo enconjunción con una serie de chips reprogramables, haciendo que lafunción de aptitud recompensara al circuito en evolución por dar comosalida una señal oscilatoria. Al final del experimento, se producíaefectivamente una señal oscilatoria -pero en lugar de actuar como unosculador, como pretendían los investigadores, ¡descubrieron que elcircuito se había convertido en un receptor de radio que estaba recibiendoy retransmitiendo una señal oscilatoria de un componente electrónicocercano!

Sin embargo, esto no es un problema en la naturaleza. En el laboratorio dela evolución biológica, sólo hay una función de aptitud que es igual paratodos los seres vivos -la carrera por sobrevivir y reproducirse, sin importarqué adaptaciones hagan esto posible. Los organismos que se reproducencon más abundancia que sus competidores están más adaptados; los quefracasan en reproducirse no están adaptados.

Además de elegir bien la función de aptitud, también deben elegirsecuidadosamente los otros parámetros de un AG -el tamaño de la población,el ritmo de mutación y cruzamiento, el tipo y fuerza de la selección. Si eltamaño de la población es demasiado pequeño, puede que el algoritmo

genético no explore suficientemente el espacio de soluciones paraencontrar buenas soluciones consistentemente. Si el ritmo de cambiogenético es demasiado alto o el sistema de selección se escogeinadecuadamente, puede alterarse el desarrollo de esquemas beneficiosos yla población puede entrar en catástrofe de errores, al cambiar demasiadorápido para que la selección llegue a producir convergencia.







Los seres vivos también se enfrentan a dificultades similares, y laevolución se ha encargado de ellas. Es cierto que si el tamaño de una población cae hacia un valor muy bajo, los ritmos de mutación son muyaltos o la presión selectiva es demasiado fuerte (una situación así podríaser resultado de un cambio ambiental drástico), entonces la especie puede

extinguirse. La solución ha sido ``la evolución de la evolutividad'' -lasadaptaciones que alteran la habilidad de una especie para adaptarse. Unejemplo. La mayoría de los seres vivos han evolucionado una elaboradamaquinaria celular que comprueba y corrigue errores durante el proceso dereplicación del ADN, manteniendo su ritmo de mutación a unos nivelesaceptablemente bajos; a la inversa, en tiempos de fuerte presión ambiental,algunas especies de bacterias entran en un estado de hipermutación en elque el ritmo de errores en la replicación del ADN aumenta bruscamente,aumentando la probabilidad de que se descubrirá una mutacióncompensatoria. Por supuesto, no pueden eludirse todas las catástrofes, perola enorme diversidad y las adaptaciones altamente complejas de los seresvivos actuales muestran que, en general, la evolución es una estrategiaexitosa. Igualmente, las aplicaciones diversas y los impresionantesresultados de los algoritmos genéticos demuestran que son un campo deestudio poderoso y que merece la pena.

Un problema con el que los algoritmos genéticos tienen dificultades sonlos problemas con las funciones de aptitud `èngañosas'' (Mitchell1996[47], p. 125), en las que la situación de los puntos mejorados ofreceninformación engañosa sobre dónde se encuentra probablemente el óptimo

global. Por ejemplo: imagine un problema en el que el espacio de búsqueda esté compuesto por todas las cadenas binarias de ochocaracteres, y en el que la aptitud de cada individuo sea directamente proporcional al número de unos en él -es decir, 00000001 sería menos aptoque 00000011, que sería menos apto que 00000111, etcétera -, con dosexcepciones: la cadena 11111111 resulta tener una aptitud muy baja, y lacadena 00000000 resulta tener una aptitud muy alta. En este problema, unAG (al igual que la mayoría de los algoritmos) no tendría más probabilidad de encontrar un óptimo global que una búsqueda aleatoria.

La solución a este problema es la misma para los algoritmos genéticos y laevolución biológica: la evolución no es un proceso que deba encontrarsiempre el óptimo global. Puede funcionar casi igual de bien alcanzando lacima de un óptimo local alto y, para la mayoría de las situaciones, eso serásuficiente, incluso aunque el óptimo global no pueda alcanzarse fácilmentedesde ese punto. La evolución es como un ``satisfactor'' -un algoritmo queentrega una solución ̀ `suficientemente buena'', aunque no necesariamente







la mejor solución posible, dada una cantidad razonable de tiempo yesfuerzo invertidos en la búsqueda. La ``FAQ de la evidencia de diseñoimprovisado en la naturaleza'' proporciona ejemplos de la naturaleza conestos resultados. (También hay que tener en cuenta que pocos o ningún problema real es tan engañoso como el ejemplo algo forzado dado arriba.

Normalmente, la situación de las mejoras locales proporciona algunainformación sobre la situación del óptimo global).

Un problema muy conocido que puede surgir con un AG se conoce comoconvergencia prematura. Si un individuo que es más apto que la mayoríade sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto, provocando que el algoritmo converja haciael óptimo local que representa ese individuo, en lugar de rastrear el paisajeadaptativo lo bastante a fondo para encontrar el óptimo global (Forrest1993[24], p. 876; Mitchell 1996[47], p. 167). Esto es un problemaespecialmente común en las poblaciones pequeñas, donde incluso unavariación aleatoria en el ritmo de reproducción puede provocar que ungenotipo se haga dominante sobre los otros.

Los métodos más comunes implementados por los investigadores en AGs para solucionar este problema implican controlar la fuerza selectiva, parano proporcionar tanta ventaja a los individuos excesivamente aptos. Laselección escalada, por rango y por torneo, discutidas anteriormente, sontres de los métodos principales para conseguir esto; algunos métodos de

selección escalada son el escalado sigma, en el que la reproducción se basaen una comparación estadística de la aptitud media de la población, y laselección de Boltzmann, en la que la fuerza selectiva aumenta durante laejecución de manera similar a la variable ``temperatura'' en el recocidosimulado (Mitchell 1996[47], p. 168).

La convergencia prematura ocurre en la naturaleza (los biólogos la llamanderiva genética). Esto no debe sorprender; como ya se dijo arriba, laevolución, como estrategia de resolución de problemas, no está obligada aencontrar la mejor solución, sólo una que sea lo bastante buena. Sin

embargo, en la naturaleza, la convergencia prematura es menos común, yaque la mayoría de las mutaciones beneficiosas en los seres vivos sólo producen mejoras en la aptitud pequeñas e incrementales; son raras lasmutaciones que producen una ganancia de aptitud tan grande que otorguea sus poseedores una drástica ventaja reproductiva.

Finalmente, varios investigadores (Holland 1992[36], p. 72; Forrest1993[24], p. 875; Haupt y Haupt 1998[34], p. 18) aconsejan no utilizar

http://www.talkorigins.org/faqs/jury-rigged.html































algoritmos genéticos en problemas resolubles de manera analítica. No esque los algoritmos genéticos no puedan encontrar soluciones buenas paraestos problemas; simplemente es que los métodos analíticos tradicionalesconsumen mucho menos tiempo y potencia computacional que los AGs y,a diferencia de los AGs, a menudo está demostrado matemáticamente que

ofrecen la única solución exacta. Por supuesto, como no existe unasolución matemática perfecta para ningún problema de adaptación biológica, este problema no aparece en la naturaleza.

Algunos ejemplos específicos de AG

Mientras el poder de la evolución gana reconocimiento cada vez másgeneralizado, los algoritmos genéticos se utilizan para abordar una ampliavariedad de problemas en un conjunto de campos sumamente diverso,

demostrando claramente su capacidad y su potencial. Esta sección analizaráalgunos de los usos más notables en los que han tomado parte.

Acústica

Sato et al. 2002[58] utilizaron algoritmos genéticos para diseñar una sala deconciertos con propiedades acústicas óptimas, maximizando la calidad del sonido para la audiencia, para el director y para los músicos del escenario. Esta tareaimplica la optimización simultánea de múltiples variables. Comenzando con unasala con forma de caja de zapatos, el AG de los autores produjo dos soluciones

no dominadas, ambas descritas como ``con forma de hoja'' (p. 526). Los autoresafirman que estas soluciones tienen proporciones similares al GrosserMusikvereinsaal de Viena, el cual está considerado generalmente como una delas mejores -si no la mejor- salas de conciertos del mundo, en términos de propiedades acústicas.

Porto, Fogel y Fogel 1995[51] utilizaron programación evolutiva para adiestrar aredes neuronales para distinguir entre reflexiones sonoras desde distintos tipos deobjetos: esferas metálicas hechas por el hombre, montañas submarinas, peces y plantas, y ruido aleatorio de fondo. Tras 500 generaciones, la mejor red neuronalque evolucionó tenía una probabilidad de clasificación correcta que iba desde el94% al 98%, y una probabilidad de clasificación errónea entre un 7,4% y un1,5%, que son ``probabilidades razonables de detección y falsa alarma'' (p. 21).Esta red evolucionada igualó las prestaciones de otra red desarrollada medianterecocido simulado, y superó consistentemente a redes entrenadas mediante propagación hacia atrás, las cuales ``se atascaban repetidamente en conjuntos de pesos subóptimos que no producían resultados satisfactorios'' (p. 21). En











contraste, ambos métodos estocásticos demostraron su capacidad para superarestos óptimos locales y producir redes más pequeñas, efectivas y robustas; perolos autores sugieren que el algoritmo evolutivo, a diferencia del recocidosimulado, opera sobre una población, y por tanto se beneficia de la informaciónglobal sobre el espacio de búsqueda, conduciendo potencialmente hacia un

rendimiento mayor a la larga.

Tang et al. 1996[62] analizan los usos de los algoritmos genéticos en el campo dela acústica y el procesamiento de señales. Un área de interés particular incluye eluso de AGs para diseñar sistemas de Control Activo de Ruido (CAR), queeliminan el sonido no deseado produciendo ondas sonoras que interfierendestructivamente con el ruido. Esto es un problema de múltiples objetivos querequiere el control y la colocación precisa de múltiples altavoces; los AGs se hanutilizado en estos sistemas tanto para diseñar los controladores como paraencontrar la colocación óptima de los altavoces, dando como resultado una`àtenuación efectiva del ruido'' (p. 33) en pruebas experimentales.

Ingeniería aeroespacial

Obayashi et al. 2000[49] utilizaron un algoritmo genético de múltiples objetivos para diseñar la forma del ala de un avión supersónico. Hay tres consideraciones principales que determinan la configuración del ala -minimizar la resistenciaaerodinámica a velocidades de vuelo supersónicas, minimizar la resistencia avelocidades subsónicas y minimizar la carga aerodinámica (la fuerza que tiende a

doblar el ala). Estos objetivos son mutuamente exclusivos, y optimizarlos todossimultáneamente requiere realizar contrapartidas.

El cromosoma de este problema es una cadena de 66 números reales, cada uno delos cuales corresponde a un aspecto específico del ala: su forma, su grosor, sutorsión, etcétera. Se simuló una evolución con selección elitista durante 70generaciones, con un tamaño de población de 64 individuos. Al final de este proceso había varios individuos paretianos, cada uno representando una soluciónno dominada del problema. El artículo comenta que estos individuos ganadorestenían características ̀ `físicamente razonables'', señalando la validez de la técnica

de optimización (p. 186). Para evaluar mejor la calidad de las soluciones, las seismejores fueron comparadas con un diseño de ala supersónica producido por elEquipo de Diseño SST del Laboratorio Aeroespacial Nacional de Japón. Las seisfueron competitivas, con valores de resistencia y carga aproximadamente igualeso menores a los del ala diseñada por humanos; en particular, una de lassoluciones evolucionadas superó al diseño del LAN en los tres objetivos. Losautores señalan que las soluciones del AG son similares a un diseño llamado `àla











flecha'', sugerido por primera vez a finales de los años 50, pero que finalmentefue abandonado en favor del diseño más convencional con forma de delta.

En un artículo posterior (Sasaki et al. 2001[57]), los autores repitieron elexperimento añadiendo un cuarto objetivo, a saber, minimizar el momento de

torsión (un conocido problema en los diseños de alas flecha en el vuelosupersónico). También se añadieron puntos de control adicionales para el grosoral conjunto de variables de diseño. Tras 75 generaciones de evolución, secompararon dos de las mejores soluciones paretianas con el diseño de ala que elLaboratorio Aeroespacial Nacional japonés realizó para el avión supersónicoexperimental NEXST-1. Se descubrió que ambos diseños (además de un diseñoóptimo de la simulación anterior, explicada arriba) eran físicamente razonables ysuperiores al diseño del LAN en los cuatro objetivos.

Williams, Crossley y Lang 2001[64] aplicaron algoritmos genéticos a la tarea de

situar órbitas de satélites para minimizar los apagones de cobertura. Mientras latecnología de telecomunicaciones sigue progresando, los humanos somos cadavez más dependientes de las funciones vitales que realizan los satélites en órbitaalrededor de la Tierra, y uno de los problemas con los que se enfrentan losingenieros es el diseño de las trayectorias orbitales. Los satélites que seencuentran en una órbita terrestre alta, a unos 35.000 kilómetros de altitud, pueden ver amplias secciones del planeta al mismo tiempo y estar en contactocon las estaciones terrestres, pero son mucho más caros de lanzar y másvulnerables a las radiaciones cósmicas. Es más económico colocar satélites enórbitas bajas, en algunos casos a sólo unos pocos cientos de kilómetros; pero, acausa de la curvatura de la Tierra, es inevitable que estos satélites pierdan duranteun tiempo la línea de visión con los receptores terrestres, y por lo tanto sevuelven inútiles. Incluso las constelaciones de varios satélites tienen apagonesineludibles y pérdidas de cobertura por esta razón. El reto consiste en colocar lasórbitas de los satélites para minimizar este tiempo muerto. Esto es un problemamulti-objetivo que implica la minimización de el tiempo medio de apagón paratodas las localizaciones y el tiempo máximo de apagón para cada una de laslocalizaciones; en la práctica, estos objetivos resultan ser mutuamente exclusivos.

Cuando se utilizó el AG en este problema, los resultados que evolucionaron paraconstelaciones de tres, cuatro y cinco satélites eran extraños, configuracionesorbitales muy asimétricas, con los satélites colocados alternando huecos grandesy pequeños, en lugar de huecos de igual tamaño como habrían hecho las técnicasconvencionales. Sin embargo, esta solución redujo significativamente los tiemposmedio y máximo de apagón, en algunos casos hasta en 90 minutos. En un artículo periodístico, el Dr. William Crossley señaló que `ìngenieros con años de











experiencia aeroespacial quedaorn sorprendidos con el rendimiento ofrecido porel diseño no convencional''.

Keane y Brown 1996[43] utilizadon un AG para producir un nuevo diseño paraun brazo o jirafa para transportar carga que pudiese montarse en órbita y

utilizarse con satélites, estaciones espaciales y otros proyectos de construcciónaeroespacial. El resultado, una estructura retorcida con aspecto orgánico que seha comparado con un fémur humano, no utiliza más material que el diseño de brazo estándar, pero es ligera, fuerte y muy superior a la hora de amortiguar lasvibraciones perjudiciales, como confirmaron las pruebas reales del productofinal. Y sin embargo ̀ `Ninguna inteligencia produjo los diseños. Simplementeevolucionaron'' (Petit 1998[43]). Los autores del artículo comentan además quesu AG sólo se ejecutó durante 10 generaciones, debido a la naturalezacomputacionalmente costosa de la simulación, y la población no se habíaestancado todavía. Haber proseguido la ejecución durante más generacioneshabría producido indudablemente mayores mejoras de rendimiento.

Figure: Un brazo tridimensional optimizado genéticamente, con una respuesta mejorada ala frecuencia (adaptado de http://www.soton.ac.uk/~ajk/truss/welcome.html).

Finalmente, como informa Gibbs 1996[25], Lockheed Martin ha utilizado unalgoritmo genético para producir mediante evolución una serie de maniobras paramover una nave espacial de una orientación a otra, dentro del 2% del tiempo

mínimo teórico para tales maniobras. La solución evolucionada era un 10% másrápida que una solución producida manualmente por un experto para el mismo problema.

Astronomía y astrofísica














Charbonneau 1995[12] sugiere la utilidad de los AGs para problemas deastrofísica, aplicándolos a tres problemas de ejemplo: obtener la curva derotación de una galaxia basándose en las velocidades rotacionales observadas desus componentes, determinar el periodo de pulsación de una estrella variable basándose en series de datos temporales, y sacar los valores de los parámetros

críticos de un modelo magnetohidrodinámico del viento solar. Son tres difíciles problemas no lineales y multidimensionales.

El algoritmo genético de Charbonneau, PIKAIA, utiliza selección generacional y proporcional a la aptitud, junto con elitismo, para asegurar que el mejor individuose copia una vez hacia la siguiente generación sin ninguna modificación. PIKAIAtiene un ritmo de cruzamiento de 0,65 y un ritmo de mutación variable que se pone a 0,003 inicialmente y luego aumenta gradualmente, mientras la poblaciónse aproxima a la convergencia, para mantener la variabilidad en el acervogenético.

En el problema de la curva de rotación galáctica, el AG produjo dos curvas, yambas estaban bien ajustadas a los datos (un resultado común en este tipo de problema, en el que hay poco contraste entre cimas cercanas); observaciones posteriores pueden distinguir cuál es la preferible. En el problema de la serietemporal, el AG fue impresionantemente exitoso, generando un ajuste de losdatos de gran calidad, aunque otros problemas más difíciles no se ajustaron tan bien (aunque, como señala Charbonneau, estos problemas son igualmentedifíciles de resolver con técnicas convencionales). El artículo sugiere que un AGhíbrido que emplee tanto evolución artificial como técnicas analíticas estándar, podría funcionar mejor. Finalmente, en el problema de obtener los seis parámetros críticos del viento solar, el AG determinó con éxito el valor de trescon una precisión de menos del 0,1% y los otros tres con precisiones entre el 1 yel 10%. (Aunque siempre serían preferibles unos errores experimentales menores para estos tres parámetros, Charbonneau señala que no existe ningún otro métodoeficiente y robusto para resolver experimentalmente un problema no lineal 6-dimensional de este tipo; un método de gradiente conjugado funciona ``siempreque se pueda proporcionar un valor inicial muy acertado'' (p. 323). En contraste,los AGs no requieren un conocimiento del dominio tan bien afinado).

Basándose en los resultados obtenidos hasta ahora, Charbonneau sugiere que losAGs pueden y deben encontrar uso en otros problemas difíciles de astrofísica, en particular, problemas inversos como las imágenes por Doppler y las inversionesheliosísmicas. Para terminar, Charbonneau sostiene que los AGs son un``contendiente poderoso y prometedor'' (p. 324) en este campo, del que se puedeesperar que complemente (no sustituya) a las técnicas tradicionales deoptimización, y concluye que `èl punto decisivo, si es que tiene que haber







alguno, es que los algoritmos genéticos funcionan, y a menudo colosalmente bien'' (p. 325).

Química

Un pulso láser ultracorto de alta energía puede romper moléculas complejas enmoléculas más sencillas, un proceso con aplicaciones importantes en la químicaorgánica y la microelectrónica. Los productos específicos de una reacción así pueden controlarse modulando la fase del pulso láser. Sin embargo, paramoléculas grandes, obtener la forma del pulso deseado de manera analítica esdemasiado difícil: los cálculos son demasiado complejos y las característicasrelevantes (las superficies de energía potencial de las moléculas) no se conocencon suficiente precisión.

Assion et al. 1998[6] resolvieron este problema utilizando un algoritmo evolutivo para diseñar la forma del pulso. En lugar de introducir información compleja,específica del problema, sobre las características cuánticas de las moléculasiniciales, para diseñar el pulso conforme a las especificaciones, el AE dispara un pulso, mide las proporciones de las moléculas producto resultantes, mutaaleatoriamente las características del rayo con la esperanza de conseguir queestas proporciones se acerquen a la salida deseada, y el proceso se repite. (Enlugar de afinar directamente las características del rayo láser, el AG de losautores representa a los individuos como un conjunto de 128 números, en el quecada número es un valor de voltaje que controla el índice de refracción de uno de

los pixeles del modulador láser. De nuevo, no se necesita un conocimientoespecífico del problema sobre las propiedades del láser o de los productos de lareacción). Los autores afirman que su algoritmo, cuando se aplica a dossustancias de muestra, ̀ èncuentra automáticamente la mejor configuración... noimporta lo complicada que sea la respuesta molecular'' (p. 921), demostrando un``control coherente automatizado de los productos que son químicamentediferentes uno del otro y de la molécula padre'' (p. 921).

A principios y mediados de los 90, la amplia adopción de una novedosa técnicade diseño de fármacos, llamada química combinatoria, revolucionó la industria

farmacéutica. Con este método, en lugar de la síntesis precisa y meticulosa de unsólo compuesto de una vez, los bioquímicos mezclan deliberadamente una granvariedad de reactivos para producir una variedad aún mayor de productos -cientos, miles o millones de compuestos diferentes en cada remesa- que luego pueden aislarse rápidamente para su actividad bioquímica. Hay dos formas dediseñar las bibliotecas de reactivos en esta técnica: diseño basado en losreactivos, que elige grupos optimizados de reactivos sin considerar qué productos







saldrán como resultado, y diseño basado en los productos, que selecciona losreactivos que producirán con mayor probabilidad los productos con las propiedades deseadas. El diseño basado en los productos es más difícil ycomplejo, pero se ha demostrado que genera bibliotecas combinatorias mejores ymás diversas, y tiene más probabilidades de ofrecer un resultado útil.

En un artículo patrocinado por el departamento de investigación y desarrollo deGlaxoSmithKline, Gillet 2002[26] describe el uso de un algoritmo genéticomultiobjetivo para el diseño basado en los productos de bibliotecascombinatorias. Al elegir los componentes que van en una biblioteca particular,deben considerarse características como la diversidad y peso molecular, el costede los suministros, la toxicidad, la absorción, la distribución y el metabolismo. Siel objetivo es encontrar moléculas similares a una molécula existente con unafunción conocida (un método común en el diseño de nuevos fármacos), tambiénse puede tener en cuenta la similaridad estructural. Este artículo presenta unenfoque multiobjetivo, donde puede desarrollarse un conjunto de resultados paretianos que maximicen o minimicen cada uno de estos objetivos. El autorconcluye diciendo que el AG fue capaz de satisfacer simultáneamente loscriterios de diversidad molecular y eficiencia sintética máxima, y también fuecapaz de encontrar moléculas parecidas a un fármaco que eran ``muy similares alas moléculas objetivo dadas, tras explorar una fracción muy pequeña del espaciode búsqueda total'' (p. 378).

En un artículo relacionado, Glen y Payne 1995[28] describen el uso dealgoritmos genéticos para diseñar automáticamente moléculas nuevas desde ceroque se ajustan a un conjunto de especificaciones dado. Dada una poblacióninicial, bien generada aleatoriamente o utilizando la sencilla molécula del etanocomo semilla, el AG añade, elimina y altera aleatoriamente átomos y fragmentosmoleculares con el objetivo de generar moléculas que se ajusten a los requisitosdados. El AG puede optimizar simultáneamente un gran número de objetivos,incluyendo el peso molecular, el volumen molecular, el número de enlaces, elnúmero de centros quirales, el número de átomos, el número de enlaces rotables,la polarizabilidad, el momento dipolar, etcétera, para producer moléculascandidatas con las propiedades deseadas. Basándose en pruebas experimentales,incluyendo un difícil problema de optimización que implicaba la generación demoléculas con propiedades similares a la ribosa (un componente del azúcarimitado a menudo en los fármacos antivirales), los autores concluyen que el AGes un `èxcelente generador de ideas'' (p. 199) que ofrece ``propiedades deoptimización rápidas y poderosas'' y puede generar `ùn conjunto diverso deestructuras posibles'' (p. 182). Continúan afirmando: `Ès de interés especial la poderosa capacidad de optimización del algoritmo genético, incluso con tamañosde población relativamente pequeños'' (p. 200). Como prueba de que estos










resultados no son simplemente teóricos, Lemley 2001[45] informa de que laempresa Unilever ha utilizado algoritmos genéticos para diseñar nuevoscomponentes antimicrobianos para su uso en productos de limpieza, algo que ha patentado.

Ingeniería eléctrica

Una matriz de puertas programable en campo (Field Programmable Gate Array, oFPGA), es un tipo especial de placa de circuito con una matriz de celdas lógicas,cada una de las cuales puede actuar como cualquier tipo de puerta lógica,interconectado con conexiones flexibles que pueden conectar celdas. Estas dosfunciones se controlan por software, así que simplemente cargando un programaespecial en la placa, puede alterarse al vuelo para realizar las funciones decualquier dispositivo de hardware de la amplia variedad existente.

El Dr. Adrian Thompson ha explotado este dispositivo, en conjunción con los principios de la evolución, para producir un prototipo de circuito reconocedor devoz que puede distinguir y responder a órdenes habladas utilizando sólo 37 puertas lógicas -una tarea que se habría considerado imposible para cualquieringeniero humano. Generó cadenas aleatorias de bits de ceros y unos y las utilizócomo configuraciones de la FPGA, seleccionando los individuos más aptos decada generación, reproduciéndolos y mutándolos aleatoriamente, intercambiandosecciones de su código y pasándolo hacia la siguiente ronda de selección. Suobjetivo era evolucionar un dispositivo que pudiera en principio discriminar entre

tonos de frecuencias distintas (1 y 10 kilohercios), y luego distinguir entre las palabras habladas ``go'' (adelante) y ``stop'' (para).

Su objetivo se alcanzó en 3.000 generaciones, pero el éxito fue mayor de lo quehabía anticipado. El sistema que evolucionó utilizaba muchas menos celdas quecualquier cosa que pudiera haber diseñado un ingeniero humano, y ni siquieranecesita del componente más crítico de los sistemas diseñados por humanos -unreloj. ¿Cómo funcionaba? Thompson no tiene ni idea, aunque ha rastreado laseñal de entrada a través de un complejo sistema de bucles realimentados delcircuito evolucionado. De hecho, de las 37 puertas lógicas que utiliza el producto

final, cinco de ellas ni siquiera están conectadas al resto del circuito de ningunamanera -pero si se les retira la alimentación eléctrica, el circuito deja defuncionar. Parece que la evolución ha explotado algún sutil efectoelectromagnético de estas celdas para alcanzar su solución, pero elfuncionamiento exacto de la compleja e intrincada estructura evolucionada siguesiendo un misterio (Davidson 1997[19]).










Altshuler y Linden 1997[2] utilizaron un algoritmo genético para evolucionarantenas de alambre con propiedades especificadas a priori. Los autores señalanque el diseño de tales antenas es un proceso impreciso, comenzando con las propiedades deseadas y luego determinando la forma de la antena mediante``conjeturas... intuición, experiencia, ecuaciones aproximadas o estudios

empíricos'' (p. 50). Esta técnica requiere mucho tiempo, a menudo no produceresultados óptimos y tiende a funcionar bien sólo con diseños simétricos yrelativamente simples. En contraste, con el método del algoritmo genético, elingeniero especifica las propiedades electromagnéticas de la antena, y el AGsintetiza automáticamente una configuración que sirva.

Figure: Una antena genética de alambre doblado (de Altshuler y Linden 1997, figura 1).

Altshuler y Linden utilizaron su AG para diseñar una antena de siete segmentos polarizada circularmente con una cobertura hemisférica; el resultado se muestra ala izquierda. Cada individuo del AG consistía en un cromosoma binario queespecificaba las coordenadas tridimensionales de cada extremo final de cadaalambre. La aptitud se evaluaba simulando a cada candidato de acuerdo con uncódigo de cableado electromagnético, y el individuo mejor de cada ronda seconstruía y probaba. Los autores describen la forma de esta antena, que no se parece a las antenas tradicionales y carece de una simetría obvia, como`ìnusualmente extraña'' y `àntiintuitiva'' (p. 52), aunque tenía un patrón deradiación casi uniforme y con un gran ancho de banda tanto en la simulación

como en la prueba experimental, adecuándose excelentemente a la especificacióninicial. Los autores concluyen que un método basado en algoritmos genéticos para diseñar antenas se muestra `èxcepcionalmente prometedor''. ``... este nuevo procedimiento de diseño es capaz de encontrar antenas genéticas capaces deresolver de manera efectiva difíciles problemas de antenas, y será especialmenteútil en situaciones en las que los diseños existentes no sean adecuados'' (p. 52).






Mercados financieros

Mahfoud y Mani 1996[46] utilizaron un algoritmo genético para predecir elrendimiento futuro de 1.600 acciones ofertadas públicamente. Concretamente, alAG se le asignó la tarea de predecir el beneficio relativo de cada acción, definidocomo el beneficio de esa acción menos el beneficio medio de las 1.600 accionesa lo largo del periodo de tiempo en cuestión, 12 semanas (un cuarto delcalendario) en el futuro. Como entrada, al AG se le proporcionaron datoshistóricos de cada acción en forma de una lista de 15 atributos, como la relación precio-beneficio y el ritmo de crecimiento, medidos en varios puntos del tiempo pasado; se le pidió al AG que evolucionara un conjunto de reglas si/entonces paraclasificar cada acción y proporcionar, como salida, una recomendación sobre quéhacer con respecto a la acción (comprar, vender o ninguna predicción) y un pronóstico numérico del beneficio relativo. Los resultados del AG fueron

comparados con los de un sistema establecido, basado en una red neuronal, quelos autores habían estado utilizando para pronosticar los precios de las acciones yadministrar las carteras de valores durante tres años. Por supuesto, el mercado devalores es un sistema extremadamente ruidoso y no lineal, y ningún mecanismo predictivo puede ser correcto el 100% del tiempo; el reto consiste en encontrar un predictor que sea preciso más de la mitad de las veces.

En el experiemnto, el AG y la red neuronal hicieron pronósticos al final de lasemana para cada una de las 1.600 acciones, durante doce semanas consecutivas.Doce semanas después de cada predicción, se comparó el rendimiento verdadero

con el beneficio relativo predicho. Globalmente, el AG superó significativamentea la red neuronal: en una ejecución de prueba, el AG predijo correctamente ladirección de una acción el 47,6% de las veces, no hizo predicción el 45,8% de lasveces y realizó una predicción incorrecta sólo un 6.6% de las veces, una precisión predictiva total de un 87,8%. Aunque la red neuronal realizó predicciones precisas más a menudo, también hizo predicciones erróneas más amenudo (de hecho, los autores especulan que la mayor capacidad del AG para norealizar predicciones cuando los datos eran dudosos fue un factor de su éxito; lared neuronal siempre produce una predicción a menos que sea restringidaexplícitamente por el programador). En el experimento de las 1.600 acciones, el

AG produjo un beneficio relativo de un +5,47%, contra el +4,40% de la redneuronal -una diferencia estadísticamente significativa. De hecho, el AG tambiénsuperó significativamente a tres índices bursátiles importantes -el S&P 500, elS&P 400 y el Russell 2000- en este periodo; la casualidad fue excluída comocausa de este resultado con un margen de confianza de un 95%. Los autoresatribuyen este convincente éxito a la capacidad del algoritmo genético de percatarse de relaciones no lineales difícilmente evidentes para los observadores







humanos, además del hecho de que carece del ``prejuicio contra las reglasantiintuitivas y contradictorias'' (p. 562) de los expertos humanos.

Andreou, Georgopoulos y Likothanassis 2002[4] lograron un éxito similarutilizando algoritmos genéticos híbridos para evolucionar redes neuronales que

predijeran los tipos de cambio de monedas extranjeras hasta un mes en el futuro.Al contrario que en el ejemplo anterior, donde competían AGs y redesneuronales, aquí los dos trabajaron conjuntamente: el AG evolucionó laarquitectura (número de unidades de entrada, número de unidades ocultas y laestructura de enlaces entre ellas) de la red, que luego era entrenada por unalgoritmo de filtro.

Se le proporciaron al algoritmo 1.300 valores brutos diarios de cinco divisascomo información histórica -el dólar estadounidense, el marco alemán, el francofrancés, la libra esterlina y el dracma griego- y se le pidió que predijera sus

valores futuros para los 1, 2, 5 y 20 días posteriores. El rendimiento del AGhíbrido mostró, en general, un ``nivel excepcional de precisión'' (p. 200) en todoslos casos probados, superando a otros varios métodos, incluyendo a las redesneuronales en solitario. Los autores concluyen que ``se ha logrado unexcepcional éxito predictivo tanto con un horizonte predictivo de un paso comode varios pasos'' (p. 208) -de hecho, afirman que sus resultados son mejores condiferencia que cualquier estrategia predictiva relacionada que se haya aplicado enesta serie de datos u otras divisas.

La utilización de los AGs en los mercados financieros ha empezado a extenderse

en las empresas de corretaje bursátil del mundo real. Naik 1996[48] informa deque LBS Capital Management, una empresa estadounidense cons ede en Florida,utiliza algoritmos genéticos para escoger las acciones de los fondos de pensionesque administra. Coale 1997[17] y Begley y Beals 1995[9] informan de que FirstQuadrant, una empresa de inversiones de Californa que mueve más de 2.200millones de dólares, utiliza AGs para tomar decisiones de inversión en todos susservicios financieros. Su modelo evolucionado gana, de media, 225 dólares porcada 100 dólares invertidos durante seis años, en contraste con los 205 dólares deotros tipos de sistemas de modelos.

Juegos

Una de las demostraciones más novedosas y persuasivas de la potencia de losalgoritmos genéticos la presentaron Chellapilla y Fogel 2001[13], que utilizaronun AG para evolucionar redes neuronales que pudieran jugar a las damas. Losautores afirman que una de las mayores dificultades en este tipo de problemasrelacionados con estrategias es el problema de la asignación de crédito -en otras























palabras, ¿cómo escribir una función de aptitud? Se ha creído ampliamente quelos criterios simples de ganar, perder o empatar no proporcionan la suficienteinformación para que un algoritmo genético averigüe qué constituye el buen juego.

En este artículo, Chellapila y Fogel echan por tierra esa suposición. Dados sólolas posiciones espaciales de las piezas en el tablero y el número total de piezasque posee cada jugador, fueron capaces de evolucionar un programa de damasque jugaba a un nivel competitivo con expertos humanos, sin ningunainformación de entrada inteligente acerca de lo que constituye el buen juego -esmás, ni siquiera se les dijo a los individuos del algoritmo evolutivo cuál era elcriterio para ganar, ni se les dijo el resultado de ningún juego.

En la representación de Chellapilla y Fogel, el estado del juego estabarepresentado por una lista numérica de 32 elementos, en donde cada posición de

la lista correspondía a una posición disponible en el tablero. El valor de cada posición era 0 para una casilla desocupada, -1 si esa casilla estaba ocupada poruna pieza enemiga, +1 si la casilla estaba ocupada por una de las piezas del programa, y -K o +K si la casilla estaba ocupada por una dama enemiga o amiga.(El valor de K no se especificaba a priori, sino que, de nuevo, era determinado por la evolución durante el curso del algoritmo). Acompañando a todo esto habíauna red neuronal con múltiples capas de procesamiento y una capa de entradacon un nodo para cada una de las 4x4, 5x5, 6x6, 7x7 y 8x8 posibles casillas deltablero. La salida de la red neuronal para una colocación de las piezas dada eraun valor entre -1 y +1, que indicaba cómo de buena le parecía esa posición. Paracada movimiento, se le presentaba a la red neuronal un árbol de juego quecontenía todos los movimientos posibles hasta cuatro turnos en el futuro, y elmovimiento se decidía basándose en qué rama del árbol producía los mejoresresultados.

El algoritmo evolutivo comenzó con una población de 15 redes neuronales con pesos y tendencias, generados aleatoriamente, asignados a cada nodo y conexión;luego, cada individuo se reprodujo una vez, generando una descendencia convariaciones en los valores de la red. Luego estos 30 individuos compitieron por lasupervivencia jugando entre ellos; cada individuo compitió en cada turno con 5oponentes elegidos aleatoriamente. Se otorgó 1 punto a cada victoria y sedescontaban 2 puntos por cada derrota. Se seleccionaron los 15 mejores jugadores en relación a su puntuación total, y el proceso se repitió. La evolucióncontinuó durante 840 generaciones más (aproximadamente seis meses de tiempode computación).



Clase Puntuación

Gran Maestro +2.400

Maestro 2.200-2.399

Experto 2.000-2.199Clase A 1.800-1.999

Clase B 1.600-1.799

Clase C 1.400-1.599

Clase J <200

El mejor individuo que surgió de esta selección fue inscrito como competidor enla página web de juegos http://www.zone.com. Durante un periodo de dos meses, jugó contra 165 oponentes humanos que componían una gama de niveles altos,desde clase C a maestros, de acuerdo con el sistema de clasificaciones de laFederación de Ajedrez de Estados Unidos (mostrado a la izquierda, con algunosrangos omitidos en aras de claridad). De estas partidas, la red neuronal ganó 94, perdió 39 y empató 32; en base a las clasificaciones de los oponentes en estas partidas, la red neuronal evolucionada era equivalente a un jugador con una puntuación media de 2.045,85, colocándola en el nivel experto -una clasificaciónsuperior a la del 99,61% de los 80.000 jugadores registrados en la página web.Una de las victorias más significativas de la red neuronal fue cuando venció a un jugador clasificado en la posición 98 de todos los jugadores registrados, cuya

puntuación estaba tan sólo 27 puntos por debajo del nivel de maestro.Las pruebas realizadas con un sencillo programa diferencial en las piezas (que basa sus movimientos solamente en la diferencia entre el número de piezas quequedan en cada lado) con una capacidad de anticipación de 8 movimientosdemostró que la red neuronal era significativamente superior, con una puntuaciónde más de 400 puntos por encima. `Ùn programa que se basa sólo en el númerode piezas y en una búsqueda de ocho capas vencerá a muchas personas, pero noes un experto. La mejor red neuronal evolucionada sí lo es'' (p. 425). Aunque podía buscar posiciones dos movimientos más lejos que la red neuronal, el

programa diferencial en las piezas perdió contundentemente 8 de 10 partidas.Esto demuestra concluyentemente que la red neuronal evolucionada no sólo estácontando piezas, sino que de alguna manera procesa las características espacialesdel tablero para decidir sus movimientos. Los autores señalan que los oponentesde zone.com que los movimientos de la red neuronal eran `èxtraños'', pero sunivel global de juego fue descrito como ``muy duro'' o con términos elogiosossimilares.



Para probar más a la red neuronal evolucionada (a la que los autores nombraron`Ànaconda'' porque a menudo ganaba restringiendo la movilidad de susoponentes), jugó contra un programa de damas comercial, el Hoyle ClassicGames, distribuído por Sierra Online (Chellapilla y Fogel 2000[14]). Este programa viene con un surtido de personajes incorporados, cada uno con un nivel

de juego distinto. Anaconda se puso a prueba con tres personajes (``Beatrice'',``Natasha'' y ̀ `Leopold'') designados como jugadores expertos, jugando una partida con las rojas y otra partida con las blancas contra cada uno de ellos conuna capacidad de anticipación de 6 movimientos. Aunque los autores dudaban deque esta profundidad de anticipación pudiera darla a Anaconda la capacidad de juego experto que demostró anteriormente, consiguió seis victorias seguidas delas seis partidas jugadas. Basándose en este resultado, los autores expresaronescepticismo sobre si el software Hoyle jugaba al nivel que anunciaba, ¡aunquedebe señalarse que llegaron a esta conclusión basándose solamente en la facilidadcon la que Anaconda le venció!

La prueba definitiva de Anaconda se detalla en Chellapilla y Fogel 2002[15],cuando la red neuronal evolucionada jugó contra el mejor jugador de damas delmundo: Chinook , un programa diseñado principalmente por el Dr. JonathanSchaeffer, de la Universidad de Alberta. Con una puntuación de 2.814 en 1996(mientras que sus competidores humanos más cercanos andan por los 2.600),Chinook incorpora un libro de movimientos de apertura proporcionado porgrandes maestros humanos, un conjunto sofisticado de algoritmos de juego parala parte central de la partida, y una base de datos completa de todos losmovimientos posibles cuando quedan en el tablero 10 piezas o menos, de maneraque nunca comete un error durante un final de partida. Se invirtió una cantidadenorme de inteligencia y experiencia humana en el diseño de este programa.

Chellapilla y Fogel enfrentaron a Anaconda y Chinook en un torneo de 10 partidas, con Chinook jugando al nivel de 5 capas de anticipación,aproximándolo más o menos al nivel de maestro. Chinook ganó estacompetición, cuatro victorias a dos, con cuatro empates. (Curiosamente, comoseñalan los autores, en dos de las partidas que acabaron con empate, Anacondalideraba con cuatro damas mientras que Chinook tenía tres. Además, una de lasvictorias de Chinook vino tras una serie de movimientos con búsqueda de 10capas sacados de su base de datos de finales de partida; unos movimientos queAnaconda, con una anticipación de 8 capas, no pudo anticipar. Si Anacondahubiera tenido acceso a una base de datos de finales de partida de la mismacalidad de la de Chinook, el resultado del torneo bien podría haber sido el devictoria para Anaconda, cuatro a tres). Estos resultados ``proporcionan un buensustento a la puntuación de experto que se ganó Anaconda en www.zone.com''(p. 76), con una puntuación global de 2.030-2.055, comparable a la puntuación






http://www.cs.ualberta.ca/chinook








de 2.045 que ganó jugando contra humanos. Aunque Anaconda no es un jugadorinvulnerable, es capaz de jugar competitivamente en el nivel experto ycomportarse ante una variedad de jugadores de damas humanos extremadamentehábiles. Cuando uno considera los criterios de aptitud tan sencillos con los que seobtuvieron estos resultados, el surgimiento de Anaconda proporciona una

espectacular corroboración del poder de la evolución.

Geofísica

Sambridge y Gallaguer 1993[56] utilizaron un algoritmo genético para loshipocentros de los terremotos basándose en datos sismológicos. (El hipocentro esel punto bajo la superficie terrestre en el que se origina un terremoto. El epicentroes el punto de la superficie directamente encima del hipocentro). Esto es unatarea sumamente compleja, ya que las propiedades de las ondas sísmicasdependen de las propiedades de las capas de roca a través de las que viajan. Elmétodo tradicional para localizar el hipocentro se basa en lo que se conoce comoalgoritmo de inversión sísmico, que empieza con la mejor estimación de laubicación, calcula las derivadas del tiempo de viaje de la onda con respecto al punto de origen, y realiza una operación de matriz para proporcionar unaubicación actualizada. Este proceso se repite hasta que se alcanza una soluciónaceptable. (Este Mensaje del Mes, de noviembre de 2003, proporciona másinformación). Sin embargo, este método requiere información diferencial y es propenso a quedar atrapado en óptimos locales.

Un algoritmo de localización que no dependa de información diferencial omodelos de velocidad puede evitar esta deficiencia calculando sólo el problemadirecto -la diferencia entre los tiempos de llegada de la onda observados y predichos para distintas localizaciones del hipocentro. Sin embargo, un métodode búsqueda exhaustivo basado en este método sería demasiado costosocomputacionalmente. Éste, por supuesto, es precisamente el tipo de problema deoptimización en el que destacan los algoritmos genéticos. Como todos los AGs,el propuesto por el artículo citado es paralelo en naturaleza -en lugar de mover unsolo hipocentro más y más cerca hacia la solución, comienza con una nube dehipocentros potenciales que encoge con el tiempo hasta converger en una sola

solución. Los autores afirman que su método ̀ `puede localizar rápidamentesoluciones casi óptimas sin una búsqueda exhaustiva del espacio de parámetros''(p. 1.467), muestra `ùn comportamiento muy organizado que produce una búsqueda eficiente'' y es `ùn compromiso entre la eficiencia de los métodos basados en derivadas y la robustez de una búsqueda exhaustiva completamenteno lineal'' (p. 1.469). Los autores concluyen que su algoritmo genético es`èficiente para una verdadera optimización global'' (p. 1.488) y `ùna



http://www.talkorigins.org/origins/postmonth/nov03.html







herramienta nueva y poderosa para realizar búsquedas robustas de hipocentros''(p. 1.489).

Ingeniería de materiales

Giro, Cyrillo y Galvão 2002[27] utilizaron algoritmos genéticos para diseñar polímeros conductores de electricidad basados en el carbono, conocicos como polianilinas. Estos polímeros, un tipo de material sintético inventadorecientemente, tienen ̀ `grandes aplicaciones tecnológicas potenciales'' y podríanabrir la puerta a ``nuevos fenómenos físicos fundamentales'' (p. 170). Sinembargo, debido a su alta reactividad, los átomos de carbono pueden formar unnúmero virtualmente infinito de estructuras, haciendo que la búsqueda de nuevasmoléculas con propiedades interesantes sea del todo imposible. En este artículo,los autores aplican un enfoque basado en AGs a la tarea de diseñar moléculasnuevas con propiedades especificadas a priori, comenzando con una población decandidatos iniciales generada aleatoriamente. Concluyen que su metodología puede ser una ̀ `herramienta muy efectiva'' (p. 174) para guiar a losinvestigadores en la búsqueda de nuevos compuestos y es lo suficientementegeneral para que pueda extenderse al diseño de nuevos materiales que pertenezcan virtualmente a cualquier tipo de molécula.

Weismann, Hammel, y Bäck 1998[63] aplicaron algoritmos evolutivos a un problema industrial ``no trivial'' (p. 162): el diseño de revestimientos ópticosmulticapa para filtros que reflejan, transmiten o absorben luz de frecuencias

especificadas. Estos revestimientos se utilizan en la fabricación de gafas de sol, por ejemplo, o discos compactos. Su fabricación es una tarea precisa: las capasdeben colocarse en una secuencia particular y con un grosor particular para producir el resultado deseado, y las variaciones incontrolables del entorno defabricación, como la temperatura, la polución o la humedad, pueden afectar alrendimiento del producto acabado. Muchos óptimos locales no son robustos anteestas variaciones, lo que significa que una mayor calidad del producto se pagacon una tasa mayor de desviaciones indeseadas. El problema particularconsiderado en este artículo también tenía múltiples criterios: además de lareflectancia, también se consideró la composición espectral (color) de la luz

reflejada.El AE actuó variando el número de capas de revestimiento y el grosor de cadauna de ellas, y produjo diseños que eran ``sustancialmente más robustos a lavariación de parámetros'' (p. 166) y tenían un rendimiento medio mayor que losmétodos tradicionales. Los autores concluyen que ̀ `los algoritmos evolutivos pueden competir e incluso superar a los métodos tradicionales'' (p. 167) de diseño










de revestimientos ópticos multicapa, sin tener que incorporar un conocimientoespecífico del dominio en la función de búsqueda y sin tener que alimentar a la población con buenos diseños iniciales.

Es digno de mención otro uso de los AGs en el campo de la ingeniería de

materiales: Robin et al. 2003[54] utilizaron AGs para diseñar patrones deexposición para un haz de electrones de litografía, utilizado para grabarestructuras a una escala menor a la del micrómetro en circuitos integrados.Diseñar estos patrones es una tarea muy difícil; es pesado y costosodeterminarlos experimentalmente, pero la alta dimensionalidad del espacio de búsqueda frustra a la mayoría de los algoritmos de búsqueda. Deben optimizarsesimultáneamente hasta 100 parámetros para controlar el haz de electrones yevitar la dispersión y efectos de proximidad que arruinarían las estructuras finasque se estén esculpiendo. El problema directo -determinar la estructura resultantecomo función de la cantidad de electrones- es sencillo y fácil de simular, pero el problema inverso de determinar la cantidad de electrones para producir unaestructura dada, que es lo que se pretende resolver aquí, es mucho más difícil yno existe una solución determinista.

Se aplicaron algoritmos genéticos a este problema, ya que ``se sabe que soncapaces de encontrar soluciones buenas a problemas muy complejos de altadimensionalidad'' (p. 75) sin necesidad de proporcionarles información específicadel dominio acerca de la topología del paisaje de búsqueda. Los autores delartículo emplearon un AG de estado estacionario con selección por rueda deruleta en una simulación por computador, que produjo unos patrones deexposición ``muy bien optimizados'' (p. 77). En contraste, se utilizó un tipo detrepacolinas conocido como algoritmo bajacolinas-simplex (simplex-downhill)en el mismo problema, sin éxito; el método BS quedaba rápidamente atrapado enóptimos locales de los que no podía escapar, produciendo soluciones de pocacalidad. Un híbrido entre los métodos del AG y el BS tampoco pudo mejorar losresultados ofrecidos por el AG en solitario.

Matemáticas y algoritmia

Aunque algunas de las aplicaciones más prometedoras y las demostraciones másconvincentes de la potencia de los AGs se encuentran en el campo de laingeniería de diseño, también son relevantes en problemas ̀ `puramente''matemáticos. Haupt y Haupt 1998[34] (p. 140) describen el uso de AGs pararesolver ecuaciones de derivadas parciales no lineales de alto orden,normalmente encontrando los valores para los que las ecuaciones se hacen cero,










y dan como ejemplo una solución casi perfecta para los coeficientes de laecuación de quinto orden conocida como Super Korteweg-de Vries.

Ordenar una lista de elementos es una tarea importante en la informática, y unared de ordenación es una manera eficiente de conseguirlo. Una red de ordenación

es una lista fija de comparaciones realizadas en un conjunto de un tamaño dado;en cada comparación se comparan dos elementos y se intercambian si no están enorden. Koza et al. 1999[41] (p. 952) utilizaron programación genética paraevolucionar redes de ordenación mínimas para conjuntos de 7 elementos (16comparaciones), conjuntos de 8 elementos (19 comparaciones) y conjuntos de 9elementos (25 comparaciones). Mitchell 1996[47], p. 21, describe el uso dealgoritmos genéticos por W. Daniel Hillis para encontrar una red de ordenaciónde 61 comparaciones para un conjunto de 16 elementos, sólo un paso más allá dela más pequeña conocida. Este último ejemplo es especialmente interesante porlas dos innovaciones que utiliza: cromosomas diploides y, más notablemente,coevolución de huésped/parásito. Tanto las redes de búsqueda como los casos de prueba evolucionaron conjuntamente; se les otorgó mayor aptitud a las redes deordenación que ordenaran correctamente un mayor número de casos de prueba,mientras que se les otorgó mayor aptitud a los casos de prueba que pudieran`èngañar'' a un mayor número de redes de búsqueda para que ordenaranincorrectamente. El AG con coevolución rindió significativamente mejor que elmismo AG sin ella.

Un ejemplo final de AG digno de mención en el campo de la algoritmia puedeencontrarse en Koza et al. 1999[41], que utilizó programación genética paradescubrir una regla para el problema de clasificación por mayoría en autómatascelulares de una dimensión, una regla mejor que todas las reglas conocidasescritas por humanos. Un autómata celular de una dimensión puede imaginarsecomo una cinta finita con un número dado de posiciones (celdas) en ella, cadauna de las cuales puede contener el estado 0 o el estado 1. El autómata se ejecutadurante un número dado de pasos temporales; en cada paso, cada celda adquiereun nuevo valor basado en su valor anterior y el valor de sus vecinos máscercanos. (El Juego de la Vida es un autómata celular bidimensional). El problema de la clasificación por mayoría implica encontrar una tabla de reglas talque si más de la mitad de las celdas de la cinta son 1 inicialmente, todas lasceldas se ponen a 1; de lo contrario, todas las celdas se ponen a 0. El reto consisteen el hecho de que cualquier celda individual sólo tiene acceso a informaciónacerca de sus vecinos más cercanos; por lo tanto, los conjuntos de reglas buenosdeben encontrar de algún modo una manera de transmitir información sobreregiones distantes de la cinta.










http://www.math.com/students/wonders/life/life.html









Se sabe que no existe una solución perfecta a este problema -ningún conjunto dereglas puede clasificar con precisión todas las configuraciones iniciales posibles-, pero durante los últimos veinte años ha habido una larga sucesión de solucionescada vez mejores. En 1978, tres investigadores desarrollaron la famosa reglaGKL, que clasifica correctamente un 81,6% de los posibles estados iniciales. En

1993, se descubrió una regla mejor con una precisión de un 81,8%; en 1995 seencontró otra regla con una precisión de un 82,178%. Todas estas reglasrequirieron para su desarrollo de un esfuerzo significativo por parte de humanosinteligentes y creativos. En contraste, la mejor regla descubierta mediante programación genética, descrito en Koza et al. 1999[41], p. 973, tiene una precisión total de 82,326% -mejor que cualquiera de las soluciones humanasdesarrolladas durante las dos últimas décadas. Los autores señalan que susnuevas reglas son cualitativamente distintas a las reglas publicadas conanterioridad, al emplear representaciones internas muy detalladas de la densidadde estados y conjuntos intrincados de señales para comunicar información alargas distancias.

Ejército y cumplimiento de la ley

Kewley y Embrechts 2002[39] utilizaron algoritmos genéticos para evolucionar planes tácticos para las batallas militares. Los autores señalan que ``planear una batalla militar táctica es una tarea compleja multidimensoinal que a menudoatormenta a los profesionales experimentados'' (p. 163), no sólo porque este tipode decisiones a menudo se toman bajo condiciones de mucho estrés, sino también

porque hasta los planes más sencillos requieren tomar en cuenta un gran númerode variables y consecuencias: minimizar las bajas amigas, maximizar las bajasenemigas, controlar el terreno deseado, conservar recursos, etcétera. Los planificadores humanos tienen dificultades al tratar con las complejidades de estatarea y a menudo deben recurrir a métodos ``rápidos y sucios'', como hacer lo quefuncionase la última vez.

Para superar estas dificultades, los autores del artículo citado desarrollaron unalgoritmo genético para automatizar la creación de planes de batalla, enconjunción con un programa gráfico de simulación de batallas. El comandante

introduce el resultado deseado y el AG evoluciona automáticamente un plan de batalla; en la simulación utilizada, se tomaron en cuenta factores como latopografía del terreno, la cobertura vegetal, la velocidad del movimiento detropas, y la precisión en los disparos. En este experimento también se utilizó lacoevolución para mejorar la calidad de las soliciones: los planes de batalla de lasfuerzas enemigas evolucionaron simultáneamente con los planes amigos,forzando al AG a corregir cualquier debilidad de su plan que pudiese explotar el










enemigo. Para medir la calidad de las soluciones producidas por el AG, secompararon con planes de batalla para el mismo escenario producidos por ungrupo de ̀ èxpertos militares experimentados... considerados muy capaces dedesarrollar planes de acción para el tamaño de las fuerzas utilizadas en esteexperimento'' (p. 166). Estos avezados expertos desarrollaron su propio plan y,

cuando la solución del AG estuvo acabada, se les dio la oportunidad deexaminarla y modificarla como vieran conveniente. Finalmente, todos los planesse ejecutaron varias veces en el simulador para determinar su calidad media.

Los resultados hablan por sí mismos: la solución evolucionada superó tanto al propio plan de los expertos militares como al plan producido por susmodificaciones sobre la solución del AG. ``...Los planes producidos por losalgoritmos automáticos tenían un rendimiento medio significativamente mayor alde los generados por los experimentados expertos militares'' (p. 161). Es más, losautores señalan que el plan del AG tenía sentido táctico. (Consistía en un ataquea dos flancos a la posición enemiga por pelotones de infantería mecanizadaapoyados por helicópteros de ataque y exploradores terrestres, en conjunción convehículos aéreos no tripulados realizando labores de reconocimiento para elfuego directo de artillería). Por añadidura, el plan evolucionado incluía unidadesamigas individuales llevando a cabo misiones doctrinales -una propiedademergente que apareció durante el curso de la ejecución, en lugar de serespecificada por el experimentador. En campos de batalla modernos, cada vezmás conectados por red, el atractivo potencial de un algoritmo evolutivo que pueda automatizar la producción de planes tácticos de alta calidad debería serobvio.

Naik 1996[48] informa de un uso interesante de los AGs en el cumplimiento dela ley, describiendo el software ``FacePrints'', un proyecto para ayudar a lostestigos a identificar y describir a los sospechosos criminales. La imagen clichédel artista policía haciendo un dibujo del rostro del sospechoso en base a ladescripción de los testigos es un método difícil e ineficiente: la mayoría de lagente no es buena describiendo aspectos individuales del rostro de una persona,como el tamaño de la nariz o la forma de la mandíbula, pero sin embargo sonmejores al reconocer caras completas. FacePrints aprovecha esto utilizando unalgoritmo genético que evoluciona dibujos de caras basándose en bases de datosde cientos de características individuales que pueden combinarse de infinitasmaneras. El programa muestra a los testigos imágenes de rostros generadasaleatoriamente, y éstos escogen las que más se parecen a la persona que vieron;las caras seleccionadas mutan y se combinan para generar nuevas combinacionesde características, y el proceso se repite hasta que emerge un retrato preciso delrostro del sospechoso. En un caso real de atraco, los retratos definitivos que






crearon los tres testigos eran sorprendentemente parecidos, y el dibujo resultanteapareció en el periódico local.

Biología molecular

En los seres vivos, las proteínas transmembrana son proteínas que sobresalen deuna membrana celular. Las proteínas transmembrana realizan a menudofunciones importantes como detectar la presencia de ciertas sustancias en elexterior de la célula o transportarlas hacia el interior de la célula. Paracomprender el comportamiento de una proteína transmembrana es necesarioidentificar el segmento de la proteína que realmente está insertado en lamembrana, lo que se conoce como dominio transmembrana. Durante las dosúltimas décadas, los biólogos moleculares han publicado una serie de algoritmoscada vez más precisos para este propósito.

Todas las proteínas utilizadas por los seres vivos están formadas por los mismos20 aminoácidos. Algunos de estos aminoácidos son hidrofóbicos, lo que significaque repelen el agua, y algunos son hidrofílicos, lo que significa que atraen elagua. Las secuencias de aminoácidos que son parte de un dominiotransmembrana tienen probabilidad de ser hidrofóbicas. Sin embargo, lahidrofobicidad no es una característica definida con precisión, y no existeacuerdo sobre una escala para medirla.

Koza et al. 1999[41], capítulo 16, utilizaron programación genética para diseñarun algoritmo que identificase el dominio transmembrana de una proteína. Se lesuministró al programa genético un conjunto de operadores matemáticosestándares con los que trabajar, además de un conjunto de funciones booleanas para la detección de aminoácidos que devuelven +1 si el aminoácido de una posición dada es el aminoácido que detectan o -1 en caso contrario. (Por ejemplo,la función A? recibe como argumento un número que corresponde a una posicióndentro de la proteína, y devuelve +1 si el aminoácido de esa posición es alanina,denotado por la letra A, y si no devuelve -1). Una variable de memoriacompartida contenía una cuenta de la suma total, y cuando el algoritmo acababa,el segmento proteínico se identificaba como dominio transmembrana si su valor

era positivo. Con tan sólo estas herramientas, ¿haría falta más información paraque un diseñador humano produjese una solución eficiente a este problema?

Las aptitudes de las soluciones producidas por la programación genética fueronevaluadas probándolas con 246 segmentos proteínicos de los que se conocía sucondición de transmembrana. Luego se evaluó al mejor individuo de la pruebacon 250 casos adicionales inéditos (out-of-sample), y se comparó su efectividadcon la de los cuatro mejores algoritmos humanos para el mismo propósito. El







resultado: la programación genética produjo un algoritmo de identificación desegmentos transmembrana con una tasa total de error del 1,6%-significativamente menor que las de los cuatro algoritmos humanos, el mejor delos cuales tenía una tasa de error del 2,5%. El algoritmo diseñado genéticamente,al que los autores llamaron regla 0-2-4, funciona de la manera siguiente:

Incrementar la suma en 4 unidades por cada instancia de ácido glutámico(un aminoácido cargado eléctricamente y muy hidrofílico) del segmento proteínico.

Incrementar la suma en 0 unidades por cada instancia de alanina,fenilanalina, isoleucina, leucina, meionina o valina (todos aminoácidosmuy hidrofóbicos) del segmento proteínico.

Incrementar la suma en 2 unidades por cada instancia de cualquier otroaminoácido.

Si [(SUMA - 3,1544)/0,9357] es menor que la longitud del segmento proteínico, clasificar ese segmento como dominio transmembrana; de locontrario, clasificarlo como dominio no transmembrana.

Reconocimiento de patrones y explotación de datos

La competición en la industria actual de las telecomunicaciones es feroz, y se haacuñado un nuevo término -``fuga''1- para describir la velocidad a la que losusuarios se cambian de un proveedor de servicios a otro. La fuga le cuesta a lascompañías de telecomunicaciones una gran cantidad de dinero cada año, y

reducir las fugas es un factor importante para aumentar la rentabilidad. Si lascompañías pueden contactar con los clientes que tienen probabilidad de cambiary ofrecerles incentivos especiales para que se queden, puede reducirse la tasa defugas; pero ninguna compañía tiene los recursos para contactar a más de un pequeño porcentaje de sus clientes. El problema es, por tanto, cómo identificar alos clientes que más piensen fugarse con mayor probabilidad. Todas lascompañías tienen grandes bases de datos con información de los clientes queteóricamente puede utilizarse para este propósito; pero ¿qué método funcionamejor para examinar esta enorme cantidad de datos e identificar los sutiles patrones y tendencias que indican la probabilidad de fuga de un cliente?

Au, Chan y Yao 2003[7] aplicaron algoritmos genéticos a este problema paragenerar un conjunto de reglas de tipo si-entonces para predecir la probabilidad defuga de distintos grupos de clientes. En su AG, la primera generación de reglas,todas las cuales tenían una condición, fue generada utilizando una técnica deinducción probabilística. Las generaciones posteriores las refinaron, combinandosencillas reglas de una condición con reglas más complejas con varias

http://the-geek.org/docs/algen/#foot204










condiciones. Para la medición de la aptitud se utilizó una medida de correlaciónobjetiva de la ̀ ìnteresantitud'', que no necesitaba información de entradasubjetiva. El algoritmo evolutivo de explotación de datos se probó sobre una basede datos real de 100.000 clientes proporcionada por una compañía malasia, y surendimiento se comparó con el de dos métodos alternativos: una red neuronal

multicapa y un algoritmo basado en árbol de decisiones ampliamente utilizado, elC4.5. Los autores afirman que su AE fue capaz de descubrir regularidadesocultas en la base de datos y ``fue capaz de hacer predicciones precisas de fugacon distintas tasas de fuga'' (p. 542), superando al C4.5 bajo todas lascircunstancias, superando a la red neuronal en tasas mensuales de fuga bajas eigualándola en tasas de fuga mayores y, en ambos casos, alcanzando lasconclusiones más rápidamente. Algunas ventajas más del enfoque evolutivo sonque puede funcionar eficientemente incluso cuando faltan algunos campos dedatos, y que puede expresar sus descubrimientos en conjuntos de reglasfácilmente comprensibles, al contrario que la red neuronal.

Entre algunas de las reglas más interesantes halladas por el AE se encuentran lassiguientes: los clientes tienen más probabilidad de fugarse si se han suscrito personalmente al plan de servicios y no han sido admitidos en ningún plan de bonificación (una solución potencial sería admitir a todos esos clientes en planesde bonificación); los clientes tienen más probabilidad de fugarse si viven enKuala Lumpur, tienen entre 36 y 44 años y pagan sus facturas en efectivo(supuestamente porque es más fácil cambiarse de proveedor para los clientes que pagan al contado, a diferencia de los que cargan en cuenta automáticamente); ylos clientes que viven en Penang y contrataron a través de un cierto vendedortienen más probabilidades de fugarse (este vendedor puede estar proporcionandoun mal servicio al cliente y debería ser investigado).

Rizki, Zmuda y Tamburino 2002[53] utilizaron algoritmos evolutivos paraevolucionar un complejo sistema de reconocimiento de patrones con una ampliavariedad de usos potenciales. Los autores señalan que el reconocimiento de patrones es una tarea cada vez más realizada por algoritmos de aprendizajeautomático, en particular, algoritmos evolutivos. La mayoría de ellos comienzancon un acervo de características predefinidas, del que un AE puede seleccionarcombinaciones apropiadas para la tarea en cuestión; en contraste, este métodoempezaba desde cero, primero evolucionando detectores individuales decaracterística en forma de árboles de expresiones, y luego evolucionandocombinaciones cooperativas de esos detectores para producir un sistemacompleto de reconocimiento de patrones. El proceso evolutivo seleccionaautomáticamente el número de detectores de característica, la complejidad de losdetectores y los aspectos específicos de los datos a los que responde cadadetector.







Para probar su sistema, los autores le asignaron la tarea de clasificar aviones basándose en sus reflexiones rádar. Un mismo tipo de avión puede devolverseñales bastante distintas dependiendo del ángulo y elevación desde el que se leobserva, y distintos tipos de avión pueden devolver señales muy parecidas, asíque esto no es una tarea trivial. El sistema de reconocimiento de patrones

evolucionado clasificó correctamente un 97,2% de los objetivos, un porcentajeneto mayor que el de las otras tres técnicas -una red neuronal perceptrón, unalgoritmo clasificador KNN y un algoritmo de base radial- con las que fuecomparado. (La precisión de la red de base radial era sólo un 0,5% menor que ladel clasificador evolucionado, una diferencia que no es estadísticamentesignificativa, pero la red de base radial necesitó 256 detectores de característicamientras que el sistema reconocedor evolucionado sólo utilizó 17). Comoafirman los autores, ̀ `los sistemas de reconocimiento que evolucionan utilizanmenos características que los sistemas producidos utilizando técnicasconvencionales, pero consiguen una precisión de reconocimiento comparable osuperior'' (p. 607). También se han aplicado varios aspectos de su sistema en problemas que incluyen el reconocimiento óptico de caracteres, la revisiónindustrial y el análisis médico de imágenes.

Hughes y Leyland 2000[37] también aplicaron AGs multiobjetivo a la tarea declasificar objetivos basándose en sus reflexiones rádar. Los datos de una seccióntransversal rádar de alta resolución necesitan enormes cantidades de espacio dealmacenamiento en disco, y producir un modelo realista de la fuente a partir delos datos es muy costoso computacionalmente. En contraste, el método basado enel AG de los autores demostró ser muy exitoso, produciendo un modelo tan bueno como el del método iterativo tradicional, pero reduciendo el gastocomputacional y las necesidades de almacenamiento hasta el punto de que erafactible generar buenos modelos en un ordenador de escritorio. En contraste, elmétodo iterativo tradicional requiere diez veces más resolución y 560.000 vecesmás accesos a los datos de imagen para producir modelos de calidad similar. Losautores concluyen que sus resultados ``demuestran claramente'' (p. 160) lacapacidad del AG de procesar datos de rádar bidimensionales y tridimensionalesde cualquier nivel de resolución con muchos menos cálculos que los métodostradicionales, manteniendo una precisión aceptablemente alta.

Robótica

El torneo internacional RoboCup es un proyecto para promocionar el avance dela robótica, la inteligencia artificial y los campos relacionados, proporcionandoun problema estándar con el que probar las nuevas tecnologías -concretamente,es un campeonato anual de fútbol entre equipos de robots autónomos. (El




http://www.robocup.org/







objetivo fijado es desarrollar un equipo de robots humanoides que puedan venceral equipo humano de fútbol que sea campeón del mundo en 2050; actualmente, lamayoría de los equipos de robots participantes funcionan con ruedas). Los programas que controlan a los miembros del equipo robótico deben exhibir uncomportamiento complejo, decidiendo cuándo bloquear, cuándo tirar, cómo

moverse, cuándo pasar la pelota a un compañero, cómo coordinar la defensa y elataque, etcétera. En la liga simulada de 1997, David Andre y Astro Tellerinscribieron a un equipo llamado Darwin United cuyos programas de controlhabían sido desarrollados automáticamente desde cero mediante programacióngenética, un desafío a la creencia convencional de que `èste problema essimplemente demasiado difícil para una técnica como ésa'' (Andre y Teller1999[3], p. 346).

Para resolver este difícil problema, Andre y Teller le proporcionaron al programagenético un conjunto de funciones de control primitivas como girar, moverse,tirar, etcétera. (Estas funciones estaban también sujetas al cambio y refinamientodurante el curso de la evolución). Su función de aptitud, escrita para querecompensara el buen juego en general en lugar de marcar goles expresamente, proporcionaba una lista de objetivos cada vez más importantes: acercarse a la pelota, golpear la pelota, conservar la pelota en el campo contrario, moverse en ladirección correcta, marcar goles y ganar el partido. Debe señalarse que no sesuministró ningún código para enseñar específicamente al equipo cómoconseguir estos objetivos complejos. Luego los programas evolucionados seevaluaron utilizando un modelo de selección jerárquico: en primer lugar, losequipos candidatos se probaron en un campo vacío y, si no marcaban un gol enmenos de 30 segundos, se rechazaban. Luego se evaluaron haciéndoles jugarcontra un equipo estacionario de ``postes pateadores'' que golpeaban la pelotahacia el campo contrario. En tercer lugar, el equipo jugaba un partido contra elequipo ganador de la competición RoboCup de 1997. Finalmente, los equiposque marcaron al menos un gol contra este equipo jugaron unos contra otros paradeterminar cuál era el mejor.

De los 34 equipos de su división, Darwin United acabó en decimoséptima posición, situándose justo en el medio de la clasificación y superando a la mitadde los participantes escritos por humanos. Aunque una victoria en el torneo sinduda habría sido más impresionante, este resultado es competitivo y significantede pleno derecho, y lo parece aún más a la luz de la historia. Hace unos 25 años,los programas informáticos que jugaban al ajedrez estaban en su infancia; por primera vez, una computadora había sido inscrita recientemente en unacompetición regional, aunque no ganó (Sagan 1979[55], p. 286). Pero `ùnamáquina que juega al ajedrez a un nivel medio de la capacidad humana es unamáquina muy capaz'' (ibid.), y podría decirse que lo mismo es cierto para el











fútbol robotizado. Si las máquinas de ajedrez actuales compiten al nivel de losgrandes maestros, ¿qué tipo de sistemas producirá la programación genéticadentro de 20 o 30 años?

Diseño de rutas y horarios

Burke y Newall 1999[11] utilizaron algoritmos genéticos para diseñar loshorarios de los exámenes universitarios. Se sabe que, en general, el problema delhorario es NP-completo, lo que significa que no se conoce un método para hallarcon garantías una solución óptima en un tiempo razonable. En un problema así,hay restricciones duras -no puede asignarse el mismo aula a dos exámenes a lavez- y restricciones suaves -si es posible, no deben asignarse varios exámenes ensucesión a un mismo estudiante, para minimizar la fatiga. Las restricciones durasdeben satisfacerse, mientras que las restricciones suaves deben satisfacerse lomáximo posible. Los autores llaman `àlgoritmo memético'' a su método híbrido para resolver este problema: un algoritmo evolutivo con selección por rango proporcional a la aptitud, combinado con un trepacolinas local para optimizar lassoluciones halladas por el AE. El AE se utilizó en cuatro conjuntos de datos deuniversidades reales (la menor de las cuales tenía 25.000 alumnos), y susresultados se compararon con los resultados producidos por un método heurísticode vuelta atrás, un algoritmo muy consolidado que se encuentra entre los mejoresque se conocen para este problema y que se utiliza en varias universidades.Comparado con este método, el AE produjo un resultado con una reducción de la penalización bastante uniforme del 40%.

He y Mort 2000[35] aplicaron algoritmos genéticos al problema de hallar rutasóptimas en las redes de telecomunicaciones (como las redes de telefonía eInternet), que se usan para transmitir datos desde los remitentes hasta losdestinatarios. Esto es un problema NP-difícil, un tipo de problema para el que losAGs son `èxtremadamente aptos... y han encontrado una enorme variedad deaplicaciones exitosas en esos campos'' (p. 42). Es además un problemamultiobjetivo, en el que hay que equilibrar objetivos en conflicto comomaximizar el caudal de datos, minimizar los retrasos en la transmisión y la pérdida de datos, encontrar caminos de bajo coste y distribuír la carga

uniformemente entre los encaminadores o conmutadores de la red. Cualquieralgoritmo real satisfactorio debe también ser capaz de redirigir el tráfico de lasrutas principales que fallen o estén congestionadas.

En el AG híbrido de los autores se utilizó un algoritmo de tipo ``primero elcamino más corto'', que minimiza el número de ``saltos'' que debe realizar un paquete de datos dado, para generar la semilla de la población inicial. Sin










embargo, esta solución no tiene en cuenta la congestión o fallo de los enlaces,condiciones inevitables en redes reales, y es entonces cuando el AG toma elcontrol, intercambiando secciones de rutas. Cuando se probó sobre un conjuntode datos derivado de una base de datos en red real de Oracle, se descubrió que elAG era capaz de redirigir enlaces rotos o congestionados, equilibrar la carga de

tráfico y maximizar el caudal total de la red. Los autores afirman que estosresultados demuestran la `èfectividad y escalabilidad'' del AG y que ``se puedenconseguir soluciones óptimas o casi óptimas'' (p. 49).

Esta técnica ha encontrado aplicaciones reales para propósitos similares, comoinforman Begley y Beals 1995[9]. La compañía de telecomunicaciones U.S.West (ahora fusionada con Qwest) se enfrentó a la tarea de desplegar una red defibra óptica. Hasta hace poco, el problema de diseñar la red para minimizar lalongitud total de cable desplegado era resuelto por un ingeniero experimentado;ahora la compañía utiliza un algoritmo genético para realizar la tareaautomáticamente. Los resultados: `Èl tiempo de diseño para las redes nuevas hacaído de dos meses a dos días, y le supone un ahorro a U.S. West de 1 millón a10 millones de dólares cada una'' (p. 70).

Jensen 2003[38] y Chryssolouris y Subramaniam 2001[16] aplicaron algoritmosgenéticos a la tarea de generar programas para líneas de montaje (job shopscheduling). Éste es un problema de optimización NP-difícil con múltiplescriterios: deben tomarse en cuenta factores como el coste, los retrasos y elrendimiento, y puede que se tenga que cambiar al vuelo el programa de la líneade montaje debido a averías en la maquinaria, ausencia de empleados, retrasos enla entrega de piezas, y otras complicaciones, lo que hace que la robustez del programa sea una consideración importante. Ambos artículos concluyen que losAGs son significativamente superiores a las reglas de despacho de prioridadutilizadas comúnmente, al producir programas eficientes que pueden tratar conmás facilidad los retrasos y las averías. Estos resultados no son simplementeteóricos, sino que se han aplicado a situaciones reales:

Como informa Naik 1996[48], los organizadores de los Juegos Paraolímpicos de1992 utilizaron un AG para diseñar los horarios de los eventos. Como informaPetzinger 1995[50], John Deere & Co. ha utilizado AGs para generar los programas de montaje para una planta de Moline, Illinois, que fabrica plantadoras y otras maquinarias agrícolas pesadas. Al igual que los coches delujo, éstas pueden construírse en una gran variedad de configuraciones conmuchas partes y opciones distintas, y la enorme cantidad de maneras posibles deconstruirlas implica que el diseño eficiente de programas de montaje sea un problema aparentemente intratable. La productividad se veía mermada porcuellos de botella en el montaje, los equipos de trabajadores discutían, y se estaba























perdiendo dinero. Finalmente, en 1993, Deer acudió a Bill Fulkerson, un analistae ingeniero de personal que concibió la utilización de un algoritmo genético para producir programas de montaje para la planta. Tras superar el escepticismoinicial, el AG demostró su valía rápidamente: la producción mensual aumentó un50 por ciento, el tiempo extra casi desapareció y otras plantas de Deere están

incorporando los AGs en sus propios diseños de programas de montaje.

Como informa Rao 1998[52], Volvo ha utilizado un programa evolutivo llamadoOptiFlex para diseñar el programa de montaje de su fábrica de Dublín, Virginia,de un millón de metros cuadrados, una tarea que requiere controlar cientos derestricciones y millones de permutaciones posibles para cada vehículo. Comotodos los algoritmos genéticos, OptiFlex funciona combinando aleatoriamentedistintos programas de montaje posibles, determinando su aptitud clasificándolosen base a sus costos, beneficios y restricciones, y luego haciendo que las mejoressoluciones intercambien genes entre ellas y vuelvan a la población para otra prueba. Hasta hace poco, esta desalentadora tarea era responsabilidad de uningeniero humano, al que le llevaba hasta cuatro días producir el programa paracada semana; ahora, gracias a los AGs, esta tarea se puede completar en un díacon una mínima intervención humana.

Como informa Lemley 2001[45], United Distillers and Vintners, una empresaescocesa que es el mayor y más rentable distribuidor de licores del mundo y esresponsable de más de un tercio de la producción mundial de whisky de grano,utiliza un algoritmo genético para administrar su inventario y sus suministros.Esto es una tarea desalentadora que exige almacenar y distribuír eficientementemás de 7 millones de barriles, que contienen 60 recetas distintas, entre un enormesistema de almacenes y destilerías, dependiendo de una multitud de factorescomo la edad, el número de malta, el tipo de madera y las condiciones delmercado. Anteriormente, coordinar este complejo flujo de suministro y demandarequería de cinco empleados a tiempo completo. Hoy, unas cuantas pulsacionesde teclado en un ordenador solicitan a un algoritmo genético que genere un programa cada semana, y la eficiencia de almacenamiento casi se ha duplicado.

Beasley, Sonander y Havelock 2001[8] utilizaron un AG para programar losaterrizajes del London Heathrow, el aeropuerto más transitado del Reino Unido.Esto es un problema multiobjetivo que implica, entre otras cosas, minimizar losretrasos y maximizar el número de vuelos mientras se mantiene la suficientedistancia de separación entre los aviones (los vórtices de aire que se forman en laestela de un avión pueden ser peligrosos para otro avión que vuele demasiadocerca). Comparado con los horarios reales de un periodo intensivo delaeropuerto, el AG fue capaz de reducir el tiempo de espera medio en un 2-5%,implicando dos o tres vuelos extra despegando y aterrizando por cada hora -una














mejora significativa. Sin embargo, se han logrado mejoras mayores: como seinforma en Wired 2002[1], aeropuertos internacionales y líneas aéreasimportantes como Heatrhow, Toronto, Sydney, Las Vegas, San Francisco,America West Airlines, AeroMexico y Delta Airlines están utilizando algoritmosgenéticos para programar los despegues, aterrizajes, mantenimiento y otras

tareas, mediante el software del Ascent Technology's SmartAirport OperationsCenter (ver http://www.ascent.com/faq.html). Cruzando y mutando lassoluciones en forma de horarios que incorporan miles de variables, `Àscentvence con comodidad a los humanos, aumentando la productividad hasta en un30 por ciento en todos los aeropuertos en los que se ha implementado''.

Ingeniería de sistemas

Benini y Toffolo 2002[10] aplicaron un algoritmo genético a la tareamultiobjetivo de diseñar molinos eólicos para generar energía eléctrica. Estediseño ̀ ès un procedimiento complejo caracterizado por varias decisiones sobrecontrapartidas... El proceso de toma de decisiones es muy difícil y no haytendencias de diseño bien establecidas'' (p. 357); como resultado, hoy existenvarios tipos de turbina distintos y no hay acuerdo sobre cuál es la óptima, sialguna lo es. Deben tomarse en cuenta objetivos mutuamente exclusivos como la producción máxima de energía anual y el coste mínimo de la energía. En esteartículo se utilizó un algoritmo evolutivo multiobjetivo para encontrar el mejorconjunto de contrapartidas entre estos objetivos, construyendo palas de molinocon una configuración óptima de características como la velocidad de la punta de

la pala, la razón buje/punta, y la distribución de cuerda y giro. Al final, al AGconsiguió encontrar soluciones competitivas con los diseños comerciales, ademásde dilucidar más claramente los márgenes entre los que se puede aumentar la producción anual de energía sin producir diseños demasiado caros.

Haas, Burnham y Mills 1997[32] utilizaron un algoritmo genético multiobjetivo para optimizar la forma, orientación e intensidad del haz de los emisores de rayosX utilizados en la radioterapia dirigida, para destruír los tumores cancerosos altiempo que se evita el tejido sano. (Los fotones de rayos X dirigidos hacia untumor tienden a dispersarse por las estructuras interiores del cuerpo, dañando

inintencionadamente los órganos internos. El reto consiste en minimizar esteefecto mientras se maximiza la dosis de radiación dirigida hacia el tumor).Utilizando un modelo de aptitud basada en rango, los investigadores comenzaroncon la solución producida por el método convencional, un método de mínimoscuadrados iterativo, y luego utilizaron el AG para modificarlo y mejorarlo.Construyendo un modelo del cuerpo humano y exponiéndolo al rayoevolucionado por el AG, encontraron un buen acuerdo entre las distribuciones de



http://www.ascent.com/faq.html















radiación predichas y reales. Los autores concluyen que sus resultados``muestran una protección [de los órganos sanos] que no podía lograrseutilizando las técnicas convencionales'' (p. 1745).

Lee y Zak 2002[44] utilizaron un algoritmo genético para evolucionar un

conjunto de reglas para controlar un sistema de frenos antibloqueoautomovilístico. Aunque la capacidad que tienen los sistemas de frenoantibloqueo de reducir la distancia de frenada y mejorar la maniobrabilidad hasalvado muchas vidas, el rendimiento del ABS depende de las condiciones de lasuperficie de la carretera: por ejemplo, un controlador ABS que esté optimizado para el asfalto seco no funcionará igual de bien en carreteras mojadas o heladas,y viceversa. En este artículo, los autores proponen un AG para ajustar uncontrolador ABS que pueda identificar las propiedades de la superficie de lacarretera (monitorizando el patinaje y aceleración de las ruedas) y pueda actuaren consecuencia, liberando la cantidad adecuada de fuerza de frenado paramaximizar la tracción de las ruedas. En las pruebas, el ABS puesto a puntogenéticamente ̀ èxhibe características de rodada excelentes'' (p. 206) y fue ``muysuperior'' (p. 209) a los otros dos métodos de maniobras de frenado, encontrandocon rapidez nuevos valores óptimos para el patinaje de las ruedas cuando cambiael tipo de terreno bajo un coche en movimiento, y reduciendo la distancia total defrenada. ``La lección que hemos aprendido de nuestro experimento... es que unAG puede ayudar a ajustar incluso un controlador bien diseñado. En nuestrocaso, ya teníamos una buena solución del problema; sin embargo, con la ayudade un AG, conseguimos mejorar significativamente la estrategia de control. Enresumen, parece que merece la pena intentar aplicar un AG incluso en uncontrolador bien diseñado, porque hay muchas probabilidades de que se puedahallar una configuración del controlador mejor utilizando AGs'' (p. 211).

Como cita Schechter 2000[59], el Dr. Peter Senecal, de la Universidad deWisconsin, utilizó algoritmos genéticos de población pequeña para mejorar laeficiencia de los motores diésel. Estos motores funcionan inyectando combustibleen una cámara de combustión que está llena de aire extremadamentecomprimido, y por tanto extremadamente caliente, lo bastante caliente para hacerque el combustible explote y empuje un pistón que produce la fuerza motriz delvehículo. Este diseño básico ha cambiado poco desde que Rudolf Diesel loinventó en 1893; aunque se ha empleado mucho esfuerzo en realizar mejoras, esuna tarea muy difícil de realizar analíticamente, porque requiere un conocimiento preciso del comportamiento turbulento que exhibe la mezcla de combustible yaire, y de la variación simultánea de muchos parámetros independientes. Sinembargo, el método de Senecal prescindía de ese conocimiento específico del problema y, en cambio, funcionaba evolucionando parámetros como la presiónde la cámara de combustión, los tiempos de inyección de combustible y la











cantidad de combustible de cada inyección. El resultado: la simulación produjoun motor mejorado que consumía un 15% menos de combustible que un motordiesel normal y producía dos tercios menos de óxido nítrico de escape y la mitadde hollín. Luego el equipo de Senecal construyó un motor diésel real de acuerdocon las especificaciones de la solución evolucionada, y obtuvieron los mismos

resultados. Ahora Senecal sigue su trabajo evolucionando la geometría del propiomotor, lo que con suerte producirá todavía más mejoras.

Como citan Begley y Beals 1995[9], Texas Instruments utilizó un algoritmogenético para optimizar la disposición de los componentes de un chipinformático, colocando las estructuras de manera que se minimice el área total para crear un chip lo más pequeño posible. Utilizando una estrategia deconexiones que no se le había ocurrido a ningún humano, el AG alcanzó undiseño que ocupaba un 18% menos de espacio.

Finalmente, como cita Ashley 1992[5], empresas de la industria aeroespacial,automovilística, fabril, turbomaquinaria y electrónica están utilizando un sistemade software propietario conocido como Engineous, que utiliza algoritmosgenéticos, para diseñar y mejorar motores, turbinas y otros dispositivosindustriales. En palabras de su creador, el Dr. Siu Shing Tong, Engineous es `ùnmaestro ̀ toqueteador', ensayando incansablemente las puntuaciones deescenarios de tipo ``y-si'' hasta que emerge la mejor solución posible'' (p. 49). Enun ensayo del sistema, Engineous consiguió producir un incremento del 0,92 porciento de la eficiencia de una turbina experimental en sólo una semana, mientrasque diez semanas de trabajo de un diseñador humano sólo produjeron un 0,5 porciento de mejora.

Supuestamente, Engineous no sólo cuenta con algoritmos genéticos; tambiénemplea técnicas de optimización numérica y sistemas expertos que utilizan reglassi-entonces para imitar el proceso de toma de decisiones de un ingeniero humano.Sin embargo, estas técnicas dependen mucho de información específica deldominio, carecen de aplicabilidad general, y son propensas a quedar atrapadas enóptimos locales. En contraste, el uso de algoritmos genéticos permite aEngineous explorar regiones del espacio de búsqueda que pasan por alto los otrosmétodos.

Engineous ha obtenido un amplio uso en una gran variedad de industrias y problemas. El más famoso fue cuando se utilizó para mejorar la turbinageneradora de energía del avión Boeing 777; como informan Begley y Beals1995[9], el diseño optimizado genéticamente era casi un 1% más eficiente encombustible que los motores anteriores, lo que en un campo como éste es unaganancia caída del cielo. Engineous también se ha utilizado para optimizar la














configuración de motores eléctricos industriales, generadores hidroeléctricos yturbinas de vapor, para proyectar redes eléctricas, y para diseñar generadoressuperconductores y generadores de energía nuclear para satélites en órbita. Rao1998[52] informa también de que la NASA ha utilizado Engineous paraoptimizar el diseño de un avión de gran altitud para analizar la disminución del

ozono, que debe ser a la vez ligero y eficiente.

Argumentos creacionistas

Como era de esperar, la demostración real del poder de la evolución querepresentan los AGs ha resultado sorprendente y descorcentante para loscreacionistas, que siempre han afirmado que sólo un diseño inteligente, no lavariación aleatoria y la selección, puede haber producido la cantidad ycomplejidad de información que contienen los seres vivos. Por tanto, han

argumentado que el éxito de los algoritmos genéticos no nos permite deducirnada sobre la evolución biológica. Abordaré las críticas de dos antievolucionistasque representan dos puntos de vista distintos: un creacionista de tipo tierra-joven,el Dr. Don Batten, de `Ànswers in Genesis'', que ha escrito un artículo titulado`Àlgoritmos genéticos - ¿demuestran que la evolución funciona?'', y uncreacionista de tipo tierra-vieja y defensor del diseño inteligente, el Dr. WilliamDembski, cuyo reciente libro ``No Free Lunch'' (Dembski 2002[21]) trata sobreeste tema.

Don Batten

Algunos caracteres de los seres vivos son cualitativos, mientras que los AGs

son siempre cuantitativos

Batten afirma que los AGs deben ser cuantitativos, de manera que se puedaseleccionar cualquier mejora. Esto es cierto. Luego continua diciendo: ̀ `Muchoscaracteres biológicos son cualitativos -o funcionan o no funcionan, así que noexiste una manera de llegar paso a paso de la ausencia de función a la función''.Sin embargo, esta aseveración no ha sido demostrada, y no está apoyada por laevidencia. Batten ni siquiera intenta ofrecer un ejemplo de caracter biológico que`ò funciona o no funciona'', y por tanto no pueda construirse paso a paso.

Pero aunque hubiera ofrecido tal ejemplo de caracter, ¿cómo podría demostrarrazonablemente que no hay un camino paso a paso hasta él? Aunque noconozcamos tal camino, ¿significa eso que no existe ninguno? Por supuesto queno. Batten afirma efectivamente que si no entendemos cómo han evolucionadociertos caracteres, entonces es imposible que esos caracteres hayan evolucionado




http://www.answersingenesis.org/home/area/faq/docs/genetic_algorithm.asp










-un ejemplo clásico de la falacia lógica elemental del argumento de la ignorancia.El espacio de búsqueda de todas las posibles variantes de cualquier caracter biológico dado es enorme, y en la mayoría de los casos nuestro conocimientosupone tan sólo una fracción infinitesimal de todas las posibilidades.Perfectamente pueden existir numerosos caminos hacia una estructura de los que

no conozcamos nada todavía; no hay ninguna razón en absoluto para creer quenuestra ignorancia actual establece límites a nuestro progreso futuro. De hecho,la historia nos da razones para estar seguros de esto: los científicos han hechoenormes progresos para explicar la evolución de muchas estructuras y sistemas biológicos complejos, tanto macroscópicos como microscópicos (por ejemplo,vea estas páginas sobre la evolución de sistemas moleculares complejos, genes``reloj'', la lengua del pájaro carpintero o el escarabajo bombardero). Tenemos justificación para creer probable que los que nos han eludido hasta ahora tambiénse entenderán con claridad en el futuro.

De hecho, los propios AGs nos ofrecen una excelente razón para suponer esto.Muchos de los problemas en los que se han aplicado son problemas complejos deingeniería y diseño de los que no se conocía la solución previamente, y por lotanto el problema no podía `àmañarse'' para facilitar el éxito del algoritmo. Si loscreacionistas tuvieran razón, habría sido completamente razonable esperar quelos algoritmos genéticos hubieran fallado estrepitosamente una y otra vez al seraplicados a estos problemas, pero, en cambio, ha ocurrido justo lo contrario: losAGs han descubierto soluciones poderosas y de gran calidad a problemasdifíciles en una gran variedad de campos. Esto pone seriamente en duda inclusosi existen problemas como los que Batten describe, cuyas soluciones seaninaccesibles a un proceso evolutivo.

Los AGs seleccionan un caracter cada vez, mientras que los seres vivos son

multidimensionales

Batten afirma que, en los AGs, ``se selecciona un caracter individual, mientrasque cualquier ser vivo es multidimensional'', y afirma que en los seres vivos concientos de caracteres, ``la selección tiene que operar con todos los caracteres queafecten a la supervivencia'', mientras que ``[un] AG no funciona con tres o cuatroobjetivos diferentes, o me atrevería a decir que ni siquiera con dos''.

Este argumento revela la profunda ignorancia de Batten sobre la literaturarelevante. Tan sólo un vistazo superficial del trabajo realizado con algoritmosevolutivos (o un vistazo a la sección anterior de este ensayo) habría revelado quelos algoritmos genéticos multiobjetivo son un campo de investigación importantey floreciente dentro del más amplio campo de la computación evolutiva, y lehabría evitado realizar una afirmación tan embarazosamente incorecta. Existen

http://www.talkorigins.org/origins/postmonth/jan04.html#run



http://www.talkorigins.org/origins/postmonth/apr01.html




http://www.talkorigins.org/faqs/woodpecker/woodpecker.html



http://www.talkorigins.org/faqs/bombardier.html









artículos de revista, números enteros de revistas prominentes sobre computaciónevolutiva, conferencias enteras y libros enteros sobre el tema de los AGsmultiobjetivo. Coello 2000[18] proporciona una recopilación muy extensa, concinco páginas de referencias a artículos sobre el uso de algoritmos genéticosmultiobjetivo en una amplio abanico de campos; vea también Fleming y

Purshouse 2002[22]; Hanne 2000[33]; Zitzler y Thiele 1999[65]; Fonseca yFleming 1995[23]; Srinivas y Deb 1994[60]; Goldberg 1989[29], p. 197. Sobre eluso de AGs multiobjetivo para resolver problemas específicos, vea los libros yartículos: Obayashi et al. 2000[49]; Sasaki et al. 2001[57]; Benini y Toffolo2002[10]; Haas, Burnham y Mulls 1997[32]; Chryssolouris y Subramaniam2001[16]; Hughes y Leyland 2000[37]; He y Mort 2000[35]; Kewley yEmbrechts 2002[39]; Beasley, Sonander y Havelock 2001[8]; Sato et al.2002[58]; Tang et al. 1996[62]; Williams, Crossley y Lang 2001[64]; Koza et al.1999[41]; Koza et al. 2003[42]. Vea un repositorio extenso de referencias sobreAGs multiobjetivo en http://www.lania.mx/ccoello/EMOO .

Los AGs no permiten la posibilidad de una extinción o una catástrofe de

errores

Batten afirma que, en los AGs, ``siempre sobrevive algo para mantener el proceso'', mientras que esto no es necesariamente cierto en el mundo real -enresument, los AGs no permiten la posibilidad de una extinción.

Sin embargo, esto no es cierto; la extinción puede ocurrir. Por ejemplo, algunosAGs utilizan un modelo de selección con umbral en el que los individuos deben

tener una aptitud superior a un nivel predeterminado para poder sobrevivir yreproducirse (Haupt y Haupt 1998[34], p. 37). Si no hay ningún individuo quecumpla este criterio en este tipo de AG, la población puede extinguirseefectivamente. Pero incluso en AGs que no establecen umbrales pueden ocurrirestados análogos a la extinción. Si las tasas de mutación son demasiado altas olas presiones selectivas demasiado fuertes, un AG nunca encontrará una soluciónfactible. La población puede acabar en un caos sin remedio al verse afectados loscantidatos aptos por el hecho de que las mutaciones perjudiciales se desarrollencon más rapidez de la que la selección puede eliminarlas (catástrofe de errores), o puede retorcerse inútilmente, incapaz de conseguir ningún aumento de la aptitudlo bastante grande para que pueda ser seleccionado. Al igual que en la naturaleza,debe haber un equilibrio o nunca se alcanzará una solución. La ventaja que tieneun programador a este respecto es que, si ocurre esto, él puede introducirle al programa valores diferentes -para el tamaño de la población, para la tasa demutación, para la presión selectiva- y comenzar de nuevo. Obviamente, esto noes una opción para los seres vivos. Batten dice que ``no existe una regla en laevolución que diga que algunos organismos de la población que evoluciona





























































http://www.lania.mx/ccoello/EMOO































permanecerán viables ocurran las mutaciones que ocurran'', pero tampoco existeuna regla así en los algoritmos genéticos.

Batten también afirma que ̀ `los AGs que he observado preservan artificialmentea los mejores de la generación anterior y los protegen de las mutaciones o la

recombinación, en caso de que no se produzca algo mejor en la siguientegeneración''. Abordaré esta crítica en el siguiente punto.

Los AGs ignoran el coste de las sustituciones

La siguiente afirmación de Batten es que los AGs ignoran el ``dilema deHaldane'', que dice que un alelo que contribuya menos a la aptitud de unorganismo tardará correspondientemente más tiempo en fijarse en la población.Obviamente, a lo que se refiere es a la técnica de selección elitista, queselecciona automáticamente al mejor candidato de cada generación sin importar

lo pequeña que sea su ventaja sobre sus competidores. Tiene razón al sugerir que,en la naturaleza, las ventajas competitivas muy pequeñas pueden tardar en propagarse mucho más. Los algoritmos genéticos no son un modelo exacto de laevolución biológica a este respecto.

Sin embargo, esto no viene al caso. La selección elitista es una idealización de laevolución biológica -un modelo de lo que pasaría en la naturaleza si de vez encuando no interviniese el azar. Como reconoce Batten, el dilema de Haldane noafirma que una mutación ligeramente ventajosa nunca quedará fijada en una población; afirma que tardará más en hacerlo. Sin embargo, cuando el tiempo de

computación está muy demandado o cuando un investigador de AGs deseaobtener una solución con mayor rapidez, puede ser deseable saltarse este procesoimplementando el elitismo. Un punto importante es que el elitismo no afecta aqué mutaciones surgen, sólo asegura la selección de las mejores que surjan. Noimportaría lo fuerte que fuera la selección si no ocurrieran mutaciones queincrementasen la información. En otras palabras, el elitismo acelera laconvergencia una vez que se ha descubierto una solución buena -no provoca unresultado que no habría ocurrido de otra manera. Por lo tanto, si los algoritmosgenéticos con elitismo pueden producir información nueva, entonces también lo puede hacer la evolución en la naturaleza.

Además, no todos los AGs utilizan selección elitista. Muchos no lo hacen, y encambio dependen sólo de selección por ruleta de rueda y otras técnicas demuestreo estocásticas, con no menor éxito. Por ejemplo, Koza et al 2003[42], p.8-9, proporciona ejemplos de 36 casos en los que la programación genética ha producido resultados competitivos con los de los humanos, incluyendo larecreación automática de 21 inventos patentados con anterioridad (seis de los

http://www.talkorigins.org/indexcc/CB/CB121.html












cuales fueron patentados durante o después de 2000), 10 de los cuales duplican lafuncionalidad de la patente de manera diferente, e incluyendo además dos nuevosinventos patentables y cinco algoritmos nuevos que superan a cualquieralgoritmo humano escrito para el mismo propósito. Como declara el Dr. Koza enuna referencia anterior al mismo trabajo (1999[41], p. 1.070): ``No se utiliza la

estrategia elitista''. Algunos artículos más citados en este ensayo, en los que no seutiliza el elitismo: Robin et al. 2003[54]; Rizki, Zmuda y Tamburino 2002[53];Chryssolouris y Subramaniam 2001[16]; Burke y Newall 1999[11]; Glen y Payne1995[28]; Au, Chan y Yao 2003[7]; Jensen 2003[38]; Kewley y Embrechts2002[39]; Williams, Crossley y Lang 2001[64]; Mahfoud y Mani 1996[46]. Entodos estos casos, sin ningún mecanismo para asegurar que se seleccionaban losmejores individuos de cada generación, sin eximir a estos individuos del potencial cambio aleatorio perjudicial, los algoritmos genéticos siguen produciendo resultados poderosos, eficientes y competitivos con los resultadoshumanos. Este hecho puede ser sorprendente para creacionistas como Batten, pero es algo completamente esperado para los defensores de la evolución.

Los AGs ignoran las limitaciones temporales para una generación

Esta crítica es confusa. Batten afirma que una generación puede durarmicrosegundos en un AG, mientras que en los seres vivos una generación puededurar desde minutos hasta años. Esto es cierto, pero no explica cómo influye estoen la validez de los AGs como evidencia para la evolución. Si un AG puedegenerar información nueva, tarde el tiempo que tarde, entonces la evoluciónnatural puede hacer lo mismo sin duda; que los AGs pueden efectivamentehacerlo es todo lo que trata de demostrar este ensayo. La única cuestión restantesería entonces si la evolución biológica ha tenido realmente el tiempo necesario para causar un cambio significativo, y la respuesta a esta cuestión está a cargo delos biólogos, geólogos y físicos, no de los programadores informáticos.

Sin embargo, la respuesta que han proporcionado estos científicos está encompleto acuerdo con las escalas de tiempo evolutivas. Numerosas líneasindependientes de evidencia, incluyendo la datación isocrónica radiométrica, los ritmos de enfriamiento de las enanas blancas, la no existencia en la naturalezade isótopos con tiempos cortos de semideintegración, los ritmos de alejamientode las galaxias lejanas, y el análisis de la radiación cósmica de fondo, convergenhacia la misma conclusión: una Tierra y un universo con muchos miles demillones de años, sin duda tiempo suficiente para que la evolución haya producido toda la diversidad de vida que observamos hoy para todas lasestimaciones razonables.

































http://www.talkorigins.org/faqs/faq-age-of-earth.html#howold



http://hubblesite.org/newscenter/newsdesk/archive/releases/2002/10



http://www.talkorigins.org/faqs/hovind/howgood-yea.html#proof6




http://www.nature.com/nsu/010607/010607-8.html




http://www.gsfc.nasa.gov/topstory/2003/0206mapresults.html























Las altas tasas de mutación y reproducción que emplean los AGs no son

realistas

Batten afirma, sin proporcionar ninguna evidencia o referencia que le apoye, quelos AGs ``producen comúnmente cientos o miles de `descendientes' por

generación'', un ritmo que ni siquiera las bacterias, los organismos biológicos quese reproducen con mayor velocidad, pueden igualar.

Esta crítica erra el tiro de varias maneras. Primero, si la métrica que se utiliza es(como debería ser) el número de descendientes por generación, en lugar delnúmero de descendientes por unidad de tiempo absoluto, entonces existenevidentemente organismos biológicos que pueden reproducirse a ritmos mayoresque los de las bacterias y que casi igualan los ritmos que Batten considera norealistas. Por ejemplo, una sola rana puede poner miles de huevos de una vez,cada uno de los cuales tiene el potencial de desarrollarse como adulto. De

acuerdo, la mayoría de éstos normalmente no sobrevivirán debido a laslimitaciones de recursos y a la depredación, pero entonces la mayoría de la``descendencia'' de cada generación en un AG tampoco sobrevivirá.

Segundo, y más importante: un algoritmo genético trabajando para resolver un problema no pretende representar a un solo organismo. En cambio, un algoritmogenético es más análogo a una población completa de organismos -después detodo, son las poblaciones, y no los individuos, los que evolucionan. Por supuesto,es completamente plausible que una población tenga colectivamente cientos omiles de descendientes por generación. (El creacionista Walter ReMine comete

este mismo error con respecto al programa ``weasel'' del Dr. Richard Dawkins.Vea este Mensaje del Mes para más información).

Además, dice Batten, la tasa de mutación es artificialmente alta en los AGs,mientras que los seres vivos tienen una maquinaria de comprobación de erroresdiseñada para limitar la tasa de mutación en aproximadamente 1 por cada 10.000millones de par de bases (aunque esto es demasiado poco -la cifra real está máscerca de 1 por cada 1.000 millones. Ver Dawkins 1996[20], p. 124). Porsupuesto, esto es cierto. Si los AGs mutasen a este ritmo, tardarían muchísimo enresolver problemas reales. Evidentemente, lo que debe considerarse relevante esla tasa de mutación relativa al tamaño del genoma. La tasa de mutación debe serlo bastante alta para promover una cantidad suficiente de diversidad en la población sin acabar con los individuos. Un ser humano corriente posee entre unay cinco mutaciones; esto es perfectamente realista para la descendencia de unAG.

Los AGs tienen genomas artificialmente pequeños

http://talkorigins.org/origins/postmonth/sep99.html









El argumento de Batten de que el genoma de un algoritmo genético `èsartificialmente pequeño y sólo realiza una cosa'' está completamente errado. En primer lugar, como ya hemos visto, no es cierto que un AG sólo realice una cosa;hay muchos ejemplos de algoritmos genéticos diseñados específicamente paraoptimizar muchos parámetros simultáneamente, a menudo muchos más

parámetros de los que podría manejar un diseñador humano.

¿Y exactamente cómo cuantifica Batten lo de `àrtificialmente pequeño''?Muchos algoritmos evolutivos, como el programa genético de John Koza,utilizan codificaciones de tamaño variable donde el tamaño de las solucionescandidatas pueden crecer arbitrariamente. Batten afirma que hasta los seres vivosmás sencillos tienen mucha más información en su genoma que la que un AGhaya producido nunca, pero si los organismos vivos actuales tienen genomasrelativamente grandes es porque se ha ganado mucha complejidad en el curso delos miles de años de evolución. Como señala el artículo Probabilidad deabiogénesis, hay buenas razones para creer que los primeros organismos vivoseran mucho más sencillos que cualquier especie actual -las moléculasautorreplicadoras probablemente no tenían más de 30 o 40 subunidades, pudiendo quedar especificadas perfectamente con los 1.800 bits de informaciónque Batten reconoce que ha generado al menos un AG. Asimismo, los algoritmosgenéticos son una técnica muy nueva cuyo potencial completo todavía no ha sidoexplotado; las propias computadoras digitales sólo tienen unas pocas décadas, ycomo señala Koza (2003[42], p. 25), las técnicas de computación evolutiva hangenerado resultados cada vez más sustanciales y complejos durante los últimos15 años, en sincronía con el rápido aumento de la potencia computacional, amenudo referida como la ``ley de Moore''. Al igual que la vida primigenia eramuy sencilla comparada con la que vino después, es probable que los algoritmosgenéticos actuales, a pesar de los impresionantes resultados que ya han producido, den origen a resultados mucho más importantes en el futuro.

Los AGs ignoran la posibilidad de que ocurran mutaciones por todo el

genoma

Aparentemente, Batten no comprende cómo funcionan los algoritmos genéticos,y lo demuestra realizando este argumento. Afirma que, en la vida real, ``lasmutaciones ocurren por todo el genoma, no sólo en un gen o sección queespecifique un caracter dado''. Esto es cierto, pero cuando dice que lo mismo noes cierto para los AGs, se equivoca. Exactamente igual que en los seres vivos, losAGs deben escardar los genes perjudiciales al tiempo que seleccionan los beneficiosos.

http://www.talkorigins.org/faqs/abioprob/abioprob.html







http://en.wikipedia.org/wiki/Moore's_law









Batten continua afirmando que `èl propio programa está protegido contra lasmutaciones, sólo las secuencias objetivo mutan'', y si el programa mutara, fallaría poco después. Esta crítica, sin embargo, es irrelevante. No existe razón para queel programa que gobierna a un AG tenga que mutar. El programa no es parte delalgoritmo genético; el programa es el que supervisa al algoritmo genético y

produce las mutaciones en las soluciones candidatas, que son lo que el programador busca mejorar. El programa que ejecuta al AG no es análogo a lamaquinaria reproductiva de un organismo, una comparación que trata deestablecer Batten. En cambio, es análogo a las leyes naturales invariantes quegobiernan los entornos en los que viven y se reproducen los seres vivos, y no seespera que éstas cambien ni necesitan ̀ `protegerse'' de ello.

Los AGs ignoran los problemas de la complejidad irreducible

Utilizando el argumento de la ``'' del creacionista de tipo tierra-vieja Michael

Behe, Batten argumenta: ̀ `Muchos caracteres biológicos requieren la presenciade muchos componentes distintos, funcionando juntos, para que el caracter puedaexistir'', mientras que esto no ocurre en los AGs.

Sin embargo, es trivial demostrar que esta afirmación es falsa, ya que losalgoritmos genéticos han producido sistemas irreduciblemente complejos. Porejemplo, el circuito reconocedor de voz que evolucionó el Dr. Adrian Thompson(Davidson 1997[19]) está compuesto de 37 puertas lógicas. Cinco de ellas nisiquiera están conectadas al resto del circuito, aunque hacen falta las 37 para queel circuito funcione; si cualquiera de ellas se desconecta de la fuente de

alimentación, todo el sistema deja de funcionar. Esto se ajusta a la definición desistema complejo irreducible de Behe, y demuestra que un proceso evolutivo puede producir cosas así.

Debe señalarse que este argumento es el mismo que el primero, simplemente presentado en un lenguaje distinto, y por tanto la refuntación es la misma. Lacomplejidad irreducible no es un problema para la evolución, esté la evoluciónocurriendo en los seres vivos de la naturaleza o en el silicio del procesador deuna computadora.

Los AGs ignoran la poligenia, la pleiotropía y otras complejidades genéticas

Batten argumenta que los AGs ignoran asuntos como la poligenia (ladeterminación de un caracter por múltiples genes), pleiotropía (un gen que afectea múltiples caracteres) y los genes dominantes y recesivos.

http://talkorigins.org/faqs/behe.html






















Sin embargo, ninguna de estas afirmaciones es cierta. Los AGs no ignoran la poligenia y la pleiotropía: simplemente se permite que estas propiedades surjande manera natural en lugar de programarlas deliberadamente. Es obvio que encualquier sistema complejo interdependiente (es decir, un sistema no lineal), laalteración o eliminación de una parte causará una reacción en cadena por todo el

sistema; por tanto, los AGs incorporan de manera natural la poligenia y la pleiotropía. `Èn la literatura sobre algoritmos genéticos, la interacción entre parámetros se conoce como epistasis (un término biológico para la interacciónentre genes). Cuando hay poca o ninguna epistasis, los algoritmos de búsquedamínima [es decir, los trepacolinas **-A.M.] rinden mejor. Los algoritmosgenéticos brillan cuando la epistasis es media o alta...'' (Haupt y Haupt 1998[34], p. 31, itálicas originales).

Igualmente, hay algunas implementaciones de algoritmos genéticos que sí tienencromosomas diploides y genes dominantes y recesivos (Goldberg 1989[29], p.150; Mitchell 1996[47], p. 22). Sin embargo, los que no lo son simplemente se parecen más a los organismos haploides, como las bacterias, que a losorganismos diploides, como los seres humanos. Ya que las bacterias están entrelos organismos más exitosos de este planeta (para ciertas medidas), tales AGssiguen siendo un buen modelo de la evolución.

Los AGs no tienen múltiples sistemas de lectura

Batten habla de la existencia de múltiples sistemas de lectura en los genomas dealgunos seres vivos, en los que las secuencias de ADN codifican distintas

proteínas funcionales cuando se leen en direcciones distintas o con distintosdesplazamientos de inicio. Afirma que ``crear un AG para generar unacodificación con información densa así parecería imposible''.

Un reto así pide una respuesta, y aquí está: Soule y Ball 2001[61]. En esteartículo, los autores presentan un algoritmo genético con múltiples sistemas delectura y codificación densa, permitiéndole almacenar más información que eltamaño total de su genoma. Al igual que los codones de tres nucleótidosespecifican aminoácidos en los genomas de los seres vivos, en este AG loscodones eran cadenas binarias de cinco dígitos (hay por lo tanto 25 o 64 codones posibles, el mismo número de codones en los sistemas biológicos). Como loscodones tenían cinco dígitos de longitud, había cinco sistemas de lectura posibles. La secuencia 11111 sirve como codon de ``comienzo'' y la 00000 comocodon de ``parada''; como el codon de comienzo y parada pueden aparecer encualquier lugar del genoma, la longitud de cada individuo era variable. Lasregiones del cromosoma que no caían entre pares comienzo-parada eranignoradas.



















El AG se probó con cuatro problemas clásicos de maximización de funciones.`Ìnicialmente, la mayoría de los bits no participan en ningún gen, es decir, lamayor parte de un cromosoma no codifica nada. De nuevo, esto es porque en losindividuos iniciales aleatorios hay relativamente pocos pares de codonescomienzo-parada. Sin embargo, el número de bits que no participan disminuye

extremadamente rápido''. Durante el curso de la ejecución, el AG puedeincrementar la longitud efectiva de su genoma introduciendo nuevos codones decomienzo en distintos sistemas de lectura. Al final de la ejecución, ``la cantidadde superposiciones es bastante alta. Muchos bits participan en varios genes (amenudo en los cinco)''. En todos los problemas probados, el AG empezó, demedia, con 5 variables especificadas; al final de la ejecución, ese número sehabía incrementado hasta una media de 25.

En los problemas de prueba, el AG con múltiples sistemas de lectura produjosoluciones significativamente mejores que un AG estándar en dos de los cuatro problemas, y mejores soluciones medias en los otros dos. En uno de los problemas, el AG comprimió con éxito 625 bits de información en uncromosoma de sólo 250 bits de longitud, utilizando sistemas de lecturaalternativos. Los autores tildan este comportamiento de ̀ èxtremadamentesofisticado'' y concluyen que `èstos datos muestran que un AG puede utilizarcon éxito sistemas de lectura a pesar de la complejidad añadida'' y que `ès claroque un AG puede introducir nuevos`genes' mientras sea necesario para resolverun cierto problema, incluso con las dificultades impuestas al utilizar codones decomienzo y parada y genes superpuestos''.

Los AGs tienen objetivos predeterminados

Como muchas otras, esta objeción demuestra que Batten no comprende bien loque es un algoritmo genético y cómo funciona. Argumenta que los AGs, alcontrario que la evolución, tienen objetivos predeterminados y especificadosdesde el principio, y como ejemplo de esto, ofrece el programa ``weasel'' del Dr.Richard Dawkins.

Sin embargo, el programa weasel no es un verdadero algoritmo genético, y norepresenta a los algoritmos genéticos, precisamente por esa razón. No pretendíademostrar el poder de resolución de problemas de la evolución. En cambio, suúnica intención era mostrar la diferencia entre la selección de un solo paso (lainfame frase del ``tornado pasando por una chatarrería y produciendo un 747'') yla selección acumulativa de múltiples pasos. Tenía un objetivo específico predeterminado de antemano. Los algoritmos genéticos verdaderos, en cambio,no lo tienen.



En un sentido más general, los AGs sí tienen un objetivo, a saber, encontrar unasolución aceptable a un problema dado. En este mismo sentido, la evolucióntambién tiene un objetivo: producir organismos que estén mejor adaptados a suentorno y por tanto experimenten un mayor éxito reproductivo. Pero al igual quela evolución es un proceso sin objetivos específicos, los AGs no especifican de

antemano cómo debe resolverse un problema dado. La función de aptitudsolamente se establece para evaluar lo bien que funciona una solución candidata,sin especificar ninguna forma de funcionar particular y sin juzgar de qué manerainventa. La solución en sí emerge luego mediante un proceso de mutación yselección.

La siguiente afirmación de Batten demuestra claramente que no entiende lo quees un algoritmo genético. Afirma que ``quizás si el programador pudiera dar conun programa que permitiera que ocurriera cualquier cosa y luego midiera lacapacidad de supervivencia de los òrganismos', se estaría acercando a lo que sesupone que hace la evolución'' -pero así es exactamente como funcionan losalgoritmos genéticos. Generan aleagoriamente soluciones candidatas y provocanmutaciones aleatorias sobre ellas durante muchas generaciones. No se especificaninguna configuración de antemano; como dice Batten, se permite que ocurracualquier cosa. Como escribe John Koza (2003[42], p. 37), repitiendomisteriosamente las palabras de Batten: ̀ Ùna característica importante... es quela selección [en la programación genética] no es codiciosa. Los individuos que sesabe que son iferiores serán seleccionados hasta un cierto grado. No se garantizaque se seleccionará el mejor individuo de la población. Además, el peorindividuo de la población no será necesariamente excluído. Puede ocurrircualquier cosa y nada está garantizado''. (Una sección anterior trató este puntoconcreto como uno de los puntos fuertes de los AGs). Y, sin embargo, aplicandoun filtro selectivo a estas candidatas mutadas aleatoriamente, surgen solucioneseficientes, complejas y poderosas a problemas difíciles, soluciones que no fuerondiseñadas por ninguna inteligencia y que a menudo pueden igualar o superar a lassoluciones diseñadas por los humanos. La alegre afirmación de Batten de que``por supuesto eso es imposible'' está en contradicción directa con la realidad.

Los AGs no generan información nueva en realidad

La crítica final de Batten dice así: ``Para un AG particular, necesitamos preguntarqué parte de la ìnformación' generada por el programa está en realidadespecificada en el programa, en lugar de haber sido generada de novo''. Acusa alos AGs de que a menudo no hacen más que encontrar la mejor manera de queciertos módulos interaccionen, cuendo los propios módulos y las maneras quetienen de interactuar están especificadas de antemano.






Es difícil saber qué hacer con este argumento. Cualquier problema imaginable -los términos en una ecuación de cálculo, las moléculas en una célula, loscomponentes de un motor, el capital en un mercado financiero- puedenexpresarse en términos de módulos que interactúan de cierta manera. Si todo loque se tiene son módulos sin especificar que interactúan de maneras sin

especificar, no hay problema que resolver. ¿Significa esto que la solución aningún problema requiere la generación de información nueva?

Respecto a la crítica de Batten sobre que la información contenida en la soluciónesté especificada en el problema, la mejora manera de mitigar sus preocupacioneses señalar la cantidad de ejemplos en los que los AGs comienzan con poblacionesiniciales generadas aleatoriamente que no están de ninguna manera diseñadas para ayudar al AG a resolver el problema. Algunos de tales ejemplos son:Graham-Rowe 2004[31]; Davidson 1997[19]; Assion et al. 1998[6]; Giro, Cyrilloy Galvão 2002[27]; Glen y Payne 1995[28]; Chryssolouris y Subramaniam2001[16]; Williams, Crossley y Lang 2001[64]; Robin et al. 2003[54]; Andreou,Georgopoulos y Lokothanassis 2002[4]; Kewley y Embrechts 2002[39]; Rizki,Zmuda y Tamburino 2002[53]; y especialmente Koza et al. 1999[41] y Koza etal. 2003[42], que analiza el uso de programación genética para generar 36inventos competitivos con los humanos de diseños de circuitos analógicos, biología molecular, algoritmia, diseño de controladores industriales y otroscampos, todos comenzando con poblaciones de candidatas iniciales generadasaleatoriamente.

De acuerdo, algunos AGs sí comienzan con soluciones generadasinteligentemente que luego intentan mejorar, pero esto es irrelevante: en esoscasos el objetivo no es sólo devolver la solución de entrada inicial, sino mejorarlamediante la producción de información nueva. En cualquier caso, aunque lasituación inicial sea como la describe Batten, encontrar la manera más eficientemediante la que un cierto número de módulos puede interactuar bajo un conjuntodado de limitaciones puede ser una tarea nada trivial, cuya solución implique unacantidad considerable de información nueva: el diseño de horarios en losaeropuertos internacionales, por ejemplo, o las líneas de montaje de una fábrica,o la distribución de barriles entre almacenes y destilerías. De nuevo, los AGs handemostrado su efectividad a la hora de resolver problemas cuya complejidadabrumaría a cualquier humano. A la luz de las múltiples innovaciones ysoluciones inesperadamente efectivas que ofrecen los AGs en muchos campos, laafirmación de Batten de que ``la cantidad de información nueva generada (por unAG) es normalmente bastante trivial'' suena verdaderamente hueca.

William Dembski























































El reciente libro ``No Free Lunch: Why Specified Complexity Cannot BePurchased Without Intelligence'' (``No dan almuerzos gratis: por qué lacomplejidad específica no puede conseguirse sin inteligencia''), del creacionistade tipo tierra-vieja, el Dr. William Dembski, está dedicado principalmente altema de los algoritmos evolutivos y de cómo se relacionan con la evolución

biológica. En particular, el libro de Dembski trata de una cualidad elusiva que élllama ̀ `complejidad especificada'' que, según afirma él, está presente en granabundancia en los seres vivos, y que además los procesos evolutivos sonincapaces de generar, dejando como única alternativa el ``diseño'' a un``diseñador inteligente'' sin identificar, mediante mecanismos sin especificar.Para apoyar su caso, Dembski apela a un tipo de teoremas matemáticosconocidos como teoremas No Dan Almuerzos Gratis que, según él, demuestranque los algoritmos evolutivos, de media, no lo hacen mejor que una búsquedaciega.

Richard Wein ha escrito una refutación excelente y detallada de Dembski,titulada Not a Free Lunch But a Box of Chocolates (No un almuerzo gratis sinouna caja de chocolates), y no reproduciré sus ideas aquí. En cambio, me centraréen el capítulo 4 del libro de Dembski, que trata en detalle de los algoritmosgenéticos.

Dembski tiene un argumento principal en contra de los AGs, desarrollado afondo a lo largo de este capítulo. Aunque no niega que pueden producirresultados impresionantes -de hecho, dice que hay algo ̀ èxtrañamente persuasivo y casi mágico'' (p. 221) acerca del modo en el que los AGs puedenencontrar soluciones diferentes a cualquier cosa diseñada por seres humanos-,sostiene que su éxito es debido a la complejidad específica ``pasada de tapadillo''dentro de ellos por sus diseñadores humanos y que posteriormente se manifiestaen las soluciones que producen. `Èn otras palabras, toda la complejidadespecífica que obtenemos de un algoritmo evolutivo debe aportarse primero en suconstrucción y en la información que guía al algoritmo. Los algoritmosevolutivos, por tanto, no generan o crean complejidad específica, sino quesimplemente aprovechan la complejidad especificada que ya existe'' (p. 270).

El primer problema evidente en el argumento de Dembski es éste. Aunque sucapítulo sobre algoritmos evolutivos ocupa aproximadamente 50 páginas, las primeras 30 de ellas hablan de nada más que el algoritmo ̀ `weasel'' del Dr.Richard Dawkins, el cual, como ya se ha dicho, no es un verdadero algoritmogenético y no es representativo de los algoritmos genéticos. Los otros dosejemplos de Dembski -las antenas genéticas de alambre doblado de EdwardAltshuler y Derek Linden y las redes neuronales que juegan a las damas deKumar Chellapilla y David Fogel- se introducen tan sólo en las últimas 10

http://www.talkorigins.org/design/faqs/nfl






páginas del capítulo y son tratadas en tres páginas, en combinación. Esto es unaseria deficiencia, considerando que el programa ̀ `weasel'' no es representativo dela mayor parte del trabajo que se hace en el campo de la computación evolutiva;no obstante, analizaré los argumentos de Dembski relacionados con él.

Respecto al programa ̀ `weasel'', Dembski afirma que ̀ `Dawkins y suscompañeros darwinistas utilizan este ejemplo para ilustrar el poder de losalgoritmos evolutivos'' (p. 182) y, de nuevo, ``los darwinistas... están encantadoscon el ejemplo CREO QUE SE PARECE A UNA COMADREJA y lo consideranilustrador del poder de los algoritmos evolutivos para generar complejidadespecífica'' (p. 183). Esto es un hombre de paja, creación de Dembski (¡sobretodo porque el libro de Dawkins fue escrito mucho antes de que Dembskiacuñara ese término!). Esto es lo que Dawkins dice realmente del propósito de su programa:

Lo que importa es la diferencia entre el tiempo que tarda laselección acumulativa, y el tiempo que tardaría la misma computadora,funcionando absolutamente a la misma velocidad, en alcanzar la frase objetivo siestuviera obligada a utilizar el otro procedimiento de selección de un solo paso:más o menos un millón de millones de millones de millones de millones de años''(Dawkins 1996[20], p. 49, itálicas originales).

En otras palabras, el programa ̀ `weasel'' pretendía demostrar la diferencia entredos tipos distintos de selección: la selección de un solo paso, en la que unresultado complejo está producido por puro azar en un solo salto, y la selección

acumulativa, en la que un resultado complejo se construye poco a poco medianteun proceso de filtrado que preserva preferentemente las mejoras. Nunca pretendió ser una simulación de la evolución en su totalidad.

La selección de un solo paso es el proceso absurdamente improbable atacado confrecuencia en la literatura creacionista, comparándolo con un tornado pasando por una chatarrería y produciendo un avión 747, o una explosión en una imprenta produciendo un diccionario. La selección acumulativa es lo que realmente utilizala evolución. Utilizando la selección de un solo paso para alcanzar un resultadofuncional de alguna complejidad significativa, hanría que esperar, de media,

muchas veces la edad actual del universo. Utilizando selección acumulativa, porcontra, se puede alcanzar ese mismo resultado en un periodo de tiempocomparativamente muy corto. El objetivo del programa ̀ `weasel'' de Dawkins erademostrar esta diferencia, y era el único objetivo del programa. En una nota al pie de este capítulo, Dembski escribe: `̀ Es curioso cómo se recicla el ejemplo deDawkins sin ninguna indicación de las dificultades fundamentales que loacompañan'' (p. 230), pero tan sólo los conceptos erróneos de las mentes de los

http://www.datanation.com/fallacies/straw.htm










creacionistas como Dembski y Batten, que atacan al programa ``weasel'' por nodemostrar algo que nunca pretendía demostrar, son los que dan lugar a estas``dificultades''.

A diferencia de todos los ejemplos de algoritmo evolutivo tratados en este

ensayo, el programa ̀ `weasel'' tiene ciertamente un resultado especificado deantemano, y la calidad de las soluciones que genera se juzga comparándolaexplicítamente con ese resultado especificado de antemano. Por tanto, Dembskitiene toda la razón cuando dice que el programa ``weasel'' no genera informaciónnueva. No obstante, luego realiza un salto gigantesco y completamenteinjustificado, al extrapolar esta conclusión a todos los algoritmos evolutivos:``Como única posibilidad que puede alcanzar el algoritmo evolutivo de Dawkins,la secuencia objetivo tiene de hecho una complejidad mínima... Por lo tanto, losalgoritmos evolutivos son incapaces de generar verdadera complejidad'' (p. 182).Hasta Dembski parece reconocer esto cuando escribe: ̀ `...la mayoría de losalgoritmos evolutivos de la literatura están programados para buscar en unespacio de soluciones posibles a un problema hasta que encuentran una respuesta-no, como hace Dawkins, programando explícitamente la respuesta de antemano''(p. 182). Pero luego, habiendo dado una razón perfectamente buena de por qué el programa ``weasel'' no es representativo de los AGs en conjunto, ¡prosigueinexplicablemente realizando esa falaz generalización!

En realidad, el programa ̀ `weasel'' es significativamente distinto de la mayoríade los algoritmos genéticos, y por tanto el argumento por analogía de Dembskino se sostiene. Los verdaderos algoritmos evolutivos, como los ejemplosexaminados en este ensayo, no buscan simplemente un camino hacia solucionesya descubiertas por otros métodos -en cambio, se les presenta un problema parael que no se conoce una solución óptima de antemano, y se les pide quedescubran esa solución por su cuenta. En realidad, si los algoritmos genéticos no pudieran hacer más que redescubrir soluciones ya programadas dentro de ellos,¿qué sentido tendría utilizarlos? Sería un ejercicio de redundancia. Sin embargo,el amplio interés científico (y comercial) por los AGs demuestra que hay muchamás sustancia en ellos que en el ejemplo bastante trivial al que Dembski pretendereducir todo este campo.

Después de colocar y luego derribar este hombre de paja, Dembski avanza haciasu siguiente línea de argumentación: que la complejida específica exhibida porlos resultados de los algoritmos evolutivos más representativos ha sido ``pasadade tapadillo'' por los diseñadores dentro del algoritmo, al igual que en el programa ``weasel''. ``Pero siempre encontramos que cuando parece generarsecomplejidad específica de la nada, en realidad ha sido cargada de antemano, pasada de tapadillo u ocultada a la vista'' (p. 204). Dembski sugiere que el



`èscondite'' más común de la complejidad específica está en la función deaptitud del AG. ``Lo que ha hecho [el algoritmo evolutivo] es aprovecharse de lacomplejidad específica inherente a la función de aptitud y la ha utilizado para buscar y encontrar el objetivo...'' (p. 194). Dembski prosigue argumentando que,antes de que un AE pueda buscar una solución en un paisaje adaptativo dado,

antes debe emplearse algún mecanismo para seleccionar ese paisaje adaptativo deentre lo que él llama un espacio de fases de todos los posibles paisajesadaptativos, y que si ese mecanismo es también evolutivo, antes debe emplearsealgún otro mecanismo para seleccionar su función de aptitud de un espacio defases aún mayor, y así sucesivamente. Dembski concluye que la única manera dedetener esta regresión infinita es mediante la inteligencia, la cual, según el, poseela irreducible y misteriosa habilidad de seleccionar una función de aptitud de unespacio de fases dado sin recurrir a espacios de fases de mayor orden. ``Sóloexiste un generador de complejidad específica conocido, y éste es la inteligencia''(p. 207).

Dembski tiene razón cuando dice que la función de aptitud ``guía a un algoritmoevolutivo hacia el objetivo'' (p. 192). Sin embargo, no tiene razón cuando afirmaque seleccionar la función de aptitud correcta es un proceso que requiera lageneración de más complejidad específica de la que el propio AE produce. Comoescribe Koza (1999[41], p. 39), la función de aptitud le dice a un algoritmoevolutivo ``qué hay que hacer'', no ``cómo hacerlo''. A diferencia del nadarepresentativo programa ̀ `weasel'', normalmente la función de aptitud de un AEno especifica ninguna forma particular que la solución deba adquirir, y por tantono se puede decir que contribuya a la ``complejidad específica'' de la soluciónevolucionada en ningún sentido.

Un ejemplo ilustrará la idea con mayor detalle. Dembski afirma que en elexperimento de las damas de Chellapilla y Fogel, su elección de mantenerconstante el criterio de victoria entre juego y juego `ìnsertó una enorme cantidadde complejidad específica'' (p. 223). Desde luego, es cierto que el producto finalde este proceso exhibía una gran cantidad de complejidad específica (se definacomo se defina ese término). Pero ¿es cierto que la medida de aptitud elegidacontuviese tanta complejidad específica? Esto es lo que dicen realmenteChellapilla y Fogel:

Para apreciar el nivel de juego que se había conseguido, puede ser útil considerarel siguiente experimento mental. Suponga que le piden jugar a un juego en untablero de ocho por ocho casillas con colores alternos. Hay 12 piezas en cadalado ordenadas de una cierta manera antes de empezar el juego. Le dicen lasreglas de movimiento de las piezas (es decir, el movimiento diagonal, comerforzosamente, la promoción) y que se pueden comer piezas. Sin embargo, no le







dicen si comer piezas es favorable o desfavorable (hay una versión de las damasllamada `damas suicidas', en la que el objetivo es `perder' lo más rápidamente posible) o incluso si constituye información relevante. Y lo que es másimportante, no le dicen cuál es el objetivo del juego. Usted simplente realizamovimientos y en algún momento un observador externo declara que el juego ha

acabado. No obstante, no le proporcionan información de si ha ganado, perdido oempatado. Los únicos datos que usted recibe llegan tras un mínimo de cinco partidas y se ofrecen en la forma de una puntuación global. Por tanto, no puedesaber con certeza qué juegos contribuyeron a la puntuación global ni en quégrado. Su reto consiste en inducir los movimientos apropiados en cada partida tansólo a partir de esta burda información'' (Chellapilla y Fogel 2001[13], p. 427).

La afirmación de Dembski de que esta medida de la aptitud insertó una `ènorme''cantidad de complejidad específica excede los límites de lo absurdo. Si se le dierala misma información a un ser humano que nunca hubiera oído hablar de las

damas, y meses después volviéramos para descubrir que se ha convertido en un jugador experto a nivel internacional, ¿podemos concluír que se ha generadocomplejidad específica?

Dembski afirma que para refutar su argumento, ``hace falta demostrar queencontrar la información que guía a un algoritmo evolutivo hacia un objetivo essustancialmente más fácil que encontrar el objetivo directamente mediante una búsqueda ciega'' (p. 204). Sostengo que ése es precisamente el caso.Intuitivamente, no debe sorprender que la función de aptitud contenga menosinformación que la solución evolucionada. Ésta es precisamente la razón por la

que los AGs han hallado un uso tan amplio: es más fácil (requiere menosinformación) escribir una función de aptitud que mida lo buena que es unasolución que diseñar una buena solución desde cero.

En términos más informales, consideremos los dos ejemplos de Dembski, laantena genética de alambre doblado y la red neuronal jugadora de damasevolucionada llamada Anaconda. Obtener una estrategia ganadora requiere unagran cantidad de información detallada sobre el juego de las damas (considere aChinook y su enorme biblioteca de finales de partida). Sin embargo, no hace faltauna información igualmente detallada para reconocer una estrategia así cuando se

la ve: todo lo que necesitamos observar es que esa estrategia venceconsistentemente a sus oponentes. De manera similar, una persona que no supieranada sobre cómo diseñar una antena que radie uniformemente en una regiónhemisférica en un cierto rango de frecuencias, podría sin embargo probar unaantena así y verificar si funciona como se pretende. En ambos casos, determinarlo que constituye una aptitud alta es mucho más fácil (requiere menosinformación) que averiguar cómo conseguir una aptitud alta.







De acuerdo, aunque requiera menos información escoger una función de aptitud para un problema dado que resolver verdaderamente el problema definido por esafunción de aptitud, sí que hace falta algo de información para especificar lafunción de aptitud en primer lugar, y es una cuestión legítima preguntar de dóndeviene esta información inicial. Dembski todavía puede preguntar sobre el origen

de la inteligencia humana que nos permite decidir resolver un problema en lugarde otro, o sobre el origen de las leyes naturales del cosmos que hacen posible quela vida exista y florezca y que ocurra la evolución. Éstas son preguntas válidas, yDembski tiene derecho a pensar en ellas. Sin embargo, en este punto -aparentemente inadvertido por el propio Dembski- se ha alejado de su argumentoinicial. Ya no está afirmando que la evolución no pueda ocurrir; en cambio,esencialmente está preguntando por qué vivimos en un universo en el que puedeocurrir la evolución. En otras palabras, Dembski no parece darse cuenta de que laconclusión lógica de su argumento es la evolución teísta. Es perfectamentecompatible con un Dios que (como muchos cristianos, incluyendo el biólogoevolutivo Kenneth Miller, creen) utilizó la evolución como su herramientacreativa, y creó el universo para hacer que fuera no sólo probable, sino seguro.

Concluiré aclarando algunos conceptos erróneos menores adicionales del capítulo4 de No Free Lunch. Para empezar, aunque Dembski, al contrario que Batten,está claramente informado acerca del campo de la optimización multiobjetivo,afirma erróneamente que ``hasta que no se consiga alguna forma de univalencia,la optimización no puede comenzar'' (p. 186). El análisis de los algoritmosgenéticos multiobjetivo de este ensayo muestran el error de esta afirmación.Quizá otras técnicas de diseño tengan esta restricción, pero una de las virtudes delos AGs es precisamente que pueden establecer contrapartidas y optimizar variosobjetivos mutuamente exclusivos simultáneamente, y luego un supervisorhumano puede elegir la solución que mejor consiga los resultados esperados delgrupo final de soluciones paretianas. No es necesario ningún método paracombinar múltiples criterios en uno.

Dembski también afirma que los AGs ``parecen menos expertos a la hora deconstruír sistemas integrados que requieran de múltiples partes para realizarfunciones novedosas'' (p. 237). La gran cantidad de ejemplos detallados en esteensayo (en particular, la utilización de John Koza de la programación genética para diseñar circuitos analógicos complejos) demuestran que esta afirmacióntambién es falsa.

Finalmente, Dembski menciona que INFORMS, la organización profesional de lacomunidad de investigación de operaciones, le presta muy poca atención a losAGs, y esto `ès una razón para ser escéptico acerca del alcance y poder generalde esta técnica'' (p. 237). Sin embargo, sólo porque una sociedad científica



particular no esté haciendo un uso generalizado de los AGs no significa que esosusos no sean generalizados en otros sitios o en general, y este ensayo ha procurado demostrar que éste es ciertamente el caso. Las técnicas evolutivas hanhallado una amplia variedad de usos en prácticamente todos los campos de laciencia que merece la pena nombrar, además de muchas empresas del sector

comercial. Aquí hay una lista parcial:

Lockheed Martin (Gibbs 1996[25]) GlaxoSmithKline (Gillet 2002[26]) LBS Capital Management (Naik 1996[48]) First Quadrant (Begley and Beals 1995[9]) Texas Instruments (Begley and Beals 1995[9]) U.S. West (Begley and Beals 1995[9]) John Deere & Co. (Petzinger 1995[50]) Volvo (Rao 1998[52]) Ascent Technology (Wired 2002[1]) Boeing (Ashley 1992[5]) British Petroleum (Lemley 2001[45]) Ford Motor Company (Lemley 2001[45]) Unilever (Lemley 2001[45]) United Distillers and Vintners (Lemley 2001[45])

En contraste, dada la escasez de descubrimientos e investigación científicaestimulados por el diseño inteligente, Dembski no se encuentra en posición dequejarse de la falta de aplicaciones prácticas. El diseño inteligente es unahipótesis vacía, que no nos dice nada más que `àlgún diseñador hizo algo, dealguna manera, en algún momento, para provocar este resultado''. En contraste,este ensayo ha demostrado con suerte que la evolución es una estrategia deresolución de problemas llena de aplicaciones prácticas.

Conclusión

Hasta los creacionistas encuentran imposible negar que la combinación de lamutación y la selección natural puede producir adaptación. No obstante, todavía

siguen intentando justificar su rechazo a la evolución dividiendo el procesoevolutivo en dos categorías -``microevolución'' y ``macroevolución''- y afirmandoque sólo la segunda es controvertida, y que cualquier cambio evolutivo que podemos observar es sólo un ejemplo de la primera.

Veamos. La microevolución y la macroevolución son términos que tienensignificado para los biólogos; se definen, respectivamente, como evolución por

























































debajo del nivel de especies y evolución al nivel de especies o por encima. Perola diferencia crucial entre el modo en el que los creacionistas utilizan estostérminos y el modo en el que lo hacen los científicos es que los científicosreconocen que los dos son fundamentalmente el mismo proceso con los mismosmecanismos, tan sólo operando a diferentes escalas. Sin embargo, los

creacionistas están obligados a postular algún tipo de brecha infranqueable quelos separa, para poder negar que los procesos de cambio y adaptación que vemosen la actualidad puedan extrapolarse para producir toda la diversidad que vemosen el mundo de los seres vivos.

No obstante, los algoritmos genéticos hacen que esta idea sea insostenible, aldemostrar la naturaleza sin junturas del proceso evolutivo. Consideremos, porejemplo, un problema que consista en programar un circuito para que discrimineentre un tono de 1 kilohercio y un tono de 10 kilohercios, y respondarespectivamente con salidas uniformes de 0 y 5 voltios. Digamos que tenemosuna solución candidata que puede discriminar con precisión entre los dos tonos, pero sus salidas no son lo bastante uniformes como se requiere; producen pequeñas ondulaciones en lugar del voltaje constante requerido. Supuestamente,de acuerdo con las ideas creacionistas, cambiar este circuito de su estado presentea la solución perfecta sería ``microevolución'', un cambio pequeño dentro de lascapacidades de la mutación y la selección. Pero, sin duda -argumentaría uncreacionista-, llegar a este mismo estado final desde una ordenación inicialcompletamente aleatoria de componentes sería ̀ `macroevolución'', y estaría másallá del alcance de un proceso evolutivo. Sin embargo, los algoritmos genéticoshan sido capaces de conseguir ambas cosas: evolucionar el sistema a partir deuna ordenación aleatoria hasta la solución casi perfecta y finalmente hasta lasolución perfecta y óptima. No surgió ninguna dificultad o brecha insalvable enningún punto del camino. En ningún momento hizo falta intervención humana para montar un conjunto de componentes irreduciblemente complejo (a pesar delhecho de que el producto final sí contiene tal cosa) o para ``guiar'' al sistemaevolutivo a través de algún pico dificultoso. El circuito evolucionó, sin la ayudade ninguna orientación inteligente, desde un estado completamente aleatorio y nofuncional hasta un estado rigurosamente complejo, eficiente y óptimo. ¿Cómo puede no ser esto una demostración experimental convincente del poder de la

evolución?Se dice que la evolución cultural humana ha reemplazado a la biológica -quenosotros, como especie, hemos llegado a un punto en el que somos capaces decontrolar conscientemente nuestra sociedad, nuestro entorno y hasta nuestrosgenes al nivel suficiente para hacer que el proceso evolutivo sea irrelevante. Sedice que los caprichos culturales de nuestra cambiante sociedad son los quedeterminan la aptitud hoy en día, en lugar de la marcha enormemente lenta, en



comparación, de la mutación genética y la selección natural. En cierto sentido,esto puede ser perfectamente cierto.

Pero en otro sentido, nada podría estar más lejos de la verdad. La evolución es un proceso de resolución de problemas cuyo poder sólo comenzamos a comprender

y explotar; a pesar de esto, ya está funcionando por todas partes, moldeandonuestra tecnología y mejorando nuestras vidas, y, en el futuro, estos usos noharán sino multiplicarse. Sin un conocimiento detallado del proceso evolutivo nohabrían sido posibles ninguno de los incontables avances que le debemos a losalgoritmos genéticos. Aquí hay una lección que deben aprender los que niegan el poder de la evolución y los que niegan que el conocimiento de ella tenga beneficios prácticos. Por increíble que pueda parecer, la evolución funciona.Como lo expresa el poeta Lord Byron: `Ès extraño pero cierto; porque la verdadsiempre es extraña, más extraña que la ficción.''

Bibliografía

1`Àdaptive Learning: Fly the Brainy Skies.'' Wired , vol.10, no.3 (marzo de2002). Disponible en línea.

2Altshuler, Edward y Derek Linden. ``Design of a wire antenna using agenetic algorithm.'' Journal of Electronic Defense, vol.20, no.7, p.50-52(julio de 1997).

3 Andre, David y Astro Teller. `Èvolving team Darwin United.''En RoboCup-98: Robot Soccer World Cup II , Minoru Asada and HiroakiKitano (eds). Lecture Notes in Computer Science, vol.1604, p.346-352.Springer-Verlag, 1999.

Ver también: Willihnganz, Alexis. ̀ `Software that writes software.'' Salon,10 de agosto de 1998. Disponible en línea.

4Andreou, Andreas, Efstratios Georgopoulos y Spiridon Likothanassis.

`Èxchange-rates forecasting: A hybrid algorithm based on geneticallyoptimized adaptive neural networks.'' Computational Economics, vol.20,no.3, p.191-210 (diciembre de 2002).

5Ashley, Steven. ̀ Èngineous explores the design space.'' Mechanical

Engineering , febrero de 1992, p.49-52.6

http://www.wired.com/wired/archive/10.03/everywhere.html?pg=2%22



http://www.salon.com/tech/feature/1999/08/10/genetic_programming







Assion, A., T. Baumert, M. Bergt, T. Brixner, B. Kiefer, V. Seyfried, M.Strehle y G. Gerber. ``Control of chemical reactions by feedback-optimized phase-shaped femtosecond laser pulses.'' Science, vol.282, p.919-922 (30 de octubre de 1998).

7

Au, Wai-Ho, Keith Chan, y Xin Yao. `À novel evolutionary data miningalgorithm with applications to churn prediction.'' IEEE Transactions on

Evolutionary Computation, vol.7, no.6, p.532-545 (diciembre de 2003).8

Beasley, J.E., J. Sonander y P. Havelock. ``Scheduling aircraft landings atLondon Heathrow using a population heuristic.'' Journal of the

Operational Research Society, vol.52, no.5, p.483-493 (mayo de 2001).9

Begley, Sharon y Gregory Beals. ``Software au naturel.'' Newsweek , 8 demayo de 1995, p.70.

10Benini, Ernesto y Andrea Toffolo. `Òptimal design of horizontal-axiswind turbines using blade-element theory and evolutionarycomputation.'' Journal of Solar Energy Engineering , vol.124, no.4, p.357-363 (noviembre de 2002).

11Burke, E.K. y J.P. Newall. `À multistage evolutionary algorithm for thetimetable problem.'' IEEE Transactions on Evolutionary Computation,vol.3, no.1, p.63-74 (abril de 1999).

12 Charbonneau, Paul. ̀ `Genetic algorithms in astronomy andastrophysics.'' The Astrophysical Journal Supplement Series, vol.101, p.309-334 (diciembre de 1995).

13Chellapilla, Kumar y David Fogel. ̀ Èvolving an expert checkers playing program without using human expertise.'' IEEE Transactions on

Evolutionary Computation, vol.5, no.4, p.422-428 (agosto de 2001).Disponible en línea.

14

Chellapilla, Kumar y David Fogel. `Ànaconda defeats Hoyle 6-0: a casestudy competing an evolved checkers program against commerciallyavailable software.'' En Proceedings of the 2000 Congress on Evolutionary

Computation, p.857-863. IEEE Press, 2000. Disponible en línea. 15

Chellapilla, Kumar y David Fogel. ̀ `Verifying Anaconda's expert rating by competing against Chinook: experiments in co-evolving a neural

http://www.natural-selection.com/NSIPublicationsOnline.htm










checkers player.'' Neurocomputing , vol.42, no.1-4, p.69-86 (enero de2002).

16Chryssolouris, George y Velusamy Subramaniam. ``Dynamic schedulingof manufacturing job shops using genetic algorithms.'' Journal of

Intelligent Manufacturing , vol.12, no.3, p.281-293 (junio de 2001).17

Coale, Kristi. ``Darwin in a box.'' Wired News, 14 de julio de 1997.Disponible en línea.

18Coello, Carlos. ̀ Àn updated survey of GA-based multiobjectiveoptimization techniques.'' ACM Computing Surveys, vol.32, no.2, p.109-143 (junio de 2000).

19Davidson, Clive. ̀ `Creatures from primordial silicon.'' New Scientist ,vol.156, no.2.108, p.30-35 (15 de noviembre de 1997). Disponible enlínea.

20Dawkins, Richard. The Blind Watchmaker: Why the Evidence of Evolution

Reveals a Universe Without Design. W.W. Norton, 1996.21

Dembski, William. No Free Lunch: Why Specified Complexity Cannot Be

Purchased Without Intelligence. Rowman & Littlefield, 2002.22

Fleming, Peter y R.C. Purshouse. `Èvolutionary algorithms in controlsystems engineering: a survey.'' Control Engineering Practice, vol.10, p.1.223-1.241 (2002).

23Fonseca, Carlos y Peter Fleming. ̀ Àn overview of evolutionaryalgorithms in multiobjective optimization.'' Evolutionary Computation,vol.3, no.1, p.1-16 (1995).

24Forrest, Stephanie. ̀ `Genetic algorithms: principles of natural selectionapplied to computation.'' Science, vol.261, p.872-878 (1993).

25 Gibbs, W. Wayt. ``Programming with primordial ooze.'' Scientific

American, octubre de 1996, p.48-50.26

Gillet, Valerie. ̀ `Reactant- and product-based approaches to the design ofcombinatorial libraries.'' Journal of Computer-Aided Molecular Design,vol.16, p.371-380 (2002).

http://www.wired.com/news/technology/0,1282,5152,00.html



http://www.newscientist.com/hottopics/ai/primordial.jsp









27Giro, R., M. Cyrillo y D.S. Galvão. ``Designing conducting polymersusing genetic algorithms.'' Chemical Physics Letters, vol.366, no.1-2, p.170-175 (25 de noviembre de 2002).

28

Glen, R.C. y A.W.R. Payne. `À genetic algorithm for the automatedgeneration of molecules within constraints.'' Journal of Computer-Aided

Molecular Design, vol.9, p.181-202 (1995).29

Goldberg, David. Genetic Algorithms in Search, Optimization, and

Machine Learning . Addison-Wesley, 1989.30

Graham-Rowe, Duncan. ̀ `Radio emerges from the electronic soup.'' New

Scientist , vol.175, no.2.358, p.19 (31 de agosto de 2002). Disponible enlínea

Ver también: Bird, Jon y Paul Layzell. ``The evolved radio and itsimplications for modelling the evolution of novel sensors.''En Proceedings of the 2002 Congress on Evolutionary Computation, p.1.836-1.841.

31Graham-Rowe, Duncan. ̀ Èlectronic circuit 'evolves' from liquidcrystals.'' New Scientist , vol.181, no.2.440, p.21 (27 de marzo de 2004).

32

Haas, O.C.L., K.J. Burnham y J.A. Mills. `Òn improving physicalselectivity in the treatment of cancer: A systems modelling andoptimisation approach.'' Control Engineering Practice, vol.5, no.12, p.1.739-1.745 (diciembre de 1997).

33Hanne, Thomas. ̀ `Global multiobjective optimization using evolutionaryalgorithms.'' Journal of Heuristics, vol.6, no.3, p.347-360 (agosto de2000).

34Haupt, Randy y Sue Ellen Haupt. Practical Genetic Algorithms. John

Wiley & Sons, 1998.35He, L. y N. Mort. ``Hybrid genetic algorithms for telecommunicationsnetwork back-up routeing.'' BT Technology Journal, vol.18, no.4, p. 42-50(octubre de 2000).

36

http://www.newscientist.com/news/news.jsp?id=ns99992732








Holland, John. ̀ `Genetic algorithms.'' Scientific American, julio de 1992, p. 66-72.

37Hughes, Evan y Maurice Leyland. ̀ Ùsing multiple genetic algorithms togenerate radar point-scatterer models.'' IEEE Transactions on

Evolutionary Computation, vol.4, no.2, p.147-163 (julio de 2000).38

Jensen, Mikkel. ``Generating robust and flexible job shop schedules usinggenetic algorithms.'' IEEE Transactions on Evolutionary Computation,vol.7, no.3, p.275-288 (junio de 2003).

39Kewley, Robert y Mark Embrechts. ̀ `Computational military tactical planning system.'' IEEE Transactions on Systems, Man and Cybernetics,

Part C - Applications and Reviews, vol.32, no.2, p.161-171 (mayo de2002).

40Kirkpatrick, S., C.D. Gelatt y M.P. Vecchi. ̀ Òptimization by simulatedannealing.'' Science, vol.220, p.671-678 (1983).

41Koza, John, Forest Bennett, David Andre y Martin Keane. Genetic

Programming III: Darwinian Invention and Problem Solving . MorganKaufmann Publishers, 1999.

42Koza, John, Martin Keane, Matthew Streeter, William Mydlowec, Jessen

Yu y Guido Lanza. Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers, 2003.

Ver también: Koza, John, Martin Keane y Matthew Streeter. ̀ Èvolvinginventions.'' Scientific American, febrero de 2003, p. 52-59.

43Keane, A.J. y S.M. Brown. ``The design of a satellite boom with enhancedvibration performance using genetic algorithm techniques.'' En Adaptive

Computing in Engineering Design and Control '96 - Proceedings of the

Second International Conference, I.C. Parmee (ed), p.107-113. University

of Plymouth, 1996.

Ver también: Petit, Charles. ``Touched by nature: Putting evolution towork on the assembly line.'' U.S. News and World Report , vol.125, no.4, p.43-45 (27 de julio de 1998). Disponible en línea.

44

http://www.genetic-programming.com/published/usnwr072798.html






Lee, Yonggon y Stanislaw H. Zak. ``Designing a genetic neural fuzzyantilock-brake-system controller.'' IEEE Transactions on Evolutionary

Computation, vol.6, no.2, p.198-211 (abril de 2002).45

Lemley, Brad. ``Machines that think.'' Discover , enero de 2001, p.75-79.

46Mahfoud, Sam y Ganesh Mani. ̀ `Financial forecasting using geneticalgorithms.'' Applied Artificial Intelligence, vol.10, no.6, p.543-565(1996).

47Mitchell, Melanie. An Introduction to Genetic Algorithms. MIT Press,1996.

48 Naik, Gautam. ``Back to Darwin: In sunlight and cells, science seeksanswers to high-tech puzzles.'' The Wall Street Journal , 16 de enero de1996, p. A1.

49Obayashi, Shigeru, Daisuke Sasaki, Yukihiro Takeguchi, y Naoki Hirose.``Multiobjective evolutionary computation for supersonic wing-shapeoptimization.'' IEEE Transactions on Evolutionary Computation, vol.4,no.2, p.182-187 (julio de 2000).

50Petzinger, Thomas. `Àt Deere they know a mad scientist may be a firm's biggest asset.'' The Wall Street Journal , 14 de julio de 1995, p.B1.

Ver también: `Èvolving business, with a Santa Fe Institute twist.'' SFI

Bulletin, invierno de 1998. Disponible en línea. 51

Porto, Vincent, David Fogel y Lawrence Fogel. ̀ Àlternative neuralnetwork training methods.'' IEEE Expert , vol.10, no.3, p.16-22 (junio de1995).

52Rao, Srikumar. `Èvolution at warp speed.'' Forbes, vol.161, no.1, p.82-83(12 de enero de 1998).

53 Rizki, Mateen, Michael Zmuda y Louis Tamburino. `Èvolving patternrecognition systems.'' IEEE Transactions on Evolutionary Computation,vol.6, no.6, p.594-609 (diciembre de 2002).

54Robin, Franck, Andrea Orzati, Esteban Moreno, Otte Homan, y WernerBachtold. ̀ `Simulation and evolutionary optimization of electron-beam

http://www.santafe.edu/sfi/publications/Bulletins/bulletin-winter98/feature.html






lithography with genetic and simplex-downhill algorithms.'' IEEE

Transactions on Evolutionary Computation, vol.7, no.1, p.69-82 (febrerode 2003).

55Sagan, Carl. Broca's Brain: Reflections on the Romance of Science.

Ballantine, 1979.56

Sambridge, Malcolm y Kerry Gallagher. ̀ Èarthquake hypocenter locationusing genetic algorithms.'' Bulletin of the Seismological Society of

America, vol.83, no.5, p.1.467-1.491 (octubre de 1993).57

Sasaki, Daisuke, Masashi Morikawa, Shigeru Obayashi y Kazuhiro Nakahashi. `Àerodynamic shape optimization of supersonic wings byadaptive range multiobjective genetic algorithms.'' En Evolutionary Multi-

Criterion Optimization: First International Conference, EMO 2001,

Zurich, Switzerland, March 2001: Proceedings, K. Deb, L. Theile, C.Coello, D. Corne y E. Zitler (eds). Notas de la confenrencia en Computer

Science, vol.1993, p.639-652. Springer-Verlag, 2001.58

Sato, S., K. Otori, A. Takizawa, H. Sakai, Y. Ando y H. Kawamura.`Àpplying genetic algorithms to the optimum design of a concerthall.'' Journal of Sound and Vibration, vol.258, no.3, p. 517-526 (2002).

59Schechter, Bruce. ``Putting a Darwinian spin on the diesel engine.'' The

New York Times, 19 de septiembre de 2000, p. F3.Ver también: Patch, Kimberly. ̀ Àlgorithm evolves more efficientengine.'' Technology Research News, junio/julio de 2000. Disponible enlínea.

60Srinivas, N. y Kalyanmoy Deb. ̀ `Multiobjective optimization usingnondominated sorting in genetic algorithms.'' Evolutionary Computation,vol.2, no.3, p.221-248 (otoño de 1994).

61

Soule, Terrence y Amy Ball. `À genetic algorithm with multiple readingframes.'' En GECCO-2001: Proceedings of the Genetic and Evolutionary

Computation Conference, Lee Spector y Eric Goodman (eds). MorganKaufmann, 2001. Disponible en línea.

62

http://www.trnmag.com/Stories/062800/Genetically_Enhanced_Engine_062800.html




http://www.cs.uidaho.edu/tsoule/research/papers.html








Tang, K.S., K.F. Man, S. Kwong y Q. He. ``Genetic algorithms and theirapplications.'' IEEE Signal Processing Magazine, vol.13, no.6, p.22-37(noviembre de 1996).

63Weismann, Dirk, Ulrich Hammel, y Thomas Bäck. ``Robust design of

multilayer optical coatings by means of evolutionary algorithms.'' IEEETransactions on Evolutionary Computation, vol.2, no.4, p.162-167(noviembre de 1998).

64Williams, Edwin, William Crossley y Thomas Lang. ̀ Àverage andmaximum revisit time trade studies for satellite constellations using amultiobjective genetic algorithm.'' Journal of the Astronautical Sciences,vol.49, no.3, p.385-400 (julio-septiembre de 2001).

Ver también: ̀ `Selecting better orbits for satelliteconstellations.'' Spaceflight Now, 18 de octubre de 2001. Disponible enlínea.

``Darwinian selection of satellite orbits for military use.'' Space.com, 16 deoctubre de 2001. Disponible en línea.

65Zitzler, Eckart y Lothar Thiele. ̀ `Multiobjective evolutionary algorithms:a comparative case study and the Strength Pareto approach.'' IEEE

Transactions on Evolutionary Computation, vol.3, no.4, p.257-271

(noviembre de 1999).

About this document ...

Algoritmos genéticos y computación evolutiva

This document was generated using the LaTeX2HTML translator Version 2002-2-1(1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning

Unit, University of Leeds.Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department,Macquarie University, Sydney.

The command line arguments were:latex2html -split 0 -local_icons -up_url http://the-geek.org/docsalgen.tex

http://spaceflightnow.com/



http://spaceflightnow.com/news/n0110/18orbits/




http://space.com/

http://space.com/

http://space.com/

http://www.space.com/news/darwin_satellites_011016.html



http://www.latex2html.org/





http://cbl.leeds.ac.uk/nikos/personal.html



http://www.maths.mq.edu.au/~ross/







http://space.com/






Documents

Algoritmos genéticos y computación evolutiva