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
Charles Darwin: teoría de la evolución natural en "El origen de las especies"
Organismos evolucionan según selección natural o el más fitness. Combinación de las mejores características de cada padre hacen a lo fittest. Se adaptan cada vez más al ambiente.
John Holland en 1975 - "Adaptación en sistemas artificiales y naturales": se plantea esta idea para optimizar y hace el primer algoritmo genético. Se basan en genética y evolución.
Trasfondo biológico:
Genética: ciencia que estudia similitudes y diferencias en las especies. Del griego "génesis" que significa crecer o convertir.
Célula:
Todo animal y humano tiene pequeñas industrias que trabajan juntas. Estas son las células, su centro se llama núcleo, donde se encuentra la información genética.
Cromosomas:
La información genética se encuentra en el cromosoma, hecho de ADN. Tiene 23 pares. Los cromosomas tienen partes llamadas genes, que tienen las propiedades/características de las especies, llamadas alelos.
Los genes pueden tener varios alelos. Por ejemplo el gen del color de ojos, tiene los alelos café, negro, celeste, verde.
El conjunto de alelos en una población se llama reserva genética, que determina todas las posibles variaciones.
El conjunto de genes de una especie se llama genoma. Cada gen tiene una posición en el genoma llamado locus.
En la vida real guardan el genoma en varios cromosomas en AG será en uno solo.
Genética:
Para individuo particular, la combinación completa de genes se llama genotipo.
El fenotipo describe el aspecto físico de decodificar el genotipo.
SELECCIÓN sobre fenotipo, y combinación de reproducción sobre genotipo.
Cromosomas tienen dos conjuntos de genes, a esto se le llama diploides. Donde gana el dominante sobre el recesivo.
AG se concentra en cromosomas haploides.
Reproducción:
-Mitosis: La misma información es copiada a la descendencia, sin intercambio.
-Meiosis: base de reproducción sexual, donde hay 2 gametos, se conjugan en una cigota, que se convierte en un individuo.
Selección natural:
Preservar las variaciones favorables y rechazar las no favorables.
*VER IMAGEN DE LO NATURAL VS AG*
Algoritmos genéticos:
*Espacio de búsqueda/espacio de estado:
El espacio de todas las soluciones prometedoras. Cada una puede ser marcada por su valor fitness, según la definición del problema.
*Mundo de algoritmos genéticos:
Es un algoritmo estocástico: debe ser aleatorio, en reproducción y selección.
Siempre considera una población de solución. Hay que mantener mas que sólo la solución en cada iteración. Pues la recombinación puede darnos un buen resultado.
Debe ser robusto: ser consistente en un rango amplio de problemas de todo tipo. Algoritmo de población base puede ser paralelo.
No dan una solución globalmente óptima, pero si una aceptablemente buena.
Evolución y optimización:
Caso de la ballena rara, se van produciendo cambios para hacerse más fuerte, y así crear más descendencia.
Evolución y algoritmos genéticos:
La idea de John es: la solución existe en la reserva genética, pero está separada entre los individuos. Incluía mutación y recombinación para esto.
La recombinación es el operador clave de la evolución natural. Toma dos genotipos y crea uno nuevo combinando estos dos. Usa mutación y crossover (recombinación)
Técnicas de búsqueda y optimización convencional:
El objetivo de optimizar es encontrar un algoritmo que resuelva una clase dada de problemas. Se combina la creatividad humana con los procesos computacionales.
1. Optimización con método local basado en gradiente:
Hessian Based. La confianza y desempeño varía mucho. Debe ser una función smooth.
Busca por mínimo, no por máximo. Problema de una dimensión. Usa conjugada, Newton, secante.
2. Búsqueda aleatoria:
Busca de forma aleatoria y evalúa su fitness. Es un método tonto. Usado para comparar con resultados de un método mejor. Nunca se queda pegado. En un espacio de solución finito, está garantizado que encuentra
la respuesta óptima. Dura mucho.
3. Escalamiento de colina estocástica:
Es el método más simple de los que existen para funciones con fitness continuo con buen comportamiento.
Se basa en elegir aleatoriamente una solución vecina de la solución actual y la mantiene si mejora la función fitness. Converge entre la solución óptima si la función fitness es continua.
En funciones con muchos picos, se detiene en el primero aunque no sea el más alto. Cuando se detiene no puede continuar más. Inicia de un punto aleatorio.
Se puede hacer iterado, para encontrar el punto óptimo global.
4. Recocido simulado:
Inspirado en la formación de cristales sólidos mientras se enfrían. Entre más duren enfriándose, mejor quedan.
Se mueve aleatoriamente, pero quedarse en un lugar específico depende de la energía y temperatura del sistema. Con la ley de Gibbs.
E = energía, k = constante de Boltzmann, T = temperatura.
También selecciona vecino de la más óptima hasta el momento. Si es mejor, se elige como la más óptima, sino se usa una probabilidad para ver su se mantiene.
Empieza de una temperatura alta que decrece exponencialmente. Casi asegura encontrar el óptimo.
Compite con GA:
-GA usa población base, SA un individuo.
-SA mas simple y rápido.
-GA tiene ventaja por paralelización, SA no se beneficia tanto de esto.
5. Inteligencia artificial simbólica:
Son estáticas, resuelven un solo problema, no se adaptan a cambios.
Algoritmo genético:
PASOS:
-Selección: seleccionar individuos para reproducir. Aleatoriamente, con probabilidad que depende en el fitness relativo, se eligen los mejores.
-Reproducción: se crea una descendencia con los seleccionados. Puede usar mutación o recombinación.
-Evaluación: Fitness de los cromosomas creados se evalúa.
-Intercambio: Se eliminan los débiles de la población anterior y se reemplazan con los nuevos.
Se detiene cuando la población converge con la solución óptima.
1. Crear población
2. Evaluar soluciones
3. Seleccionar los más aptos
4. Crossover
5. Mutación
6. Reemplazar
7. Evaluar criterio de finalización.
A. Determinismo: alta variación en la calidad de la solución. Porque se puede quedar pegado en algún momento y no salir. Se puede evitar.
B. No determinismo: no le pasa eso, búsqueda estocástica, contiene un poco de determinismo.
C. Determinismo local: puramente estocástico, lento. greedy search, local hill climbing. Hace muchas predicciones determinísticas.
Características:
-Completitud: toda solución debe tener su codificación.
-No redundante: códigos y soluciones deben ser uno a uno.
-Robusto: cualquier código debe tener su solución correspondiente.
-Perseverancia característica: descendencia debe heredar características útiles de sus padres.
Ventajas:
Paralelismo, espacio de solución amplio, fitness landscape complejo, facil de ver el óptimo global, etc. VER LIBRO
Desventajas:
Identificar función fitness, representar el problema, ocurre convergencia prematura, etc. VER LIBRO
aplicaciones:
ver libro
