algoritmos geneticos

5/13/2018 ALGORITMOS GENETICOS - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-geneticos-55a74dce7598b 1/86

ALGORITMICA III

Algori tmos gené t icos



UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURIMAC

ING.INFORMATICA Y SISTEMAS

ALGORITMOS GENETICOS

2

Índice

ALGORITMOS GENÉTICOS……………………………………………………….4

Métodos de representación…………………………………………………..….5

Métodos de selección…………………………………………………………… ..7

Métodos de cambio……………………………………………………………… ..9

Otras técnicas de resolución de problemas………………………………….10

Redes neuronales………………………………………………………………….11

Ascenso a colina (Hill Climbing)……………………………………………….12

Recocido simulado (simulated annealing)……………………………………13

Una breve historia de los AGs………………………………………………… ..13

¿Cuáles son las ventajas de los AGs?....................................................16

¿Cuáles son las limitaciones de los AGs? …………………………………..22

Algunos ejemplos específicos de AG……………………………………….…28

Acústica………………………………………………………………………… .….28

Ingeniería aeroespacial……………………………………………………………30

Astronomía y astrofísica……………………………………………………….…33






3

Ingeniería eléctrica……………………………………………………….…… .…37

Mercados financieros…………………………………………………………….39

Juegos ………………………………………………………………………………42

Geofísica………………………………………………………………………… .…46

Ingeniería de materiales………………………………………………………… .48

Matemáticas y algoritmia…………………………………………………… ..…50

Ejército y cumplimiento de la ley ………………………………………….….52

Biología molecular………………………………………………………… ..……54

Reconocimiento de patrones y explotación de datos ……………….……56

Diseño de rutas y horarios………………………………………………………61

Ingeniería de sistemas …………………………………………………….……65

Los AGs no tienen múltiples sistemas de lectura………………………….79

Los AGs tienen objetivos predeterminados………………………………….80

Los AGs no generan información nueva en realida………………………82






4

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 para

resolver problemas. Dado un problema específico a resolver, la entrada del AG es

un conjunto de soluciones potenciales a ese problema, codificadas de alguna

manera, y una métrica llamada función de aptitud que permite evaluar

cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones que

ya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelen

generar aleatoriamente.

Luego el AG evalúa cada candidata de acuerdo con la función de aptitud. En un

acervo de candidatas generadas aleatoriamente, por supuesto, la mayoría no

funcionarán en absoluto, y serán eliminadas. Sin embargo, por puro azar, unas

pocas pueden ser prometedoras -pueden mostrar actividad, aunque sólo sea

actividad débil e imperfecta, hacia la solución del problema.

Estas candidatas prometedoras se conservan y se les permite reproducirse. Se

realizan múltiples copias de ellas, pero las copias no son perfectas; se introducen

cambios aleatorios durante el proceso de copia. Luego, esta descendencia digital

prosigue con la siguiente generación, formando un nuevo acervo de soluciones

candidatas, 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 son

eliminadas de nuevo; pero, de nuevo, por puro azar, las variaciones aleatorias

introducidas 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 la

siguiente generación con cambios aleatorios, y el proceso se repite. Las

expectativas son que la aptitud media de la población se incrementará en cada

ronda y, por tanto, repitiendo este proceso cientos o miles de rondas, pueden

descubrirse soluciones muy buenas del problema.






5

Aunque a algunos les puede parecer asombroso y antiintuitivo, los algoritmos

genéticos han demostrado ser una estrategia enormemente poderosa y exitosa

para resolver problemas, demostrando de manera espectacular el poder de losprincipios evolutivos. Se han utilizado algoritmos genéticos en una amplia variedad

de campos para desarrollar soluciones a problemas tan difíciles o más difíciles que

los abordados por los diseñadores humanos. Además, las soluciones que

consiguen son a menudo más eficientes, más elegantes o más complejas que

nada que un ingeniero humano produciría. ¡En algunos casos, los algoritmos

genéticos han producido soluciones que dejan perplejos a los programadores que

escribieron los algoritmos en primera instancia!

Métodos de representación

Antes de que un algoritmo genético pueda ponerse a trabajar en un problema, se

necesita un método para codificar las soluciones potenciales del problema de

forma que una computadora pueda procesarlas. Un enfoque común es codificar

las soluciones como cadenas binarias: secuencias de 1s y 0s, donde el dígito de

cada posición representa el valor de algún aspecto de la solución. Otro método

similar consiste en codificar las soluciones como cadenas de enteros o números

decimales, donde cada posición, de nuevo, representa algún aspecto particular de

la solución. Este método permite una mayor precisión y complejidad que el método

comparativamente restringido de utilizar sólo números binarios, y a menudo ``está

intuitivamente más cerca del espacio de problemas'' .

Esta técnica se utilizó, por ejemplo, en el trabajo de Steffen Schulze-Kremer, que

escribió un algoritmo genético para predecir la estructura tridimensional de unaproteína, basándose en la secuencia de aminoácidos que la componen . El AG de

Schulze-Kremer utilizaba números reales para representar 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 de una cadena. Una vez que






6

todos los aminoácidos están enlazados, la proteína se dobla formando una

compleja estructura tridimensional, basada en cuáles aminoácidos se atraen entre

ellos y cuáles se repelen. La forma de una proteína determina su función). Losalgoritmos genéticos para entrenar a las redes neuronales también utilizan a

menudo este método de codificación.

Un tercer método consiste en representar a los individuos de un AG como

cadenas de letras, donde cada letra, de nuevo, representa un aspecto específico

de la solución. Un ejemplo de esta técnica es el método basado en ``codificación

gramática'' de Hiroaki Kitano, en el que a un AG se le encargó la tarea de

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

La virtud de estos tres métodos es que facilitan la definición de operadores que

causen los cambios aleatorios en las candidatas seleccionadas: cambiar un 0 por

un 1 o viceversa, sumar o restar al valor de un número una cantidad elegida al

azar, 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, y

denominada programación genética, representa a los programas como estructuras

de datos ramificadas llamadas árboles . En este método, los cambios aleatorios

pueden generarse cambiado el operador o alterando el valor de un cierto nodo del

árbol, o sustituyendo un subárbol por otro.






7

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 las

representan de esta manera, pero otros no; por ejemplo, la ``codificación

gramatical'' de Kitano, explicada arriba, puede escalarse eficientemente para crear

redes neuronales grandes y complejas, y los árboles de programación genética de

Koza pueden crecer arbitrariamente tanto como sea necesario para resolver

cualquier problema que se les pida.

Métodos de selección

Un algoritmo genético puede utilizar muchas técnicas diferentes para seleccionar a

los individuos que deben copiarse hacia la siguiente generación, pero abajo se

listan algunos de los más comunes. Algunos de estos métodos son mutuamente

exclusivos, pero otros pueden utilizarse en combinación, algo que se hace a

menudo.

Selección elitista: se garantiza la selección de los miembros más aptos de

cada generación. (La mayoría de los AGs no utilizan elitismo puro, sino que

usan una forma modificada por la que el individuo mejor, o algunos de los






8

mejores, son copiados hacia la siguiente generación en caso de que no

surja nada mejor).

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

Selección por rueda de ruleta: una forma de selección proporcional a la

aptitud 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 -

cada individuo 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

hace girar, y en cada vez se elige al individuo que ``posea'' la sección en la

que se pare la ruleta).

Selección escalada: al incrementarse la aptitud media de la población, la

fuerza 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ás

tarde, cuando todos los individuos tengan una aptitud relativamente alta y

só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 un

individuo de cada subgrupo para la reproducción.

Selección por rango: a cada individuo de la población se le asigna un rango

numérico basado en su aptitud, y la selección se basa en este ranking, en

lugar de las diferencias absolutas en aptitud. La ventaja de este método es

que puede evitar que individuos muy aptos ganen dominancia al principio a

expensas de los menos aptos, lo que reduciría la diversidad genética de lapoblación y podría obstaculizar la búsqueda de una solución aceptable.

Selección generacional: la descendencia de los individuos seleccionados en

cada generación se convierte en toda la siguiente generación. No se

conservan individuos entre las generaciones.






9

Selección por estado estacionario: la descendencia de los individuos

seleccionados en cada generación vuelven al acervo genético preexistente,

reemplazando a algunos de los miembros menos aptos de la siguientegeneración. Se conservan algunos individuos entre generaciones.

Selección jerárquica: los individuos atraviesan múltiples rondas de

selección en cada generación. Las evaluaciones de los primeros niveles

son más rápidas y menos discriminatorias, mientras que los que sobreviven

hasta niveles más altos son evaluados más rigurosamente. La ventaja de

este método es que reduce el tiempo total de cálculo al utilizar una

evaluación más rápida y menos selectiva para eliminar a la mayoría de los

individuos que se muestran poco o nada prometedores, y sometiendo a una

evaluación de aptitud más rigurosa y computacionalmente más costosa só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 ser

alterados aleatoriamente con la esperanza de mejorar su aptitud para la siguiente

generació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 vivos

cambia 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 los

cromosomas durante la reproducción sexual. Las formas comunes de cruzamiento

incluyen al cruzamiento de un punto, en el que se establece un punto de

intercambio en un lugar aleatorio del genoma de los dos individuos, y uno de los






10

individuos contribuye todo su código anterior a ese punto y el otro individuo

contribuye todo su código a partir de ese punto para producir una descendencia, y

al 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

dos operadores genéticos en los individuos de una población de cadenas de 8

bits. El diagrama superior 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 un nuevo 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 su

genoma 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 los

mé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. Esta

sección explica algunas de estas técnicas, en qué se parecen a los AGs y en qué

se diferencian.






11

Redes neuronales

Una red neuronal es un método de resolución de problemas basado en un modelo

informá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 o más capas ocultas enmedio. Se le presenta un patrón inicial de entrada a la

capa de entrada, y luego los nodos que se estimulan transmiten una señal a los

nodos de la siguiente capa a la que están conectados. Si la suma de todas las

entradas que entran en una de estas neuronas virtuales es mayor que el famosoumbral de activación de la neurona, esa neurona se activa, y transmite su propia

señal a las neuronas de la siguiente capa. El patrón de activación, por tanto, se

propaga hacia delante hasta que alcanza a la capa de salida, donde es devuelto

como solución a la 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 del tiempo, mediante la repetición de rondas en las que se ajustan sus

umbrales, hasta que la salida real coincide con la salida deseada para cualquierentrada dada. Este proceso puede ser supervisado por un experimentador

humano, o puede correr automáticamente utilizando un algoritmo de aprendizaje

.Se han utilizado algoritmos genéticos para construir y entrenar a redes

neuronales.






12

Figure: Una sencilla red neuronal anticipativa (feedforward), con una capa

consistente en cuatro neuronas, una capa oculta consistente en tres neuronas y

una capa de salida consistente en cuatro neuronas. El número de cada neuronarepresenta su umbral de activación: sólo se excitará si recibe al menos esa

cantidad de entradas. El diagrama muestra 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 menos aleatorios.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, se conserva

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 se devuelve

como . (Para entender de dónde viene 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. Un conjunto de coordenadas en ese paisaje

representa una solución particular. Las soluciones 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, un algoritmo que comienza en un punto

dado del paisaje y se mueve inexorablemente colina arriba). El algoritmo de

ascenso a colina es lo que se conoce como algoritmo voraz, lo que significa que

siempre hace la mejor elecció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 los algoritmos genéticos y el recocido simulado, discutido abajo, no

son voraces; a veces, estos métodos hacen elecciones menos óptimas al principio

con la esperanza de que conducirán hacia una solución mejor más adelante.






13

Recocido simulado (simulated annealing)

Otra técnica de optimización similar a los algoritmos evolutivos se conoce como

recocido simulado. La idea toma prestado su nombre del proceso industrial en el

que un material se calienta por encima de su punto de fusión y luego se enfría

gradualmente para eliminar defectos en su estructura cristalina, produciendo un

entramado de átomos más estable y regular .En el recocido simulado, como en los

algoritmos genéticos, existe una función de aptitud que define un paisaje

adaptativo; sin embargo, en lugar de una población de candidatas como en los

AGs, sólo existe una solución candidata. El recocido simulado también añade el

concepto de ``temperatura'', una cantidad numérica global que disminuyegradualmente en el tiempo. En cada paso del algoritmo, la solució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 la aptitud de la solución

anterior; si es mayor, se conserva la nueva solución. En caso contrario, el

algoritmo toma la decisión de conservarla o descartarla en base a la temperatura.

Si la temperatura es alta, como lo es al principio, pueden conservarse incluso

cambios que causan decrementos significativos en la aptitud, y utilizarse comobase para la siguiente ronda del algoritmo, pero al ir disminuyendo la temperatura,

el algoritmo se va haciendo más y más propenso a aceptar sólo los cambios que

aumentan la aptitud. Finalmente, la temperatura alzanca el cero y el sistema se

``congela''; cualquiera que sea la configuración que 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ón física de los componentes en

un chip .

Una breve historia de los AGs

Los primeros ejemplos de lo que hoy podríamos llamar algoritmos genéticos

aparecieron a finales de los 50 y principios de los 60, programados en

computadoras por biólogos evolutivos que buscaban explícitamente realizar






14

modelos de aspectos de la evolución natural. A ninguno de ellos se le ocurrió que

esta estrategia podría aplicarse de manera más general a los problemas

artificiales, pero ese reconocimiento no tardaría en llegar: ``La computaciónevolutiva estaba definitivamente en el aire en los días formativos de la

computadora electrónica'' . En 1962, investigadores como G.E.P. Box, G.J.

Friedman, W.W. Bledsoe y H.J. Bremermann habían desarrollado

independientemente algoritmos inspirados en la evolución para optimización de

funciones y aprendizaje automático, pero sus trabajos generaron poca reacción.

En 1965 surgió un desarrollo más exitoso, cuando Ingo Rechenberg, 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 los algoritmos

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

posteriores introdujeron la idea de población. Las estrategias 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 igual

que en la estrategia evolutiva de Rechenberg, su algoritmo funcionaba mutando

aleatoriamente una de estas máquinas simuladas y conservando la mejor de las

dos . También al igual que las estrategias evolutivas, hoy en día existe una

