Algoritm

os genético

s y computación evolutiva

Adam Marczyk

2004

Resumen:

Los creacionistas afirm

an a menudo que el proceso evolutivo no puede crear inform

ación nueva, o que la evolución no posee beneficios prácticos. E

ste artículo refuta esas afirmaciones describiendo el

crecimiento explosivo y las extensas aplicaciones de los algoritm

os genéticos, una técnica de com

putación basada en los principios de la evolución biológica.

Introducció

n

De vez en cuando, los creacionistas acusan a la evolución de que carece de utilidad com

o teoría científica porque no produce beneficios prácticos y no tiene relevancia en la vida diaria. S

in embargo,

tan sólo la evidencia de la biología demuestra que esta afirm

ación es falsa. Hay num

erosos fenómenos

naturales para los que la evolución nos ofrece un sólido fundamento teórico. P

or nombrar uno, el

desarrollo observado de la resistencia -a los insecticidas en las plagas de cultivos, a los antibióticos en las bacterias, a la quim

ioterapia en las células cancerosas, y a los fármacos antiretrovirales en virus

como el V

IH- es una consecuencia abierta de las leyes de la m

utación y la selección, y comprender estos

principios nos ha ayudado a desarrollar estrategias para enfrentarnos a estos nocivos organismos. E

l postulado evolutivo de la descendencia com

ún ha ayudado al desarrollo de nuevos medicam

entos y técnicas, al proporcionar a los investigadores una buena idea de con qué organism

os deben experimentar

para obtener resultados que probablemente serán relevantes para los seres hum

anos. Finalm

ente, el hom

bre ha utilizado con grandes resultados el principio de cría selectiva para crear organismos

personalizados, distintos a cualquiera que se pueda encontrar en la naturaleza, para beneficio propio. El

ejemplo canónico, por supuesto, es la diversidad de variedades de perros dom

ésticos (razas tan diversas com

o los bulldogs, chihuahuas y dachshunds han sido producidas a partir de lobos en sólo unos pocos miles de años), pero ejem

plos menos conocidos incluyen al m

aíz cultivado (muy diferente de sus

parientes salvajes, que carecen de las familiares ``orejas'' del m

aíz cultivado), a los peces de colores (com

o los perros, hemos criado variedades cuyo aspecto es drásticam

ente distinto al del tipo salvaje), y a las vacas lecheras (con ubres inm

ensas, mucho m

ayores que las necesarias para alimentar a una cría).

Los críticos pueden argum

entar que los creacionistas pueden explicar estas cosas sin recurrir a la evolución. P

or ejemplo, a m

enudo los creacionistas explican el desarrollo de la resistencia a los agentes antibióticos en las bacterias, o los cam

bios forjados en los animales dom

ésticos por selección artificial, asum

iendo que Dios decidió crear a los organism

os en grupos fijos, llamados ``tipos'' o baram

ins. Aunque la m

icroevolución natural o la selección artificial dirigida por humanos pueden producir

diferentes variedades dentro de los ``tipo-perro'', ``tipo-vaca'' o ``tipo-bacteria'' (!) creados originalm

ente, ninguna cantidad de tiempo o cam

bio genético puede transformar un ``tipo'' en otro. S

in em

bargo, nunca se explica cómo determ

inan los creacionistas lo que es un ``tipo'', o qué mecanism

o im

pide a los seres vivos evolucionar más allá de sus lím

ites.

Página 1 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Pero en las últim

as décadas, el continuo avance de la tecnología moderna ha producido algo nuevo.

Ahora la evolución está produciendo beneficios prácticos en un cam

po muy distinto y, esta vez, los

creacionistas no pueden afirmar que su explicación se adapte a los hechos igual de bien. E

ste campo es

la informática, y los beneficios provienen de una estrategia de program

ación llamada algoritm

os genéticos. E

ste ensayo explicará qué son los algoritmos genéticos y m

ostrará de qué manera son

relevantes en el debate evolución/creacionismo.

¿Qué es u

n algoritm

o genético

?

Expuesto concisam

ente, un algoritmo genético (o A

G para abreviar) es una técnica de program

ación que im

ita a la evolución biológica como estrategia para resolver problem

as. Dado un problem

a específico a resolver, la entrada del A

G es un conjunto de soluciones potenciales a ese problem

a, codificadas de alguna m

anera, y una métrica llam

ada función de aptitud que permite evaluar cuantitativam

ente a cada candidata. E

stas candidatas pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el A

G las m

ejore, pero se suelen generar aleatoriamente.

Luego el A

G evalúa cada candidata de acuerdo con la función de aptitud. E

n un acervo de candidatas generadas aleatoriam

ente, por supuesto, la mayoría no funcionarán en absoluto, y serán elim

inadas. Sin

embargo, por puro azar, unas pocas pueden ser prom

etedoras -pueden mostrar actividad, aunque só lo sea

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

a.

Estas candidatas prom

etedoras se conservan y se les permite reproducirse. S

e 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, form

ando un nuevo acervo de soluciones candidatas, y son som

etidas a una ronda de evaluación de aptitud. Las candidatas que han

empeorado o no han m

ejorado con los cambios en su código son elim

inadas de nuevo; pero, de nuevo, por puro azar, las variaciones aleatorias introducidas en la población pueden haber m

ejorado a algunos individuos, convirtiéndolos en m

ejores soluciones del problema, m

ás completas o m

ás eficientes. 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 m

edia de la población se increm

entará en cada ronda y, por tanto, repitiendo este proceso cientos o miles de rondas, pueden

descubrirse soluciones muy buenas del problem

a.

Aunque a algunos les puede parecer asom

broso y antiintuitivo, los algoritmos genéticos han dem

ostrado ser una estrategia enorm

emente poderosa y exitosa para resolver problem

as, demostrando de m

anera espectacular el poder de los principios evolutivos. S

e han utilizado algoritmos genéticos en una am

plia variedad de cam

pos para desarrollar soluciones a problemas tan difíciles o m

ás difíciles que los abordados por los diseñadores hum

anos. Adem

ás, las soluciones que consiguen son a menudo m

ás eficientes, m

ás elegantes o más com

plejas que nada que un ingeniero humano produciría. ¡E

n algunos casos, los algoritm

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

escribieron los algoritmos en prim

era instancia!

Métodos de rep

resentación

Antes de que un algoritm

o genético pueda ponerse a trabajar en un problema, se necesita un m

étodo para codificar las soluciones potenciales del problem

a de forma que una com

putadora pueda procesarlas. Un

enfoque común es codificar las soluciones com

o 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. O

tro método sim

ilar consiste en codificar las soluciones com

o cadenas de enteros o números decim

ales, donde cada posición, de nuevo,

Página 2 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

representa algún aspecto particular de la solución. Este m

étodo permite una m

ayor precisión y com

plejidad que el método com

parativamente restringido de utilizar sólo núm

eros binarios, y a menudo

``está intuitivamente m

ás cerca del espacio de problemas'' (F

leming y P

urshouse 2002[3], p 1.228).

Esta técnica se utilizó, por ejem

plo, en el trabajo de Steffen S

chulze-Krem

er, que escribió un algoritmo

genético para predecir la estructura tridimensional de una proteína, basándose en la secuencia de

aminoácidos que la com

ponen (Mitchell 1996[ 47], p. 62). E

l AG de S

chulze-Krem

er utilizaba números

reales para representar los famosos ``ángulos de torsión'' entre los enlaces peptídicos que conectan a los

aminoácidos. (U

na proteína está formada por una secuencia de bloques básicos llam

ados aminoácidos,

que se conectan como los eslabones de una cadena. U

na vez que todos los aminoácidos están enlazados,

la proteína se dobla formando una com

pleja estructura tridimensional, basada en cuáles am

inoácidos se atraen entre ellos y cuáles se repelen. L

a forma de una proteína determ

ina su función). Los algoritm

os genéticos para entrenar a las redes neuronales tam

bién utilizan a menudo este m

étodo de codificación.

Un tercer m

étodo consiste en representar a los individuos de un AG com

o cadenas de letras, donde cada letra, de nuevo, representa un aspecto específico de la solución. U

n ejemplo de esta técnica es el m

étodo basado en ``codificación gram

ática'' de Hiroaki K

itano, 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 problem

as (Mitchell 1996[ 47], p. 74).

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, sum

ar o restar al valor de un núm

