Algoritmos Genticos

Grupo 6
Sharn Benass
Michell Vanrell

Agenda

Introduccin

Cmo funcionan
Ejemplo

Por qu funcionan
Algoritmos genticos paralelos

Introduccin

Provienen de la familia de modelo computacional

basado en la evolucin
Introducidos por Holland en 1975
Proveen una solucin potencial a un problema
especfico en una estructura tipo cromosoma y
aplican operadores de recombinacin para
preservar la informacin crtica
Cualquier modelo basado en poblacin que usa
seleccin y recombinacin para generar nuevos
elementos en el espacio de bsqueda

Introduccin

Poblacin

Conjunto de soluciones potenciales, donde la

poblacin inicial puede ser elegida
randmicamente
Cambia con el tiempo pero su tamao se
mantiene

Individuo

Elemento de la poblacin
Cada individuo es representado por una cadena
de caracteres

Introduccin

Crossover

Mutacin

Dos nuevos individuos pueden ser obtenidos de

dos padres en el mating pool, recombinando a
ambos padres
Individuos en el mating pool tambin pueden
cambiar a travs de mutacin randmica

Resultado -> Un nueva generacin

El proceso se repite y converge a una poblacin

con individuos muy similares entre si

Algoritmo gentico Cannico

Los individuos son cadenas binarias de largo fijo

codificadas segn el problema a resolver
En general las poblaciones iniciales se eligen de
forma randmica
Luego de creada la poblacin inicial se le aplica a
cada individuo la funcin de evaluacin
En base al resultado de dicha funcin se calcula el
fitness
Fitness = fi/f

Algoritmo gentico Cannico

Una vez calculado el fitness de cada

individuo, se pasa a la seleccin para
generar la generacin intermedia
Los individuos con mayor nivel de
fitness son copiados en la generacin
intermedia

Stochastic Sampling with Replacement

Remainder Stochastic Sampling

Algoritmo gentico Cannico

Crossover

Se eligen pares de individuos randmicamente

que sern recombinados con una probabilidad p
Se elige un punto aleatorio del individuo y se
intercambian sus partes

Mutacin

Es aplicada con una probabilidad muy baja a

cada bit
Diferentes variantes

Generar un nuevo bit

Invertir un bit

Algoritmo
Repetir
para cada individuo i evaluar y calcular fitness f(i)
Crear mating pool de tamao N basado en los valores de fitness f(i)

para i=1 hasta (N/2)

quitar pares de individuos {j,k} del mating pool
recombinar usando los individuos j y k
aplicar mutacin

Hasta condicin de parada

Consideraciones

Diferentes implementaciones. Idea bsica: nuevas

buenas soluciones pueden ser obtenidas a partir de
bloques de soluciones existentes
El tiempo de corrida va a depender de los
parmetros con gran probabilidad de que si se deja
correr por un buen tiempo se obtenga una solucin
ptima o casi ptima
Trabajan sobre toda una poblacin otorgando
mayor paralelismo
Pueden trabajar sobre un problema sin conocer los
detalles del mismo con demasiada exactitud

Ejemplo Assembly Line Balancing Problem

Diseo de lnea de fabricacin usando n

estaciones
En cada estacin se realizan ciertas
operaciones en cada producto fabricado y
luego se pasa a otra estacin en la lnea
Problema: asignar las operaciones a las n
estaciones de forma de que la lnea de
produccin sea balanceada, dado el tiempo
que lleva cada operacin
Algunas operaciones deben realizarse antes
de que otras puedan empezar

Grafo de precedencia

Pasos a seguir

Codificacin
Espacio de soluciones
Fitness y seleccin de generacin
intermedia
Recombinacin

Codificacin

Se utilizar un string de nmeros

El nmero en el i-cimo lugar del string

corresponde a la estacin en la cual la i-cima
operacin se llevar a cabo

Los nmeros de las operaciones van a ser

consistentes con el grafo de precedencia
Segn el grafo presentado:

Espacio de soluciones

Soluciones no posibles porque rompen las

reglas de precedencia
Opciones

Crossover y mutacin espaciales para mantener

las restricciones
Dejar que se generen soluciones no aceptables

Funcin de penalizacin para alejar las soluciones no

aceptables
Forzar cada string a formar una solucin aceptable
Se mantiene el string no aceptable pero se decodifica
de forma que represente una solucin posible

Fitness y seleccin de la
generacin intermedia