formulación más amplia de la té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 el reconocimiento de la importancia del cruzamiento.

En una fecha tan temprana como 1962, el trabajo de John Holland sobre sistemas

adaptativos estableció las bases para desarrollos posteriores; y lo que es más

importante, Holland fue también el primero en proponer explícitamente el






15

cruzamiento y otros operadores de recombinación. Sin embargo, el trabajo

fundamental en el campo de los algoritmos genéticos apareció en 1975, con la

publicación del libro ``Adaptación en Sistemas Naturales y Artificiales''. Basado eninvestigaciones y papers anteriores del propio Holland y de colegas de la

Universidad de Michigan, este libro fue el primero en presentar sistemática y

rigurosamente el concepto de sistemas digitales adaptativos utilizando la

mutació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 el concepto de

esquema .Ese mismo año, la importante tesis de Kenneth De Jong estableció el

potencial de los AGs demostrando que podían desenvolverse bien en una gran

variedad de funciones de prueba, incluyendo paisajes de búsqueda ruidosos,

discontinuos y multimodales .

Estos trabajos fundacionales establecieron un interés más generalizado en la

computación evolutiva. Entre principios y mediados de los 80, los algoritmos

genéticos se estaban aplicando en una amplia variedad de áreas, desde

problemas matemáticos abstractos como el ``problema de la mochila'' (bin-packing) y la coloración de grafos hasta asuntos tangibles de ingeniería como el

control de flujo en una línea de ensamble, reconocimiento y clasificación de

patrones y optimización estructural.

Al principio, estas aplicaciones eran principalmente teóricas. Sin embargo, al

seguir proliferando la investigación, los algoritmos genéticos migraron hacia el

sector 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''

en áreas de estudio tan diversas como la predicción en la bolsa y la planificación

de la cartera de valores, ingeniería aeroespacial, diseño de microchips, bioquímica






16

y biología molecular, y diseño de horarios en aeropuertos y líneas de montaje. La

potencia de la evolución ha tocado virtualmente cualquier campo que uno pueda

nombrar, modelando invisiblemente el mundo que nos rodea de incontablesmaneras, y siguen descubriéndose nuevos usos mientras la investigación sigue su

curso. Y en el 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, es una técnica de resolución de problemas de inmenso poder y de

aplicación casi ilimitada.

¿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 serie

y sólo pueden explorar el espacio de soluciones hacia una solución en una

dirección al mismo tiempo, y si la solución que descubren resulta

subóptima, no se puede hacer otra cosa que abandonar todo el trabajo

hecho y empezar de nuevo. Sin embargo, ya que los AGs tienen

descendencia múltiple, pueden explorar el espacio de soluciones en

mú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 de

encontrar la solución.

Sin embargo, la ventaja del paralelismo va más allá de esto. Considere lo

siguiente: todas las cadenas binarias (cadenas de ceros y unos) de 8

dígitos forman un espacio de búsqueda, que puede representarse como******** (donde * significa ``o 0 o 1''). La cadena 01101010 es un miembro

de este espacio. Sin embargo, también es un miembro del espacio 0*******,

del espacio 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






17

pertenece. Tras muchas evaluaciones, iría obteniendo un valor cada vez

más preciso de la aptitud media de cada uno de estos espacios, cada uno

de los cuales contiene muchos miembros. Por tanto, un AG que evalúeexplícitamente un número pequeño de individuos está evaluando

implícitamente un grupo de individuos mucho más grande -de la misma

manera que un encuestador que le hace preguntas a un cierto miembro de

un grupo étnico, religioso o social espera aprender algo acerca de las

opiniones de todos los miembros de ese grupo, y por tanto puede predecir

con fiabilidad la opinión nacional sondeando sólo un pequeño porcentaje de

la población. De la misma manera, el AG puede dirigirse hacia el espacio

con los individuos más aptos y encontrar el mejor de ese grupo. En el

contexto de los algoritmos evolutivos, esto se conoce como teorema del

esquema, y es la ventaja principal de los AGs sobre otros métodos de

resolución de problemas

Debido al paralelismo que les permite evaluar implícitamente muchos

esquemas a la vez, los algoritmos genéticos funcionan particularmente bien

resolviendo problemas cuyo espacio de soluciones potenciales es

realmente grande -demasiado vasto para hacer una búsqueda exhaustivaen un tiempo razonable. La mayoría de los problemas que caen en esta

categoría se conocen como ``no lineales''. En un problema lineal, la aptitud

de cada componente es independiente, por lo que cualquier mejora en

alguna parte dará como resultado una mejora en el sistema completo. No

es necesario decir que hay pocos problemas como éste en la vida real. La

no linealidad es la norma, donde cambiar un componente puede tener

efectos en cadena en todo el sistema, y donde cambios múltiples que,individualmente, son perjudiciales, en combinación pueden conducir hacia

mejoras en la aptitud mucho mayores. La no linealidad produce una

explosión combinatoria: el espacio de cadenas binarias de 1.000 dígitos

puede examinarse exhaustivamente evaluando sólo 2.000 posibilidades si

el problema es lineal, mientras que si no es lineal, una búsqueda exhaustiva






18

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 superar

incluso este enorme número de posibilidades, y encontrar con éxito

resultados óptimos o muy buenos en un corto periodo de tiempo, tras

muestrear directamente sólo regiones pequeñas del vasto paisaje

adaptativo Por ejemplo, un algoritmo genético desarrollado en común por

ingenieros de General Electric y el Rensselaer Polytechnic Institute produjo

el diseño de la turbina de un motor a reacción de altas prestaciones que era

tres veces mejor que la configuración diseñada por humanos, y un 50%

mejor que una configuración diseñada por un sistema experto que recorrió

con éxito un espacio de soluciones que contenía más de 10.387

posibilidades. Los métodos convencionales para diseñar estas turbinas son

una parte fundamental de proyectos de ingeniería que pueden durar hasta

cinco años y 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íaOtra ventaja notable de los algoritmos genéticos es que se desenvuelven

bien en problemas con un paisaje adaptativo complejo -aquéllos en los que

la función de aptitud es discontinua, ruidosa, cambia con el tiempo, o tiene

muchos óptimos locales. La mayoría de los problemas prácticos tienen un

espacio de soluciones enorme, imposible de explorar exhaustivamente; el

reto 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 del

espacio de soluciones. Muchos algoritmos de búsqueda pueden quedar

atrapados 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, aunque






19

existan 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 la

realidad, 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. Sin embargo,

aunque un AG no devuelva siempre una solución perfecta y demostrable a

un problema, casi siempre puede devolver al menos una muy buena

solución). Todos los cuatro componentes principales de los AGs -

paralelismo, selección, mutación y cruzamiento- trabajan juntos para

conseguir esto. Al principio, el AG genera una población inicial diversa,

lanzando una ``red'' sobre el paisaje adaptativo. compara esto con un

ejército de paracaidistas cayendo sobre el paisaje del espacio 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 individuo explorar 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 desoluciones

Sin embargo, el cruzamiento es el elemento clave que distingue a los

algoritmos genéticos de los otros métodos como los trepacolinas y el

recocido simulado. Sin el cruzamiento, cada solución individual va por su

cuenta, explorando el espacio de búsqueda en sus inmediaciones sin

referencia de lo que el resto de individuos puedan haber descubierto. Sinembargo, con el cruzamiento en juego, hay una transferencia de

informació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 descendencia

que tenga las virtudes de sus dos padres y ninguna de sus debilidades.






20

donde los autores analizan 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 unabuena topología (componentes como inductores y condensadores

colocados en el sitio correcto) pero malos tamaños (valores demasiado

bajos de inductancia y capacidad para los componentes). El otro padre

tenía mala topología pero buenos tamaños. El resultado de aparearlos

mediante cruzamiento fue una descendencia con la buena topología de un

padre y los 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ón versus

explotación, ``un problema clásico de todos los sistemas que pueden

adaptarse y aprender'' Una vez que un algoritmo (o un diseñador humano)

ha encontrado una estrategia para resolver problemas que parece funcionar

satisfactoriamente, ¿debería centrarse en hacer el mejor uso de esa

estrategia, o buscar otras? Abandonar una estrategia de probada solvenciapara buscar otras nuevas casi garantiza que supondrá una pérdida y

degradación del rendimiento, al menos a corto plazo. Pero si uno se queda

con una estrategia particular excluyendo a todas las demás, corre el riesgo

de no descubrir estrategias mejores que existen pero no se han encontrado.

De nuevo, los algoritmos genéticos han demostrado ser muy buenos en dar

con este equilibrio y descubrir buenas soluciones en un tiempo y esfuerzo

computacional razonables.Otro área en el que destacan los algoritmos genéticos es su habilidad para

manipular muchos parámetros simultáneamente Muchos problemas de la

vida real no pueden definirse en términos de un único valor que hay que

minimizar o maximizar, sino que deben expresarse en términos de múltiples

objetivos, a menudo involucrando contrapartidas: uno sólo puede mejorar a






21

expensas de otro. Los AGs son muy buenos resolviendo estos problemas:

en particular, su uso del paralelismo les permite producir múltiples

soluciones, igualmente buenas, al mismo problema, donde posiblementeuna solución candidata optimiza un parámetro y otra candidata optimiza uno

distinto y luego un supervisor humano puede seleccionar una de esas

candidatas para su utilización. Si una solución particular a un problema con

múltiples objetivos optimiza un parámetro hasta el punto en el que ese

parámetro no puede mejorarse más sin causar una correspondiente pérdida

de calidad en algún otro parámetro, esa solución se llama óptimo paretiano

o no dominada Finalmente, una de las cualidades de los algoritmos

genéticos que, a primera vista, puede parecer un desastre, resulta ser una

de sus ventajas: a saber, 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 hacen los diseñadores humanos, son ``relojeros

ciegos'' realizan cambios aleatorios en sus soluciones candidatas y luego

utilizan la función de aptitud para determinar si esos cambios producen una

mejora.

La virtud de esta técnica es que permite a los algoritmos genéticos

comenzar con una mente abierta, por así decirlo. Como sus decisiones

están basadas en la aleatoriedad, todos los caminos de búsqueda posibles

están abiertos teóricamente a un AG; en contraste, cualquier estrategia de

resolución de problemas que dependa de un conocimiento previo, debe

inevitablemente comenzar descartando muchos caminos a priori, perdiendoasí cualquier solución novedosa que pueda existir. Los AGs, al carecer de

ideas preconcebidas basadas en creencias establecidas sobre ``cómo

deben hacerse las cosas'' o sobre lo que ``de ninguna manera podría

funcionar'', los AGs no tienen este problema. De manera similar, cualquier

técnica que dependa de conocimiento previo fracasará cuando no esté






22

disponible tal conocimiento, pero, de nuevo, los AGs no se ven afectados

negativamente por la ignoranci. Mediante sus componentes de paralelismo,

cruzamiento y mutación, pueden viajar extensamente por el paisajeadaptativo, explorando regiones que algoritmos producidos con inteligencia

podrían no haber tenido en cuenta, y revelando potencialmente soluciones

de asombrosa e inesperada creatividad que podrían no habérseles ocurrido

nunca a los diseñadores humanos. Un ejemplo muy gráfico de esto es el

redescubrimiento, mediante la programación genética, del concepto de

retroalimentación negativa -un principio crucial para muchos componentes

electrónicos importantes de hoy en día, pero un concepto que, cuando fue

descubierto en primera instancia, se le denegó una patente de nueve años

porque el concepto era demasiado contrario a las creencias establecidas .

Por supuesto, los algoritmos evolutivos no están enterados ni preocupados

de si una solució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 como

estrategia de resolución de problemas, no son la panacea. Los AGs tienen ciertas

limitaciones; sin embargo, se demostrará que todas ellas pueden superarse y que

ninguna 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ético

es definir una representación del problema. El lenguaje utilizado para

especificar soluciones candidatas debe ser robusto; es decir, debe sercapaz de tolerar cambios aleatorios que no produzcan constantemente

errores fatales o resultados sin sentido.

Hay dos maneras principales para conseguir esto. La primera, utilizada por

la mayoría de los algoritmos genéticos, es definir a los individuos como






23

listas de números -binarios, enteros o reales- donde cada número

representa algún aspecto de la solución candidata. Si los individuos son

cadenas 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ían

representar muchas cosas distintas: los pesos de las conexiones en una

red neuronal, el orden de las ciudades visitadas en un recorrido dado, la

situación espacial de componentes electrónicos, los valores con los que se

alimenta a un controlador, los ángulos de torsión de los enlaces péptidos de

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 propio

código del programa no cambia; el código es lo que dirige la simulación y

hace 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 de representación'', la PG

representa a los individuos como árboles de código ejecutables que puedenmutar 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 dice en la sección ``Algunos

ejemplos específicos'', ambas han tenido un éxito considerable.

El problema de representar a las soluciones candidatas de manera robusta

no surge en la naturaleza, porque el método de representación utilizado porla evolución, a saber, el código genético, es inherentemente robusto: con

muy pocas excepciones, como una cadena de codones de parada, no

existe una secuencia de bases de ADN que no pueda traducirse en una

proteína. Por lo tanto, virtualmente, cualquier cambio en los genes de un

individuo siempre producirá un resultado inteligible, y por tanto las






24

mutaciones en la evolución tienen mayor probabilidad de producir una

mejora. Esto entra en contraste con los lenguajes creados por el hombre

como el inglés, donde el número de palabras con significado es pequeñocomparado con el número total de formas en las que se pueden combinar

las letras del alfabeto, y por tanto, es probable que un cambio aleatorio en

una frase en inglés produzca un sinsentido.

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

cuidadosamente para que se pueda alcanzar una mayor aptitud y

verdaderamente signifique una solución mejor para el problema dado. Si se

elige mal una función de aptitud o se define de manera inexacta, puede que

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 ``engañ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 que hiciera). Se puede encontrar

un ejemplo de esto en Graham-Rowe 2002 donde unos investigadores

utilizaron un algoritmo evolutivo en conjunción con una serie de chips

reprogramables, haciendo que la función de aptitud recompensara alcircuito en evolución por dar como salida una señal oscilatoria. Al final del

