2.1.5.
Operador de Selección
El operador de Selección es el encargado de transmitir y conservar aquellas carac-
terísticas
de
la
soluciones
que
se
consideran
valiosas
a
lo
largo
de
las
generacio-
nes.
El
principal
medio
para
que
la
información
útil
se
transmita
es
que
aquellos
individuos
mejor
adaptados
(mejor
valor
de
función
de
evaluación)
tengan
más
probabilidades de reproducirse. Sin embargo, es necesario también incluir un fac-
tor aleatorio que permita reproducirse a individuos que aunque no estén muy bien
adaptados,
puedan
contener
alguna
información
útil
para
posteriores
generacio-
nes,
con
el
objeto
de
mantener
así
también
una
cierta
diversidad
en
cada
pobla-
ción.
Algunas de las técnicas de las cuales se dispone son las siguientes:
Ruleta
o
Selección
Proporcional:
Con
este
método
la
probabilidad
que
tiene
un
individuo
de
reproducirse
es
proporcional
a
su
valor
de
función
de
evaluación,
es
decir, a su adaptación. En este método se define un rango con las características de
la
selección
por
sorteo.
El
número
al
azar
será
un
número
aleatorio
forzosamente
menor
que
el
tamaño
del
rango.
El
elemento
escogido
será
aquel
en
cuyo
rango
esté
el
número
resultante
de
sumar
el
número
aleatorio
con
el
resultado
total
que
sirvió
para
escoger
el
elemento
anterior.
El
comportamiento
es
similar
al
de
una
ruleta, donde se define un avance cada tirada a partir de la posición actual.
Tiene
la ventaja de que no es posible escoger dos veces consecutivas el mismo elemento,
y
que
puede
ser
forzado
a
que
sea
alta
la
probabilidad
de
que
no
sean
elementos
próximos
en
la
población
-esto
último
no
es
una
ventaja
de
por
sí;
salvo
que
al-
gunos de los otros operadores genéticos, es
mejor utilizar
un
método de selección
directa basado en la posición relativa de los individuos de la población-.
Selección
por
Ranking:
Desarrollado
por
Whitley(1989)
consiste
en
calcular
las
probabilidades
de reproducción atendiendo a la ordenación
de la población
por el
valor de adaptación en vez de atender simplemente a su valor de adecuación. Estas
probabilidades se pueden calcular de diversas formas, aunque el método
habitual
es el ranking lineal (Baker (1985)).
Selección por Torneo: Reporta un valor computacional muy bajo debido a su sen-
cillez. Se selecciona un grupo de t individuos (normalmente t = 2, torneo binario)
y
se genera un número aleatorio entre 0 y 1. Si este número es menor que un cierto
umbral
K
(usualmente 0,75), se selecciona para reproducirse al individuo con
me-
jor
adaptación,
y
si
este
número
es
menor
que
K,
se
selecciona,
por
el
contrario,
al individuo con peor adaptación.
Esta técnica tiene la ventaja
de que permite un cierto
grado de elitismo -el mejor
nunca va a morir, y los mejores tienen más probabilidad de reproducirse y de emi-
grar
que
los
peores-
pero
sin
producir
una
convergencia
genética
prematura,
si
la
población
es,
al
menos,
un
orden
de
magnitud
superior
al
del
número
de
elemen-
tos
involucrados
en
el
torneo.
En
caso
de
que
la
diferencia
sea
menor
no
hemos
observado mucha diferencia entre emplear el torneo o no.
2.1.6.
Operador de Cruce
El
operador
de
cruce
permite
realizar
una
exploración
de
toda
la
información
al-
macenada
hasta
el
momento
en
la
población
y
combinarla
para
crear
mejores
in-
dividuos.
Dentro de los métodos habituales destacamos los siguientes:
Cruce de un punto: Es el método de cruce más sencillo. Se selecciona una posición
en
las
cadenas
de
los
progenitores,
y
se
intercambian
los
genes
a
la
izquierda
de
esta posición.
Cruce de n
puntos: Es una
generalización
del método anterior. Se seleccionan
varias posiciones (n) en las cadenas de los progenitores y se intercambian los
genes a ambos lados de estas posiciones.
Cruce
Uniforme:
Se
realiza
un
test
aleatorio
para
decidir
de
cual
de
los
progeni-
tores se toma cada posición de la cadena.
Cruces
para
permutación:
Existe
una
familia
de
cruces
específicas
para
los
pro-
blemas de permutación, siendo algunos de ellos:
Cruce de mapeamiento parcial: Toma una subsecuencia del genoma del
padre y procura preservar el orden absoluto de los fenotipos -es decir, orden
y
posición
en
el
genoma-
del
resto
del
genoma
lo
más
parecido
posible
de
la
madre.
Cruce
de
orden:
toma
una
subsecuencia
del
genoma
del
padre
y
procura
preservar el orden relativo de los fenotipos del resto del genoma lo más
parecido posible de la madre.
Cruce de ciclo: Tomamos el primer
gen del
genoma del padre,
poniéndolo
en la primera posición del hijo, y el primer gen del genoma de la madre, po-
niéndolo dentro del genoma del hijo en la posición que ocupe en el genoma
del
padre.
El
fenotipo
que
está
en
la
posición
que
ocupa
el
gen
del
genoma
del
padre igual al primer
gen del
genoma de la
madre se va a colocar en la
posición
que
ocupe
en
el
genoma
del
padre,
y
así
hasta
rellenar
el
genoma
del hijo.
Es una buena idea que, tanto la codificación como la técnica de cruce, se hagan de
manera que las características buenas se hereden; o, al menos, no sea mucho peor
que el peor de los
padres. En problemas en los
que, por ejemplo, la adaptación es
función
de
los
pares
de
genes
colaterales,
el
resultante
del
cruce
uniforme
tiene
una adaptación completamente aleatoria.
2.1.7.
Operador de Mutación
La
mutación
se
considera
un
operador
básico,
que
proporciona
un
pequeño
ele-
mento de aleatoriedad en la vecindad (entorno) de los individuos de la población.
Si
bien
se
admite
que
el
operador
de
cruce
es
el
responsable
de
efectuar
la
bús-
queda a lo largo del espacio de
posibles soluciones, también parece desprenderse
de
los
experimentos
efectuados
por
varios
investigadores
que
el
operador
de
mu-
tación
va
ganando
en
importancia
a
medida
que
la
población
de
individuos
va
convergiendo
(Davis).
El
objetivo
del
operador
de
mutación
es
producir
nuevas
soluciones
a
partir
de
la
modificación
de
un
cierto
número
de
genes
de
una
solu-
ción existente, con la intención de fomentar la variabilidad dentro de la población.
Existen
muy diversas formas de realizar la mutación, desde la más sencilla ( Pun-
tual ), donde cada gen muta aleatoriamente con independencia
del resto de
genes,
hasta
configuraciones
más
complejas
donde
se
tienen
en
cuanta
la
estructura
del
problema y la relación entre los distintos genes.
Schaffer y col. encuentran que el efecto del cruce en la búsqueda es inferior al que
previamente se esperaba.
Utilizan la denominada evolución primitiva, en la cual,
el proceso evolutivo consta tan sólo
de selección y
mutación. Encuentran que
di-
cha evolución primitiva supera con creces a una evolución basada exclusivamente
en
la
selección
y
el
cruce.
Otra
conclusión
de
su
trabajo
es
que
la
determinación
del valor óptimo de la probabilidad de mutación es mucho más crucial que el rela-
tivo a la probabilidad de cruce. Si bien en la
mayoría de las implementaciones
de
AG
se
asume
que
tanto
la
probabilidad
de
cruce
como
la
de
mutación
permane-
cen
constantes,
algunos
autores
han
obtenido
mejores
resultados
experimentales
modificando
la
probabilidad
de
mutación
a
medida
que
aumenta
el
número
de
iteraciones.
2.1.8.
Reemplazo de la Población y Condición de Parada
Cada
vez
que
se
aplica
el
operador
de
cruce,
nos
encontramos
con
un
número
de
nuevos
individuos
(la
descendencia)
que
se
han
de
integrar
en
la
población
para
formar la siguiente generación. Esta operación se puede hacer de diversas formas,
pero en general existen tres métodos fundamentales para realizar el reemplazo:
-
Cuando el número de individuos llega a un cierto número, se elimina un subcon-
junto de la población conteniendo a los individuos peor adaptados.
-
Cada
vez
que
se
crea
un
nuevo
individuo,
en
la
población
se
elimina
el
peor
adaptado para dejar su lugar a este nuevo individuo.
-
Cada
vez
que
se
crea
un
nuevo
individuo,
en
la
población
se
elimina
aleatoria-
mente una solución, independientemente de su adaptación.
En cuanto a el criterio de parada, generalmente viene determinado por criterios a
priori
sencillos,
como
un
número
máximo
de
generaciones
o
un
tiempo
máximo
de
resolución,
o
más
eficientemente
por
estrategias
relacionadas
con
indicadores
del estado de evolución de la población, como por la pérdida de diversidad dentro
de la población o
por no
haber
mejora en un cierto número
de iteraciones, siendo
por lo general una condición mixta lo más
utilizado, es decir, limitar el tiempo
de
ejecución
a
un
número
de
iteraciones
y
tener
en
cuenta
algún
indicador
del
esta-
do de la población para considerar la convergencia antes de alcanzar tal limitación.
El
problema
que
confrontan
los
AG
consiste
en
identificar
dentro
de
un
espacio
de hipótesis candidato, la
mejor, donde la mejor hipótesis es aquella que optimiza
una medida numérica predefinida para el problema, llamada adaptación ( f itness)
de
la
hipótesis.
Por
ejemplo,
si
la
tarea
de
aprendizaje
es
el
problema
de
aproxi-
mar
una
función
desconocida
dado
un
conjunto
de
entrenamiento
de
entradas
y
salidas,
la
adaptación
puede
definirse
como
la
precisión
de
la
hipótesis
sobre
el
conjunto
de entrenamiento (porcentaje de éxitos al
predecir la salida). Si la tarea
de
aprendizaje
tiene
la
forma
de
un
juego,
la
adaptación
puede
medirse
en
térmi-
nos
del
porcentaje
de
partidas
ganadas.
Aunque
los
detalles
de
implementación
varían
entre
diferentes
AG,
todo
comparten
en
general
la
siguiente
estructura:
El
algoritmo opera iterativamente, actualizando un conjunto de hipótesis llamada po-
blación.
En
cada
iteración,
todos
los
miembros
de
la
población
son
evaluados
de
acuerdo
a
una
función
de
adaptación.
Una
nueva
población
es
generada,
selec-
cionando probabilísticamente los individuos de
mayor adaptación en la población
presente.
Algunos
de
estos
individuos
pasan
intactos
a
la
siguiente
generación.
Otros son seleccionados para crear una
nueva generación, aplicando operaciones
genéticas como el cruce y la mutación.
El prototipo de un
AG simple se muestra a continuación:
——————————————————-
generación de la población inicial
while no se cumpla la condición de parada do
.
evaluación de los individuos
.
selección
.
cruce
.
mutación
end while
——————————————————-
Las
entradas
de
este
algoritmo
incluyen
una
función
de
adaptación
para
evaluar
los
candidatos
a
hipótesis,
un
umbral
definiendo
el
nivel
aceptado
de
adaptación
para dar por terminado el algoritmo, el tamaño que debe
mantener la población, y
los parámetros necesarios para determinar como evoluciona la población, esto es,
la
fracción
de
la
población
que
será
remplazada
en
cada
generación
y
la
tasa
de
mutación presente.
Observen
que
cada
iteración
de
este
algoritmo
produce
una
nueva
generación
de
hipótesis, con base en la población actual de hipótesis. Primero, un cierto número
de hipótesis en la población ((1 - r) × p) es seleccionado probabilísticamente para
su
inclusión
en
la
prole.
La
probabilidad
de
una
hipotesis
h
i
?
pob
de
ser
selec-
cionada esta dada por:
Por lo tanto, la probabilidad de que una hipótesis sea seleccionada es proporcional
a
su propio indice
de adaptación, e inversamente proporcional a la adaptación de
las hipótesis concurrentes en la misma población.
Una vez que estos miembros de la población son seleccionados para ser incluidos
en
la
generación,
el
resto
de
los
miembros
de
esta
se
genera
usando
el
operador
de cruce.
Este
operador,
selecciona
(r
×
p)/2
pares
de
hipótesis
en
la
población
y
genera
dos descendientes para cada par, combinando porciones de ambos padres. Los
padres son elegidos probabilísticamente con la
Fr
(h
i
)
definida como
hasta ahora.
En
este
momento,
la
generación
tiene
el
tamaño
de
población
deseado
p,
así
que
solo
resta
seleccionar
m
elementos
de
la
población
para
aplicar
la
operación
de
mutación.
Estos
elementos
son
elegidos
al
azar
y
los
cambios
efectuados
en
ellos
son también aleatorios.
Algunos
enfoques
de
AG
practican
un
elitismo
al
evitar
explícitamente
que
las
mejores hipótesis encontradas hasta ese momento, puedan
mutar.
Este
AG
lleva
a
cabo
una
búsqueda
por
barrido
(beam),
paralela
y
aleatoria
de
hipótesis que tienen un buen desempeño de acuerdo a la función de adaptación.
2.1.9.
Otros Operadores
Estos
operadores
no
son
utilizados
en
todos
los
problemas,
solamente
son
em-
pleados en algunos,
y
en
principio su variedad
es infinita.
Generalmente son ope-
radores
que
exploran
el
espacio
de
soluciones
de
una
forma
más
ordenada,
y
que
actúan
más
en
las
últimas
fases
de
la
búsqueda,
en
la
cuál
se
pasa
de
soluciones
çasi buenas.
a
"buenas"soluciones.
Cromosomas de Longitud Variable:
Hasta ahora se han descrito cromoso-
mas de longitud fija, donde se conoce de antemano el número de parámetros
de un problema. Pero hay problemas en los que esto no sucede. Por ejemplo,
en un problema de clasificación, donde dado un vector de entrada, queremos
agruparlo
en
una
serie
de
clases,
podemos
no
saber
siquiera
cuántas
clases
hay.
Por
ejemplo,
en
un
perceptrón
hay
reglas
que
dicen
cuantas
neuronas
se
deben
de
utilizar
en
la
capa
oculta;
pero
en
un
problema
determinado
puede que no haya ninguna regla heurística aplicable; se tendría que utilizar
los
AG
para hallar el número óptimo
de neuronas.
En estos casos, se necesitan operadores más: añadir y eliminar. Estos opera-
dores
se
utilizan
para
añadir
un
gen,
o
eliminar
un
gen
del
cromosoma.
La
forma
más
habitual
de
añadir
un
gen
es
duplicar
uno
ya
existente,
el
cuál
sufre
mutación
y
se
añade
al
lado
del
anterior.
En
este
caso,
los
operadores
del
AG
simple
(selección,
mutación,
cruce)
funcionarán
de
la
forma
habi-
tual,
salvo,
claro
está,
que
sólo
se
hará
cruce
en
la
zona
del
cromosoma
de
menor longitud.
Operadores
de
Nicho
(Ecológico):
Otros
operadores
importantes
son
los
operadores de nicho. Estos operadores están encaminados a mantener la
diversidad
genética
de
la
población,
de
forma
que
cromosomas
similares
Mister Wong
Portal para Investigadores y Profesionales