ero una cantidad elegida al azar, o cambiar una letra por otra. (V

er 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 K

oza, de la Universidad de S

tanford, y denominada program

ación genética, representa a los program

as como estructuras de datos ram

ificadas llamadas árboles (K

oza et al. 2003[42], p. 35). E

n este método, los cam

bios aleatorios pueden generarse cambiado el operador o alterando

el valor de un cierto nodo del árbol, o sustituyendo un subárbol por otro.

Es im

portante señalar que los algoritmos evolutivos no necesitan representar las soluciones candidatas

como cadenas de datos de una longitud fija. A

lgunos las representan de esta manera, pero otros no; por

ejemplo, la ``codificación gram

atical'' de Kitano, explicada arriba, puede escalarse eficientem

ente para crear redes neuronales grandes y com

plejas, y los árboles de programación genética de K

oza pueden crecer arbitrariam

ente tanto como sea necesario para resolver cualquier problem

a que se les pida.

Figure: T

res sencillos árboles de programa del tipo utilizado norm

almente en la program

ación genética. D

ebajo se proporciona la expresión matem

ática que representa cada uno.

Página 3 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Métodos de selecció

n

Un algoritm

o 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 com

unes. Algunos

de estos métodos son m

utuamente exclusivos, pero otros pueden utilizarse en com

binación, algo que se hace a m

enudo.

�Selección elitista: se garantiza la selección de los m

iembros m

ás aptos de cada generación. (La

mayoría de los A

Gs no utilizan elitism

o puro, sino que usan una forma m

odificada por la que el individuo m

ejor, o algunos de los 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ás probabilidad de ser

seleccionados, pero no la certeza. �

Selección por rueda de ruleta: una form

a 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 com

petidores. (Conceptualm

ente, esto puede representarse como un juego de ruleta -

cada individuo obtiene una sección de la ruleta, pero los más aptos obtienen secciones m

ayores que las de los m

enos 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 increm

entarse la aptitud media de la población, la fuerza de la presión

selectiva también aum

enta y la función de aptitud se hace más discrim

inadora. 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, y los m

iembros 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 dom

inancia al principio a expensas de los m

enos aptos, lo que reduciría la diversidad genética de la població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.

�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 m

iembros

menos aptos de la siguiente generación. S

e 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 prim

eros niveles son más rápidas y m

enos discriminatorias, m

ientras que los que sobreviven hasta niveles m

ás altos son evaluados más rigurosam

ente. La ventaja de este

método es que reduce el tiem

po total de cálculo al utilizar una evaluación más rápida y m

enos selectiva para elim

inar a la mayoría de los individuos que se m

uestran poco o nada prometedores,

y sometiendo a una evaluación de aptitud m

ás rigurosa y computacionalm

ente más costosa sólo a

los que sobreviven a esta prueba inicial.

Métodos de ca

mbio

Una vez que la selección ha elegido a los individuos aptos, éstos deben ser alterados aleatoriam

ente con la esperanza de m

ejorar su aptitud para la siguiente generación. Existen dos estrategias básicas para

Página 4 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

llevar esto a cabo. La prim

era y más sencilla se llam

a mutación. A

l igual que una mutación en los seres

vivos cambia un gen por otro, una m

utación en un algoritmo genético tam

bién causa pequeñas alteraciones en puntos concretos del código de un idividuo.

El segundo m

étodo se llama cruzam

iento, e implica elegir a dos individuos para que intercam

bien segm

entos de su código, produciendo una ``descendencia'' artificial cuyos individuos son combinaciones

de sus padres. Este proceso pretende sim

ular el proceso análogo de la recombinación que se da en los

cromosom

as durante la reproducción sexual. Las form

as comunes de cruzam

iento incluyen al cruzam

iento 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 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 cruzam

iento uniforme, en el que el valor de una posición dada en el genom

a de la descendencia corresponde al valor en esa posición del genom

a de uno de los padres o al valor en esa posición del genom

a del otro padre, elegido con un 50% de probabilidad.

Otras técn

icas de reso

lución de problem

as

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 com

puterizada de problemas que en algunos aspectos son

similares a los algoritm

os genéticos. Esta sección explica algunas de estas técnicas, en qué se parecen a

los AGs y en qué se diferencian.

Figure: C

ruzamiento y m

utación. El diagram

a de arriba ilustra el efecto de estos dos operadores genéticos en los individuos de una población de cadenas de 8

bits. El diagram

a superior muestra a dos individuos llevando a cabo un cruzam

iento de un punto; el punto de intercam

bio se establece entre las posiciones quinta y sexta del genom

a, produciendo un nuevo individuo

que es híbrido de sus progenitores. E

l segundo diagram

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

Página 5 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Redes n

euronales

Una red neuronal es un m

étodo de resolución de problemas basado en un m

odelo informático de la

manera en que están conectadas las neuronas del cerebro. U

na red neuronal consiste en capas de unidades procesadoras, llam

adas nodos, unidas por conexiones direccionales: una capa de entrada, una capa de salida y cero o m

ás capas ocultas enmedio. S

e le presenta un patrón inicial de entrada a la capa de entrada, y luego los nodos que se estim

ulan transmiten una señal a los nodos de la siguiente capa a la

que están conectados. Si la sum

a de todas las entradas que entran en una de estas neuronas virtuales es mayor que el fam

oso umbral de activación de la neurona, esa neurona se activa, y transm

ite su propia señal a las neuronas de la siguiente capa. E

l patrón de activación, por tanto, se propaga hacia delante hasta que alcanza a la capa de salida, donde es devuelto com

o solución a la entrada presentada. Al igual

que en el sistema nervioso de los organism

os biológicos, las redes neuronales aprenden y afinan su rendim

iento a lo largo del tiempo, m

ediante la repetición de rondas en las que se ajustan sus umbrales,

hasta que la salida real coincide con la salida deseada para cualquier entrada dada. Este proceso puede

ser supervisado por un experimentador hum

ano, o puede correr automáticam

ente utilizando un algoritm

o de aprendizaje (Mitchell 1996[ 47], p. 52). S

e han utilizado algoritmos genéticos para construir

y entrenar a redes neuronales.

Ascen

so a colina (Hill C

limbing)

Sim

ilares a los algoritmos genéticos, aunque m

ás sistemáticos y m

enos aleatorios. Un algoritm

o de ascenso a colina com

ienza con una solución al problema a m

ano, normalm

ente elegida al azar. Luego, la

cadena se muta, y si la m

utació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 algoritm

o se repite hasta que no se pueda encontrar una m

utación que provoque un incremento en la aptitud de la

solución actual, y esta solución se devuelve como resultado (K

oza et al. 2003[42], p. 59). (Para entender

de dónde viene el nombre de esta técnica, im

agine que el espacio de todas las soluciones posibles de un cierto problem

a se representa como un paisaje tridim

ensional. Un conjunto de coordenadas en ese

paisaje representa una solución particular. Las soluciones m

ejores están a mayor altitud, form

ando

Figure: U

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

ero de cada neurona representa su um

bral de activación: sólo se excitará si recibe al menos esa cantidad de entradas. E

l diagram

a muestra cóm

o la red neuronal recibe una cadena de entrada y cómo la activación se extiende por la red

hasta producir una salida.

Página 6 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

colinas y picos; las que son peores están a menor altitud, form

ando valles. Un ``trepacolinas'' es, por

tanto, un algoritmo que com

ienza en un punto dado del paisaje y se mueve inexorablem

ente colina arriba). E

l algoritmo de ascenso a colina es lo que se conoce com

o algoritmo voraz, lo que significa que

siempre hace la m

ejor elección disponible en cada paso, con la esperanza de que de esta manera se

puede obtener el mejor resultado global. E

n contraste, los métodos com

o 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 m

ejor más adelante.

Recocido sim

ulado (sim

ulated annealing)

Otra técnica de optim

ización similar a los algoritm

os evolutivos se conoce como recocido sim

ulado. La

idea toma prestado su nom

bre del proceso industrial en el que un material se calienta por encim

a de su punto de fusión y luego se enfría gradualm

ente para eliminar defectos en su estructura cristalina,

produciendo un entramado de átom

os más estable y regular (H

aupt y Haupt 1998[ 34], p. 16). E

n el recocido sim

ulado, como en los algoritm

os genéticos, existe una función de aptitud que define un paisaje adaptativo; sin em

bargo, en lugar de una población de candidatas como en los A

Gs, sólo existe

una solución candidata. El recocido sim

ulado también añ ade el concepto de ``tem

peratura'', una cantidad num

érica global que disminuye gradualm

ente en el tiempo. E

n cada paso del algoritmo, la solución m

uta (lo que es equivalente a m

overse 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 m

ayor, se conserva la nueva solución. E

n caso contrario, el algoritmo tom

a la decisión de conservarla o descartarla en base a la tem

peratura. Si la tem

peratura es alta, como lo es al principio, pueden conservarse incluso cam

bios que causan decrem

entos significativos en la aptitud, y utilizarse como base para la siguiente ronda del

algoritmo, pero al ir dism

inuyendo la temperatura, el algoritm

o se va haciendo más y m

ás propenso a aceptar sólo los cam

bios que aumentan la aptitud. F

inalmente, la tem

peratura alzanca el cero y el sistem

a se ``congela''; cualquiera que sea la configuración que exista en ese punto se convierte en la solución. E

l recocido simulado tiene a m

enudo aplicaciones en la ingeniería del diseño, como determ

inar la disposición física de los com

ponentes en un chip informático (K

irkpatrick, Gelatt y V

ecchi 1983[40]).

Una breve historia de los AGs

Los prim

eros ejemplos de lo que hoy podríam

os llamar algoritm

os genéticos aparecieron a finales de los 50 y principios de los 60, program

ados en computadoras por biólogos evolutivos que buscaban

explícitamente realizar m

odelos 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: ``L

a computació n evolutiva estaba definitivam

ente en el aire en los días form

ativos de la computadora electrónica'' (M

itchell 1996[47], p.2). En 1962, investigadores com

o G.E.P. B

ox, G.J. F

riedman, W

.W. B

ledsoe y H.J. B

remerm

ann habían desarrollado independientemente

algoritmos inspirados en la evolución para optim

izació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. E

n esta técnica no había población ni cruzam

iento; un padre mutaba para producir un descendiente, y se conservaba el m

ejor de los dos, convirtiéndose en el padre de la siguiente ronda de m

utación (Haupt y H

aupt 1998[34], p.146). Versiones posteriores introdujeron la idea de población. L

as estrategias evolutivas todavía se emplean

hoy en día por ingenieros y científicos, sobre todo en Alem

ania.

El siguiente desarrollo im

portante en el campo vino en 1966, cuando L

.J. Fogel, A

.J. Owens y M

.J. W

alsh introdujeron en América una técnica que llam

aron programación evolutiva. E

n este método, las

Página 7 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

soluciones candidatas para los problemas se representaban com

o máquinas de estado finito sencillas; al

igual que en la estrategia evolutiva de Rechenberg, su algoritm

o funcionaba mutando aleatoriam

ente una de estas m

áquinas simuladas y conservando la m

ejor de las dos (Mitchell 1996[47], p.2; G

oldberg 1989[ 29], p.105). T

ambién al igual que las estrategias evolutivas, hoy en día existe una form

ulación más

amplia de la técnica de program

ación evolutiva que todavía es un área de investigación en curso. Sin

embargo, lo que todavía faltaba en estas dos m

etodologías era el reconocimiento de la im

portancia del cruzam

iento.

En una fecha tan tem

prana como 1962, el trabajo de John H

olland sobre sistemas adaptativos estableció

las bases para desarrollos posteriores; y lo que es más im

portante, Holland fue tam

bién el primero en

proponer explícitamente el cruzam

iento y otros operadores de recombinación. S

in embargo, el trabajo

fundamental en el cam

po de los algoritmos genéticos apareció en 1975, con la publicación del libro

``Adaptación en S

istemas N

aturales y Artificiales''. B

asado en investigaciones y papers anteriores del propio H

olland y de colegas de la Universidad de M

ichigan, este libro fue el primero en presentar

sistemática y rigurosam

ente el concepto de sistemas digitales adaptativos utilizando la m

utación, la selección y el cruzam

iento, simulando el proceso de la evolución biológica com

o estrategia para resolver problem

as. El libro tam

bién intentó colocar los algoritmos genéticos sobre una base teórica firm

e introduciendo el concepto de esquem

a (Mitchell 1996[47], p.3; H

aupt y Haupt 1998[34], p.147). E

se mism

o año, la importante tesis de K

enneth De Jong estableció el potencial de los A

Gs dem

ostrando que podían desenvolverse bien en una gran variedad de funciones de prueba, incluyendo paisajes de búsqueda ruidosos, discontinuos y m

ultimodales (G

oldberg 1989[29], p.107).

Estos trabajos fundacionales establecieron un interés m

ás generalizado en la computación evolutiva.

Entre principios y m

ediados de los 80, los algoritmos genéticos se estaban aplicando en una am

plia variedad de áreas, desde problem

as matem

áticos abstractos como el ``problem

a 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, reconocim

iento y clasificación de patrones y optimización estructural (G

oldberg 1989[ 29], p.128).

Al principio, estas aplicaciones eran principalm

ente teóricas. Sin em

bargo, al seguir proliferando la investigación, los algoritm

os genéticos migraron hacia el sector com

ercial, al cobrar importancia con el

crecimiento exponencial de la potencia de com

putación y el desarrollo de Internet. Hoy en día, la

computación evolutiva es un cam

po floreciente, y los algoritmos genéticos están ``resolviendo

problemas de interés cotidiano'' (H

aupt y Haupt 1998[34], p.147) en áreas de estudio tan diversas com

o la predicción en la bolsa y la planificación de la cartera de valores, ingeniería aeroespacial, diseño de microchips, bioquím

ica y biología molecular, y diseño de horarios en aeropuertos y líneas de m

ontaje. La potencia de la evolución ha tocado virtualm

ente cualquier campo que uno pueda nom

brar, modelando invisiblem

ente el mundo que nos rodea de incontables m

aneras, y siguen descubriéndose nuevos usos m

ientras la investigación sigue su curso. Y en el corazón de todo esto se halla nada m

ás que la sim

ple y poderosa idea de Charles D

arwin: 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 inm

enso poder y de aplicación casi ilimitada.

¿Cuáles so

n las ventajas de los AGs?

�El prim

er y más im

portante punto es que los algoritmos genéticos son intrínsecam

ente paralelos. La m

ayorí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 mism

o tiempo, y si la solución que descubren resulta

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

pezar de nuevo. Sin em

bargo, ya que los AGs tienen descendencia m

últiple, pueden explorar el espacio de soluciones en m

últiples direcciones a la vez. Si un cam

ino resulta ser un callejón sin salida,

Página 8 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

pueden eliminarlo fácilm

ente y continuar el tabajo en avenidas más prom

etedoras, dándoles una mayor probabilidad en cada ejecución de encontrar la solución.

Sin em

bargo, 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''). L

a cadena 01101010 es un miem

bro de este espacio. S

in embargo, tam

bién es un miem

bro 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 algoritm

o genético estaría sondeando cada uno de los espacios a los que pertenece. T

ras muchas evaluaciones, iría obteniendo un valor cada vez

más preciso de la aptitud m

edia de cada uno de estos espacios, cada uno de los cuales contiene muchos m

iembros. P

or tanto, un AG que evalúe explícitam

ente un número pequeño de individuos

está evaluando implícitam

ente un grupo de individuos mucho m

ás grande -de la mism

a manera

que un encuestador que le hace preguntas a un cierto miem

bro de un grupo étnico, religioso o social espera aprender algo acerca de las opiniones de todos los m

iembros 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. D

e la mism

a manera, el A

G puede dirigirse hacia el espacio con los individuos m

ás aptos y encontrar el m

ejor de ese grupo. En el contexto de los algoritm

os evolutivos, esto se conoce com

o teorema del esquem

a, y es la ventaja principal de los AGs sobre otros m

étodos de resolución de problem

as (Holland 1992[36], p. 68; M

itchell 1996[47], p. 28-29; Goldberg 1989

[ 29], p. 20). �

Debido al paralelism

o que les permite evaluar im

plícitamente m

uchos esquemas a la vez, los

algoritmos genéticos funcionan particularm

ente bien resolviendo problemas cuyo espacio de

soluciones potenciales es realmente grande -dem

asiado vasto para hacer una búsqueda exhaustiva en un tiem

po razonable. La m

ayoría de los problemas que caen en esta categoría se conocen com

o ``no lineales''. E

n un problema lineal, la aptitud de cada com

ponente es independiente, por lo que cualquier m

ejora en alguna parte dará como resultado una m

ejora en el sistema com

pleto. No es

necesario decir que hay pocos problemas com

o éste en la vida real. La no linealidad es la norm

a, donde cam

biar un componente puede tener efectos en cadena en todo el sistem

a, y donde cambios

múltiples que, individualm

ente, son perjudiciales, en combinación pueden conducir hacia m

ejoras en la aptitud m

ucho mayores. L

a no linealidad produce una explosión combinatoria: el espacio de

cadenas binarias de 1.000 dígitos puede examinarse exhaustivam

ente evaluando sólo 2.000 posibilidades si el problem

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

requiere evaluar 21.000 posibilidades -un número que, escrito, ocuparía m

ás de 300 dígitos. Afortunadam

ente, el paralelismo im

plícito de los AGs les perm

ite superar incluso este enorme

número de posibilidades, y encontrar con éxito resultados óptim

os o muy buenos en un corto

periodo de tiempo, tras m

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

adaptativo (Forrest 1993[24], p. 877). P

or ejemplo, un algoritm

o genético desarrollado en común

por ingenieros de General E

lectric y el Rensselaer P

olytechnic Institute produjo el diseño de la turbina de un m

otor 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 sistem

a 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 fundam

ental 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ía (Holland 1992[ 36], p. 72).

�Otra ventaja notable de los algoritm

os 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 tiem

po, o tiene muchos óptim

os locales. La m

ayoría de los problemas prácticos

tienen un espacio de soluciones enorme, im

posible de explorar exhaustivamente; el reto se

Página 9 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

convierte entonces en cómo evitar los óptim

os locales -soluciones que son mejores que todas las

que son similares a ella, pero que no son m

ejores que otras soluciones distintas situadas en algún otro lugar del espacio de soluciones. M

uchos 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 m

ejor de todas, aunque existan picos m

ás altos en algún otro lugar del mapa.

Los algoritm

os evolutivos, por otro lado, han demostrado su efectividad al escapar de los óptim

os locales y descubrir el óptim

o global incluso en paisajes adaptativos muy escabrosos y com

plejos. (D

ebe decirse que, en la realidad, a menudo no hay m

anera de decir si una cierta solución a un problem

a es el óptimo global o sólo un óptim

o local muy alto. S

in embargo, aunque un A

G no

devuelva siempre una solución perfecta y dem

ostrable a un problema, casi siem

pre puede devolver al m

enos una muy buena solución). T

odos los cuatro componentes principales de los

AGs -paralelism

o, selección, mutación y cruzam

iento- trabajan juntos para conseguir esto. Al

principio, el AG genera una población inicial diversa, lanzando una ``red'' sobre el paisaje

adaptativo. (Koza 2003[42], p. 506) com

para esto con un ejército de paracaidistas cayendo sobre el paisaje del espacio de búsqueda de un problem

a, cada uno de ellos con órdenes de buscar el pico m

ás alto). Pequeñas m

utaciones permiten a cada individuo explorar sus proxim

idades, mientras que la selección enfoca el progreso, guiando a la descendencia del algoritm

o cuesta arriba hacia zonas m

ás prometedoras del espacio de soluciones (H

olland 1992[36], p. 68). Sin em

bargo, el cruzamiento es el elem

ento clave que distingue a los algoritmos genéticos de los

otros métodos com

o los trepacolinas y el recocido simulado. S

in 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. Sin em

bargo, con el cruzam

iento 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 m

ezclarse y com

binarse, con el potencial de producir una descendencia que tenga las virtudes de sus dos padres y ninguna de sus debilidades. E

ste punto está ilustrado en Koza et al. 1999[41], p. 486,

donde los autores analizan el problema de sintetizar un filtro de paso bajo utilizando program

ació n genética. E

n una generación se seleccionaron dos circuitos progenitores para llevar a cabo el cruzam

iento; un padre tenía una buena topología (componentes com

o inductores y condensadores colocados en el sitio correcto) pero m

alos tamaños (valores dem

asiado bajos de inductancia y capacidad para los com

ponentes). El otro padre tenía m

ala topología pero buenos tamaños. E

l resultado de aparearlos m

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

padre y los buenos tamaños del otro, dando com

o resultado una mejora sustancial de la aptitud

sobre sus dos padres. El problem

a de encontrar el óptimo global en un espacio con m

uchos óptimos locales tam

bién se conoce com

o el dilema de la exploración versus explotación, ``un problem

a clásico de todos los sistem

as que pueden adaptarse y aprender'' (Holland 1992[ 36], p. 69). U

na vez que un algoritmo

(o un diseñador humano) ha encontrado una estrategia para resolver problem

as que parece funcionar satisfactoriam

ente, ¿debería centrarse en hacer el mejor uso de esa estrategia, o buscar

otras? Abandonar una estrategia de probada solvencia para buscar otras nuevas casi garantiza que

supondrá una pérdida y degradación del rendimiento, al m

enos 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. D

e nuevo, los algoritmos gené ticos han

demostrado ser m

uy buenos en dar con este equilibrio y descubrir buenas soluciones en un tiempo

y esfuerzo computacional razonables.

�Otro área en el que destacan los algoritm

os genéticos es su habilidad para manipular m

uchos parám

etros simultáneam

ente (Forrest 1993[24], p. 874). M

uchos problemas de la vida real no

Página 10 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

pueden definirse en términos de un único valor que hay que m

inimizar o m

aximizar, sino que

deben expresarse en términos de m

últiples objetivos, a menudo involucrando contrapartidas: uno

sólo puede mejorar a expensas de otro. L

os AGs son m

uy buenos resolviendo estos problemas: en

particular, su uso del paralelismo les perm

ite producir múltiples soluciones, igualm

ente buenas, al mism

o problema, donde posiblem

ente una solución candidata optimiza un parám

etro y otra candidata optim

iza uno distinto (Haupt y H

aupt 1998[34], p. 17), 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ám

etro 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 óptim

o paretiano o no dominada (C

oello 2000[18], p. 112). �

Finalm

ente, una de las cualidades de los algoritmos genéticos que, a prim

era vista, puede parecer un desastre, resulta ser una de sus ventajas: a saber, los A

Gs no saben nada de los problem

as que deben resolver. E

n lugar de utilizar información específica conocida a priori para guiar cada paso

y realizar cambios con un ojo puesto en el m

ejoramiento, com

o hacen los diseñadores humanos,

son ``relojeros ciegos'' (Daw

kins 1996[20]); realizan cambios aleatorios en sus soluciones

candidatas y luego utilizan la función de aptitud para determinar si esos cam

bios producen una mejora.

La virtud de esta técnica es que perm

ite a los algoritmos genéticos com

enzar con una mente

abierta, por así decirlo. Com

o sus decisiones están basadas en la aleatoriedad, todos los caminos

de búsqueda posibles están abiertos teóricamente a un A

G; en contraste, cualquier estrategia de

resolución de problemas que dependa de un conocim

iento previo, debe inevitablemente com

enzar descartando m

uchos caminos a priori, perdiendo así cualquier solución novedosa que pueda existir

(Koza et al. 1999[41], p. 547). L

os AGs, al carecer de ideas preconcebidas basadas en creencias

establecidas sobre ``cómo deben hacerse las cosas'' o sobre lo que ``de ninguna m

anera podría funcionar'', los A

Gs no tienen este problem

a. De m

anera similar, cualquier té cnica que dependa de

conocimiento previo fracasará cuando no esté disponible tal conocim

iento, pero, de nuevo, los AGs no se ven afectados negativam

ente por la ignorancia (Goldberg 1989[ 29], p. 23). M

ediante sus com

ponentes de paralelismo, cruzam

iento y mutación, pueden viajar extensam

ente por el paisaje adaptativo, explorando regiones que algoritm

os producidos con inteligencia podrían no haber tenido en cuenta, y revelando potencialm

ente soluciones de asombrosa e inesperada

creatividad que podrían no habérseles ocurrido nunca a los diseñadores humanos. U

n ejemplo

muy gráfico de esto es el redescubrim

iento, mediante la program

ación genética, del concepto de retroalim

entación negativa -un principio crucial para muchos com

ponentes electrónicos im

portantes 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 (Koza et al. 2003[42], p. 413). P

or 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 so

n las lim

itaciones d

e los AGs?

Aunque los algoritm

os genéticos han demostrado su eficiencia y potencia com

o estrategia de resolución de problem

as, no son la panacea. Los A

Gs tienen ciertas lim

itaciones; sin embargo, se dem

ostrará que todas ellas pueden superarse y que ninguna de ellas afecta a la validez de la evolución biológica.

�La prim

era y más im

portante consideración al crear un algoritmo genético es definir una

representación del problema. E

l lenguaje utilizado para especificar soluciones candidatas debe ser robusto; es decir, debe ser capaz de tolerar cam

bios aleatorios que no produzcan constantemente

errores fatales o resultados sin sentido.

Página 11 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Hay dos m

aneras principales para conseguir esto. La prim

era, utilizada por la mayoría de los

algoritmos genéticos, es definir a los individuos com

o listas de números -binarios, enteros o

reales- donde cada número representa algún aspecto de la solución candidata. S

i los individuos son cadenas binarias, un 0 o 1 podría significar la ausencia o presencia de una cierta característica. Si son listas de núm

eros, estos números podrían representar m

uchas 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 com

ponentes 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 im

plica cambiar estos núm

eros, cambiar bits o sum

ar o restar valores aleatorios. En este

caso, el propio código del programa no cam

bia; 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 program

a sí cambia. C

omo ya se

dijo en la sección ``Métodos de representación'', la P

G representa a los individuos com

o árboles de código ejecutables que pueden m

utar cambiando o intercam

biando subárboles. Ambos

méetodos producen representaciones robustas ante la m

utación, y pueden representar muchos

tipos diferentes de problemas y, com

o se dice en la sección ``Algunos ejem

plos específicos'', am

bas han tenido un éxito considerable. El problem

a de representar a las soluciones candidatas de manera robusta no surge en la

naturaleza, porque el método de representación utilizado por la evolución, a saber, el código

genético, es inherentemente robusto: con m

uy 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. P

or lo tanto, virtualm

ente, cualquier cambio en los genes de un individuo siem

pre producirá un resultado inteligible, y por tanto las m

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

mejora. E

sto entra en contraste con los lenguajes creados por el hombre com

o el inglés, donde el núm

ero de palabras con significado es pequeño comparado con el núm

ero total de formas en las

que se pueden combinar las letras del alfabeto, y por tanto, es probable que un cam

bio aleatorio en una frase en inglés produzca un sinsentido.

�El problem

a de cómo escribir la función de aptitud debe considerarse cuidadosam

ente para que se pueda alcanzar una m

ayor aptitud y verdaderamente signifique una solución m

ejor para el problem

a dado. Si se elige m

al 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 problem

a, o puede acabar resolviendo el problem

a equivocado. (Esta últim

a situación se describe a veces como la tendencia

del AG a ``engañar'', aunque en realidad lo que está pasando es que el A

G está haciendo lo que se

le pidió hacer, no lo que sus creadores pretendían que hiciera). Se puede encontrar un ejem

plo de esto en G

raham-R

owe 2002[30], donde unos investigadores utilizaron un algoritm

o evolutivo en conjunción con una serie de chips reprogram

ables, haciendo que la función de aptitud recom

pensara al circuito en evolución por dar como salida una señal oscilatoria. A

l final del experim

ento, se producía efectivamente una señal oscilatoria -pero en lugar de actuar com

o un osculador, com

o pretendían los investigadores, ¡descubrieron que el circuito se había convertido en un receptor de radio que estaba recibiendo y retransm

itiendo una señal oscilatoria de un com

ponente electrónico cercano! Sin em

bargo, esto no es un problema en la naturaleza. E

n 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 im

portar qué adaptaciones hagan esto posible. Los organism

os que se reproducen con m

ás abundancia que sus competidores están m

ás adaptados; los que fracasan en reproducirse no están adaptados.

Página 12 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

�Adem

ás de elegir bien la función de aptitud, también deben elegirse cuidadosam

ente los otros parám

etros de un AG -el tam

año de la población, el ritmo de m

utación y cruzamiento, el tipo y

fuerza de la selección. Si el tam

año de la población es demasiado pequeño, puede que el algoritm

o genético no explore suficientem

ente el espacio de soluciones para encontrar buenas soluciones consistentem

ente. Si el ritm

o de cambio genético es dem

asiado alto o el sistema de selección se

escoge inadecuadamente, puede alterarse el desarrollo de esquem

as beneficiosos y la población puede entrar en catástrofe de errores, al cam

biar demasiado rápido para que la selección llegue a

producir convergencia. Los seres vivos tam

bién se enfrentan a dificultades similares, y la evolución se ha encargado de

ellas. Es cierto que si el tam

año de una población cae hacia un valor muy bajo, los ritm

os de mutación son m

uy altos o la presión selectiva es demasiado fuerte (una situación así podría ser

resultado de un cambio am

biental drástico), entonces la especie puede extinguirse. La solución ha

sido ``la evolución de la evolutividad'' -las adaptaciones que alteran la habilidad de una especie para adaptarse. U

n ejemplo. L

a mayoría de los seres vivos han evolucionado una elaborada

maquinaria celular que com

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

manteniendo su ritm

o de mutación a unos niveles aceptablem

ente bajos; a la inversa, en tiempos

de fuerte presión ambiental, algunas especies de bacterias entran en un estado de hiperm

utació n en el que el ritm

o de errores en la replicación del ADN aum

enta bruscamente, aum

entando la probabilidad de que se descubrirá una m

utación compensatoria. P

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

e diversidad y las adaptaciones altamente com

plejas de los seres vivos actuales m

uestran que, en general, la evolución es una estrategia exitosa. Igualmente,

las aplicaciones diversas y los impresionantes resultados de los algoritm

os genéticos demuestran

que son un campo de estudio poderoso y que m

erece la pena. �

Un problem

a con el que los algoritmos genéticos tienen dificultades son los problem

as con las funciones de aptitud ``engañosas'' (M

itchell 1996[ 47], p. 125), en las que la situación de los puntos m

ejorados ofrecen información engañosa sobre dónde se encuentra probablem

ente el óptim

o global. Por ejem

plo: imagine un problem

a en el que el espacio de búsqueda esté com

puesto por todas las cadenas binarias de ocho caracteres, y en el que la aptitud de cada individuo sea directam

ente proporcional al número de unos en él -es decir, 00000001 sería m

enos apto que 00000011, que sería m

enos apto que 00000111, etcétera -, con dos excepciones: la cadena 11111111 resulta tener una aptitud m

uy baja, y la cadena 00000000 resulta tener una aptitud m

uy alta. En este problem

a, un AG (al igual que la m

ayoría de los algoritmos) no tendría

más probabilidad de encontrar un óptim

o global que una búsqueda aleatoria. La solución a este problem

a es la mism

a para los algoritmos genéticos y la evolución biológica: la

evolución no es un proceso que deba encontrar siempre el óptim

o global. Puede funcionar casi

igual de bien alcanzando la cima de un óptim

o local alto y, para la mayoría de las situaciones, eso

será suficiente, incluso aunque el óptimo global no pueda alcanzarse fácilm

ente desde ese punto. La evolución es com

o un ``satisfactor'' -un algoritmo que entrega una solución ``suficientem

ente buena'', aunque no necesariam

ente la mejor solución posible, dada una cantidad razonable de

tiempo y esfuerzo invertidos en la búsqueda. L

a ``FAQ de la evidencia de diseño im

provisado en la naturaleza'' proporciona ejem

plos de la naturaleza con estos resultados. (Tam

bién hay que tener en cuenta que pocos o ningún problem

a real es tan engañoso como el ejem

plo algo forzado dado arriba. N

ormalm

ente, la situación de las mejoras locales proporciona alguna inform

ación sobre la situación del óptim

o global). �

Un problem

a muy conocido que puede surgir con un A

G se conoce com

o convergencia prem

atura. Si un individuo que es m

ás apto que la mayoría de sus com

petidores emerge m

uy pronto en el curso de la ejecución, se puede reproducir tan abundantem

ente que merm

e la diversidad de la población dem

asiado pronto, provocando que el algoritmo converja hacia el

óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a

Página 13 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

fondo para encontrar el óptimo global (F

orrest 1993[24], p. 876; Mitchell 1996[47], p. 167). E

sto es un problem

a especialmente com

ún en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritm

o de reproducción puede provocar que un genotipo se haga dominante sobre los

otros. Los m

étodos más com

unes implem

entados por los investigadores en AGs para solucionar este

problema im

plican controlar la fuerza selectiva, para no proporcionar tanta ventaja a los individuos excesivam

ente 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 de

selección escalada son el escalado sigma, en el que la reproducción se basa en una com

paración estadística de la aptitud m

edia de la población, y la selección de Boltzm

ann, en la que la fuerza selectiva aum

enta durante la ejecución de manera sim

ilar a la variable ``temperatura'' en el

recocido simulado (M

itchell 1996[47], p. 168). La convergencia prem

atura ocurre en la naturaleza (los biólogos la llaman deriva genética). E

sto no debe sorprender; com

o ya se dijo arriba, la evolución, como estrategia de resolución de

problemas, no está obligada a encontrar la m

ejor solución, sólo una que sea lo bastante buena. Sin

embargo, en la naturaleza, la convergencia prem

atura es menos com

ún, ya que la mayoría de las

mutaciones beneficiosas en los seres vivos sólo producen m

ejoras en la aptitud pequeñas e increm

entales; son raras las mutaciones que producen una ganancia de aptitud tan grande que

otorgue a sus poseedores una drástica ventaja reproductiva. �

Finalm

ente, varios investigadores (Holland 1992[36], p. 72; F

orrest 1993[24], p. 875; Haupt y

Haupt 1998[34], p. 18) aconsejan no utilizar algoritm

os genéticos en problemas resolubles de

manera analítica. N

o es que los algoritmos genéticos no puedan encontrar soluciones buenas para

estos problemas; sim

plemente es que los m

étodos analíticos tradicionales consumen m

ucho menos

tiempo y potencia com

putacional que los AGs y, a diferencia de los A

Gs, a m

enudo está dem

ostrado matem

áticamente que ofrecen la única solución exacta. P

or supuesto, como no existe

una solución matem

ática perfecta para ningún problema de adaptación biológica, este problem

a no aparece en la naturaleza.

Algunos ejem

plos esp

ecíficos de AG

Mientras el poder de la evolución gana reconocim

iento cada vez más generalizado, los algoritm

os genéticos se utilizan para abordar una am

plia variedad de problemas en un conjunto de cam

pos sum

amente diverso, dem

ostrando claramente su capacidad y su potencial. E

sta sección analizará algunos de los usos m

ás notables en los que han tomado parte.

Acústica

Sato et al. 2002[58] utilizaron algoritm

os genéticos para diseñar una sala de conciertos con propiedades acústicas óptim

as, maxim

izando la calidad del sonido para la audiencia, para el director y para los músicos del escenario. E

sta tarea implica la optim

ización simultánea de m

últiples variables. Com

enzando con una sala con forma de caja de zapatos, el A

G de los autores produjo dos soluciones no

dominadas, am

bas descritas como ``con form

a de hoja'' (p. 526). Los autores afirm

an que estas soluciones tienen proporciones sim

ilares al Grosser M

usikvereinsaal de Viena, el cual está considerado

generalmente com

o una de las mejores -si no la m

ejor- salas de conciertos del mundo, en térm

inos de propiedades acústicas.

Porto, F

ogel y Fogel 1995[51] utilizaron program

ación evolutiva para adiestrar a redes neuronales para

Página 14 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

distinguir entre reflexiones sonoras desde distintos tipos de objetos: esferas metálicas hechas por el

hombre, m

ontañas submarinas, peces y plantas, y ruido aleatorio de fondo. T

ras 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 alarm

a'' (p. 21). Esta red evolucionada igualó las prestaciones de otra red

desarrollada mediante recocido sim

ulado, y superó consistentemente a redes entrenadas m

ediante propagación hacia atrás, las cuales ``se atascaban repetidam

ente en conjuntos de pesos subóptimos que

no producían resultados satisfactorios'' (p. 21). En contraste, am

bos métodos estocásticos dem

ostraron su capacidad para superar estos óptim

os locales y producir redes más pequeñas, efectivas y robustas;

pero los autores sugieren que el algoritmo evolutivo, a diferencia del recocido sim

ulado, opera sobre una población, y por tanto se beneficia de la inform

ación global sobre el espacio de búsqueda, conduciendo potencialm

ente hacia un rendimiento m

ayor a la larga.

Tang et al. 1996[62] analizan los usos de los algoritm

os genéticos en el campo de la acústica y el

procesamiento de señales. U

n área de interés particular incluye el uso de AGs para diseñar sistem

as de Control A

ctivo de Ruido (C

AR), que elim

inan el sonido no deseado produciendo ondas sonoras que interfieren destructivam

ente con el ruido. Esto es un problem

a de múltiples objetivos que requiere el

control y la colocación precisa de múltiples altavoces; los A

Gs se han utilizado en estos sistem

as tanto para diseñar los controladores com

o para encontrar la colocación óptima de los altavoces, dando com

o resultado una ``atenuación efectiva del ruido'' (p. 33) en pruebas experim

entales.

Ingeniería

aeroespacial

Obayashi et al. 2000[49] utilizaron un algoritm

o genético de múltiples objetivos para diseñar la form

a del ala de un avión supersónico. H

ay tres consideraciones principales que determinan la configuración

del ala -minim

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

inimizar la

resistencia a velocidades subsónicas y minim

izar la carga aerodinámica (la fuerza que tiende a doblar el

ala). Estos objetivos son m

utuamente exclusivos, y optim

izarlos todos simultá neam

ente requiere realizar contrapartidas.

El crom

osoma de este problem

a es una cadena de 66 nú meros reales, cada uno de los cuales corresponde

a un aspecto específico del ala: su forma, su grosor, su torsión, etcétera. S

e simuló una evolución con

selección elitista durante 70 generaciones, con un tamaño de población de 64 individuos. A

l final de este proceso había varios individuos paretianos, cada uno representando una solución no dom

inada del problem

a. El artículo com

enta que estos individuos ganadores tenían características ``físicamente

razonables'', señalando la validez de la técnica de optimizació n (p. 186). P

ara evaluar mejor la calidad de

las soluciones, las seis mejores fueron com

paradas con un diseño de ala supersónica producido por el Equipo de D

iseño SST del L

aboratorio Aeroespacial N

acional de Japón. Las seis fueron com

petitivas, con valores de resistencia y carga aproxim

adamente iguales o m

enores a los del ala diseñada por hum

anos; 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 A

G son sim

ilares a un diseño llamado ``ala flecha'',

sugerido por primera vez a finales de los años 50, pero que finalm

ente fue abandonado en favor del diseño m

ás convencional con forma de delta.

En un artículo posterior (S

asaki et al. 2001[57]), los autores repitieron el experimento añadiendo un

cuarto objetivo, a saber, minim

izar el mom

ento de torsión (un conocido problema en los diseños de alas

flecha en el vuelo supersónico). Tam

bién se añadieron puntos de control adicionales para el grosor al conjunto de variables de diseño. T

ras 75 generaciones de evolución, se compararon dos de las m

ejores soluciones paretianas con el diseño de ala que el L

aboratorio Aeroespacial N

acional japonés realizó para el avión supersónico experim

ental NEXST-1. S

e descubrió que ambos diseños (adem

ás de un diseño

Página 15 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

óptimo de la sim

ulación anterior, explicada arriba) eran físicamente razonables y superiores al diseño

del LAN en los cuatro objetivos.

William

s, Crossley y L

ang 2001[64] aplicaron algoritmos genéticos a la tarea de situar órbitas de

satélites para minim

izar los apagones de cobertura. Mientras la tecnología de telecom

unicaciones sigue progresando, los hum

anos somos cada vez m

ás dependientes de las funciones vitales que realizan los satélites en órbita alrededor de la T

ierra, 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 am

plias secciones del planeta al mism

o 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. E

s más económ

ico colocar satélites en órbitas bajas, en algunos casos a sólo unos pocos cientos de kilóm

etros; pero, a causa de la curvatura 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. E

l reto consiste en colocar las órbitas de los satélites para minim

izar este tiem

po muerto. E

sto es un problema m

ulti-objetivo que implica la m

inimización de el tiem

po 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 mutuam

ente exclusivos.

Cuando se utilizó el A

G en este problem

a, los resultados que evolucionaron para constelaciones de tres, cuatro y cinco satélites eran extraños, configuraciones orbitales m

uy asimétricas, con los satélites

colocados alternando huecos grandes y pequeños, en lugar de huecos de igual tamaño com

o habrían hecho las técnicas convencionales. S

in embargo, esta solución redujo significativam

ente los tiempos

medio y m

áximo de apagón, en algunos casos hasta en 90 m

inutos. En un artículo periodístico, el D

r. W

illiam C

rossley señaló que ``ingenieros con años de experiencia aeroespacial quedaorn sorprendidos con el rendim

iento ofrecido por el diseño no convencional''.

Keane y B

rown 1996[43] utilizadon un A

G 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ém

ur humano, no utiliza m

ás material que el diseño de brazo estándar, pero es

ligera, fuerte y muy superior a la hora de am

ortiguar las vibraciones perjudiciales, como confirm

aron las pruebas reales del producto final. Y

sin embargo ``N

inguna inteligencia produjo los diseños. Sim

plemente evolucionaron'' (P

etit 1998[43]). Los autores del artículo com

entan además que su A

G

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

ente costosa de la sim

ulación, y la población no se había estancado todavía. Haber proseguido la ejecución durante m

ás generaciones habría producido indudablem

ente mayores m

ejoras de rendimiento.

Página 16 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Finalm

ente, como inform

a Gibbs 1996[25], L

ockheed Martin ha utilizado un algoritm

o genético para producir m

ediante evolución una serie de maniobras para m

over una nave espacial de una orientación a otra, dentro del 2%

del tiempo m

ínimo teórico para tales m

aniobras. La solución evolucionada era un

10% m

ás rápida que una solución producida manualm

ente por un experto para el mism

o problema.

Astro

nomía y astro

física

Charbonneau 1995[12] sugiere la utilidad de los A

Gs para problem

as de astrofísica, aplicándolos a tres problem

as de ejemplo: obtener la curva de rotación de una galaxia basándose en las velocidades

rotacionales observadas de sus componentes, determ

inar el periodo de pulsación de una estrella variable basándose en series de datos tem

porales, y sacar los valores de los parámetros críticos de un m

odelo magnetohidrodinám

ico del viento solar. Son tres difíciles problem

as no lineales y multidim

ensionales.

El algoritm

o genético de Charbonneau, P

IKAIA

, utiliza selección generacional y proporcional a la aptitud, junto con elitism

o, para asegurar que el mejor individuo se copia una vez hacia la siguiente

generación sin ninguna modificación. P

IKAIA

tiene un ritmo de cruzam

iento de 0,65 y un ritmo de

mutación variable que se pone a 0,003 inicialm

ente y luego aumenta gradualm

ente, mientras la

población se aproxima a la convergencia, para m

antener la variabilidad en el acervo genético.

En el problem

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

bas 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. E

n el problema de la

serie temporal, el A

G fue im

presionantemente exitoso, generando un ajuste de los datos de gran calidad,

aunque otros problemas m

ás difíciles no se ajustaron tan bien (aunque, como señala C

harbonneau, estos problem

as son igualmente difíciles de resolver con técnicas convencionales). E

l artículo sugiere que un AG híbrido que em

plee tanto evolución artificial como técnicas analíticas estándar, podría funcionar

mejor. F

inalmente, en el problem

a de obtener los seis parámetros críticos del viento solar, el A

G

determinó con éxito el valor de tres con una precisió n de m

enos del 0,1% y los otros tres con precisiones

entre el 1 y el 10%. (A

unque siempre serían preferibles unos errores experim

entales menores para estos

tres parámetros, C

harbonneau señala que no existe ningún otro método eficiente y robusto para resolver

experimentalm

ente un problema no lineal 6-dim

ensional de este tipo; un método de gradiente conjugado

Figure: U

n brazo tridimensional optim

izado genéticam

ente, con una respuesta mejorada a la

frecuencia (adaptado de http://w

ww.soton.ac.uk/~ajk/truss/w

elcome.htm

l).

Página 17 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

funciona ``siempre que se pueda proporcionar un valor inicial m

uy acertado'' (p. 323). En contraste, los

AGs no requieren un conocim

iento del dominio tan bien afinado).

Basándose en los resultados obtenidos hasta ahora, C

harbonneau sugiere que los AGs pueden y deben

encontrar uso en otros problemas difíciles de astrofísica, en particular, problem

as inversos como las

imágenes por D

oppler y las inversiones heliosísmicas. P

ara terminar, C

harbonneau sostiene que los AGs

son un ``contendiente poderoso y prometedor'' (p. 324) en este cam

po, del que se puede esperar que com

plemente (no sustituya) a las técnicas tradicionales de optim

ización, y concluye que ``el punto decisivo, si es que tiene que haber alguno, es que los algoritm

os genéticos funcionan, y a menudo

colosalmente bien'' (p. 325).

Química

Un pulso láser ultracorto de alta energía puede rom

per moléculas com

plejas en moléculas m

ás sencillas, un proceso con aplicaciones im

portantes en la química orgánica y la m

icroelectrónica. Los productos

específicos de una reacción así pueden controlarse modulando la fase del pulso láser. S

in embargo, para

moléculas grandes, obtener la form

a del pulso deseado de manera analítica es dem

asiado difícil: los cálculos son dem

asiado 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[6] resolvieron este problem

a utilizando un algoritmo evolutivo para diseñar la form

a del pulso. E

n lugar de introducir información com

pleja, específica del problema, sobre las caracterí sticas

cuánticas de las moléculas iniciales, para diseñar el pulso conform

e a las especificaciones, el AE dispara

un pulso, mide las proporciones de las m

oléculas producto resultantes, muta aleatoriam

ente las características del rayo con la esperanza de conseguir que estas proporciones se acerquen a la salida deseada, y el proceso se repite. (E

n lugar de afinar directamente las características del rayo láser, el A

G

de los autores representa a los individuos como un conjunto de 128 núm

eros, 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. D

e nuevo, no se necesita un conocim

iento específico del problema sobre las propiedades del láser o de los

productos de la reacción). Los autores afirm

an que su algoritmo, cuando se aplica a dos sustancias de

muestra, ``encuentra autom

áticamente la m

ejor configuración... no importa lo com

plicada que sea la respuesta m

olecular'' (p. 921), demostrando un ``control coherente autom

atizado de los productos que son quím

icamente diferentes uno del otro y de la m

olécula padre'' (p. 921).

A principios y m

ediados de los 90, la amplia adopción de una novedosa técnica de diseño de fárm

acos, llam

ada química com

binatoria, revolucionó la industria farmacéutica. C

on este método, en lugar de la

síntesis precisa y meticulosa de un sólo com

puesto de una vez, los bioquímicos m

ezclan deliberadam

ente una gran variedad de reactivos para producir una variedad aún mayor de productos -

cientos, miles o m

illones de compuestos diferentes en cada rem

esa- que luego pueden aislarse rápidam

ente para su actividad bioquímica. H

ay 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 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. E

l diseño basado en los productos es m

ás difícil y complejo, pero se ha dem

ostrado 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 departam

ento de investigación y desarrollo de GlaxoS

mithK

line, Gillet

2002[26] describe el uso de un algoritmo genético m

ultiobjetivo para el diseño basado en los productos de bibliotecas com

binatorias. Al elegir los com

ponentes que van en una biblioteca particular, deben considerarse características com

o la diversidad y peso molecular, el coste de los sum

inistros, la

Página 18 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

toxicidad, la absorción, la distribución y el metabolism

o. Si el objetivo es encontrar m

olé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), tam

bién se puede tener en cuenta la similaridad estructural. E

ste artículo presenta un enfoque multiobjetivo, donde puede desarrollarse un conjunto de resultados paretianos que m

aximicen o

minim

icen cada uno de estos objetivos. El autor concluye diciendo que el A

G fue capaz de satisfacer

simultáneam

ente los criterios de diversidad molecular y eficiencia sintética m

áxima, y tam

bién fue capaz de encontrar m

oléculas parecidas a un fármaco que eran ``m

uy similares a las m

oléculas objetivo dadas, tras explorar una fracción m

uy pequeña del espacio de búsqueda total'' (p. 378).

En un artículo relacionado, G

len y Payne 1995[ 28] describen el uso de algoritm

os genéticos para diseñar autom

áticamente m

oléculas nuevas desde cero que se ajustan a un conjunto de especificaciones dado. Dada una población inicial, bien generada aleatoriam

ente o utilizando la sencilla molécula del etano

como sem

illa, el AG añade, elim

ina y altera aleatoriamente átom

os y fragmentos m

oleculares con el objetivo de generar m

oléculas que se ajusten a los requisitos dados. El A

G puede optim

izar sim

ultáneamente un gran núm

ero de objetivos, incluyendo el peso molecular, el volum

en molecular, el

número de enlaces, el núm

ero de centros quirales, el número de átom

os, el número de enlaces rotables,

la polarizabilidad, el mom

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

deseadas. Basándose en pruebas experim

entales, incluyendo un difícil problema de optim

ización que im

plicaba la generación de moléculas con propiedades sim

ilares a la ribosa (un componente del azúcar

imitado a m

enudo en los fármacos antivirales), los autores concluyen que el A

G es un ``excelente

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

generar ``un conjunto diverso de estructuras posibles'' (p. 182). Continúan afirm

ando: ``Es de interés

especial la poderosa capacidad de optimización del algoritm

o genético, incluso con tamaños de

población relativamente pequeños'' (p. 200). C

omo prueba de que estos resultados no son sim

plemente

teóricos, Lem

ley 2001[ 45] informa de que la em

presa Unilever ha utilizado algoritm

os genéticos para diseñar nuevos com

ponentes antimicrobianos para su uso en productos de lim

pieza, algo que ha patentado.

Ingeniería

eléctrica

Una m

atriz de puertas programable en cam

po (Field P

rogrammable G

ate Array, o F

PGA), es un tipo

especial de placa de circuito con una matriz de celdas lógicas, cada una de las cuales puede actuar com

o cualquier tipo de puerta lógica, interconectado con conexiones flexibles que pueden conectar celdas. Estas dos funciones se controlan por softw

are, así que simplem

ente 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 D

r. Adrian T

hompson ha explotado este dispositivo, en conjunción con los principios de la evolución,

para producir un prototipo de circuito reconocedor de voz que puede distinguir y responder a órdenes habladas utilizando sólo 37 puertas lógicas -una tarea que se habría considerado im

posible para cualquier ingeniero hum

ano. Generó cadenas aleatorias de bits de ceros y unos y las utilizó com

o configuraciones de la F

PGA, seleccionando los individuos m

ás aptos de cada generación, reproduciéndolos y m

utándolos aleatoriamente, intercam

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

u objetivo era evolucionar un dispositivo que pudiera en principio discrim

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

Su objetivo se alcanzó en 3.000 generaciones, pero el éxito fue m

ayor de lo que había anticipado. El

sistema que evolucionó utilizaba m

uchas menos celdas que cualquier cosa que pudiera haber diseñado

un ingeniero humano, y ni siquiera necesita del com

ponente más crítico de los sistem

as diseñados por

Página 19 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

humanos -un reloj. ¿C

ómo funcionaba? T

hompson no tiene ni idea, aunque ha rastreado la señal de

entrada a través de un complejo sistem

a de bucles realimentados del circuito evolucionado. D

e 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 m

anera -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 electrom

agnético de estas celdas para alcanzar su solución, pero el funcionam

iento exacto de la compleja e intrincada estructura evolucionada sigue

siendo un misterio (D

avidson 1997[19]).

Altshuler y L

inden 1997[ 2] utilizaron un algoritmo genético para evolucionar antenas de alam

bre con propiedades especificadas a priori. L

os autores señalan que el diseño de tales antenas es un proceso im

preciso, comenzando con las propiedades deseadas y luego determ

inando la forma de la antena

mediante ``conjeturas... intuición, experiencia, ecuaciones aproxim

adas o estudios empíricos'' (p. 50).

Esta técnica requiere m

ucho tiempo, a m

enudo no produce resultados óptimos y tiende a funcionar bien

sólo con diseños simétricos y relativam

ente simples. E

n contraste, con el método del algoritm

o gené tico, el ingeniero especifica las propiedades electrom

agnéticas de la antena, y el AG sintetiza

automáticam

ente una configuración que sirva.

Altshuler y L

inden utilizaron su AG para diseñar una antena de siete segm

entos polarizada circularm

ente con una cobertura hemisférica; el resultado se m

uestra a la izquierda. Cada individuo del

AG consistía en un crom

osoma binario que especificaba las coordenadas tridim

ensionales de cada extrem

o final de cada alambre. L

a aptitud se evaluaba simulando a cada candidato de acuerdo con un

código de cableado electromagnético, y el individuo m

ejor 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, com

o ``inusualmente extraña'' y ``antiintuitiva'' (p. 52), aunque tenía un patrón de

radiación casi uniforme y con un gran ancho de banda tanto en la sim

ulación como en la prueba

experimental, adecuándose excelentem

ente a la especificación inicial. Los autores concluyen que un

método basado en algoritm

os genéticos para diseñar antenas se muestra ``excepcionalm

ente prom

etedor''. ``... este nuevo procedimiento de diseño es capaz de encontrar antenas genéticas capaces

de resolver de manera efectiva difíciles problem

as de antenas, y será especialmente útil en situaciones en

las que los diseños existentes no sean adecuados'' (p. 52).

Merca

dos fin

anciero

s

Figure: U

na antena genética de alam

bre doblado (de Altshuler y L

inden 1997, figura 1).

Página 20 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Mahfoud y M

ani 1996[46] utilizaron un algoritmo genético para predecir el rendim

iento futuro de 1.600 acciones ofertadas públicam

ente. Concretam

ente, al AG se le asignó la tarea de predecir el beneficio

relativo de cada acción, definido como el beneficio de esa acción m

enos el beneficio medio de las 1.600

acciones a lo largo del periodo de tiempo en cuestión, 12 sem

anas (un cuarto del calendario) en el futuro. C

omo entrada, al A

G se le proporcionaron datos históricos de cada acción en form

a de una lista de 15 atributos, com

o la relación precio-beneficio y el ritmo de crecim

iento, medidos en varios puntos

del tiempo pasado; se le pidió al A

G que evolucionara un conjunto de reglas si/entonces para clasificar

cada acción y proporcionar, como salida, una recom

endación sobre qué hacer con respecto a la acción (com

prar, vender o ninguna predicción) y un pronóstico numérico del beneficio relativo. L

os resultados del A

G fueron com

parados 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 m

ercado de valores es un sistema extrem

adamente ruidoso y

no lineal, y ningún mecanism

o predictivo puede ser correcto el 100% del tiem

po; el reto consiste en encontrar un predictor que sea preciso m

ás de la mitad de las veces.

En el experiem

nto, el AG y la red neuronal hicieron pronósticos al final de la sem

ana para cada una de las 1.600 acciones, durante doce sem

anas consecutivas. Doce sem

anas después de cada predicción, se com

paró el rendimiento verdadero con el beneficio relativo predicho. G

lobalmente, el A

G superó

significativamente a la red neuronal: en una ejecución de prueba, el A

G predijo correctam

ente 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 m

enudo, también hizo predicciones erróneas m

ás a menudo (de hecho, los autores especulan que la m

ayor capacidad del AG para no realizar predicciones

cuando los datos eran dudosos fue un factor de su éxito; la red neuronal siempre produce una predicción

a menos que sea restringida explícitam

ente por el programador). E

n el experimento de las 1.600

acciones, el AG produjo un beneficio relativo de un +

5,47%, contra el +

4,40% de la red neuronal -una

diferencia estadísticamente significativa. D

e hecho, el AG tam

bién superó significativamente a tres

índices bursátiles importantes -el S

&P 500, el S

&P 400 y el R

ussell 2000- en este periodo; la casualidad fue excluí da com

o 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 hum

anos, además del hecho de que carece del ``prejuicio

contra las reglas antiintuitivas y contradictorias'' (p. 562) de los expertos humanos.

Andreou, G

eorgopoulos y Likothanassis 2002[ 4] lograron un éxito sim

ilar utilizando algoritmos

genéticos híbridos para evolucionar redes neuronales que predijeran los tipos de cambio de m

onedas extranjeras hasta un m

es en el futuro. Al contrario que en el ejem

plo anterior, donde competían A

Gs y

redes neuronales, aquí los dos trabajaron conjuntamente: el A

G evolucionó la arquitectura (núm

ero de unidades de entrada, núm

ero de unidades ocultas y la estructura de enlaces entre ellas) de la red, que luego era entrenada por un algoritm

o de filtro.

Se le proporciaron al algoritm

o 1.300 valores brutos diarios de cinco divisas como inform

ación histórica -el dólar estadounidense, el m

arco alemán, el franco francés, la libra esterlina y el dracm

a griego- y se le pidió que predijera sus valores futuros para los 1, 2, 5 y 20 días posteriores. E

l rendimiento del A

G

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

os autores concluyen que ``se ha logrado un excepcional éxito predictivo tanto con un horizonte predictivo de un paso com

o de varios pasos'' (p. 208) -de hecho, afirm

an que sus resultados son mejores con diferencia que cualquier

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

La utilización de los A

Gs en los m

ercados financieros ha empezado a extenderse en las em

presas de corretaje bursátil del m

undo real. Naik 1996[48] inform

a de que LBS C

apital Managem

ent, una empresa

Página 21 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

estadounidense cons ede en Florida, utiliza algoritm

os genéticos para escoger las acciones de los fondos de pensiones que adm

inistra. Coale 1997[17] y B

egley y Beals 1995[9] inform

an de que First Q

uadrant, una em

presa de inversiones de Californa que m

ueve más de 2.200 m

illones de dólares, utiliza AGs para

tomar decisiones de inversión en todos sus servicios financieros. S

u 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 m

odelos.

Juegos

Una de las dem

ostraciones más novedosas y persuasivas de la potencia de los algoritm

os genéticos la presentaron C

hellapilla y Fogel 2001[13], que utilizaron un A

G para evolucionar redes neuronales que

pudieran jugar a las damas. L

os autores afirman que una de las m

ayores dificultades en este tipo de problem

as relacionados con estrategias es el problema de la asignación de crédito -en otras palabras,

¿cómo escribir una función de aptitud? S

e ha creído ampliam

ente que los criterios simples de ganar,

perder o empatar no proporcionan la suficiente inform

ación para que un algoritmo genético averigüe qué

constituye el buen juego.

En este artículo, C

hellapila y Fogel echan por tierra esa suposición. D

ados sólo las posiciones espaciales de las piezas en el tablero y el núm

ero total de piezas que posee cada jugador, fueron capaces de evolucionar un program

a de damas que jugaba a un nivel com

petitivo con expertos humanos, sin

ninguna información de entrada inteligente acerca de lo que constituye el buen juego -es m

ás, ni siquiera se les dijo a los individuos del algoritm

o evolutivo cuál era el criterio para ganar, ni se les dijo el resultado de ningún juego.

En la representación de C

hellapilla y Fogel, el estado del juego estaba representado por una lista

numérica de 32 elem

entos, en donde cada posición de la lista correspondía a una posición disponible en el tablero. E

l valor de cada posición era 0 para una casilla desocupada, -1 si esa casilla estaba ocupada por una pieza enem

iga, +1 si la casilla estaba ocupada por una de las piezas del program

a, y -K o +

K si

la casilla estaba ocupada por una dama enem

iga o amiga. (E

l valor de K no se especificaba a priori, sino

que, de nuevo, era determinado por la evolución durante el curso del algoritm

o). Acom

pañ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óm

o de buena le parecí a esa posición. P

ara cada movim

iento, se le presentaba a la red neuronal un árbol de juego que contenía todos los m

ovimientos posibles hasta cuatro turnos en el futuro, y el m

ovimiento se decidía basándose

en qué rama del árbol producía los m

ejores resultados.

El algoritm

o evolutivo comenzó con una población de 15 redes neuronales con pesos y tendencias,

generados aleatoriamente, asignados a cada nodo y conexión; luego, cada individuo se reprodujo una

vez, generando una descendencia con variaciones en los valores de la red. Luego estos 30 individuos

compitieron por la supervivencia jugando entre ellos; cada individuo com

pitió en cada turno con 5 oponentes elegidos aleatoriam

ente. Se otorgó 1 punto a cada victoria y se descontaban 2 puntos por cada

derrota. Se seleccionaron los 15 m

ejores jugadores en relación a su puntuación total, y el proceso se repitió. L

a evolución continuó durante 840 generaciones más (aproxim

adamente seis m

eses de tiempo

de computación).

Clase

Puntuación

Gran M

aestro+2.400

Página 22 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

El m

ejor individuo que surgió de esta selección fue inscrito como com

petidor en la página web de

juegos http://www.zone.com. D

urante un periodo de dos meses, jugó contra 165 oponentes hum

anos que com

ponían una gama de niveles altos, desde clase C

a maestros, de acuerdo con el sistem

a de clasificaciones de la F

ederación de Ajedrez de E

stados Unidos (m

ostrado a la izquierda, con algunos rangos om

itidos en aras de claridad). De estas partidas, la red neuronal ganó 94, perdió 39 y em

pató 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 m

edia de 2.045,85, colocándola en el nivel experto -una clasificación superior a la del 99,61%

de los 80.000 jugadores registrados en la página web. U

na 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 program

a diferencial en las piezas (que basa sus movim

ientos solam

ente en la diferencia entre el número de piezas que quedan en cada lado) con una capacidad de

anticipación de 8 movim

ientos demostró que la red neuronal era significativam

ente superior, con una puntuación de m

ás de 400 puntos por encima. ``U

n programa que se basa sólo en el núm

ero de piezas y en una búsqueda de ocho capas vencerá a m

uchas personas, pero no es un experto. La m

ejor red neuronal evolucionada sí lo es'' (p. 425). A

unque podía buscar posiciones dos movim

ientos más lejos

que la red neuronal, el programa diferencial en las piezas perdió contundentem

ente 8 de 10 partidas. Esto dem

uestra 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 m

ovimientos.

Los autores señalan que los oponentes de zone.com

que los movim

ientos de la red neuronal eran ``extraños'', pero su nivel global de juego fue descrito com

o ``muy duro'' o con térm

inos elogiosos sim

ilares.

Para probar m

ás a la red neuronal evolucionada (a la que los autores nombraron ``A

naconda'' porque a menudo ganaba restringiendo la m

ovilidad de sus oponentes), jugó contra un programa de dam

as com

ercial, el Hoyle C

lassic Gam

es, distribuído por Sierra O

nline (Chellapilla y F

ogel 2000[ 14]). Este

programa viene con un surtido de personajes incorporados, cada uno con un nivel de juego distinto.

Anaconda se puso a prueba con tres personajes (``B

eatrice'', ``Natasha'' y ``L

eopold'') 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 m

ovimientos. A

unque los autores dudaban de que esta profundidad de anticipación pudiera darla a A

naconda la capacidad de juego experto que demostró

anteriormente, consiguió seis victorias seguidas de las seis partidas jugadas. B

asándose en este resultado, los autores expresaron escepticism

o sobre si el software H

oyle jugaba al nivel que anunciaba, ¡aunque debe señalarse que llegaron a esta conclusión basándose solam

ente en la facilidad con la que Anaconda le venció!

La prueba definitiva de A

naconda se detalla en Chellapilla y F

ogel 2002[15], cuando la red neuronal evolucionada jugó contra el m

ejor jugador de damas del m

undo: Chinook, un program

a diseñado

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

Página 23 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

principalmente por el D

r. Jonathan Schaeffer, de la U

niversidad de Alberta. C

on una puntuación de 2.814 en 1996 (m

ientras que sus competidores hum

anos más cercanos andan por los 2.600), C

hinook incorpora un libro de m

ovimientos de apertura proporcionado por grandes m

aestros humanos, un

conjunto sofisticado de algoritmos de juego para la parte central de la partida, y una base de datos

completa de todos los m

ovimientos posibles cuando quedan en el tablero 10 piezas o m

enos, de manera

que nunca comete un error durante un final de partida. S

e invirtió una cantidad enorme de inteligencia y

experiencia humana en el diseño de este program

a.

Chellapilla y F

ogel enfrentaron a Anaconda y C

hinook 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 m

aestro. Chinook

ganó esta competición, cuatro victorias a dos, con cuatro em

pates. (Curiosam

ente, como señalan los

autores, en dos de las partidas que acabaron con empate, A

naconda lideraba con cuatro damas m

ientras que C

hinook tenía tres. Adem

ás, una de las victorias de Chinook vino tras una serie de m

ovimientos con

búsqueda de 10 capas sacados de su base de datos de finales de partida; unos movim

ientos que Anaconda, con una anticipación de 8 capas, no pudo anticipar. S

i Anaconda hubiera tenido acceso a una

base de datos de finales de partida de la mism

a calidad de la de Chinook, el resultado del torneo bien

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

stos resultados ``proporcionan un buen sustento a la puntuación de experto que se ganó A

naconda en www.zone.com

'' (p. 76), con una puntuación global de 2.030-2.055, com

parable a la puntuación de 2.045 que ganó jugando contra hum

anos. Aunque A

naconda no es un jugador invulnerable, es capaz de jugar competitivam

ente en el nivel experto y com

portarse ante una variedad de jugadores de damas hum

anos extremadam

ente hábiles. Cuando uno considera los criterios de aptitud tan sencillos con los que se obtuvieron estos resultados, el

surgimiento de A

naconda proporciona una espectacular corroboración del poder de la evolución.

Geofísica

Sam

bridge y Gallaguer 1993[56] utilizaron un algoritm

o genético para los hipocentros de los terremotos

basándose en datos sismológicos. (E

l hipocentro es el punto bajo la superficie terrestre en el que se origina un terrem

oto. El epicentro es el punto de la superficie directam

ente encima del hipocentro). E

sto es una tarea sum

amente com

pleja, ya que las propiedades de las ondas sísmicas dependen de las

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 com

o algoritmo de inversión sísm

ico, que empieza con la m

ejor estim

ació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. E

ste proceso se repite hasta que se alcanza una solución aceptable. (E

ste Mensaje del M

es, de noviembre de 2003,

proporciona más inform

ación). Sin em

bargo, este método requiere inform

ació n diferencial y es propenso a quedar atrapado en óptim

os locales.

Un algoritm

o de localización que no dependa de información diferencial o m

odelos de velocidad puede evitar esta deficiencia calculando sólo el problem

a directo -la diferencia entre los tiempos de llegada de

la onda observados y predichos para distintas localizaciones del hipocentro. Sin em

bargo, un método de

búsqueda exhaustivo basado en este método sería dem

asiado costoso computacionalm

ente. Éste, por

supuesto, es precisamente el tipo de problem

a de optimización en el que destacan los algoritm

os genéticos. C

omo todos los A

Gs, 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, com

ienza con una nube de hipocentros potenciales que encoge con el tiem

po hasta converger en una sola solución. Los autores afirm

an que su método ``puede localizar rápidam

ente soluciones casi óptimas sin una búsqueda exhaustiva del espacio

de parámetros'' (p. 1.467), m

uestra ``un comportam

iento muy organizado que produce una búsqueda

eficiente'' y es ``un comprom

iso entre la eficiencia de los métodos basados en derivadas y la robustez de

una búsqueda exhaustiva completam

ente no lineal'' (p. 1.469). Los autores concluyen que su algoritm

o

Página 24 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

genético es ``eficiente para una verdadera optimización global'' (p. 1.488) y ``una herram

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

Ingeniería

de materia

les

Giro, C

yrillo y Galvão 2002[27] utilizaron algoritm

os genéticos para diseñar polímeros conductores de

electricidad basados en el carbono, conocicos como polianilinas. E

stos polímeros, un tipo de m

aterial sintético inventado recientem

ente, tienen ``grandes aplicaciones tecnológicas potenciales'' y podrían abrir la puerta a ``nuevos fenóm

enos físicos fundamentales'' (p. 170). S

in embargo, debido a su alta

reactividad, los átomos de carbono pueden form

ar un número virtualm

ente infinito de estructuras, haciendo que la búsqueda de nuevas m

oléculas con propiedades interesantes sea del todo imposible. E

n este artículo, los autores aplican un enfoque basado en A

Gs a la tarea de diseñar m

oléculas nuevas con propiedades especificadas a priori, com

enzando con una población de candidatos iniciales generada aleatoriam

ente. Concluyen que su m

etodología puede ser una ``herramienta m

uy efectiva'' (p. 174) para guiar a los investigadores en la búsqueda de nuevos com

puestos y es lo suficientemente general para que

pueda extenderse al diseño de nuevos materiales que pertenezcan virtualm

ente a cualquier tipo de molécula.

Weism

ann, Ham

mel, y B

äck 1998[63] aplicaron algoritmos evolutivos a un problem

a industrial ``no trivial'' (p. 162): el diseño de revestim

ientos ópticos multicapa para filtros que reflejan, transm

iten o absorben luz de frecuencias especificadas. E

stos revestimientos se utilizan en la fabricación de gafas de

sol, por ejemplo, o discos com

pactos. Su fabricación es una tarea precisa: las capas deben colocarse en

una secuencia particular y con un grosor particular para producir el resultado deseado, y las variaciones incontrolables del entorno de fabricación, com

o la temperatura, la polución o la hum

edad, pueden afectar al rendim

iento del producto acabado. Muchos óptim

os locales no son robustos ante estas variaciones, lo que significa que una m

ayor calidad del producto se paga con una tasa mayor de

desviaciones indeseadas. El problem

a particular considerado en este artículo también tenía m

últiples criterios: adem

ás de la reflectancia, también se consideró la com

posición espectral (color) de la luz reflejada.

El A

E actuó variando el núm

ero 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 m

edio mayor que los m

étodos tradicionales. Los autores concluyen que ``los algoritm

os evolutivos pueden com

petir e incluso superar a los métodos tradicionales'' (p. 167) de diseño de

revestimientos ópticos m

ulticapa, sin tener que incorporar un conocimiento específico del dom

inio en la función de búsqueda y sin tener que alim

entar a la población con buenos diseños iniciales.

Es digno de m

ención otro uso de los AGs en el cam

po de la ingeniería de materiales: R

obin et al. 2003[54] utilizaron A

Gs 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 m

icrómetro en circuitos integrados. D

iseñar estos patrones es una tarea m

uy difícil; es pesado y costoso determinarlos experim

entalmente, pero la alta

dimensionalidad del espacio de búsqueda frustra a la m

ayoría de los algoritmos de búsqueda. D

eben optim

izarse simultáneam

ente 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. E

l problem

a directo -determinar la estructura resultante com

o función de la cantidad de electrones- es sencillo y fácil de sim

ular, pero el problema inverso de determ

inar la cantidad de electrones para producir una estructura dada, que es lo que se pretende resolver aquí, es m

ucho más difícil y no existe

una solución determinista.

Se aplicaron algoritm

os genéticos a este problema, ya que ``se sabe que son capaces de encontrar

Página 25 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

soluciones buenas a problemas m

uy complejos de alta dim

ensionalidad'' (p. 75) sin necesidad de proporcionarles inform

ación específica del dominio acerca de la topología del paisaje de búsqueda. L

os autores del artículo em

plearon un AG de estado estacionario con selección por rueda de ruleta en una

simulación por com

putador, que produjo unos patrones de exposición ``muy bien optim

izados'' (p. 77). En contraste, se utilizó un tipo de trepacolinas conocido com

o algoritmo bajacolinas-sim

plex (simplex-

downhill) en el m

ismo problem

a, sin éxito; el método B

S quedaba rápidam

ente atrapado en óptimos

locales de los que no podía escapar, produciendo soluciones de poca calidad. Un híbrido entre los

métodos del A

G y el B

S tam

poco pudo mejorar los resultados ofrecidos por el A

G en solitario.

Matem

ática

s y algoritm

ia

Aunque algunas de las aplicaciones m

ás prometedoras y las dem

ostraciones más convincentes de la

potencia de los AGs se encuentran en el cam

po de la ingeniería de diseño, también son relevantes en

problemas ``puram

ente'' matem

áticos. Haupt y H

aupt 1998[34] (p. 140) describen el uso de AGs para

resolver ecuaciones de derivadas parciales no lineales de alto orden, normalm

ente encontrando los valores para los que las ecuaciones se hacen cero, y dan com

o ejemplo una solución casi perfecta para

los coeficientes de la ecuación de quinto orden conocida como S

uper Kortew

eg-de Vries.

Ordenar una lista de elem

entos es una tarea importante en la inform

ática, y una red de ordenació n es una manera eficiente de conseguirlo. U

na red de ordenación es una lista fija de comparaciones realizadas en

un conjunto de un tamaño dado; en cada com

paración se comparan dos elem

entos y se intercambian si

no están en orden. Koza et al. 1999[41] (p. 952) utilizaron program

ación genética para evolucionar redes de ordenación m

ínimas para conjuntos de 7 elem

entos (16 comparaciones), conjuntos de 8 elem

entos (19 com

paraciones) y conjuntos de 9 elementos (25 com

paraciones). Mitchell 1996[47], p. 21, describe

el uso de algoritmos genéticos por W

. Daniel H

illis para encontrar una red de ordenación de 61 com

paraciones para un conjunto de 16 elementos, sólo un paso m

ás allá de la más pequeña conocida.

Este últim

o ejemplo es especialm

ente interesante por las dos innovaciones que utiliza: cromosom

as diploides y, m

ás notablemente, coevolución de huésped/parásito. T

anto las redes de búsqueda como los

casos de prueba evolucionaron conjuntamente; se les otorgó m

ayor aptitud a las redes de ordenació n que ordenaran correctam

ente un mayor núm

ero de casos de prueba, mientras que se les otorgó m

ayor aptitud a los casos de prueba que pudieran ``engañar'' a un m

ayor número de redes de búsqueda para que

ordenaran incorrectamente. E

l AG con coevolución rindió significativam

ente mejor que el m

ismo A

G

sin ella.

Un ejem

plo final de AG digno de m

enció n en el campo de la algoritm

ia puede encontrarse en Koza et al.

1999[41], que utilizó programación genética para descubrir una regla para el problem

a de clasificación por m

ayoría en autómatas celulares de una dim

ensión, una regla mejor que todas las reglas conocidas

escritas por humanos. U

n autómata celular de una dim

ensión puede imaginarse com

o una cinta finita con un núm

ero dado de posiciones (celdas) en ella, cada una de las cuales puede contener el estado 0 o el estado 1. E

l autómata se ejecuta durante un núm

ero dado de pasos temporales; en cada paso, cada

celda adquiere un nuevo valor basado en su valor anterior y el valor de sus vecinos más cercanos. (E

l Juego de la V

ida es un autómata celular bidim

ensional). El problem

a 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. E

l reto consiste en el hecho de que cualquier celda individual sólo tiene acceso a inform

ación acerca de sus vecinos más

cercanos; por lo tanto, los conjuntos de reglas buenos deben encontrar de algún modo una m

anera de transm

itir información sobre regiones distantes de la cinta.

Se sabe que no existe una solución perfecta a este problem

a -ningún conjunto de reglas puede clasificar con precisión todas las configuraciones iniciales posibles-, pero durante los últim

os veinte años ha

Página 26 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

habido una larga sucesión de soluciones cada vez mejores. E

n 1978, tres investigadores desarrollaron la fam

osa regla GKL, que clasifica correctam

ente un 81,6% de los posibles estados iniciales. E

n 1993, se descubrió una regla m

ejor con una precisión de un 81,8%; en 1995 se encontró otra regla con una

precisión de un 82,178%. T

odas estas reglas requirieron para su desarrollo de un esfuerzo significativo por parte de hum

anos inteligentes y creativos. En contraste, la m

ejor regla descubierta mediante

programación genética, descrito en K

oza et al. 1999[41], p. 973, tiene una precisión total de 82,326% -

mejor que cualquiera de las soluciones hum

anas desarrolladas durante las dos últimas décadas. L

os autores señalan que sus nuevas reglas son cualitativam

ente distintas a las reglas publicadas con anterioridad, al em

plear representaciones internas muy detalladas de la densidad de estados y conjuntos

intrincados de señales para comunicar inform

ación a largas distancias.

Ejército

y cumplimiento de la ley

Kew

ley y Embrechts 2002[39] utilizaron algoritm

os genéticos para evolucionar planes tácticos para las batallas m

ilitares. Los autores señalan que ``planear una batalla m

ilitar táctica es una tarea compleja

multidim

ensoinal que a menudo atorm

enta a los profesionales experimentados'' (p. 163), no sólo porque

este tipo de decisiones a menudo se tom

an bajo condiciones de mucho estrés, sino tam

bién porque hasta los planes m

ás sencillos requieren tomar en cuenta un gran núm

ero de variables y consecuencias: minim

izar las bajas amigas, m

aximizar las bajas enem

igas, controlar el terreno deseado, conservar recursos, etcétera. L

os planificadores humanos tienen dificultades al tratar con las com

plejidades de esta tarea y a m

enudo deben recurrir a métodos ``rápidos y sucios'', com

o hacer lo que funcionase la última

vez.

Para superar estas dificultades, los autores del artículo citado desarrollaron un algoritm

o genético para autom

atizar la creación de planes de batalla, en conjunción con un programa gráfico de sim

ulación de batallas. E

l comandante introduce el resultado deseado y el A

G evoluciona autom

áticamente un plan de

batalla; en la simulación utilizada, se tom

aron en cuenta factores como la topografía del terreno, la

cobertura vegetal, la velocidad del movim

iento de tropas, y la precisión en los disparos. En este

experimento tam

bién se utilizó la coevolución para mejorar la calidad de las soliciones: los planes de

batalla de las fuerzas enemigas evolucionaron sim

ultá neamente con los planes am

igos, forzando al AG a

corregir cualquier debilidad de su plan que pudiese explotar el enemigo. P

ara medir la calidad de las

soluciones producidas por el AG, se com

pararon con planes de batalla para el mism

o escenario producidos por un grupo de ``expertos m

ilitares experimentados... considerados m

uy capaces de desarrollar planes de acción para el tam

año de las fuerzas utilizadas en este experimento'' (p. 166). E

stos avezados expertos desarrollaron su propio plan y, cuando la solución del A

G estuvo acabada, se les dio

la oportunidad de examinarla y m

odificarla como vieran conveniente. F

inalmente, todos los planes se

ejecutaron varias veces en el simulador para determ

inar su calidad media.

Los resultados hablan por sí m

ismos: la solución evolucionada superó tanto al propio plan de los

expertos militares com

o al plan producido por sus modificaciones sobre la solución del A

G. ``...L

os planes producidos por los algoritm

os automáticos tenían un rendim

iento medio significativam

ente mayor al de los generados por los experim

entados expertos militares'' (p. 161). E

s más, los autores

señalan que el plan del AG tenía sentido táctico. (C

onsistía en un ataque a dos flancos a la posición enem

iga 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 am

igas individuales llevando a cabo m

isiones doctrinales -una propiedad emergente que apareció durante el curso de la

ejecución, en lugar de ser especificada por el experimentador. E

n campos de batalla m

odernos, cada vez más conectados por red, el atractivo potencial de un algoritm

o evolutivo que pueda automatizar la

producción de planes tácticos de alta calidad debería ser obvio.

Página 27 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Naik 1996[48] inform

a de un uso interesante de los AGs en el cum

plimiento de la ley, describiendo el

software ``F

acePrints'', un proyecto para ayudar a los testigos a identificar y describir a los sospechosos

criminales. L

a imagen cliché del artista policí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 m

ayoría de la gente no es buena describiendo aspectos individuales del rostro de una persona, com

o el tamaño de la nariz o la form

a de la m

andíbula, pero sin embargo son m

ejores al reconocer caras completas. F

acePrints 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 m

aneras. El program

a muestra a los

testigos imágenes de rostros generadas aleatoriam

ente, y éstos escogen las que más se parecen a la

persona que vieron; las caras seleccionadas mutan y se com

binan para generar nuevas combinaciones de

características, y el proceso se repite hasta que emerge un retrato preciso del rostro del sospechoso. E

n un caso real de atraco, los retratos definitivos que crearon los tres testigos eran sorprendentem

ente parecidos, y el dibujo resultante apareció en el periódico local.

Biología molecu

lar

En los seres vivos, las proteínas transm

embrana son proteínas que sobresalen de una m

embrana celular.

Las proteínas transm

embrana realizan a m

enudo funciones importantes com

o detectar la presencia de ciertas sustancias en el exterior de la célula o transportarlas hacia el interior de la célula. P

ara com

prender el comportam

iento de una proteína transmem

brana es necesario identificar el segmento de

la proteína que realmente está insertado en la m

embrana, lo que se conoce com

o dominio

transmem

brana. Durante las dos últim

as décadas, los biólogos moleculares han publicado una serie de

algoritmos cada vez m

ás precisos para este propósito.

Todas las proteínas utilizadas por los seres vivos están form

adas por los mism

os 20 aminoácidos.

Algunos de estos am

inoácidos son hidrofóbicos, lo que significa que repelen el agua, y algunos son hidrofílicos, lo que significa que atraen el agua. L

as secuencias de aminoácidos que son parte de un

dominio transm

embrana tienen probabilidad de ser hidrofóbicas. S

in 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[41], capítulo 16, utilizaron program

ación genética para diseñar un algoritmo que

identificase el dominio transm

embrana de una proteína. S

e le suministró al program

a genético un conjunto de operadores m

atemáticos estándares con los que trabajar, adem

ás de un conjunto de funciones booleanas para la detección de am

inoácidos que devuelven +1 si el am

inoácido de una posición dada es el am

inoácido que detectan o -1 en caso contrario. (Por ejem

plo, la función A? recibe

como argum

ento un número que corresponde a una posición dentro de la proteína, y devuelve +

1 si el am

inoácido de esa posición es alanina, denotado por la letra A, y si no devuelve -1). U

na variable de mem

oria compartida contenía una cuenta de la sum

a total, y cuando el algoritmo acababa, el segm

ento proteínico se identificaba com

o dominio transm

embrana si su valor era positivo. C

on tan sólo estas herram

ientas, ¿haría falta más inform

ación para que un diseñador humano produjese una solución

eficiente a este problema?

Las aptitudes de las soluciones producidas por la program

ación genética fueron evaluadas probándolas con 246 segm

entos proteínicos de los que se conocía su condición de transmem

brana. Luego se evaluó

al mejor individuo de la prueba con 250 casos adicionales inéditos (out-of-sam

ple), y se comparó su

efectividad con la de los cuatro mejores algoritm

os humanos para el m

ismo propósito. E

l resultado: la program

ación genética produjo un algoritmo de identificación de segm

entos transmem

brana con una tasa total de error del 1,6%

- significativamente m

enor que las de los cuatro algoritmos hum

anos, el mejor

de los cuales tenía una tasa de error del 2,5%. E

l algoritmo diseñado genéticam

ente, al que los autores llam

aron regla 0-2-4, funciona de la manera siguiente:

Página 28 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

�Increm

entar la suma en 4 unidades por cada instancia de ácido glutám

ico (un aminoácido cargado

eléctricamente y m

uy hidrofílico) del segmento proteínico.

�Increm

entar la suma en 0 unidades por cada instancia de alanina, fenilanalina, isoleucina, leucina,

meionina o valina (todos am

inoácidos muy hidrofóbicos) del segm

ento proteínico. �

Incrementar la sum

a en 2 unidades por cada instancia de cualquier otro aminoácido.

�Si [(S

UM

A - 3,1544)/0,9357] es m

enor que la longitud del segmento proteínico, clasificar ese

segmento com

o dominio transm

embrana; de lo contrario, clasificarlo com

o dominio no

transmem

brana.

Reconocim

iento de patrones y

explotación de datos

La com

petició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 los usuarios se cam

bian de un proveedor de servicios a otro. L

a fuga le cuesta a las compañías de telecom

unicaciones una gran cantidad de dinero cada año, y reducir las fugas es un factor im

portante para aumentar la rentabilidad. S

i 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. E

l problema es, por tanto, cóm

o identificar a los clientes que m

ás piensen fugarse con mayor probabilidad. T

odas las compañías tienen grandes bases

de datos con información de los clientes que teóricam

ente puede utilizarse para este propósito; pero ¿qué método funciona m

ejor para examinar esta enorm

e cantidad de datos e identificar los sutiles patrones y tendencias que indican la probabilidad de fuga de un cliente?

Au, C

han y Yao 2003[ 7] aplicaron algoritm

os 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 prim

era generación de reglas, todas las cuales tenían una condición, fue generada utilizando una técnica de inducción probabilística. L

as generaciones posteriores las refinaron, combinando sencillas

reglas de una condición con reglas más com

plejas con varias condiciones. Para la m

edición de la aptitud se utilizó una m

edida de correlación objetiva de la ``interesantitud'', que no necesitaba información de

entrada subjetiva. El algoritm

o evolutivo de explotación de datos se probó sobre una base de datos real de 100.000 clientes proporcionada por una com

pañía malasia, y su rendim

iento se comparó con el de

dos métodos alternativos: una red neuronal m

ulticapa y un algoritmo basado en árbol de decisiones

ampliam

ente utilizado, el C4.5. L

os autores afirman que su A

E 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 C

4.5 bajo todas las circunstancias, superando a la red neuronal en tasas mensuales de fuga bajas e igualándola en tasas de fuga m

ayores y, en ambos casos, alcanzando las

conclusiones más rápidam

ente. Algunas ventajas m

ás del enfoque evolutivo son que puede funcionar eficientem

ente incluso cuando faltan algunos campos de datos, y que puede expresar sus

descubrimientos en conjuntos de reglas fácilm

ente 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 personalm

ente al plan de servicios y no han sido adm

itidos 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 K

uala Lum

pur, tienen entre 36 y 44 años y pagan sus facturas en efectivo (supuestam

ente porque es más fácil cam

biarse de proveedor para los clientes que pagan al contado, a diferencia de los que cargan en cuenta autom

áticamente); y los clientes que viven en P

enang y contrataron a través de un cierto vendedor tienen más probabilidades de fugarse (este vendedor puede estar proporcionando un m

al servicio al cliente y debería ser investigado).

Página 29 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Rizki, Z

muda y T

amburino 2002[53] utilizaron algoritm

os evolutivos para evolucionar un complejo

sistema de reconocim

iento de patrones con una amplia variedad de usos potenciales. L

os autores señalan que el reconocim

iento de patrones es una tarea cada vez más realizada por algoritm

os de aprendizaje autom

ático, en particular, algoritmos evolutivos. L

a mayoría de ellos com

ienzan con un acervo de características predefinidas, del que un A

E puede seleccionar com

binaciones apropiadas para la tarea en cuestión; en contraste, este m

é todo empezaba desde cero, prim

ero evolucionando detectores individuales de característica en form

a de árboles de expresiones, y luego evolucionando combinaciones cooperativas

de esos detectores para producir un sistema com

pleto de reconocimiento de patrones. E

l proceso evolutivo selecciona autom

áticamente el núm

ero 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 sistem

a, los autores le asignaron la tarea de clasificar aviones basándose en sus reflexiones rádar. U

n mism

o 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 m

uy parecidas, así que esto no es una tarea trivial. E

l sistema de reconocim

iento de patrones evolucionado clasificó correctam

ente un 97,2% de los objetivos, un porcentaje neto m

ayor que el de las otras tres técnicas -una red neuronal perceptrón, un algoritm

o clasificador KNN y un algoritm

o de base radial- con las que fue com

parado. (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 sistem

a reconocedor evolucionado sólo utilizó 17). C

omo afirm

an los autores, ``los sistemas de reconocim

iento que evolucionan utilizan menos

características que los sistemas producidos utilizando técnicas convencionales, pero consiguen una

precisión de reconocimiento com

parable o superior'' (p. 607). Tam

bién se han aplicado varios aspectos de su sistem

a en problemas que incluyen el reconocim

iento óptico de caracteres, la revisión industrial y el análisis m

édico de imágenes.

Hughes y L

eyland 2000[37] también aplicaron A

Gs m

ultiobjetivo a la tarea de clasificar objetivos basándose en sus reflexiones rádar. L

os datos de una sección transversal rádar de alta resolución necesitan enorm

es cantidades de espacio de almacenam

iento en disco, y producir un modelo realista de

la fuente a partir de los datos es muy costoso com

putacionalmente. E

n contraste, el método basado en el

AG de los autores dem

ostró ser muy exitoso, produciendo un m

odelo tan bueno como el del m

étodo iterativo tradicional, pero reduciendo el gasto com

putacional y las necesidades de almacenam

iento hasta el punto de que era factible generar buenos m

odelos 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 m

odelos de calidad similar. L

os autores concluyen que sus resultados ``dem

uestran claramente'' (p. 160) la capacidad del A

G de procesar datos de rádar bidim

ensionales y tridim

ensionales de cualquier nivel de resolución con muchos m

enos cálculos que los métodos

tradicionales, manteniendo una precisión aceptablem

ente alta.

Robótica

El torneo internacional R

oboCup es un proyecto para prom

ocionar el avance de la robótica, la inteligencia artificial y los cam

pos relacionados, proporcionando un problema estándar con el que probar

las nuevas tecnologías -concretamente, es un cam

peonato anual de fútbol entre equipos de robots autónom

os. (El objetivo fijado es desarrollar un equipo de robots hum

anoides que puedan vencer al equipo hum

ano de fútbol que sea campeón del m

undo en 2050; actualmente, la m

ayoría de los equipos de robots participantes funcionan con ruedas). L

os programas que controlan a los m

iembros del equipo

robótico deben exhibir un comportam

iento complejo, decidiendo cuándo bloquear, cuándo tirar, cóm

o moverse, cuándo pasar la pelota a un com

pañero, cómo coordinar la defensa y el ataque, etcétera. E

n la liga sim

ulada de 1997, David A

ndre y Astro T

eller inscribieron a un equipo llamado D

arwin U

nited

Página 30 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

cuyos programas de control habían sido desarrollados autom

áticamente desde cero m

ediante program

ación genética, un desafío a la creencia convencional de que ``este problema es sim

plemente

demasiado difícil para una técnica com

o ésa'' (Andre y T

eller 1999[3], p. 346).

Para resolver este difícil problem

a, Andre y T

eller le proporcionaron al programa genético un conjunto

de funciones de control primitivas com

o girar, moverse, tirar, etcétera. (E

stas funciones estaban también

sujetas al cambio y refinam

iento durante el curso de la evolución). Su función de aptitud, escrita para

que recompensara el buen juego en general en lugar de m

arcar goles expresamente, proporcionaba una

lista de objetivos cada vez más im

portantes: acercarse a la pelota, golpear la pelota, conservar la pelota en el cam

po contrario, moverse en la dirección correcta, m

arcar goles y ganar el partido. Debe señalarse

que no se suministró ningún código para enseñar específicam

ente al equipo cómo conseguir estos

objetivos complejos. L

uego los programas evolucionados se evaluaron utilizando un m

odelo de selección jerárquico: en prim

er lugar, los equipos candidatos se probaron en un campo vacío y, si no

marcaban un gol en m

enos 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. E

n tercer lugar, el equipo jugaba un partido contra el equipo ganador de la com

petición RoboC

up de 1997. Finalm

ente, los equipos que marcaron al m

enos un gol contra este equipo jugaron unos contra otros para determ

inar cuál era el mejor.

De los 34 equipos de su división, D

arwin U

nited acabó en decimoséptim

a posición, situándose justo en el m

edio de la clasificación y superando a la mitad de los participantes escritos por hum

anos. Aunque

una victoria en el torneo sin duda habría sido más im

presionante, este resultado es competitivo y

significante de pleno derecho, y lo parece aún más a la luz de la historia. H

ace unos 25 años, los program

as informáticos que jugaban al ajedrez estaban en su infancia; por prim

era vez, una com

putadora había sido inscrita recientemente en una com

petición regional, aunque no ganó (Sagan

1979[ 55], p. 286). Pero ``una m

áquina que juega al ajedrez a un nivel medio de la capacidad hum

ana es una m

áquina muy capaz'' (ibid.), y podría decirse que lo m

ismo es cierto para el fútbol robotizado. S

i las máquinas de ajedrez actuales com

piten al nivel de los grandes maestros, ¿qué tipo de sistem

as producirá la program

ación genética dentro de 20 o 30 años?

Diseñ

o de ru

tas y horarios

Burke y N

ewall 1999[11] utilizaron algoritm

os genéticos para diseñar los horarios de los exámenes

universitarios. Se sabe que, en general, el problem

a del horario es NP-com

pleto, lo que significa que no se conoce un m

étodo para hallar con garantías una solución óptima en un tiem

po razonable. En un

problema así, hay restricciones duras -no puede asignarse el m

ismo aula a dos exám

enes a la vez- y restricciones suaves -si es posible, no deben asignarse varios exám

enes en sucesión a un mism

o estudiante, para m

inimizar la fatiga. L

as restricciones duras deben satisfacerse, mientras que las

restricciones suaves deben satisfacerse lo máxim

o posible. Los autores llam

an ``algoritmo m

emético'' a

su método híbrido para resolver este problem

a: un algoritmo evolutivo con selección por rango

proporcional a la aptitud, combinado con un trepacolinas local para optim

izar las soluciones halladas por el A

E. E

l AE se utilizó en cuatro conjuntos de datos de universidades reales (la m

enor de las cuales tenía 25.000 alum

nos), y sus resultados se compararon con los resultados producidos por un m

étodo heurístico de vuelta atrás, un algoritm

o muy consolidado que se encuentra entre los m

ejores que se conocen para este problem

a y que se utiliza en varias universidades. Com

parado con este método, el A

E

produjo un resultado con una reducción de la penalización bastante uniforme del 40%

.

He y M

ort 2000[35] aplicaron algoritmos genéticos al problem

a de hallar rutas óptimas en las redes de

telecomunicaciones (com

o las redes de telefonía e Internet), que se usan para transmitir datos desde los

remitentes hasta los destinatarios. E

sto es un problema N

P-difícil, un tipo de problem

a para el que los

Página 31 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

AGs son ``extrem

adamente aptos... y han encontrado una enorm

e variedad de aplicaciones exitosas en esos cam

pos'' (p. 42). Es adem

ás un problema m

ultiobjetivo, en el que hay que equilibrar objetivos en conflicto com

o maxim

izar el caudal de datos, minim

izar los retrasos en la transmisión y la pérdida de

datos, encontrar caminos de bajo coste y distribuír la carga uniform

emente entre los encam

inadores o conm

utadores de la red. Cualquier algoritm

o real satisfactorio debe también ser capaz de redirigir el

tráfico de las rutas principales que fallen o estén congestionadas.

En el A

G híbrido de los autores se utilizó un algoritm

o de tipo ``primero el cam

ino más corto'', que

minim

iza el número de ``saltos'' que debe realizar un paquete de datos dado, para generar la sem

illa de la población inicial. S

in 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 tom

a 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 A

G era capaz de redirigir enlaces rotos o congestionados, equilibrar

la carga de tráfico y maxim

izar el caudal total de la red. Los autores afirm

an que estos resultados dem

uestran la ``efectividad y escalabilidad'' del AG y que ``se pueden conseguir soluciones óptim

as o casi óptim

as'' (p. 49).

Esta técnica ha encontrado aplicaciones reales para propósitos sim

ilares, como inform

an Begley y B

eals 1995[9]. L

a compañía de telecom

unicaciones U.S. W

est (ahora fusionada con Qwest) se enfrentó a la

tarea de desplegar una red de fibra óptica. Hasta hace poco, el problem

a de diseñar la red para minim

izar la longitud total de cable desplegado era resuelto por un ingeniero experim

entado; ahora la compañía

utiliza un algoritmo genético para realizar la tarea autom

áticamente. L

os resultados: ``El tiem

po de diseño para las redes nuevas ha caído de dos m

eses a dos días, y le supone un ahorro a U.S. W

est de 1 millón a 10 m

illones de dólares cada una'' (p. 70).

Jensen 2003[38] y Chryssolouris y S

ubramaniam

2001[16] aplicaron algoritmos genéticos a la tarea de

generar programas para líneas de m

ontaje (job shop scheduling). Éste es un problem

a de optimización

NP-difícil con m

últiples criterios: deben tomarse en cuenta factores com

o el coste, los retrasos y el rendim

iento, y puede que se tenga que cambiar al vuelo el program

a de la línea de montaje debido a

averías en la maquinaria, ausencia de em

pleados, retrasos en la entrega de piezas, y otras com

plicaciones, lo que hace que la robustez del programa sea una consideración im

portante. Ambos

artículos concluyen que los AGs son significativam

ente superiores a las reglas de despacho de prioridad utilizadas com

únmente, al producir program

as eficientes que pueden tratar con má s facilidad los retrasos

y las averías. Estos resultados no son sim

plemente teóricos, sino que se han aplicado a situaciones

reales:

Com

o informa N

aik 1996[48], los organizadores de los Juegos Paraolím

picos de 1992 utilizaron un AG

para diseñar los horarios de los eventos. Com

o informa P

etzinger 1995[50], John Deere &

Co. ha

utilizado AGs para generar los program

as de montaje para una planta de M

oline, Illinois, que fabrica plantadoras y otras m

aquinarias 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 enorm

e cantidad de m

aneras posibles de construirlas implica que el diseño eficiente de program

as de montaje

sea un problema aparentem

ente intratable. La productividad se veía m

ermada por cuellos de botella en el

montaje, los equipos de trabajadores discutían, y se estaba perdiendo dinero. F

inalmente, en 1993, D

eer acudió a B

ill Fulkerson, un analista e ingeniero de personal que concibió la utilización de un algoritm

o genético para producir program

as de montaje para la planta. T

ras superar el escepticismo inicial, el A

G

demostró su valía rápidam

ente: la producción mensual aum

entó un 50 por ciento, el tiempo extra casi

desapareció y otras plantas de Deere están incorporando los A

Gs en sus propios diseños de program

as de m

ontaje.

Com

o informa R

ao 1998[52], Volvo ha utilizado un program

a evolutivo llamado O

ptiFlex para diseñar

Página 32 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

el programa de m

ontaje de su fábrica de Dublín, V

irginia, de un millón de m

etros cuadrados, una tarea que requiere controlar cientos de restricciones y m

illones de permutaciones posibles para cada vehículo.

Com

o todos los algoritmos genéticos, O

ptiFlex funciona com

binando aleatoriamente distintos

programas de m

ontaje posibles, determinando su aptitud clasificándolos en base a sus costos, beneficios

y restricciones, y luego haciendo que las mejores soluciones intercam

bien genes entre ellas y vuelvan a la población para otra prueba. H

asta hace poco, esta desalentadora tarea era responsabilidad de un ingeniero hum

ano, al que le llevaba hasta cuatro días producir el programa para cada sem

ana; ahora, gracias a los A

Gs, esta tarea se puede com

pletar en un día con una mínim

a intervención humana.

Com

o informa L

emley 2001[45], U

nited Distillers and V

intners, una empresa escocesa que es el m

ayor y m

ás rentable distribuidor de licores del mundo y es responsable de m

ás de un tercio de la producción mundial de w

hisky de grano, utiliza un algoritmo genético para adm

inistrar su inventario y sus sum

inistros. Esto es una tarea desalentadora que exige alm

acenar y distribuír eficientemente m

ás de 7 millones de barriles, que contienen 60 recetas distintas, entre un enorm

e sistema de alm

acenes y destilerías, dependiendo de una m

ultitud de factores como la edad, el núm

ero de malta, el tipo de m

adera y las condiciones del m

ercado. Anteriorm

ente, coordinar este complejo flujo de sum

inistro y demanda

requería de cinco empleados a tiem

po completo. H

oy, unas cuantas pulsaciones de teclado en un ordenador solicitan a un algoritm

o genético que genere un programa cada sem

ana, y la eficiencia de alm

acenamiento casi se ha duplicado.

Beasley, S

onander y Havelock 2001[ 8] utilizaron un A

G para program

ar los aterrizajes del London

Heathrow

, el aeropuerto más transitado del R

eino Unido. E

sto es un problema m

ultiobjetivo que im

plica, entre otras cosas, minim

izar los retrasos y maxim

izar el número de vuelos m

ientras se mantiene

la suficiente distancia de separación entre los aviones (los vórtices de aire que se forman en la estela de

un avión pueden ser peligrosos para otro avión que vuele demasiado cerca). C

omparado con los horarios

reales de un periodo intensivo del aeropuerto, el AG fue capaz de reducir el tiem

po de espera medio en

un 2-5%, im

plicando dos o tres vuelos extra despegando y aterrizando por cada hora -una mejora

significativa. Sin em

bargo, se han logrado mejoras m

ayores: como se inform

a en Wired 2002[1],

aeropuertos internacionales y líneas aéreas importantes com

o Heatrhow

, Toronto, S

ydney, Las V

egas, San F

rancisco, America W

est Airlines, A

eroMexico y D

elta Airlines están utilizando algoritm

os genéticos para program

ar los despegues, aterrizajes, mantenim

iento y otras tareas, mediante el softw

are del A

scent Technology's S

martA

irport Operations C

enter (ver http://www.ascent.com

/faq.html).

Cruzando y m

utando las soluciones en forma de horarios que incorporan m

iles de variables, ``Ascent

vence con comodidad a los hum

anos, aumentando la productividad hasta en un 30 por ciento en todos

los aeropuertos en los que se ha implem

entado''.

Ingeniería

de sistem

as

Benini y T

offolo 2002[10] aplicaron un algoritmo genético a la tarea m

ultiobjetivo de diseñar molinos

eólicos para generar energía eléctrica. Este diseño ``es un procedim

iento complejo caracterizado por

varias decisiones sobre contrapartidas... El proceso de tom

a 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. D

eben tomarse en cuenta objetivos

mutuam

ente exclusivos como la producción m

áxima de energía anual y el coste m

ínimo de la energía.

En este artículo se utilizó un algoritm

o evolutivo multiobjetivo para encontrar el m

ejor conjunto de contrapartidas entre estos objetivos, construyendo palas de m

olino 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 A

G consiguió encontrar soluciones com

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

Página 33 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Haas, B

urnham y M

ills 1997[32] utilizaron un algoritmo genético m

ultiobjetivo para optimizar la form

a, orientación e intensidad del haz de los em

isores de rayos X utilizados en la radioterapia dirigida, para

destruír los tumores cancerosos al tiem

po que se evita el tejido sano. (Los fotones de rayos X

dirigidos hacia un tum

or tienden a dispersarse por las estructuras interiores del cuerpo, dañando inintencionadam

ente los órganos internos. El reto consiste en m

inimizar este efecto m

ientras se maxim

iza la dosis de radiación dirigida hacia el tumor). U

tilizando 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ínim

os cuadrados iterativo, y luego utilizaron el AG para m

odificarlo y mejorarlo. C

onstruyendo un modelo del cuerpo hum

ano 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é cnicas

convencionales'' (p. 1745).

Lee y Z

ak 2002[ 44] utilizaron un algoritmo genético para evolucionar un conjunto de reglas para

controlar un sistema de frenos antibloqueo autom

ovilístico. Aunque la capacidad que tienen los sistem

as de freno antibloqueo de reducir la distancia de frenada y m

ejorar la maniobrabilidad ha salvado m

uchas vidas, el rendim

iento del ABS depende de las condiciones de la superficie de la carretera: por ejem

plo, un controlador A

BS que esté optim

izado para el asfalto seco no funcionará igual de bien en carreteras mojadas o heladas, y viceversa. E

n este artí culo, los autores proponen un AG para ajustar un controlador

ABS que pueda identificar las propiedades de la superficie de la carretera (m

onitorizando el patinaje y aceleración de las ruedas) y pueda actuar en consecuencia, liberando la cantidad adecuada de fuerza de frenado para m

aximizar la tracción de las ruedas. E

n las pruebas, el ABS puesto a punto genéticam

ente ``exhibe características de rodada excelentes'' (p. 206) y fue ``m

uy superior'' (p. 209) a los otros dos métodos de m

aniobras de frenado, encontrando con rapidez nuevos valores óptimos para el patinaje de

las ruedas cuando cambia el tipo de terreno bajo un coche en m

ovimiento, y reduciendo la distancia total

de frenada. ``La lección que hem

os aprendido de nuestro experimento... es que un A

G puede ayudar a

ajustar incluso un controlador bien diseñado. En nuestro caso, ya teníam

os una buena solución del problem

a; sin embargo, con la ayuda de un A

G, conseguim

os mejorar significativam

ente la estrategia de control. E

n resumen, parece que m

erece 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 A

Gs'' (p. 211).

Com

o cita Schechter 2000[59], el D

r. Peter S

enecal, de la Universidad de W

isconsin, utilizó algoritmos

genéticos de población pequeña para mejorar la eficiencia de los m

otores diésel. Estos m

otores funcionan inyectando com

bustible en una cámara de com

bustión que está llena de aire extremadam

ente com

primido, y por tanto extrem

adamente caliente, lo bastante caliente para hacer que el com

bustible explote y em

puje un pistón que produce la fuerza motriz del vehículo. E

ste diseño básico ha cambiado

poco desde que Rudolf D

iesel lo inventó en 1893; aunque se ha empleado m

ucho esfuerzo en realizar mejoras, es una tarea m

uy difícil de realizar analí ticamente, porque requiere un conocim

iento preciso del com

portamiento turbulento que exhibe la m

ezcla de combustible y aire, y de la variación sim

ultánea de muchos parám

etros independientes. Sin em

bargo, el método de S

enecal prescindía de ese conocimiento

específico del problema y, en cam

bio, funcionaba evolucionando parámetros com

o la presión de la cám

ara de combustión, los tiem

pos de inyección de combustible y la cantidad de com

bustible de cada inyección. E

l resultado: la simulación produjo un m

otor mejorado que consum

ía un 15% m

enos de com

bustible que un motor diesel norm

al y producía dos tercios menos de óxido nítrico de escape y la

mitad de hollín. L

uego el equipo de Senecal construyó un m

otor diésel real de acuerdo con las especificaciones de la solución evolucionada, y obtuvieron los m

ismos resultados. A

hora Senecal sigue

su trabajo evolucionando la geometría del propio m

otor, lo que con suerte producirá todavía más

mejoras.

Com

o citan Begley y B

eals 1995[9], Texas Instrum

ents utilizó un algoritmo genético para optim

izar la

Página 34 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

disposición de los componentes de un chip inform

ático, colocando las estructuras de manera que se

minim

ice el área total para crear un chip lo más pequeño posible. U

tilizando una estrategia de conexiones que no se le había ocurrido a ningún hum

ano, el AG alcanzó un diseño que ocupaba un 18%

menos de espacio.

Finalm

ente, como cita A

shley 1992[5], empresas de la industria aeroespacial, autom

ovilística, fabril, turbom

aquinaria y electrónica están utilizando un sistema de softw

are propietario conocido como

Engineous, que utiliza algoritm

os genéticos, para diseñar y mejorar m

otores, turbinas y otros dispositivos industriales. E

n palabras de su creador, el Dr. S

iu Shing T

ong, Engineous es ``un m

aestro `toqueteador', ensayando incansablem

ente las puntuaciones de escenarios de tipo ``y-si'' hasta que em

erge la mejor solución posible'' (p. 49). E

n un ensayo del sistema, E

ngineous consiguió producir un increm

ento del 0,92 por ciento de la eficiencia de una turbina experimental en só lo una sem

ana, mientras

que diez semanas de trabajo de un diseñador hum

ano sólo produjeron un 0,5 por ciento de mejora.

Supuestam

ente, Engineous no sólo cuenta con algoritm

os genéticos; también em

plea técnicas de optim

ización numérica y sistem

as expertos que utilizan reglas si- entonces para imitar el proceso de tom

a de decisiones de un ingeniero hum

ano. Sin em

bargo, estas técnicas dependen mucho de inform

ación específica del dom

inio, carecen de aplicabilidad general, y son propensas a quedar atrapadas en óptimos

locales. En contraste, el uso de algoritm

os genéticos permite a E

ngineous explorar regiones del espacio de búsqueda que pasan por alto los otros m

étodos.

Engineous ha obtenido un am

plio uso en una gran variedad de industrias y problemas. E

l más fam

oso fue cuando se utilizó para m

ejorar la turbina generadora de energía del avión Boeing 777; com

o inform

an Begley y B

eals 1995[ 9], el diseño optimizado genéticam

ente era casi un 1% m

ás eficiente en com

bustible que los motores anteriores, lo que en un cam

po como éste es una ganancia caída del cielo.

Engineous tam

bién se ha utilizado para optimizar la configuración de m

otores 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. R

ao 1998[52] inform

a también de que la N

ASA ha utilizado E

ngineous 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 crea

cionistas

Com

o era de esperar, la demostración real del poder de la evolución que representan los A

Gs ha

resultado sorprendente y descorcentante para los creacionistas, que siempre han afirm

ado que sólo un diseño inteligente, no la variación aleatoria y la selección, puede haber producido la cantidad y com

plejidad de información que contienen los seres vivos. P

or tanto, han argumentado que el éxito de

los algoritmos genéticos no nos perm

ite 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 D

r. Don B

atten, de ``Answ

ers in Genesis'', que ha escrito un artículo titulado ``A

lgoritmos

genéticos - ¿demuestran que la evolución funciona?'', y un creacionista de tipo tierra-vieja y defensor del

diseño inteligente, el Dr. W

illiam D

embski, cuyo reciente libro ``N

o Free L

unch'' (Dem

bski 2002[21]) trata sobre este tem

a.

Don Batten

Algunos ca

racteres d

e los seres v

ivos son cualitativos, m

ientras que los AGs son

siempre cu

antitativos

Página 35 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Batten afirm

a que los AGs deben ser cuantitativos, de m

anera que se pueda seleccionar cualquier mejora. E

sto es cierto. Luego continua diciendo: ``M

uchos caracteres biológicos son cualitativos -o funcionan o no funcionan, así que no existe una m

anera de llegar paso a paso de la ausencia de función a la función''. S

in embargo, esta aseveración no ha sido dem

ostrada, y no está apoyada por la evidencia. Batten ni siquiera intenta ofrecer un ejem

plo de caracter biológico que ``o funciona o no funciona'', y por tanto no pueda construirse paso a paso.

Pero aunque hubiera ofrecido tal ejem

plo de caracter, ¿cómo podría dem

ostrar razonablemente que no

hay un camino paso a paso hasta él? A

unque no conozcamos tal cam

ino, ¿significa eso que no existe ninguno? P

or supuesto que no. Batten afirm

a efectivamente que si no entendem

os cómo han

evolucionado ciertos caracteres, entonces es imposible que esos caracteres hayan evolucionado -un

ejemplo clásico de la falacia lógica elem

ental del argumento de la ignorancia. E

l espacio de búsqueda de todas las posibles variantes de cualquier caracter biológico dado es enorm

e, y en la mayoría de los casos

nuestro conocimiento supone tan sólo una fracción infinitesim

al de todas las posibilidades. Perfectam

ente pueden existir numerosos cam

inos 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 m

uchas estructuras y sistemas biológicos

complejos, tanto m

acroscópicos como m

icroscópicos (por ejemplo, vea estas páginas sobre la evolución

de sistemas m

oleculares complejos, genes ``reloj'', la lengua del pájaro carpintero o el escarabajo

bombardero). T

enemos justificación para creer probable que los que nos han eludido hasta ahora

también se entenderán con claridad en el futuro.

De hecho, los propios A

Gs nos ofrecen una excelente razó n para suponer esto. M

uchos de los problemas

en los que se han aplicado son problemas com

plejos de ingeniería y diseño de los que no se conocía la solución previam

ente, y por lo tanto el problema no podía ``am

añarse'' para facilitar el éxito del algoritm

o. Si los creacionistas tuvieran razón, habría sido com

pletamente razonable esperar que los

algoritmos gené ticos hubieran fallado estrepitosam

ente una y otra vez al ser aplicados a estos problemas,

pero, en cambio, ha ocurrido justo lo contrario: los A

Gs han descubierto soluciones poderosas y de gran

calidad a problemas difíciles en una gran variedad de cam

pos. Esto pone seriam

ente en duda incluso si existen problem

as como los que B

atten describe, cuyas soluciones sean inaccesibles a un proceso evolutivo.

Los AGs selec

cionan un caracter ca

da vez, m

ientras que los seres v

ivos son

multidimensionales

Batten afirm

a que, en los AGs, ``se selecciona un caracter individual, m

ientras que cualquier ser vivo es multidim

ensional'', y afirma que en los seres vivos con cientos de caracteres, ``la selección tiene que

operar con todos los caracteres que afecten a la supervivencia'', mientras que ``[un] A

G no funciona con

tres o cuatro objetivos diferentes, o me atrevería a decir que ni siquiera con dos''.

Este argum

ento revela la profunda ignorancia de Batten sobre la literatura relevante. T

an sólo un vistazo superficial del trabajo realizado con algoritm

os evolutivos (o un vistazo a la sección anterior de este ensayo) habría revelado que los algoritm

os genéticos multiobjetivo son un cam

po de investigación im

portante y floreciente dentro del más am

plio campo de la com

putación evolutiva, y le habría evitado realizar una afirm

ación tan embarazosam

ente incorecta. Existen artículos de revista, núm

eros enteros de revistas prom

inentes sobre computación evolutiva, conferencias enteras y libros enteros sobre el tem

a de los A

Gs m

ultiobjetivo. Coello 2000[18] proporciona una recopilación m

uy extensa, con cinco páginas de referencias a artículos sobre el uso de algoritm

os genéticos multiobjetivo en una am

plio abanico de cam

pos; vea también F

leming y P

urshouse 2002[22]; Hanne 2000[33]; Z

itzler y Thiele 1999[65];

Página 36 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Fonseca y F

leming 1995[23]; S

rinivas y Deb 1994[60]; G

oldberg 1989[29], p. 197. Sobre el uso de A

Gs

multiobjetivo para resolver problem

as específicos, vea los libros y artículos: Obayashi et al. 2000[49];

Sasaki et al. 2001[57]; B

enini y Toffolo 2002[10]; H

aas, Burnham

y Mulls 1997[32]; C

hryssolouris y Subram

aniam 2001[ 16]; H

ughes y Leyland 2000[37]; H

e y Mort 2000[35]; K

ewley y E

mbrechts 2002

[ 39]; Beasley, S

onander y Havelock 2001[8]; S

ato et al. 2002[58]; Tang et al. 1996[62]; W

illiams,

Crossley y L

ang 2001[64]; Koza et al. 1999[41]; K

oza et al. 2003[42]. Vea un repositorio extenso de

referencias sobre AGs m

ultiobjetivo en http://www.lania.m

x/ccoello/EM

OO.

Los AGs no perm

iten la posibilidad de una extinción o una catástro

fe de erro

res

Batten afirm

a que, en los AGs, ``siem

pre sobrevive algo para mantener el proceso'', m

ientras que esto no es necesariam

ente cierto en el mundo real -en resum

ent, los AGs no perm

iten la posibilidad de una extinción.

Sin em

bargo, esto no es cierto; la extinción puede ocurrir. Por ejem

plo, algunos AGs utilizan un m

odelo de selección con um

bral en el que los individuos deben tener una aptitud superior a un nivel predeterm

inado para poder sobrevivir y reproducirse (Haupt y H

aupt 1998[34], p. 37). Si no hay ningún

individuo que cumpla este criterio en este tipo de A

G, la población puede extinguirse efectivam

ente. Pero incluso en A

Gs que no establecen um

brales pueden ocurrir estados análogos a la extinción. Si las

tasas de mutación son dem

asiado altas o las presiones selectivas demasiado fuertes, un A

G nunca

encontrará una solución factible. La población puede acabar en un caos sin rem

edio al verse afectados los cantidatos aptos por el hecho de que las m

utaciones perjudiciales se desarrollen con más rapidez de

la que la selección puede eliminarlas (catástrofe de errores), o puede retorcerse inútilm

ente, incapaz de conseguir ningún aum

ento de la aptitud lo 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 al program

a valores diferentes -para el tam

año de la población, para la tasa de mutación, para la presión selectiva- y com

enzar de nuevo. Obviam

ente, 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 perm

anecerán viables ocurran las m

utaciones que ocurran'', pero tampoco existe una regla así en los algoritm

os genéticos.

Batten tam

bién afirma que ``los A

Gs que he observado preservan artificialm

ente a los mejores de la

generación anterior y los protegen de las mutaciones o la recom

binación, en caso de que no se produzca algo m

ejor en la siguiente generación''. Abordaré esta crítica en el siguiente punto.

Los AGs ignoran el c

oste d

e las su

stituciones

La siguiente afirm

ación de Batten es que los A

Gs ignoran el ``dilem

a de Haldane'', que dice que un alelo

que contribuya menos a la aptitud de un organism

o tardará correspondientemente m

ás tiempo en fijarse

en la población. Obviam

ente, a lo que se refiere es a la técnica de selección elitista, que selecciona autom

áticamente al m

ejor candidato de cada generación sin importar lo pequeña que sea su ventaja

sobre sus competidores. T

iene razón al sugerir que, en la naturaleza, las ventajas competitivas m

uy pequeñas pueden tardar en propagarse m

ucho más. L

os algoritmos genéticos no son un m

odelo exacto de la evolución biológica a este respecto.

Sin em

bargo, 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. C

omo reconoce

Batten, el dilem

a de Haldane no afirm

a que una mutación ligeram

ente ventajosa nunca quedará fijada en una población; afirm

a que tardará más en hacerlo. S

in embargo, cuando el tiem

po de computación está

muy dem

andado o cuando un investigador de AGs desea obtener una solución con m

ayor rapidez, puede

Página 37 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

ser deseable saltarse este proceso implem

entando el elitismo. U

n punto importante es que el elitism

o no afecta a qué m

utaciones surgen, sólo asegura la selección de las mejores que surjan. N

o importaría lo

fuerte que fuera la selección si no ocurrieran mutaciones que increm

entasen la información. E

n otras palabras, el elitism

o acelera la convergencia una vez que se ha descubierto una solución buena -no provoca un resultado que no habría ocurrido de otra m

anera. Por lo tanto, si los algoritm

os genéticos con elitism

o pueden producir información nueva, entonces tam

bién lo puede hacer la evolución en la naturaleza.

Adem

ás, no todos los AGs utilizan selección elitista. M

uchos 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 m

enor éxito. Por

ejemplo, K

oza et al 2003[ 42], p. 8-9, proporciona ejemplos de 36 casos en los que la program

ación genética ha producido resultados com

petitivos 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), 10 de los cuales duplican la funcionalidad de la patente de manera diferente, e

incluyendo además dos nuevos inventos patentables y cinco algoritm

os nuevos que superan a cualquier algoritm

o humano escrito para el m

ismo propósito. C

omo declara el D

r. Koza en una referencia anterior

al mism

o trabajo (1999[ 41], p. 1.070): ``No se utiliza la estrategia elitista''. A

lgunos artículos más

citados en este ensayo, en los que no se utiliza el elitismo: R

obin et al. 2003[54]; Rizki, Z

muda y

Tam

burino 2002[53]; Chryssolouris y S

ubramaniam

2001[16]; Burke y N

ewall 1999[11]; G

len y Payne

1995[ 28]; Au, C

han y Yao 2003[7]; Jensen 2003[38]; K

ewley y E

mbrechts 2002[39]; W

illiams,

Crossley y L

ang 2001[64]; Mahfoud y M

ani 1996[46]. En todos estos casos, sin ningún m

ecanismo para

asegurar que se seleccionaban los mejores individuos de cada generación, sin exim

ir a estos individuos del potencial cam

bio aleatorio perjudicial, los algoritmos genéticos siguen produciendo resultados

poderosos, eficientes y competitivos con los resultados hum

anos. Este hecho puede ser sorprendente

para creacionistas como B

atten, pero es algo completam

ente esperado para los defensores de la evolución.

Los AGs ignoran las lim

itaciones tem

porales p

ara una generación

Esta crítica es confusa. B

atten afirma que una generación puede durar m

icrosegundos en un AG,

mientras que en los seres vivos una generación puede durar desde m

inutos hasta años. Esto es cierto,

pero no explica cómo influye esto en la validez de los A

Gs com

o evidencia para la evolución. Si un A

G

puede generar información nueva, tarde el tiem

po que tarde, entonces la evolución natural puede hacer lo m

ismo sin duda; que los A

Gs pueden efectivam

ente 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 realm

ente 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 em

bargo, la respuesta que han proporcionado estos científicos está en completo acuerdo con las

escalas de tiempo evolutivas. N

umerosas líneas independientes de evidencia, incluyendo la datación

isocrónica radiométrica, los ritm

os de enfriamiento de las enanas blancas, la no existencia en la

naturaleza de isótopos con tiempos cortos de sem

ideintegración, los ritmos de alejam

iento de las galaxias lejanas, y el análisis de la radiación cósm

ica de fondo, convergen hacia la mism

a conclusión: una T

ierra y un universo con muchos m

iles de millones de años, sin duda tiem

po suficiente para que la evolución haya producido toda la diversidad de vida que observam

os hoy para todas las estimaciones

razonables.

Las altas tasas de mutación y rep

roducción que emplean los AGs no son rea

listas

Batten afirm

a, sin proporcionar ninguna evidencia o referencia que le apoye, que los AGs ``producen

Página 38 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

comúnm

ente cientos o miles de `descendientes' por generación'', un ritm

o que ni siquiera las bacterias, los organism

os biológicos que se reproducen con mayor velocidad, pueden igualar.

Esta crítica erra el tiro de varias m

aneras. Prim

ero, si la métrica que se utiliza es (com

o debería ser) el núm

ero de descendientes por generación, en lugar del número de descendientes por unidad de tiem

po absoluto, entonces existen evidentem

ente organismos biológicos que pueden reproducirse a ritm

os mayores que los de las bacterias y que casi igualan los ritm

os que Batten considera no realistas. P

or ejem

plo, una sola rana puede poner miles de huevos de una vez, cada uno de los cuales tiene el potencial

de desarrollarse como adulto. D

e acuerdo, la mayoría de éstos norm

almente no sobrevivirán debido a las

limitaciones de recursos y a la depredación, pero entonces la m

ayoría de la ``descendencia'' de cada generación en un A

G tam

poco sobrevivirá.

Segundo, y m

ás importante: un algoritm

o genético trabajando para resolver un problema no pretende

representar a un solo organismo. E

n cambio, un algoritm

o genético es más análogo a una población

completa de organism

os -después de todo, son las poblaciones, y no los individuos, los que evolucionan. Por supuesto, es com

pletamente plausible que una población tenga colectivam

ente cientos o miles de

descendientes por generación. (El creacionista W

alter ReM

ine comete este m

ismo error con respecto al

programa ``w

easel'' del Dr. R

ichard Daw

kins. Vea este M

ensaje del Mes para m

ás información).

Adem

ás, dice Batten, la tasa de m

utació n es artificialmente alta en los A

Gs, m

ientras que los seres vivos tienen una m

aquinaria de comprobación de errores diseñada para lim

itar la tasa de mutación en

aproximadam

ente 1 por cada 10.000 millones de par de bases (aunque esto es dem

asiado poco -la cifra real está m

ás cerca de 1 por cada 1.000 millones. V

er Daw

kins 1996[20], p. 124). Por supuesto, esto es

cierto. Si los A

Gs m

utasen a este ritmo, tardarían m

uchísimo en resolver problem

as reales. Evidentem

ente, lo que debe considerarse relevante es la tasa de mutación relativa al tam

año del genoma.

La tasa de m

utación debe ser lo bastante alta para promover una cantidad suficiente de diversidad en la

población sin acabar con los individuos. Un ser hum

ano corriente posee entre una y cinco mutaciones;

esto es perfectamente realista para la descendencia de un A

G.

Los AGs tien

en genomas artificia

lmente p

equeños

El argum

ento de Batten de que el genom

a de un algoritmo genético ``es artificialm

ente pequeño y sólo realiza una cosa'' está com

pletamente errado. E

n primer lugar, com

o ya hemos visto, no es cierto que un

AG sólo realice una cosa; hay m

uchos ejemplos de algoritm

os genéticos diseñados especí ficamente para

optimizar m

uchos parámetros sim

ultáneamente, a m

enudo muchos m

ás parámetros de los que podría

manejar un diseñador hum

ano.

¿Y exactam

ente cómo cuantifica B

atten lo de ``artificialmente pequeño''? M

uchos algoritmos

evolutivos, como el program

a genético de John Koza, utilizan codificaciones de tam

año variable donde el tam

año de las soluciones candidatas pueden crecer arbitrariamente. B

atten afirma que hasta los seres

vivos más sencillos tienen m

ucha más inform

ación en su genoma que la que un A

G haya producido

nunca, pero si los organismos vivos actuales tienen genom

as relativamente grandes es porque se ha

ganado mucha com

plejidad en el curso de los miles de años de evolución. C

omo señala el artículo

Probabilidad de abiogénesis, hay buenas razones para creer que los prim

eros organismos vivos eran

mucho m

ás sencillos que cualquier especie actual -las moléculas autorreplicadoras probablem

ente no tenían m

ás de 30 o 40 subunidades, pudiendo quedar especificadas perfectamente con los 1.800 bits de

información que B

atten reconoce que ha generado al menos un A

G. A

simism

o, los algoritmos genéticos

son una técnica muy nueva cuyo potencial com

pleto todavía no ha sido explotado; las propias com

putadoras digitales sólo tienen unas pocas décadas, y como señala K

oza (2003[ 42], p. 25), las técnicas de com

putación evolutiva han generado resultados cada vez más sustanciales y com

plejos

Página 39 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

durante los últimos 15 años, en sincronía con el rápido aum

ento de la potencia computacional, a m

enudo referida com

o la ``ley de Moore''. A

l igual que la vida primigenia era m

uy sencilla comparada con la que

vino después, es probable que los algoritmos genéticos actuales, a pesar de los im

presionantes resultados que ya han producido, den origen a resultados m

ucho más im

portantes en el futuro.

Los AGs ignoran la posibilidad de que ocurran mutaciones p

or todo el g

enoma

Aparentem

ente, Batten no com

prende cómo funcionan los algoritm

os genéticos, y lo demuestra

realizando este argumento. A

firma que, en la vida real, ``las m

utaciones 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

mism

o no es cierto para los AGs, se equivoca. E

xactamente igual que en los seres vivos, los A

Gs deben

escardar los genes perjudiciales al tiempo que seleccionan los beneficiosos.

Batten continua afirm

ando que ``el propio programa está protegido contra las m

utaciones, sólo las secuencias objetivo m

utan'', y si el programa m

utara, fallaría poco después. Esta crítica, sin em

bargo, es irrelevante. N

o existe razón para que el programa que gobierna a un A

G tenga que m

utar. El program

a no es parte del algoritm

o genético; el programa es el que supervisa al algoritm

o genético y produce las mutaciones en las soluciones candidatas, que son lo que el program

ador busca mejorar. E

l programa que

ejecuta al AG no es análogo a la m

aquinaria reproductiva de un organismo, una com

paración que trata de establecer B

atten. En cam

bio, 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 cam

bien ni necesitan ``protegerse'' de ello.

Los AGs ignoran los problem

as de la complejid

ad irred

ucible

Utilizando el argum

ento de la ``'' del creacionista de tipo tierra-vieja Michael B

ehe, Batten argum

enta: ``M

uchos caracteres biológicos requieren la presencia de muchos com

ponentes distintos, funcionando juntos, para que el caracter pueda existir'', m

ientras que esto no ocurre en los AGs.

Sin em

bargo, es trivial demostrar que esta afirm

ación es falsa, ya que los algoritmos genéticos han

producido sistemas irreduciblem

ente complejos. P

or ejemplo, el circuito reconocedor de voz que

evolucionó el Dr. A

drian Thom

pson (Davidson 1997[19]) está com

puesto 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 alim

entación, todo el sistema deja de

funcionar. Esto se ajusta a la definición de sistem

a complejo irreducible de B

ehe, y demuestra que un

proceso evolutivo puede producir cosas así.

Debe señalarse que este argum

ento es el mism

o que el primero, sim

plemente presentado en un lenguaje

distinto, y por tanto la refuntación es la mism

a. La com

plejidad 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 com

putadora.

Los AGs ignoran la poligenia, la pleiotropía y otras co

mplejid

ades g

enéticas

Batten argum

enta que los AGs ignoran asuntos com

o la poligenia (la determinació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 em

bargo, ninguna de estas afirmaciones es cierta. L

os AGs no ignoran la poligenia y la pleiotropía:

simplem

ente se permite que estas propiedades surjan de m

anera natural en lugar de programarlas

Página 40 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

deliberadamente. E

s obvio que en cualquier sistema com

plejo 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 sistem

a; por tanto, los A

Gs incorporan de m

anera natural la poligenia y la pleiotropía. ``En la literatura sobre

algoritmos genéticos, la interacción entre parám

etros se conoce como ep

istasis (un térm

ino biológico para la interacción entre genes). C

uando hay poca o ninguna epistasis, los algoritmos de búsqueda

mínim

a [es decir, los trepacolinas **-A.M

.] rinden mejor. L

os algoritmos genéticos brillan cuando la

epistasis es media o alta...'' (H

aupt y Haupt 1998[34], p. 31, itálicas originales).

Igualmente, hay algunas im

plementaciones de algoritm

os genéticos que sí tienen cromosom

as diploides y genes dom

inantes y recesivos (Goldberg 1989[ 29], p. 150; M

itchell 1996[47], p. 22). Sin em

bargo, los que no lo son sim

plemente se parecen m

ás a los organismos haploides, com

o las bacterias, que a los organism

os diploides, como los seres hum

anos. Ya que las bacterias están entre los organism

os más

exitosos de este planeta (para ciertas medidas), tales A

Gs siguen siendo un buen m

odelo de la evolución.

Los AGs no tienen múltiples sistem

as de lectu

ra

Batten habla de la existencia de m

últiples sistemas de lectura en los genom

as de algunos seres vivos, en los que las secuencias de A

DN codifican distintas proteínas funcionales cuando se leen en direcciones

distintas o con distintos desplazamientos de inicio. A

firma que ``crear un A

G para generar una

codificación con información densa así parecería im

posible''.

Un reto así pide una respuesta, y aquí está: S

oule y Ball 2001[ 61]. E

n este artículo, los autores presentan un algoritm

o genético con múltiples sistem

as de lectura y codificación densa, permitiéndole alm

acenar más inform

ación que el tamaño total de su genom

a. Al igual que los codones de tres nucleótidos

especifican aminoácidos en los genom

as 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 mism

o nú mero de codones en los

sistemas biológicos). C

omo los codones tenían cinco dígitos de longitud, había cinco sistem

as de lectura posibles. L

a secuencia 11111 sirve como codon de ``com

ienzo'' y la 00000 como codon de ``parada'';

como el codon de com

ienzo y parada pueden aparecer en cualquier lugar del genoma, la longitud de

cada individuo era variable. Las regiones del crom

osoma que no caían entre pares com

ienzo-parada eran ignoradas.

El A

G se probó con cuatro problem

as clásicos de maxim

ización de funciones. ``Inicialmente, la m

ayorí a de los bits no participan en ningún gen, es decir, la m

ayor parte de un cromosom

a no codifica nada. De

nuevo, esto es porque en los individuos iniciales aleatorios hay relativamente pocos pares de codones

comienzo-parada. S

in embargo, el núm

ero de bits que no participan disminuye extrem

adamente rápido''.

Durante el curso de la ejecución, el A

G puede increm

entar la longitud efectiva de su genoma

introduciendo nuevos codones de comienzo en distintos sistem

as de lectura. Al final de la ejecució n, ``la

cantidad de superposiciones es bastante alta. Muchos bits participan en varios genes (a m

enudo en los cinco)''. E

n todos los problemas probados, el A

G em

pezó, de media, con 5 variables especificadas; al

final de la ejecución, ese número se había increm

entado hasta una media de 25.

En los problem

as de prueba, el AG con m

últiples sistemas de lectura produjo soluciones

significativamente m

ejores que un AG estándar en dos de los cuatro problem

as, y mejores soluciones

medias en los otros dos. E

n uno de los problemas, el A

G com

primió con éxito 625 bits de inform

ación en un crom

osoma de sólo 250 bits de longitud, utilizando sistem

as de lectura alternativos. Los autores

tildan este comportam

iento de ``extremadam

ente sofisticado'' y concluyen que ``estos datos muestran

que un AG puede utilizar con éxito sistem

as de lectura a pesar de la complejidad añadida'' y que ``es

claro que un AG puede introducir nuevos`genes' m

ientras sea necesario para resolver un cierto problem

a, incluso con las dificultades impuestas al utilizar codones de com

ienzo y parada y genes

Página 41 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

superpuestos''.

Los AGs tien

en objetiv

os predeterm

inados

Com

o muchas otras, esta objeción dem

uestra que Batten no com

prende bien lo que es un algoritmo

genético y cómo funciona. A

rgumenta que los A

Gs, al contrario que la evolución, tienen objetivos

predeterminados y especificados desde el principio, y com

o ejemplo de esto, ofrece el program

a ``w

easel'' del Dr. R

ichard Daw

kins.

Sin em

bargo, el programa w

easel no es un verdadero algoritmo genético, y no representa a los

algoritmos genéticos, precisam

ente por esa razón. No pretendía dem

ostrar el poder de resolución de problem

as de la evolución. En cam

bio, 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 predeterm

inado de antemano.

Los algoritm

os 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. E

n este mism

o sentido, la evolución también tiene un objetivo: producir organism

os que estén m

ejor adaptados a su entorno y por tanto experimenten un m

ayor éxito reproductivo. Pero al igual

que la evolución es un proceso sin objetivos específicos, los AGs no especifican de antem

ano cómo

debe resolverse un problema dado. L

a 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. L

a solución en sí emerge luego m

ediante un proceso de mutación y selección.

La siguiente afirm

ación de Batten dem

uestra claramente que no entiende lo que es un algoritm

o genético. A

firma que ``quizás si el program

ador pudiera dar con un programa que perm

itiera que ocurriera cualquier cosa y luego m

idiera la capacidad de supervivencia de los `organismos', se estaría

acercando a lo que se supone que hace la evolución'' -pero así es exactamente com

o funcionan los algoritm

os genéticos. Generan aleagoriam

ente soluciones candidatas y provocan mutaciones aleatorias

sobre ellas durante muchas generaciones. N

o se especifica ninguna configuración de antemano; com

o dice B

atten, se permite que ocurra cualquier cosa. C

omo escribe John K

oza (2003[42], p. 37), repitiendo misteriosam

ente las palabras de Batten: ``U

na característica importante... es que la selección [en la

programación genética] no es codiciosa. L

os individuos que se sabe que son iferiores serán seleccionados hasta un cierto grado. N

o 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. P

uede ocurrir cualquier cosa y nada está garantizado''. (U

na 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 m

utadas aleatoriam

ente, surgen soluciones eficientes, complejas y poderosas a problem

as difíciles, soluciones que no fueron diseñadas por ninguna inteligencia y que a m

enudo pueden igualar o superar a las soluciones diseñadas por los hum

anos. La alegre afirm

ació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 rea

lidad

La crítica final de B

atten dice así: ``Para un A

G particular, necesitam

os preguntar qué parte de la `inform

ación' generada por el programa está en realidad especificada en el program

a, en lugar de haber sido generada de novo''. A

cusa a los AGs de que a m

enudo no hacen más que encontrar la m

ejor manera

de que ciertos módulos interaccionen, cuendo los propios m

ódulos y las maneras que tienen de

interactuar están especificadas de antemano.

Página 42 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Es difícil saber qué hacer con este argum

ento. Cualquier problem

a imaginable -los térm

inos en una ecuación de cálculo, las m

oléculas en una célula, los componentes de un m

otor, el capital en un mercado

financiero- pueden expresarse en términos de m

ódulos que interactúan de cierta manera. S

i todo lo que se tiene son m

ódulos sin especificar que interactúan de maneras sin especificar, no hay problem

a que resolver. ¿S

ignifica esto que la solución a ningún problema requiere la generación de inform

ación nueva?

Respecto a la crítica de B

atten sobre que la información contenida en la solución esté especificada en el

problema, la m

ejora manera de m

itigar sus preocupaciones es señalar la cantidad de ejemplos en los que

los AGs com

ienzan con poblaciones iniciales generadas aleatoriamente que no están de ninguna m

anera diseñadas para ayudar al A

G a resolver el problem

a. Algunos de tales ejem

plos son: Graham

-Row

e 2004[31]; D

avidson 1997[19]; Assion et al. 1998[6]; G

iro, Cyrillo y G

alvão 2002[27]; Glen y P

ayne 1995[28]; C

hryssolouris y Subram

aniam 2001[16]; W

illiams, C

rossley y Lang 2001[64]; R

obin et al. 2003[ 54]; A

ndreou, Georgopoulos y L

okothanassis 2002[4]; Kew

ley y Embrechts 2002[39]; R

izki, Zmuda y

Tam

burino 2002[53]; y especialmente K

oza et al. 1999[41] y Koza et al. 2003[42], que analiza el uso de

programación genética para generar 36 inventos com

petitivos con los humanos de diseños de circuitos

analógicos, biología molecular, algoritm

ia, diseño de controladores industriales y otros campos, todos

comenzando con poblaciones de candidatas iniciales generadas aleatoriam

ente.

De acuerdo, algunos A

Gs sí com

ienzan 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 mejorarla m

ediante la producción de información nueva. E

n cualquier caso, aunque la situación inicial sea com

o la describe Batten, encontrar la m

anera más eficiente m

ediante la que un cierto núm

ero de módulos puede interactuar bajo un conjunto dado de lim

itaciones puede ser una tarea nada trivial, cuya solución im

plique una cantidad considerable de información nueva: el diseño de

horarios en los aeropuertos internacionales, por ejemplo, o las líneas de m

ontaje de una fábrica, o la distribución de barriles entre alm

acenes y destilerías. De nuevo, los A

Gs han dem

ostrado su efectividad a la hora de resolver problem

as cuya complejidad abrum

aría a cualquier humano. A

la luz de las mú ltiples innovaciones y soluciones inesperadam

ente efectivas que ofrecen los AGs en m

uchos campos,

la afirmación de B

atten de que ``la cantidad de información nueva generada (por un A

G) es

normalm

ente bastante trivial'' suena verdaderamente hueca.

Willia

m Dembski

El reciente libro ``N

o Free L

unch: Why S

pecified Com

plexity Cannot B

e Purchased W

ithout Intelligence'' (``N

o dan almuerzos gratis: por qué la com

plejidad específica no puede conseguirse sin inteligencia''), del creacionista de tipo tierra-vieja, el D

r. William

Dem

bski, está dedicado principalm

ente al tema de los algoritm

os evolutivos y de cómo se relacionan con la evolución biológica.

En particular, el libro de D

embski trata de una cualidad elusiva que él llam

a ``complejidad especificada''

que, según afirma él, está presente en gran abundancia en los seres vivos, y que adem

ás los procesos evolutivos son incapaces de generar, dejando com

o única alternativa el ``diseño'' a un ``diseñador inteligente'' sin identificar, m

ediante mecanism

os sin especificar. Para apoyar su caso, D

embski apela a

un tipo de teoremas m

atemáticos conocidos com

o teoremas N

o Dan A

lmuerzos G

ratis que, según él, dem

uestran que los algoritmos evolutivos, de m

edia, no lo hacen mejor que una búsqueda ciega.

Richard W

ein ha escrito una refutación excelente y detallada de Dem

bski, titulada Not a F

ree Lunch B

ut a B

ox of Chocolates (N

o un almuerzo gratis sino una caja de chocolates), y no reproduciré sus ideas

aquí. En cam

bio, me centraré en el capí tulo 4 del libro de D

embski, que trata en detalle de los algoritm

os genéticos.

Página 43 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

Dem

bski tiene un argumento principal en contra de los A

Gs, desarrollado a fondo a lo largo de este

capítulo. Aunque no niega que pueden producir resultados im

presionantes -de hecho, dice que hay algo ``extrañam

ente persuasivo y casi mágico'' (p. 221) acerca del m

odo en el que los AGs pueden encontrar

soluciones diferentes a cualquier cosa diseñada por seres humanos-, sostiene que su éxito es debido a la

complejidad específica ``pasada de tapadillo'' dentro de ellos por sus diseñadores hum

anos y que posteriorm

ente se manifiesta en las soluciones que producen. ``E

n otras palabras, toda la complejidad

específica que obtenemos de un algoritm

o evolutivo debe aportarse primero en su construcción y en la

información que guía al algoritm

o. Los algoritm

os evolutivos, por tanto, no generan o crean complejidad

específica, sino que simplem

ente aprovechan la complejidad especificada que ya existe'' (p. 270).

El prim

er problema evidente en el argum

ento de Dem

bski es éste. Aunque su capítulo sobre algoritm

os evolutivos ocupa aproxim

adamente 50 páginas, las prim

eras 30 de ellas hablan de nada más que el

algoritmo ``w

easel'' del Dr. R

ichard Daw

kins, el cual, como ya se ha dicho, no es un verdadero

algoritmo genético y no es representativo de los algoritm

os genéticos. Los otros dos ejem

plos de Dem

bski -las antenas genéticas de alambre doblado de E

dward A

ltshuler y Derek L

inden y las redes neuronales que juegan a las dam

as de Kum

ar Chellapilla y D

avid Fogel- se introducen tan sólo en las

últimas 10 páginas del capítulo y son tratadas en tres páginas, en com

binación. Esto es una seria

deficiencia, considerando que el programa ``w

easel'' no es representativo de la mayor parte del trabajo

que se hace en el campo de la com

putación evolutiva; no obstante, analizaré los argumentos de D

embski

relacionados con él.

Respecto al program

a ``weasel'', D

embski afirm

a que ``Daw

kins y sus compañeros darw

inistas utilizan este ejem

plo para ilustrar el poder de los algoritmos evolutivos'' (p. 182) y, de nuevo, ``los darw

inistas... están encantados con el ejem

plo CREO Q

UE SE PARECE A

UNA C

OM

ADREJA

y lo consideran ilustrador del poder de los algoritm

os evolutivos para generar complejidad específica'' (p. 183). E

sto es un hom

bre de paja, creación de Dem

bski (¡sobre todo porque el libro de Daw

kins fue escrito mucho

antes de que Dem

bski acuñara ese término!). E

sto es lo que Daw

kins dice realmente del propósito de su

programa:

Lo que im

porta es la diferencia entre el tiempo que tarda la selección a

cum

ula

tiva, y el tiem

po que tardaría la mism

a computadora, funcionando absolutam

ente a la mism

a velocidad, en alcanzar la frase objetivo si estuviera obligada a utilizar el otro procedim

iento de selecció

n d

e un so

lo p

aso: m

ás o menos un m

illón de millones de m

illones de millones

de millones de años'' (D

awkins 1996[20], p. 49, itálicas originales).

En otras palabras, el program

a ``weasel'' pretendía dem

ostrar la diferencia entre dos tipos distintos de selección: la selección de un solo paso, en la que un resultado com

plejo está producido por puro azar en un solo salto, y la selección acum

ulativa, en la que un resultado complejo se construye poco a poco

mediante un proceso de filtrado que preserva preferentem

ente las mejoras. N

unca pretendió ser una sim

ulación de la evolución en su totalidad.

La selección de un solo paso es el proceso absurdam

ente improbable atacado con frecuencia en la

literatura creacionista, comparándolo con un tornado pasando por una chatarrería y produciendo un

avión 747, o una explosión en una imprenta produciendo un diccionario. L

a selección acumulativa es lo

que realmente utiliza la evolución. U

tilizando la selección de un solo paso para alcanzar un resultado funcional de alguna com

plejidad significativa, hanría que esperar, de media, m

uchas veces la edad actual del universo. U

tilizando selecció n acumulativa, por contra, se puede alcanzar ese m

ismo resultado

en un periodo de tiempo com

parativamente m

uy corto. El objetivo del program

a ``weasel'' de D

awkins

era demostrar esta diferencia, y era el único objetivo del program

a. En una nota al pie de este capítulo,

Dem

bski escribe: ``Es curioso cóm

o se recicla el ejemplo de D

awkins sin ninguna indicación de las

dificultades fundamentales que lo acom

pañan'' (p. 230), pero tan sólo los conceptos erróneos de las

Página 44 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

mentes de los creacionistas com

o Dem

bski y Batten, que atacan al program

a ``weasel'' por no dem

ostrar algo que nunca pretendía dem

ostrar, son los que dan lugar a estas ``dificultades''.

A diferencia de todos los ejem

plos de algoritmo evolutivo tratados en este ensayo, el program

a ``weasel''

tiene ciertamente un resultado especificado de antem

ano, y la calidad de las soluciones que genera se juzga com

parándola explicítamente con ese resultado especificado de antem

ano. Por tanto, D

embski

tiene toda la razón cuando dice que el programa ``w

easel'' no genera información nueva. N

o obstante, luego realiza un salto gigantesco y com

pletamente injustificado, al extrapolar esta conclusió n a todos los

algoritmos evolutivos: ``C

omo única posibilidad que puede alcanzar el algoritm

o evolutivo de Daw

kins, la secuencia objetivo tiene de hecho una com

plejidad mínim

a... Por lo tanto, los algoritm

os evolutivos son incapaces de generar verdadera com

plejidad'' (p. 182). Hasta D

embski parece reconocer esto cuando

escribe: ``...la mayoría de los algoritm

os evolutivos de la literatura están programados para buscar en un

espacio de soluciones posibles a un problema hasta que encuentran una respuesta -no, com

o hace Daw

kins, programando explícitam

ente la respuesta de antemano'' (p. 182). P

ero luego, habiendo dado una razón perfectam

ente buena de por qué el programa ``w

easel'' no es representativo de los AGs en

conjunto, ¡prosigue inexplicablemente realizando esa falaz generalización!

En realidad, el program

a ``weasel'' es significativam

ente distinto de la mayoría de los algoritm

os genéticos, y por tanto el argum

ento por analogía de Dem

bski no se sostiene. Los verdaderos algoritm

os evolutivos, com

o los ejemplos exam

inados en este ensayo, no buscan simplem

ente un camino hacia

soluciones ya descubiertas por otros métodos -en cam

bio, se les presenta un problema para el que no se

conoce una solución óptima de antem

ano, y se les pide que descubran esa solución por su cuenta. En

realidad, si los algoritmos genéticos no pudieran hacer m

ás que redescubrir soluciones ya programadas

dentro de ellos, ¿qué sentido tendría utilizarlos? Sería un ejercicio de redundancia. S

in embargo, el

amplio interés científico (y com

ercial) por los AGs dem

uestra que hay mucha m

á s sustancia en ellos que en el ejem

plo bastante trivial al que Dem

bski pretende reducir todo este campo.

Después de colocar y luego derribar este hom

bre de paja, Dem

bski avanza hacia su siguiente línea de argum

entación: que la complejida específica exhibida por los resultados de los algoritm

os evolutivos más representativos ha sido ``pasada de tapadillo'' por los diseñadores dentro del algoritm

o, al igual que en el program

a ``weasel''. ``P

ero siempre encontram

os que cuando parece generarse complejidad

específica de la nada, en realidad ha sido cargada de antemano, pasada de tapadillo u ocultada a la

vista'' (p. 204). Dem

bski sugiere que el ``escondite'' más com

ún de la complejidad específica está en la

función de aptitud del AG. ``L

o que ha hecho [el algoritmo evolutivo] es aprovecharse de la

complejidad específica inherente a la función de aptitud y la ha utilizado para buscar y encontrar el

objetivo...'' (p. 194). Dem

bski prosigue argumentando que, antes de que un A

E pueda buscar una

solución en un paisaje adaptativo dado, antes debe emplearse algún m

ecanismo para seleccionar ese

paisaje adaptativo de entre lo que él llama un espacio de fases de todos los posibles paisajes adaptativos,

y que si ese mecanism

o es también evolutivo, antes debe em

plearse algún otro mecanism

o para seleccionar su función de aptitud de un espacio de fases aún m

ayor, y así sucesivamente. D

embski

concluye que la única manera de detener esta regresión infinita es m

ediante la inteligencia, la cual, según el, posee la irreducible y m

isteriosa habilidad de seleccionar una función de aptitud de un espacio de fases dado sin recurrir a espacios de fases de m

ayor orden. ``Só lo existe un generador de com

plejidad específica conocido, y éste es la inteligencia'' (p. 207).

Dem

bski tiene razón cuando dice que la función de aptitud ``guía a un algoritmo evolutivo hacia el

objetivo'' (p. 192). Sin em

bargo, no tiene razón cuando afirma que seleccionar la función de aptitud

correcta es un proceso que requiera la generación de más com

plejidad específica de la que el propio AE

produce. Com

o escribe Koza (1999[ 41], p. 39), la función de aptitud le dice a un algoritm

o evolutivo ``qué hay que hacer'', no ``cóm

o hacerlo''. A diferencia del nada representativo program

a ``weasel'',

normalm

ente la función de aptitud de un AE no especifica ninguna form

a particular que la solución deba

Página 45 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

adquirir, y por tanto no se puede decir que contribuya a la ``complejidad específica'' de la solución

evolucionada en ningún sentido.

Un ejem

plo ilustrará la idea con mayor detalle. D

embski afirm

a que en el experimento de las dam

as de Chellapilla y F

ogel, su elección de mantener constante el criterio de victoria entre juego y juego

``insertó una enorme cantidad de com

plejidad específica'' (p. 223). Desde luego, es cierto que el

producto final de este proceso exhibía una gran cantidad de complejidad específica (se defina com

o se defina ese térm

ino). Pero ¿es cierto que la m

edida de aptitud elegida contuviese tanta complejidad

específica? Esto es lo que dicen realm

ente Chellapilla y F

ogel:

Para apreciar el nivel de juego que se había conseguido, puede ser útil considerar el

siguiente experimento m

ental. Suponga que le piden jugar a un juego en un tablero de ocho

por ocho casillas con colores alternos. Hay 12 piezas en cada lado ordenadas de una cierta

manera antes de em

pezar el juego. Le dicen las reglas de m

ovimiento de las piezas (es decir,

el movim

iento diagonal, comer forzosam

ente, la promoción) y que se pueden com

er piezas. Sin em

bargo, no le dicen si comer piezas es favorable o desfavorable (hay una versión de

las damas llam

ada `damas suicidas', en la que el objetivo es `perder' lo m

ás rápidamente

posible) o incluso si constituye información relevante. Y

lo que es más im

portante, no le dicen cuál es el objetivo del juego. U

sted simplente realiza m

ovimientos y en algún

mom

ento un observador externo declara que el juego ha acabado. No obstante, no le

proporcionan información de si ha ganado, perdido o em

patado. Los únicos datos que usted

recibe llegan tras un mínim

o de cinco partidas y se ofrecen en la forma de una puntuación

global. Por tanto, no puede saber con certeza qué juegos contribuyeron a la puntuación

global ni en qué grado. Su reto consiste en inducir los m

ovimientos apropiados en cada

partida tan sólo a partir de esta burda información'' (C

hellapilla y Fogel 2001[13], p. 427).

La afirm

ación de Dem

bski de que esta medida de la aptitud insertó una ``enorm

e'' cantidad de com

plejidad específica excede los límites de lo absurdo. S

i se le diera la mism

a información a un ser

humano que nunca hubiera oído hablar de las dam

as, y meses después volviéram

os para descubrir que se ha convertido en un jugador experto a nivel internacional, ¿podem

os concluír que se ha generado com

plejidad específica?

Dem

bski afirma que para refutar su argum

ento, ``hace falta demostrar que encontrar la inform

ación que guía a un algoritm

o evolutivo hacia un objetivo es sustancialmente m

ás fácil que encontrar el objetivo directam

ente mediante una búsqueda ciega'' (p. 204). S

ostengo que ése es precisamente el caso.

Intuitivamente, no debe sorprender que la función de aptitud contenga m

enos información que la

solución evolucionada. Ésta es precisam

ente la razón por la que los AGs han hallado un uso tan am

plio: es m

ás fácil (requiere menos inform

ación) escribir una función de aptitud que mida lo buena que es una

solución que diseñar una buena solución desde cero.

En térm

inos más inform

ales, consideremos los dos ejem

plos de Dem

bski, la antena genética de alambre

doblado y la red neuronal jugadora de damas evolucionada llam

ada Anaconda. O

btener una estrategia ganadora requiere una gran cantidad de inform

ación detallada sobre el juego de las damas (considere a

Chinook y su enorm

e biblioteca de finales de partida). Sin em

bargo, no hace falta una información

igualmente detallada para reconocer una estrategia así cuando se la ve: todo lo que necesitam

os observar es que esa estrategia vence consistentem

ente a sus oponentes. De m

anera similar, una persona que no

supiera nada sobre cómo diseñar una antena que radie uniform

emente en una región hem

isférica en un cierto rango de frecuencias, podría sin em

bargo probar una antena así y verificar si funciona como se

pretende. En am

bos casos, determinar lo que constituye una aptitud alta es m

ucho más fácil (requiere

menos inform

ación) que averiguar cómo conseguir una aptitud alta.

Página 46 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

De acuerdo, aunque requiera m

enos información escoger una función de aptitud para un problem

a dado que resolver verdaderam

ente el problema definido por esa función de aptitud, sí que hace falta algo de

información para especificar la función de aptitud en prim

er lugar, y es una cuestión legítima preguntar

de dónde viene esta información inicial. D

embski todavía puede preguntar sobre el origen de la

inteligencia humana que nos perm

ite decidir resolver un problema en lugar de otro, o sobre el origen de

las leyes naturales del cosmos que hacen posible que la vida exista y florezca y que ocurra la evolución.

Éstas son preguntas válidas, y D

embski tiene derecho a pensar en ellas. S

in embargo, en este punto -

aparentemente inadvertido por el propio D

embski- se ha alejado de su argum

ento inicial. Ya no está

afirmando que la evolución no pueda ocurrir; en cam

bio, esencialmente está preguntando por qué

vivimos en un universo en el que puede ocurrir la evolución. E

n otras palabras, Dem

bski no parece darse cuenta de que la conclusión lógica de su argum

ento es la evolución teísta. Es perfectam

ente compatible

con un Dios que (com

o muchos cristianos, incluyendo el biólogo evolutivo K

enneth Miller, creen)

utilizó la evolución como su herram

ienta creativa, y creó el universo para hacer que fuera no sólo probable, sino seguro.

Concluiré aclarando algunos conceptos erróneos m

enores adicionales del capítulo 4 de No F

ree Lunch.

Para em

pezar, aunque Dem

bski, al contrario que Batten, está claram

ente informado acerca del cam

po de la optim

ización multiobjetivo, afirm

a erróneamente que ``hasta que no se consiga alguna form

a de univalencia, la optim

ización no puede comenzar'' (p. 186). E

l análisis de los algoritmos genéticos

multiobjetivo de este ensayo m

uestran el error de esta afirmación. Q

uizá otras técnicas de diseño tengan esta restricción, pero una de las virtudes de los A

Gs es precisam

ente que pueden establecer contrapartidas y optim

izar varios objetivos mutuam

ente exclusivos simultáneam

ente, y luego un supervisor hum

ano puede elegir la solución que mejor consiga los resultados esperados del grupo final

de soluciones paretianas. No es necesario ningún m

étodo para combinar m

últiples criterios en uno.

Dem

bski también afirm

a que los AGs ``parecen m

enos expertos a la hora de construír sistemas

integrados que requieran de múltiples partes para realizar funciones novedosas'' (p. 237). L

a gran cantidad de ejem

plos detallados en este ensayo (en particular, la utilización de John Koza de la

programación genética para diseñar circuitos analógicos com

plejos) demuestran que esta afirm

ación tam

bién es falsa.

Finalm

ente, Dem

bski menciona que IN

FORM

S, la organización profesional de la com

unidad de investigación de operaciones, le presta m

uy poca atención a los AGs, y esto ``es una razón para ser

escéptico acerca del alcance y poder general de esta técnica'' (p. 237). Sin em

bargo, sólo porque una sociedad científica particular no esté haciendo un uso generalizado de los A

Gs no significa que esos

usos no sean generalizados en otros sitios o en general, y este ensayo ha procurado demostrar que éste es

ciertamente el caso. L

as técnicas evolutivas han hallado una amplia variedad de usos en prácticam

ente todos los cam

pos de la ciencia que merece la pena nom

brar, además de m

uchas empresas del sector

comercial. A

quí hay una lista parcial:

�Lockheed M

artin (Gibbs 1996[25])

�GlaxoS

mithK

line (Gillet 2002[26])

�LBS C

apital Managem

ent (Naik 1996[48])

�First Q

uadrant (Begley and B

eals 1995[9]) �

Texas Instrum

ents (Begley and B

eals 1995[9]) �

U.S. W

est (Begley and B

eals 1995[9]) �

John Deere &

Co. (P

etzinger 1995[50]) �

Volvo (R

ao 1998[52]) �

Ascent T

echnology (Wired 2002[1])

�Boeing (A

shley 1992[5]) �

British P

etroleum (L

emley 2001[45])

Página 47 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

�Ford M

otor Com

pany (Lem

ley 2001[45]) �

Unilever (L

emley 2001[45])

�United D

istillers and Vintners (L

emley 2001[45])

En contraste, dada la escasez de descubrim

ientos e investigación científica estimulados por el diseño

inteligente, Dem

bski no se encuentra en posición de quejarse de la falta de aplicaciones prácticas. El

diseño inteligente es una hipótesis vacía, que no nos dice nada más que ``algún diseñador hizo algo, de

alguna manera, en algún m

omento, para provocar este resultado''. E

n contraste, este ensayo ha dem

ostrado con suerte que la evolución es una estrategia de resolución de problemas llena de

aplicaciones prácticas.

Conclusión

Hasta los creacionistas encuentran im

posible negar que la combinación de la m

utación y la selección natural puede producir adaptación. N

o obstante, todavía siguen intentando justificar su rechazo a la evolución dividiendo el proceso evolutivo en dos categorías -``m

icroevolución'' y ``macroevolución''- y

afirmando que sólo la segunda es controvertida, y que cualquier cam

bio evolutivo que podemos

observar es sólo un ejemplo de la prim

era.

Veam

os. La m

icroevolución y la macroevolución son térm

inos que tienen significado para los biólogos; se definen, respectivam

ente, como evolución por debajo del nivel de especies y evolución al nivel de

especies o por encima. P

ero la diferencia crucial entre el modo en el que los creacionistas utilizan estos

términos y el m

odo en el que lo hacen los científicos es que los científicos reconocen que los dos son fundam

entalmente el m

ismo proceso con los m

ismos m

ecanismos, tan sólo operando a diferentes

escalas. Sin em

bargo, los creacionistas están obligados a postular algún tipo de brecha infranqueable que los separa, para poder negar que los procesos de cam

bio y adaptación que vemos en la actualidad puedan

extrapolarse para producir toda la diversidad que vemos en el m

undo de los seres vivos.

No obstante, los algoritm

os genéticos hacen que esta idea sea insostenible, al demostrar la naturaleza sin

junturas del proceso evolutivo. Considerem

os, por ejemplo, un problem

a 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 uniform

es de 0 y 5 voltios. Digam

os que tenemos una solución candidata

que puede discriminar con precisión entre los dos tonos, pero sus salidas no son lo bastante uniform

es com

o se requiere; producen pequeñas ondulaciones en lugar del voltaje constante requerido. Supuestam

ente, de acuerdo con las ideas creacionistas, cambiar este circuito de su estado presente a la

solución perfecta sería ``microevolución'', un cam

bio pequeño dentro de las capacidades de la mutación

y la selección. Pero, sin duda -argum

entaría un creacionista-, llegar a este mism

o estado final desde una ordenación inicial com

pletamente aleatoria de com

ponentes sería ``macroevolución'', y estaría m

ás allá del alcance de un proceso evolutivo. S

in embargo, los algoritm

os genéticos han sido capaces de conseguir am

bas 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 óptim

a. No surgió ninguna dificultad o brecha

insalvable en ningún punto del camino. E

n ningún mom

ento hizo falta intervenció n humana para m

ontar un conjunto de com

ponentes irreduciblemente com

plejo (a pesar del hecho de que el producto final sí contiene tal cosa) o para ``guiar'' al sistem

a evolutivo a través de algún pico dificultoso. El circuito

evolucionó, sin la ayuda de ninguna orientación inteligente, desde un estado completam

ente aleatorio y no funcional hasta un estado rigurosam

ente complejo, eficiente y óptim

o. ¿Cóm

o puede no ser esto una dem

ostración experimental convincente del poder de la evolución?

Se dice que la evolución cultural hum

ana ha reemplazado a la biológica -que nosotros, com

o especie, hem

os llegado a un punto en el que somos capaces de controlar conscientem

ente nuestra sociedad,

Página 48 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

nuestro entorno y hasta nuestros genes al nivel suficiente para hacer que el proceso evolutivo sea irrelevante. S

e dice que los caprichos culturales de nuestra cambiante sociedad son los que determ

inan la aptitud hoy en día, en lugar de la m

archa enormem

ente lenta, en comparación, de la m

utación genética y la selección natural. E

n 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 com

enzamos a com

prender y explotar; a pesar de esto, ya está funcionando por todas partes, m

oldeando nuestra tecnología y mejorando nuestras vidas, y, en el futuro,

estos usos no harán sino multiplicarse. S

in un conocimiento detallado del proceso evolutivo no habrían

sido posibles ninguno de los incontables avances que le debemos a los algoritm

os genéticos. Aquí hay

una lección que deben aprender los que niegan el poder de la evolución y los que niegan que el conocim

iento de ella tenga beneficios prácticos. Por increíble que pueda parecer, la evolución funciona.

Com

o lo expresa el poeta Lord B

yron: ``Es extraño pero cierto; porque la verdad siem

pre es extraña, más extraña que la ficción.''

Bibliografía

1 ``A

daptive Learning: F

ly the Brainy S

kies.'' Wired, vol.10, no.3 (m

arzo de 2002). Disponible en

línea.

2 Altshuler, E

dward y D

erek Linden. ``D

esign of a wire antenna using a genetic algorithm

.'' Journ

al

of E

lectronic D

efense, vol.20, no.7, p.50-52 (julio de 1997).

3 Andre, D

avid y Astro T

eller. ``Evolving team

Darw

in United.'' E

n RoboCup-9

8: R

obot S

occer

World

Cup II, M

inoru Asada and H

iroaki Kitano (eds). L

ecture Notes in C

omputer S

cience, vol.1604, p.346-352. S

pringer-Verlag, 1999.

Ver tam

bién: Willihnganz, A

lexis. ``Softw

are that writes softw

are.'' Salo

n, 10 de agosto de 1998. Disponible en línea.

4 Andreou, A

ndreas, Efstratios G

eorgopoulos y Spiridon L

ikothanassis. ``Exchange-rates

forecasting: A hybrid algorithm

based on genetically optimized adaptive neural netw

orks.'' Com

puta

tional E

conom

ics, vol.20, no.3, p.191-210 (diciembre de 2002).

5 Ashley, S

teven. ``Engineous explores the design space.'' M

echanica

l Engin

eering, febrero de

1992, p.49-52.

6 Assion, A

., T. B

aumert, M

. Bergt, T

. Brixner, B

. Kiefer, V

. Seyfried, M

. Strehle y G

. Gerber.

``Control of chem

ical reactions by feedback-optimized phase-shaped fem

tosecond laser pulses.'' Scien

ce, vol.282, p.919-922 (30 de octubre de 1998).

7 Au, W

ai-Ho, K

eith Chan, y X

in Yao. ``A

novel evolutionary data mining algorithm

with

applications to churn prediction.'' IEEE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.7, no.6,

p.532-545 (diciembre de 2003).

8 Beasley, J.E

., J. Sonander y P

. Havelock. ``S

cheduling aircraft landings at London H

eathrow

using a population heuristic.'' Journ

al o

f the O

pera

tional R

esearch

Society, vol.52, no.5, p.483-

493 (mayo de 2001).

9 Begley, S

haron y Gregory B

eals. ``Softw

are au naturel.'' New

sweek, 8 de m

ayo de 1995, p.70.

Página 49 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

10 Benini, E

rnesto y Andrea T

offolo. ``Optim

al design of horizontal-axis wind turbines using blade-

element theory and evolutionary com

putation.'' Journ

al o

f Sola

r Energ

y Engin

eering, vol.124,

no.4, p.357-363 (noviembre de 2002).

11 Burke, E

.K. y J.P

. New

all. ``A m

ultistage evolutionary algorithm for the tim

etable problem.''

IEEE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.3, no.1, p.63-74 (abril de 1999).

12 Charbonneau, P

aul. ``Genetic algorithm

s in astronomy and astrophysics.'' T

he A

strophysica

l Jo

urn

al S

upplem

ent S

eries, vol.101, p.309-334 (diciembre de 1995).

13 Chellapilla, K

umar y D

avid Fogel. ``E

volving an expert checkers playing program w

ithout using hum

an expertise.'' IEEE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.5, no.4, p.422-428

(agosto de 2001). Disponible en línea.

14 Chellapilla, K

umar y D

avid Fogel. ``A

naconda defeats Hoyle 6-0: a case study com

peting an evolved checkers program

against commercially available softw

are.'' En P

roceed

ings o

f the 2

000

Congress o

n E

volu

tionary C

om

puta

tion, p.857-863. IE

EE Press, 2000. D

isponible en línea.

15 Chellapilla, K

umar y D

avid Fogel. ``V

erifying Anaconda's expert rating by com

peting against Chinook: experim

ents in co-evolving a neural checkers player.'' Neu

roco

mputin

g, vol.42, no.1-4, p.69-86 (enero de 2002).

16 Chryssolouris, G

eorge y Velusam

y Subram

aniam. ``D

ynamic scheduling of m

anufacturing job shops using genetic algorithm

s.'' Journ

al o

f Intellig

ent M

anufa

cturin

g, vol.12, no.3, p.281-293 (junio de 2001).

17 Coale, K

risti. ``Darw

in in a box.'' Wired

New

s, 14 de julio de 1997. Disponible en línea.

18 Coello, C

arlos. ``An updated survey of G

A-based m

ultiobjective optimization techniques.'' A

CM

Com

putin

g S

urveys, vol.32, no.2, p.109-143 (junio de 2000).

19 Davidson, C

live. ``Creatures from

primordial silicon.'' N

ew S

cientist, vol.156, no.2.108, p.30-35

(15 de noviembre de 1997). D

isponible en línea.

20 Daw

kins, Richard. T

he B

lind W

atch

maker: W

hy th

e Evid

ence o

f Evo

lutio

n R

eveals a

Universe

With

out D

esign. W

.W. N

orton, 1996.

21 Dem

bski, William

. No F

ree Lunch

: Why S

pecified

Com

plexity C

annot B

e Purch

ased

With

out

Intellig

ence. R

owman &

Littlefield, 2002.

22 Flem

ing, Peter y R

.C. P

urshouse. ``Evolutionary algorithm

s in control systems engineering: a

survey.'' Contro

l Engin

eering P

ractice, vol.10, p.1.223-1.241 (2002).

23 Fonseca, C

arlos y Peter F

leming. ``A

n overview of evolutionary algorithm

s in multiobjective

optimization.'' E

volu

tionary C

om

puta

tion, vol.3, no.1, p.1-16 (1995).

24 Forrest, S

tephanie. ``Genetic algorithm

s: principles of natural selection applied to computation.''

Scien

ce, vol.261, p.872-878 (1993).

25 Gibbs, W

. Wayt. ``P

rogramming w

ith primordial ooze.'' S

cientific A

merica

n, octubre de 1996,

Página 50 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

p.48-50.

26 Gillet, V

alerie. ``Reactant- and product- based approaches to the design of com

binatorial libraries.'' Jo

urn

al o

f Com

puter-A

ided

Molecu

lar D

esign, vol.16, p.371-380 (2002).

27 Giro, R

., M. C

yrillo y D.S. G

alvão. ``Designing conducting polym

ers using genetic algorithms.''

Chem

ical P

hysics L

etters, vol.366, no.1-2, p.170-175 (25 de noviembre de 2002).

28 Glen, R

.C. y A

.W.R

. Payne. ``A

genetic algorithm for the autom

ated generation of molecules

within constraints.'' Jo

urn

al o

f Com

puter-A

ided

Molecu

lar D

esign, vol.9, p.181-202 (1995).

29 Goldberg, D

avid. Gen

etic Alg

orith

ms in

Sea

rch, O

ptim

izatio

n, a

nd M

ach

ine L

earn

ing. A

ddison-W

esley, 1989.

30 Graham

-Row

e, Duncan. ``R

adio emerges from

the electronic soup.'' New

Scien

tist, vol.175, no.2.358, p.19 (31 de agosto de 2002). D

isponible en línea Ver tam

bién: Bird, Jon y P

aul Layzell. ``T

he evolved radio and its implications for m

odelling the evolution of novel sensors.'' E

n Pro

ceedin

gs o

f the 2

002 C

ongress o

n E

volu

tionary C

om

puta

tion,

p.1.836-1.841.

31 Graham

-Row

e, Duncan. ``E

lectronic circuit 'evolves' from liquid crystals.'' N

ew S

cientist , vol.181,

no.2.440, p.21 (27 de marzo de 2004).

32 Haas, O

.C.L., K

.J. Burnham

y J.A. M

ills. ``On im

proving physical selectivity in the treatment of

cancer: A system

s modelling and optim

isation approach.'' Contro

l Engin

eering P

ractice, vol.5,

no.12, p.1.739-1.745 (diciembre de 1997).

33 Hanne, T

homas. ``G

lobal multiobjective optim

ization using evolutionary algorithms.'' Jo

urn

al o

f H

euristics, vol.6, no.3, p.347-360 (agosto de 2000).

34 Haupt, R

andy y Sue E

llen Haupt. P

ractica

l Gen

etic Alg

orith

ms. John W

iley & Sons, 1998.

35 He, L

. y N. M

ort. ``Hybrid genetic algorithm

s for telecommunications netw

ork back- up routeing.'' BT T

echnolo

gy Jo

urn

al, vol.18, no.4, p. 42-50 (octubre de 2000).

36 Holland, John. ``G

enetic algorithms.'' S

cientific A

merica

n, julio de 1992, p. 66-72.

37 Hughes, E

van y Maurice L

eyland. ``Using m

ultiple genetic algorithms to generate radar point-

scatterer models.'' IE

EE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.4, no.2, p.147-163 (julio

de 2000).

38 Jensen, M

ikkel. ``Generating robust and flexible job shop schedules using genetic algorithm

s.'' IE

EE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.7, no.3, p.275-288 (junio de 2003).

39 Kew

ley, Robert y M

ark Embrechts. ``C

omputational m

ilitary tactical planning system.'' IE

EE

Tra

nsa

ctions o

n S

ystems, M

an a

nd C

ybern

etics, Part C

- Applica

tions a

nd R

eviews, vol.32, no.2,

p.161-171 (mayo de 2002).

40 Kirkpatrick, S

., C.D

. Gelatt y M

.P. V

ecchi. ``Optim

ization by simulated annealing.'' S

cience,

Página 51 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

vol.220, p.671-678 (1983).

41 Koza, John, F

orest Bennett, D

avid Andre y M

artin Keane. G

enetic P

rogra

mm

ing III: D

arw

inia

n

Inven

tion a

nd P

roblem

Solvin

g. Morgan K

aufmann P

ublishers, 1999.

42 Koza, John, M

artin Keane, M

atthew Streeter, W

illiam M

ydlowec, Jessen Y

u y Guido L

anza. G

enetic P

rogra

mm

ing IV

: Routin

e Hum

an-C

om

petitive M

ach

ine In

telligen

ce. Kluw

er Academ

ic Publishers, 2003.

Ver tam

bién: Koza, John, M

artin Keane y M

atthew Streeter. ``E

volving inventions.'' Scien

tific Am

erican, febrero de 2003, p. 52-59.

43 Keane, A

.J. y S.M

. Brow

n. ``The design of a satellite boom

with enhanced vibration perform

ance using genetic algorithm

techniques.'' En A

daptive C

om

putin

g in

Engin

eering D

esign a

nd C

ontro

l '9

6 - P

roceed

ings o

f the S

econd In

ternatio

nal C

onferen

ce, I.C. P

armee (ed), p.107-113. U

niversity of P

lymouth, 1996.

Ver tam

bién: Petit, C

harles. ``Touched by nature: P

utting evolution to work on the assem

bly line.'' U

.S. N

ews a

nd W

orld

Rep

ort, vol.125, no.4, p.43-45 (27 de julio de 1998). D

isponible en línea.

44 Lee, Y

onggon y Stanislaw

H. Z

ak. ``Designing a genetic neural fuzzy antilock-brake-system

controller.'' IE

EE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.6, no.2, p.198-211 (abril de

2002).

45 Lem

ley, Brad. ``M

achines that think.'' Disco

ver, enero de 2001, p.75-79.

46 Mahfoud, S

am y G

anesh Mani. ``F

inancial forecasting using genetic algorithms.'' A

pplied

Artificia

l Intellig

ence, vol.10, no.6, p.543-565 (1996).

47 Mitchell, M

elanie. An In

troductio

n to

Gen

etic Alg

orith

ms. M

IT Press, 1996.

48 Naik, G

autam. ``B

ack to Darw

in: In sunlight and cells, science seeks answers to high-tech

puzzles.'' The W

all S

treet Journ

al, 16 de enero de 1996, p. A

1.

49 Obayashi, S

higeru, Daisuke S

asaki, Yukihiro T

akeguchi, y Naoki H

irose. ``Multiobjective

evolutionary computation for supersonic w

ing-shape optimization.'' IE

EE T

ransa

ctions o

n

Evo

lutio

nary C

om

puta

tion, vol.4, no.2, p.182-187 (julio de 2000).

50 Petzinger, T

homas. ``A

t Deere they know

a mad scientist m

ay be a firm's biggest asset.'' T

he W

all

Street Jo

urn

al, 14 de julio de 1995, p.B

1. Ver tam

bién: ``Evolving business, w

ith a Santa F

e Institute twist.'' S

FI B

ulletin, invierno de 1998.

Disponible en línea.

51 Porto, V

incent, David F

ogel y Law

rence Fogel. ``A

lternative neural network training m

ethods.'' IE

EE E

xpert, vol.10, no.3, p.16-22 (junio de 1995).

52 Rao, S

rikumar. ``E

volution at warp speed.'' F

orb

es, vol.161, no.1, p.82-83 (12 de enero de 1998).

53 Rizki, M

ateen, Michael Z

muda y L

ouis Tam

burino. ``Evolving pattern recognition system

s.''

Página 52 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

IEEE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.6, no.6, p.594-609 (diciem

bre de 2002).

54 Robin, F

ranck, Andrea O

rzati, Esteban M

oreno, Otte H

oman, y W

erner Bachtold. ``S

imulation

and evolutionary optimization of electron-beam

lithography with genetic and sim

plex-downhill

algorithms.'' IE

EE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.7, no.1, p.69-82 (febrero de

2003).

55 Sagan, C

arl. Bro

ca's B

rain

: Reflectio

ns o

n th

e Rom

ance o

f Scien

ce. Ballantine, 1979.

56 Sam

bridge, Malcolm

y Kerry G

allagher. ``Earthquake hypocenter location using genetic

algorithms.'' B

ulletin

of th

e Seism

olo

gica

l Society o

f Am

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

57 Sasaki, D

aisuke, Masashi M

orikawa, S

higeru Obayashi y K

azuhiro Nakahashi. ``A

erodynamic

shape optimization of supersonic w

ings by adaptive range multiobjective genetic algorithm

s.'' En

Evo

lutio

nary M

ulti-C

riterion O

ptim

izatio

n: F

irst Intern

atio

nal C

onferen

ce, EM

O 2

001, Z

urich

, Switzerla

nd, M

arch

2001: P

roceed

ings, K

. Deb, L

. Theile, C

. Coello, D

. Corne y E

. Zitler (eds).

Notas de la confenrencia en C

om

puter S

cience, vol.1993, p.639-652. S

pringer-Verlag, 2001.

58 Sato, S

., K. O

tori, A. T

akizawa, H

. Sakai, Y

. Ando y H

. Kaw

amura. ``A

pplying genetic algorithm

s to the optimum

design of a concert hall.'' Journ

al o

f Sound a

nd V

ibra

tion, vol.258,

no.3, p. 517-526 (2002).

59 Schechter, B

ruce. ``Putting a D

arwinian spin on the diesel engine.'' T

he N

ew Y

ork T

imes, 19 de

septiembre de 2000, p. F

3. Ver tam

bién: Patch, K

imberly. ``A

lgorithm evolves m

ore efficient engine.'' Tech

nolo

gy R

esearch

New

s, junio/julio de 2000. Disponible en línea.

60 Srinivas, N

. y Kalyanm

oy Deb. ``M

ultiobjective optimization using nondom

inated sorting in genetic algorithm

s.'' Evo

lutio

nary C

om

puta

tion, vol.2, no.3, p.221-248 (otoño de 1994).

61 Soule, T

errence y Amy B

all. ``A genetic algorithm

with m

ultiple reading frames.'' E

n GEC

CO

-2001: P

roceed

ings o

f the G

enetic a

nd E

volu

tionary C

om

puta

tion C

onferen

ce, Lee S

pector y Eric

Goodm

an (eds). Morgan K

aufmann, 2001. D

isponible en línea.

62 Tang, K

.S., K

.F. M

an, S. K

wong y Q

. He. ``G

enetic algorithms and their applications.'' IE

EE

Sig

nal P

rocessin

g M

agazin

e, vol.13, no.6, p.22-37 (noviembre de 1996).

63 W

eismann, D

irk, Ulrich H

ammel, y T

homas B

äck. ``Robust design of m

ultilayer optical coatings by m

eans of evolutionary algorithms.'' IE

EE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.2,

no.4, p.162-167 (noviembre de 1998).

64 W

illiams, E

dwin, W

illiam C

rossley y Thom

as Lang. ``A

verage and maxim

um revisit tim

e trade studies for satellite constellations using a m

ultiobjective genetic algorithm.'' Jo

urn

al o

f the

Astro

nautica

l Scien

ces, vol.49, no.3, p.385-400 (julio-septiembre de 2001).

Ver tam

bién: ``Selecting better orbits for satellite constellations.'' S

paceflight Now

, 18 de octubre de 2001. D

isponible en línea.

Página 53 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/

``Darw

inian selection of satellite orbits for military use.'' S

pace.com, 16 de octubre de 2001.

Disponible en línea.

65 Zitzler, E

ckart y Lothar T

hiele. ``Multiobjective evolutionary algorithm

s: a comparative case

study and the Strength P

areto approach.'' IEEE T

ransa

ctions o

n E

volu

tionary C

om

puta

tion, vol.3,

no.4, p.257-271 (noviembre de 1999).

About this document ...

Algoritm

os genético

s y computación evolutiva

This docum

ent was generated using the L

aTeX

2HTML translator V

ersion 2002-2-1 (1.70)

Copyright ©

1993, 1994, 1995, 1996, Nikos D

rakos, Com

puter Based L

earning Unit, U

niversity of Leeds.

Copyright ©

1997, 1998, 1999, Ross M

oore, Mathem

atics Departm

ent, Macquarie U

niversity, Sydney.

The com

mand line argum

ents were:

latex2html -

split 0 -local_icons -up_url http://the-geek.org/docs algen.tex

Traducción realizada por G

abriel Rodríguez A

lberich. El docum

ento original se encuentra en la página web de T

alk.Origins.

Notas al pie

... 1

En inglés ``churn'', térm

ino de difícil traducción.

G

abriel R

odríg

uez A

lberich

2004-1

0-2

2

Página 54 de 54

Algoritm

os genéticos y computación evolutiva

07-11-2005http://the-geek.org/docs/algen/