El fitness para el ALBP incluye

un elemento correspondiente al tiempo total de

la estacin mas lenta
Un costo de penalizacin para las soluciones
que no sean viables por restricciones de
precedencia
max i (Si) + KNv

Si Tiempo total para las operaciones asignadas a la

estacin i
Nv Nmero de violaciones de precedencia
K Constante igual al tiempo de la operacin mas larga

Fitness y seleccin de la
generacin intermedia

Hay diferentes opciones para obtener el

fitness

Fitness = constante funcin_objetivo

Fitness = Recproco (funcin objetivo)
Fitness i = exp(-hvi)

Con h elegida para que el fitness caiga en cierto rango

particular

Superar las dificultades graduando el valor

de fitness explcitamente. Esto da control de
la velocidad de convergencia del algoritmo

Fitness y seleccin de la
generacin intermedia

Si el problema es de maximizacin, el
fitness del individuo i va a ser el valor de su
evaluacin de la funcin objetivo (vi)
Si el problema es de minimizacin, se toma
como fitness el opuesto a ese valor (-vi)
Se realiza una escala lineal de los valores
para obtener una distribucin de fitness con
las siguientes propiedades

N
i 1

Fi 1

max i F i Fi / N
i 1

Fi 0i

Fitness y seleccin de la
generacin intermedia

Seleccin de la generacin intermedia a

travs de Stochastic Universal Sampling

Se toman los integrantes de la poblacin y se

ordenan randmicamente
A cada uno se le asigna un intervalo proporcional
a su fitness y escalado de forma que el total de
los intervalos sea N
Se consideran los intervalos alineados en una
lnea que va de 0 a N
Se elige un nmero x (aleatorio uniforme entre 0
y 1) y se pone a los individuos correspondientes
a los intervalos x, x+1, , x+N en el mating pool
Pares de individuos del mating pool son
recombinados usando crossover y mutacin

Recombinacin

Crossover

Ocurre en un nico punto randmico con

probabilidad p

Mutacin

Para cada operacin, con una

probabilidad pequea q, se le cambia la
estacin asignada a la anterior o a la
siguiente en el string

Recombinacin ajustes

Ajustes incluidos por los autores

Elitismo

Incluir en una posicin aleatoria de la poblacin el

individuo con mejor valor de fitness de la generacin
anterior

Luego de que se genera la nueva generacin, si

algn descendiente tiene peor valor de fitness
que cualquiera de la generacin anterior, se lo
retira y se deja a uno de sus padres que siga
adelante incambiado en la prxima generacin

Resultados experimentales

Consideraciones previas

No se realizaron optimizaciones en el cdigo

Las comparaciones se realizan fijando el
nmero de generaciones en una corrida y
observando al mejor individuo en la poblacin
final
Mtodo de inicializacin de la primer poblacin

Aleatoriamente
Arcus

Si bien tiene resultados muy buenos, se tiene el

problema de convergencia prematura por poca
variabilidad

50 operaciones a asignar a 5 estaciones

Resultados experimentales

Valores fijados para la condicin de parada

de 350 generaciones

Probabilidad de crossover

Probabilidad de mutacin

0.6
0.7
0.8
{0.005, 0.01, 0.015, 0.020, 025, 0.030, 0.035, 0.04}

Scaling factor

{1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 2.5}

Resultados experimentales

5 problemas generados randmicamente

8 corridas para cada problema con diferentes
semillas para generacin de valores aleatorios
Valores en la tabla

(a) promedio del porcentaje de la desviacin de las

mejores soluciones en la ltima generacin de la mejor
solucin encontrada
(b) promedio del porcentaje de individuos de la poblacin
final que tuvieron el mismo valor que el mejor de la
generacin
(c) primer generacin en la que un promedio del 90% o
mas de los individuos de la poblacin tienen el mismo
valor que el mejor de la poblacin

Resultados

p = 0.06

Otros resultados

Comparaciones eliminando el crossover y realizando

seleccin de la siguiente manera

Realizando mutacin solo si la solucin anterior es mejorada

Dejando que la mutacin genere peores soluciones y dejar

que la seleccin mejore la calidad global de la generacin,
agregando elitismo y eliminando aquellos individuos que
luego de la mutacin son peores soluciones que el peor de
la generacin anterior

El porcentaje de desviacin del valor ptimo es mayor que el

encontrado en los resultados anteriores

