2.2.
ALGORITMOS GENÉTICOS PARALELOS
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,
destruir
y
especificar
procesos
así
como
la
interacción
entre
ellos.
Básicamente
existen tres formas de paralelizar un programa:
Faralelizació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 algo-
ritmo (selección, cruce y mutación) sobre la población común.
Faralelización de grano medio: los
programas se paralelizan a nivel de bu-
cle.
Esta
paralelización
se
realiza
habitualmente
de
una
forma
automática en
los compiladores.
Faralelizació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álculos sobre sus datos locales.
La
paralelización
de
grano
grueso
tiene
como
atractivo
la
portabilidad,
ya
que
se
adapta
perfectamente
tanto
a
multiprocesadores
de
memoria
distribuida
como
de
memoria
compartida.
Este
tipo
de
paralelización
se
puede
a
su
vez
realizar
siguiendo
tres
estilos
distintos
de
programación:
paralelismo
en
datos,
programa-
ción por paso de
mensajes y programación por paso de datos.
Faralelismo en datos: El compilador se encarga de la distribución de los da-
tos guiado por un conjunto de directivas que introduce el programador. Estas
directivas hacen que cuando se compila el programa las funciones se distri-
buyan entre los
procesadores disponibles.
Como
principal ventaja presenta
su
facilidad
de
programación.
Los
lenguajes
de
paralelismo
de
datos
mas
utilizados son el estándar HPF (High Performance Fortran) y el OpenMP.
Frogramación
por
paso
de
mensaies:
El
método
mas
utilizado
para
pro-
gramar
sistemas
de
memoria
distribuida
es
el
paso
de
mensajes
o
alguna
variante del mismo. La forma mas básica consiste en que los procesos coor-
dinan
sus
actividades
mediante
el
envío
y
la
recepción
de
mensajes.
Las
librerías
mas
utilizadas
son
por
este
orden
la
estándar
MPI
(Message
Pas-
sing Interface) y PVM (Parallel
Virtual
Machine).
Frogramación por paso de datos: A diferencia del modelo de paso de men-
sajes,
la
transferencia
de
datos
entre
los
procesadores
se
realiza
con
primi-
tivas
unilaterales
tipo
put-get,
lo
que
evita
la
necesidad
de
sincronización
entre los procesadores emisor y receptor. Es un modelo de programación de
muy
bajo
nivel
pero
muy
eficiente,
aunque
en
la
actualidad
son
muy
pocos
los fabricantes que los soportan.
Una
de
las
principales
ventajas
de
los
AG
es
que
permite
que
sus
operaciones
se
puedan
ejecutar
en
paralelo.
Debido
a
que
la evolución
natural
trata
con
una
po-
blación entera y no con individuos
particulares, excepto para la fase de selección,
durante
la
cual
existe
una
competencia
entre
los
individuos
y
en
la
fase
de
repro-
ducción,
en
donde
se
presentan
iteraciones
entre
los
miembros
de
la
población,
cualquier otra operación de la
población, en
particular la evaluación de cada uno
de los miembros de la población, pueden hacerse separadamente. Por lo tanto, casi
todas las operaciones en los
AG son implícitamente paralelas.
Se ha establecido que la eficiencia de los
AG
para encontrar
una solución
optima,
esta determinada por el tamaño de la población. Por lo tanto, una población grande
requiere
de
mas
memoria
para
ser
almacenada.
También
se
ha
probado
que
toma
mayor
cantidad
de
tiempo
para
converger.
Si
n
es
el
tamaño
de
la
población,
la
convergencia esperada es n log(n).
Al
utilizar
computadores
en
paralelo,
no
solamente
se
provee
de
mas
espacio
de
almacenamiento,
sino
también
con
el
uso
de
ellos
se
podrán
producir
y
evaluar
mas
soluciones
en
una
cantidad
de
tiempo
mas
pequeño.
Debido
al
paralelismo,
es posible incrementar el tamaño de la población, reducir el costo computacional
y
mejorar el desempeño de los
AG.
Probablemente
el
primer
intento
que
se
hizo
para
implementar
los
AG
en
arqui-
tecturas en paralelo fue en 1981, por John Grefenstette. Los primeros ensayos
consistían en un paralelismo global. Esta aproximación trataba por
paralelizar ex-
plícitamente
las
tareas
paralelas
implícitas
de
los
AG
secuénciales,
por
lo
tanto
la
naturaleza
de
los
problemas
permanecía
invariable.
El
algoritmo
simplemente
manejaba
una
sencilla
población
en
donde
cada
individuo
podía
combinarse
con
cualquiera de los otros, pero la generación de los nuevos hijos y/o su evaluación se
hacía
en
paralelo.
La
idea
básica
es
que
los
diferentes
procesadores
puedan
crear
nuevos individuos y computar sus aptitudes en paralelo, sin tener que comunicarse
con los otros.
La evaluación de la población en paralelo es simple de implementar. A cada proce-
sador se le asigna
un subconjunto
de individuos
para ser evaluados. Por ejemplo,
en
un
computador
de
memoria
compartida,
los
individuos
pueden
estar
almace-
nados
en
la
memoria,
y
cada
uno
de
los
procesadores
puede
leer
los
cromosomas
asignados
y
puede grabar los resultados del computo de las aptitudes. Este
méto-
do
solamente
supone
que
los
AG
trabajan
con
una
generación
actualizada
de
la
población. Se necesita además, alguna sincronización entre las generaciones.
Generalmente,
la
mayor
parte
del
tiempo
de
computo
en
un
AG
se
gasta
en
la
funcion objetivo. El tiempo que se gasta en el manejo de los cromosomas durante
las fases de selección y recombinación es despreciable. En un computador de me-
moria distribuida se puede almacenar la población en un procesador "maestro", el
cual
es
responsable
de
enviar
los
individuos
a
los
otros
procesadores
”esclavos".
El "maestro", también es responsable por guardar los resultados de la evaluación.
Una
desventaja de esta implementación es que se pueden presentar cuellos de bo-
tella,
cuando
los
esclavos
están
desocupados
y
solo
el
maestro
esta
trabajando.
Pero si se hace
un buen uso
del procesador maestro, se puede
mejorar el factor
de
balance, distribuyendo dinámicamente los individuos a los procesadores esclavos,
cuando ellos terminen sus trabajos.
Una
segunda
clase
de
AG
paralelos
consiste
en
dividir
la
población
en
subpo-
blaciones,
y
cada
una
de
ellas
ejecutarlas
en
un
procesador.
El
intercambio
entre
subpoblaciones es posible por medio de un operador de "migración".
Se
emplea
el
modelo
de
islas
para
mostrar
como
los
AG
se
comportan
como
si
el
mundo fuera constituido por islas que se desarrollaran en forma independiente,
unas de las otras. En cada una de las islas, la población es libre de converger hacia
un
optimo
diferente.
El
operador
de
migración
permite
extraer
de
las
diferentes
subpoblaciones las buenas características, para luego mezclarlas.
A
continuación se
muestra el seudocódigo de un algoritmo con la evaluación
pa-
ralelizada:
——————————————————–
generación de la población inicial
while no se cumpla la condición de parada do
do in parallel
.
evaluación de los individuos
end parallel do
.
selección
.
cruce
.
mutación
end while
——————————————————–
y
en el siguiente esquema se muestra el seudocódigo de un
AG con varias
pobla-
ciones que evolucionan en paralelo:
——————————————————–
do in parallel
generación de la población inicial
while no se cumpla la condición de parada do
.
evaluación de los individuos
.
selección
.
producción de nuevos individuos
.
mutación
end while
end parallel do
Escoger la meior solución
——————————————————–
2.3.
COMPARACIÓN DE LOS ALGORITMOS GENÉTICOS
CON OTRAS TÉCNICAS DE OPTIMIZACIÓN
Existen
otras
técnicas
para
resolver
problemas
de
búsqueda
y
de
optimización.
Tanto
los
métodos
que
se
describen
a
continuación,
como
los
AG
no
requieren
información relacionada con la estructura del espacio de búsqueda, ni con las pro-
piedades
de
la
función
objetivo.
Estos
métodos
son
generalmente
estocásticos
y
necesitan utilizar generadores de números aleatorios. Su proceso se realiza hacien-
do suposiciones sobre en donde las soluciones mas optimas tienen la probabilidad
mas alta
de ser encontradas
en el espacio de
búsqueda. La
mayoría de las
ve-
ces
estos
métodos
no
garantizan
que
se
encuentra
una
solución
optima
global
al
problema
a
resolver.
Ellos
solamente
son
capaces
de
proveer
buenas
soluciones
en
una
cantidad
de
tiempo
razonable,
sin
verificar
que
es
la
mejor,
siendo
esto
una de las desventajas de estos métodos. Entre otras técnicas consideradas para la
solución de problemas de búsqueda y optimización se tienen:
Búsqueda
aleatoria:
Explora
el
espacio
de
búsqueda
seleccionando
solu-
ciones y evaluando sus aptitudes. Se considera una estrategia no inteligente
y
se utiliza pocas veces. Sin embargo, cuando se obtiene una solución y no
es
la
optima,
se
puede
mejorar
continuando
la
ejecución
del
algoritmo
por
mas
tiempo.
Teóricamente
si
el
espacio
de
búsqueda
es
finito,
este
método
garantiza encontrar la solución optima, pero en la
mayoria de los problemas,
explorar todo el espacio de búsqueda toma gran cantidad de tiempo.
Escalada
por
la
Máxima
Fendiente:
Es
el
método
mas
simple
de
los
que
utilizan
una clase de gradiente para
direccionar la búsqueda. En cada itera-
ción
se
escoge
aleatoriamente
una
solución,
cercana
a
la
solución
actual
y
si
la
seleccionada
mejora
la
función
objetivo,
se
guarda.
Este
método
con-
verge a una solución optima si la función objetivo del problema es continua
y
si
tiene
solamente
un
pico
(unímodal).
Si
la
función
es
multimodal,
el
algoritmo
termina
en
el
primer
pico
que
encuentre,
aun
sin
ser
este
el
mas
alto. Una forma de evitar que termine en un óptimo local consiste en repetir
varias veces el proceso, comenzando
desde diferentes puntos seleccionados
aleatoriamente.
Temple
Simulado:
Este
método
se
origino
debido
al
proceso
de
formación
de
cristales
en
sólidos
durante
el
proceso
de
enfriamiento.
Este
método
se
comporta
similar
al
método
de
la
Escalada
por
la
Máxima
Pendiente,
pero
con
la
posibilidad
de
descender,
para
evitar
que
se
logre
un
optimo
local.
Cuando
la
temperatura
es
alta,
la
probabilidad
de
modificar
la
solución
es
importante y por lo tanto es posible realizar varios movimientos para explo-
rar
el
espacio
de
búsqueda.
Cuando
la
temperatura
decrece,
existe
mayor
dificultad para descender y el algoritmo trata de escalar desde la ultima
solución encontrada.
Cuando la temperatura es baja, se toma la solución ac-
tual.
Usualmente,
el
temple
simulado
comienza
con
una
temperatura
alta,
la cual decrece exponencialmente. El punto
mas bajo de enfriamiento, es el
mejor.
La
mayor
dificultad
de
este
método
consiste
en
definir
una
tasa
de
decrecimiento, para que el comportamiento del algoritmo sea bueno.
El
método
del
Temple
Simulado
mezclado
con
algunas
características
de
exploración
del
método
de
Búsqueda
Aleatoria
y
del
método
de
Máxima
Pendiente, conlleva a buenos resultados. El Temple Simulado es uno
de los
competidores
mas fuertes de los
AG.
Ambos se derivan de una analogía con
sistemas de evolución natural. Los
AG difieren del Temple Simulado en dos
principales
características:
Primero,
los
AG
usan
una
población
basada
en
selección, mientras el Temple Simulado solamente trabaja con un individuo
en
cada
iteración,
pero
de
otro
lado,
las
iteraciones
en
el
Temple
Simula-
do
son
mucho
mas
simples
y
a
menudo
se
ejecutan
mucho
mas
rápido.
La
mayor
ventaja
de
los
AG
consiste
en
la
habilidad
excepcional
para
ser
pa-
ralelizado,
mientras
que
el
Temple
Simulado
no
gana
mucho.
Segundo,
los
AG
usan
operadores
de
recombinación,
capaces
de
mezclar
buenas
carac-
terísticas
desde
diferentes
soluciones.
De
otro
lado,
el
método
del
Temple
Simulado es muy simple de implementar y genera buenos resultados.
Mister Wong
Portal para Investigadores y Profesionales