experimento, se producía efectivamente una señal oscilatoria -pero en lugar

de actuar como un osculador, como pretendían los investigadores,

¡descubrieron que el circuito se había convertido en un receptor de radio

que estaba recibiendo y retransmitiendo una señal oscilatoria de un

componente electrónico cercano!

Sin embargo, esto no es un problema en la naturaleza. En el laboratorio de

la evolución biológica, sólo hay una función de aptitud que es igual para

todos los seres vivos -la carrera por sobrevivir y reproducirse, sin importar

qué adaptaciones hagan esto posible. Los organismos que se reproducen






25

con más abundancia que sus competidores están más adaptados; los que

fracasan 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 el

tamaño de la población es demasiado pequeño, puede que el algoritmo

genético no explore suficientemente el espacio de soluciones para

encontrar buenas soluciones consistentemente. Si el ritmo de cambio

genético es demasiado alto o el sistema de selección se escoge

inadecuadamente, puede alterarse el desarrollo de esquemas beneficiosos

y la población puede entrar en catástrofe de errores, al cambiar demasiado

rápido para que la selección llegue a producir convergencia.

Los seres vivos también se enfrentan a dificultades similares, y la evolució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 muy altos o la presión

selectiva es demasiado fuerte (una situación así podría ser resultado de un

cambio ambiental drástico), entonces la especie puede extinguirse. Lasolución ha sido ``la evolución de la evolutividad'' -las adaptaciones que

alteran la habilidad de una especie para adaptarse. Un ejemplo. La mayoría

de los seres vivos han evolucionado una elaborada maquinaria celular que

comprueba y corrigue errores durante el proceso de replicación del ADN,

manteniendo su ritmo de mutación a unos niveles aceptablemente bajos; a

la inversa, en tiempos de fuerte presión ambiental, algunas especies de

bacterias entran en un estado de hipermutación en el que el ritmo deerrores en la replicación del ADN aumenta bruscamente, aumentando la

probabilidad de que se descubrirá una mutación compensatoria. Por

supuesto, no pueden eludirse todas las catástrofes, pero la enorme

diversidad y las adaptaciones altamente complejas de los seres vivos

actuales muestran que, en general, la evolución es una estrategia exitosa.






26

Igualmente, las aplicaciones diversas y los impresionantes resultados de los

algoritmos genéticos demuestran que son un campo de estudio poderoso y

que merece la pena.Un problema con el que los algoritmos genéticos tienen dificultades son los

problemas con las funciones de aptitud `̀ engañosas'' en las que la

situación de los puntos mejorados ofrecen informació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 ocho caracteres, 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 apto que 00000011, que sería menos apto que

00000111, etcétera -, con dos excepciones: la cadena 11111111 resulta

tener una aptitud muy baja, y la cadena 00000000 resulta tener una aptitud

muy alta. En este problema, un AG (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 encontrar

siempre el óptimo global. Puede funcionar casi igual de bien alcanzando la

cima 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ácilmente

desde ese punto. La evolución es como un ``satisfactor'' -un algoritmo que

entrega 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ño

improvisado en la naturaleza'' proporciona ejemplos de la naturaleza con

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

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










27

Normalmente, la situación de las mejoras locales proporciona alguna

informació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ía de

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 hacia el óptimo

local que representa ese individuo, en lugar de rastrear el paisaje

adaptativo lo bastante a fondo para encontrar el óptimo global .Esto es un

problema especialmente común en las poblaciones pequeñas, donde

incluso una variación aleatoria en el ritmo de reproducción puede provocar

que un genotipo 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, para no

proporcionar tanta ventaja a los individuos excesivamente aptos. La

selección escalada, por rango y por torneo, discutidas anteriormente, son

tres de los métodos principales para conseguir esto; algunos métodos deselección escalada son el escalado sigma, en el que la reproducción se

basa en una comparación estadística de la aptitud media de la población, y

la selección de Boltzmann, en la que la fuerza selectiva aumenta durante la

ejecución de manera similar a la variable ``temperatura'' en el recocido

simulado

La convergencia prematura ocurre en la naturaleza (los biólogos la llaman

deriva genética). Esto no debe sorprender; como ya se dijo arriba, laevolución, como estrategia de resolución de problemas, no está obligada a

encontrar la mejor solución, sólo una que sea lo bastante buena. Sin

embargo, en la naturaleza, la convergencia prematura es menos común, ya

que la mayoría de las mutaciones beneficiosas en los seres vivos sólo

producen mejoras en la aptitud pequeñas e incrementales; son raras las






28

mutaciones que producen una ganancia de aptitud tan grande que otorgue

a sus poseedores una drástica ventaja reproductiva.

Finalmente, varios investigadores aconsejan no utilizar algoritmosgenéticos en problemas resolubles de manera analítica. No es que los

algoritmos genéticos no puedan encontrar soluciones buenas para estos

problemas; simplemente es que los métodos analíticos tradicionales

consumen 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 una

solució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ás

generalizado, los algoritmos genéticos se utilizan para abordar una amplia

variedad 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 utilizaron algoritmos genéticos para diseñar una sala de

conciertos con propiedades acústicas óptimas, maximizando la calidad del sonido

para la audiencia, para el director y para los músicos del escenario. Esta tarea

implica la optimización simultánea de múltiples variables. Comenzando con una

sala 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 autores

afirman que estas soluciones tienen proporciones similares al Grosser

Musikvereinsaal de Viena, el cual está considerado generalmente como una de las






29

mejores -si no la mejor- salas de conciertos del mundo, en términos de

propiedades acústicas.

Porto, Fogel y Fogel 1995 utilizaron programación evolutiva para adiestrar a redes

neuronales para distinguir entre reflexiones sonoras desde distintos tipos de

objetos: esferas metálicas hechas por el hombre, montañas submarinas, peces y

plantas, y ruido aleatorio de fondo. Tras 500 generaciones, la mejor red neuronal

que evolucionó tenía una probabilidad de clasificación correcta que iba desde el

94% al 98%, y una probabilidad de clasificación errónea entre un 7,4% y un 1,5%,

que son ``probabilidades razonables de detección y falsa alarma'' (p. 21). Esta red

evolucionada igualó las prestaciones de otra red desarrollada mediante recocidosimulado, 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 superar estos

óptimos locales y producir redes más pequeñas, efectivas y robustas; pero los

autores sugieren que el algoritmo evolutivo, a diferencia del recocido simulado,

opera sobre una población, y por tanto se beneficia de la información global sobreel espacio de búsqueda, conduciendo potencialmente hacia un rendimiento mayor

a la larga.

Tang et al. 1996 analizan los usos de los algoritmos genéticos en el campo de la

acústica y el procesamiento de señales. Un área de interés particular incluye el

uso de AGs para diseñar sistemas de Control Activo de Ruido (CAR), que eliminan

el sonido no deseado produciendo ondas sonoras que interfieren destructivamente

con el ruido. Esto es un problema de múltiples objetivos que requiere el control y lacolocación precisa de múltiples altavoces; los AGs se han utilizado en estos

sistemas tanto para diseñar los controladores como para encontrar la colocación

óptima de los altavoces, dando como resultado una ``atenuación efectiva del

ruido'' (p. 33) en pruebas experimentales.






30

Ingeniería aeroespacial

Obayashi et al. 2000 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 resistencia

aerodinámica a velocidades de vuelo supersónicas, minimizar la resistencia a

velocidades subsónicas y minimizar la carga aerodinámica (la fuerza que tiende a

doblar el ala). Estos objetivos son mutuamente exclusivos, y optimizarlos todos

simultáneamente requiere realizar contrapartidas.

El cromosoma de este problema es una cadena de 66 números reales, cada unode los cuales corresponde a un aspecto específico del ala: su forma, su grosor, su

torsión, etcétera. Se simuló una evolución con selección elitista durante 70

generaciones, 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ón

no dominada del problema. El artículo comenta que estos individuos ganadores

tení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 seis

mejores fueron comparadas con un diseño de ala supersónica producido por el

Equipo de Diseño SST del Laboratorio Aeroespacial Nacional de Japón. Las seis

fueron competitivas, con valores de resistencia y carga aproximadamente iguales

o menores a los del ala diseñada por humanos; en particular, una de las

soluciones evolucionadas superó al diseño del LAN en los tres objetivos. Los

autores señalan que las soluciones del AG son similares a un diseño llamado ``ala

flecha'', sugerido por primera vez a finales de los años 50, pero que finalmente fue

abandonado en favor del diseño más convencional con forma de delta.

En un artículo posterior (Sasaki et al. 2001), los autores repitieron el experimento

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 vuelo supersónico).

También se añadieron puntos de control adicionales para el grosor al conjunto de






31

variables de diseño. Tras 75 generaciones de evolución, se compararon dos de las

mejores soluciones paretianas con el diseño de ala que el Laboratorio

Aeroespacial Nacional japonés realizó para el avión supersónico experimentalNEXST-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 y superiores al

diseño del LAN en los cuatro objetivos.

Williams, Crossley y Lang 2001 aplicaron algoritmos genéticos a la tarea de situar

órbitas de satélites para minimizar los apagones de cobertura. Mientras la

tecnología de telecomunicaciones sigue progresando, los humanos somos cada

vez 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 los

ingenieros es el diseño de las trayectorias orbitales. Los satélites que se

encuentran 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 contacto con

las estaciones terrestres, pero son mucho más caros de lanzar y más vulnerables

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, a causa de lacurvatura de la Tierra, es inevitable que estos satélites pierdan durante un tiempo

la línea de visión con los receptores terrestres, y por lo tanto se vuelven inútiles.

Incluso las constelaciones de varios satélites tienen apagones ineludibles 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 problema multi-objetivo

que implica la minimización de el tiempo medio de apagón para todas las

localizaciones y el tiempo máximo de apagón para cada una de las localizaciones;

en la práctica, estos objetivos resultan ser mutuamente exclusivos.

Cuando se utilizó el AG en este problema, los resultados que evolucionaron para

constelaciones de tres, cuatro y cinco satélites eran extraños, configuraciones

orbitales muy asimétricas, con los satélites colocados alternando huecos grandes

y pequeños, en lugar de huecos de igual tamaño como habrían hecho las técnicas






32

convencionales. Sin embargo, esta solución redujo significativamente los tiempos

medio 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 ``ingenieros con años deexperiencia aeroespacial quedaorn sorprendidos con el rendimiento ofrecido por el

diseño no convencional''.

Keane y Brown 1996 utilizadon un AG para producir un nuevo diseño para un

brazo o jirafa para transportar carga que pudiese montarse en órbita y utilizarse

con satélites, estaciones espaciales y otros proyectos de construcción

aeroespacial. El resultado, una estructura retorcida con aspecto orgánico que se

ha comparado con un fémur humano, no utiliza más material que el diseño debrazo estándar, pero es ligera, fuerte y muy superior a la hora de amortiguar las

vibraciones perjudiciales, como confirmaron las pruebas reales del producto final.

Y sin embargo ``Ninguna inteligencia produjo los diseños. Simplemente

evolucionaron'' (Petit 1998). Los autores del artículo comentan además que su AG

sólo se ejecutó durante 10 generaciones, debido a la naturaleza

computacionalmente costosa de la simulación, y la población no se había

estancado 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






33

mejorada a la frecuencia (adaptado de

http://www.soton.ac.uk/~ajk/truss/welcome.html).

Finalmente, como informa Gibbs 1996, Lockheed Martin ha utilizado un algoritmo

genético para producir mediante evolución una serie de maniobras para mover

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ás rápida

que una solución producida manualmente por un experto para el mismo problema.

Astronomía y astrofísica

Charbonneau 1995 sugiere la utilidad de los AGs para problemas de astrofísica,

aplicándolos a tres problemas de ejemplo: obtener la curva de rotación de una

galaxia basándose en las velocidades rotacionales observadas de sus

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 individuo

se copia una vez hacia la siguiente generación sin ninguna modificación. PIKAIA

tiene 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ón se

aproxima a la convergencia, para mantener la variabilidad en el acervo genético.

En el problema de la curva de rotación galáctica, el AG produjo dos curvas, y

ambas 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 serie

temporal, el AG fue impresionantemente exitoso, generando un ajuste de los datos






34

de gran calidad, aunque otros problemas más difíciles no se ajustaron tan bien

(aunque, como señala Charbonneau, estos problemas son igualmente difíciles de

resolver con técnicas convencionales). El artículo sugiere que un AG híbrido queemplee 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 tres con una

precisión de menos del 0,1% y los otros tres con precisiones entre el 1 y el 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étodo

eficiente y robusto para resolver experimentalmente un problema no lineal 6-

dimensional de este tipo; un método de gradiente conjugado funciona ``siempre

que 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 los

AGs 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 inversiones

heliosísmicas. Para terminar, Charbonneau sostiene que los AGs son un``contendiente poderoso y prometedor'' (p. 324) en este campo, del que se puede

esperar que complemente (no sustituya) a las técnicas tradicionales de

optimización, y concluye que ``el 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 en

moléculas más sencillas, un proceso con aplicaciones importantes en la química

orgá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, para

moléculas grandes, obtener la forma del pulso deseado de manera analítica es






35

demasiado difícil: los cálculos son demasiado complejos y las características

relevantes (las superficies de energía potencial de las moléculas) no se conocen

con suficiente precisión.

Assion et al. 1998 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éculas iniciales, para

diseñar el pulso conforme a las especificaciones, el AE dispara un pulso, mide las

proporciones de las moléculas producto resultantes, muta aleatoriamente las

características del rayo con la esperanza de conseguir que estas proporciones se

acerquen a la salida deseada, y el proceso se repite. (En lugar de afinardirectamente las características del rayo láser, el AG de los autores representa a

los individuos como un conjunto de 128 números, en el que cada 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 conocimiento específico del

problema sobre las propiedades del láser o de los productos de la reacción). Los

autores afirman que su algoritmo, cuando se aplica a dos sustancias de muestra,

``encuentra automáticamente la mejor configuración... no importa lo complicadaque sea la respuesta molecular'' (p. 921), demostrando un ``control coherente

automatizado de los productos que son químicamente diferentes 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écnica de

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 un

só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 de

diseñar las bibliotecas de reactivos en esta técnica: diseño basado en los

reactivos, que elige grupos optimizados de reactivos sin considerar qué productos






36

saldrán como resultado, y diseño basado en los productos, que selecciona los

reactivos 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 y

má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 de

GlaxoSmithKline, Gillet 2002 describe el uso de un algoritmo genético multiobjetivo

para el diseño basado en los productos de bibliotecas combinatorias. Al elegir los

componentes que van en una biblioteca particular, deben considerarse

características como la diversidad y peso molecular, el coste de los suministros, latoxicidad, la absorción, la distribución y el metabolismo. Si el objetivo es encontrar

moléculas similares a una molécula existente con una función conocida (un

método común en el diseño de nuevos fármacos), también se puede tener en

cuenta la similaridad estructural. Este artículo presenta un enfoque multiobjetivo,

donde puede desarrollarse un conjunto de resultados paretianos que maximicen o

minimicen cada uno de estos objetivos. El autor concluye diciendo que el AG fue

capaz de satisfacer simultáneamente los criterios de diversidad molecular yeficiencia sintética máxima, y también fue capaz de encontrar moléculas parecidas

a un fármaco que eran ``muy similares a las moléculas objetivo dadas, tras

explorar una fracción muy pequeña del espacio de búsqueda total'' (p. 378).

En un artículo relacionado, Glen y Payne 1995 describen el uso de algoritmos

genéticos para diseñar automáticamente moléculas nuevas desde cero que se

ajustan a un conjunto de especificaciones dado. Dada una población inicial, bien

generada aleatoriamente o utilizando la sencilla molécula del etano como semilla,el AG añade, elimina y altera aleatoriamente átomos y fragmentos moleculares

con el objetivo de generar moléculas que se ajusten a los requisitos dados. El AG

puede optimizar simultáneamente un gran número de objetivos, incluyendo el peso

molecular, el volumen molecular, el número de enlaces, el número de centros

quirales, el número de átomos, el número de enlaces rotables, la polarizabilidad, el






37

momento dipolar, etcétera, para producer moléculas candidatas con las

propiedades deseadas. Basándose en pruebas experimentales, incluyendo un

difícil problema de optimización que implicaba la generación de moléculas conpropiedades similares a la ribosa (un componente del azúcar imitado a menudo en

los fármacos antivirales), los autores concluyen que el AG es un `èxcelente