Las mejores soluciones despus de 350 generaciones estaban

en promedio a un 32% de la mejor solucin encontrada

La combinacin de crossover y seleccin es mas efectiva

que la utilizacin de cada una por separado

Solo seleccin, se reemplaza si

mejora

Solo seleccin, se reemplaza siempre

Fundamentos Matemticos de los

Algoritmos Genticos

Por qu funcionan los Algoritmos

Genticos?
Los Esquemas (Hiperplanos)
El Teorema Fundamental
Paralelismo Implcito.

Fundamentos Matemticos de los

Algoritmos Genticos

Los Algoritmos Genticos no procesan

estrictamente individuos, sino
similitudes entre ellos: patrones de
similitud entre individuos o esquemas
Dado que cada individuo encaja en
muchos patrones a la vez, la eficiencia
de la bsqueda se multiplica.

Los Esquemas

El esquema es una herramienta para estudiar la forma

en que una cadena representa a otras cadenas.
Es un patrn de similitud que describe un subconjunto
de cadenas con similitudes en ciertas posiciones de la
cadena.
Consideramos el alfabeto binario extendido { 0, 1, *} .
Un esquema recoge una determinada cadena si en
cada posicin del esquema un 1 corresponde a un 1
en la cadena, un 0 a un 0, y el * se corresponde con
cualquier cosa

Los Esquemas
Ejemplos

El esquema *0000 encaja con las

cadenas {00000, 10000}.

El esquema 0*0*1 encaja con las

cadenas {00001, 00011, 01001,
01011}.

Los Esquemas
Proposicin: Se verifican las siguientes propiedades:
1.
Si un esquema contiene k smbolos de indeferencia
( * ) entonces representa a 2k cadenas binarias.
2.
Una cadena binaria de longitud L encaja en 2 L
esquemas distintos.
3.
Considerando cadenas binarias de longitud L,
existen en total 3L posibles esquemas.
4.
Una poblacin de n cadenas binarias de longitud L
contiene entre 2L y n2L esquemas distintos.

Los Esquemas

Consideraremos los efectos de las

operaciones de reproduccin, cruce y
mutacin de los esquemas contenidos en la
poblacin.
En cada instante de tiempo t (generacin)
consideraremos una poblacin de cadenas
individuales P(t) compuestas por P j, j= 1..n

Los Esquemas

Ciertos esquemas son ms especficos que

otros.
Ciertos esquemas abarcan ms parte de la
longitud total de la cadena que otros.
Para cuantificar estas ideas introducimos dos
propiedades de los esquemas:

Los Esquemas

: H
Orden de un esquema,
Es el nmero de posiciones
fijas (con 0 1) que contiene dicho esquema.
Ejemplo:
H = 011*1**
=4
Longitud caracterstica de
Es la
Hun esquema,
distancia entre la primera y ltima posiciones fijadas
H de la

cadena.
Ejemplo:
H = 011*1**
H = 0******
H 5 1 4
H 11 0

Los Esquemas

L H

Un esquema H representa a 2
cadenas: cuanto mayor sea el orden del
esquema a menos cadenas representar.
El orden de un esquema da una medida de su
especificidad.
La longitud caracterstica da una medida de la
compacidad de la informacin contenida en el
esquema.

Diferentes vistas del

Muestreo de los hiperplanos

Diferentes vistas del

Muestreo de los hiperplanos (2)

Los Esquemas
Dados una poblacin de cadenas binarias P en un instante t y un
esquema H se definen:
Presencia de H en P en el instante t, m(H,t): Es el nmero de
cadenas de la poblacin P en el instante t que encajan en el
esquema H.
Aptitud del esquema H en P en el instante t,
f H , t : Es el
promedio de las aptitudes de todas las cadenas de la poblacin
que encajan en el esquema H en el instante t.

1 i m
f H , t Aptitud vi
m i 1

siendo m m H , t y

vi i 1..m las cadenas de P que encajan en H.

Los Esquemas

Aptitud media de la poblacin en el instante t, f : Es

el promedio de las aptitudes de todas las cadenas de
la poblacin en el instante t.
i n

1
f Aptitud (vi )
n i 1

EL TEOREMA FUNDAMENTAL

Buscamos una formulacin de cmo

evoluciona en promedio un esquema
dentro de una poblacin de un A.G.

Consideramos los efectos individuales

