INTELIGENCIA ARTIFICIAL II

ALGORITMOS
GENÉTICOS
2006-2007

Adrián Juan Verdejo

2
INDICE
1. Introducción ………………………………………………………………………5
2. Definición de algoritmo genético………………………………………...……8
3. Transformación de conceptos de evolución biológica a algoritmos ge-
néticos
3.1 Acercamiento teórico a los conceptos biológicos básicos……………..…....... 11
3.2 Extrapolación de los conceptos biológicos a los AG………………….............. 12
4. Operadores Genéticos más usuales……………………………………...… 13
4.1 Mutación ………………….....……….....……….....……….....……….....……............ 13
4.2 Reproducción ………………….....……….....……….....………........……….............. 14
4.3 Crossover …………………...……….....……….....……….....……….....……............ 15
5. Algoritmo Genético Simple………………………………………………...… 16
5.1 Pseudocódigo……………........……….....……….....……….....……….....………....... 16
5.2 Codificación del problema……………..............……….....……….....………........... 16
5.3 Ejemplo…………….……….....……….....……….....……….....……….....…............... 18
6. Algoritmo Genético Paralelo ……………...……………………………...… 20
6.1 Modelos de Islas……………....……….....……….....……….....……….................... 21
6.1.1 Algoritmos maestro-esclavo
6.1.2 Algoritmos de grano fino
6.1.3 Algoritmos de grano grueso
6.1.4 Algoritmos híbridos
6.2 Influencia de las migraciones en un algoritmo paralelo………………............ 25
6.3 Influencia de la topología de comunicación en un algoritmo paralelo........... 26
7. Aplicaciones de los algoritmos genéticos ………………………….....… 27
8. Aplicación Informática basada en algoritmos genéticos…….….....… 28
9. Bibliografía …….….....……….….....……….….....……….…...…….….....… 31

3
4
1. Introducción
El algoritmo genético es una técnica de búsqueda basada en la teoría de la
evolución de Darwin, que ha cobrado tremenda popularidad alrededor del mundo
durante los últimos años.

Fue en las décadas de 1950 y 1960 cuando varios científicos, de modo indepen-
diente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de que se
podrían emplear como herramienta en problemas de optimización en ingeniería. La idea
era evolucionar una población de candidatos a ser solución de un problema conocido,
utilizando operadores inspirados en la selección natural y la variación genética natural.

Con esta idea nace en el año 1993 la computación evolutiva, que retoma con-
ceptos de la evolución y la genética para resolver principalmente problemas de optimi-
zación. Esta rama de la inteligencia artificial tiene sus raíces en tres desarrollos relacio-
nados pero independientes entre sí:
- Algoritmos genéticos
- Programación evolutiva
- Estrategias Evolutivas
De estas tres áreas parten los caminos hacia todos los campos de investigación
inspirados en nuestros conocimientos sobre Evolución.

Las estrategias evolutivas son métodos computacionales que trabajan con una
población de individuos que pertenecen al dominio de los números reales, que mediante
los procesos de mutación y de recombinación evolucionan para alcanzar el óptimo de la
función objetivo. Entre 1965 y 1973 Rechenberg las introdujo como método para opti-
mizar parámetros reales para ciertos dispositivos. La misma idea fue desarrollada poco
después (75-77) por Schwefel. El campo de las estrategias evolutivas ha permanecido
como un área de investigación activa, cuyo desarrollo se produce, en su mayor parte, de
modo independiente al de los algoritmos genéticos (aunque recientemente se ha visto
como las dos comunidades han comenzado ha colaborar).

La programación evolutiva (PE) es prácticamente una variación de los algorit-

mos genéticos, donde lo que cambia es la representación de los individuos. En el caso
de la PE los individuos son ternas (tripletas) cuyos valores representan estados de un
autómata finito. Cada terna está formada por el valor del estado actual, un símbolo del
alfabeto utilizado y el valor del nuevo estado.
Estos valores se utilizan como en un autómata finito, teniendo el valor del estado
actual en el que nos encontramos, tomamos el valor del símbolo actual y si es el símbo-
lo de nuestra terna, nos debemos mover al nuevo estado. Además las funciones de se-
lección, cruce (crossover) y mutación deben variar para adaptarse y funcionar con una
población de individuos de este tipo.
Fogel, Owens y Walsh fueron los creadores en el 1966 de la programación evo-
lutiva, una técnica en la cual las candidatas a soluciones a tareas determinadas, eran
representadas por máquinas de estados finitos, cuyos diagramas de estados de transición
se evolucionaban mediante mutación aleatoria, seleccionándose el que mejor aproxima-
ra.

5
 Pasamos ahora a hablar de los algoritmos genéticos. La primera mención del
término, y la primera publicación sobre una aplicación del mismo, se deben a Bagley
en 1967. Este diseñó algoritmos genéticos para buscar conjuntos de parámetros en fun-
ciones de evaluación de juegos, y los comparó con los algoritmos de correlación, proce-
dimientos de aprendizaje modelizados después de los algoritmos de pesos variantes de
ese periodo. Sin embargo el que es considerado como el creador de los algoritmos gené-
ticos es John Holland, que los desarrolló, junto a sus alumnos y colegas, durante las
décadas de 1960 y 1970.
En contraste con las estrategias evolutivas y la programación evolutiva, el pro-
pósito original de Holland no era diseñar algoritmos para resolver problemas concretos,
sino estudiar, de un modo formal, el fenómeno de la adaptación tal y como ocurre en la
naturaleza, y desarrollar vías de extrapolar esos mecanismos de adaptación natural a los
sistemas computacionales. El libro que Holland escribió en 1975 Adaptación en siste-
mas naturales y artificiales presentaba el algoritmo genético como una abstracción de la
evolución biológica, y proporcionaba el entramado teórico para la adaptación bajo el
algoritmo genético. El algoritmo genético de Holland era un método para desplazarse,
de una población de cromosomas (bits) a una nueva población, utilizando un sistema
similar a la selección natural junto con los operadores de cruces, mutaciones e inversión
inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes
(bits), y cada uno de ellos es una muestra de un alelo particular (0 o 1).
Holland adapta los operadores de selección, cruces, mutaciones e inversión a su
algoritmo:
- Selección: este operador escoge entre los cromosomas de la población aque-
llos con capacidad de reproducción, y entre estos, los que sean más compati-
bles, producirán más descendencia que el resto.
- Cruce: extrae partes de dos cromosomas, imitando la combinación biológica
de dos cromosomas aislados (gametos).
- Mutación: se encarga de cambiar, de modo aleatorio, los valores del alelo en
algunas localizaciones del cromosoma.
o Inversión: invierte el orden de una sección contigua del cromosoma,
recolocando por tanto el orden en el que se almacenan los genes.
La mayor innovación de Holland fue la de introducir un algoritmo basado en po-
blaciones con cruces, mutaciones e inversiones. Es más, Holland fue el primero en in-
tentar colocar la computación evolutiva sobre una base teórica firme. Hasta hace poco,
esta base teórica, fundamentada en la noción de esquemas, fue la estructura sobre la que
se edificaron la mayoría de los trabajos teóricos sobre algoritmos genéticos en las déca-
das siguientes.

