Hoy hablaremos sobre cómo estas ideas de evolución
se pueden ver como cómputos y cómo podemos usarlos
para entender y tomar ventaja de las ideas evolutivas.
Revisemos primero los tres elementos básicos
de la evolución darwiniana
que acaban de aprender:
la variación aleatoria de los individuos,
la selección de algunos de estos individuos,
basado en el diferencial de la "aptitud",
y la herencia de esas variaciones
por parte de los individuos de la siguiente generación.
También necesitamos pensar un poco
acerca de cómo esas variaciones son representadas,
lo cual nos lleva al campo de la genética,
pero que no necesitamos conocer, solo necesitamos saber
que la información,
estas variaciones, están representadas
como unidades discretas que hoy llamamos genes.
Necesitamos saber que la representación
de la información de los genes está separada
de cómo se expresan estos en el fenotipo.
Nos referimos a esto como el mapeo del genotipo
versus el fenotipo.
Y lo último que necesitamos saber es
que estos genes están organizados en un arreglo lineal
que hoy llamamos cromosoma.
La comprensión de esto comenzó en realidad
con Mendel en 1865 y culmina
con el descubrimiento de la estructura del ADN
por Watson y Crick.
Entonces, tomaremos
esos elementos y conocimientos tan simples
y los convertiremos en un algoritmo.
La forma en que lo haremos
es que, en vez de tener cromosomas y genes,
tendremos una cadena de dígitos binarios
Los dígitos binarios son números
que son cero o uno, solo tienen dos valores,
y estas cadenas de dígitos binarios
serán nuestros individuos de la población.
Imaginen que comenzamos, y este está
hacia el extremo izquierdo del panel de la figura.
Imaginen que comenzamos con una población
de individuos generados aleatoriamente, o cadenas,
aquí solo se muestran tres
y cada una tiene 5 bits, pero que en el algoritmo
de la genética real tendríamos más bits
y poblaciones más grandes.
También necesitaremos una manera de evaluar la aptitud
y lo haremos usando la función de la aptitud.
En nuestro ejemplo, supondremos que la función de aptitud
tomará valores entre 0 y 1
y que el valor más alto, 1, es el mejor.
Entonces, el primer paso es generar una población inicial;
luego, necesitamos evaluar cada individuo
de la población a través de la función de aptitud
y usar los valores de la aptitud para seleccionar
la siguiente generación.
Se puede ver que en el panel del centro
donde hay dos copias del individuo
con un valor de aptitud más alto, donde no hay copias del individuo
con la aptitud más baja y hay una sola copia
del individuo con la aptitud promedio.
Esto no es muy interesante
porque estos individuos son exactamente iguales a sus padres.
Tomaremos ventaja de lo que se conoce
como operadores genéticos para introducir nuevas variaciones
mediante el uso de mutaciones que se muestran
en el individuo con mayor aptitud donde el primer bit, un uno,
cambia y toma el valor de cero,
esto no siempre pasa con la primera posición,
sucede aleatoriamente en diferentes posiciones
dentro de la cadena y entre las cadenas
de la población.
Luego, usaremos también un proceso llamado
entrecruzamiento, o recombinación,
donde se toman dos individuos e intercambiamos segmentos
de ADN, o segmentos de sus cadenas de bits,
lo cual se ve en los segundos dos individuos.
En el tercer panel, tenemos
la verdadera nueva generación, la Generación T+1.
Ahora, es necesario repetir el ciclo
y evaluarlos usando la función de aptitud,
hacer una nueva selección, introducir nuevas mutaciones
y entrecruzamiento y así es como
opera el proceso evolutivo.
Esta estrategia básica, y la idea básica del uso
de cadenas de bits para representar los cromosomas,
fue introducida por John Holland a inicios de los años de 1960.
John estaba muy interesado
en los efectos a nivel poblacional
y en el impacto del entrecruzamiento.
Regresemos al algoritmo...
¿Cómo será esto cuando ejecutemos este algoritmo
para múltiples generaciones?
En la diapositiva anterior, ya les mostré una generación,
pero normalmente iteramos esto por cientos
e, incluso, a veces, por miles de generaciones.
Y la forma de analizarlo es a través es del gráfico del tiempo
en términos de números de generaciones en el eje X
y la aptitud, generalmente la aptitud promedio
de la población o el valor más alto de la aptitud de la población,
los cuales se muestran
en el eje Y.
De modo que esta es la típica curva de comportamiento
que vemos en los algoritmos genéticos
donde la aptitud de la población
comienza en un punto inicial muy bajo,
aumenta muy rápidamente y mejora cuando
los individuos menos aptos son eliminados
y los más aptos son copiados,
de modo que la aptitud promedio aumenta.
Luego, se hace una búsqueda
para ver que hay otra innovación.
Pero, finalmente, la población se mantiene
en lo que denominamos una meseta.
Esto es lo que conocemos como equilibrio puntuado
y cuando eso sucede, el algoritmo
tiene que explorar de forma eficaz el espacio
para encontrar una innovación
con un valor alto de la aptitud, de manera que le puede tomar
diversas cantidades de tiempo. Podemos ver dos mesetas:
en la primera meseta que vemos en la figura,
se encontró finalmente otra innovación
y el valor de la aptitud de la población aumenta,
lo cual es muy característico
de estos algoritmos genéticos.
Ahora hablemos sobre algunas aplicaciones,
y cómo se usan.
Los algoritmos genéticos se han usado extensamente
en aplicaciones de ingeniería
y también en modelos científicos.
Primero, hablaremos de las aplicaciones en ingeniería.
La más común de estas aplicaciones
es la que conocemos
como optimización de funciones con múltiples parámetros
y que se muestra en la figura.
Es una función de dos dimensiones,
es decir, es una función de dos variables.
Pero, si una función es compleja, muchas veces
no contamos con métodos analíticos para hallar matemáticamente
el valor máximo de la función
y cuando eso sucede tenemos que recurrir al muestreo
y podemos considerar al algoritmo genético
como un tipo de algoritmo de muestreo sesgado.
El objetivo, por tanto, sería encontrar
los puntos que están situados en el tope del pico más alto
en esta superficie de múltiples picos.
Detallemos un poco más
cómo funciona.
Aquí hay un ejemplo de esta función
y no es fácil analizarla matemáticamente,
supongan que queremos hallar los valores de X y Y
para esta función que tiene
el máximo F(X,Y).
Para ello, extraemos cadenas de bits
y considerar conceptualmente a la primera mitad
de la cadena como una representación
del valor de X y a la segunda mitad de la cadena
como una representación del valor de Y.
Para evaluar la aptitud necesitamos
tomar estos ceros y estos unos y entenderlos
como números en Base 2 y pasarlos
a sus equivalentes decimales,
los cuales se muestran en la figura, y, luego tomar esos valores decimales
como sustitutos
en la función de aptitud y obtener, en este caso,
el valor de 4.
Entonces, tendríamos que hacer esto
para cada individuo de la población.
Quiero decir algunas palabras
acerca de dónde provienen estos algoritmos.
Yo mencioné a John Holland, pero hay otros
que estuvieron interesados en algoritmos
similares y los tres primeros grupos
que están en la lista, de manera independiente
hicieron descubrimientos de ideas similares y que se superponen
y, luego, a inicios de la década de los 90, vino John Koza
y sorpresivamente mostró
cómo podíamos usar los algoritmos genéticos
para que los programas informáticos evolucionen.
Estas dos corrientes de inventos
ahora están agrupadas y el campo se llama
computación evolutiva.
Es evidente, que ha habido
mucha recombinación
entre estos diferentes orígenes.