y combinados de la reproduccin,
cruce y mutacin sobre los esquemas
de una poblacin de cadenas.

El Efecto de la Seleccin

Asumimos que las cadenas son

copiadas a la nueva generacin con
una probabilidad basada en su valor de
capacidad (fitness fi ) divida por la
capacidad total de la generacin:

pi

fi

f
j

El Efecto de la Seleccin

Supongamos que en un instante dado

de tiempo t hay m ejemplares de un
esquema particular H contenido en la
poblacin P(t) (m = m(H,t) ).

Tomamos una poblacin de tamao n.

El Efecto de la Seleccin
Mediante reemplazamientos a partir de la poblacin P(t),
esperamos tener m(H,t+1) representantes del
esquema en la poblacin en el instante t +1 donde:

f H ,t
m H , t 1 m H , t n
fj
j

Siendo f(H) la aptitud media de las cadenas

representadas por el esquema H en el instante t.

Los Esquemas
Recordando ...

Aptitud media de la poblacin en el

instante t, f : Es el promedio de las
aptitudes de todas las cadenas de la
poblacin en el instante t.
i n

1
f fi
n i 1

El Efecto de la Seleccin
Ecuacin de crecimiento reproductivo del esquema:

m H , t 1 m H , t

f H ,t
f

Un esquema particular crece como el porcentaje de la

aptitud media del esquema respecto de la aptitud de
la poblacin.

El Efecto de la Seleccin
Sea un esquema particular H que permanece por encima
de la media una cantidad c f
( c constante), entonces:

f c f
m H , t 1 m H , t
1 c
m H ,t
f
Comenzando en t 0 :
m H , t m H , 0 1 c

La reproduccin asigna un nmero exponencialmente

creciente (decreciente) de ejemplares a los esquemas por
encima (por debajo) de la media.

El Efecto de la Cruza
El valor esperado de cadenas representantes de H que
han sido seleccionadas y a las que no se les aplica
cruzamiento es:

f H,t
1 pC m H , t
f

El Efecto de la Cruza
El valor esperado del nmero de cadenas representantes
de H que fueron seleccionadas y permanecen en el
esquema despus de aplicrseles cruzamiento es:

pc m H , t

f H ,t
f

1 pR

Siendo pR la probabilidad de ruptura del esquema H bajo

el tipo de cruzamiento que est siendo utilizado.

El Efecto de la Cruza
Sea g el nmero de cadenas ganadas por el esquema H
durante el procedimiento de cruza:

pc m H , t

f H ,t
f

1 pR

El Efecto de la Cruza
Resumiendo las anteriores diapositivas, el valor esperado del
nmero de representantes del esquema H tras haber
efectuado seleccin y cruzamiento es:

f H ,t
f H ,t
m H , t sel cru 1 pC m H , t
pc m H , t
1 pR
f
f

Aporte de las cadenas de H que

no intervinieron en la cruza.
Aporte de las cadenas de H que se cruzan y
se mantienen en H + las cadenas que no eran
de H, pero luego del cruce pasan a formar
parte de l.

El Efecto de la Cruza
Si las cadenas se cortan en un solo punto, la probabilidad de
romper el esquema H con un corte es:
H
pR
L 1
Volviendo a la ecuacin:

f H ,t
f H,t
m H , t sel cru 1 pC m H , t
pc m H , t
1 pR g
f
f

Eliminando g y haciendo cuentas...:

m H , t sel cru m H , t

f H,t
f

1 pC pR

El Efecto de la Cruza
En el algoritmo original de Holland se elige a un compaero, para realizar la
cruza, sin predisposicin. A s que la probabilidad de que esa cadena
encaje en el esquema H es:

P H ,t

m H ,t
n

Tomando en cuenta esto, podemos definir nuevamente

H
pR
1 P H , t
L 1

pR

El Efecto de la Cruza
De esta manera llegamos a:

f H,t
H

P H , t 1 P H , t
1 pC
1 P H , t

L 1
f

f H ,t
H
f H , t
P H , t 1 P H , t
1 pC
1 P H , t

L 1
f
f
Seleccin del 2do padre basado en su aptitud

El Efecto de la Mutacin

Suponemos que la mutacin se aplica con probabilidad pm y que tiene el

efecto de invertir un bit (cambiar un 1 por un 0 viceversa).

Para que una cadena representante del esquema H permanezca en l

