Apuntes de una clase sobre Inteligencia Artificial en el que trata el tema de la Vida Artificial
Fecha:  20 de Marzo de 2007
 

Estoy haciendo una Maestría en Ingeniería con énfasis en Ingeniería de Sistemas y ahora estamos viendo una cátedra sobre computación inteligente. El tema que trato a continuación es sobre lo visto en el tema de Vida Artificial. En letra normal lo visto en el curso (diapositivas) y en letra cursiva mis comentarios.

1. Comportamiento emergente: Al interactuar entre si entidades similares con comportamiento muy simple, puede surgir un comportamiento mucho mas complejo que no estaba programado en las entidades simples (hormigas, dilemas sociales, etc.)
Por ejemplo cuando las aves emigran logran hacer la característica figura triangular en el aire para minimizar el frenado del aire (una figura aerodinámica), o los cardúmenes que se mueven al unísono. Son comportamientos de grupo, de manada, de enjambre, de colonia. El todo es mas que la suma de las partes. Determinados miembros se especializan o se dedican a una tarea exclusivamente y las otras tareas que requieren para sobrevivir son hechas por otros miembros. El inicio de una simbiosis pero en entes similares.

2. La inteligencia se basa en predecir el futuro, anticiparlo, adaptarse y sobrevivir.
En el libro del "el cerebro y el mito del yo", el autor anota que la capacidad de predecir es de seres con capacidad para desplazarse de su entorno porque deben predecir sus movimientos (por ejemplo, para eludir una roca en el camino) y ese es el inicio de la inteligencia.

3. La Teoría de la Evolución también evoluciona (mas bien se complementa o se amplia).
Charles Darwin (Darwinismo) = Selección del mas apto.
a. Competencia.
b. Lucha (gana el mas fuerte).... ¡¡no!! es el mas apto.
c. Ambiente cruel porque sobrevive el mas fuerte.... ¿ambiente cruel? no siempre, y repito: ¡sobrevive el mas apto!.

NeoDarwinismo = Darwinismo + Teoría de Juegos
a. La competencia sigue existiendo, pero la cooperación es mas importante.
b. Sobreviven los que se apoyan mutuamente entre si y crean nuevas estructuras (como las células eucariota, seres multicelulares, grupos sociales)... es lo que sostengo con la simbiosis y mi hipótesis del macroorganismo
c. El mundo lo fabrica y lo domina el mas inteligente... ¿dominio? déjame dudar un poco, la inteligencia es solo una más de las estrategias de la vida para sobrevivir, pero que sea el fin último, no creo. Si este se vuelve un ambiente muy hostil, dudo que dure mucho el ser humano, en cambio, sobrevivirán las bacterias extremófilas (no inteligentes pero si le sacan provecho a ambientes hostiles)

4. Sistemas evolutivos:
a. Población (conjunto) de entes.
b. Se reproducen (sexual o asexualmente).
c. Con variabilidad (por el cruce sexual o por mutaciones).
d. Sometidos a una presión selectiva (comparten un recurso vital escaso).

5. ¿Por que se necesita variabilidad?
Si todos los entes son iguales, hay estancamiento (¿y el comportamiento emergente?). las teorías evolutivas actuales hablan de equilibrios puntuales (la evolución no es continua sino a saltos). Actualmente estamos en un punto de "estancamiento" (no me lo creo, inclusive la explosión cámbrica requirió millones de años).

6. La humanidad exhibe tres niveles de evolución (¿solo la especie humana? no lo creo).
a. ontogenética (dentro del individuo). La mínima unidad es la neurona. El deposito es el conocimiento.
b. philogenética (el linaje). La mínima unidad son los genes. El deposito es el genoma.
c. sociogenética (la sociedad). La mínima unidad son las ideas. El deposito es la cultua. Los "memes".

7. ADN compuesto de Adenina, Timina, Guanina, Citosina (ATCG). 3 nucleótidos = codon. codón se traduce en aminoácido, aminoácidos son los bloques de las proteínas. Las proteínas se comportan dependiendo de sus estructura 3D y son las que generan al individuo (forma y funcionamiento). Hay codones que son marcas de finalización. La sucesión de codones es un gen.
Al ADN se le llama genotipo, la forma y funcionamiento se le llama fenotipo. Pasar de genotipo a fenotipo se llama expresión.

8. En computación evolutiva hay un solo cromosoma muy largo. No hay expresión. El fenotipo y el genotipo es lo mismo. Un gen produce UNA sola característica en el fenotipo. En biología un gen puede producir varias características del fenotipo o un fenotipo es el resultado de la interacción de varios genes.

9. Los algoritmos determinísticos (los clásicos) son muy eficientes pero poco generalizan y caso contrario, entre mas aleatorio (sea el algoritmo), mas genérico es, pero son poco eficientes. La computación evolutiva trata de ponerse en el medio.

10. Algoritmos genéticos: Búsqueda de óptimos, muy robusto, basado en el concepto de la evolución. Sirven principalmente para problemas numéricos. Búsqueda orientada. Soluciones múltiples. Problemas generales. Aplicaciones: Minimización/Maximización de funciones multidimensionales, descubrimiento de estrategias óptimas en juegos.