Además de los investigadores de los que hemos hablado muchos otros investiga-
dores desarrollaron su trabajo en los algoritmos para la optimización y el aprendizaje
inspirados en la evolución. Cabe resaltar nombres como los de Box (1957), Friedman
(1959), Bledsoe (1961), Bremermann (1962), y Reed, Toombs y Baricelli (1967). Sin
embargo, su trabajo no ha tenido, ni con mucho, la atención que han recibido las estra-
tegias evolutivas, programación evolutiva, y los algoritmos genéticos. Hay que recordar
además a los biólogos evolucionistas que han utilizado el ordenador para simular la evo-
lución para realizar experimentos controlados (Baricelli (1957-1962), Fraser 1957, Mar-
tin y Coreman 1960). Pero habría que esperar hasta que la computación electrónica se
desarrollara, para poder apreciar la consolidación definitiva de la computación evoluti-
va.

6
 En estos últimos años se ha generado una amplia interacción entre los investiga-
dores de varios métodos de computación evolutiva, rompiéndose las fronteras entre al-
goritmos genéticos, estrategias evolutivas y programación evolutiva. Como consecuen-
cia, en la actualidad, el término “algoritmo genético” se utiliza para designar un concep-
to mucho más amplio del que concibió Holland.

7
2. Definición de algoritmo genético
Los objetivos que perseguían John Holland y sus colegas de la Universidad de
Michigan cuando concibieron los algoritmos genéticos, eran dos: primero abstraer y
explicar rigurosamente el proceso adaptativo de los sistemas naturales; segundo diseñar
sistemas artificiales que retuvieran los mecanismos más importantes de los sistemas
naturales. En este sentido, podemos dar una definición de los algoritmos genéticos:

Algoritmos de búsqueda basados en los mecanismos de selección

natural y genética natural. Combinan la supervivencia de los más
compatibles entre las estructuras de cadenas, con una estructura
de información ya aleatorizada, intercambiada para construir un
algoritmo de búsqueda con algunas de las capacidades de innova-
ción de la búsqueda humana.

Básicamente, el Algoritmo Genético funciona como sigue: en cada generación,

se crea un conjunto nuevo de “criaturas artificiales” (cadenas) utilizando bits y partes
más adecuadas del progenitor. Esto involucra un proceso aleatorio que no es, en absolu-
to, simple. La novedad que introducen los Algoritmos Genéticos es que explotan efi-
cientemente la información histórica para especular sobre nuevos puntos de búsqueda,
esperando un funcionamiento mejorado.

El tema central en las investigaciones sobre algoritmos genéticos, ha sido la ro-

bustez, el equilibrio necesario entre la eficiencia y la eficacia suficiente para la supervi-
vencia en entornos diferentes. Las implicaciones que tiene la robustez en los sistemas
artificiales son variadas. Si se puede conseguir que un sistema artificial sea más robusto,
se podrán reducir, e incluso eliminar, los costes por rediseños. Y si se es capaz de lograr
niveles altos de adaptación, los sistemas podrán desarrollar sus funciones mejor y du-
rante más tiempo. Sin embargo, ante la robustez, eficiencia y flexibilidad de los siste-
mas biológicos, sólo podemos sentarnos a contemplar, y maravillarnos; mentiríamos si
dijéramos que somos capaces de igualarlos.

Podríamos plantearnos la pregunta de porque deberíamos basarnos en nuestros

conocimientos sobre la evolución biológica. La respuesta la encontramos si observamos
una constante que se repite en muchos problemas: la búsqueda de soluciones entre una
cantidad ingente de candidatos. Veámoslo con un ejemplo, el cálculo de un conjunto de
reglas o ecuaciones capaz de regir las subidas y bajadas de un mercado financiero. El
modo de llegar a la mejor solución en estas situaciones, pasa por ser capaz de obtener
rendimiento de un uso eficaz del paralelismo, que permita explorar diferentes posibili-
dades de modo simultáneo. Para ello, se precisa, tanto paralelismo computacional (con-
tar con varios procesadores computando al mismo tiempo), como una estrategia adecua-
da de búsqueda.
Otra buena razón para adoptar los algoritmos genéticos pasa por los problemas
computacionales, estos suelen precisar de un programa adaptativo, capaz de comportar-
se bien ante cambios en el entorno. Además, la mayoría de estos problemas tienen solu-
ciones complejas, muy difíciles de programar a mano. La computación evolutiva puede
ser la respuesta, mediante la selección natural, con variaciones debidas a cruces y/o mu-
taciones. Su objetivo es el diseño de soluciones de alta calidad para problemas de eleva-
do grado de complejidad, y la habilidad de adaptar esas soluciones de cara a cambios en
el entorno.

8
 La evolución, tal y como la conocemos, es básicamente un método de búsqueda
entre un número enorme de posibles soluciones. En biología las posibilidades están
formadas por un conjunto de secuencias genéticas posibles, y las soluciones deseadas,
por organismos capaces de sobrevivir y reproducirse en sus entornos. La evolución pue-
de verse, asimismo, como un modo de diseñar soluciones a problemas complejos, con la
capacidad de innovar. Estos son los motivos de que los mecanismos evolutivos sean una
fuente de inspiración para los algoritmos de búsqueda. Por supuesto, el buen funciona-
miento de un organismo biológico depende de muchos criterios, que además varían a
medida que el organismo evoluciona, de modo que la evolución está “buscando” conti-
nuamente entre un conjunto cambiante de posibilidades. Por ello, podemos considerarla
como un método de búsqueda masivamente paralelo, ya que evalúa y cambia millones
de especies en paralelo.
Características de los algoritmos genéticos
o Son algoritmos estocásticos. Dos ejecuciones distintas pueden dar dos solucio-
nes distintas.
o Son algoritmos de búsqueda múltiple, de los que se obtiene como respuesta va-
rias soluciones
o Son los algoritmos que hacen una barrida mayor al subespacio de posibles solu-
ciones válidas. De hecho, se considera que, de todos los algoritmos de optimiza-
ción estocásticos, los algoritmos genéticos son de los más exploratorios disponi-
bles.
o A diferencia de otros algoritmos, cuya convergencia y resultado final son fuer-
temente dependientes de la posición inicial, en los algoritmos genéticos (salvo
poblaciones iniciales realmente degeneradas, en los que el operador de mutación
va a tener mucho trabajo) la convergencia del algoritmo es poco sensible a la
población inicial si esta se escoge de forma aleatoria y es lo suficientemente
grande.
o Por su grado de penetración casi nulo, la curva de convergencia asociada al algo-
ritmo presenta una convergencia excepcionalmente rápida al principio, que casi
enseguida se bloquea.
o Es una búsqueda paramétricamente robusta. Eso quiere decir que hemos de es-
coger realmente mal los parámetros del algoritmo para que no converga. Con ta-
sas razonables, va a converger (mejor o peor) en una solución razonablemente
buena si la representación es la adecuada.
o Por último, los algoritmos genéticos son intrínsecamente paralelos. Esto signifi-
ca que, independientemente de que lo hayamos implementado de forma paralela
o no, buscan en distintos puntos del espacio de soluciones de forma paralela. Ese
paralelismo intrínseco permite que sean fácilmente paralelizables, es decir, que
sea fácil modificar el código para que se ejecute simultáneamente en varios pro-
cesadores.

Ventajas y Desventajas respecto a otras técnicas de búsqueda

o No necesitan conocimientos específicos sobre el problema que intentan resolver.
o Operan de forma simultánea con varias soluciones, en vez de trabajar de forma
secuencial como las técnicas tradicionales.
o Cuando se usan para problemas de optimización (maximizar una función objeti-
vo) resultan menos afectados por los máximos locales (falsas soluciones) que las
técnicas tradicionales.

9
o Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en
paralelo.
o Usan operadores probabilísticos, en vez de los típicos operadores determinísti-
cos de las otras técnicas.
o Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en
cierta medida de los parámetros que se utilicen: tamaño de la población, número
de generaciones, etc.
o Pueden converger prematuramente

