Algoritmos Genéticos Cap 1

 

Computación evolucionaria se encarga aplicar las características de la evolución para encontrar soluciones óptimas a problemas. 
-Búsqueda exhaustiva: se examinan todas las posibles soluciones.

4 paradigmas bases:
            -Algoritmos genéticos, Holland 1975
            -Programación genética, Koza 1992 1994
            -Estrategias evolucionarias Recheuberg 1973
            -Programación evolucionaria Forgel et al 1966

 

Algoritmos genéticos:

La más popular. Usa un string de bits de tamaño fijo, cada posición es una característica del individuo y su valor es como se expresa en la solución. Tienen poca o nula interacción entre ellos. 

-El mayor operador de reproducción es el "bit-string crossover" o cruce de string de bits. Dos strings son usados como padres y tienen strings hijos haciendo combinaciones entre los padres. 
-Otro es mutación por cambio de bits. Donde un bit es cambiado para formar uno nuevo. 
-Otra menos usada es inversión. La secuencia de bits es invertida.

Es importante ver si los operadores introducen nueva información en la población, cosa que mutación hace pero el cruce no. Y los operadores tienen que producir cambios válidos en las restricciones de genes.

 

Programación genética:

En un programa genético, la representación usada es un árbol de funciones y valores. Cada hoja es una etiqueta de un conjunto de etiquetas funciones disponible. 
El árbol completo es una sola función que será evaluada. Es evaluada por profundidad desde la parte de más a la izquierda. Una función es evaluada usando argumentos que son el resultado de evaluar a los hijos.

-El operador más usado es el cruce de árboles. Un subárbol entero es cambiado entre dos padres.

Todas las funciones y valores deben retornar el mismo tipo, pero los argumentos pueden variar en cantidad.

Este principio de cierre (Koza 1994) permite a cualquier subárbol ser considerado a la par con cualquier otro, y que los operadores generarán descendencia permitida.  

 

Estrategias evolucionarias:

Se usa un vector de tamaño fijo con valores reales. Cada posición del vector corresponde a una característica del individuo. Pero son características mas de comportamiento que de estructura. 

-El operador principal es la mutación Gaussiana. Donde un valor aleatorio de la distribución de Gauss es agregada a cada elemento del vector de un individuo para crear descendencia.
-Otro operador es recombinación intermedia. Donde los elementos de dos vectores padres son promediados elemento por elemento para generar descendencia. 

 

Programación evolucionaria:

Idea de fenotipo y de responder a estímulos y desarrollar operadores para afectar cambios de comportamiento y estructura. Para problemas de predicción, optimización y machine learning.

Su representación es adaptada al dominio del problema. Una común es vector de tamaño fijo con valores reales. La diferencia de las demás es que no hay intercambio de material entre los individuos. Sólo se permite mutar. 

Una operación común es agarrar N padres, mutarlos para hacer N descendencia y seleccionar probabilísticamente por fitness solo N de los 2N que tendríamos. 

 

 

Características de la computación evolucionaria:

 Esquema de representación: lo que elige el investigador como conjunto de soluciones para el algoritmo.
Un número de soluciones es creada para ser población inicial. Luego se itera repetidamente hasta encontrar una solución que satisfaga el criterio de termino. Cada individuo se evalúa usando una función de fitness para el problema específico. Basados en su fitness se eligen individuos que serán padres, que generarán descendencia basados en operadores de reproducción. Se crean nuevas generaciones con supervivientes y descendencia.

El método de selección es el que determina cuántos padres habrán el operador, quienes sobreviven, etc. Estos generalmente se aseguran que la población de cada generación sea igual en cantidad.

 

Características fundamentales de la evolución biológica:

1. genes de partículas y genética de la población. Preguntar si el estado del EC tiene lo básico de evolución biológica.
2. el código genético adaptativo. Demuestra que ambas evoluciones (EC y biológica) pueden contribuir para entender las abstracciones evolutivas
3. la dicotomía del genotipo y fenotipo. Ilustra la pregunta de BE que EC se ve mejor ajustada que la biología.

 

Genes de partículas y genética de la población:

Fenotipo: líquido que se mezcla cuando hombre y mujer se reproducen. 

Primer profesor de ingeniería: Fleming Jenkin 1867. Teoría de Mendel de los genes de partículas, donde el alelo de un gen está presente o no, y la herencia biparental produce diploidía.

La selección natural altera las proporciones de alelos, una mutación ventajosa puede ser seleccionada sin perder fitness. 

Introduce estocasticidad a la evolución. Los genes están o no en el genoma, es probabilístico qué alelos se heredan de los padres.

Deriva genética, error de muestreo. La magnitud de esta es inversamente proporcional al tamaño de la población. 

 

Libro de código adaptativo:

ADN -> ARN -> proteína.

ADN y ARN formados de nucleótidos (4 letras). Proteína de amino ácidos (20 letras).
         -Transcripción: complementar el ADN para crear ARN.
         -Translación: 

Redundancia en el código agrega selectividad neutral al ambiente de fitness que mejora la conexión de óptima local.

Un código de minimización de error maximiza la probabilidad de que efectos aleatorios sucedan en un organismo. Esta probabilidad es inversamente proporcional a su magnitud. La mutación aumenta la 
probabilidad de fitness según "La teoría geométrica del gradualismo".

 

Dicotomía del genotipo y fenotipo:

ARN funciona como medio de almacenamiento genético y como molécula catalítica. 

El tamaño del alfabeto de aminoácidos desencadenó una gran diversidad catalítica de replicadores.

 

Ventajas de EC:

Da ventajas a problemas de optimización. Por su simplicidad, robustez ante cambio de circunstancias, flexibilidad, etc.

 

Simplicidad conceptual:

Es simple en conceptos. Se hace:

1. Inicializa la población.
2. Varía los individuos aleatoriamente.
3.Evalúa su fitness.
4. Aplica selección.
Lo realiza de nuevo del 2 al 4.

Su efectividad depende de la variación y selección sobre una representación e inicialización.

 

Amplia aplicabilidad:

Se aplica a cualquier problema  que se puede formular como problema con función de optimización.

Se seleccionan las representaciones basadas en intuición humana. Deben permitir a los operadores de variación mantener una conexión de comportamiento entre padres e hijos. 

Cambios pequeños en padres crearán cambios pequeños en hijos y grandes en grandes. Son adaptativos:

Al ser amplios se usan en: problemas de combinatoria discreta, de enteros mezclados, etc.

 

Híbridos con otros métodos:

Se pueden combinar con otros métodos de optimización. 

 

Paralelismo:

Se puede hacer evaluación y selección en paralelo. 

 

Robusto a cambios dinámicos:

Se adaptan a cambios, sin necesidad de reiniciar o rediseñar. Se adaptan a circunstancias que cambian. Por ejemplo: carro con dos postes

 

Resuelve problemas sin solución:

Resuelve problemas que el humano no puede. Usados cuando un humano no tiene acceso a la solución de un problema (automatización, velocidad computacional). 
Pueden resolver problemas, pero no el problema de como resolver problemas. (EC provee el método para esto).

 

Aplicaciones para EC:

-Medicina (cáncer de mama)
-Ingeniería (eléctrica, mecánica, civil, aeronáutica, robótica)
-Travelling salesman.
-Machine intelligence.
-Expert system.
-Diseño y ruteo de red.
-Redes por cable y sin cable