generador de ideas'' (p. 199) que ofrece ``propiedades de optimización rápidas y

poderosas'' y puede generar `ùn conjunto diverso de estructuras posibles'' (p.

182). Continúan afirmando: `Ès de interés especial la poderosa capacidad de

optimización del algoritmo genético, incluso con tamaños de población

relativamente pequeños'' (p. 200). Como prueba de que estos resultados no son

simplemente teóricos, Lemley 2001[45] informa de que la empresa Unilever ha

utilizado algoritmos genéticos para diseñar nuevos componentes 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, o

FPGA), 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 dos

funciones se controlan por software, así que simplemente cargando un programa

especial en la placa, puede alterarse al vuelo para realizar las funciones de

cualquier 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 cualquier

ingeniero humano. Generó cadenas aleatorias de bits de ceros y unos y las utilizó

como configuraciones de la FPGA, seleccionando los individuos más aptos de

cada generación, reproduciéndolos y mutándolos aleatoriamente, intercambiando

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









38

secciones de su código y pasándolo hacia la siguiente ronda de selección. Su

objetivo era evolucionar un dispositivo que pudiera en principio discriminar entre

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

Su objetivo se alcanzó en 3.000 generaciones, pero el éxito fue mayor de lo que

había anticipado. El sistema que evolucionó utilizaba muchas menos celdas que

cualquier cosa que pudiera haber diseñado un ingeniero humano, y ni siquiera

necesita del componente más crítico de los sistemas diseñados por humanos -un

reloj. ¿Cómo funcionaba? Thompson no tiene ni idea, aunque ha rastreado la

señ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 ninguna

manera -pero si se les retira la alimentación eléctrica, el circuito deja de funcionar.

Parece que la evolución ha explotado algún sutil efecto electromagnético de estas

celdas para alcanzar su solución, pero el funcionamiento exacto de la compleja e

intrincada estructura evolucionada sigue siendo un misterio (Davidson 1997).

Altshuler y Linden 1997 utilizaron un algoritmo genético para evolucionar antenas

de alambre con propiedades especificadas a priori. Los autores señalan que 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 produce

resultados óptimos y tiende a funcionar bien sólo con diseños simétricos y

relativamente simples. En contraste, con el método del algoritmo genético, elingeniero especifica las propiedades electromagnéticas de la antena, y el AG

sintetiza automáticamente una configuración que sirva.






39

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 a

la izquierda. Cada individuo del AG consistía en un cromosoma binario que

especificaba las coordenadas tridimensionales de cada extremo final de cada

alambre. La aptitud se evaluaba simulando a cada candidato de acuerdo con un

código de cableado electromagnético, y el individuo mejor de cada ronda se

construí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 de

radiació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ón

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






40

Mahfoud y Mani 1996 utilizaron un algoritmo genético para predecir el rendimiento

futuro de 1.600 acciones ofertadas públicamente. Concretamente, al AG se le

asignó la tarea de predecir el beneficio relativo de cada acción, definido como elbeneficio de esa acción menos el beneficio medio de las 1.600 acciones a lo largo

del periodo de tiempo en cuestión, 12 semanas (un cuarto del calendario) en el

futuro. Como entrada, al AG se le proporcionaron datos histó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 para clasificar 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, que los autores habían estado utilizando

para pronosticar los precios de las acciones y administrar las carteras de valores

durante tres años. Por supuesto, el mercado de valores 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 la

semana 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ó significativamente a la red neuronal: en una ejecución de prueba, el AG

predijo correctamente la dirección de una acción el 47,6% de las veces, no hizo