10
3. Transformación de conceptos de evolución biológica
a algoritmos genéticos
3.1 Acercamiento teórico a los conceptos biológicos básicos:

Cada individuo de cada una de las especies del planeta posee ciertas característi-
cas que lo identifican. Dichas características, que suelen ser externas (como el color de
ojos) aunque también pueden ser internas (como el grupo sanguíneo), forman el fenoti-
po de un individuo que es el resultado de la interacción del medio ambiente en que se
desarrolla y la herencia que recibe de sus ancestros. Dicho fenotipo está determinado
por las proteínas que produce y está definido en la información genética de cada una de
las células del individuo. A su vez, la información acerca de las proteínas que se produ-
cirán está contenida en los cromosomas. En cada célula existen dos juegos de cromo-
somas que definen las mismas características. Un cromosoma es una larga molécula de
ADN formada por proteínas que definen los genes. El conjunto de todos los cromoso-
mas, es decir, de toda la información genética de un individuo se llama genoma y el
conjunto de genes contenidos en el genoma se denomina genotipo que es que determina
en buena medida el fenotipo del individuo. Existen unas células especiales, llamadas
gametos, que intervienen en la reproducción dividiéndose mediante un proceso denomi-
nado meiosis del siguiente modo:
1. Se duplica el número de cromosomas en la célula, esto es, se hace una copia de
cada cromosoma. Al final quedan dos juegos correspondientes al padre y dos a
la madre.
2. Se cruzan un juego de cromosomas del padre con uno de la madre, formándose
dos juegos de cromosomas híbridos. El resultado es un juego de cromosomas
puros del padre, un juego puro de la madre y dos juegos de cromosomas híbri-
dos.
3. Se divide la célula dos veces y al final del proceso quedan cuatro células haploi-
des (con un solo juego de cromosomas): una con cromosomas puros del padre,
una con cromosomas puros de la madre y dos con cromosomas híbridos.

El proceso de meiosis

Para el cruce de dos cromosomas se forman entre ellos puntos de ruptura y

unión de las cadenas de ADN que se denominan quiasmas y cortan el cromosoma en
segmentos llamados cromáticas y unen cromáticas complementarias de dos cromosomas
distintos. Para la réplica un cromosoma ya existente interviene una enzima denominada
ADN-polimerasa. La molécula de ADN tiene forma de doble hélice y dicha enzima se
encarga de abrir por la mitad la molécula y replicar el cromosoma. Ocasionalmente la
ADN-polimerasa comete un error que puede ser causado por radiaciones energéticas
externas o sustancias extrañas. La alteración de dicha molécula de ADN constituye una

11
mutación que puede manifestarse en el fenotipo y hacer al individuo diferente del resto
de sus congéneres. Por lo general las mutaciones son desfavorables e incluso letales
para el organismo mutante pero a veces pueden no serlo y conferir a dicho organismo
alguna ventaja que le permita sobrevivir más fácilmente en su medio. Dicha caracterís-
tica será transmitida a sus descendientes y se habrá producido un pequeño paso evoluti-
vo.

3.2 Extrapolación de los conceptos biológicos a los AG:

Veamos ahora la relación comúnmente establecida entre conceptos genéticos y

su traducción al mundo de los algoritmos genéticos.
Un cromosoma es una cadena que codifica la información de cada solución, que
proviene de la idea que hemos descrito antes de una larga molécula de ADN y por tanto
con información genética del descendiente. La cadena generalmente en binaria, aunque
se han usado también números reales o letras en vectores. No obstante la implementa-
ción utilizando la cadena binaria es más usada y fue la propuesta original de Holland.
Los cromosomas son los portadores de los genes que podemos ver como un bit,
o en otros casos como bloques cortos de bits adyacentes que codifican un elemento par-
ticular del candidato a solución.
Un alelo es una de las formas variantes de un gen en un locus (posición) o de un
marcador particular en un cromosoma. Diferentes alelos de un gen producen variaciones
en las características hereditarias tales como el color del cabello o el tipo de sangre. Por
ejemplo, el gen que regula el color de la semilla del guisante presenta dos alelos: uno
que determina color verde y otro que determina color amarillo. En este caso extrapola-
mos dos conceptos a los algoritmos genéticos: un alelo será el valor de una característi-
ca (podríamos decir que en una cadena de bits sería un 0 o un 1), el locus posición en la
palabra o cadena que simboliza el cromosoma.
Hablemos ahora de la traducción que podemos hacer de las operaciones que po-
demos aplicar sobre el material genético de las que ya hemos hablado en la introduc-
ción. El cruce o recombinación consiste, normalmente, como en su espejo biológico, en
un intercambio de material genético entre dos cromosomas de dos padres haploides. La
mutación es una permutación en un bit en un lugar aleatorio (o, en el caso de alfabetos
largos, remplazar el símbolo de un lugar escogido aleatoriamente con un símbolo nuevo
escogido también aleatoriamente). En cuanto a la selección, es el proceso en el que se
eligen n individuos de la población inicial P0 (m individuos, es decir m posibles solu-
ciones a un problema dado) que van a pasar a la siguiente generación, generalmente
n≤m. Estos n individuos forman la población intermedia Pi. De estos n individuos se
vuelven a seleccionar p individuos (p≤n), que serán utilizados como progenitores y uti-
lizarán la reproducción para generar descendientes. Reproducción se seleccionan n indi-
viduos de la población inicial P0 de m individuos.
El genotipo de un individuo en un algoritmo genético que emplea cadenas de
bits es, simplemente, la configuración de bits del cromosoma de ese individuo. La no-
ción de fenotipo, que es la expresión del genotipo, en el contexto tratado aparece como
otra cadena al igual que el genotipo o los cromosomas. Podemos decir que el genotipo
es la estructura y el fenotipo la estructura sometida al problema.

12
 4. Operadores Genéticos más usuales
4.1 Mutación:

En la evolución, una mutación es un suceso bastante poco común (sucede

aproximadamente una de cada mil replicaciones). En la mayoría de los casos las muta-
ciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie.
En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es decir, muy
baja).
Una vez establecida la frecuencia de mutación, por ejemplo, uno por mil, se ex-
amina cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus
padres (normalmente se hace de forma simultánea al crossover). Si un número generado
aleatoriamente está por debajo de esa probabilidad, se cambiará el bit (es decir, de 0 a 1
o de 1 a 0). Si no, se dejará como está. Dependiendo del número de individuos que haya
y del número de bits por individuo, puede resultar que las mutaciones sean extremada-
mente raras en una sola generación. No hace falta decir que no conviene abusar de la
mutación. Es cierto que es un mecanismo generador de diversidad, y por tanto la solu-
ción cuando un algoritmo genético está estancado, pero también es cierto que reduce el
algoritmo genético a una búsqueda aleatoria. Siempre es más conveniente usar otros
mecanismos de generación de diversidad, como aumentar el tamaño de la población, o
garantizar la aleatoriedad de la población inicial. Esta operación, junto con el crossover
y el método de selección de ruleta, constituyen un algoritmo genético simple, AGS, in-
troducido por Goldberg.
Si tenemos una población intermedia Pi de n+q individuos después de haber ge-
nerado la descendencia. Estos individuos se representan por cadenas binarias de longi-
tud L, razón por la que el número de bits totales de la población es de (n+q)* L. Cual-
quiera de estos bits puede sufrir el efecto del operador mutación con la misma probabi-
lidad. La probabilidad de que un bit de la población sea mutado es el parámetro conoci-
do como Probabilidad de Mutación (Pmut). Los valores típicos son 1%, 0,5%, 0,1%,
etc.
Un ejemplo de aplicación de este operador. Supongamos una población de 2 in-
dividuos w1 y w2 vistos anteriormente. Como su longitud es de 11 bits, el número total
de bits de esta población es de 22.
Bits totales =1001101110001101110000
Supongamos también que la probabilidad de mutación de cada bit es del 1%. Por
cada uno de los bits se genera un número aleatorio r. La probabilidad de mutación del
bit i expresada en tanto por uno es Pmut(i) = 0,01; si se cumple la condición ri<Pmut(i),
entonces el bit i será mutado, si no se mantendrá intacto.
Tras evolucionar la población inicial varias generaciones es posible que ningún
bit sea mutado o que algunos pocos lo hayan hecho, ya que este operador depende alea-
toriamente de ri. Si suponemos que r12 <Pmut(12), el bit a mutar será:
Bits totales =10011011100 0 1101110000
y por lo tanto la nueva población será:
Bits totales =10011011100 1 1101110000