11. Diseño de un algoritmo genético
a. Definir un cromosoma (secuencia de símbolos)
    . Cada gen del cromosoma almacena un símbolo
    . Cada gen puede tener varios alelos.
    . Un cromosoma debe representar TODAS las posibles soluciones al problema.
    . La posición de cada gen debe definir alguna característica relevante a la solución.
b. Definir una una función de evaluación (la selección natural).
c. Definir los operadores de reproducción.
d. Definir la forma sobre como los nuevos cromosomas reemplazarán los viejos.
e. Definir la manera de normalizar la función de evaluación para conseguir la función de aptitud. (Esto lo entiendo sobre como evalúo cuantitativamente la adaptación del algoritmo genético dada la función de selección, porque aunque varios organismos pasan la prueba de la selección natural, algunos les va mejor que a otros y a los que les va mejor son los que tienen mayores posibilidades de reproducirse)

12. Funcionamiento de un algoritmo genético
a. Generar una población de N cromosomas al azar (típicamente N=100) Hay que hacer pruebas si una población mas grande que ese valor sería mejor.
b. Evaluar cada cromosoma usando la función de aptitud (deseche los que no pasaron y evalúe a los que si pasaron)
c. Seleccionar un subconjunto de cromosomas dependiendo de su aptitud y pasarlos a la "matting pool" (los mejores pasan a la "sala VIP" para ser reproducidos).
d. Reproducir los cromosomas de la "matting pool" utilizando ciertos operadores (cruzamiento, mutaciones).
e. Reemplazar los viejos cromosomas por los nuevos (usualmente manteniendo constante el número N de cromosomas). (Pero en la naturaleza las especies exitosas tienden a crecer, hay que hacer pruebas). Hay políticas generacionales: Puede ser un reemplazo total de los padres (no muy recomendado) o eliminando los peores padres. Hay políticas de estado estacionario: No hay "matting pool" solo se adiciona un nuevo individuo por selección de unos determinados padres (eso si que es mas cercano a la naturaleza).
f.  Repetir (volver a b.) hasta que se estabilice la solución. (la naturaleza nunca termina).

Detalles de la función de evaluación (fi)
a. Un indicador de lo bueno que es el cromosoma.
b. Debe ser rápido para evaluarse.

Detalles de la función de aptitud (Ui)
a. Es la función de evaluación dividida por el máximo esperado de ella Ui=fi/fmax
b. Hay que normalizarla entre [0,1]

Para seleccionar los cromosomas que pasan a la "matting pool" se tiene en cuenta el resultado de la función de aptitud de cada uno y esto se le aplica una distribución de probabilidad para saber cuales serán los escogidos. Puede ser por:
. Sorteo: Cada puesto de la "matting pool" es rifado (dándole mas probabilidad al mejor). Consume una cantidad K de números aleatorios=tamaño de la piscina.
. Ruleta (la típica distribución empírica)
. Por Restos: Los mejores entran a la piscina y las vacantes se rifan usando los métodos anteriores.
. Por torneo: Se seleccionan tres cromosomas al azar y se escoge el mejor. Así hasta que complete la piscina. Es el más rápido.

13. Los "peros" de los algoritmos genéticos:
a. NO hay, NI habrá seguridad teórica que el algoritmo genético vaya a converger, ni que llegue a la mejor solución.
b. Al diseñar debe tener en cuenta la completitud (cada solución se puede codificar en el cromosoma), es decir, no se puede dejar nada por fuera, la cerradura (cada cromosoma equivale a una solución), la solución encontrada debe ser viable.
c. Y preferiblemente los cromosomas deben presentar uniformidad (todas las soluciones deben estar representadas por la misma cantidad de cromosomas), localidad (un pequeño cambio al cromosoma solo hace un pequeño cambio al resultado). Lo último si es difícil de lograr sobre todo en la programación genética que estoy desarrollando.
d. Como la solución se codifica en bits, si escoge un tamaño pequeño en la cadena de bits deja por fuera soluciones, si escoge un tamaño grande de la cadena de bits se cuelan soluciones no viables. Resolver esto no es sencillo.
e. Mantener la diversidad (los superpadres que generan hijos que finalmente consumen toda la población), evolución errática en las últimas generaciones (no me ha sucedido en las simulaciones).
f. La epistasis: un gen genera individuos muy buenos pero no tan buenos, pero la selección no logra deshacerse de ese gen.
g. Mínimo local (convergen muy rápido).

14. Como minimizar los problemas de los algoritmos genéticos:
a. Aumentar la población de cromosomas.
b. Mantener la diversidad de los cromosomas.
c. Controlar la presión selectiva.
d. Islas (Charles Darwin lo dedujo)
e. Controlar las edades de los individuos (interesante forma de deshacerse de los superindividuos pero echa por la borda una estrategia de la naturaleza que es la longevidad).
f. Reiniciar todo, salvando los mejores (¿un diluvio y un arca de Noe?)