predicción el 45,8% de las veces 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 a menudo (de hecho, los autores especulan que la mayor capacidad del AG

para no realizar predicciones cuando los datos eran dudosos fue un factor de su






41

éxito; la red neuronal siempre produce una predicción a menos que sea restringida

explí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én

superó significativamente a tres índices bursátiles importantes -el S&P 500, el S&P

400 y el Russell 2000- en este periodo; la casualidad fue excluída como causa de

este resultado con un margen de confianza de un 95%. Los autores atribuyen 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 reglas antiintuitivas y

contradictorias'' (p. 562) de los expertos humanos.

Andreou, Georgopoulos y Likothanassis 2002 lograron un éxito similar utilizando

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 redes neuronales, aquí los dos

trabajaron conjuntamente: el AG evolucionó la arquitectura (número de unidades

de entrada, número de unidades ocultas y la estructura de enlaces entre ellas) dela red, que luego era entrenada por un algoritmo de filtro.

Se le proporciaron al algoritmo 1.300 valores brutos diarios de cinco divisas como

información histórica -el dólar estadounidense, el marco alemán, el franco francé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 AG híbrido mostró, en

general, un ``nivel excepcional de precisión'' (p. 200) en todos los casos probados,

superando a otros varios métodos, incluyendo a las redes neuronales en solitario.Los autores concluyen que ``se ha logrado un excepcional éxito predictivo tanto

con un horizonte predictivo de un paso como de varios pasos'' (p. 208) -de hecho,

afirman que sus resultados son mejores con diferencia que cualquier estrategia

predictiva relacionada que se haya aplicado en esta serie de datos u otras divisas.






42

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[informa de que

LBS Capital Management, una empresa estadounidense cons ede en Florida,utiliza algoritmos genéticos para escoger las acciones de los fondos de pensiones

que administra. Coale 1997 y Begley y Beals 1995 informan de que First

Quadrant, una empresa de inversiones de Californa que mueve más de 2.200

millones de dólares, utiliza AGs para tomar decisiones de inversión en todos sus

servicios financieros. Su modelo evolucionado gana, de media, 225 dólares por

cada 100 dólares invertidos durante seis años, en contraste con los 205 dólares de

otros tipos de sistemas de modelos.

Juegos

Una de las demostraciones más novedosas y persuasivas de la potencia de los

algoritmos genéticos la presentaron Chellapilla y Fogel 2001, que utilizaron un AG

para evolucionar redes neuronales que pudieran jugar a las damas. Los autores

afirman que una de las mayores dificultades en este tipo de problemas

relacionados 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 que

los criterios simples de ganar, perder o empatar no proporcionan la suficiente

informació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ólo las

posiciones espaciales de las piezas en el tablero y el número total de piezas que

posee cada jugador, fueron capaces de evolucionar un programa de damas que

jugaba a un nivel competitivo con expertos humanos, sin ninguna información deentrada inteligente acerca de lo que constituye el buen juego -es más, ni siquiera

se les dijo a los individuos del algoritmo evolutivo cuál era el criterio para ganar, ni

se les dijo el resultado de ningún juego.






43

En la representación de Chellapilla y Fogel, el estado del juego estaba

representado 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 cadaposición era 0 para una casilla desocupada, -1 si esa casilla estaba ocupada por

una 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ía una

red neuronal con múltiples capas de procesamiento y una capa de entrada con un

nodo para cada una de las 4x4, 5x5, 6x6, 7x7 y 8x8 posibles casillas del tablero.

La salida de la red neuronal para una colocación de las piezas dada era un valor

entre -1 y +1, que indicaba cómo de buena le parecía esa posición. Para cada

movimiento, se le presentaba a la red neuronal un árbol de juego que contenía

todos los movimientos posibles hasta cuatro turnos en el futuro, y el movimiento se

decidía basándose en qué rama del árbol producía los mejores resultados.

El algoritmo evolutivo comenzó con una población de 15 redes neuronales con

pesos y tendencias, generados aleatoriamente, asignados a cada nodo yconexión; luego, cada individuo se reprodujo una vez, generando una

descendencia con variaciones en los valores de la red. Luego estos 30 individuos

compitieron por la supervivencia jugando entre ellos; cada individuo compitió en

cada turno con 5 oponentes elegidos aleatoriamente. Se otorgó 1 punto a cada

victoria y se descontaban 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ón continuó durante 840 generaciones más (aproximadamente seis meses

de tiempo de computación).

Clase Puntuación

Gran Maestro +2.400






44

Maestro 2.200-2.399

Experto 2.000-2.199

Clase 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 en la

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 la

Federación de Ajedrez de Estados Unidos (mostrado a la izquierda, con algunos

rangos 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 que

quedan en cada lado) con una capacidad de anticipación de 8 movimientos

demostró que la red neuronal era significativamente superior, con una puntuación

de más de 400 puntos por encima. ``Un programa que se basa sólo en el número

de piezas y en una búsqueda de ocho capas vencerá a muchas personas, pero no

es un experto. La mejor red neuronal evolucionada sí lo es'' (p. 425). Aunque






45

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

espaciales del tablero para decidir sus movimientos. Los autores señalan que los

oponentes de zone.com que los movimientos de la red neuronal eran ``extraños'',

pero su nivel global de juego fue descrito como ``muy duro'' o con términos

elogiosos similares.

Para probar más a la red neuronal evolucionada (a la que los autores nombraron

``Anaconda'' porque a menudo ganaba restringiendo la movilidad de susoponentes), jugó contra un programa de damas comercial, el Hoyle Classic

Games, distribuído por Sierra Online (Chellapilla y Fogel 2000). 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 con una capacidad de

anticipación de 6 movimientos. Aunque los autores dudaban de que estaprofundidad de anticipación pudiera darla a Anaconda la capacidad de juego

experto que demostró anteriormente, consiguió seis victorias seguidas de las seis

partidas jugadas. Basándose en este resultado, los autores expresaron

escepticismo sobre si el software Hoyle jugaba al nivel que anunciaba, ¡aunque

debe señalarse que llegaron a esta conclusión basándose solamente en la

facilidad con la que Anaconda le venció!

La prueba definitiva de Anaconda se detalla en Chellapilla y Fogel 2002, cuando lared neuronal evolucionada jugó contra el mejor jugador de damas del mundo:

Chinook, un programa diseñado principalmente por el Dr. Jonathan Schaeffer, 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 por grandes

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








46

maestros humanos, un conjunto sofisticado de algoritmos de juego para la parte

central de la partida, y una base de datos completa de todos los movimientos

posibles cuando quedan en el tablero 10 piezas o menos, de manera que nuncacomete un error durante un final de partida. Se invirtió una cantidad enorme 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ó esta competición, cuatro victorias a dos,

con cuatro empates. (Curiosamente, como señalan los autores, en dos de las

partidas que acabaron con empate, Anaconda lideraba con cuatro damas mientrasque Chinook tenía tres. Además, una de las victorias de Chinook vino tras una

serie de movimientos con búsqueda de 10 capas sacados de su base de datos de

finales de partida; unos movimientos que Anaconda, con una anticipación de 8

capas, no pudo anticipar. Si Anaconda hubiera tenido acceso a una base de datos

de finales de partida de la misma calidad de la de Chinook, el resultado del torneo

bien podría haber sido el de victoria para Anaconda, cuatro a tres). Estos

resultados ``proporcionan un buen sustento a la puntuación de experto que seganó Anaconda en www.zone.com'' (p. 76), con una puntuación global de 2.030-

2.055, comparable a la puntuación de 2.045 que ganó jugando contra humanos.

Aunque Anaconda no es un jugador invulnerable, es capaz de jugar

competitivamente en el nivel experto y comportarse ante una variedad de

jugadores de damas humanos extremadamente hábiles. Cuando uno considera

los criterios de aptitud tan sencillos con los que se obtuvieron estos resultados, el

surgimiento de Anaconda proporciona una espectacular corroboración del poder

de la evolución.

Geofísica

Sambridge y Gallaguer 1993 utilizaron un algoritmo genético para los hipocentros

de los terremotos basándose en datos sismológicos. (El hipocentro es el punto






47

bajo la superficie terrestre en el que se origina un terremoto. El epicentro es el

punto de la superficie directamente encima del hipocentro). Esto es una tarea

sumamente compleja, ya que las propiedades de las ondas sísmicas dependen delas propiedades de las capas de roca a través de las que viajan. El método

tradicional para localizar el hipocentro se basa en lo que se conoce como

algoritmo de inversión sísmico, que empieza con la mejor estimación de la

ubicació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 una

ubicación actualizada. Este proceso se repite hasta que se alcanza una solución

aceptable. (Este Mensaje del Mes, de noviembre de 2003, proporciona más

informació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 o modelos

de velocidad puede evitar esta deficiencia calculando sólo el problema directo -la

diferencia entre los tiempos de llegada de la onda observados y predichos para

distintas localizaciones del hipocentro. Sin embargo, un método de búsqueda

exhaustivo basado en este método sería demasiado costoso computacionalmente.Éste, por supuesto, es precisamente el tipo de problema de optimizació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 un solo hipocentro

más y más cerca hacia la solución, comienza con una nube de hipocentros

potenciales que encoge con el tiempo hasta converger en una sola solución. Los

autores afirman que su método ``puede localizar rápidamente soluciones 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 completamente no lineal'' (p.

1.469). Los autores concluyen que su algoritmo genético es `èficiente para una

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








48

verdadera optimización global'' (p. 1.488) y ``una herramienta nueva y poderosa

para realizar búsquedas robustas de hipocentros'' (p. 1.489).

Ingeniería de materiales

Giro, Cyrillo y Galvão 2002 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 inventado recientemente, tienen

``grandes aplicaciones tecnológicas potenciales'' y podrían abrir la puerta a

``nuevos fenómenos físicos fundamentales'' (p. 170). Sin embargo, debido a su

alta reactividad, los átomos de carbono pueden formar un número virtualmenteinfinito de estructuras, haciendo que la búsqueda de nuevas molé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éculas nuevas con

propiedades especificadas a priori, comenzando con una población de candidatos

iniciales generada aleatoriamente. Concluyen que su metodología puede ser una

``herramienta muy efectiva'' (p. 174) para guiar a los investigadores en la

búsqueda de nuevos compuestos y es lo suficientemente general 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 aplicaron algoritmos evolutivos a un problema

industrial ``no trivial'' (p. 162): el diseño de revestimientos ópticos multicapa 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 capas deben colocarse en unasecuencia particular y con un grosor particular para producir el resultado deseado,

y las variaciones incontrolables del entorno de fabricación, como la temperatura, la

polución o la humedad, pueden afectar al rendimiento del producto acabado.

Muchos óptimos locales no son robustos ante estas variaciones, lo que significa

que una mayor calidad del producto se paga con una tasa mayor de desviaciones






49

indeseadas. El problema particular considerado en este artículo también tenía

múltiples criterios: además de la reflectancia, 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 cada una

de ellas, y produjo diseños que eran ``sustancialmente más robustos a la variación

de parámetros'' (p. 166) y tenían un rendimiento medio mayor que los mé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 conocimiento

específico del dominio en la función de búsqueda y sin tener que alimentar a lapoblació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 utilizaron AGs para diseñar patrones de exposición

para un haz de electrones de litografía, utilizado para grabar estructuras 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 costoso determinarlos experimentalmente,

pero la alta dimensionalidad del espacio de búsqueda frustra a la mayoría de los

algoritmos de búsqueda. Deben optimizarse simultáneamente hasta 100

parámetros para controlar el haz de electrones y evitar la dispersión y efectos de

proximidad que arruinarían las estructuras finas que se estén esculpiendo. El

problema directo -determinar la estructura resultante como 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 una estructura dada, que es lo

que se pretende resolver aquí, es mucho más difícil y no existe una solucióndeterminista.

Se aplicaron algoritmos genéticos a este problema, ya que ``se sabe que son

capaces de encontrar soluciones buenas a problemas muy complejos de alta

dimensionalidad'' (p. 75) sin necesidad de proporcionarles información específica






50

del dominio acerca de la topología del paisaje de búsqueda. Los autores del

artículo emplearon un AG de estado estacionario con selección por rueda de ruleta

en una simulación por computador, que produjo unos patrones de exposición``muy bien optimizados'' (p. 77). En contraste, se utilizó un tipo de trepacolinas

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 poca calidad. Un

híbrido entre los métodos del AG y el BS tampoco pudo mejorar los resultados

ofrecidos por el AG en solitario.

Matemáticas y algoritmia

Aunque algunas de las aplicaciones más prometedoras y las demostraciones más

convincentes de la potencia de los AGs se encuentran en el campo de la

ingeniería de diseño, también son relevantes en problemas ``puramente''

matemáticos. Haupt y Haupt 1998 describen el uso de AGs para resolver

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 la ecuación de quinto

orden conocida como Super Korteweg-de Vries.

Ordenar una lista de elementos es una tarea importante en la informática, y una

red 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

en orden 1999 utilizaron programación genética para evolucionar redes deordenación mínimas para conjuntos de 7 elementos (16 comparaciones),

conjuntos de 8 elementos (19 comparaciones) y conjuntos de 9 elementos (25

comparaciones). Mitchell 1996, describe el uso de algoritmos genéticos por W.

Daniel Hillis para encontrar una red de ordenación de 61 comparaciones para un

conjunto de 16 elementos, sólo un paso más allá de la más pequeña conocida.






51

Este último ejemplo es especialmente interesante por las 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 pruebaevolucionaron conjuntamente; se les otorgó mayor aptitud a las redes de

ordenació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

``engañar'' a un mayor número de redes de búsqueda para que ordenaran

incorrectamente. El AG con coevolución rindió significativamente mejor que el

mismo AG sin ella.

Un ejemplo final de AG digno de mención en el campo de la algoritmia puedeencontrarse en 1999 que utilizó programación genética para descubrir una regla

para el problema de clasificación por mayoría en autómatas celulares de una

dimensión, una regla mejor que todas las reglas conocidas escritas por humanos.

Un autómata celular de una dimensión puede imaginarse como una cinta finita con

un número dado de posiciones (celdas) en ella, cada una de las cuales puede

contener el estado 0 o el estado 1. El autómata se ejecuta durante un número

dado de pasos temporales; en cada paso, cada celda adquiere un nuevo valorbasado en su valor anterior y el valor de sus vecinos más cercanos. (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 tal que si más de la mitad de las

celdas de la cinta son 1 inicialmente, todas las celdas se ponen a 1; de lo

contrario, todas las celdas se ponen a 0. El reto consiste en el hecho de que

cualquier celda individual sólo tiene acceso a información acerca de sus vecinos

más cercanos; por lo tanto, los conjuntos de reglas buenos deben encontrar de

algún modo una manera de transmitir información sobre regiones distantes de la

cinta.

Se sabe que no existe una solución perfecta a este problema -ningún conjunto de

reglas puede clasificar con precisión todas las configuraciones iniciales posibles-,

pero durante los últimos veinte años ha habido una larga sucesión de soluciones

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










52

cada vez mejores. En 1978, tres investigadores desarrollaron la famosa regla

GKL, 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 reglas

requirieron para su desarrollo de un esfuerzo significativo por parte de humanos

inteligentes y creativos. En contraste, la mejor regla descubierta mediante

programación genética, tiene una precisión total de 82,326% -mejor que

cualquiera de las soluciones humanas desarrolladas durante las dos últimas

décadas. Los autores señalan que sus nuevas reglas son cualitativamente

distintas a las reglas publicadas con anterioridad, al emplear representaciones

internas muy detalladas de la densidad de estados y conjuntos intrincados de

señales para comunicar información a largas distancias.

Ejército y cumplimiento de la ley

Kewley y Embrechts 2002 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 menudo atormenta a

los profesionales experimentados'' (p. 163), no sólo porque este tipo de 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úmero de variables y

consecuencias: minimizar las bajas amigas, maximizar las bajas enemigas,

controlar el terreno deseado, conservar recursos, etcétera. Los planificadores

humanos tienen dificultades al tratar con las complejidades de esta tarea y a

menudo deben recurrir a métodos ``rápidos y sucios'', como hacer lo que

funcionase la última vez.

Para superar estas dificultades, los autores del artículo citado desarrollaron un

algoritmo genético para automatizar la creación de planes de batalla, en

conjunció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






53

batalla; en la simulación utilizada, se tomaron en cuenta factores como la

topografía del terreno, la cobertura vegetal, la velocidad del movimiento de tropas,

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 las

fuerzas 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, se

compararon con planes de batalla para el mismo escenario producidos por un

grupo de ``expertos militares experimentados... considerados muy capaces de

desarrollar planes de acción para el tamaño de las fuerzas utilizadas en este

experimento'' (p. 166). Estos avezados expertos desarrollaron su propio plan y,

cuando la solución del AG estuvo acabada, se les dio la oportunidad de

examinarla y modificarla como vieran conveniente. Finalmente, todos los planes se

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 sus

modificaciones sobre la solución del AG. ``...Los planes producidos por losalgoritmos automáticos tenían un rendimiento medio significativamente mayor al

de los generados por los experimentados expertos militares'' (p. 161). Es más, los

autores señalan que el plan del AG tenía sentido táctico. (Consistía en un ataque a

dos flancos a la posición enemiga por pelotones de infantería mecanizada

apoyados por helicópteros de ataque y exploradores terrestres, en conjunción con

vehículos aéreos no tripulados realizando labores de reconocimiento para el fuego

directo de artillería). Por añadidura, el plan evolucionado incluía unidades amigas

individuales llevando a cabo misiones doctrinales -una propiedad emergente que

apareció durante el curso de la ejecución, en lugar de ser especificada por el

experimentador. En campos de batalla modernos, cada vez má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 ser obvio.






54

Naik 1996 informa de un uso interesante de los AGs en el cumplimiento de la ley,

describiendo el software ``FacePrints'', un proyecto para ayudar a los testigos a

identificar y describir a los sospechosos criminales. La imagen cliché del artistapolicía haciendo un dibujo del rostro del sospechoso en base a la descripción de

los testigos es un método difícil e ineficiente: la mayoría de la gente 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 son mejores al reconocer

caras completas. FacePrints aprovecha esto utilizando un algoritmo genético que

evoluciona dibujos de caras basándose en bases de datos de cientos de

características individuales que pueden combinarse de infinitas maneras. El

programa muestra a los testigos imágenes de rostros generadas aleatoriamente, y

éstos escogen las que más se parecen a la persona que vieron; las caras

seleccionadas mutan y se combinan para generar nuevas combinaciones de

características, y el proceso se repite hasta que emerge un retrato preciso del

rostro del sospechoso. En un caso real de atraco, los retratos definitivos que

crearon los tres testigos eran sorprendentemente parecidos, y el dibujo resultante

apareció en el periódico local.

Biología molecular

En los seres vivos, las proteínas transmembrana son proteínas que sobresalen de

una membrana celular. Las proteínas transmembrana realizan a menudo

funciones importantes como detectar la presencia de ciertas sustancias en el

exterior de la célula o transportarlas hacia el interior de la célula. Para comprender

el comportamiento de una proteína transmembrana es necesario identificar el

segmento de la proteína que realmente está insertado en la membrana, lo que seconoce como dominio transmembrana. Durante las dos últimas décadas, los

biólogos moleculares han publicado una serie de algoritmos cada vez más

precisos para este propósito.






55

Todas las proteínas utilizadas por los seres vivos están formadas por los mismos

20 aminoácidos. Algunos de estos aminoácidos son hidrofóbicos, lo que significa

que repelen el agua, y algunos son hidrofílicos, lo que significa que atraen el agua.Las secuencias de aminoácidos que son parte de un dominio transmembrana

tienen probabilidad de ser hidrofóbicas. Sin embargo, la hidrofobicidad no es una

característica definida con precisión, y no existe acuerdo sobre una escala para

medirla.

Koza et al. 1999 utilizaron programación genética para diseñar un algoritmo que

identificase el dominio transmembrana de una proteína. Se le suministró al

programa genético un conjunto de operadores matemáticos estándares con losque 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ón dentro 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 memoria compartida contenía una

cuenta de la suma total, y cuando el algoritmo acababa, el segmento proteínico seidentificaba como dominio transmembrana si su valor era positivo. Con tan sólo

estas herramientas, ¿haría falta más información para que un diseñador humano

produjese una solución eficiente a este problema?

Las aptitudes de las soluciones producidas por la programación genética fueron

evaluadas probándolas con 246 segmentos proteínicos de los que se conocía su

condición de transmembrana. Luego se evaluó al mejor individuo de la prueba con

250 casos adicionales inéditos (out-of-sample), y se comparó su efectividad con lade los cuatro mejores algoritmos humanos para el mismo propósito. El resultado:

la programación genética produjo un algoritmo de identificación de segmentos

transmembrana con una tasa total de error del 1,6%-significativamente menor que

las de los cuatro algoritmos humanos, el mejor de los cuales tenía una tasa de






56

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ácidos muy

hidrofóbicos) del segmento proteínico.

Incrementar la suma en 2 unidades por cada instancia de cualquier otro

aminoácido.Si [(SUMA - 3,1544)/0,9357] es menor que la longitud del segmento

proteínico, clasificar ese segmento como dominio transmembrana; de lo

contrario, 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 ha

acuñ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 las

compañías de telecomunicaciones una gran cantidad de dinero cada año, y

reducir las fugas es un factor importante para aumentar la rentabilidad. Si las

compañías pueden contactar con los clientes que tienen probabilidad de cambiar y

ofrecerles incentivos especiales para que se queden, puede reducirse la tasa de

fugas; 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 las

compañías tienen grandes bases de datos con información de los clientes que

teóricamente puede utilizarse para este propósito; pero ¿qué método funciona

mejor para examinar esta enorme cantidad de datos e identificar los sutiles

patrones y tendencias que indican la probabilidad de fuga de un cliente?

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









57

Au, Chan y Yao 2003[7] aplicaron algoritmos genéticos a este problema para

generar un conjunto de reglas de tipo si-entonces para predecir la probabilidad de

fuga 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 de

inducción probabilística. Las generaciones posteriores las refinaron, combinando

sencillas reglas de una condición con reglas más complejas con varias

condiciones. Para la medición de la aptitud se utilizó una medida de correlación

objetiva de la ``interesantitud'', que no necesitaba información de entrada

subjetiva. El algoritmo evolutivo de explotación de datos se probó sobre una base

de datos real de 100.000 clientes proporcionada por una compañía malasia, y su

rendimiento se comparó con el de dos métodos alternativos: una red neuronal

multicapa y un algoritmo basado en árbol de decisiones ampliamente utilizado, el

C4.5. Los autores afirman que su AE fue capaz de descubrir regularidades ocultas

en la base de datos y ``fue capaz de hacer predicciones precisas de fuga con

distintas tasas de fuga'' (p. 542), superando al C4.5 bajo todas las circunstancias,

superando a la red neuronal en tasas mensuales de fuga bajas e igualándola en

tasas de fuga mayores y, en ambos casos, alcanzando las conclusiones más

rápidamente. Algunas ventajas más del enfoque evolutivo son que puedefuncionar eficientemente incluso cuando faltan algunos campos de datos, y que

puede expresar sus descubrimientos en conjuntos de reglas fácilmente

comprensibles, al contrario que la red neuronal.

Entre algunas de las reglas más interesantes halladas por el AE se encuentran las

siguientes: 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 planes

de bonificación); los clientes tienen más probabilidad de fugarse si viven en Kuala

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); y










58

los clientes que viven en Penang y contrataron a través de un cierto vendedor

tienen más probabilidades de fugarse (este vendedor puede estar proporcionando

un mal servicio al cliente y debería ser investigado).

Rizki, Zmuda y Tamburino 2002 utilizaron algoritmos evolutivos para evolucionar

un complejo sistema de reconocimiento de patrones con una amplia variedad de

usos potenciales. Los autores señalan que el reconocimiento de patrones es una

tarea cada vez más realizada por algoritmos de aprendizaje automático, en

particular, algoritmos evolutivos. La mayoría de ellos comienzan con un acervo de

características predefinidas, del que un AE puede seleccionar combinaciones

apropiadas para la tarea en cuestión; en contraste, este método empezaba desdecero, primero evolucionando detectores individuales de característica en forma de

árboles de expresiones, y luego evolucionando combinaciones cooperativas de

esos detectores para producir un sistema completo de reconocimiento de

patrones. El proceso evolutivo selecciona automáticamente el número de

detectores de característica, la complejidad de los detectores y los aspectos

específicos de los datos a los que responde cada detector.

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 devolver

señales bastante distintas dependiendo del ángulo y elevación desde el que se le

observa, 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 porcentaje

neto mayor que el de las otras tres técnicas -una red neuronal perceptrón, un

algoritmo 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 la

del clasificador evolucionado, una diferencia que no es estadísticamente

significativa, pero la red de base radial necesitó 256 detectores de característica

mientras que el sistema reconocedor evolucionado sólo utilizó 17). Como afirman

los autores, ``los sistemas de reconocimiento que evolucionan utilizan menos






59

características que los sistemas producidos utilizando técnicas convencionales,

pero consiguen una precisión de reconocimiento comparable o superior'' (p. 607).

También se han aplicado varios aspectos de su sistema en problemas queincluyen el reconocimiento óptico de caracteres, la revisión industrial y el análisis

médico de imágenes.

Hughes y Leyland 2000 también aplicaron AGs multiobjetivo a la tarea de clasificar

objetivos basándose en sus reflexiones rádar. Los datos de una sección

transversal rádar de alta resolución necesitan enormes cantidades de espacio de

almacenamiento en disco, y producir un modelo realista de la fuente a partir de los

datos es muy costoso computacionalmente. En contraste, el método basado en elAG de los autores demostró ser muy exitoso, produciendo un modelo tan bueno

como el del método iterativo tradicional, pero reduciendo el gasto computacional y

las necesidades de almacenamiento hasta el punto de que era factible generar

buenos modelos en un ordenador de escritorio. En contraste, el método iterativo

tradicional requiere diez veces más resolución y 560.000 veces más accesos a los

datos de imagen para producir modelos de calidad similar. Los autores concluyen

que sus resultados ``demuestran claramente'' (p. 160) la capacidad del AG deprocesar datos de rádar bidimensionales y tridimensionales de cualquier nivel de

resolución con muchos menos cálculos que los métodos tradicionales,

manteniendo una precisión aceptablemente alta.

Robótica

El torneo internacional RoboCup es un proyecto para promocionar el avance de la

robótica, la inteligencia artificial y los campos relacionados, proporcionando unproblema 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 objetivo

fijado es desarrollar un equipo de robots humanoides que puedan vencer al equipo

humano de fútbol que sea campeón del mundo en 2050; actualmente, la mayoría

de los equipos de robots participantes funcionan con ruedas). Los programas que

http://www.robocup.org/

http://www.robocup.org/






60

controlan a los miembros del equipo robótico deben exhibir un comportamiento

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 el ataque, etcétera. En laliga simulada de 1997, David Andre y Astro Teller inscribieron a un equipo llamado

Darwin United cuyos programas de control habían sido desarrollados

automáticamente desde cero mediante programación genética, un desafío a la

creencia convencional de que ``este problema es simplemente demasiado difícil

para una técnica como ésa'' (Andre y Teller 1999, p. 346).

Para resolver este difícil problema, Andre y Teller le proporcionaron al programa

genético un conjunto de funciones de control primitivas como girar, moverse, tirar,etcétera. (Estas funciones estaban también sujetas al cambio y refinamiento

durante el curso de la evolución). Su función de aptitud, escrita para que

recompensara 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 la

dirección correcta, marcar goles y ganar el partido. Debe señalarse que no se

suministró ningún código para enseñar específicamente al equipo cómo conseguirestos objetivos complejos. Luego los programas evolucionados se evaluaron

utilizando un modelo de selección jerárquico: en primer lugar, los equipos

candidatos se probaron en un campo vacío y, si no marcaban un gol en menos de

30 segundos, se rechazaban. Luego se evaluaron haciéndoles jugar contra un

equipo estacionario de ``postes pateadores'' que golpeaban la pelota hacia el

campo contrario. En tercer lugar, el equipo jugaba un partido contra el equipo

ganador de la competición RoboCup de 1997. Finalmente, los equipos que

marcaron al menos un gol contra este equipo jugaron unos contra otros para

determinar 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 mitad de los

participantes escritos por humanos. Aunque una victoria en el torneo sin duda






61

habría sido más impresionante, este resultado es competitivo y significante de

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 primeravez, una computadora había sido inscrita recientemente en una competición

regional, aunque no ganó (Sagan 1979, p. 286). Pero ``una máquina que juega al

ajedrez a un nivel medio de la capacidad humana es una má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 los grandes maestros, ¿qué

tipo de sistemas producirá la programación genética dentro de 20 o 30 años?

Diseño de rutas y horarios

Burke y Newall 1999 utilizaron algoritmos genéticos para diseñar los horarios de

los exámenes universitarios. Se sabe que, en general, el problema del horario es

NP-completo, lo que significa que no se conoce un método para hallar con

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 la vez- y

restricciones suaves -si es posible, no deben asignarse varios exámenes en

sucesión a un mismo estudiante, para minimizar la fatiga. Las restricciones duras

deben satisfacerse, mientras que las restricciones suaves deben satisfacerse lo

máximo posible. Los autores llaman ``algoritmo 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 las

soluciones halladas por el AE. El AE se utilizó en cuatro conjuntos de datos de

universidades reales (la menor de las cuales tenía 25.000 alumnos), y sus

resultados se compararon con los resultados producidos por un método heurísticode vuelta atrás, un algoritmo muy consolidado que se encuentra entre los mejores

que 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%.






62

He y Mort 2000 aplicaron algoritmos genéticos al problema de hallar rutas óptimas

en las redes de telecomunicaciones (como las redes de telefonía e Internet), que

se usan para transmitir datos desde los remitentes hasta los destinatarios. Esto esun problema NP-difícil, un tipo de problema para el que los AGs son

``extremadamente aptos... y han encontrado una enorme variedad de aplicaciones

exitosas en esos campos'' (p. 42). Es además un problema multiobjetivo, en el que

hay que equilibrar objetivos en conflicto como maximizar 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. Cualquier algoritmo real satisfactorio debe también ser

capaz de redirigir el tráfico de las rutas principales que fallen o estén

congestionadas.

En el AG híbrido de los autores se utilizó un algoritmo de tipo ``primero el camino

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 el control,intercambiando secciones de rutas. Cuando se probó sobre un conjunto de datos

derivado de una base de datos en red real de Oracle, se descubrió que el AG 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 estos resultados

demuestran la ``efectividad y escalabilidad'' del AG y que ``se pueden conseguir

soluciones óptimas o casi óptimas'' (p. 49).

Esta técnica ha encontrado aplicaciones reales para propósitos similares, comoinforman Begley y Beals 1995. La compañía de telecomunicaciones U.S. West

(ahora fusionada con Qwest) se enfrentó a la tarea de desplegar una red de fibra

óptica. Hasta hace poco, el problema de diseñar la red para minimizar la longitud

total de cable desplegado era resuelto por un ingeniero experimentado; ahora la

compañía utiliza un algoritmo genético para realizar la tarea automáticamente. Los






63

resultados: ``El tiempo de diseño para las redes nuevas ha caído de dos meses a

dos días, y le supone un ahorro a U.S. West de 1 millón a 10 millones de dólares

cada una'' (p. 70).

Jensen 2003 y Chryssolouris y Subramaniam 2001 aplicaron algoritmos genéticos

a la tarea de generar programas para líneas de montaje (job shop scheduling).

Éste es un problema de optimización NP-difícil con múltiples criterios: deben

tomarse en cuenta factores como el coste, los retrasos y el rendimiento, y puede

que se tenga que cambiar al vuelo el programa de la línea de montaje debido a

averías en la maquinaria, ausencia de empleados, retrasos en la entrega de

piezas, y otras complicaciones, lo que hace que la robustez del programa sea unaconsideración importante. Ambos artículos concluyen que los AGs son

significativamente superiores a las reglas de despacho de prioridad utilizadas

comúnmente, al producir programas eficientes que pueden tratar con más facilidad

los retrasos y las averías. Estos resultados no son simplemente teóricos, sino que

se han aplicado a situaciones reales:

Como informa Naik 1996, los organizadores de los Juegos Paraolímpicos de 1992

utilizaron un AG para diseñar los horarios de los eventos. Como informa Petzinger

1995, 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 de lujo, éstas pueden construírse en

una gran variedad de configuraciones con muchas partes y opciones distintas, y la

enorme cantidad de maneras posibles de construirlas implica que el diseño

eficiente de programas de montaje sea un problema aparentemente intratable. La

productividad se veía mermada por cuellos de botella en el montaje, los equiposde trabajadores discutían, y se estaba perdiendo dinero. Finalmente, en 1993,

Deer acudió a Bill Fulkerson, un analista e ingeniero de personal que concibió la

utilización de un algoritmo genético para producir programas de montaje para la

planta. Tras superar el escepticismo inicial, el AG demostró su valía rápidamente:

la producción mensual aumentó un 50 por ciento, el tiempo extra casi desapareció






64

y otras plantas de Deere están incorporando los AGs en sus propios diseños de

programas de montaje.

Como informa Rao 1998, Volvo ha utilizado un programa evolutivo llamado

OptiFlex 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 de

restricciones y millones de permutaciones posibles para cada vehículo. Como

todos los algoritmos genéticos, OptiFlex funciona combinando aleatoriamente

distintos programas de montaje posibles, determinando su aptitud clasificándolos

en base a sus costos, beneficios y restricciones, y luego haciendo que las mejores

soluciones intercambien genes entre ellas y vuelvan a la población para otraprueba. Hasta hace poco, esta desalentadora tarea era responsabilidad de un

ingeniero humano, al que le llevaba hasta cuatro días producir el programa para

cada semana; ahora, gracias a los AGs, esta tarea se puede completar en un día

con una mínima intervención humana.

Como informa Lemley 2001, United Distillers and Vintners, una empresa escocesa

que es el mayor y más rentable distribuidor de licores del mundo y es responsable

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 eficientemente más de 7

millones de barriles, que contienen 60 recetas distintas, entre un enorme sistema

de almacenes y destilerías, dependiendo de una multitud de factores como la

edad, el número de malta, el tipo de madera y las condiciones del mercado.

Anteriormente, coordinar este complejo flujo de suministro y demanda requería de

cinco empleados a tiempo completo. Hoy, unas cuantas pulsaciones de teclado enun 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 utilizaron un AG para programar los

aterrizajes del London Heathrow, el aeropuerto más transitado del Reino Unido.






65

Esto es un problema multiobjetivo que implica, entre otras cosas, minimizar los

retrasos y maximizar el número de vuelos mientras se mantiene la suficiente

distancia 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 demasiado

cerca). Comparado con los horarios reales de un periodo intensivo del aeropuerto,

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 se informa en

Wired 2002[1], aeropuertos internacionales y líneas aéreas importantes como

Heatrhow, Toronto, Sydney, Las Vegas, San Francisco, America West Airlines,

AeroMexico y Delta Airlines están utilizando algoritmos genéticos para programar

los despegues, aterrizajes, mantenimiento y otras tareas, mediante el software del

Ascent Technology's SmartAirport Operations Center (Cruzando y mutando las

soluciones en forma de horarios que incorporan miles de variables, ``Ascent vence

con comodidad a los humanos, aumentando la productividad hasta en un 30 por

ciento en todos los aeropuertos en los que se ha implementado''.

Ingeniería de sistemas

Benini y Toffolo 2002 aplicaron un algoritmo genético a la tarea multiobjetivo de

diseñar molinos eólicos para generar energía eléctrica. Este diseño ``es un

procedimiento complejo caracterizado por varias decisiones sobre contrapartidas...

El proceso de toma de decisiones es muy difícil y no hay tendencias de diseño

bien establecidas'' (p. 357); como resultado, hoy existen varios tipos de turbina

distintos y no hay acuerdo sobre cuál es la óptima, si alguna lo es. Deben tomarse

en cuenta objetivos mutuamente exclusivos como la producción máxima deenergía anual y el coste mínimo de la energía. En este artículo se utilizó un

algoritmo evolutivo multiobjetivo para encontrar el mejor conjunto de

contrapartidas entre estos objetivos, construyendo palas de molino con 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 AG consiguió










66

encontrar soluciones competitivas con los diseños comerciales, además de

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 utilizaron un algoritmo genético multiobjetivo para

optimizar la forma, orientación e intensidad del haz de los emisores de rayos X

utilizados en la radioterapia dirigida, para destruír los tumores cancerosos al

tiempo que se evita el tejido sano. (Los fotones de rayos X dirigidos hacia un

tumor tienden a dispersarse por las estructuras interiores del cuerpo, dañando

inintencionadamente los órganos internos. El reto consiste en minimizar este

efecto mientras se maximiza la dosis de radiación dirigida hacia el tumor).Utilizando un modelo de aptitud basada en rango, los investigadores comenzaron

con la solución producida por el método convencional, un método de mínimos

cuadrados iterativo, y luego utilizaron el AG para modificarlo y mejorarlo.

Construyendo un modelo del cuerpo humano y exponiéndolo al rayo evolucionado

por el AG, encontraron un buen acuerdo entre las distribuciones de radiación

predichas y reales. Los autores concluyen que sus resultados ``muestran una

protección [de los órganos sanos] que no podía lograrse utilizando las técnicasconvencionales'' (p. 1745).

Lee y Zak 2002 utilizaron un algoritmo genético para evolucionar un conjunto de

reglas para controlar un sistema de frenos antibloqueo automovilístico. Aunque la

capacidad que tienen los sistemas de freno antibloqueo de reducir la distancia de

frenada y mejorar la maniobrabilidad ha salvado muchas vidas, el rendimiento del

ABS depende de las condiciones de la superficie de la carretera: por ejemplo, un

controlador ABS que esté optimizado para el asfalto seco no funcionará igual debien en carreteras mojadas o heladas, y viceversa. En este artículo, los autores

proponen un AG para ajustar un controlador ABS que pueda identificar las

propiedades de la superficie de la carretera (monitorizando el patinaje y

aceleración de las ruedas) y pueda actuar en consecuencia, liberando la cantidad

adecuada de fuerza de frenado para maximizar la tracción de las ruedas. En las






67

pruebas, el ABS puesto a punto genéticamente ``exhibe características de rodada

excelentes'' (p. 206) y fue ``muy superior'' (p. 209) a los otros dos métodos de

maniobras de frenado, encontrando con rapidez nuevos valores óptimos para elpatinaje de las ruedas cuando cambia el tipo de terreno bajo un coche en

movimiento, y reduciendo la distancia total de frenada. ``La lección que hemos

aprendido de nuestro experimento... es que un AG puede ayudar a ajustar incluso

un controlador bien diseñado. En nuestro caso, ya teníamos una buena solución

del problema; sin embargo, con la ayuda de un AG, conseguimos mejorar

significativamente la estrategia de control. En resumen, parece que merece la

pena intentar aplicar un AG incluso en un controlador bien diseñado, porque hay

muchas probabilidades de que se pueda hallar una configuración del controlador

mejor utilizando AGs'' .

Como cita Schechter 2000, el Dr. Peter Senecal, de la Universidad de Wisconsin,

utilizó algoritmos genéticos de población pequeña para mejorar la eficiencia de los

motores diésel. Estos motores funcionan inyectando combustible en una cámara

de combustión que está llena de aire extremadamente comprimido, y por tanto

extremadamente caliente, lo bastante caliente para hacer que el combustibleexplote y empuje un pistón que produce la fuerza motriz del vehículo. Este diseño

básico ha cambiado poco desde que Rudolf Diesel lo inventó en 1893; aunque se

ha empleado mucho esfuerzo en realizar mejoras, es una tarea muy difícil de

realizar analíticamente, porque requiere un conocimiento preciso del

comportamiento turbulento que exhibe la mezcla de combustible y aire, y de la

variación simultánea de muchos parámetros independientes. Sin embargo, el

método de Senecal prescindía de ese conocimiento específico del problema y, en

cambio, funcionaba evolucionando parámetros como la presión de 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 produjo un motor mejorado que

consumía un 15% menos de combustible que un motor diesel normal y producía

dos tercios menos de óxido nítrico de escape y la mitad de hollín. Luego el equipo






68

de Senecal construyó un motor diésel real de acuerdo con las especificaciones de

la solución evolucionada, y obtuvieron los mismos resultados. Ahora Senecal

sigue su trabajo evolucionando la geometría del propio motor, lo que con suerteproducirá todavía más mejoras.

Como citan Begley y Beals 1995, Texas Instruments utilizó un algoritmo genético

para optimizar la disposición de los componentes de un chip informá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 de conexiones que no se le

había ocurrido a ningún humano, el AG alcanzó un diseño que ocupaba un 18%

menos de espacio.

Finalmente, como cita Ashley 1992, empresas de la industria aeroespacial,

automovilística, fabril, turbomaquinaria y electrónica están utilizando un sistema de

software propietario conocido como Engineous, que utiliza algoritmos genéticos,

para diseñar y mejorar motores, turbinas y otros dispositivos industriales. En

palabras de su creador, el Dr. Siu Shing Tong, Engineous es ``un maestro

`toqueteador', ensayando incansablemente las puntuaciones de escenarios de tipo

``y-si'' hasta que emerge la mejor solución posible'' (p. 49). En un ensayo del

sistema, Engineous consiguió producir un incremento del 0,92 por ciento de la

eficiencia de una turbina experimental en sólo una semana, mientras que diez

semanas de trabajo de un diseñador humano sólo produjeron un 0,5 por ciento de

mejora.

Supuestamente, Engineous no sólo cuenta con algoritmos genéticos; también

emplea 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 del

dominio, carecen de aplicabilidad general, y son propensas a quedar atrapadas en

óptimos locales. En contraste, el uso de algoritmos genéticos permite a Engineous

explorar regiones del espacio de búsqueda que pasan por alto los otros métodos.






69

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 turbina

generadora de energía del avión Boeing 777; como informan Begley y Beals 1995el diseño optimizado genéticamente era casi un 1% más eficiente en combustible

que los motores anteriores, lo que en un campo como éste es una ganancia caída

del cielo. Engineous también se ha utilizado para optimizar la configuración de

motores eléctricos industriales, generadores hidroeléctricos y turbinas de vapor,

para proyectar redes eléctricas, y para diseñar generadores superconductores y

generadores de energía nuclear para satélites en órbita. Rao 1998 informa

también de que la NASA ha utilizado Engineous para optimizar 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 que

representan los AGs ha resultado sorprendente y descorcentante para los

creacionistas, que siempre han afirmado que sólo un diseño inteligente, no la

variación aleatoria y la selección, puede haber producido la cantidad y complejidad

de información que contienen los seres vivos. Por tanto, han argumentado que el

éxito de los algoritmos genéticos no nos permite deducir nada sobre la evolución

biológica. Abordaré las críticas de dos antievolucionistas que representan dos

puntos de vista distintos: un creacionista de tipo tierra-joven, el Dr. Don Batten, de

``Answers in Genesis'', que ha escrito un artículo titulado ``Algoritmos genéticos -

¿demuestran que la evolución funciona?'', y un creacionista de tipo tierra-vieja y

defensor del diseño inteligente, el Dr. William Dembski, cuyo reciente libro ``NoFree Lunch'' (Dembski 2002) trata sobre este tema.

Don Batten

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









70

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 pueda

seleccionar cualquier mejora. Esto es cierto. Luego continua diciendo: ``Muchos

caracteres biológicos son cualitativos -o funcionan o no funcionan, así que no

existe 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 la

evidencia. Batten ni siquiera intenta ofrecer un ejemplo de caracter biológico que

``o 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 demostrar

razonablemente que no hay un camino paso a paso hasta él? Aunque no

conozcamos tal camino, ¿significa eso que no existe ninguno? Por supuesto que

no. Batten afirma efectivamente que si no entendemos cómo han evolucionado

ciertos caracteres, entonces es imposible que esos caracteres hayan evolucionado

-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 conocimiento

supone 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 que

nuestra 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 hecho

enormes progresos para explicar la evolución de muchas estructuras y sistemas

biológicos complejos, tanto macroscópicos como microscópicos (por ejemplo, veaestas 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én

se entenderán con claridad en el futuro.

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

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

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




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






71

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 de

ingeniería y diseño de los que no se conocía la solución previamente, y por lotanto el problema no podía ``amañarse'' para facilitar el éxito del algoritmo. Si los

creacionistas tuvieran razón, habría sido completamente razonable esperar que

los algoritmos genéticos hubieran fallado estrepitosamente una y otra vez al ser

aplicados a estos problemas, pero, en cambio, ha ocurrido justo lo contrario: los

AGs han descubierto soluciones poderosas y de gran calidad a problemas difíciles

en una gran variedad de campos. Esto pone seriamente en duda incluso si existen

problemas como los que Batten describe, cuyas soluciones sean inaccesibles a un

proceso evolutivo.

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 -en

resument, los AGs no permiten la posibilidad de una extinción.

Sin embargo, esto no es cierto; la extinción puede ocurrir. Por ejemplo, algunos

AGs 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 y

reproducirse (Haupt y Haupt 1998, p. 37). Si no hay ningún individuo que cumpla

este criterio en este tipo de AG, la población puede extinguirse efectivamente.

Pero incluso en AGs que no establecen umbrales pueden ocurrir estados análogos

a la extinción. Si las tasas de mutación son demasiado altas o las presionesselectivas demasiado fuertes, un AG nunca encontrará una solución factible. La

población puede acabar en un caos sin remedio al verse afectados los cantidatos

aptos por el hecho de que las mutaciones perjudiciales se desarrollen con 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 aptitud lo






72

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 tiene

un programador a este respecto es que, si ocurre esto, él puede introducirle alprograma valores diferentes -para el tamaño de la población, para la tasa de

mutación, para la presión selectiva- y comenzar de nuevo. Obviamente, esto no es

una opción para los seres vivos. Batten dice que ``no existe una regla en la

evolución que diga que algunos organismos de la población que evoluciona

permanecerán viables ocurran las mutaciones que ocurran'', pero tampoco existe

una regla así en los algoritmos genéticos.

Batten también afirma que ``los AGs que he observado preservan artificialmente alos 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 siguiente

generació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 de Haldane'',

que dice que un alelo que contribuya menos a la aptitud de un organismo 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, que selecciona 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 la evolución biológica a este

respecto.

Sin embargo, esto no viene al caso. La selección elitista es una idealización de la

evolución biológica -un modelo de lo que pasaría en la naturaleza si de vez en

cuando no interviniese el azar. Como reconoce Batten, el dilema de Haldane no

afirma que una mutación ligeramente ventajosa nunca quedará fijada en una

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

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






73

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 desea

obtener una solución con mayor rapidez, puede ser deseable saltarse esteproceso implementando el elitismo. Un punto importante es que el elitismo no

afecta a qué mutaciones surgen, sólo asegura la selección de las mejores que

surjan. No importaría lo fuerte que fuera la selección si no ocurrieran mutaciones

que incrementasen la información. En otras palabras, el elitismo acelera la

convergencia una vez que se ha descubierto una solución buena -no provoca un

resultado que no habría ocurrido de otra manera. Por lo tanto, si los algoritmos

gené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 en

cambio dependen sólo de selección por ruleta de rueda y otras técnicas de

muestreo estocásticas, con no menor éxito, proporciona ejemplos de 36 casos en

los que la programación genética ha producido resultados competitivos con los de

los humanos, incluyendo la recreación automática de 21 inventos patentados con

anterioridad (seis de los cuales fueron patentados durante o después de 2000), 10de los cuales duplican la funcionalidad de la patente de manera diferente, e

incluyendo además dos nuevos inventos patentables y cinco algoritmos nuevos

que superan a cualquier algoritmo humano escrito para el mismo propósito. Como

declara el Dr. Koza en una referencia anterior al mismo trabajo . En todos estos

casos, sin ningún mecanismo para asegurar que se seleccionaban los mejores

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 resultados humanos. 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






74

Esta crítica es confusa. Batten afirma que una generación puede durar

microsegundos en un AG, mientras que en los seres vivos una generación puede

durar 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 puede

generar información nueva, tarde el tiempo que tarde, entonces la evolución

natural puede hacer lo mismo sin duda; que los AGs pueden efectivamente

hacerlo es todo lo que trata de demostrar este ensayo. La única cuestión restante

serí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 de

los biólogos, geólogos y físicos, no de los programadores informáticos.

Sin embargo, la respuesta que han proporcionado estos científicos está en

completo acuerdo con las escalas de tiempo evolutivas. Numerosas líneas

independientes de evidencia, incluyendo la datación isocrónica radiométrica, los

ritmos de enfriamiento de las enanas blancas, la no existencia en la naturaleza de

isótopos con tiempos cortos de semideintegración, los ritmos de alejamiento de las

galaxias lejanas, y el análisis de la radiación cósmica de fondo, convergen hacia la

misma conclusión: una Tierra y un universo con muchos miles de millones deaños, sin duda tiempo suficiente para que la evolución haya producido toda la

diversidad de vida que observamos hoy para todas las estimaciones razonables.

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, que

los AGs ``producen comúnmente cientos o miles de `descendientes' porgeneración'', un ritmo que ni siquiera las bacterias, los organismos biológicos que

se 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 del

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

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







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

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






75

número de descendientes por unidad de tiempo absoluto, entonces existen

evidentemente organismos biológicos que pueden reproducirse a ritmos mayores

que 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 las

limitaciones 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 de

todo, son las poblaciones, y no los individuos, los que evolucionan. Por supuesto,

es completamente plausible que una población tenga colectivamente cientos o

miles 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 errores

diseñada para limitar la tasa de mutación en aproximadamente 1 por cada 10.000

millones de par de bases (aunque esto es demasiado poco -la cifra real está más

cerca de 1 por cada 1.000 millones. Ver Dawkins Por supuesto, esto es cierto. Si

los AGs mutasen a este ritmo, tardarían muchísimo en resolver problemas reales.

Evidentemente, lo que debe considerarse relevante es la tasa de mutación relativa

al tamaño del genoma. La tasa de mutación debe ser lo bastante alta parapromover una cantidad suficiente de diversidad en la población sin acabar con los

individuos. Un ser humano corriente posee entre una y cinco mutaciones; esto es

perfectamente realista para la descendencia de un AG.

Los AGs tienen genomas artificialmente pequeños

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

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






76

El argumento de Batten de que el genoma de un algoritmo genético ``es

artificialmente 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 para

optimizar 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 ``artificialmente 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 soluciones candidatas

pueden crecer arbitrariamente. Batten afirma que hasta los seres vivos mássencillos tienen mucha más información en su genoma que la que un AG haya

producido nunca, pero si los organismos vivos actuales tienen genomas

relativamente grandes es porque se ha ganado mucha complejidad en el curso de

los miles de años de evolución. Como señala el artículo Probabilidad de

abiogénesis, hay buenas razones para creer que los primeros organismos vivos

eran mucho más sencillos que cualquier especie actual -las moléculas

autorreplicadoras probablemente no tenían más de 30 o 40 subunidades,pudiendo quedar especificadas perfectamente con los 1.800 bits de información

que Batten reconoce que ha generado al menos un AG. Asimismo, los algoritmos

genéticos son una técnica muy nueva cuyo potencial completo todavía no ha sido

explotado; las propias computadoras digitales sólo tienen unas pocas décadas, y,

las técnicas de computación evolutiva han generado resultados cada vez más

sustanciales y complejos durante los últimos 15 años, en sincronía con el rápido

aumento de la potencia computacional, a menudo referida como la ``ley de

Moore''. Al igual que la vida primigenia era muy sencilla comparada con la que

vino después, es probable que los algoritmos genéticos actuales, a pesar de los

impresionantes resultados que ya han producido, den origen a resultados mucho

más importantes en el futuro.

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


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













77

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, ``las

mutaciones ocurren por todo el genoma, no sólo en un gen o sección que

especifique un caracter dado''. Esto es cierto, pero cuando dice que lo mismo no

es cierto para los AGs, se equivoca. Exactamente igual que en los seres vivos, los

AGs deben escardar los genes perjudiciales al tiempo que seleccionan los

beneficiosos.

Batten continua afirmando que ``el propio programa está protegido contra las

mutaciones, 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 que

el programa que gobierna a un AG tenga que mutar. El programa no es parte del

algoritmo 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 la

maquinaria reproductiva de un organismo, una comparación que trata de

establecer Batten. En cambio, es análogo a las leyes naturales invariantes que

gobiernan los entornos en los que viven y se reproducen los seres vivos, y no se

espera 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 presencia de

muchos componentes distintos, funcionando juntos, para que el caracter pueda

existir'', mientras que esto no ocurre en los AGs.

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













78

Sin embargo, es trivial demostrar que esta afirmación es falsa, ya que los

algoritmos genéticos han producido sistemas irreduciblemente complejos. Por

ejemplo, el circuito reconocedor de voz que evolucionó el Dr. Adrian Thompson(Davidson 1997[19]) está compuesto de 37 puertas lógicas. Cinco de ellas ni

siquiera están conectadas al resto del circuito, aunque hacen falta las 37 para que

el 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 de

sistema 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, simplementepresentado en un lenguaje distinto, y por tanto la refuntación es la misma. La

complejidad irreducible no es un problema para la evolución, esté la evolución

ocurriendo en los seres vivos de la naturaleza o en el silicio del procesador de una

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 afecte

a múltiples caracteres) y los genes dominantes y recesivos.

Sin embargo, ninguna de estas afirmaciones es cierta. Los AGs no ignoran la

poligenia y la pleiotropía: simplemente se permite que estas propiedades surjan de

manera natural en lugar de programarlas deliberadamente. Es obvio que en

cualquier sistema complejo interdependiente (es decir, un sistema no lineal), la

alteració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. ``En la literatura sobre algoritmos genéticos, la interacción entre

parámetros se conoce como epistasis (un término biológico para la interacción

entre genes). Cuando hay poca o ninguna epistasis, los algoritmos de búsqueda








79

mínima [es decir, los trepacolinas **-A.M.] rinden mejor. Los algoritmos genéticos

brillan cuando la epistasis es media o alta... Igualmente, hay algunas

implementaciones de algoritmos genéticos que sí tienen cromosomas diploides ygenes dominantes y recesivos Sin embargo, los que no lo son simplemente se

parecen más a los organismos haploides, como las bacterias, que a los

organismos diploides, como los seres humanos. Ya que las bacterias están entre

los organismos más exitosos de este planeta (para ciertas medidas), tales AGs

siguen 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 de

algunos seres vivos, en los que las secuencias de ADN codifican distintas

proteínas funcionales cuando se leen en direcciones distintas o con distintos

desplazamientos de inicio. Afirma que ``crear un AG para generar una codificación

con información densa así parecería imposible''.

Un reto así pide una respuesta, y aquí está: Soule y Ball 2001.En este artículo, los

autores presentan un algoritmo genético con múltiples sistemas de lectura ycodificación densa, permitiéndole almacenar más información que el tamaño total

de su genoma. Al igual que los codones de tres nucleótidos especifican

aminoácidos en los genomas de los seres vivos, en este AG los codones 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 los codones 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 como codon de ``parada'';como el codon de comienzo y parada pueden aparecer en cualquier lugar del

genoma, la longitud de cada individuo era variable. Las regiones del cromosoma

que no caían entre pares comienzo-parada eran ignoradas.






80

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, la

mayor parte de un cromosoma no codifica nada. De nuevo, esto es porque en losindividuos iniciales aleatorios hay relativamente pocos pares de codones

comienzo-parada. Sin embargo, el número de bits que no participan disminuye

extremadamente rápido''. Durante el curso de la ejecución, el AG puede

incrementar la longitud efectiva de su genoma introduciendo nuevos codones de

comienzo en distintos sistemas de lectura. Al final de la ejecución, ``la cantidad de

superposiciones es bastante alta. Muchos bits participan en varios genes (a

menudo en los cinco)''. En todos los problemas probados, el AG empezó, de

media, con 5 variables especificadas; al final de la ejecución, ese número se había

incrementado hasta una media de 25.

En los problemas de prueba, el AG con múltiples sistemas de lectura produjo

soluciones 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 un cromosoma

de sólo 250 bits de longitud, utilizando sistemas de lectura alternativos. Losautores tildan este comportamiento de `èxtremadamente sofisticado'' y concluyen

que `èstos datos muestran que un AG puede utilizar con éxito sistemas de lectura

a pesar de la complejidad añadida'' y que `ès claro que un AG puede introducir

nuevos`genes' mientras sea necesario para resolver un cierto problema, incluso

con las dificultades impuestas al utilizar codones de comienzo y parada y genes

superpuestos''.

Los AGs tienen objetivos predeterminados

Como muchas otras, esta objeción demuestra que Batten no comprende bien lo

que es un algoritmo genético y cómo funciona. Argumenta que los AGs, al

contrario que la evolución, tienen objetivos predeterminados y especificados desde






81

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 no

representa a los algoritmos genéticos, precisamente por esa razón. No pretendía

demostrar 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 (la

infame frase del ``tornado pasando por una chatarrería y produciendo un 747'') y la

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 una

solución aceptable a un problema dado. En este mismo sentido, la evolución

también tiene un objetivo: producir organismos que estén mejor adaptados a su

entorno y por tanto experimenten un mayor éxito reproductivo. Pero al igual que la

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 aptitud

solamente se establece para evaluar lo bien que funciona una solución candidata,

sin especificar ninguna forma de funcionar particular y sin juzgar de qué manera

inventa. La solución en sí emerge luego mediante un proceso de mutación y

selección.

La siguiente afirmación de Batten demuestra claramente que no entiende lo que

es un algoritmo genético. Afirma que ``quizás si el programador pudiera dar con un

programa que permitiera que ocurriera cualquier cosa y luego midiera la capacidadde supervivencia de los `organismos', se estaría acercando a lo que se supone

que hace la evolución'' -pero así es exactamente como funcionan los algoritmos

genéticos. Generan aleagoriamente soluciones candidatas y provocan mutaciones

aleatorias sobre ellas durante muchas generaciones. No se especifica ninguna

configuración de antemano; como dice Batten, se permite que ocurra cualquier






82

cosa repitiendo misteriosamente las palabras de Batten: ``Una característica

importante... es que la selección [en la programación genética] no es codiciosa.

Los individuos que se sabe que son iferiores serán seleccionados hasta un ciertogrado. No se garantiza que se seleccionará el mejor individuo de la población.

Además, el peor individuo de la población no será necesariamente excluído.

Puede ocurrir cualquier cosa y nada está garantizado''. (Una sección anterior trató

este punto concreto como uno de los puntos fuertes de los AGs). Y, sin embargo,

aplicando un filtro selectivo a estas candidatas mutadas aleatoriamente, surgen

soluciones eficientes, complejas y poderosas a problemas difíciles, soluciones que

no fueron diseñadas por ninguna inteligencia y que a menudo pueden igualar o

superar a las soluciones 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 preguntar

qué parte de la `información' generada por el programa está en realidad

especificada en el programa, en lugar de haber sido generada de novo''. Acusa a

los AGs de que a menudo no hacen más que encontrar la mejor manera de que

ciertos módulos interaccionen, cuendo los propios módulos y las maneras que

tienen 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, los

componentes de un motor, el capital en un mercado financiero- puedenexpresarse en términos de módulos que interactúan de cierta manera. Si todo lo

que 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 a ningún

problema requiere la generación de información nueva?






83

Respecto a la crítica de Batten sobre que la información contenida en la solución

esté especificada en el problema, la mejora manera de mitigar sus preocupaciones

es 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; Davidson 1997; Assion et al. 1998; Giro, Cyrillo y Galvão

2002; Glen y Payne 1995; Chryssolouris y Subramaniam 2001; Williams, Crossley

y Lang 2001; Robin et al. 2003; Andreou, Georgopoulos y Lokothanassis 2002;

Kewley y Embrechts 2002; Rizki, Zmuda y Tamburino 2002; y especialmente Koza

et al. 1999 y Koza et al. 2003, que analiza el uso de programación genética para

generar 36 inventos competitivos con los humanos de diseños de circuitos

analógicos, biología molecular, algoritmia, diseño de controladores industriales y

otros campos, todos comenzando con poblaciones de candidatas iniciales

generadas aleatoriamente.

De acuerdo, algunos AGs sí comienzan con soluciones generadas

inteligentemente que luego intentan mejorar, pero esto es irrelevante: en esos

casos 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 la

situación inicial sea como la describe Batten, encontrar la manera más eficiente

mediante la que un cierto número de módulos puede interactuar bajo un conjunto

dado de limitaciones puede ser una tarea nada trivial, cuya solución implique una

cantidad considerable de información nueva: el diseño de horarios en los

aeropuertos 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 han

demostrado su efectividad a la hora de resolver problemas cuya complejidad

abrumaría a cualquier humano. A la luz de las múltiples innovaciones y soluciones

inesperadamente efectivas que ofrecen los AGs en muchos campos, la afirmación

de Batten de que ``la cantidad de información nueva generada (por un AG) es

normalmente bastante trivial'' suena verdaderamente hueca.






84

Conclusión

Hasta los creacionistas encuentran imposible negar que la combinación de la

mutació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 proceso

evolutivo en dos categorías -``microevolución'' y ``macroevolución''- y afirmando

que 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 tienen

significado para los biólogos; se definen, respectivamente, como evolución pordebajo del nivel de especies y evolución al nivel de especies o por encima. Pero la

diferencia crucial entre el modo en el que los creacionistas utilizan estos términos

y el modo en el que lo hacen los científicos es que los científicos reconocen que

los dos son fundamentalmente el mismo proceso con los mismos mecanismos, tan

sólo operando a diferentes escalas. Sin embargo, los creacionistas están

obligados a postular algún tipo de brecha infranqueable que los separa, para

poder negar que los procesos de cambio y adaptación que vemos en la actualidad

puedan extrapolarse para producir toda la diversidad que vemos en el mundo de

los seres vivos.

No obstante, los algoritmos genéticos hacen que esta idea sea insostenible, al

demostrar la naturaleza sin junturas del proceso evolutivo. Consideremos, por

ejemplo, un problema que consista en programar un circuito para que discrimine

entre un tono de 1 kilohercio y un tono de 10 kilohercios, y responda

respectivamente con salidas uniformes de 0 y 5 voltios. Digamos que tenemos unasolució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 presente a la

solución perfecta sería ``microevolución'', un cambio pequeño dentro de las






85

capacidades de la mutación y la selección. Pero, sin duda -argumentaría un

creacionista-, llegar a este mismo estado final desde una ordenación inicial

completamente aleatoria de componentes sería ``macroevolución'', y estaría másallá del alcance de un proceso evolutivo. Sin embargo, los algoritmos genéticos

han sido capaces de conseguir ambas cosas: evolucionar el sistema a partir de

una ordenación aleatoria hasta la solución casi perfecta y finalmente hasta la

solución perfecta y óptima. No surgió ninguna dificultad o brecha insalvable en

ningún punto del camino. En ningún momento hizo falta intervención humana para

montar un conjunto de componentes irreduciblemente complejo (a pesar del hecho

de que el producto final sí contiene tal cosa) o para ``guiar'' al sistema evolutivo a

través de algún pico dificultoso. El circuito evolucionó, sin la ayuda de ninguna

orientación inteligente, desde un estado completamente aleatorio y no funcional

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 -que

nosotros, como especie, hemos llegado a un punto en el que somos capaces de

controlar conscientemente nuestra sociedad, nuestro entorno y hasta nuestrosgenes al nivel suficiente para hacer que el proceso evolutivo sea irrelevante. Se

dice que los caprichos culturales de nuestra cambiante sociedad son los que

determinan 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 comprendery explotar; a pesar de esto, ya está funcionando por todas partes, moldeando

nuestra tecnología y mejorando nuestras vidas, y, en el futuro, estos usos no

harán sino multiplicarse. Sin un conocimiento detallado del proceso evolutivo no

habrían sido posibles ninguno de los incontables avances que le debemos a los

algoritmos genéticos. Aquí hay una lección que deben aprender los que niegan el






86

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: ``Es extraño pero cierto; porque la verdad siemprees extraña, más extraña que la ficción.''

algoritmos geneticos

Documents