13
 4.2 Reproducción:

Con este operador se seleccionan n individuos de la población inicial P0 de m

individuos. Para seleccionar qué individuos deben pasar a la población intermedia se
pueden utilizar diferentes mecanismos:
• Selección directa. De entre los m individuos de la población inicial, se escogen
los n individuos con mayor aptitud.
• Selección aleatoria. De entre los m individuos iniciales se eligen n individuos
de forma aleatoria.
• Selección estocástica. A cada individuo de la población inicial se le asigna una
probabilidad p de ser seleccionado en función de su aptitud respecto de la apti-
tud de toda la población. De esta forma para el individuo i ( wi ), cuya aptitud es
ui, la probabilidad de ser seleccionado es:

ui
Pi =
uT
donde uT es la suma de las aptitudes de todos los individuos de la población.

4.3 Crossover:

Consiste en el intercambio de material genético entre dos cromosomas (a veces

más, como el operador orgía propuesto por Eiben et al.). El crossover es el principal
operador genético, hasta el punto que se puede decir que no es un algoritmo genético si
no tiene crossover, y sin embargo puede serlo perfectamente sin mutación, según descu-
brió Holland. El teorema de los esquemas confía en él para hallar la mejor solución a un
problema.
Para aplicar el crossover, entrecruzamento o recombinación, se escogen aleato-
riamente dos miembros de la población. No pasa nada si se emparejan dos descencientes
de los mismos padres; ello garantiza la perpetuación de un individuo con buena puntua-
ción (y además, algo parecido ocurre en la realidad; es una práctica utilizada, por ejem-
plo, en la cría de ganado, llamada inbreeding, y destinada a potenciar ciertas caracterís-
ticas frente a otras). Sin embargo, si esto sucede demasiado a menudo, puede crear pro-
blemas: toda la población puede aparecer dominada por los descendientes de algún gen,
que además puede tener caracteres no deseados. Esto se suele denominar en otros méto-
dos de optimización atranque en un mínimo local, y es uno de los principales problemas
con los que se enfrentan los que aplican algoritmos genéticos.
En cuanto al teorema de los esquemas, se basa en la noción de bloques de cons-
trucción. Una buena solución a un problema está constituida por unos buenos bloques,
igual que una buena máquina está hecha por buenas piezas. El crossover es el encargado
de mezclar bloques buenos que se encuentren en los diversos progenitores, y que serán
los que den a los mismos una buena puntuación. La presión selectiva se encarga de que
sólo los buenos bloques se perpetúen, y poco a poco vayan formando una buena solu-
ción. El teorema de los esquemas viene a decir que la cantidad de buenos bloques se va
incrementando con el tiempo de ejecución de un algoritmo genético, y es el resultado
teórico más importante en algoritmos genéticos. El intercambio genético se puede llevar
a cabo de muchas formas, pero hay dos grupos principales:

14
• Crossover n-puntos: los dos cromosomas se cortan por n puntos, y el material-
genético situado entre ellos se intercambia. Lo más habitual es un crossover de
un punto o de dos puntos.

• Crossover uniforme: se genera un patrón aleatorio de 1s y 0s, y se intercam-

bian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrón.
O bien se genera un número aleatorio para cada bit, y si supera una determinada
probabilidad se intercambia ese bit entre los dos cromosomas.

• Crossover especializado: en algunos problemas, aplicar aleatoriamente el cros-

sover da lugar a cromosomas que codifican soluciones inválidas; en este caso
hay que aplicar el crossover de forma que genere siempre soluciones válidas. Un
ejemplo de estos son los operadores de crossover usados en el problema del via-
jante.

15
 5. Algoritmo Genético Simple

5.1 Pseudocódigo:

El Algoritmo Genético Simple, también denominado Canónico que explicare-

mos a continuación a modo de pseudódigo.

BEGIN
Generar una población inicial
Computar la función de evaluación de cada individuo
WHILE NOT Terminado DO
BEGIN /* Producir nueva generación */
FOR (Tamaño población)/2 DO
BEGIN /*Ciclo reproductivo*/
Seleccionar dos individuos de la generación an-
terior, para el cruce (probabilidad de selec-
ción proporcional a la función de e evaluación
del individuo)
Cruzar con cierta probabilidad los dos indivi-
duos obteniendo dos descendientes
Mutar los dos descendientes con cierta probabi-
lidad
Computar la función de evaluación de los dos
descendientes mutados
Insertar los dos descendientes mutados en la
nueva generación
END
IF la población ha convergido THEN
Terminado := TRUE
END
END

Se necesita una codificación o representación del problema, que resulte adecua-

da al mismo. Además se requiere una función de ajuste ó adaptación al problema, la
cual asigna un número real a cada posible solución codificada. Durante la ejecución del
algoritmo, los padres deben ser seleccionados para la reproducción, a continuación di-
chos padres seleccionados se cruzarán generando dos hijos, sobre cada uno de los cuales
actuará un operador de mutación. El resultado de la combinación de las anteriores fun-
ciones será un conjunto de individuos (posibles soluciones al problema), los cuales en la
evolución del Algoritmo Genético formarán parte de la siguiente población.

5.2 Codificación del problema:

Se supone que los individuos (posibles soluciones del problema), pueden repre-
sentarse como un conjunto de parámetros (que denominaremos genes), los cuales agru-
pados forman una ristra de valores (a menudo referida como cromosoma). Si bien el
alfabeto utilizado para representar los individuos no debe necesariamente estar consti-
tuido por el {0, l}, buena parte de la teoría en la que se fundamentan los algoritmos ge-
néticos utiliza dicho alfabeto.
Durante la fase reproductiva se seleccionan los individuos de la población para
cruzarse y producir descendientes, que constituirán, una vez mutados, la siguiente gene-
ración de individuos. La selección de padres se efectúa al azar usando un procedimiento

