Ecología: En la modelización de fenómenos ecológicos tales como las carre-
ras de armamento biológico, la coevolución de parásito-huesped, la simbio-
sis, y el flujo de recursos.
Genética
de
poblaciones:
En
el
estudio
de
preguntas
del
tipo
"¿Bajo
qué
condiciones será viable evolutivamente un gene para la recombinación?".
Evolución y aprendizaje: Los
AG se han utilizado en el estudio de las rela-
ciones entre el aprendizaje individual y la evolución de la especie.
Sistemas sociales: En el estudio de aspectos evolutivos de los sistemas so-
ciales,
tales
como
la
evolución
del
comportamiento
social
en
colonias
de
insectos,
y
la
evolució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
AG.
Gracias al éxito en estas y otras áreas,
los
AG
han llegado a ser un campo puntero en la investigación actual.
2.
ALGORITMOS GENÉTICOS
2.1.
ALGORITMOS GENÉTICOS SIMPLES
2.1.1.
Tipos de Representación
Durante los primeros años el tipo de representación utilizado era siempre
binario,
debido a que se adapta perfectamente al tipo de operaciones y el tipo de operado-
res
que
se
utilizan
en
un
AG.
Sin
embargo,
las
representaciones
binarias
no
son
siempre efectivas por lo que se empezaron a utilizar otro tipo de representaciones.
En
general,
una
representación
ha
de
ser
capaz
de
identificar
las
características
constituyentes
de
un
conjunto
de
soluciones,
de
forma
que
distintas
representa-
ciones dan lugar a distintas perspectivas y por tanto distintas soluciones. Podemos
considerar tres tipos básicos de representaciones:
Representación binaria: Cada gen es un valor 1 ó 0.
1
0
1
1
0
1
Representación entera:
Cada gen es un valor entero.
1
0
3
-1 0 4
Representación real:
Cada gen es un valor real.
1,78 2,6 7 0 -1,2 6,5
Ejemplo:
Primero
considere
como
se
puede
usar
una
cadena
de
bits
para
describir
una
res-
tricción
sobre
un
atributo,
por
ejemplo,
el
atributo
cielo
con
sus
tres
valores
po-
sibles:
soleado,
nublado,
lluvia.
Una
manera
obvia
de
codificar
una
restricción
sobre este atributo, consiste en usar una cadena de 3 bits, en donde cada posición
de
la
cadena
corresponde
a
un
valor
en
particular.
Colocar
un
1
en
alguna
posi-
ción,
indica
que
el
atributo
puede
tomar
el
valor
correspondiente.
Por
ejemplo,
la
cadena 010, representa la restricción cielo = nublado. De manera similar, la cade-
na 011 representa la restricción mas general cielo = nublado ? cielo = lluvia.
Observe
que
111 representa
la restricción
mas
general posible,
indicando
que
no
importa que valor tome el atributo cielo.
Dado este método para representar restricciones sobre atributos, las conjunciones
de restricciones sobre múltiples atributos pueden representarse por concatenación.
Por
ejemplo,
considere
un
segundo
atributo,
viento,
con
valores
posibles
fuerte
y
débil.
La
precondición
de
una
regla
como:
(cielo
=
nublado
?
lluvia)
?
(viento
= fuerte) puede representarse por la siguiente cadena de bits de longitud 5:
cielo viento
011 10
Las
post-condiciones,
como
jugar-tenis?
=
si,
pueden
representarse
de
la
misma
manera.
La
regla
completa
puede
describirse
concatenando
también
la
cadena
que
repre-
senta
la
post-condición.
Por
ejemplo,
la
regla:
Si
viento
=
fuerte
Entonces
jugar-
tenis? = si, puede representarse como:
cielo viento jugar-tenis?
111
10
10
Los
primeros
tres
bits
indican
que
no
nos
importa
el
valor
del
atributo
cielo;
los
siguientes
dos describen la restricción sobre viento; los dos
últimos bits represen-
tan
la
post-condición
de
la
regla.
Aquí
asumimos
que
jugar-tenis?
Puede
tomar
valores si o no. Esto nos da una representación donde las reglas que nos interesan
se codifican como cadenas de bits de longitud fija.
Es útil considerar que toda cadena de bits que es sintacticamente valida, represen-
ta
una
hipótesis
bien
definida.
Por
ejemplo,
en
el
código
anterior,
la
cadena
111
10
11,
representa
una
regla
cuya
post-condición
no
establece
restricciones
sobre
el atributo jugar tenis?. Para evitar esta posibilidad, se puede usar un código dife-
rente, por ej., para el atributo jugar-tenis? usar un solo bit que indique los valores
si
o
no;
o
bien,
se
pueden
alterar
los
operadores
genéticos
para
evitar
explícita-
mente la construcción
de tales cadenas de bits; o simplemente asignar un valor
de
adaptación muy bajo a estas cadenas.
2.1.2.
Tamaño de la Población
Una
cuestión
que
se
puede
plantear
es
la
relacionada
con
el
tamaño
idóneo
de
la
población.
Parece
intuitivo
que
las
poblaciones
pequeñas
corren
el
riesgo
de
no cubrir adecuadamente el espacio de búsqueda, mientras que el trabajar con
poblaciones
de
gran
tamaño
puede
acarrear
problemas
relacionados
con
el exce-
sivo
costo
computacional.
Goldberg
efectuó
un
estudio
teórico,
obteniendo
como
conclusión
que
el
tamaño
óptimo
de
la
población
para
ristras
de
longitud
I,
con
codificación binaria, crece exponencialmente con el tamaño de la ristra.
Este
resultado
traería
como
consecuencia
que
la
aplicabilidad
de
los
AG
en
pro-
blemas
reales
sería
muy
limitada,
ya
que
resultarían
no
competitivos
con
otros
métodos de optimización combinatoria.
Alander,
basándose en evidencia empíri-
ca sugiere que un tamaño de población comprendida entre l y 21 es suficiente para
atacar con éxito los problemas por el considerados.
2.1.3.
Población Inicial
Habitualmente
la
población
inicial
se
escoge
generando
ristras
al
azar,
pudien-
do
contener
cada
gen
uno
de
los
posibles
valores
del
alfabeto
con
probabilidad
uniforme.
Se
podria
preguntar
que
es
lo
que
sucedería
si
los
individuos
de
la
po-
blación inicial se obtuviesen como resultado de alguna técnica heurística o de
optimización local. En los pocos trabajos que existen sobre este aspecto, se cons-
tata
que
esta
inicialización
no
aleatoria
de
la
población
inicial,
puede
acelerar
la
convergencia
del
AG.
Sin
embargo
en
algunos
casos
la
desventaja
resulta
ser
la
prematura convergencia del algoritmo, queriendo indicar con esto la convergencia
hacia óptimos locales.
La
población
inicial
de
un
AG
puede
ser
creada
de
muy
diversas
formas,
desde
generar aleatoriamente
el valor
de cada gen
para cada individuo,
utilizar
una fun-
ción ávida o generar alguna
parte
de cada individuo y luego aplicar
una búsqueda
local.
2.1.4.
Función Objetivo
Dos aspectos
que resultan cruciales en el comportamiento
de los
AG son la deter-
minación
de
una
adecuada
función
de
adaptación
o
función
objetivo,
así
como
la
codificación utilizada.
Idealmente
nos
interesaría
construir
funciones
objetivo
con
“ciertas
regularida-
des”,
es
decir
funciones
objetivo
que
verifiquen
que
para
dos
individuos
que
se
encuentren cercanos en el espacio de búsqueda, sus respectivos valores en las fun-
ciones
objetivo sean similares. Por otra parte una dificultad en el comportamiento
del
AG
puede
ser
la
existencia
de
gran
cantidad
de
óptimos
locales,
así
como
el
hecho de que el óptimo global se encuentre
muy aislado.
La regla general para construir una buena función objetivo es que ésta debe reflejar
el
valor
del
individuo
de
una
manera
“real”,
pero
en
muchos
problemas
de
opti-
mización
combinatoria,
donde
existe
gran
cantidad
de
restricciones,
buena
parte
de los puntos del espacio de búsqueda representan individuos no válidos.
Para
este
planteamiento
en
el
que
los
individuos
están
sometidos
a
restricciones,
se
han
propuesto
varias
soluciones.
La
primera
sería
la
que
se
podria
denominar
absolutista,
en
la
que
aquellos
individuos
que
no
verifican
las
restricciones,
no
son
considerados
como
tales,
y
se
siguen
efectuando
cruces
y
mutaciones
hasta
obtener
individuos
válidos,
o
bien,
a
dichos
individuos
se
les
asigna
una
función
objetivo igual a cero.
Otra
posibilidad
consiste
en
reconstruir
aquellos
individuos
que
no
verifican
las
restricciones.
Dicha
reconstrucción
suele
llevarse
a
cabo
por
medio
de
un
nuevo
operador que se acostumbra a denominar reparador.
Otro enfoque está basado en la penalización de la función objetivo. La idea general
consiste en dividir la función objetivo del individuo por una cantidad (la penaliza-
ción)
que
guarda
relación
con
las
restricciones
que
dicho
individuo
viola.
Dicha
cantidad
puede
simplemente
tener
en
cuenta
el
número
de
restricciones
violadas
ó
bien el denominado costo esperado de reconstrucción, es decir el coste asociado
a
la conversión de dicho individuo en otro que no viole ninguna restricción.
Otra
técnica
que
se
ha
venido
utilizando
en
el
caso
en
que
la
computación
de
la
función objetivo sea
muy compleja es la denominada evaluación aproximada de la
función objetivo. En algunos casos la obtención de n funciones objetivo aproxima-
das
puede
resultar
mejor
que
la evaluación
exacta
de
una
única
función
objetivo
(supuesto
el
caso
de
que
la evaluación
aproximada
resulta
como
mínimo
n
veces
más rápida que la evaluación exacta).
Un
problema
habitual
en
las
ejecuciones
de
los
AG
surge
debido
a
la
velocidad
con
la
que
el
algoritmo
converge.
En
algunos
casos
la
convergencia
es
muy
rá-
pida,
lo
que
suele
denominarse
convergencia
prematura,
en
la
cual
el
algoritmo
converge hacia óptimos locales,
mientras que en otros casos el problema es justo
el contrario, es decir se produce una convergencia lenta
del algoritmo.
Una posi-
ble
solución
a
estos
problemas
pasa
por
efectuar
transformaciones
en
la
función
objetivo.
El
problema
de
la
convergencia
prematura,
surge
a
menudo
cuando
la
selección
de
individuos
se
realiza
de
manera
proporcional
a
su
función
objetivo.
En
tal
caso,
pueden
existir
individuos
con
una
adaptación
al
problema
muy
supe-
rior al resto,
que a medida que avanza el algoritmo “dominan” a la población. Por
medio de una transformación de la función objetivo, en este caso una comprensión
del
rango
de
variación
de
la
función
objetivo,
se
pretende
que
dichos
“superindi-
viduos” no lleguen a dominar a la población.
El problema de la lenta convergencia del algoritmo, se resolvería de
manera aná-
loga, pero en este caso efectuando una expansión del rango de la función objetivo.
La
idea
de
especies
de
organismos,
ha
sido
imitada
en
el
diseño
de
los
AG
en
un
método
propuesto
por
Goldberg
y
Richardson,
utilizando
una
modificación
de
la
función
objetivo
de
cada
individuo,
de
tal
manera
que
individuos
que
estén
muy
cercanos
entre
sí
devalúen
su
función
objetivo,
con
objeto
de
que
la
población
gane en diversidad.
verán devaluada la probabilidad de ser seleccionados como padres, aumentándose
la probabilidad de los individuos que se encuentran más aislados.
(la
distancia
de
Hamming
se
define
como
el
número
de
bits
que
tienen
que
cam-
biarse
para
transformar
una
palabra
de
código
válida
en
otra
palabra
de
código
válida.
Si
dos
palabras
de
código
difieren
en
una
distancia
d,
se
necesitan
d
errores
para
convertir una en la otra.
Por ejemplo:
La distancia
Hamming entre
1011101 y
1001001 es 2.
La distancia
Hamming entre
2143896 y
2233796 es 3.
La distancia Hamming entre “toned” y “roses” es 3.)
Mister Wong
Portal para Investigadores y Profesionales