15. Criterios de terminación: por número de ejecuciones (pésimo), convergido en un porcentaje, si el cambio de una generación a otra esta por debajo de un porcentaje.

16. Típicos parámetros en una simulación con algoritmos genéticos:
a. Población: Entre 50 y 100 cromosomas (yo los llamo entre 50 y 100 organismos)
b. Longitud del cromosoma: Depende del problema.
c. Probabilidad de cruce: 20% a 60% por cromosoma.
d. Probabilidad de mutación: 0.1% a 5% por gen.

17. Los parámetros anteriores pueden ajustarse con otro algoritmo genético, se codifican en cromosomas esos parámetros e igual se evalúan como cualquier algoritmo genético ¿La función de aptitud? Depende como con esos parámetros les va en las simulaciones de algoritmos genéticos.  (si era un problema que tenía, los parámetros son ajustados por el usuario en el archivo de inicialización, esta es una buena idea pero consume mucho tiempo de computo)

18. Programación Genética
Es la misma que he estado haciendo desde el capitulo 2 solo que Koza su fundador representa los algoritmos como si fuesen árboles (igual que un evaluador de expresiones basados en árboles). La mutación son cambios en las ramas del árbol.

Se deben cumplir las condiciones de suficiencia (cada solución se puede codificar en el cromosoma) y cerradura (cada cromosoma equivale a una solución).

Hay que tener especial cuidado cuando se codifican funciones en el que se debe tener en cuenta el número de parámetros y el tipo de parámetros.

Para Iniciar (recordar que se representan como árboles)
1. "Full" Crear los programas con todo el camino L completo.
2. "Grow" Se crean los programas de tamaño variable.
3. "Ramped half and half" Se define un porcentaje de probabilidad por cada tamaño entre 2 y L (y este es el que da mejor diversidad). Excelente idea para evitar superpadres.

Operadores de reproducción
Cruce: Intercambiar dos sub-arboles al azar entre dos individuos.
Mutación: Eliminar al azar un sub-árbol y reemplazarla con otro.
Permutación: Similar al cruce pero dentro del mismo individuo.
Edición: Eliminar bloques inútiles.
Encapsulación: Cambiar toda una función por otra

Los problemas:
a. Mucho poder de computo.
b. Mucho código basura (intrones)
c. Las funciones primitivas deben estar orientadas a la solución. Si sobran genera código inútil, si faltan se pierden posibilidades de solución. Es como cuando uno toma la decisión de usar funciones como seno, coseno, tangente o solo operaciones básicas.

Para diseñar:
a. Funciones a usar.
b. ¿Uso de bucles?
c. Número de variables internas (y si va a usar arreglos unidimensionales o N-dimensionales).
d. ¿Uso de constantes?

Aplicaciones:
a. Regresión simbólica (lo que vengo haciendo desde el capitulo 2).
b. Predicción de secuencias.
c. Diseño en Ingeniería
d. Estrategia en robots.
e. Diseño de circuitos digitales.
f. Demostración de identidades matemáticas.
g. Comportamiento emergente.
h. Clasificación de datos.
i. Diseño de controladores y automatismos (parquear un camión articulado).
j. Diseño de estrategias óptimas en videojuegos.

19. Evolución Gramatical
Codifican instrucciones en una tupla tipo NTPS (N símbolos no terminales, T símbolos terminales, P conjunto de reglas de producción, S símbolo inicial). Es lo último que estoy haciendo, en el que codifico una instrucción en un número entero.
La teoría de la evolución neutral de Kimura dice que las mutaciones silenciosas (las que afectan a instrucciones no ejecutadas) son las responsables de la gran diversidad genética que hay.

20. Programación por expresión genética
Es el capítulo 1 donde son ecuaciones representadas por un árbol (el típico evaluador de expresiones) y van ejecutándose de igual manera que un algoritmo genético. Los árboles formados se recorren por niveles y eso da origen a la expresión horizontal del cromosoma.

21. Programación Evolutiva
No hay una codificación fija (como la binaria que tiene que ser cromosoma), sino que se puede codificar dependiendo de como lo necesite el problema (árboles, máquinas de estado finito, etc..). No hay operador de cruce sino de mutación.

22. Estrategias evolutivas
El famoso ejemplo de diseñar un ala de avión utilizando estrategias evolutivas (Schwefel y Bienert en Berlín en 1963). Reproducción con mutación. Estrategias como reemplazo total de los padres o competencia padre vs hijos

23. Sistemas clasificadores
Se basan en puros IF condicionales: IF condicion THEN hagaesto, la condición y el hagaesto son deducidos por evolución, se evalúa cada IF y se recompensa si la acción fue adecuada.

24. Simulated Annealing
Es una meta-heurística para problemas de optimización global, es decir, encontrar una buena aproximación al óptimo global de una función en un espacio de búsqueda grande. El concepto es análogo a calentar un metal y enfriarlo con la esperanza de que en este proceso repetitivo los átomos se acomoden en las posiciones de menor energía, si un átomo queda mal ubicado será fácil de desprender de la lámina por otros átomos por su poca fuerza de cohesión.