16
que favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna
una probabilidad de ser seleccionado que es proporcional a su función de adaptación.
Este procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema,
los individuos bien adaptados se escogerán probablemente varias veces por generación,
mientras que, los pobremente adaptados al problema, no se escogerán más que de vez en
cuando.
Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando ha-
bitualmente los operadores de cruce y mutación. Estos y otros operadores están explica-
dos en la sección de operadores genéticos.
Para criterios prácticos, es muy útil la definición de convergencia introducida en
este campo por De Jong en su tesis doctoral en relación con los algoritmos genéticos
simples. Si el algoritmo ha sido correctamente implementado, la población evolucionará
a lo largo de las generaciones sucesivas de tal manera que la adaptación media extendi-
da a todos los individuos de la población, así como la adaptación del mejor individuo se
irán incrementando hacia el óptimo global. El concepto de convergencia está relaciona-
do con la progresión hacia la uniformidad: un gen ha convergido cuando al menos el 95
% de los individuos de la población comparten el mismo valor para dicho gen. Se dice
que la población converge cuando todos los genes han convergido. Se puede generalizar
dicha definición al caso en que al menos un pequeño porcentaje de los individuos de la
población hayan convergido.
Resumiendo, se puede explicar el proceso de un algoritmo genético simple de un
modo bastante gráfico (vemos la probabilidad de un suceso como el acto de lanzar una
modela al aire) como sigue:
1. Decidir cómo codificar el dominio del problema.
2. Generar un conjunto aleatorio (población inicial) de N posibles soluciones codi-
ficadas al problema. A esta se le llamará población actual.
3. Calificar cada posible solución (individuo) de la población actual.
4. Seleccionar dos individuos de la población actual con una probabilidad propor-
cional a su calificación.
5. Lanzar una moneda al aire (supongamos que la probabilidad de cara es pc).
6. Si cayó cara mezclar los códigos de los dos individuos seleccionados para for-
mar dos híbridos, a los que llamaremos nuevos individuos.
7. Si cayó cruz llamamos a los individuos seleccionados nuevos individuos.
8. Por cada bit de cada nuevo individuo lanzar otra moneda al aire (supongamos
que en este caso cae cara con probabilidad pm ).
9. Si cae cara cambiar el bit en turno por su complemento.
10. Si cae cruz, el bit permanece inalterado.
11. Incluir a los dos nuevos individuos en una nueva población.
12. Si la nueva población tiene ya N individuos, llamarla población actural y regre-
sar al paso 3, a menos que se cumpla alguna condición de terminación.
13. Si no, regresar al paso 4.

17
 5.3 Ejemplo:

Como ilustración de los diferentes componentes del algoritmo genético simple,

supongamos el problema adaptado de Goldberg de encontrar el máximo de la función
f(x) = x² sobre los enteros {1,2,...,32}. Para lograr dicho óptimo, bastaría actuar por
búsqueda exhaustiva, dada la baja cardinalidad del espacio de búsqueda. Se trata por
tanto de un mero ejemplo con el que pretendemos ilustrar el comportamiento del algo-
ritmo anteriormente descrito. Consultando el pseudocódigo descrito anteriormente, ve-
mos que el primer paso a efectuar consiste en determinar el tamaño de la población ini-
cial, para a continuación obtener dicha población al azar y computar la función de eva-
luación de cada uno de sus individuos.
Suponiendo que el alfabeto utilizado para codificar los individuos esté constitui-
do por {0, 1}, necesitaremos ristras de longitud 5 para representar los 32 puntos del es-
pacio de búsqueda. En la tabla a continuación, hemos representado los 4 individuos que
constituyen la población inicial, junto con su función de adaptación al problema, así
como la probabilidad de que cada uno de dichos individuos sea seleccionado según el
modelo de ruleta sesgada para emparejarse (la probabilidad de que un individuo sea
seleccionado es el cociente entre su función adaptación y la suma de las funciones de
adaptación de sus competidores).

Población inicial de la simulación efectuada a mano correspondiente al AG simple

El siguiente paso consiste en la selección de 2 parejas de individuos. Para ello es
suficiente, con obtener 4 números reales provenientes de una distribución de probabili-
dad uniforme en el intervalo (0, 1), y compararlos con la última columna de la tabla an-
terior. Así por ejemplo, supongamos que dichos 4 números hayan sido: 0.58; 0.84; 0.11
y 0.43. Esto significa que los individuos seleccionados para el cruce han sido: el indivi-
duo 2 junto con el individuo 4, así como el individuo 1 junto con el individuo 2 (para
ello basta fijarnos en que un individuo i se elige cuando el número obtenido al azar está
comprendido entre la probabilidad de selección acumulada del individuo i-1 y la proba-
bilidad de selección acumulada del individuo i).
Para seguir con el algoritmo genético simple, necesitamos determinar la probabi-
lidad de cruce (p). Supongamos que se fije en p = 0.8. Valiéndonos al igual que antes de
números provenientes de la distribución uniforme (dos en este caso), determinaremos si
los emparejamientos anteriores se llevan a cabo.

18
 Población en el tiempo 3, proveniente de efectuar los operadores de
cruce y mutación sobre los individuos de la tabla anterior.

Admitamos, por ejemplo, que los dos números extraídos sean menores que 0.8,
decidiéndose por tanto efectuar el cruce entre las dos parejas. Para ello escogeremos un
número al azar entre 1 y L (siendo L la longitud de la ristra utilizada para representar el
individuo). Notése que la restricción impuesta al escoger el número entre 1 y L, se reali-
za con la finalidad de que los descendientes no coincidan con los padres. Supongamos,
tal y como se indica en la segunda tabla, que los puntos de cruce resulten ser 2 y 3. De
esta manera obtendríamos los 4 descendientes descritos en la tercera columna de dicha
tabla. A continuación (siguiendo el pseudocódigo descrito) mutaríamos con una proba-
bilidad p, cercana a cero, cada uno de los bits de las cuatro ristras de individuos. En este
caso suponemos que el único bit mutado corresponde al primer gen del tercer individuo.
En las dos últimas columnas se pueden consultar los valores de los individuos, así como
las funciones de adaptación correspondientes. Como puede observarse, tanto el mejor
individuo como la función de adaptación media han mejorado sustancialmente al com-
pararlos con los resultados de la tabla inicial.

19
6. Algoritmo Genético Paralelo

Un programa es paralelo si en cualquier momento de su ejecución puede ejecutar

más de un proceso. Para crear programas paralelos eficientes hay que poder crear, des-
truir y especificar procesos así como la interacción entre ellos. Básicamente existen tres
formas de paralelizar un programa:
- Paralelización de grano fino: la paralelización del programa se realiza a nivel de
instrucción. Cada procesador hace una parte de cada paso del algoritmo (selección,
cruce y mutación) sobre la población común.
- Paralelización de grano medio: los programas se paralelizan a nivel de bucle. Esta
paralelización se realiza habitualmente de una forma automática en los compilado-
res.
- Paralelización de grano grueso: se basan en la descomposición del dominio de datos
entre los procesadores, siendo cada uno de ellos el responsable de realizar los cálcu-
los sobre sus datos locales.
La computación paralela se ha convertido en una parte fundamental en todas las
áreas de cálculo científico, ya que permite la mejora del rendimiento simplemente con la
utilización de un mayor número de procesadores, memorias y la inclusión de elementos
de comunicación que permitan a los procesadores trabajar conjuntamente para resolver
un determinado problema.
Podemos decir que los algoritmos genéticos tienen una estructura que se adapta
perfectamente a la paralelización. De hecho la evolución natural es en si un proceso
paralelo ya que evoluciona utilizando varios individuos. Los principales métodos de
paralelización de AGs consisten en la división de la población en varias subpoblaciones.
El tamaño y distribución de la población entre los distintos procesadores será uno de los
factores fundamentales a la hora de paralelizar el algoritmo.
Existen varias formas de paralelizar un algoritmo genético. La primera y más in-
tuitiva es la global, que consiste básicamente en paralelizar la evaluación de los indivi-
duos manteniendo una población. Otra forma de paralelización global consiste en reali-
zar una ejecución de distintos AGs secuenciales simultáneamente (estas dos formas de
paralelización no cambian la estructura del algoritmo utilizado). El resto de aproxima-
ciones sí cambian la estructura del algoritmo y dividen la población en subpoblaciones
que evolucionan por separado e intercambian individuos cada cierto número de genera-
ciones. Si las poblaciones son pocas y grandes, tenemos la paralelización de grano grue-
so. Si el número de poblaciones es grande y con pocos individuos en cada población
tenemos la paralelización de grano fino. Por ultimo, existen algoritmos que mezclan
propiedades de estos dos últimos y que se denominan mixtos.
Además de conseguir tiempos de ejecución menores, al paralelizar un AG esta-
mos modificando el comportamiento algorítmico, y esto hace que podamos obtener
otras soluciones y experimentar con las distintas posibilidades de implementación y los
distintos factores que influyen en ella. Estas poblaciones van evolucionando por separa-
do para detenerse en un momento determinado e intercambiar los mejores individuos
entre ellas.