tras una mutacin, debe ocurrir que ninguno de los bits definidos del
esquema sea invertido.

pm 1 pm

Estamos suponiendo que los eventos de invertir un bit

son independientes entre si.

El Efecto de la Mutacin

Aadiendo a la expresin que tenamos:

f H ,t
H
f H , t
H
P H , t 1 P H , t
1 pC
1 P H , t 1 pm

1
f
f

El Teorema Fundamental

Este resultado recibe el nombre de Teorema del

esquema o Teorema Fundamental de los algoritmos
genticos:
La presencia de un esquema H en la poblacin P de
la generacin del instante t en un Algoritmo Gentico
evoluciona estadsticamente de modo exponencial
segn la ecuacin anterior.
Los esquemas de orden bajo adaptados por encima
de la media reciben un nmero exponencialmente
creciente de oportunidades en siguientes
generaciones.

El Teorema Fundamental
f H ,t
H
f H , t
H
P H , t 1 P H , t
1 pC
1 P H , t 1 pm

1
f
f

Factor de Crecimiento

Kg

Factor de Supervivencia

KS

El Teorema Fundamental

Los esquemas con una aptitud por encima de la

media
incrementan exponencialmente su presencia en
sucesivas generaciones K g 1
Los que tienen la aptitud por debajo de la media
decrementan exponencialmente su presencia en
la poblacin
K g 1
La tendencia de los esquemas aventajados a
incrementar su presencia en sucesivas
generaciones se acenta cuando el esquema es
corto y de bajo orden, pues entonces K S 1

Crticas al Teorema

Slo es una cota inferior, es decir, no es exacto.

No es muy til para predecir a largo plazo el
comportamiento de un algoritmo gentico.
Slo considera los efectos destructivos de los
operadores genticos y no los efectos constructivos.
Es muy particular. Est hecho para un AGS con
seleccin proporcional (de ruleta), cruzamiento de un
punto y probabilidad de mutacin uniforme.

El problema de la Ineficiencia

Los AGs slo se pueden considerar eficientes en

comparacin con otros mtodos estocsticos, pero si se
encuentra un mtodo determinista para resolver un
problema lo har ms eficientemente.
Tendencia al extravo de la bsqueda: el AG realiza la
bsqueda de los mejores puntos utilizando nicamente la
aptitud de los individuos para recombinar internamente los
bloques constructivos.
A veces esta informacin proporcionada es insuficiente para
orientar la bsqueda del ptimo: desorientacin (deception).

El problema de la Ineficiencia

Un caso especialmente desfavorable ocurre cuando

hay una fuerte interaccin entre dos o ms atributos
(genes), de tal forma que la contribucin a la aptitud
de un individuo que realiza cierto gen depende
grandemente de los valores que tomen otros
(epistasis o acoplamiento).
Existen mecanismos para atenuar estos efectos.
En otras ocasiones es necesario incorporar
conocimiento especfico al AG.

Diversidad en los AGs

Diversidad en individuos

Diversidad en Aptitudes

Diversidad en los AGs

Con poca variedad de individuos

poca variedad de esquemas

el operador de cruce pierde la capacidad de
intercambio de informacin til entre individuos

Diversidad en los AGs

Con poca diversidad de aptitudes todos los

individuos tienen similares posibilidades de
sobrevivir

bsqueda aleatoria.

Una gran disparidad de aptitudes suele afectar

negativamente a la diversidad de la poblacin.

Convergencia Prematura

En algn momento de la evolucin de un AG puede ocurrir que un individuo o un

grupo de ellos obtengan una aptitud notablemente superior a los dems (fases
tempranas de la evolucin).
Riesgo de que se produzca una evolucin en avalancha: al incrementar los
individuos ms aptos su presencia en la poblacin, la diversidad disminuye, ello
hace que en la siguiente generacin se favorezca an ms a los individuos ms
aptos hasta que dominan toda la poblacin (sper individuos).
Los sper individuos slo son los ms aptos en cierto momento

Diversidad en los AGs

Deriva gentica: Favorecer ms de lo que les

corresponde a individuos ocasionalmente ms aptos.

