Modelo para computación paralela:
Máquina de von Neumann es una por una instrucción, uno por uno item de data, siguiendo un programa en memoria.
En el libro se usa el modelo "parallel random-access machine" o p-ram. También llamado "single-instruction multiple-data-stream"
Se tienen varios procesadores, que se asume que comparten una memoria global. Todos ejecutan el mismo programa dado por un punto central de control. Trabajan en la misma instrucción al mismo tiempo.
En cada paso lee o escribe en la memoria global que todos comparten, pero en no mas de una ubicación de esta. Dos pueden leer lo mismo, pero no escribir en lo mismo, ni leer mientras el otro escribe.
concurrent-read, exclusive-write(CREW). Usado en el libro
También existen:
-exclusive-read,exclusive-write(EREW)
-concurrent-read,concurrent-write(CRCW).
En el modelo, leer o escribir, es tiempo constante, sin importar el número de procesadores. Para términos del libro, en la realidad no funciona así.
No se permite que el statement sea llamadas a función, ni loops que el largo dependa de la data.
Si tenemos p procesadores, toma 8(log p) en que comience, para decirle a todos que hacer.
Técnicas básicas:
1-Árbol binario completo:
Todas las hojas de un mismo nivel se ejecutan en paralelo. La solución se da en el paso lg-n. Por lo que le toma 8(log n) en hacer la operación con un arreglo con todos los valores. Se ocupan n/2 procesadores como máximo.
2- Pointer doubling:
Técnica más simple, para listas. En la lista cada item tiene un puntero al siguiente s[i]. Y el ultimo tiene un puntero a nulo s[n]=nil.
No hay problemas de escritura, pues cada procesador escribe en un solo nodo, pero si de lectura, hay que asegurarse que antes de leer, los anteriores deben haber terminado su proceso.
Cada vez que se corre se dobla el puntero al que apunta. 8(log n) cada procesador hace tiempo constante por las operaciones elementales que realiza.
Trabajo y eficiencia:
Trabajo: p*t, p=cantidad de procesadores, t=el tiempo
Dos algoritmos son work-efficient, si están en el orden del otro.
Dos reglas para que sea eficiente:
-La cantidad de procesadores para una instancia de tamaño n debe estar en O(n^a) a siendo una constante.
-El tiempo requerido para resolver una instancia de tamaño n deber estar en O(log^b n)b siendo una constante.
Un algoritmo paralelo eficiente tiene número polinomial de procesadores y tiempo poligarítmico.
Es óptimo si work-efficient con el mejor algoritmo secuencial o con el mejor conocido. Se puede decir que tiene aceleración óptima (optimal speed-up)
Se cree que hay problemas que se solucionan con secuencial, pero no se puede con paralelo.
Ejemplos con grafos:
1. Camino más corto:
En la iteración k, da los caminos más cortos entre nodos usando no mas de 2^k arcos.
Orden: 8(log^2 n)
2. Componentes conexos:
Se encarga de ver que componentes se encuentran conexos de un grafo, dejando un árbol o bosque de resultado. Utiliza conjuntos disjuntos y los une después.
Orden: 8(n^2)
Evaluación de expresiones paralelas:
suma, resta, multiplicación y división. Árbol binario nodos internos son operadores y las hojas son los operandos.
Redes de ordenamiento paralelo:
Comparador: circuito con dos entradas y dos salidas, izquierda y derecha respectivamente. Si son iguales se cambian de arriba a abajo. Se crean redes se comparadores que ordenan los números que les demos en paralelo.
N = cantidad de comparadores a usar (tamaño de la red)
Funciona en 8(n)
El principio cero-uno:
VER IMAGEN
Redes unidoras paralelas:
Una red unidora consiste de comparadores, con dos grupos de n entradas y un grupo de 2n salidas. Cada grupo está ya ordenado, sale todo el conjunto ordenado.
Redes unidoras mejoradas:
Se implementa divide and conquer a lo anterior.
Ordenamiento paralelo:
Lo anterior puede ordenar n elementos en 8(log^2 n) y con 8(log^2 n) procesadores.
ALGORTIMO DE COLE:
Ordena en 8(n log n)
Números en potencia de 2, todos distintos.
EREW vs CRCW p-rams:
EREW < CREW < CRCW
Computación distribuida:
Modelo múltiple-instrucción múltiple-flujo-datos: cada procesador trabaja a su ritmo con su data y sus instrucciones.
SIMD and MIMD.
SIMD: procesadores cerca entre ellos.
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