20
 Técnicamente hay 3 características importantes que influyen en la eficiencia de
un algoritmo genético paralelo:
• La topología que define la comunicación entre subpoblaciones.
• La proporción de intercambio: número de individuos a intercambiar.
• Los intervalos de migración: periodicidad con que se intercambian los
individuos.

6.1 Modelos de Islas:

En este apartado se introducirán tres maneras diferentes de explotar el paralelis-

mo de los Algoritmos Genéticos, por medio de los denominados modelos de islas. La
idea básica consiste en dividir la población total en varias subpoblaciones en cada una
de las cuales se lleva, a cabo un Algoritmo Genético. Cada cierto número de generacio-
nes, se efectúa un intercambio de información entre las subpoblaciones, proceso que se
denomina migración. La introducción de la migración hace que los modelos de islas
sean capaces de explotar las diferencias entre las diversas subpoblaciones, obteniéndose
de esta manera una fuente de diversidad genética. Cada subpopulación es una "isla",
definiéndose un procedimiento por medio del cual se mueve el material genético de una
“isla” a otra. La determinación de la tasa de migración, es un asunto de capital impor-
tancia, ya que de ella puede depender la convergencia prematura de la búsqueda.
Se pueden distinguir diferentes modelos de islas en función de la comunicación
entre las subpoblaciones.

6.1.1 Algoritmos maestro-esclavo

En los algoritmos maestro-esclavo o con comunicación en estrella, existe una

subpoblación que es seleccionada como maestra (aquella que tiene mejor media en el
valor de la función objetivo), siendo las demás consideradas como esclavas. Todas las
subpoblaciones esclavas mandan sus h1 mejores individuos (h1 > 1) a la subploblación
maestra la cual a su vez manda sus h2 mejores individuos (h2 >1) a cada una de las
subpoblaciones esclavas.

Comunicación en Estrella
Normalmente, la operación que se suele implementar en paralelo es la evalua-
ción de la adecuación de los individuos, porque suele ser la más compleja. Además, este
valor es independiente del resto de la población, por lo que su implementación es muy
sencilla.

21
 El intercambio de información entre los nodos es sencillo: el nodo maestro envía
el subconjunto de inviduos que corresponde a cada nodo, y estos le devuelven los valo-
res de adecuación para cada uno de ellos. La comunicación puede ser implementada de
dos maneras: síncrona o asíncrona. En la primera de ellas, el nodo maestro espera a re-
cibir los valores de adecuación de todos los individuos para generar la siguiente genera-
ción. En la segunda, el algoritmo no espera a que los nodos más lentos envíen sus valo-
res de fitness (función de capacidad, aptitud o potencial asigna una puntuación (la capa-
cidad) a cada cromosoma de la población actual, que depende de cómo resuelva ese
cromosoma el problema a tratar). De este modo conseguimos agilizar el proceso, pero el
comportamiento no es exactamente el mismo que el de un algoritmo genético secuen-
cial. La implementación síncrona, en cambio, sí mantiene este comportamiento.
Varios estudios han sido realizados para evaluar el rendimiento de este tipo de
algoritmos. Algunos resultados interesantes pueden verse, por ejemplo, en el que reali-
zaron Abramson, Mills y Perkins, que usando dos computadores de memoria comparti-
da observaron un incremento de prestaciones razonablemente alto en comparación con
los algoritmos genéticos tradicionales usando hasta 16 procesadores. A partir de ese
número, el comportamiento se degradaba, dato que justificaban por el aumento del coste
de las comunicaciones.

6.1.2 Algoritmos de grano fino

Los algoritmos de grano fino o de comunicación en red trabajan desde la pers-

pectiva de que no existe una jerarquía entre las subpoblaciones, mandando todas y cada
una de ellas sus h3 (h3 > 1) mejores individuos al resto de las subpoblaciones. Han sido
diseñados para ser implementados usando computadores masivamente paralelos. Ahora,
la población se encuentra dividida espacialmente entre los distintos procesadores e,
idealmente, cada procesador debería albergar un único individuo. El cruce y la selec-
ción de individuos se hará entre individuos que pertenezcan a un mismo vecindario,
formado por un conjunto de individuos adyacentes según la representación espacial an-
tes citada. Sin embargo, se permite el solapamiento entre vecindarios para propiciar la
interacción, aunque leve, entre todos los individuos de la población. Un esquema de esta
aproximación.

Comunicación en red
Se han llevado a cabo algunos estudios para determinar si el tamaño de los ve-
cindarios influía o no en la presión de selección de los individuos. Sarma y De Jong
encontraron que la relación entre el radio de los vecindarios y el radio de la población
completa influía en este aspecto, y cuantificaron el tiempo que tardaba en propagarse
una solución buena al resto de la población con diferentes tamaños para los vecindarios.
Otros estudios han intentado determinar qué tipo de representaciones espaciales
daban mejores resultados. Schwehm experimentó con varias representaciones: un anillo,

22
un toro, un cubo 16x8x8 y un hipercubo 4x4x4x4x4. El problema con el que trabajó fue
el particionamiento de grafos, y encontró que el algoritmo que usó la estructura de toro
convergió más rápidamente que el resto, aunque no da detalles sobre la calidad de las
soluciones encontradas.

6.1.3 Algoritmos de grano grueso

Las características más importantes de los algoritmos de grano grueso o de co-

municación en anillo son el uso de múltiples poblaciones y la migración de individuos
entre ellas. Dado que cada una de las poblaciones evoluciona independientemente, el
ratio de migración será muy importante de cara a obtener resultados satisfactorios. Cada
subpoblación envía sus h4 mejores individuos (h4 > 1), a una población vecina, efec-
tuándose la migración en un único sentido de flujo. Se puede observar una posible solu-
ción usando este tipo de algoritmos a continuación.

Comunicación en anillo

En 1985 Grosso realizó el que se puede considerar como el primer estudio de los
algoritmos genéticos paralelos con múltiples poblaciones. Algunos de sus resultados,
lejos de aclarar si el uso de este tipo de algoritmos es recomendable en sustitución de
los tradicionales algoritmos genéticos secuenciales, arrojan nuevas incógnitas. Por
ejemplo, observó que los individuos de las poblaciones, cuando estas están aisladas,
convergen más rápidamente hacia valores óptimos, pero que estos valores no son tan
buenos como los obtenidos con los algoritmos secuenciales. Con valores bajos en el
ratio de migraciones los cambios apenas son apreciables. Una vez alcanzado un deter-
minado ratio de migración, que dependerá del problema y de la topología empleada, las
soluciones encontradas por estos algoritmos igualan en calidad a las encontradas por el
algoritmo secuencial. Como este y otros estudios demuestran, el buen funcionamiento
de estos algoritmos depende en gran medida de varios factores, de entre los que desta-
can la frecuencia con la que se realicen las migraciones y la topología de comunicación
entre las subpoblaciones que se use.

