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