[Rello-99] AG-Introduccion_ metodos de busqueda y optimizacion

Vista previa del material en texto

Perspectiva
E
n los últimos años el gran interés por la
Computación Natural (Soft Computing),
ha hecho que la misma sea aplicada a
multitud de problemas reales tales como:
reconocimiento automático, control inteligente,
aprendizaje en sistemas complejos, etc.
La Computación Natural se caracteriza por uti-
lizar las técnicas que emplean los seres vivos para
evolucionar en la Naturaleza. Dentro de esta
tecnología se engloban las Redes Neuronales que
emulan la estructura del cerebro, los Sistemas
Borrosos que simulan la forma de razonar del ser
humano, los Algoritmos Genéticos basados en la
Teoría de la Evolución para encontrar solucio-
nes óptimas, etc.
En el presente artículo se pretende dar una
idea básica de qué son los Algoritmos Genéti-
cos, para qué se utilizan, cómo y porqué fun-
cionan. Al final del artículo se expondrá un
ejemplo práctico para ver su funcionamiento y
se incluirá un apartado final con todas las refe-
rencias a la bibliografía utilizada. Esta biblio-
grafía puede ser de gran ayuda para aquellas per-
sonas que estén interesadas en profundizar más
en el tema.
LOS ALGORITMOS GENÉTICOS
Los Algoritmos Genéticos, es una herramienta
matemática que se utiliza para resolver proble-
mas asociados a la optimización y a la búsque-
da de soluciones óptimas. Estos algoritmos se
basan en la Teoría de la Evolución de los seres
vivos en la Naturaleza.
En los Algoritmos Genéticos, se parte de un con-
junto de posibles soluciones para un problema
dado, al que se le denomina población, y a cada
una de las posibles soluciones se les llama indi-
viduos. Por medio de una serie de operadores lla-
mados Operadores Genéticos, los individuos de
la población inicial, van evolucionando en cada
generación a poblaciones mejores, de tal forma
que en un instante dado de la evolución, podrá
existir un individuo de la población que sea la
solución óptima al problema dado.
Los Operadores Genéticos que se aplican
sobre las poblaciones, para que éstas vayan evo-
lucionando a lo largo del tiempo son de lo más
variados (reproducción, cruce, mutación, vecin-
dad, creación de nichos y especies, diferencia-
ción sexual, dominación, etc.). Para simplificar
la explicación de los Algoritmos Genéticos, en
este artículo se van a explicar la reproducción,
el cruce y la mutación, por ser los tres operado-
res genéticos básicos.
LOS INDIVIDUOS
La representación de cada individuo dentro de
una población, se realiza por medio de una
cadena de bits de longitud fija L (bit1 bit2 bit3 ...
bitL). Estos individuos pueden estar formados por
un único gen o por varios. A continuación se
explica qué es un gen y otros conceptos común-
Algoritmos genéticos
Introducción, métodos de búsqueda 
y optimización
TRATAMIENTO DE SEÑAL. La resolución de problemas de búsqueda y optimización en sistemas
complejos, mediante los métodos matemáticos tradicionales, es en muchas ocasiones inabordable.
En este artículo se realiza una introducción a los Algoritmos Genéticos, métodos de búsqueda y
optimización masivamente paralelos, que en sistemas complejos obtienen resultados asombrosos.
RAÚL MARTÍN RELLO
DPTO. ELECTRÓNICA I+D, ORBIS TECNOLOGÍA ELÉCTRICA. raul.martin@orbis.es
Figura 1. Estructura básica de un 
Algoritmo Genético
Perspectiva
mente utilizados en los algoritmos genéticos:
Gen. Es cada parámetro que caracteriza a un
individuo, y por ello los genes que formen un
individuo establecerán el comportamiento del
mismo. El número de genes dentro de un indi-
viduo es variable y depende de la aplicación.
Cada gen dentro de un individuo se representa
por uno o más bits consecutivos.
Genoma. Son todos los parámetros, o genes
diferentes, que caracterizan a todos los indivi-
duos de una población.
Genotipo. Es la información genética que des-
cribe a un individuo específico, es decir, los genes
que posee.
Fenotipo. Es la expresión del genotipo, es
decir, una cadena de números binarios.
ESTRUCTURA DE LOS ALGORITMOS
GENÉTICOS
En un algoritmo genético se parte de una
población de m posibles soluciones a un proble-
ma dado (m individuos). Sobre esta población
inicial (P0) se realizan diferentes procesos que
son los siguientes:
Selección. En este proceso se eligen n indivi-
duos de la población inicial P0 que van a pasar a
la siguiente generación, generalmente n≤m. Estos
n individuos forman la población intermedia Pi.
De estos n individuos se vuelven a seleccionar p
individuos (p≤n), que serán utilizados como
progenitores y utilizarán la reproducción para
generar descendientes.
Reproducción. En este proceso, los p individuos
de la población intermedia Pi se juntan en parejas
y generan q descendientes. Ahora la población
intermedia Pi está formada por n+q individuos.
Reemplazo. En este proceso, de los n+q indi-
viduos de la población intermedia Pi, se eligen n
individuos, generalmente los más aptos, que
son los que formarán la siguiente población.
Estos procesos se irán ejecutando cíclicamen-
te, generación tras generación, hasta que uno de
los individuos de la población sea lo suficiente-
mente apto como para ser considerado solución
óptima.
Para evaluar la aptitud de cada individuo den-
tro de una población es necesario utilizar una fun-
ción de aptitud Fitness(w) que se obtiene a par-
tir de una función de evaluación Eval(w). Nor-
malmente la función de aptitud se obtiene tras
realizar un escalado y un desplazamiento a la fun-
ción de evaluación, aunque a veces ambas fun-
ciones pueden coincidir.
El algoritmo que representa el funcionamiento
de los algoritmos genéticos es el siguiente:
1º. Se crea una población inicial de m indivi-
duos.
2º. El valor de cada individuo se escoge de for-
ma aleatoria.
3º. Se evalúa cada uno de los individuos sobre
la función de evaluación.
4º. Se seleccionan n individuos para formar la
población intermedia.
5º. Se aplica el cruce a los p individuos proge-
nitores.
6º. Se aplica la mutación a la nueva población.
7º. Se sustituyen los individuos de la población
inicial por los nuevos.
8º. Si se cumple la condición de parada, se eli-
ge el individuo más apto, si no se vuelve al 3º
punto.
LOS OPERADORES GENÉTICOS
En los algoritmos genéticos hay una amplia
gama de operadores genéticos. En este artículo
se van a describir los operadores Reproducción,
Cruce y Mutación, ya que son los operadores
básicos de todo algoritmo genético. Estos ope-
radores se utilizan para hacer evolucionar a los
individuos de tal forma que vayan sobrevivien-
do los mejores.
Reproducción
Con este operador se seleccionan n individuos
de la población inicial P0 de m individuos. Para
seleccionar qué individuos deben pasar a la
población intermedia se pueden utilizar diferen-
tes mecanismos:
Selección directa. De entre los m individuos de
la población inicial, se escogen los n individuos
con mayor aptitud.
Selección aleatoria. De entre los m individuos
iniciales se eligen n individuos de forma aleato-
ria.
Selección estocástica. A cada individuo de la
población inicial se le asigna una probabilidad
p de ser seleccionado en función de su aptitud
respecto de la aptitud de toda la población. De
esta forma para el individuo i (wi), cuya apti-
tud es ui, la probabilidad de ser seleccionado
es:
donde uT es la suma de las aptitudes de todos
los individuos de la población.
Cruce
Gracias a este operador genético, es posible
combinar parejas de individuos de la población
inicial P0 para crear descendientes cuyo fenoti-
po sea una mezcla de los progenitores. Supon-
gamos los dos individuos w1 y w2 de la pobla-
ción inicial, cuya longitud es de 11 bits:
w1 = 1 0 0 1 1 0 1 1 1 0 0
w2 = 0 1 1 0 1 1 1 0 0 0 0
P
u
ui
i
T
=
ALGORITMOS GENÉTICOS
Perspectiva
Para realizar el cruce de estos dos individuos
es necesario establecer un punto de cruce.
Generalmente este punto se elige de forma ale-
atoria y estará acotado entre 1 y el número de bits
de los individuos. Supongamos que se ha obte-
nido un punto de cruce igual a 4.
w1 = 1 0 0 1 | 1 0 1 1 1 0 0
w2 = 0 1 1 0 | 1 1 1 0 0 0 0
Puntode cruce
Al cruzar dos individuos se obtienen dos des-
cendientes: el primero, d1, está formado por los
bits del progenitor 1 anteriores al cruce y por
los bits del progenitor 2 posteriores al cruce. En
el ejemplo que se está tratando, el descendiente
d1 tendría el siguiente fenotipo:
d1 = 1 0 0 1 1 1 1 0 0 0 0
El segundo descendiente d2, está formado por
los bits anteriores al cruce del progenitor 2 y
por los bits posteriores al cruce del progenitor
1:
d2 = 0 1 1 0 1 0 1 1 1 0 0
Con este operador genético se pretende que los
descendientes hereden las mejores característi-
cas de sus progenitores, además de permitir man-
tener la diversidad de individuos en sucesivas
poblaciones. Lo más usual es utilizar cruces
monopunto, como en este ejemplo, aunque en
ocasiones es interesante utilizar cruces multi-
punto.
Cuando se tiene la población intermedia Pi for-
mada por n individuos hay que seleccionar p indi-
viduos que serán los progenitores para crear
descendencia. La probabilidad de que un indivi-
duo de la población intermedia Pi forme parte del
conjunto de los p progenitores es el parámetro
llamado Probabilidad de Cruce (Pcruce) y su valor
está dado en tanto por ciento. Los valores típi-
cos suelen ser 20%, 30%, 50%, etc.
Mutación
En la Naturaleza, los seres vivos han ido sufrien-
do mutaciones para adaptarse al medio; estas
mutaciones se han ido produciendo muy lenta-
mente a lo largo de millones de años. El opera-
dor genético Mutación trata de representar este
hecho. A continuación se explica cómo se apli-
ca sobre una población de individuos.
Tenemos una población intermedia Pi de n+q
individuos después de haber generado la des-
cendencia. Estos individuos se representan por
cadenas binarias de longitud L, razón por la que
el número de bits totales de la población es de
(n+q)* L. Cualquiera de estos bits puede sufrir
el efecto del operador mutación con la misma
probabilidad.
La probabilidad de que un bit de la población
sea mutado es el parámetro conocido como Pro-
babilidad de Mutación (Pmut). Los valores típi-
cos son 1%, 0,5%, 0,1%, etc.
Este operador genético se utiliza para desesta-
bilizar a individuos estancados en un óptimo local
(y no global) y que puedan seguir evolucionan-
do hacia otras posibles soluciones más óptimas.
Estas alteraciones en el fenotipo de los indivi-
duos debe ser muy leve para que el objetivo
final no se pierda, ya que un uso excesivo de
este operador podría desestabilizar la evolución
de los individuos hacia soluciones óptimas y
por lo tanto nunca encontrar la solución al pro-
blema.
Un ejemplo de aplicación de este operador es
el siguiente:
Supongamos una población de 2 individuos w1
y w2 vistos anteriormente. Como su longitud es
de 11 bits, el número total de bits de esta pobla-
ción es de 22.
Bits totales =1001101110001101110000
Supongamos también que la probabilidad de
mutación de cada bit es del 1%. Por cada uno de
los bits se genera un número aleatorio r. La pro-
babilidad de mutación del bit i expresada en
tanto por uno es Pmut(i) = 0,01; si se cumple la
condición ri<Pmut(i), entonces el bit i será muta-
do, si no se mantendrá intacto.
Tras evolucionar la población inicial varias
generaciones es posible que ningún bit sea
mutado o que algunos pocos lo hayan hecho, ya
que este operador depende aleatoriamente de ri.
Si suponemos que r12 <Pmut(12), el bit a mutar
será:
Bits totales =10011011100 0 1101110000 y por
lo tanto la nueva población será:
Bits totales =10011011100 1 1101110000
CÓMO Y POR QUÉ FUNCIONAN
Para explicar cómo y porqué funciona un algo-
ritmo genético es necesario introducir un con-
cepto básico, el esquema, ya que los esquemas
representan el grado de parecido o similitud entre
los individuos de una misma población.
Para representar un esquema, es necesario
emplear el signo de indiferencia “*” en la cade-
na de bits de los individuos. Así por ejemplo, para
una población cuyos individuos tienen cadenas
binarias de longitud 3, el esquema (***) repre-
sentaría a todos los individuos de la población.
De igual forma el esquema (10*) representaría al
individuo (100) y al individuo (101).
ALGORITMOS GENÉTICOS
Perspectiva
Lo que procesa realmente
un algoritmo genético son
los esquemas. De esta mane-
ra al evolucionar la pobla-
ción inicial, generación tras
generación, los esquemas
más aptos irán sobrevivien-
do mientras que los esque-
mas menos aptos irán desa-
pareciendo.
Al hablar de esquemas es
importante saber cuál es el orden de un esque-
ma o(S) y cuál es su longitud característica
l(S), ya que dependiendo de ambos parámetros
se puede predecir qué esquemas serán los más
aptos.
Orden de un esquema. El orden de un esquema
es el número de bits distintos de “*” dentro de
una cadena binaria. Por ejemplo, el esquema
(**10*0*) tiene orden 3.
Longitud característica. La longitud caracte-
rística de un esquema es la máxima distancia
medida en número de bits entre las posiciones
fijas ( bits a 1 o a 0) de los dos extremos. Por
ejemplo, en el esquema anterior (**10*0*), la
distancia característica es 4.
En los algoritmos genéticos se puede deducir
matemáticamente (ver [1]), que los esquemas
más aptos son aquellos que presentan bajo orden
y corta longitud característica, ya que al aplicar
sobre ellos los operadores de cruce y mutación
es más difícil destruirlos.
UN EJEMPLO DE OPTIMIZACIÓN
Para ver cómo funciona un algoritmo genético
se ha pensado en el problema del viajante, cuyo
enunciado de optimización es el siguiente:
“Una persona debe recorrer varias ciudades dis-
tintas, con la condición de que debe pasar sola-
mente una vez por cada una de ellas y volver a
la ciudad de origen, recorriendo la menor dis-
tancia posible.”
En este ejemplo se han considerado 4 ciudades
(ver figura 2); para saber a priori cuál es la solu-
ción correcta y comprobar que el algoritmo gené-
tico funciona, se han situado en los vértices de
un cuadrado de lado 1.
El viajante parte inicialmente de la ciudad A y
puede ir hacia cualquiera de las restantes ciuda-
des. En la figura 3 se muestran todas las posi-
bles combinaciones que puede realizar el via-
jante.
Como puede verse en la figura 3, las solucio-
nes óptimas son la 1ª y la 2ª pues en ambas se
recorren todas las ciudades una vez con la
menor distancia.
Para resolver este problema con un algoritmo
genético, lo primero que se debe realizar es la
codificación de los individuos. En este caso se
ha optado por codificar la existencia de tramos
recorridos; es decir, si todos los tramos posibles
son 6: AB, BC, CD, DA, AC y BD, los indivi-
duos pueden representarse como cadenas bina-
rias de 6 bits (tabla 1).
El primer bit (bit 5), se corresponderá con el tra-
mo AB, el segundo con BC, y así hasta el últi-
mo que coincidirá con BD. Si un bit tiene valor
1, significa que ese tramo se recorre, mientras
que si el bit vale 0, significa que ese tramo no se
recorre. Por ejemplo, un individuo que represente
el recorrido 1 o el recorrido 2 de la figura 3,
tendría la cadena (111100), pues recorre los tra-
mos AB, BC, CD, DA y no recorre los tramos
AC y BD.
Hay que tener en cuenta que puede haber indi-
viduos que representen soluciones incorrectas.
Por ejemplo, (111000) nunca vuelve al origen
(ver figura 4a), o el individuo (111110) pasa
dos veces por una misma ciudad (figura 4b).
Estos individuos tendrán menos posibilidades
de evolucionar a siguientes generaciones.
Para ver cómo evoluciona la población es
necesario definir una función de evaluación; la
función que se ha elegido debe cumplir las
siguientes condiciones:
*El número de tramos recorridos debe ser
igual a 4. Por esta razón habrá que maximizar la
ecuación:
Fitness w
C b
C
i
i
i L
( )1
0
1
1= −
− ∑
=
= −
ALGORITMOS GENÉTICOS
Figura 2. Situación de las cuatro ciudades
Figura 3. Posibles recorridos a realizar 
Individuo Tramo AB Tramo BC Tramo CD Tramo DA Tramo AC Tramo BD
wi Bit5 Bit4 Bit3 Bit2 Bit1 Bit0
Tabla 1
Perspectiva
donde C es el número de ciudades, L es la lon-
gitud de la cadena de bitsy bi es el bit i-ésimo
de la cadena de bits.
De esta forma los individuos que recorran
sólo cuatro tramos obtendrán el valor máximo
de la función de evaluación, es decir, Fitness(w)1
= 1.
*La distancia recorrida debe ser mínima. En este
caso la ecuación a minimizar es:
donde Ti es la distancia del tramo i, para i = 5 es
la distancia del tramo AB y para i = 0 es la dis-
tancia del tramo BD.
Para que ambas condiciones se cumplan, se ha
optado por satisfacer de forma global la ecuación
siguiente:
Esta ecuación representa la aptitud de cada indi-
viduo. En ella puede verse que la aptitud depen-
de 10 veces más de la primera condición que de
la segunda; esto es así porque es indispensable
que se recorran sólo 4 tramos, mientras que la
segunda condición da idea de qué individuo es
el mejor dentro de los seleccionados como váli-
dos con la primera opción.
Además de estas condiciones es necesario
decidir cuando se ha encontrado la solución ópti-
ma. En este ejemplo se ha supuesto que un indi-
viduo es la solución óptima si durante cinco gene-
raciones (ciclos de evolución) su aptitud es la
mayor de la población y además no cambia.
Para realizar la demostración de este ejemplo
se ha utilizado un algoritmo genético simple
con 6 individuos iniciales elegidos de forma
aleatoria. La probabilidad de cruce Pcruce es del
40% y la probabilidad de mutación Pmut es del
1%. La selección de los individuos se realiza
por selección estocástica (dependiente de la apti-
tud relativa) y el cruce será monopunto. En la
tabla 2 se representan estos parámetros:
Código.- Valor del individuo. Es una cadena
binaria de 6 bits.
Fitness(w).- Valor devuelto por la función de
aptitud al aplicar sobre ella el individuo w.
Aptt(w).- Aptitud del individuo w respecto del
resto de individuos.
ApttAcc(w).- Aptitud acumulada de w. Distri-
buye probabilísticamente los individuos para rea-
lizar la selección en función de su aptitud
(selección estocástica).
FitTOT.- Es la aptitud total de la población
actual.
FitTOT = 0,7+0,7+0,935+0,9292+0,935+
0,6646= 4,8638
Así se han calculado los parámetros del tercer
individuo:
Fitness(w3)= 1- 0,1((1+1+1+0+√2+0)/6,8284)=
0,935
Appt(w3) = Fitness(w3)/FitTOT = 0,935/4,8638
= 0,1922
El cálculo de ApptAcc para el individuo wi es
la suma de las aptitudes de los individuos ante-
riores a él y la aptitud de él mismo:
Así:
ApttAcc(w3) = Aptt(w3)+Aptt(w2)+Aptt(w1) =
0,1439+0,1439+0,1922 = 0,48
Ahora se realiza el proceso de selección, para
lo cual es necesario generar tantos números ale-
atorios como individuos tiene la población. En
este caso hay que generar 6 números. Estos han
sido los que se han obtenido (tabla 3).
ApptAcc w Appt wi t
t
t i
( ) ( )= ∑
=
=
1
donde t =1,2,...., i
Fitness w Fitness w Fitness w( ) ( ) . * ( )= −1 20 1
Fitness w
b T
b
i i
i
i L
i
i L( )2
0
1
1
0
1=
∑
∑
=
= −
=
= −
ALGORITMOS GENÉTICOS
Figura 4. Recorrido y codificación
Individuos Fitness (x) Aptt (x) ApttAcc(x)
(Código: 6 bits)
010110 0.70 0.1439 0.1439
001101 0.70 0.1439 0.2878
111010 0.935 0.1922 0.48
001111 0.9292 0.1910 0.671
101110 0.935 0.1922 0.8632
101111 0.6646 0.366 1
Tabla 2
Número aleatorio
r1 = 0.2015
r2 = 0.0145
r3 = 0.7589
r4 = 01987
r5 = 0.6914
r6 = 0.9156
Tabla 3
Población Intermedia
w1 = 001101
w2 = 010110
w3 = 101110
w4 = 001101
w5 = 101110
w6 = 101111
Tabla 4
Perspectiva
El primer número aleatorio r1 (0,2015) hace
que se seleccione el 2º individuo ya que se
cumple:
ApptAcc(w1) < r1 < ApptAcc(w2)
De igual forma, los siguientes números alea-
torios hacen que se seleccionen w1, w5, w2, w5
y w6. La aleatoriedad del proceso hace que
pueda seleccionarse un mismo individuo varias
veces.
En este momento la población intermedia obte-
nida es la que se muestra en la tabla 4.
De entre estos individuos deben elegirse
aquellos que serán los reproductores, para lo que
se vuelve a generar un número aleatorio por cada
individuo. Si el número generado es menor que
la probabilidad de cruce expresada en tanto por
uno, en este caso 0,4, el individuo será selec-
cionado como reproductor. Estos son los
números aleatorios obtenidos (tabla 5).
Como se puede comprobar los individuos w2
y w3 son los reproductores pues r2 y r3 son
menores de 0,4. Para establecer el punto de
cruce se debe generar otro número aleatorio.
Este número estará acotado entre 1 y el núme-
ro de bits de las cadenas, en este caso 6. El
número generado es el 3, y los descendientes
obtenidos w7 y w8 son:
w7 = 101010
w8 = 111101
Ahora la población intermedia cuenta con 8
individuos. En este punto es necesario aplicar
el operador Mutación, para lo que se generará
un número aleatorio por cada uno de los bits
de la población (hay 8 individuos con 6 bits cada
uno = 48 bits totales). Si el valor del número
aleatorio es menor que la probabilidad de muta-
ción expresada en tanto por uno (en este caso
0,01), el bit será mutado. Se ha llevado a cabo
este proceso y no ha resultado mutado ningún
bit.
Una vez aplicados todos los operadores gené-
ticos hay que sustituir los 6 individuos de la
población inicial por otros 6 individuos de los
8 que hay en la población intermedia. Para rea-
lizar este reemplazo se ha optado por elegir de
forma directa todos aquellos individuos que sólo
recorren 4 tramos. En este caso la nueva pobla-
ción es la que se muestra en la tabla 6.
w6 = 101010
Para comprobar que esta población es más apta
que la inicial se vuelven a calcular los paráme-
tros de aptitud (tabla 7):
FitTOT = 5,5936
Y se llega a la conclusión de que esta genera-
ción es más apta que la anterior puesto que el
valor de FitTOT actual (5,5936) es mayor que
el inicial (4,8638).
Si se deja evolucionar esta población durante
15 ciclos más, se llega a la condición de para-
da ya que el individuo w3 tiene una cadena
(111100) constante durante 5 ciclos seguidos.
CONCLUSIONES
El ejemplo que se ha planteado es un ejemplo
sencillo cuya solución óptima se obtiene ins-
tantáneamente, pero si en vez de ser 4 ciudades
fueran 20 ó 30, entonces el problema no sería
nada sencillo.
Como se ha visto en este ejemplo y a lo largo
del artículo, los algoritmos genéticos son una
buena herramienta de búsqueda y optimización
en problemas complejos donde los métodos de
cálculo tradicionales no son viables. Se ha
demostrado empíricamente que cualquier pro-
blema que pueda resolverse con alguno de los
métodos matemáticos tradicionales siempre ten-
drá un mejor resultado que si se utiliza un algo-
ritmo genético. Por esta razón estos algoritmos
son una herramienta complementaria a las ya
existentes y no una herramienta sustitutoria de
las mismas.
REFERENCIAS
[1]. http://library.thinkquest.org/18242/ga_math.shtml
[2] . www.geocities.com/SiliconValley/Vista/7491
/mapa.htm
[3]. http://po1.pep.ufrj.br/~jfbarros/agbibli.html
[4]. www.wi.leidenuniv.nl/~gusz/Flying_Circus/
1.Reading/2.Tutorial/apprefs/apprefs.html
[5]. Gregory J. E. Rawlins; “Foundation of Genetic
Algorithms”, Morgan Kauffmann Publishers Inc.
1991
[6]. B. Martín del Brio, A. Sanz Molina; “Redes
Neuronales y Sistemas Borrosos”, Ra-ma 1997
[7]. I. Olmeda, S. Barba-Romero; “Redes Neurona-
les Artificiales”, Universidad de Alcalá 1993.
[8]. D. E. Goldberg; “Genetic Algorithms in Search,
Optimizations and Machine Learning”, Addison-Wes-
ley 1989 ME
ALGORITMOS GENÉTICOS
Individuos Fitness (x) Aptt (x) ApttAcc(x)
(Código: 6 bits)
010111 0.9292 0.1661 0.1661
101101 0.9353 0.1672 0.333
001111 0.9292 0.1661 0.4994
101110 0.9353 0.1672 0.666
101111 0.9146 0.1635 0.8301
101010 0.9500 0.1698 1
Tabla 7
Número aleatorio
R1 = 0.519
R2 = 0.249
R3 = 0.041
R4 = 0.783
R5 = 0.879
R6 = 0.426
Tabla 5
Nueva población 
w1 = 010111
w2 = 101101
w3 = 001111
w4 = 101110
w5 = 101111
w6 = 101010
Tabla 6