6.1.4 Algoritmos híbridos

Este tipo de algoritmos son, quizás, los más complejos de los vistos hasta el
momento, dado que combinan dos de los algoritmos anteriores una estructura de dos
niveles. En el nivel superior suele haber siempre un algoritmo de grano grueso (multi-
población). En el nivel inferior se han probado los tres tipos de algoritmos vistos: maes-
tro-esclavo, de grano fino y de grano grueso. A esta estructuración en dos niveles se le

23
denomina jerarquía y, por eso, muchas veces a estos algoritmos se les denomina algo-
ritmos genéticos jerárquicos (del inglés Hierarchical Genetic Algorithms).
La primera posibilidad es combinar un algoritmo multipoblación en el nivel su-
perior con un algoritmo de grano fino en el nivel inferior.

Representación esquemática de un algoritmo híbrido de tipo multipoblación

en el nivel superior y de grano fino en el nivel inferior
Existen varias implementaciones de este tipo de algoritmos. Gruau usó un algo-
ritmo genético multipoblación cuyas poblaciones estaban conectadas en forma toroidal
de dos dimensiones. Cada una de las poblaciones fue organizada siguiendo una estructu-
ra de grano fino, en este caso una cuadrícula de dos dimensiones. Otros autores, como
Lin, Goodman y Punch, conectaron las poblaciones del nivel superior usando una topo-
logía de anillo, y conservaron la distribución en cuadrícula de dos dimensiones para el
nivel inferior. Compararon esta implementación con varios tipos de algoritmos genéti-
cos, para lo cual usaron un problema de planificación. Entre los algoritmos usados para
la comparativa se encuentran algunas implementaciones paralelas de las vistas ante-
riormente, así como algoritmos genéticos secuenciales. Los resultados que obtuvieron
con este algoritmo híbrido fueron mejores que los obtenidos por el resto de aproxima-
ciones.
Como segunda alternativa para implementar algoritmos híbridos se puede usar
un algoritmo multipoblación en el nivel superior y un algoritmo maestro-esclavo en
cada una de las poblaciones.

Representación esquemática de un algoritmo híbrido de tipo multipoblación

en el nivel superior y maestro-esclavo en el nivel inferior
Bianchini y Brown experimentaron con estos algoritmos, consiguiendo solucio-
nes de la misma calidad que las obtenidas con algoritmos paralelos tradicionales (multi-
población y maestroesclavo) en menos tiempo.
La tercera opción de hibridación es usar algoritmos multipoblación en ambos ni-
veles (superior e inferior). Usando una topología altamente conectada en el nivel infe-
rior y una frecuencia de migración elevada se consigue una mejor distribución de las
soluciones óptimas a través de las poblaciones. En el nivel superior se suele optar por

24
frecuencias de migraciones bajas, lo cual hace que la complejidad no crezca demasiado,
siendo aproximadamente igual a la de un algoritmo paralelo con multipoblaciones tradi-
cional.

Representación esquemática de un algoritmo híbrido de tipo

multipoblación tanto en el nivel superior como en el nivel inferior.

6.2 Influencia de las migraciones en un algoritmo paralelo

Hay que tener en cuenta varios factores en la migración de individuos entrepo-

blaciones. El primero de ellos es la frecuencia con la que estas se llevarán a cabo. La
mayor parte de las implementaciones existentes programan las migraciones a intervalos
fijos o, dicho de otra forma, de una forma síncrona. Por otro lado, se puede introducir
asincronía en la política de migraciones haciendo que estas sean efectuadas sólo cuando
se produzca un evento. En el estudio descrito en la tesis de Grosso, este programó las
migraciones para que fueran efectuadas únicamente cuando la población estuviera cerca
de converger. Braun hizo algo parecido, aunque en este caso las migraciones se realiza-
ban una vez la población había convergido completamente con el propósito de restaurar
la diversidad. Este es un aspecto muy importante, ya que una migración prematura de-
individuos puede entrañar serios problemas, ya que la calidad de los individuos envia-
dos podría no aportar ninguna mejora en el resto de poblaciones, con lo que estaríamos
desperdiciando valiosos y costosos recursos de red. Sin embargo, una migración muy
tardía puede afectar también negativamente y aumentar considerablemente el tiempo de
convergencia al óptimo global o, incluso, propiciar que esta no se produzca. Por tanto,
encontrar el momento adecuado para la migración de los individuos es un aspecto muy a
tener en cuenta a la hora de diseñar un algoritmo de este tipo.
Otro aspecto muy a tener en cuenta es qué individuo se envía en las migraciones.
Pettey, Leuze y Grefenstette proponen enviar el mejor individuo de cada población a
todas sus adyacentes. Los resultados experimentales que obtuvieron desvelaron que los
resultados así obtenidos eran de una calidad similar a los obtenidos por algoritmos gené-
ticos con una única población. Una aproximación diferente es la que desarrollaron Ma-
rin, Trelles-Salazar y Sandoval. Propusieron que cada subpoblación, transcurridas las
generaciones necesarias para realizar la migración, enviaran su mejor individuo a un
nodo maestro, que se encargaría de elegir a los mejores individuos entre todos los reci-
bidos y de reenviarlos de nuevo a todas las poblaciones. Con un número pequeño de
nodos (alrededor de seis) obtuvieron resultados que propiciaban speed-ups casi lineales
en los tiempos de ejecución.

25
 6.3 Influencia de la topología de comunicación en un algorit-
mo paralelo

Aunque muchas veces no se tenga demasiado en cuenta, este es un factor muy

importante a la hora de implementar un algoritmo genético paralelo, ya que determina la
velocidad con la que las buenas soluciones encontradas se propagan hacia el resto de
poblaciones. Si el grado de conectividad es alto o e diámetro de la red es pequeño (o
ambas cosas) las soluciones buenas se expandirán rápidamente a través de todas las po-
blaciones, favoreciendo así la evolución hacia el óptimo. En caso contrario, las pobla-
ciones estarán más aisladas las unas de las otras, por lo que evolucionarán mucho más
despacio, y llevará más tiempo la incorporación de los genes potencialmente buenos a
las nueva soluciones.
Por otro lado, es necesario tener en cuenta que la densidad de conexiones puede
influir negativamente en el algoritmo, ya que supone una sobrecarga importante en el
tráfico de la red. Por eso, es muy importante elegir una buena topología para obtener el
máximo rendimiento del algoritmo.
Por lo general, se suelen utilizar topologías estáticas, es decir, topologías prede-
finidas que no cambian según avanza la ejecución del algoritmo. Las más utilizadas
suelen ser las topologías de anillo y de hipercubo de cuatro dimensiones. Sin embargo,
algunas implementaciones proponen que las conexiones entre poblaciones no estén de-
finidas desde el principio, sino que se establezcan sobre la marcha cuando alguna pobla-
ción cumpla algún criterio, como la diversidad de la población o la distancia entre los
genotipos de las dos poblaciones. Esta medida de distancia se puede simplificar calcu-
lando únicamente la distancia entre los dos mejores individuos de ambas poblaciones.

26
7. Aplicaciones de los Algoritmos Genéticos

Optimización: Se trata de un campo especialmente abonado para el uso de los