convergencia prematura hacia tal `individuo afortunado'.

Conclusin: es necesario tener control sobre la

diversidad de aptitudes de la poblacin para evitar
que se produzca una convergencia prematura
(avalancha) ya sea por exceso diversidad
(superindividuos) o por falta de ella (deriva gentica).

Paralelismo Implcito

La eficacia a los AGs se basa en que, aunque el AG slo procesa n

estructuras en cada generacin, se puede probar que, bajo hiptesis muy
generales, se procesan de modo til al menos
esquemas.
Este paralelismo implcito se consigue sin ningn dispositivo o memoria
adicionales, slo
n3 con la propia poblacin.
A pesar de la ruptura de los esquemas largos de orden alto por los operadores
de cruce y mutacin, los algoritmos genticos procesan inherentemente una
gran cantidad de esquemas mientras procesan una cantidad relativamente
pequea de cadenas.

Algoritmos genticos paralelos

Paralelismo inherente proporcional al tamao de la

poblacin
Sugiere que se puede incrementar el tamao de la
poblacin sin afectar la performance
Problemas en performance generados por
sincronizacin y envo de mensajes
Si se explotan todas las fuentes de paralelismo el
tiempo de ejecucin para generar una generacin
no depende del tamao de la poblacin (Gordon,
Whitley y Bohm)
Grandes poblaciones convergen mas lentamente

Poblaciones globales con

paralelismo

Implementacin del algoritmo gentico

cannico pero con Seleccin por torneo

Se eligen dos individuos de la poblacin actual,

el mejor de ambos pasa a la generacin
intermedia

Se utilizan N/d procesadores donde N es el

tamao de la poblacin
Los procesadores se numeran de 1 a N/2 y
el tamao de la poblacin es par
En cada procesador x habitan dos
individuos: 2x y 2x-1

Poblaciones globales con

paralelismo (2)

Se evalan los individuos

Cada procesador realiza dos sorteos
independientes y guarda los individuos
ganadores de los dos sorteos
El crossover se realiza en los procesadores
numerados con un nmero menor a p*N/2
Todos los procesadores realizan mutacin
en sus individuos (si corresponde)

Modelos isla

6400 individuos en 64 procesadores, por ejemplo

Dividir la poblacin total en subpoblaciones de 100

individuos cada una

Cada subpoblacin ejecuta un algoritmo gentico

Cada x cantidad de generaciones, las
subpoblaciones intercambian algunos individuos
intercambiando material gentico
Si un gran nmero de individuos migra en cada
generacin, se pierden las diferencias entre las
islas
Si la migracin es poco frecuente, podra llevar a
que cada poblacin converja prematuramente

Algoritmos genticos celulares

2500 procesadores dispuestos en una grilla de 50 x

50
Los procesadores solo se comunican con sus
vecinos inmediatos
Cada string (cada procesador) se fija en sus vecinos
inmediatos y elige el mejor individuo que encuentra
Recombina su individuo con el elegido del vecino
Si un vecindario esta a 20 o 25 movimientos de otro,
estos vecindarios estn aislados como en el modelo
de islas
Luego de algunas generaciones hay algunos focos
conteniendo individuos similares

Paralelismo en el ALBP

Se eligi la implementacin de forma de

minimizar el pasaje de mensajes
Locations vs procesadores

En una location habita un nico individuo

Un procesador puede manejar varios individuos

Cada location est conectada con un

pequeo grupo de locations -> vecindario
Definicin del vecindario

El vecindario de una location estar formado por

aquellas locations que no estn a mas de 4 links

Paralelismo en el ALBP

En cada location el algoritmo selecciona un

individuo del vecindario basndose en fitness para
recombinarlo con el individuo residente
La seleccin se realiza de forma que el individuo i
es elegido del vecindario con probabilidad dada por
fi

jvecind ( i )

fj

La reproduccin produce dos descendientes

Se sustituye el individuo actual por su mejor descendiente

siempre que sea mejor que el peor individuo del
vecindario

Paralelismo en el ALBP
Repetir
Para cada individuo i
Evaluar f(i)
Transmitir f(i) para todos los individuos j en el
vecindario
Elegir un individuo j para combinar basado en
fitness
Pedir el individuo j
Reproducir usando los individuos i y j

Hasta que la variacin en la poblacin es

pequea

Conclusiones

El tiempo computacional est dominado por

la evaluacin del fitness incluyendo el
chequeo de validez de la nueva generacin
de soluciones
Los resultados no son tan buenos como
para el algoritmo no paralelo

La convergencia es mas lenta y hay muchos

casos en que no converge

La performance del algoritmo paralelo es

menos sensitiva al scaling factor que la
secuencial

FIN