sustituyan
sólo
a
cromosomas
similares,
y
son
especialmente
útiles
en
pro-
blemas
con
muchas
soluciones;
un
AG
con
estos
operadores
es
capaz
de
hallar todos los
máximos, dedicándose cada especie a un máximo.
Más
que
operadores genéticos, son formas de enfocar la selección y la evaluación de
la población.
Uno
de
las
formas
de
llevar
esto
a
cabo
es
la
introducción
del
crowding
(apiñamiento). Otra forma es introducir una función de compartición o sha-
ring,
que
indica
cuán
similar
es
un
cromosoma
al
resto
de
la
población.
La
puntuación
de cada individuo se dividirá por esta función de compartición,
de
forma
que
se
facilita
la
diversidad
genética
y
la
aparición
de
individuos
diferentes.
También
se
pueden
restringir
los
emparejamientos,
por
ejemplo,
a
aquellos
cromosomas que sean similares. Para evitar las malas consecuencias del
inbreeding
(destinado
a
potenciar
ciertas
características
frente
a
otras)
que
suele
aparecer
en
poblaciones
pequeñas,
estos
periodos
se
intercalan
con
otros periodos en los cuáles el emparejamiento es libre.
Operadores Especializados:
En
una
serie
de
problemas
hay
que
restringir
las nuevas soluciones generadas por los operadores genéticos, pues no todas
las soluciones generadas van a ser válidas, sobre todo en los problemas con
restricciones.
Por
ello,
se
aplican
operadores
que
mantengan
la
estructura
del
problema.
Otros
operadores
son
simplemente
generadores
de
diversi-
dad, pero la generan de una forma determinada:
Zap:En vez de cambiar un solo bit de
un cromosoma, cambia un gen com-
pleto de un cromosoma.
Creep:Este
operador
aumenta
o
disminuye
en
1
el
valor
de
un
gen;
sirve
para cambiar suavemente y de forma controlada los valores de los genes.
Transposición:Similar
al
cruce
y
a
la
recombinación
genética
(Cuando
las
dos
células
sexuales,
o
gametos,
una
masculina
y
otra
femenina
se
combi-
nan,
los
cromosomas
de
cada
una
también
lo
hacen,
intercambiándose
ge-
nes, que a partir de ese momento pertenecerán a un cromosoma diferente.),
pero dentro de un solo cromosoma; dos genes intercambian sus valores, sin
afectar al resto del cromosoma. Similar a este es el operador de eliminación-
reinserción, en el que un gen cambia de posición con respecto a los demás.
2.1.10.
Aplicando Operadores Genéticos
En
toda
ejecución
de
un
AG
hay
que
decidir
con
qué
frecuencia
se
va
a
aplicar
cada uno de los
AG; en algunos casos, como en la mutación o el cruce uniforme,
se
debe
de
añadir
algún
parámetro
adicional,
que
indique
con
qué
frecuencia
se
va
a
aplicar
dentro
de
cada
gen
del
cromosoma.
La
frecuencia
de
aplicación
de
cada
operador
estará
en
función
del
problema;
teniendo
en
cuenta
los
efectos
de
cada
operador,
tendrá
que
aplicarse
con
cierta
frecuencia
o
no.
Generalmente,
la
mutación
y
otros
operadores
que
generen
diversidad
se
suelen
aplicar
con
poca
frecuencia; la recombinación se suele aplicar con frecuencia alta.
En
general,
la
frecuencia
de
los
operadores
no
varía
durante
la
ejecución
del
al-
goritmo,
pero
hay
que
tener
en
cuenta
que
cada
operador
es
más
efectivo
en
un
momento
de
la
ejecución.
Por
ejemplo,
al
principio,
los
más
eficaces
son
la
mu-
tación y la recombinación; posteriormente, cuando la población
ha convergido en
parte, la recombinación no es útil, pues se está trabajando con individuos bastante
similares, y es poca la información que se intercambia. Sin embargo, si se produce
un
estancamiento,
la
mutación
tampoco
es
útil,
pues
está
reduciendo
el
AG
a
una
búsqueda
aleatoria;
y
hay
que
aplicar
otros
operadores.
En
todo
caso,
se
pueden
usar operadores especializados.
Ejemplo simple de AG:
Se requiere calcular el máximo de una función f(x) en un intervalo [a,b]. Para esto
solamente
se
deriva
la
función
y
se
iguala
a
cero.
Pero
se
presenta
un
pequeño
inconveniente y es que no se conoce a f(x), aunque sí se puede calcular o estimar
su valor en cualquier punto.
He aquí los pasos a seguir:
Se
estiman
la
resolución
con
la
que
se
desea
trabajar.
Es
decir,
se
elige
el
número
de puntos
que se van a examinar
dentro
del intervalo. Si, por ejem-
plo, el intervalo es el [0,100] y se asigna una resolución de 0.5, entonces se
obtendrán 200 puntos en el intervalo.
Se genera
una población inicial
de n individuos; que serán n números (ele-
gidos al azar). Es decir, se obtiene a
x1, x2, ..., x
n
.
Todos ellos se encuentran
dentro del intervalo [a,b].
Ahora se le debe asignar mayor capacidad de reproducción a los mejor do-
tados. Si se esta buscando el
máximo, pues el
mejor dotado será aquel cuyo
valor
de f (x
i
)
sea
mayor.
De
los
n
individuos
que
se
tienen,
se
creara
una
Ejempo: Supongamos que n es igual a 4, y que, por ejemplo, se tiene:
f
(x
0
)
=
10
f(x1) = 40
f(x2) = 30
f(x3) = 20
Por lo tanto,
p(x
0
)
=
0,1
p(x1) = 0,4
p(x2) = 0,3
p(x3) = 0,2
y
también,
F(x
0
)
=
0,1
P(x1) = 0,5
P(x2) = 0,8
P(x3) = 1,0
Es claro que los
p(x
i
)
suman 1. A continuación se generan n números aleato-
rios entre 0 y 1.
Cada uno de esos números por ejemplo, t estará relacionado
con un individuo de la generación intermedia; de la siguiente forma:
si t está entre F(x
i
)
y
F(x
i+1
)
escogemos
x
i+1
.
Siguiendo con el ejemplo: Si los cuatro números aleatorios son 0.359, 0.188,
0.654 y 0.399, entonces la generación intermedia será:
Como se ve, está claro que, pese al azar el individuo mejor dotado es el más
favorecido.
El siguiente paso es la recombinación.
Se puede hacer de la forma
que pa-
rezca
más adecuada. En primer lugar hay que buscar las parejas. Se trata de
Número Aleatorio
Individuo Seleccionado
Nuevo Valor
0.1<0.359<0.5
0.1<0.188<0.5
0.5<0.654<0.8
0.1<0.399<0.5
x1
x1
x2
x1
x
0
x1
x2
x3
obtener
una
nueva
generación
como
mezcla
de
esta
con
la
que
se
esta
tra-
bajando.
Una
vez
que
se
tienen
las
parejas,
se
hace
la
recombinación.
Una
alternativa:
media
aritmética;
otra:
media
geométrica.
Otra,
la
más
usada:
cortar los dos números "papás"por un lugar al azar y conseguir los "hi-
jos"intercambiando partes.
Para
ejemplificar
mejor
veamos:
si
los
individuos
son
456
y
123,
se
elige
al
azar
un
número
entre
1
y
2
(ya
que
hay
tres
cifras).
Si,
por
ejemplo,
se
obtiene el 1, entonces un posible hijo podría ser el 4-23 y otro 1-56. Aunque
lo
más habitual es trabajar en base 2 (por lo menos, los números serán
más
largos).
En
este
momento
ya
se
tiene
una
nueva
generación.
Generalmente,
mejor
dotada que la inicial. Lo que se hace ahora es volver al tercer punto (cálculo
de
una
población intermedia).
Por
supuesto,
el algoritmo
se
para
cuando
se
considere prudente
o
necesario. Por ejemplo, cuando se lleve
un número
de
iteraciones determinado, o cuando la población no mejore demasiado.
Una
variante
posible
es
permitir
la
existencia
de
mutaciones
(por
ejemplo,
introducir
cada
cierto
número
de
generaciones
alguna
variación
en
una
ci-
fra
en
busca
de
mejores
soluciones.
Esto
es
interesante
debido
a
que,
por
ejemplo, si se están dando vueltas en torno a un
máximo local, la variación
introducida podría llevarnos hacia un genotipo
mejor dotado.
Otra
variante
es
la
elitista,
consistente
en
que
los
mejores
genotipos
no
se
recombinen,
sino
que
pasen
directamente
-tal
cual-
a
la
siguiente
genera-
ción.
Ejemplo:
Un
AG
puede
verse
como
un
método
de
optimización
general,
que
busca
en
un
gran espacio de candidatos, a los elementos que tienen mejor desempeño con res-
pecto a la función
de objetivo.
Aunque no garantizan encontrar el elemento opti-
mo, los
AG
generalmente tienen éxito en encontrar un elemento con alta adapta-
ción.
Para ilustrar el uso de los
AG en el aprendizaje de conceptos, se presentara breve-
mente
el
sistema
GABIL
que
usa
AG
para
aprender
conceptos
booleanos
repre-
sentados como un conjunto disyuntivo de reglas preposicionales.
Se
tomara
el
parámetro
r
=
0,6
que
determina
el
porcentaje
de
la
población
que
será
remplazada
por
cruce,.
El
parámetro
m
que
determina
la
tasa
de
mutación,
fue fijado en 0.001.
Estos son valores tipicos para ambos parámetros. El tamaño de la población vario
entre 100 y 1000, dependiendo de la tarea de aprendizaje específica en cada expe-
rimento.
Las
hipótesis
en
GABIL
se
representan
como
un
conjunto
disyuntivo
de
reglas
proposicionales,
solo
que
el
atributo
objetivo
es codificado
por
un
solo
bit.
Para representar el conjunto de reglas, las cadenas representando reglas individua-
les
son
concatenadas.
Por
ejemplo,
consideren
un
espacio
de
hipótesis
donde
las
pre-condiciones
de
las
reglas
son
conjunciones
restricciones
sobre
dos
atributos
a1 y
a2.
El
atributo
objetivo
es
c.
Entonces,
la
hipótesis
que
consta
de
estas
dos
reglas:
Si a1 = T
?
a2 =
F
Entonces c
=
T
;
Si a2 = T
Entonces c
=
F, se representa por
la cadena:
a1
a2
c
a1
a2
c
10
01
1
11
10
0
Observen que la longitud de la cadena de bits crece con el número de reglas en la
hipótesis. Esta longitud variable requiere una ligera modificación en la definición
de
operador
de
cruce.
El
operador
de
cruce
usado
por
GABIL
es
una
extensión
estándar del operador de cruce en dos puntos.
En
particular,
dada
la
longitud
variable
de
la
cadena
de
bits
representando
las
hi-
pótesis,
el
operador
de
corte
debe
estar
restringido
a
aplicarse
bajo
las
siguientes
condiciones:
Dos
padres
son
seleccionados,
luego
dos
puntos
de
cruce
son
elegi-
dos aleatoriamente sobre el primer
padre. Sea d1(d2) la distancia del punto
mas a
la
izquierda
(mas
a
la
derecha)
al
limite
de
la
regla
inmediatamente
a
la
izquier-
da.
Los
puntos
de
cruce
en
el
segundo
padre
se
fijan
ahora
aleatoriamente
con
la
restricción
de
que
deben
tener
los
mismos
valores
d1(d2).
Por
ejemplo,
si
los
dos
padres son:
a1
a2
c
a1
a2
c
h1 =
10
01
1
11
10
0
y:
a1
a2
c
a1
a2
c
h2 =
01
11
0
10
01
0
y
los puntos de cruce para el primer padre son los bits 1 y 8:
a1
a2
c
a1
a2
c
h1 =
1[0
01
1
11
1]0
0
entonces d1 = 1 y d2 = 3, por lo que los pares de puntos de cruce permitidos para
la hipótesis h2 son: <1, 3> , <1, 8> y <6, 8> . Si el par <1, 3> es elegido:
a1
a2
c
a1
a2
c h2 =
0[1 1]1
0
10
01
0
Por lo que la prole resultante de estas dos hipótesis es:
a1
a2
c
h3 =
11
10
0
y:
a1
a2
c
a1
a2
c
a1
a2
c
h
4
=
00
01
1
11
11
0
10
01
0
Como
se
puede
ver
en
el
ejemplo,
este
operador
de
cruce
permite
que
la
prole
contenga diferente número de reglas que sus padres,
y
al mismo tiempo
garantiza
que
todas
las
cadenas
de
bits
generadas
de
esta
forma,
representen
conjuntos
de
reglas bien definidos.
La
función
objetivo
para
cada
hipótesis
se
basa
en
su
precisión
como
clasificador
sobre
un
conjunto
de
ejemplos
de
entrenamiento.
En
particular,
la
función
usada
para
medir la adaptación es:
ada ptacion(h) = (correcto(h))²
donde
correcto(h)
es
el
porcentaje
de
ejemplos
bien
clasificados
por
la
hipótesis
h.
Mister Wong
Portal para Investigadores y Profesionales