Algoritmos Genéticos, por las características intrínsecas de estos problemas. No en vano
fueron la fuente de inspiración para los creadores estos algoritmos. Los Algoritmos Ge-
néticos se han utilizado en numerosas tareas de optimización, incluyendo la optimiza-
ción numérica, y los problemas de optimización combinatoria.
Programación automática: Los Algoritmos Genéticos se han empleado para
desarrollar programas para tareas específicas, y para diseñar otras estructuras computa-
cionales tales como el autómata celular, y las redes de clasificación.
Aprendizaje máquina: Los algoritmos genéticos se han utilizado también en
muchas de estas aplicaciones, tales como la predicción del tiempo o la estructura de una
proteína. Han servido asimismo para desarrollar determinados aspectos de sistemas par-
ticulares de aprendizaje, como pueda ser el de los pesos en una red neuronal, las reglas
para sistemas de clasificación de aprendizaje o sistemas de producción simbólica, y los
sensores para robots.
Economía: En este caso, se ha hecho uso de estos Algoritmos para modelizar
procesos de innovación, el desarrollo estrategias de puja, y la aparición de mercados
económicos.
Sistemas inmunes: A la hora de modelizar varios aspectos de los sistemas in-
munes naturales, incluyendo la mutación somática durante la vida de un individuo y el
descubrimiento de familias de genes múltiples en tiempo evolutivo, ha resultado útil el
empleo de esta técnica.
Ecología: En la modelización de fenómenos ecológicos tales como las carreras
de armamento biológico, la coevolución de parásito-huésped, la simbiosis, y el flujo de
recursos.
Genética de poblaciones: En el estudio de preguntas del tipo “¿Bajo qué con-
diciones será viable evolutivamente un gene para la recombinación?”
Evolución y aprendizaje: Los Algoritmos Genéticos se han utilizado en el es-
tudio de las relaciones entre el aprendizaje individual y la evolución de la especie.
Sistemas sociales: En el estudio de aspectos evolutivos de los sistemas sociales,
tales como la evolución del comportamiento social en colonias de insectos, y la evolu-
ción de la cooperación y la comunicación en sistemas multi-agentes. Aunque esta lista
no es, en modo alguno, exhaustiva, sí transmite la idea de la variedad de aplicaciones
que tienen los Algoritmos Genéticos. Gracias al éxito en estas y otras áreas, los Algo-
ritmos Genéticos han llegado a ser un campo puntero en la investigación actual.

27
8. Aplicación informática basada en Algoritmos Gené-
ticos
8.1 Descripción general

La aplicación que he elegido para estudiar una aplicación práctica de los algo-
ritmos genéticos es un applet que busca el extremo de una función dada utilizando di-
chos algoritmos. Podemos variar dicha función además de indicarle al programa si ha de
buscar bien el máximo o bien el mínimo. El applet se encontrón en una introducción a
algoritmos genéticos de la página del profesor Marek Obitko del Departamento de
Ciencias Computacionales e Ingeniería de la universidad de Praga
http://cs.felk.cvut.cz/~xobitko/ga/example3d.html.

Como vemos en la figura la aplicación dibuja la función que le indiquemos en el

cuadro de texto creado a tal efecto. Hecho esto al presionar Change la aplicación dibuja
la función en la gráfica de 3D y mediante el uso del ratón podemos variar la perspectiva
de la vista.

28
 El applet ofrece la posibilidad de variar el factor de recombinación y el de muta-
ción. El factor de recombinación lo podemos variar entre el 0% y 100% con una varia-
ción de una unidad porcentual. En cuanto al factor de mutación, este puede ser oscilado
entre 0% y el 20% con una variación mínima del 0.1%.
Una vez hayamos elegido los parámetros correctos de recombinación y de muta-
ción así como el mínimo y máximo de X e Y, podemos presionar Star para comenzar la
búsqueda del mínimo, pudiendo parar la ejecución en cualquier momento mediante Stop
para retomarla posteriormente con Continue. Si nos parece que la aplicación funciona a
demasiada velocidad con el botón Step podemos ir ejecutando paso a paso. Por último
con Reset se vuelve a iniciar la búsqueda tomando unos parámetros iniciales nuevos.
Durante la ejecución podemos ir variando los parámetros de mutación y crossover e ir
viendo como cambia la ejecución. También podemos variar el objetivo de la búsqueda
(máximo o mínimo).
A lo largo de la ejecución podemos ver donde buscamos la solución (líneas azu-
les) y la mejor solución actual (línea roja).

8.2 Prueba

Para la prueba he elegido la función tg(x² + y²) (TAN(x^2 + y^2)) y primero he

seleccionado un valor de mutación del 0.2% y como factor de recombinación el 50%.
Tomando los valores de X e Y entre -10 y 10.

29
 Vemos que así la solución permanece por algunos ciclos estancada en puntos
que no son la mejor solución pero con el tiempo la solución habitualmente mejora. No
obstante si aumentamos el factor de mutación (a un 1.5%) se evitan esos estancamientos
alcanzando una solución mejor en un período de tiempo inferior. Pues cuando la solu-
ción no mejora por el efecto de la recombinación se produce una mutación que varía la
descendencia.
Si aumentamos el factor de recombinación (80%) pero dejando el valor para la
mutación al 0.2% vemos como la solución se alcanza antes que en la primera ejecución
pero por ser la mutación baja en algunas ejecuciones tarda más que en otras.

30
8. Bibliografía
Los links que pertenecen a la bibliografía han sido comprobados el (20/05/07)
Tutorial de Informática Evolutiva
http://geneura.ugr.es/~jmerelo/ie/index.html
Informática evolutiva: Algoritmos genéticos Juan Julián Merelo Guervós
http://geneura.ugr.es/~jmerelo/ie/ags.htm
Introducción a los Algoritmos Genéticos Carlos A. Coello Coello
http://www.redcientifica.com/doc/doc199904260011.html
Algoritmos genéticos y computación evolutiva Adam Marczyk 2004
http://the-geek.org/docs/algen/
Búsqueda, Optimización y Aprendizaje (algoritmos genéticos) Eduardo Morales
http://ccc.inaoep.mx/~emorales/Cursos/Busqueda04/node98.html
Algoritmos Genéticos
http://eddyalfaro.galeon.com/geneticos.html
Introducción a los algoritmos genéticos y sus aplicaciones Piedad Tolmos Rodríguez-
Piñero
http://www.uv.es/asepuma/X/J24C.pdf
Algoritmos genéticos paralelos Antonio la Torre de la Fuente (16/09/ 2005)
http://laurel.datsi.fi.upm.es/~atorre/_media/universidad/algoritmos_geneticos_paralelos.
pdf?id=universidad%3Adoctorado&cache=cache
Algoritmos Genéticos en Paralelo de Grado Fino por Martin Pelikan, Prasanna
Parthasarathy, and Arun Ramraj Traducido por Germán Rojo Eguren
http://www.acm.org/crossroads/espanol/xrds8-3/fineGrained.html
Informática evolutiva J. J. Merelo Guervós
http://geneura.ugr.es/~jmerelo/ie/ie.ps.gz
Creación de música mediante algoritmos genéticos
http://www.rieoei.org/opinion43.htm
Algoritmos genéticos
http://www.ecobachillerato.com/experto/algoritmo.pdf
Algoritmos genéticos Introducción, métodos de búsqueda y optimización
Raúl Martín Rello
Algoritmos genéticos en grafos: Algoritmos Evolutivos
http://www.dma.eui.upm.es/MatDis/Seminario3/GenAlg.pdf
Algoritmos Genéticos: Princípios y Aplicaciones Marco Aurélio Cavalcanti Pacheco

31
Algoritmos Genéticos Katherine Viteri, Christian Salazar, Carlos Paredes, José Luis
Muñoz
http://www.fiec.espol.edu.ec/investigacion/topico/tabusearch.pdf
Introducción a los algoritmos genéticos y applets de ejemplo (incluido el applet
utilizado en este trabajo
http://cs.felk.cvut.cz/~xobitko/ga/

32