Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi

Equation Chapter 1 Section 1 Proyecto Fin de Grado Ingeniería de Telecomunicación Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Autor: Álvaro Espejo Muñoz Tutor: Sergio Luis Toral Marin Dpto. Ingeniería Electrónica Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 iii Proyecto Fin de Grado Ingeniería de Telecomunicación Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Autor: Álvaro Espejo Muñoz Tutor: Sergio Luis Toral Marin Catedrático de Universidad Dpto. de Ingeniería Electrónica Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 v Proyecto Fin de Carrera: Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Autor: Álvaro Espejo Muñoz Tutor: Sergio Luis Toral Marin El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2019 El Secretario del Tribunal vii Agradecimientos Por supuesto agradecer a mi tutor, Sergio Luis Toral Marin, que me ha facilitado en todo lo posible la realización de este trabajo, pero también quiero dar unas palabras de agradecimiento a Daniel Gutierrez Reina, que a pesar del tiempo que ha pasado desde que solicité este trabajo siempre ha estado ayudándome y proporcionándome lecturas interesantes que sin duda me han sido útiles para poder completarlo. Llegar hasta aquí no habría sido posible sin el cariño y la educación que mis padres, Roberto y María Dolores, me han sabido dar en su infinita paciencia conmigo. Cómo no, agradezco a Merche por soportarme, sobre todo quererme, pero en especial ayudarme a terminar este grado en ingeniería, que sin su fuerza y ánimo no hubiera conseguido nunca. A mi hermano Rober, por aconsejarme y escuchar siempre mis dudas y problemas. Me acuerdo también de mis dos abuelos y dos abuelas que, allí donde estén, sé que sonreirán al verme convertirme en ingeniero. A todos, gracias por el apoyo recibido durante toda esta larga etapa. ix Resumen El uso de algoritmos genéticos para resolver problemas de optimización combinatoria es una técnica cada vez más utilizada debido a que el espacio de búsqueda de soluciones es generalmente demasiado elevado como para ser resuelto por métodos convencionales. A menudo un algoritmo genético aplicado de forma secuencial se topa con la dificultad de que, al ser computacionalmente muy intensivo, en problemas donde se presenta una población de cierta envergadura se necesita de un tiempo de evaluación excesivamente elevado, lo que puede resultar poco adecuado para la resolución de problemas de optimización combinatoria. Una forma de extender la aplicabilidad de la computación evolutiva hacia problemas de mayor complejidad es la inclusión de paralelismo debido a las mejoras que presenta en cuanto a rendimiento. Este trabajo está dividido en dos partes. La primera de ellas está dedicada a un estudio sobre las bases teóricas de dichos algoritmos, así como sus usos en computación en paralelo y computación distribuida en una red. En la segunda parte, se realiza un montaje de varios dispositivos Raspberry Pi conectados mediante Wi-Fi en una red de área local (LAN). Estos dispositivos serán configurados para trabajar de forma conjunta (distribuida) con el fin de resolver un problema de optimización clásico, el conocido como „problema de las N reinas‟. Usando esta estructura, se diseñará una serie de ensayos en el que se plantean diversos escenarios, haciendo uso de dichos algoritmos genéticos con el objetivo de paralelizar el algoritmo y poder realizar comparaciones entre los resultados obtenidos. Como una de las conclusiones más reseñables de este trabajo podría decirse que existe un punto de inflexión a partir del cual es conveniente el uso de algoritmos genéticos paralelos con modelo de población basado en islas (para dispositivos con limitaciones computacionales, como puede ser una Raspberry Pi) xvii ÍNDICE DE FIGURAS Figura 2-1. Esquema de resolución de un problema clásico. 5 Figura 2-2. Esquema de resolución de un problema mediante el uso de Algoritmo Evolutivo Simple. 6 Figura 2-3. Esquema simple representando un cruce de un único punto. 8 Figura 2-4. Esquema simple representando un cruce de doble punto 8 Figura 2-5. Pseudocódigo de un algoritmo genético simple. 11 Figura 2-6. Esquema de funcionamiento de modelo de islas con comunicación en estrella. 12 Figura 2-7. Esquema de funcionamiento de modelo de islas con comunicación en red. 13 Figura 2-8. Esquema de funcionamiento de modelo de islas con comunicación en anillo. 13 Figura 2-9. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Primer paso: Copia de la subcadena en la descendencia. 15 Figura 2-10. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Segundo paso: Rellenar las demás celdas. Caso en que una celda ya esté en la subcadena central (Celda #1) 16 Figura 2-11. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Segundo paso: Rellenar las demás celdas. Caso en que dos celdas ya estén en la subcadena central. (Celda #8) 16 Figura 2-12. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Tercer paso: Repetir el segundo paso con el segundo hijo. Representación final. 16 Figura 3-1. Raspberry de primera generación. Modelo A. 19 Figura 3-2. Raspberry de primera generación. Modelo B. 20 Figura 4-1. Captura de pantalla del sistema modificado sobre Raspbian. 25 Figura 4-2. Captura de pantalla de interfaz de Etcher en un sistema MacOS 26 Figura 5-1 Ejemplo de archivo de resultados generado por Ensayo_Isla_NoScoop.py 34 Figura 6-1.Comparación entre tiempos medios de ejecución a lo largo de los cinco escenarios. 48 Figura 6-2. Comparación, en el Escenario A, de los mejores valores fitness encontrados. 49 Figura 6-3. Comparación, en el Escenario E, de los mejores valores fitness encontrados. 50 1 1 INTRODUCCIÓN Y OBJETIVOS n este primer capítulo se pretende dar contexto a la materia que se va a tratar durante este proyecto, los algoritmos genéticos, así como un pequeño resumen de su historia y actual estado del arte para, finalmente, introducir los principales objetivos que se pretenden alcanzar con el desarrollo del proyecto. 1.1 Introducción Con el vertiginoso avance de las tecnologías en las últimas décadas, más concretamente desde la aparición de los primeros ordenadores de bajo coste a mediados de la década de 1980‟s, se ha impulsado el desarrollo de resolución a problemas que anteriormente la ingeniería era incapaz de abordar. A lo largo de este estudio vamos a centrarnos en una técnica que nació en dicho momento, se trata de los algoritmos evolutivos cuyo desarrollo desde entonces y hasta el día de hoy ha sido continuo. Los algoritmos evolutivos se inspiran en los métodos de selección que usa la naturaleza, más concretamente en el principio darviniano de la selección natural. Actualmente han cobrado una gran importancia ya que por su evolución natural se han convertido en una poderosísima técnica de optimización y búsqueda, con una alta carga de computación en paralelo. 1.1.1 Trasfondo histórico. Selección natural y teoría de la evolución En 1859 el científico naturalista inglés Charles Darwin publica “El origen de las especies por medio de la selección natural, o la preservación de las razas favorecidas en la lucha por la vida” dónde expone que las diversas especies biológicas compartimos una descendencia común que se ha ido ramificando a través de la evolución, sosteniendo que las especies evolucionan acorde al medio con el fin de adaptarse a éste. Esta rompedora visión diverge de la clásica visión de la naturaleza, estática y perfecta creada por Dios. En este escrito apareció por primera vez el concepto Selección Natural, definido como aquel medio que permite explicar la evolución biológica de la siguiente forma (Darwin, 1859): Existen organismos que se reproducen y la progenie hereda características de sus progenitores, existen variaciones de características si el medio ambiente no admite a todos los miembros de una población en crecimiento. Entonces aquellos miembros de la población con características menos adaptadas (según lo determine su medio ambiente) morirán con mayor probabilidad. Entonces aquellos miembros con características mejor adaptadas sobrevivirán más probablemente. La teoría de la evolución de Charles Darwin se sustenta en tres premisas: La primera es que debe existir variabilidad del rasgo entre los individuos de una población, es decir ha de presentar diferentes estados o E “We can only see a short distance ahead, but we can see plenty there that needs to be done”. - Computing Machinery and Intelligence (1950), Alan Turing - Introducción y objetivos 2 fenotipos; La segunda, el rasgo debe ser sujeto a transmisión, es decir cada fenotipo de dicha característica ha de poder ser transmitido; La tercera y última, la variabilidad del rasgo debe dar lugar a diferencias en la supervivencia, es decir debe de haber algún factor que afecte a la probabilidad de que algunas características de nueva aparición se pueda extender en la población. Si se cumplen estas tres premisas, puede tener lugar el fenómeno de la selección natural. En caso de no cumplirse cualquiera de ellas, no puede haber selección natural. August Friedrich Leopold Weismann, científico biólogo alemán formuló (Weismann, 1892) en el siglo XIX la teoría de plasma germinal, o germoplasma, en la cual distinguía entre células germinales, que eran capaces de transmitir información hereditaria, y células somáticas, que no transmitían información alguna. Gregor Johann Mendel, científico, monje agustino católico y Abad de la abadía de Santo Tomás de Brno realizó una serie de experimentos (Mendel, 1865) con guisantes durante un largo periodo de su vida, los cuales estudió y le sirvió para enunciar a partir de ellos las leyes básicas que gobiernan la herencia y que son conocidas como leyes de mendel. Hoy en día se conoce como paradigma Neo-Darwiniano a la conjución de la teoría evolutiva original de Charles Darwin junto al seleccionismo de August Weismann y la genética de Gregor Mendel. El Neo-Darwinismo establece (Hoffmann, 1989) que con sólo 4 procesos se puede explicar la mayoría de vida en nuestro planeta.  Reproducción  Mutación  Competencia  Selección 1.1.2 Trasfondo histórico. Computación Evolutiva Los primeros hechos relacionados con algoritmos genéticos surgen en 1942, cuando Walter Bradford Cannon interpreta la evolución natural como un aprendizaje similar al ensayo y error (Cannon, 1954). También en 1948, el matemático, lógico, científico de la computación, criptógrafo y filósofo Alan Turing establece una conexión entre evolución y aprendizaje máquina, en un informe supervisado por el mismo Sir Charles Darwin dónde proponía máquinas llamadas unorganized machines o u-machines (Turing, 1948). No obstante la apertura en el desarrollo de los algoritmos genéticos se da, durante principios de los años sesenta, cuando distintos investigadores desarrollan de manera independiente algoritmos inspirados en la evolución. El profesor Ingo Rechenben, de la Universidad Técnica de Berlin, introdujo la que llamó Estrategia Evolutiva. Una técnica sin población ni cruce; un padre mutaba para producir un descendiente y se conservaba el mejor de los dos, convirtiéndose en padre de la siguiente iteración. En 1966 Lawrence J. Fogel desarrolla la Programación Evolutiva, donde se introduce por primera vez el concepto de población, que permitía que la salida de resultados no dependiera sólo de la entrada de datos actuales sino también de las anteriores (Fogel, Owens, & Walsh, 1966). Sin embargo, en estas dos metodologías se obvia un fenómeno fundamental de la propia evolución, el cruce. Fue el profesor de Filosofía, Ingeniería Eléctrica y Ciencias de computación, John H. Holland de la Universidad de Míchigan el primero en plantear la posibilidad de adaptar e incorporar mecanismos naturales de selección y supervivencia a la resolución de problemas computacionales, presentando por primera vez de forma rigurosa y sistemática el concepto de sistemas digitales adaptativos con mecanismos de mutación, selección y cruce. Holland es considerado el „Padre de los algoritmos genéticos‟ por desarrollar (Holland, 1975) dos puntos clave:  Imitar los procesos adaptativos de la naturaleza.  Diseñar un sistema informático capaz de usar mecanismos y técnicas de los sistemas naturales para resolver problemas Esta investigación fue fundamentalmente teórica, siendo su realización práctica muy difícil y limitada en aquella década. El trabajo de John Holland da como resultado una técnica de optimización estocástica 3 3 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi originalmente llamada “planes reproductivos” y tachada como técnica no convencional de optimización para problemas del mundo real. No obstante, a partir de la creación de estas estrategias evolutivas aparecieron otras vías de investigación, siendo la más extendida la conocida como algoritmos genéticos, llevada a cabo por David Goldberg, Ingeniero Industrial de la Universidad de Illionis y alumno de John Holland. Goldberg definiría al algoritmo genético como (Goldberg, Genetic algorithms in search, optimization, and machine learning, 1989): “Algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas” 1.1.3 Estado actual A menudo un algoritmo genético aplicado de forma secuencial se topa con la dificultad de que, al ser computacionalmente muy intensivos, en problemas donde se presenta una población de cierta envergadura se necesita de un tiempo de evaluación excesivamente elevado que en ciertos casos imposibilita su implementación. Un ejemplo de ello lo podemos ver en el trabajo (Burgener & Storti, 2004) en el que plantea un problema de optimización para un sistema de refrigeración en el que con una población de 500 individuos, se descarta el uso del algoritmo secuencial ya que se requiere un tiempo de procesamiento por generación extremadamente elevado, aproximadamente 623 minutos. Una forma de extender la aplicabilidad de la computación evolutiva hacia problemas de mayor complejidad es la inclusión de paralelismo, debido a las mejoras que presenta en cuanto a rendimiento. Aplicado al caso anterior, para la misma situación planteada, haciendo uso de un algoritmo en paralelo se requiere un tiempo aproximado de 83 minutos. Esto se debe a dos factores, el primero, una ejecución en paralelo permite un mayor uso de recursos de cómputo como tiempo de procesador o memoria. El segundo factor es que el mismo comportamiento del algoritmo cambia en consecuencia de la estructura de la población, la ejecución en paralelo del algoritmo evolutivo permite una estructura poblacional formada por varios grupos interconectados de individuos. El balance final que se pretende encontrar es que se obtenga no solo un tiempo de espera menor para obtener la solución del problema si no una mejor calidad de búsqueda y del resultado obtenido. Sin embargo, en el paso de un algoritmo genético secuencial a un algoritmo genético en paralelo no todos los elementos son susceptibles de paralelizarse. Es claro que la evaluación de la bondad de los individuos es una tarea cuya paralelización no afecta al comportamiento del algoritmo. No obstante, el esquema de un algoritmo genético es muy secuencial ya que el operador selección sí debe ser aplicado de foma global a toda la población lo que dificulta la total paralelización del problema. El uso de los algoritmos evolutivos hoy en día está presente en muchos y diversos campos, como lo son medicina, desarrollo informático o incluso otros más alejados de la técnica como ciencias sociales o análisis lingüistico, dada su gran utilidad en problemas de tipo multivariable. Ejemplos de sus aplicaciones dentro del campo de la Medicina puede darse en sistemas con sistema de soporte de decisión, p.e medicina oftalmológica (Krawiec & Pawlak, 2015) y medicina oncológica (Conor, Fitzgerald, Medernach, & Krawiec, 2015). Dentro del campo de desarrollo informático, un ejemplo podría ser en uso de sistemas de búsqueda bugs (Yang, Jeong, Min, Lee, & Lee, 2018). En campos más alejados de la técnica, podemos ver ejemplo en sociología, dónde se pueden modelar evoluciones de pensamiento social (Khan, Streater, Bathia, Fiore, & Bölöni, 2013) o economía, usándolos para modelar el comportamiento de agentes del mercado (Markowska-Kaczmar, Kwasnicka, & Szczepkowski, 2008). A continuación se lista las principales áreas en las que más está creciendo el uso de los algoritmos evolutivos.  Redes Neuronales: De la fusión entre redes neuronales y algoritmos evolutivos obtenemos neuroevolución, un conjunto de técnicas y métodos que evolucionan redes neuronales artificiales.  Evolve Hardware: Se trata de un campo centrado en el uso de algoritmos evolutivos para crear electrónica especializada sin necesidad de ingeniería manual. Engloba campos como hardware reconfigurable, computación evolutiva, tolerancia a fallos y sistemas autónomos. o Ejemplo clásico de Ingeniería Aeroespacial (Petit, 1998): Andrew Keane, profesor de ingeniería en la Universidad de Southampton en Inglaterra, utilizó los algoritmos genéticos Introducción y objetivos 4 para producir un nuevo diseño para una viga de carga que pudiese montarse en órbita y utilizarse en satélites y estaciones espaciales. Tras quince generaciones el resultado de su estudio fueron 4.500 diseños diferentes de estructuras retorcidas que ningún ingeniero humano diseñaría. Entre ellas el mejor modelo tenía un aspecto irregular y, en cierta forma, orgánico que Keane comparó con un fémur humano. Este diseño resultó ligero, fuerte y con gran capacidad de amortiguación de vibraciones perjudiciales. Las pruebas en modelos confirmaron su superioridad a los diseñados por humanos como un soporte estable. Sin embargo "Ninguna inteligencia produjo los diseños. Simplemente evolucionaron" o Ejemplo clásico de diseño de antena (Lohn, Hornby, & Linden, 2005): Los investigadores han investigando el diseño y optimización de antenas evolutivas desde principios de la década de 1990s. Hoy en día la velocidad de computación ha aumentado y los simuladores electromagnéticos han mejorado en los últimos años. Muchos tipos de antenas han sido investigados haciendo uso de algoritmos genéticos, incluyendo antenas de alambre con propiedades especificadas a priori, investigadas por Altshuler y Linden en 1997, Arrays de antenas, investigadas por Haupt en 1996, ó antenas cuadrifilares helicoidales (QFH), estudiadas por Jason Lohn en 2002. Por otra parte, en los tiempos recientes millones de dispositivos con implementación de IOT (Internet de las Cosas) que nos rodea presentan un problema: son dispositivos de media o baja capacidad de computación que recolectan información, pero no hacen nada con ella. La envían, por ejemplo, a la nube, donde grandes centros de datos (súper computadoras) la procesan para obtener ciertas conclusiones o activar ciertas acciones. Es por esto que se está imponiendo una nuevo paradigma de computación distribuida, denominado Edge Computing, en la que dicha computación se realiza en parte (o completamente) en nodos de dispositivos distribuidos a los que se les denomina dispositivos inteligentes o dispositivos de borde (Edge) en lugar de tener lugar principalmente en un entorno de nube centralizada. La principal motivación es proporcionar recursos de servidor, como pueden ser análisis de datos e inteligencia artificial, más cercanos a las fuentes de recopilación de datos y sistemas ciberfísicos, como por ejemplo sensores inteligentes. El Edge Computing se considera una herramienta importante en la realización de campos tales como computación física, contribución a las ciudades inteligentes, computación ubicua, aplicaciones multimedia como VR (realidad aumentada) y juegos en la nube, así como el Internet de las cosas. 1.2 Objetivos El objetivo principal de este proyecto es realizar un análisis del funcionamiento de los algoritmos genéticos en un escenario distribuido. Para esta tarea en primer lugar se va a realizar un estudio previo sobre las bases teóricas de dichos algoritmos, así como sus usos en computación en paralelo y computación distribuida en una red. En segundo lugar se va a realizar un montaje de varios dispositivos Raspberry Pi conectados mediante Wi-Fi en una red de área local (LAN). Estos dispositivos serán configurados para trabajar de forma conjunta (distribuida) con el fin de resolver un problema de optimización clásico, el conocido como „problema de las N reinas‟, haciendo uso de dichos algoritmos genéticos con el objetivo de paralelizar el algoritmo y poder realizar comparaciones entre los resultados obtenidos. La elección de solucionar este problema haciendo uso de algoritmos genéticos no es casual, pues entre las diferentes técnicas de computación evolutiva la de los algoritmos genéticos con representación ordinal (Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning., 1989) es la utilizada en la resolución de problemas de optimización combinatoria, donde el espacio de búsqueda se compone de permutaciones (ordenamiento de números enteros). Seguidamente se realizará un estudio del software disponible para implementar técnicas relacionadas con algoritmos genéticos y su posterior aplicación para la resolución del problema ya mencionado de las N reinas. Finalmente se diseñará una serie de ensayos haciendo uso de todos lo anterior descrito en el que se plantean diversos escenarios, de los cuales se va a realizar un análisis comparativo de resultados. 5 2 FUNDAMENTOS TEÓRICOS Una vez se ha explicado el trasfondo a cerca de los algoritmos genéticos, en qué se inspiran, su origen y porqué funcionan bien, toca explicar de forma concisa los procedimientos con los que se sirve. En primer lugar se va a comentar, de forma resumida, la base biológica en la que se sustentan los algoritmos genéticos para. Seguidamente, entraremos de lleno en el concepto y componentes fundamentales que conforman, desde un punto de vista computacional, un algoritmo genético: Inicialización, selección, cruce, reemplazo, elitismo, mutación y métodos de evaluación. A continuación, comentaremos diferentes estrategias de implementación, haciendo hincapié en aquellas que utilizan procesamiento en paralelo. Por último en este capítulo se va desarrollar en profundidad el problema tipo que vamos a utilizar durante el desarrollo de este trabajo, el llamado „Problema de las N Reinas‟. 2.1 Base Biológica Tal y como se ha comentado anteriormente, los algoritmos genéticos se basan en la evolución biológica y su base genético-molecular. La evolución es un proceso que opera sobre cromosomas. Un cromosoma se puede considerar como la herramienta orgánica que codifica la vida y aquella información contenida en los cromosomas se conoce como genotipo. En genética se define a fenotipo como aquella expresión del genotipo en función de un determinado ambiente (Oliva, Ballesta, Oriola, & Clària, 2008), en otras palabras, son aquellas diferencias físicas y de comportamiento que afectan a la respuesta de un individuo a su entorno. En la naturaleza, los distintos rasgos fenotípicos vienen determinados tanto por herencia como por factores relacionados con el desarrollo del individuo. Es decir, si los rasgos fenotípicos incrementan la posibilidad de reproducción y además son heredables, dichos rasgos tienden a incrementar en las subsecuentes generaciones, sirviendo de base a nuevas combinaciones de rasgos. Durante la fase de reproducción ocurre el llamado proceso evolutivo. Los mecanismos más importantes a estudiar en esta introducción son: Mutación, en la cual los cromosomas de padres e hijos resultan diferentes, y Cruce (o recombinación), que combinan los cromosomas de los padres para producir la descendencia. La combinación de buenas características de heredadas puede originar que el individuo esté mejor adaptado al medio que sus ancestros. 2.2 Algoritmos genéticos La idea básica de un algoritmo genético nace en aquellos problemas donde no podemos usar un método resolutivo clásico. Figura 2-1. Esquema de resolución de un problema clásico. En el método resolutivo clásico hemos de conocer el algoritmo a usar para resolver el problema mientras que la selección natural elimina uno de los mayores obstáculos en el diseño software: especificar de antemano todas las características de un problema y las acciones que el programa habría de tomar para enfrentarlo. Al Fundamentos Teóricos 6 aprovechar los mecanismos de la evolución se pueden resolver problemas cuya estructura nos es desconocida. Un algoritmo evolutivo es capaz de resolver problemas de tipo NP, siglas en inglés para nondeterministic polynomial time, es decir problemas que no pueden resolverse en un tiempo polinómico. Este tipo de problema engloba problemas de búsqueda y de optimización para los que se desea saber si existe una cierta solución o si existe una mejor solución que las ya conocidas, es decir, se debe realizar una búsqueda exhaustiva de todas las posibilidades del espectro. Figura 2-2. Esquema de resolución de un problema mediante el uso de Algoritmo Evolutivo Simple. Durante el proceso evolutivo se trabaja sobre una población de individuos, donde cada uno representa una posible solución al problema que se desea resolver. A cada individuo se le asocia un valor de ajuste, denominado fitness, que cuantifica la validez de la solución respecto al problema. Buscando una analogía con la propia naturaleza, podría decirse que el valor de ajuste sería el equivalente a cuantificar la eficiencia de un individuo en aprovechar los recursos del medio. 2.2.1 Inicialización Se trata de la primera parte del algoritmo y es el encargado de elegir de entre todo el espectro posible de soluciones que el problema puede aceptar. La elección se hace de una forma aleatoria tal que se consiga una población inicial lo más heterogénea que se pueda, representando la diversidad que presenta el sistema y llegando así a los óptimos de manera más rápida y abarcando todo el dominio. Para evaluar los individuos de forma efectiva y atendiendo a las necesidades específicas de cada problema se usa un tipo de codificación específica. La codificación es pues una representación, elegida, del formato de la solución. 2.2.2 Selección Parte del algoritmo que se encarga de escoger cuál individuo va a tener oportunidad de reproducirse y cuál no. Para ello se ha de tener en cuenta que se ha de otorgar una mayor tasa de probabilidad de reproducción a aquellos individuos más aptos sin descartar a los menos aptos, ya que esto podría provocar que la población se volviese homogénea en pocas generaciones. Existen dos grupos en los que se puede dividir los algoritmos de selección: Probabilísticos y Determinísticos. 7 7 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi 2.2.2.1 Algoritmos de selección probabilísticos En este tipo de algoritmos se adjudica la probabilidad de selección con una componente de aleatoriedad. Es en este grupo donde se encuentran los algoritmos de selección por ruleta o por torneo que, dada su importancia por ser los más utilizados, se describen a continuación.  Selección por ruleta (Blickle & Thiele, 1995): A cada individuo le es asignada una parte proporcional a su valor de ajuste en una “ruleta” de tal forma que la suma de los porcentajes asignados a cada individuo sea la unidad y que los mejores individuos recibirán una porción de la ruleta mayor que la recibida por los peores. Generalmente la población está ordenada en base al ajuste, por lo que las porciones más grandes se encuentran al inicio de la ruleta. Para seleccionar a un individuo se genera un número aleatorio comprendido [0,1] y se escoge el individuo situado en dicha posición de la ruleta. A pesar de ser, probablemente, el método de selección más conocido por ser muy sencillo es altamente ineficiente a medida que aumenta el tamaño de la población.  Selección por torneo probabilístico (Miller & Goldberg, 1995): Este método consiste en hacer comparaciones entre individuos. Primero se selecciona un número p de individuos (generalmente se escoge p=2 para hacer comparaciones dos a dos) de manera aleatoria y luego se genera un número al azar en el intervalo [0,1]. Si dicho valor es mayor a un parámetro q fijado para todo el proceso evolutivo, que suele comprender el rango 0.5 < q ≤ 1, se escoge el individuo más apto o en caso contrario se escoge el menos apto. 2.2.2.2 Algoritmos de selección determinísticos Dependiendo del número de veces que se tomen los mejores y peores individuos las distintas variaciones en este tipo de algoritmos permiten hacer una búsqueda más intensiva en cierto lugar del espectro (por ejemplo si se seleccionan muchas más veces aquellos con mejor valor de ajuste) o que se reparta la búsqueda en todo el dominio.  Selección por torneo determinístico: Al igual que en el caso probabilístico este algoritmo se basa en hacer comparaciones entre individuos, seleccionando a un número p de individuos (generalmente se escoge p=2 para hacer comparaciones dos a dos) de manera aleatoria. La diferencia radica en la forma de elegir el ganador, aquí directamente gana aquel cuyo valor de ajuste sea más alto. 2.2.3 Cruce Tal y como ocurre en la naturaleza una generación proviene de otra anterior, así una vez seleccionados los individuos éstos han de ser recombinados para producir la descendencia que se insertará en la siguiente generación. El operador de cruce equivale a una reproducción de tipo sexual en la naturaleza. Se trabajan con probabilidades, siendo éstas de gran importancia pues independientemente del algoritmo un alto porcentaje de cruce hace que el algoritmo tienda a perder rápidamente heterogeneidad y, por tanto, es conveniente dejar parte de la población sin cruce para conservar diversidad y evitar converger hacia óptimos locales.  Cruce basado en un punto (comúnmente conocido como SPX, Single Point Exchange): Los dos individuos seleccionados como progenitores son recombinados por medio de la selección de un único punto de corte seleccionado aleatoriamente. El resultado será la misma información a la izquierda pero intercambiarán el contenido que se encuentran a la derecha.  Cruce de doble punto (comúnmente conocido como DPX, Double Point Crossover): Los dos individuos seleccionados como progenitores son recombinados por medio de dos cortes no coincidentes, garantizando que se originen tres segmentos. Por normal general para generar los individuos resultantes se escoge el segmento central de uno de los individuos y los segmentos de cola del otro. Fundamentos Teóricos 14 se encarga de ejecutar los operadores evolutivos (Selección, Cruce, Mutación) y los demás procesos esclavos son los encargados de evaluar la funciones de fitness de cada individuo (Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning., 1989). El rendimiento es superior a un algoritmo genético en serie para complejos pero puede presentar problemas de convergencia prematura. 2.3.2.3 Algoritmo genético paralelo de grano fino (o Modelo Celular) El algoritmo genético de grano fino es un modelo que asigna a cada elemento de procesamiento (EP) un único individuo y dónde la evaluación se realiza de forma simultáneamente para todos los individuos. La selección, reproducción y cruce se realiza de forma local con un reducido número de vecinos. Esta conectividad entre individuos vecinos aumenta la difusión de individuos aptos, pero convierte a la población susceptible a una convergencia prematura ya que, con el tiempo, se forman grupos homogéneos genéticamente debido a una lenta difusión de individuos. Este modelo celular limita las interacciones, por lo que se ve afectado en el rendimiento. 2.4 El problema de las N Reinas En este apartado se presenta el problema de las N Reinas, un problema tipo de combinatoria computacional que se va a utilizar para testear diferentes técnicas de paralelización de los algoritmos genéticos basados en islas. El problema de las N reinas es un problema típico de combinatoria, formulado por primera vez por el ajedrecista Max Bezzel y publicado en Septiembre de 1848 en la revista de ajedrez alemana Schachzeitung (Campbell, 1977) bajo el nombre de: “Problema de las ocho reinas”. Durante este capítulo se estudiará el problema aumentado a un espacio N, es decir, el problema va a consistir en colocar N reinas sobre un tablero cuadrado de ajedrez de NxN subdivisiones, de forma que ninguna reina amenace a otra reina. Una reina amenaza a otra si comparte fila, columna o diagonal con otra reina. Este tipo de problema tiene una complejidad tal que una búsqueda de todas las posibles combinaciones implicaría un total de N! distintas posibilidades. A modo de ejemplo, en el problema clásico propuesto de ocho reinas, requeriría un tablero 8x8 y por tanto habría un total de 8! = 4320 distintas posibilidades. De todas estas posibilidades tendríamos que quedarnos con aquellas que cumplieran la condición de no amenaza, que son únicamente 92 de ellas. A la vista de este fácil cálculo se deduce que atacar un problema de estas dimensiones con una búsqueda secuencial no tiene sentido y es por ello que vamos a abordarlo a continuación mediante el empleo de Algoritmos Genéticos. 2.4.1 Inicialización. Problema de las N Reinas. El primer paso para inicializar una población es elegir una codificación adecuada. Para ello, hay que recordar que una de las condiciones de no amenaza es que tanto en cada fila, como en cada columna, ha de existir una única reina. Por lo tanto la codificación que se elige es un vector S = (𝑋1,𝑋2,…,𝑋𝑛) tal que cada 𝑋𝑖 va a representar una columna en la que se coloca la reina de la fila i. Al elegir esta representación ya nos aseguramos una de las condiciones de no amenaza, pues habrá una entrada de la tupla por fila, es decir una reina por fila del tablero. Para asegurar otra de las condiciones de no amenaza, hemos de codificar el problema de forma que los valores de S sean una permutación de la tupla (1,2,…N), de esta forma es seguro que nunca más de una reina estará en una misma columna. Queda solucionar la última restricción para garantizar que no haya amenaza, dos reinas no han de compartir diagonal. Dos reinas comparten diagonal si para un par de posiciones del vector S = (𝑋1,𝑋2,…,𝑋𝑛) se cumple que comparten mismo valor para (𝑓𝑖𝑙𝑎−𝑐𝑜𝑙𝑢𝑚𝑛𝑎) o bien para (𝑓𝑖𝑙𝑎 + 𝑐𝑜𝑙𝑢𝑚𝑛𝑎). 15 15 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi 2.4.2 Selección. Problema de las N Reinas. Para el desarrollo de este proyecto, se ha optado por una Selección por torneo probabilístico, con tres individuos distintos como participantes en cada torneo. 2.4.3 Cruce. Problema de las N Reinas. Ya hemos visto en el epígrafe 2.4.1 que en nuestro algoritmo genético vamos a tener una población cuyos individuos van a ser vectores S = (𝑋1,𝑋2,…,𝑋𝑛) dónde cada valor cada 𝑋𝑖 será una permutación de la tupla (1,2,…N). Por lo tanto, se han de elegir con especial cuidado las operaciones de cruce y mutación adecuadas ya que se ha de tener en cuenta que cada individuo es una permutación de (1,2,…N) y lo deberá seguir siendo incluso después de aplicar dichos operadores. El operador cruce que se va a usar es el llamado cruce por emparejamiento parcial (comúnmente conocido como PMX, o Partially Mapped Crossover) cuyo funcionamiento es el siguiente (Larrañaga, Kuijpers, Murga, & Dizdarevic, 1999).  Se eligen dos puntos de corte aleatorios  Se copian, en los hijos, las subcadenas comprendida entre dichos puntos de corte, es decir la subcadena del padre uno se copia en la subcadena del hijo dos. La subcadena del padre dos se copia en la subcadena del primer uno. Figura 2-9. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Primer paso: Copia de la subcadena en la descendencia.  A continuación se rellena el resto de las celdas de los hijos, de izquierda a derecha. Para ello se siguiendo la siguiente metodología o Se copia el valor de la celda del padre i en el hijo i. o Si el valor de la celda del padre ya existe en la subcadena que ha sido copiada en el paso anterior se sustituye por el valor asociado al otro hijo. En el ejemplo de la figura 2-10 el primer valor a copiar en el hijo uno sería „1‟, pero como dicho valor ya ha sido copiado anteriormente, se coge el valor asociado que tenga el hijo dos, que en el caso del ejemplo es „4‟. Fundamentos Teóricos 16 Figura 2-10. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Segundo paso: Rellenar las demás celdas. Caso en que una celda ya esté en la subcadena central (Celda #1) o Otro caso que se puede ver en el ejemplo sería el caso de la última celda del hijo uno, que queda recogida en la figura 2-11, ya que las celdas segunda, tercera y séptima se pueden coger sin problema del primer padre. La última celda del padre uno es „8‟, pero este valor ya aparece dentro del hijo 1 y también lo hace su par con el hijo dos, que sería „6‟. En este caso se coge el par de „6‟ en el hijo uno, que sería „5‟. Figura 2-11. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Segundo paso: Rellenar las demás celdas. Caso en que dos celdas ya estén en la subcadena central. (Celda #8) o Se procede de nuevo de igual manera con el segundo hijo, pero intercambiado los papeles de los padres. Figura 2-12. Esquema simple representando un ejemplo de cruce por emparejamiento parcial. Tercer paso: Repetir el segundo paso con el segundo hijo. Representación final. 17 17 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi 2.4.4 Mutación. Problema de las N Reinas El operador usado para este problema es muy simple, tan sólo hay que aplicar la mutación como un intercambio entre dos valores y así se mantiene la restricción de formato correctamente formado para el individuo. 2.4.5 Evaluación. Problema de las N Reinas La función de fitness es la encargada de determinar lo cerca que está cada una de las soluciones de ser una solución válida. Una solución es válida cuando cumple tres condiciones de no ataque, a recordar: Una reina no puede compartir fila con otra reina, condición que se cumple independientemente de la función fitness tal y como se ha codificado el problema (epígrafe 2.4.1), una reina no puede compartir columna con otra reina, condición que se cumple independientemente de la función fitness tal y como se ha codificado el problema y, por último, una reina no puede compartir diagonal con otra reina. Esta última condición no la hemos abarcado hasta ahora por ningún operador genético y será la función fitness quien va a determinar si una solución es buena, que será si, y sólo si, se cumple esta condición de no compartir diagonal. Tal y como se dijo en el epígrafe 2.4.1 la condición de compartición de diagonal se da si para un par de posiciones del vector S = (𝑋1,𝑋2,…,𝑋𝑛) se cumple que comparten mismo valor para (fila-columna) o bien para (fila + columna). Por lo tanto, en la función de evaluación se considera el valor de fitness de una solución como el número de ataques en diagonal. A más conflictos en diagonal peor será la solución y solamente si el número de conflictos es 0, el individuo es solución válida. Fundamentos Teóricos 18 19 3 HARDWARE El objetivo de este capítulo es describir los dispositivos físicos utilizados en el proyecto, proporcionando descripción, configuración y montaje de los mismos. 3.1 Introducción a Raspberry Pi Raspberry Pi fue creada por la Raspberry Pi Foundation en 2012 bajo dirección del británico, actual CEO de Raspberry Pi (Trading) Ltd., Eben Upton con la idea original de ser un dispositivo destinado a ser usado con fines de enseñanza y promoción de ciencia básica de computación en escuelas y colegios de Reino Unido (Lyons, 2015). Su popularidad aumentó rápidamente principalmente por su bajo coste, que oscilaba entre las 17 y 23 libras, así como su eficiencia, durabilidad y accesibilidad para modificar y crear proyectos. Se trata además de un dispositivo open hardware (Red Hat, 2010), a excepción del chip primario Broadcomm SoC (siglas para 'System on a Chip'), el cual se encarga de muchas de las funciones principales de la placa – CPU, gráficos, memoria, controlador USB, etc. El software que emplea es, también, open source. Originalmente se crearon 2 imágenes que podrían instalarse fácilmente en una tarjeta SD que luego actuaría como el sistema operativo en el dispositivo, una de ellas se basó en Debian, un popular sistema operativo Linux, y se llamó Raspbian, la otra se llamó RaspBMC basada en Kodi cuyo objetivo era utilizar la Raspberry Pi como un media center. 3.2 Distintos modelos de Raspberry Desde su fundación en 2012 hasta hoy día Raspberry ha lanzado hasta la tercera versión de Raspberry (Raspberry 3), en distintos modelos, aunque siguen produciendo modelos antiguos ya que por lo general las distintas versiones son compatibles entre sí 1 . 3.2.1 Raspberry de primera generación Originalmente había dos modelos, A y B, con diferentes capacidades y especificaciones. Figura 3-1. Raspberry de primera generación. Modelo A. 1 A día de hoy, en su p{gina web el modelo m{s antiguo a la venta es Modelo 1 en sus versiones A+ y B+, no así su primer modelo A y B cuya Entrada/Salida de Propósito General (GPIO) era de tan solo 26 pines y no garantiza compatibilidad con modelos modernos Hardware 20 Raspberry Modelo A tenía una capacidad de 256MB de memoria RAM, un único puerto USB, salida de vídeo vía HDMI (con resoluciones desde 640×350 hasta 1920×1200 con compatibilidad de varios estándares PAL y NTSC) y vídeo RCA. Su precio era inferior al modelo B, así como su consumo. Raspberry modelo B incluía un Segundo Puerto USB, así como un Puerto Ethernet para conexión a red y 512MB de memoria RAM. Figura 3-2. Raspberry de primera generación. Modelo B. Ambos modelos poseen una versión revisada y actualizada, rebautizada como A+ y B+ respectivamente. Presentan mejoras tales como un mayor número de puertos USB, una mejora en el consumo de potencia y lector MicroSDHC en vez de SDHC. 21 21 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Tabla 1. Comparación entre los distintos modelos Raspberry de primera generación. Modelo A Modelo A+ Modelo B Modelo B+ Velocidad CPU 700 MHz 700 MHz 700 MHz 700 MHz Memoria 256mb 256mb 512mb 512mb Puertos USB 1 1 2 4 GPIO 8 17 8 17 SD/MMC SD microSD SD microSD Capacidad de corriente recomendada 700mA 700mA 1.2A 1.8A Máx. consumo corriente periférica USB 500mA 500mA 500mA 600mA Corriente activa típica de la placa base 200mA 180mA 500mA 330mA Tamaño (mm) 85.60 × 56.5 65 × 56.5 85.60 × 56.5 85.60 × 56.5 3.2.2 Raspberry de segunda generación La segunda generación de Raspberry Pi fue lanzada originalmente en 2015. Ésta versión 2 estrena un procesador ARM Cortex-A7 de cuatro núcleos a diferencia del ARM1176JZF-S de un solo núcleo de su primera versión a una, con lo que se consigue un aumento de la velocidad de procesamiento de 700 MHz en su primera versión a una velocidad de procesamiento de 900MHz. Esta versión mantiene la lectura de MicroSDHC de la versión A+ y B+. Otras mejoras notorias son la capacidad de memoria RAM, que alcanza 1GB y el número de puertos USB, que aumenta a cuatro. 3.2.3 Raspberry de tercera generación Raspberry modelo 3 fue lanzado originalmente en 2016, mejora nuevamente el procesador, esta vez un ARM Cortex-A53, que con cuatro núcleos permite alcanzar una velocidad de 1,200MHz. Por primera vez, este modelo incluye de fábrica módulo Wi-Fi 802.11n y módulo Bluetooth 4.1 Durante el año 2018 Raspberry también ha sacado modelos mejorados Raspberry 3 A+ y Raspberry B+. Raspberry B+ goza del procesador Arm Cortex-A53 de cuatro núcleos que le permite alcanzar velocidad de procesamiento 1.4GH Raspberry 3 A+ tiene el procesador Arm Cortex-A53 al igual que el modelo B+, pero al igual que el modelo A original solamente tiene 1 puerto USB y no tiene puerto Ethernet. La ausencia de dichos puertos que su forma sea más pequeña y cuadrada en comparación con RPi 3B+. Sus precios de mercado son de $35 en su versión A+ y $25 en su versión B+. Hardware 22 Tabla 2. Comparación entre los modelos A+, B y B+ de Raspberry de tercera generación. Raspberry Pi 3 B Raspberry Pi 3 B+ Raspberry Pi 3 A+ Velocidad CPU 1.2 GHz 1.4 GHz 1.4 GHz Memoria 1 GB 1 GB DDR2 512 MB DDR2 Puertos USB 4 4xUSB 2.0 1xUSB 2.0 Ethernet SI Gigabit Over USB 2.0 NO WiFi 802.11n 2.4GHz y 5GHz 802.11 b/g/n/ac 2.4GHz y 5GHz 802.11 b/g/n/ac GPIO 40 40 40 SD/MMC microSD microSD microSD Capacidad de corriente recomendada 2.5A 2.5A 2.5A Máx. consumo corriente periférica USB 1.2A 1.2A Limitado únicamente por fuente de alimentación, placa y conector. Corriente activa típica de la placa base 400mA 500mA 350mA Tamaño (mm) 85.6 × 56.5 85.6 × 56.5 65 x 56 3.3 Material y montaje usado para la realización del proyecto. Para la realización de este proyecto se ha decidido usar tres dispositivos Raspberry Pi Modelo 3 B, proporcionados por el departamento de Ingeniería Electrónica de la Escuela Técnica Superior de Ingeniería de la Universidad de Sevilla. Aprovechando una de las grandes ventajas del modelo 3 de Raspberry, que es la inclusión del módulo Wi-Fi con la placa se ha reducido la complejidad del montaje de las Raspberry Pi y su configuración en red. Por tanto para el montaje del escenario únicamente se ha necesitado de los siguientes periféricos y materiales:  Una fuente de alimentación Micro USB de, al menos, 5V y cuyo amperaje dependerá de los periféricos que conectemos a la Raspberry: el modelo B consume unos 1200mA en reposo, sin ningún tipo de periférico conectado. o Para el desarrollo de este proyecto se ha usado una fuente de 5.1V y 2.5A.  Únicamente para la configuración y para el mantenimiento se van a hacer uso de otros periféricos, como un ratón y un teclado que únicamente han de conectarse al puerto USB, y una pantalla conectada mediante un cable HDMI para HDTV y haciendo uso del puerto HDMI. o Para el desarrollo de este proyecto se ha usado un cable genérico HDMI, un ratón y teclado 23 23 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi inalámbricos genéricos que funcionan con el uso de un solo puerto USB y un monitor HDTV.  Una tarjeta micro SD para cada Raspberry con una imagen pre-cargada de NOOBS, un asistente de instalación que incluye de fábrica sistema operativo Raspbian, pero que incluye también Pidora, OpenELEC, OSMC, RISC OS, Arch Linux y Windows 10 IOT Core. Pi. Software 30 tareas tanto de tratamiento de datos, como visualización, cálculo numérico y simbólico entre otras aplicaciones específicas. Todo ello arropado por una comunidad de usuarios que, debido a la filosofía código abierto, son proclives a compartir su código y mejorarlo entre todos. 31 5 METODOLOGÍA Para llevar a cabo los objetivos planteados en este proyecto se ha seguido la siguiente metodología a partir del diseño del experimento que se describe: Lo primero ha sido llevar a cabo tanto el montaje de los dispositivos Raspberry, como su posterior configuración conforme a lo descrito en el epígrafe 3.3. Lo siguiente ha consistido en la implementación del código necesario para realizar ensayos de forma que solucionemos el problema de las N Reinas, desarrollado en el epígrafe 2.4, de las siguientes formas: 1. Haciendo uso de algoritmo genético simple que nos proporciona la librería DEAP, en una sola máquina y de forma secuencial. Con una única población total. 2. Haciendo uso de algoritmo genético simple que nos proporciona la librería DEAP y haciendo uso de la paralelización que nos proporciona la librería SCOOP, de nuevo con una única población total. 3. Haciendo uso de algoritmo genético simple que nos proporciona la librería DEAP e implementando un modelo de islas de forma que se va a dividir la población total en diversas subpoblaciones y estableciendo un flujo de migración entre las mismas. 4. Haciendo uso de algoritmo genético simple que nos proporciona la librería DEAP e implementando un modelo de islas de forma que se divida la población total en diversas subpoblaciones, estableciendo un flujo de migración entre las mismas y haciendo uso de las capacidades de la librería SCOOP para paralelizar la carga de trabajo entre varios workers. A continuación, se ha planteado una serie de ensayos consistentes en la resolución de cinco escenarios, que hemos llamado A, B, C, D y E, tales que:  Escenario A: se resuelve el problema de las N Reinas bajo la condición de que el tablero tenga unas dimensiones 20x20 y que el algoritmo genético va a trabajar con una población total de 300 individuos, una probabilidad de cruce de 0.5 y una probabilidad de mutación de 0.2.  Escenario B: se resuelve el problema de las N Reinas bajo la condición de que el tablero tenga unas dimensiones 40x40 y que el algoritmo genético va a trabajar con una población total de 300 individuos, una probabilidad de cruce de 0.5 y una probabilidad de mutación de 0.2.  Escenario C: se resuelve el problema de las N Reinas bajo la condición de que el tablero tenga unas dimensiones 60x60 y que el algoritmo genético va a trabajar con una población total de 300 individuos, una probabilidad de cruce de 0.5 y una probabilidad de mutación de 0.2.  Escenario D: se resuelve el problema de las N Reinas bajo la condición de que el tablero tenga unas dimensiones 80x80 y que el algoritmo genético va a trabajar con una población total de 300 individuos, una probabilidad de cruce de 0.5 y una probabilidad de mutación de 0.2.  Escenario E: se resuelve el problema de las N Reinas bajo la condición de que el tablero tenga unas dimensiones 100x100 y que el algoritmo genético va a trabajar con una población total de 300 individuos, una probabilidad de cruce de 0.5 y una probabilidad de mutación de 0.2. Estos escenarios van a resolverse en los siguientes casos (Tabla 3) 1. Un ensayo secuencial sin SCOOP: Como su nombre indica no se va a hacer uso de la librería SCOOP, por lo tanto se va a resolver el problema de las N Reinas usando un algoritmo evolutivo simple sin paralelización de carga. Esto implica que únicamente vamos a hacer uso de un dispositivo Raspberry Pi. 2. Un ensayo haciendo uso del modelo de islas, pero sin hacer uso de SCOOP: La población total, 300 en todos los escenarios, se dividirá en subpoblaciones asignadas a cada isla, 3 en todos los escenarios, por lo tanto cada isla contará con un total de 100 individuos. No obstante, en este caso no paralelizaremos el algoritmo, por lo tanto será un único ensayo en un dispositivo Raspberry Pi. 3. Seis ensayo secuenciales haciendo uso de SCOOP. En esta serie de ensayos se va a hacer uso tanto de Metodología 32 la librería DEAP como SCOOP, por lo tanto todos ellos van a paralelizar la carga. En estos ensayos se va a usar tanto una, dos y tres dispositivos Raspberry Pi. En el caso de una única Raspberry no distribuiremos la carga en red porque el experimento será en local. En todos estos casos vamos a realizar el ensayo en dos vertientes, distribuyendo la carga en dos workers por dispositivo RPi o en cuatro. 4. Seis ensayos haciendo uso del modelo de islas y SCOOP: La población total, 300 en todos los escenarios, se dividirá en subpoblaciones asignadas a cada isla, 3 en todos los escenarios, por lo tanto cada isla contará con un total de 100 individuos. Nuevamente, en estos ensayos se va a usar tanto una, dos y tres dispositivos Raspberry Pi. En el caso de una única Raspberry no distribuiremos la carga en red porque el experimento será en local. En todos estos casos vamos a realizar el ensayo en dos vertientes, distribuyendo la carga en dos workers por dispositivo RPi o en cuatro. Estos 14 casos planteados se van a llevar a cabo en los cinco escenarios, descritos anteriormente y realizando un total de 70 casos. Puesto que el tiempo de ejecución y los resultados obtenidos varían en cada situación de forma impredecible, se ha optado que por cada uno de estos 70 ensayos se repita 5 veces, elevando el número de ejecuciones a 350. Para el posterior análisis de resultados se han recogido los valores medios de cada una de estas cinco repeticiones. Tabla 3. Ensayos realizados por escenario Modelo AG Paralelo Distribuido Nº RPi Workers Modelo Secuencial sin Scoop NO NO 1 Modelo Secuencial con Scoop SI NO 1 2 4 SI SI 2 2 4 3 2 4 Modelo de islas sin Scoop NO NO 1 Modelo de islas con Scoop SI NO 1 2 4 SI SI 2 2 4 3 2 4 33 33 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi 5.1 Código escrito Para la realización de este trabajo se ha realizado una batería de pruebas en los que se hacen uso de cuatro scripts escritos en Python que representan las cuatro técnicas que van a ser evaluadas y en los que, con el fin de adecuarse a los diferentes escenarios, aceptan como entrada los diferentes parámetros que formarán el algoritmo genético. Para los casos que usen SCOOP se han escrito ficheros hostfile que se pasan a la librería y sirven para designar los Brokers y Workers que se van a desplegar. Como se comentó en la introducción de este capítulo por cada escenario se van a resolver 14 casos, cada uno repetido cinco veces. Para automatizar este proceso, se han realizado diferentes scripts en shellscript. Además, se ha diseño un script más en Python que calcula las medias de estas cinco repeticiones por caso. 5.1.1 Scripts en Python  Ensayo_Sec_NoScoop.py: Script que acepta por parámetro de entrada la dimensión N del tablero, el número de generaciones que van a ser evaluadas, el tamaño de la población generacional, el nombre del fichero donde se van a guardar los resultados, la probabilidad de cruce y la probabilidad de mutación. La peculiaridad de este script respecto al siguiente que se describe a continuación es que no hace uso de la librería SCOOP y por lo tanto su ejecución se realiza secuencialmente, de forma local en la misma máquina en la que se ejecuta. En el fichero de resultados se anota un array con las generaciones que se han muestreado, un array con el mejor valor encontrado en cada generación y finalmente el tiempo de ejecución total.  Ensayo_Sec_Scoop.py: Script que acepta por parámetro de entrada la dimensión N del tablero, el número de generaciones que van a ser evaluadas, el tamaño de la población generacional, el nombre del fichero donde se van a guardar los resultados, la probabilidad de cruce y la probabilidad de mutación. Para ejecutar este Script que, como su propio nombre indica, hará uso de paralelización de trabajo mediante SCOOP se ha de señalizar la opción -- hosfile por línea de comandos, tras la cual le añadiremos el fichero hostfile personalizado con las direcciones IP de las distintas RPi de las que haremos uso y en las cuales distribuiremos la carga de la ejecución. En el fichero de resultados se anota un array con las generaciones que se han muestreado, un array con el mejor valor encontrado en cada generación y finalmente el tiempo de total.  Ensayo_Islas_NoScoop.py: Script que acepta por parámetro de entrada la dimensión N del tablero, el número de generaciones que van a ser evaluadas, el tamaño de la población generacional, el nombre del fichero donde se van a guardar los resultados, el número de islas en el que se va a dividir la población, la frecuencia en que va a ocurrir la migración, el número de individuos que van a migrar por cada migración, la probabilidad de cruce y la probabilidad de mutación. La peculiaridad de este script respecto al siguiente que se describe a continuación es que no hace uso de la librería SCOOP y por lo tanto su ejecución se realiza secuencialmente, de forma local en la misma máquina en la que se ejecuta. En el fichero de resultados se anota un array con las generaciones que se han muestreado, que en este caso será una muestra por migración, un array con el mejor valor encontrado en cada generación y finalmente el tiempo de total.  Ensayo_Islas_NoScoop.py: Script que acepta por parámetro de entrada la dimensión N del tablero, el número de generaciones que van a ser evaluadas, el tamaño de la población generacional, el nombre del fichero donde se van a guardar los resultados, el número de islas en el que se va a dividir la población, la frecuencia en que va a ocurrir la migración, el número de individuos que van a migrar por cada migración, la probabilidad de cruce y la probabilidad de mutación. Nuevamente para la ejecución de este Script se hará uso de la opción -- hostfile, especificando el fichero que contiene las IPs de las RPi en las que se va a distribuir la carga junto al número de workers que operarán. En el fichero de resultados se anota un array con las generaciones que se han muestreado, que en este caso será una muestra por migración, un array con el mejor valor encontrado en cada generación y finalmente el tiempo de total.  HacerDatos.py: Este sencillo Script acepta dos parámetros de entrada: El nombre un archivo de resultados del que va a obtener datos y el nombre de un archivo nuevo a crear y en el que se van a guardar las medias del contenido del primer archivo. Por lo tanto en este script se calcula la media, Metodología 34 generación a generación, de los valores de fitness de todos los ensayos guardados en el archivo y también se calcula la media de los tiempos de cada ensayo y su desviación típica. Figura 5-1 Ejemplo de archivo de resultados generado por Ensayo_Isla_NoScoop.py 5.1.2 Scripts en shell Para la realización de todos los casos descritos en la introducción de este capítulo, se ha realizado una batería de scripts con las siguientes características.  Script_Sec_NoScoop_A.sh, Script_ Sec_NoScoop_B.sh, Script_ Sec_NoScoop_C.sh, Script_ Sec_NoScoop_D.sh, Script_ Sec_NoScoop_E.sh: Este ensayo se realiza en local, es decir no se necesita de ningún fichero hostfile. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Sec_NoScoop.py con las siguientes especificaciones según el escenario: o Script_Sec_NoScoop_A) Un tablero 20x20, a resolver en 100 generaciones con una población total de 300 individuos. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Sec_NoScoop_B) Un tablero 40x40, a resolver en 200 generaciones con una población total de 300 individuos. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Sec_NoScoop_C) Un tablero 60x60, a resolver en 300 generaciones con una población total de 300 individuos. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Sec_NoScoop_D) Un tablero 80x80, a resolver en 400 generaciones con una población total de 300 individuos. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Sec_NoScoop_E) Un tablero 100x100, a resolver en 500 generaciones con una población total de 300 individuos. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación.  Script_Islas_NoScoop_A.sh, Script_ Islas _NoScoop_B.sh, Script_ Islas _NoScoop_C.sh, Script_ Islas _NoScoop_D.sh, Script_ Islas _NoScoop_E.sh: Este ensayo se realiza en local, es decir no se necesita de ningún fichero hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Isla_NoScoop.py con las siguientes especificaciones según el escenario: 35 35 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi o Script_Isla_NoScoop_A) Un tablero 20x20, en 100 generaciones con una población de 3 islas con 100 individuos cada una. La frecuencia de migración será cada 5 generaciones y se intercambiará un volumen de 15 individuos por isla en cada migración. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Isla_NoScoop_B) Un tablero 40x40, en 200 generaciones con una población de 3 islas con 100 individuos cada una. La frecuencia de migración será cada 10 generaciones y se intercambiará un volumen de 15 individuos por isla en cada migración. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Isla_NoScoop_C) Un tablero 60x60, en 300 generaciones con una población de 3 islas con 100 individuos cada una. La frecuencia de migración será cada 15 generaciones y se intercambiará un volumen de 15 individuos por isla en cada migración. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Isla_NoScoop_D) Un tablero 80x80, en 300 generaciones con una población de 3 islas con 100 individuos cada una. La frecuencia de migración será cada 20 generaciones y se intercambiará un volumen de 15 individuos por isla en cada migración. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación. o Script_Isla_NoScoop_E) Un tablero 100x100, en 300 generaciones con una población de 3 islas con 100 individuos cada una. La frecuencia de migración será cada 25 generaciones y se intercambiará un volumen de 15 individuos por isla en cada migración. La probabilidad de cruce especificada para todo el problema es 0.5 para cruce y 0.2 para mutación.  Script_Sec_Scoop_A_1rpi.sh, Script_Sec_Scoop_B_1rpi.sh, Script_Sec_Scoop_C_1rpi.sh, Script_Sec_Scoop_D_1rpi.sh, Script_Sec_Scoop_E_1rpi.sh: Este ensayo se realiza de forma distribuida, por lo tanto sí necesitará de ficheros hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Sec_Scoop.py con los mismos parámetros, según el escenario que corresponda, que los especificados en el fichero Script_Sec_NoScoop_A/ Script_Sec_NoScoop_B/ Script_Sec_NoScoop_C/ Script_Sec_NoScoop_D/ Script_Sec_NoScoop_E. Los archivos de resultados van a anotar lo siguiente: o Resultados_Sec_Scoop_A_1RPI_2Wor: En este archivo de resultados se anota la salida cuando el fichero hostfile especifica una única máquina con dos workers. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. o Resultados_Sec_Scoop_A_1RPI_4Wor: En este archivo de resultados se anota la salida cuando el fichero hostfile especifica una única máquina con cuatro workers. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares.  Script_Sec_Scoop_A_2rpi.sh, Script_Sec_Scoop_B_2rpi.sh, Script_Sec_Scoop_C_2rpi.sh, Script_Sec_Scoop_D_2rpi.sh, Script_Sec_Scoop_E_2rpi.sh: Este ensayo se realiza de forma distribuida, por lo tanto sí necesitará de ficheros hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Sec_Scoop.py con los mismos parámetros, según el escenario que corresponda, que los especificados en el fichero Script_Sec_NoScoop_A/ Script_Sec_NoScoop_B/ Script_Sec_NoScoop_C/ Script_Sec_NoScoop_D/ Script_Sec_NoScoop_E. Los archivos de resultados van a anotar lo siguiente: o Resultados_Sec_Scoop_A_2RPI_2Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica dos máquinas con dos workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. o Resultados_Sec_Scoop_A_2RPI_4Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica dos máquinas con cuatro workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares.  Script_Sec_Scoop_A_3rpi.sh, Script_Sec_Scoop_B_3rpi.sh, Script_Sec_Scoop_C_3rpi.sh, Script_Sec_Scoop_D_3rpi.sh, Script_Sec_Scoop_E_3rpi.sh: Este ensayo se realiza de forma Metodología 36 distribuida, por lo tanto sí necesitará de ficheros hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Sec_Scoop.py con los mismos parámetros, según el escenario que corresponda, que los especificados en el fichero Script_Sec_NoScoop_A/ Script_Sec_NoScoop_B/ Script_Sec_NoScoop_C/ Script_Sec_NoScoop_D/ Script_Sec_NoScoop_E. Los archivos de resultados van a anotar lo siguiente: o Resultados_Sec_Scoop_A_3RPI_2Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica tres máquinas con dos workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. o Resultados_Sec_Scoop_A_3RPI_4Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica tres máquinas con dos workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares.  Script_Isla_Scoop_A_1rpi.sh, Script_Isla_Scoop_B_1rpi.sh, Script_Isla_Scoop_C_1rpi.sh, Script_Isla_Scoop_D_1rpi.sh, Script_Isla_Scoop_E_1rpi.sh: Este ensayo se realiza de forma distribuida, por lo tanto sí necesitará de ficheros hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Isla_Scoop.py con los mismos parámetros, según el escenario que corresponda, que los especificados en el fichero Script_Isla_NoScoop_A/ Script_Isla_NoScoop_B/ Script_Isla_NoScoop_C/ Script_Isla_NoScoop_D/ Script_Isla_NoScoop_E. Los archivos de resultados van a anotar las siguientes especificaciones. o Resultados_Isla_Scoop_A_1RPI_2Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica una única máquina con dos workers. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. o Resultados_Ensayo_IslaBest_A_1RPI_4Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica una única máquina con cuatro workers. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares.  Script_Isla_Scoop_A_2rpi.sh, Script_Isla_Scoop_B_2rpi.sh, Script_Isla_Scoop_C_2rpi.sh, Script_Isla_Scoop_D_2rpi.sh, Script_Isla_Scoop_E_2rpi.sh: Este ensayo se realiza de forma distribuida, por lo tanto sí necesitará de ficheros hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Isla_Scoop.py con los mismos parámetros, según el escenario que corresponda, que los especificados en el fichero Script_Isla_NoScoop_A/ Script_Isla_NoScoop_B/ Script_Isla_NoScoop_C/ Script_Isla_NoScoop_D/ Script_Isla_NoScoop_E. Los archivos de resultados van a anotar las siguientes especificaciones. o Resultados_Isla_Scoop_A_2RPI_2Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica dos máquinas con dos workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. o Resultados_Ensayo_IslaBest_A_2RPI_4Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica dos máquinas con cuatro workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares.  Script_Isla_Scoop_A_3rpi.sh, Script_Isla_Scoop_B_3rpi.sh, Script_Isla_Scoop_C_3rpi.sh, Script_Isla_Scoop_D_3rpi.sh, Script_Isla_Scoop_E_3rpi.sh: Este ensayo se realiza de forma distribuida, por lo tanto sí necesitará de ficheros hostfile para ejecutarlo. Se trata de una iteración dónde se va a ejecutar 5 veces el script Ensayo_Isla_Scoop.py con los mismos parámetros, según el escenario que corresponda, que los especificados en el fichero Script_Isla_NoScoop_A/ Script_Isla_NoScoop_B/ Script_Isla_NoScoop_C/ Script_Isla_NoScoop_D/ Script_Isla_NoScoop_E. Los archivos de resultados van a anotar las siguientes especificaciones. o Resultados_Isla_Scoop_A_3RPI_2Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica tres máquinas con dos workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. 37 37 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi o Resultados_Ensayo_IslaBest_A_3RPI_4Wor: En este archivo de resultados se ha anotado la salida cuando el fichero hostfile especifica tres máquinas con cuatro workers cada una. De forma análoga, los escenarios B, C, D y E generarán ficheros de resultados similares. 5.1.3 Ficheros hostfile Para poder realizar los distintos ensayos de manera distribuida haciendo uso de SCOOP se le ha de proporcionar mediante el comando --hostfile un archivo con una lista de los workers que se van a desplegar. A continuación, se listan los distintos ficheros hostfile de los que se han hecho uso y su contenido.  hostfile_1rpi_2worker 192.168.1.49 2  hostfile_1rpi_4worker: 192.168.1.49 4  hostfile_2rpi_2worker: 192.168.1.49 2 192.168.1.51 2  hostfile_2rpi_4worker: 192.168.1.49 4 192.168.1.51 4  hostfile_3rpi_2worker: 192.168.1.49 4 192.168.1.51 4 192.168.1.50 4  hostfile_3rpi_4worker: 192.168.1.49 4 192.168.1.51 4 192.168.1.50 4 Metodología 38 39 6 RESULTADOS En este capitulo se presenta un análisis de los resultados recogidos tras la ejecución de los casos descritos en el capítulo anterior. Comencemos por el escenario A. Recordemos, este escenario cuenta con un array de solución de tan sólo 20 entradas (ya que el tablero es 20x20), y una población total de 300 individuos así como un tiempo generacional de 100 generaciones. De la tabla 4,5 y 6 podemos concluir con algunas consideraciones importantes.  Una de ellas sería que no existe una diferencia apreciable en términos de tiempo medio de ejecución (sólo un 5.26% de incremento), en el caso de no usar SCOOP, entre usar un modelo de población total o un modelo de subpoblaciones con migración.  Un resultado importante (y que se va a dar en todos los escenarios) es que aunque tengamos 2 o 4 workers por dispositivo e independientemente de tener una, dos o tres Raspberry Pi puestas a trabajar, en el caso de usar un algoritmo genético de población total con SCOOP, el tiempo no varía en gran medida. En este escenario se consigue, apenas, una reducción de tiempo de ejecución del 9.62% entre los dos casos más extremos, 1RPi con 2 Workers frente a 3RPi con 4Workers por dispositivo.  Otra consideración a destacar es, si se observa en las filas de método con islas y SCOOP, que conforme se va distribuyendo en más workers, el tiempo medio de ejecución se va reduciendo. Lo cual quiere decir que al contrario que con el modelo secuencial, aquí SCOOP tiene algo más para paralelizar. Al dividir la población total en subpoblaciones casi independientes, estamos dando más libertad a la paralelización y explotamos más eficazmente las prestaciones de SCOOP. En este escenario se consigue una reducción en el tiempo de ejecución en un 42.42% entre los casos más extremos, 1RPi con 2 Workers frente a 3RPi con 4Workers por dispositivo.  Finalmente, observar que en el caso de ejecutar el algoritmo con modelo de islas sin paralelización obtenemos un tiempo medio de unos 20 segundos por ejecución mientras que si nos vamos al extremo opuesto, a la máxima distribución (3 Raspberry Pi a 4 Worker por dispositivo, modelo de islas paralelizado con SCOOP), observamos un tiempo medio de unos 38 segundos. Es decir se emplea un 90% más de tiempo que si no hubiéramos usado la librería SCOOP. o De manera análoga si comparamos entre ejecutar el algoritmo de población total sin paralelización frente al modelo de población total con SCOOP, obtenemos que se emplea un 168.42% más de tiempo en este segundo modelo. Método 1 RPi 1 Worker/Dispositivo 2 Workers/Dispositivo 4 Workers/Dispositivo Tiempo medio Desv. std. Tiempo medio Desv. std. Tiempo medio Desv. std. Secuencial 19.74775 0.60309 - - - - Secuencial (Scoop) - - 57.84502 1.03282 52.92366 0.48318 Islas (No Scoop) 20.43486 0.38390 - - - - Islas (Scoop) - - 47.32385 0.61884 38.71383 0.43921 Tabla 4. Tabla de tiempos de ejecución, en segundos, de Escenario A. 1 Dispositivo Raspberry. Resultados 46 Con respecto a las últimas tablas (16,17 y 18) pertenecientes al escenario E, que recordemos cuenta con un array de solución 100 entradas (ya que el tablero es 100x100), una población total de 300 individuos y se resuelve en 500 generaciones, podemos comentar lo siguiente:  Al igual que observamos en los anteriores escenarios, en el caso de no usar SCOOP, el tiempo medio de ejecución varía mínimamente (tan sólo un 0.68% de incremento) entre usar un modelo de población total o subpoblaciones con migración.  En el caso de usar un algoritmo genético de población total con SCOOP, se detecta una diferencia en los tiempos medios de 13.1% entre los casos más extremos (1RPi con 2 Workers frente a 3RPi con 4Workers por dispositivo) que es ligeramente superior a la que se observó en escenarios anteriores.  Con el método de islas y haciendo uso de SCOOP se observa nuevamente que conforme se va distribuyendo la carga en más workers, el tiempo medio de ejecución se va reduciendo. En este escenario se disminuye el tiempo medio de ejecución en un 33.04% entre los casos más extremos.  En este escenario se observa que se incrementa la diferencia de tiempos medios de cómputo entre ejecutar el algoritmo de modelo de islas sin paralelización alguna frente al modelo de islas con SCOOP en el caso más extremo. En este escenario, si paralelizamos, se disminuye el tiempo de ejecución un 23.73%. Esto quiere decir que: o Se sigue mejorando el tiempo al paralelizar la carga frente a realizarlo secuencialmente. o Si hacemos de manera análoga la comparación entre ejecutar el algoritmo sin paralelización frente al modelo de población total con SCOOP, obtenemos que paralelizando se emplea un 35.84% más de tiempo. Nuevamente en este escenario sigue la tendencia de los escenarios anteriores de recortar tiempo conforme el escenario tenga mayores dimensiones, pero siguen siendo unos tiempos mayores a los no paralelizados. Método 1 RPi 1 Worker/Dispositivo 2 Workers/Dispositivo 4 Workers/Dispositivo Tiempo medio Desv. std. Tiempo medio Desv. std. Tiempo medio Desv. std. Secuencial 293.820 1.58351 - - - - Secuencial (Scoop) - - 458.33676 6.53407 414.9073 6.55418 Islas (No Scoop) 295.91976 1.09551 - - - - Islas (Scoop) - - 336.5484 1.15108 250.46509 2.63758 Tabla 16. Tabla de tiempos de ejecución, en segundos, de Escenario E. 1 Dispositivo Raspberry 47 47 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Método 2 RPi 1 Worker/Dispositivo 2 Workers/Dispositivo 4 Workers/Dispositivo Tiempo medio Desv. std. Tiempo medio Desv. std. Tiempo medio Desv. std. Secuencial - - - - - - Secuencial (Scoop) - - 422.83656 7.31842 412.2308 6.42537 Islas (No Scoop) - - - - - - Islas (Scoop) - - 54.13818 2.16556 231.5918 2.24818 Tabla 17. Tabla de tiempos de ejecución, en segundos, de Escenario E. 2 Dispositivos Raspberry. Método 3 RPi 1 Worker/Dispositivo 2 Workers/Dispositivo 4 Workers/Dispositivo Tiempo medio Desv. std. Tiempo medio Desv. std. Tiempo medio Desv. std. Secuencial - - - - - - Secuencial (Scoop) - - 405.62763 6 .857402 398.2811 7.55943 Islas (No Scoop) - - - - - - Islas (Scoop) - - 241.39071 4.16445 225.6373 4.68001 Tabla 18. Tabla de tiempos de ejecución, en segundos, de Escenario E. 3 Dispositivos Raspberry En la figura 6-1 podemos observar, de forma visual, curvas que representan la evolución de los tiempos medios de ejecución de los ensayos tanto sin paralelización (modelo de población total sin SCOOP y modelo de islas sin SCOOP) como aquellos paralelizados con 3RPi y 4Worker/Dispositivo (modelo de población total con SCOOP y modelo de islas con SCOOP) a lo largo de los diferentes escenarios planteados. Cada escenario quedaría identificado según las dimensiones del tablero. Resultados 48 Figura 6-1.Comparación entre tiempos medios de ejecución a lo largo de los cinco escenarios. Lo más reseñable de esta gráfica es que se puede identificar fácilmente el punto de inflexión que marca la diferencia entre aquellos casos en que se tarde más tiempo (o menos), a pesar de estar usando SCOOP y distribuir la población en subpoblaciones, que directamente no usar SCOOP (distribuir la carga). Dicho punto estaría en torno al escenario C (tablero 60x60, 300 generaciones), donde, como ya se ha comentado, se consigue emplear un 2.59% menos de tiempo medio al paralelizar. Otra anotación importante sería ver como en el caso de usar un modelo de población total y SCOOP los tiempos medio de ejecución son siempre los más altos. Se podría decir que SCOOP es una herramienta para paralelizar, pero no sabe paralelizar lo que no es paralelizable. Con esto último se quiere decir que al trabajar con una única población y al ser el algoritmo genético secuencial, se pierde más tiempo dialogando entre los workers, que tiempo de cómputo. Un último comentario sobre la figura 6-1 es que, como ya se ha reseñado en el análisis de las tablas anteriores, en el caso de no usar SCOOP, el tiempo medio de ejecución varía mínimamente entre los casos de usar un modelo de población total o un modelo de subpoblaciones con migración. Este hecho puede observarse en la superposición de las curvas secuencial sin SCOOP e islas sin SCOOP. 0 50 100 150 200 250 300 350 400 20 30 40 50 60 70 80 90 100 Tiempo ejecución (sg.) Dimensión N del Tablero (NxN) Comparación de tiempos medios de ejecución entre los cuatro modelos Secuencial sin Scoop Islas sin Scoop Secuencial con Scoop Islas con Scoop 49 49 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Figura 6-2. Comparación, en el Escenario A, de los mejores valores fitness encontrados. Tanto en la figura 6-2 como en la figura 6-3 se representa una comparación, entre los distintos modelos, de los valores de fitness encontrados a lo largo de un único escenario. Siendo representado el escenario A en la figura 6-2 y el escenario E en la figura 6-3. En líneas generales, se observa que el valor de fitness mejora, como es lógico, conforme aumenta el número de generaciones. También puede observarse como en el escenario E, donde el problema tiene una mayor dimensión y por tanto complejidad, que los valores de fitness decrementan exponencialmente de manera más clara que en escenario A. En cualquier caso, no existe diferencia significativa en cuanto a las medias de valores de fitness en los modelos analizados. 0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 010 20 30 40 50 60 70 80 90 100 Media Valor Función Fitness Nº de generaciones Comparación a lo largo de un ensayo de mejores valores fitness encontrados SecSinScoop IslaSinScoop SecConScoop IslaConScoop Resultados 50 Figura 6-3. Comparación, en el Escenario E, de los mejores valores fitness encontrados. 0 5 10 15 20 25 25 75 125 175 225 275 325 375 425 475 Media Valor Función Fitness Nº de generaciones Comparación a lo largo de un ensayo de mejores valores fitness encontrados SecSinScoop IslaSinScoop SecConScoop IslaConScoop 51 7 CONCLUSIONES Y FUTUROS TRABAJOS En este capítulo se presentan algunas conclusiones derivadas del análisis anterior. Finalmente se proponen algunas líneas futuras de trabajo. 7.1 Conclusiones El uso de algoritmos genéticos para resolver un problema de optimización combinatoria es una técnica cada vez más utilizada debido a que el espacio de soluciones es generalmente demasiado elevado como para ser resuelto por métodos convencionales. A menudo un algoritmo genético aplicado de forma secuencial se topa con la dificultad de que, al ser computacionalmente muy intensivo, en problemas donde se presenta una población de cierta envergadura se necesita de un tiempo de evaluación excesivamente elevado, lo que puede resultar poco adecuado para la resolución de problemas de optimización combinatoria. Una forma de extender la aplicabilidad de la computación evolutiva hacia problemas de mayor complejidad es la inclusión de paralelismo debido a las mejoras que presenta en cuanto a rendimiento. Esto se debe a dos factores, el primero, una ejecución en paralelo permite un mayor uso de recursos de cómputo como tiempo de procesador o memoria. El segundo factor es que el mismo comportamiento del algoritmo cambia como consecuencia de la estructura de la población. La ejecución en paralelo del algoritmo evolutivo permite una estructura poblacional formada por varios grupos interconectados de individuos. El resultado final que se ha pretendido encontrar a lo largo de este trabajo, comparando varias estrategias de implementación de algoritmos genéticos, es que se obtenga no solo un tiempo de espera menor para obtener la solución del problema sino que no se vea afectada la efectividad de la búsqueda (valor de fitness). A lo largo de este trabajo se han desarrollado cuatro estrategias de implementación, correspondientes a: modelo secuencial de población única, modelo secuencial de población basado en islas, modelo paralelo de población única y modelo paralelo de población basado en islas. Cada uno de estos modelos ha sido aplicado para resolver el problema de las N reinas y se han considerado cinco escenarios distintos dependiendo de la dimensión del problema y el número de generaciones a considerar. Como primera conclusión podemos decir que existe un punto de inflexión que marca la diferencia entre aquellos casos en que se tarda más tiempo (o menos), usando un modelo paralelo de población basado en islas, que hacerlo usando un modelo secuencial de población basado en islas. Dicho punto estaría en torno al escenario C, es decir, un escenario dónde el problema a resolver comienza a tener cierta envergadura (dimensión de tablero y número de generaciones). Por tanto, a partir de este punto comienza a ser útil el uso de modelo paralelo de población basado en islas. Por otra parte, la calidad de la solución obtenida por este método sigue siendo del mismo orden que la alcanzada con cualquier otro modelo de los que se han analizado. Una de las razones por las que podría darse la situación comentada es que, cuando la dimensión del problema no es lo suficientemente grande, el tiempo empleado en el cómputo del valor de fitness no es lo suficientemente elevado en relación al tiempo que se emplea en montar la estructura de paralelización. Dicho punto de inflexión indica el momento en el cual, al crecer la dimensión del problema, el tiempo empleado en el cómputo del valor de fitness excede al tiempo empleado en el montaje de la estructura de paralelización. Por tanto, a partir de este punto es recomendable utilizar un modelo paralelo frente a uno secuencial. Otra conclusión es que, en el modelo paralelo de población única los tiempos medios de ejecución son siempre los más altos. Esto se debe a que si se trabaja con una única población, la paralelización no es eficaz, pues el algoritmo genético simple sigue una estructura muy secuencial (ya que el operador selección sí debe ser aplicado de forma global a toda la población lo que dificulta la total paralelización del problema) y a pesar de desplegar varios trabajadores se sufren tiempos de espera que penalizan el tiempo de ejecución. Por otro lado, en el modelo paralelo con población basada en islas no se pierde este tiempo de espera porque cada isla es independiente y se optimiza la paralelización. Con ello concluimos que para explotar de forma efectiva la paralelización, a la librería que se usa para paralelizar (SCOOP) se le ha de otorgar un modelo que explote la paralelización (por ejemplo, el modelo de islas). Conclusiones y futuros trabajos 52 Finalmente concluimos también que, al no variar en exceso el tiempo medio de ejecución entre los casos de modelo secuencial de población única y modelo secuencial de población basado en islas, si no vamos a usar paralelismo, sería independiente usar un método u otro. Por lo tanto los resultados que arrojan los experimentos realizados en este trabajo validan el uso de los algoritmos genéticos paralelos para la optimización de problemas de este tipo, en dispositivos de ciertas limitaciones computacionales como puede ser Raspberry Pi. 7.2 Futuras líneas de trabajo A continuación se presentan diferentes líneas de trabajo futuro relacionadas con el desarrollo de este trabajo:  Es interesante estudiar la influencia de la heterogeneidad de la población en algoritmos paralelos distribuidos.  Investigar la implementación de algoritmos que determinen si se es útil seguir buscando o no, evitando estancamientos y creando sistemas distribuidos donde las islas nazcan y mueran, con el objetivo de mejorar la eficacia de los algoritmos y mejorando su adaptación al problema.  Extender el estudio sobre nuevos dominios de aplicación, como puedan ser la inclusión de la optimización de PathPlanning en una red de robots donde el cómputo necesario para su procesamiento no se centralice sino que se distribuya a través de una red. 53 REFERENCIAS Adbelmalik, M., Inza, I., & Larrañaga, P. (2008). Tema 2. Algoritmos Genéticos / Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad del País Vasco. Universidad del País Vasco . Blickle, T., & Thiele, L. (1995). A Comparison of Selection Schemes Used in Evolutionary Algorithms. Campbell, P. J. (1977). Gauss and the eight queens problem: a study in miniature of the propagation of historical error. Historia Mathematica 4, 397-404. Cannon, W. B. (1954). The body psychologic and the body politics. The Scientific Monthly, 20-26. Conor, R., Fitzgerald, J., Medernach, D., & Krawiec, K. (2015). An integrated approach to stage 1 breast cancer detection. GECCO '15 Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, 1199-1206. Darwin, C. (1859). On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. John Murray. De Jong, K. A. (1975). An analysis of the behavior of a class of genetic adaptive systems. Fogel, L. J., Owens, A. J., & Walsh, M. J. (1966). Artificial Intelligence through Simulated Evolution. Oxford: John Wiley & Sons. Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co. Goldberg, D. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Publishing Company. Gordon, V. S., & Whitley, D. (1993). Serial and Parallel Genetic Algorithms as Function Optimizers. Proceedings of the Fifth International Conference on Genetic Algorithms, (págs. 177-183). Illinois, WA, USA. Gorges-Schleuter, M. (1990). Explicit parallelism of genetic algorithms through population structures. Parallel Problem Solving from Nature, 150-159. Hoffmann, A. (1989). Arguments on Evolution: A Paleontologist’s Perspective. New York: Oxford University Press. Holland, J. H. (1975). Adaptation in Natural and Artificial System. Cambridge, Massachusetts: The MIT Press. Khan, S. A., Streater, J., Bathia, T. S., Fiore, S., & Bölöni, L. (2013). Learning social calculus with genetic programing. FLAIRS 2013 - Proceedings of the 26th International Florida Artificial Intelligence Research Society Conference, 88-93. Koza, J. R. (1994). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Statistics and Computing, Vol 4, Número 2, 87-112. Krawiec, K., & Pawlak, M. A. (2015). Genetic Programming with Alternative Search Drivers for Detection of Retinal Blood Vessels. EvoApplications 2015: Applications of Evolutionary Computation, 554-566. Larrañaga, P., Kuijpers, C., Murga, R., & Dizdarevic, S. (1999). Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial intelligence review, 13, 129-170. Levine, D. (1993). A Genetic Algorithm For The Set Partitioning Problem. Proceedings of the Fifth International Conference on Genetic Algorithms, (págs. 481-487). Illinois, WA, USA. Lin, S.-C., Punch, W., & E.D.Goodman. (1994). Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach. Proceedings of the Sixth IEEE Parallel & Distributed Processing, 28-37. Referencias 54 Lohn, J. D., Hornby, G. S., & Linden, D. S. (2005). An Evolved Antenna for Deployment on Nasa‟s Space Technology 5 Mission. Genetic Programming Theory and Practice II, 301-315. Lyons, C. (4 de Marzo de 2015). novadigitalmedia. Recuperado el 27 de Noviembre de 2018, de http://novadigitalmedia.com/history-raspberry-pi/ Markowska-Kaczmar, U., Kwasnicka, H., & Szczepkowski, M. (2008). Genetic Algorithm as a Tool for Stock Market Modelling. ICAISC 2008: Artificial Intelligence and Soft Computing, 450-459. Mendel, G. (1865). Versuche über Pflanzenhybriden. Verhandlungen des naturforschenden Vereines in Brünn, Bd. IV, (págs. 3–47). Brno. Miller, B. L., & Goldberg, D. E. (1995). Genetic Algorithms, Tournament Selection, and the Effects of Noise. Complex Systems, 9, 193–212. Nesmachnow, S. (2002). Evolución en el diseño y clasificación. Conferencia Latinoamericana de Informatica , (pág. 12). Montevideo, Uruguay. Nosuna, [. (23 de Septiembre de 2011). Velneo. Obtenido de Velneo: https://velneo.es/guido-van-rossum-ypython/ Oliva, R., Ballesta, F., Oriola, J., & Clària, J. (2008). Genética médica. Barcelona: Edicions Universitat Barcelona. Petit, C. (1998). Touched by nature: Putting evolution to work on the assembly line. U.S. News and World Report, vol.125, no.4, 43-45. Red Hat. (24 de Enero de 2010). OpenSource. Recuperado el 8 de Enero de 2019, de https://opensource.com/resources/raspberry-pi Starkweather, T., Whitley, D., & Mathias, K. E. (1991). Optimization Using Distributed Genetic Algorithms. Parallel Problem Solving from Nature, 176-185. Stender, J. (1993). Parallel Genetic Algorithm: Theory & Applications. Tomasini, M. (1999). Parallel and Distributed Evolutionary Algorithms: A Review. Evolutionary Algorithms in Engineering and Computer Science, 113-133. Turing, A. (1948). Intelligent Machinery. National Physical Laboratory. Weismann, A. (1892). Das Keimplasma: eine Theorie der Vererbung. Jena: Fischer. Whitley, D. (1989). The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best. Proceedings of the Third International Conference on Genetic Algorithms, (págs. 116-121). San Francisco, CA, USA. Whitley, D., Beveridge, J. R., Guerra, C., & Graves, C. (1998). Messy Genetic Algorithms for Subset Feature Selection. Yang, G., Jeong, Y., Min, K., Lee, J.-w., & Lee, B. (2018). Applying Genetic Programming with Similar Bug Fix Information to Automatic Fault Repair. Symmetry 10, no. 4, 92. 55 APÉNDICE. CÓDIGOS Código 1. Ensayo_Sec_NoScoop.py #!/usr/bin/env python2 # -*- coding: utf-8 -*- # Problema de las N Reinas. # # Modelo de poblacion unica. # # El problema consiste en colocar N Reinas en un tablero de dimensiones # NxN, de forma que el número de ataques entre reinas sea el menor posible. # # Simplificaciones del problema: # > Se considera que solo hay una reina por fila y columna # > Por lo tanto los ataques solo pueden ser diagonales # # Codificación del problema: # > Los individuos son una lista en la que el indice representa # la columna donde se coloca la reina y el contenido es la fila. # # Argumentos de entrada # --> Dimension N del tablero # --> Numero de generaciones # --> Tamaño de la poblacion # --> Nombre del fichero en el que se van a registrar los resultados # --> Probabilidad, en tanto por 1, de cruce # --> Probabilidad, en tanto por 1, de mutacion ######################################################################## import random import numpy import sys from deap import algorithms from deap import base from deap import creator from deap import tools from time import time #Parametros del problema NB_QUEENS = int(sys.argv[1]) # FUNCION DE FITNESS def evalNQueens(individual): Apéndice. Códigos 62 suma += diagonal_derecha_izquierda[i] - 1 return suma, # DEFINICION DEL PROBLEMA creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.FitnessMin) # REGISTRO DE FUNCIONES QUE SON NECESARIAS -- CAJA DE HERRAMIENTAS toolbox = base.Toolbox() toolbox.register("permutation", random.sample, range(NB_QUEENS), NB_QUEENS) # Funciones de inicializacion del individuo y de la poblacion toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.permutation) toolbox.register("population", tools.initRepeat, list, toolbox.individual) # Funcion de evaluacion toolbox.register("evaluate", evalNQueens) # Operadores geneticos toolbox.register("mate", tools.cxPartialyMatched) toolbox.register("mutate", tools.mutShuffleIndexes, indpb=2.0/NB_QUEENS) toolbox.register("select", tools.selTournament, tournsize=3) def main(num_generaciones, tam_poblacion, num_islas, frec_mig, num_migrant, prob_cruce, prob_muta): islands = [toolbox.population(tam_poblacion) for i in range(num_islas)] hof = tools.HallOfFame(1) # objeto que almacena el mejor individuo stats = tools.Statistics(lambda ind: ind.fitness.values) # objeto para calcular estadisticas stats.register("Avg", numpy.mean) stats.register("Std", numpy.std) stats.register("Min", numpy.min) stats.register("Max", numpy.max) logbook = tools.Logbook() #A continuacion se registra el algoritmo genetico como una funcion toolbox.register("algorithm", algorithms.eaSimple, toolbox=toolbox, cxpb=prob_cruce, mutpb=prob_muta, ngen=frec_mig, halloffame=hof, verbose=False) generaciones = [] #Lista que guarda aquellas generaciones que han sido evaluadas fitnesses = [] #Lista que almacena valores fitness después de cada migracion for i in range(0, num_generaciones, frec_mig): results=[] #Se ejecuta, por isla, el algoritmo genetico for j in range(len(islands)): results.append(algorithms.eaSimple(islands[j], toolbox,cxpb=prob_cruce, mutpb=prob_muta, ngen=frec_mig, stats=stats, halloffame=hof, verbose=False)) islands = [pop for pop, logbook in results] #comprehensive list en la que, por isla, se obtiene la población y datos asociados generaciones.append(i+frec_mig) 63 63 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi fitnesses.append(hof[0].fitness.values[0]) tools.migRing(islands, num_migrant, tools.selBest) #puesta en marcha de la mmigracion return hof, logbook, generaciones, fitnesses if __name__ == "__main__": num_generaciones = int(sys.argv[2]) tam_poblacion = int(sys.argv[3]) nombre_fichero = sys.argv[4] num_islas = int(sys.argv[5]) frec_mig = int(sys.argv[6]) num_migrant = int (sys.argv[7]) prob_cruce = float(sys.argv[8]) prob_muta = float(sys.argv[9]) start_time = time() best, logbook, generaciones, fitnesses = main(num_generaciones, tam_poblacion, num_islas, frec_mig, num_migrant, prob_cruce, prob_muta) tiempo = str(time() - start_time) with open(nombre_fichero, 'a') as filehandle: filehandle.writelines("gen:" ) filehandle.writelines("%s," % element for element in generaciones) filehandle.writelines("\nfit:" ) filehandle.writelines("%s," % element for element in fitnesses) filehandle.writelines("\nElapsed time:") filehandle.writelines("%s" % tiempo) filehandle.writelines("\n---\n" ) Código 4. Ensayo_Isla_Scoop.py #!/usr/bin/env python2 # -*- coding: utf-8 -*- # Problema de las N Reinas. # # Modelo de poblacion basada en islas y uso de capacidades de SCOOP. # # El problema consiste en colocar N Reinas en un tablero de dimensiones # NxN, de forma que el número de ataques entre reinas sea el menor posible. # # Simplificaciones del problema: # > Se considera que solo hay una reina por fila y columna # > Por lo tanto los ataques solo pueden ser diagonales # # Codificacion del problema: # > Los individuos son una lista en la que el indice representa # la columna donde se coloca la reina y el contenido es la fila. # Apéndice. Códigos 64 # Argumentos de entrada # --> Dimension N del tablero # --> Numero de generaciones # --> Tamaño de la poblacion de cada isla # --> Nombre del fichero en el que se van a registrar los resultados # --> Numero de islas # --> Frecuencia, en generaciones, de migracion entre islas # --> Numero de individuos, por islas, que van a migrar # --> Probabilidad, en tanto por 1, de cruce # --> Probabilidad, en tanto por 1, de mutacion ######################################################################## import random import numpy import sys from scoop import futures from deap import algorithms from deap import base from deap import creator from deap import tools from time import time #Parametros del problema NB_QUEENS = int(sys.argv[1]) # FUNCION DE FITNESS def evalNQueens(individual): """ Funcion de evaluacion del problema. El problema consiste en posiciones N reinas en un tablero de ajedrez de dimensiones NxN. La funcion de evaluacion calcula el numero de reinas R que hay en cada diagonal. El numero de ataques que hay en cada diagonal se puede calcular como R-1. """ size = len(individual) # Los ataques solo pueden ser en las diagonales diagonal_izquierda_derecha = [0] * (2*size-1) diagonal_derecha_izquierda = [0] * (2*size-1) # Numero de reinas en cada diagonal for i in range(size): # recorremos las columnas diagonal_izquierda_derecha[i+individual[i]] += 1 # [columna + fila] diagonal_derecha_izquierda[size-1-i+individual[i]] += 1 # [size-1-columna + fila] # Numero de ataques en cada diagonal 65 65 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi suma = 0 for i in range(2*size-1): # recorremos todas las diagonales if diagonal_izquierda_derecha[i] > 1: # hay ataques suma += diagonal_izquierda_derecha[i] - 1 # n-1 ataques if diagonal_derecha_izquierda[i] > 1: suma += diagonal_derecha_izquierda[i] - 1 return suma, # DEFINICION DEL PROBLEMA creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.FitnessMin) # REGISTRO DE FUNCIONES QUE SON NECESARIAS (CAJA DE HERRAMIENTAS) toolbox = base.Toolbox() toolbox.register("permutation", random.sample, range(NB_QUEENS), NB_QUEENS) # Funciones de inicializacion del individuo y de la poblacion toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.permutation) toolbox.register("population", tools.initRepeat, list, toolbox.individual) # Funcion de evaluacion toolbox.register("evaluate", evalNQueens) # Operadores geneticos toolbox.register("mate", tools.cxPartialyMatched) toolbox.register("mutate", tools.mutShuffleIndexes, indpb=2.0/NB_QUEENS) toolbox.register("select", tools.selTournament, tournsize=3) # Operador multiproceso toolbox.register("map", futures.map) def main(num_generaciones, tam_poblacion, num_islas, frec_mig, num_migrant, prob_cruce, prob_muta): islands = [toolbox.population(tam_poblacion) for i in range(num_islas)] hof = tools.HallOfFame(1) # objeto que almacena el mejor individuo stats = tools.Statistics(lambda ind: ind.fitness.values) # objeto para calcular estadisticas stats.register("Avg", numpy.mean) stats.register("Std", numpy.std) stats.register("Min", numpy.min) stats.register("Max", numpy.max) logbook = tools.Logbook() # Elimina metodos no seleccionables antes de enviar a la toolbox toolbox.unregister("permutation") toolbox.unregister("individual") toolbox.unregister("population") Apéndice. Códigos 66 #A continuacion se registra el algoritmo genetico como una funcion toolbox.register("algorithm", algorithms.eaSimple, toolbox=toolbox, cxpb=prob_cruce, mutpb=prob_muta, ngen=frec_mig, halloffame=hof, verbose=False) generaciones = [] #Lista que guarda aquellas generaciones que han sido evaluadas fitnesses = [] #Lista que almacena valores fitness despues de cada migracion for i in range(0, num_generaciones, frec_mig): results = toolbox.map(toolbox.algorithm, islands, stats=stats) islands = [pop for pop, logbook in results] #comprehensive list en la que, por isla, se obtiene la poblacion y datos asociados generaciones.append(i+frec_mig) fitnesses.append(hof[0].fitness.values[0]) tools.migRing(islands, num_migrant, tools.selBest) #puesta en marcha de la migracion return hof, logbook, generaciones, fitnesses if __name__ == "__main__": num_generaciones = int(sys.argv[2]) tam_poblacion = int(sys.argv[3]) nombre_fichero = sys.argv[4] num_islas = int(sys.argv[5]) frec_mig = int(sys.argv[6]) num_migrant = int (sys.argv[7]) prob_cruce = float(sys.argv[8]) prob_muta = float(sys.argv[9]) start_time = time() best, logbook, generaciones, fitnesses = main(num_generaciones, tam_poblacion, num_islas, frec_mig, num_migrant, prob_cruce, prob_muta) tiempo = str(time() - start_time) with open(nombre_fichero, 'a') as filehandle: filehandle.writelines("gen:" ) filehandle.writelines("%s," % element for element in generaciones) filehandle.writelines("\nfit:" ) filehandle.writelines("%s," % element for element in fitnesses) filehandle.writelines("\nElapsed time:") filehandle.writelines("%s" % tiempo) filehandle.writelines("\n---\n" ) Código 5. HacerDatos.py # # Sencillo script que dado un archivo que se le entrega por parametro de entrada # extrae los resultados de los cinco primeros ensayos y calcula la media de los valores # de fitness, valor medio de tiempo de ejecución y varianza 67 67 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi # Argumentos de entrada # --> Fichero de entrada # --> Fichero de salida ######################################################################## from collections import defaultdict import numpy as np import matplotlib.pyplot as plt import sys c1valor_gen = [] c1valor_fit = [] c2valor_gen = [] c2valor_fit = [] c3valor_gen = [] c3valor_fit = [] c4valor_gen = [] c4valor_fit = [] c5valor_gen = [] c5valor_fit = [] valoresTiempo = [] valorMedioFitness = [] obtener = sys.argv[1] guardar = sys.argv[2] f = open(obtener) #Curva1 for line in f: if line.startswith("gen"): name, val = line.split(":") gen, retorno = val.split(",\n") c1valor_gen = gen.split(',') elif line.startswith("fit"): name, val = line.split(":") fit, retorno = val.split(",\n") c1valor_fit = fit.split(',') elif line.startswith("Elapsed time"): name, val = line.split(":") tiempo, retorno = val.split("\n") valoresTiempo.append(float(tiempo)) elif line.startswith("---"): break #Curva2 for line in f: Apéndice. Códigos 68 if line.startswith("gen"): name, val = line.split(":") gen, retorno = val.split(",\n") c2valor_gen = gen.split(',') elif line.startswith("fit"): name, val = line.split(":") fit, retorno = val.split(",\n") c2valor_fit = fit.split(',') elif line.startswith("Elapsed time"): name, val = line.split(":") tiempo, retorno = val.split("\n") valoresTiempo.append(float(tiempo)) elif line.startswith("---"): break #Curva3 for line in f: if line.startswith("gen"): name, val = line.split(":") gen, retorno = val.split(",\n") c3valor_gen = gen.split(',') elif line.startswith("fit"): name, val = line.split(":") fit, retorno = val.split(",\n") c3valor_fit = fit.split(',') elif line.startswith("Elapsed time"): name, val = line.split(":") tiempo, retorno = val.split("\n") valoresTiempo.append(float(tiempo)) elif line.startswith("---"): break #Curva4 for line in f: if line.startswith("gen"): name, val = line.split(":") gen, retorno = val.split(",\n") c4valor_gen = gen.split(',') elif line.startswith("fit"): name, val = line.split(":") fit, retorno = val.split(",\n") c4valor_fit = fit.split(',') elif line.startswith("Elapsed time"): name, val = line.split(":") tiempo, retorno = val.split("\n") valoresTiempo.append(float(tiempo)) 69 69 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi elif line.startswith("---"): break #Curva5 for line in f: if line.startswith("gen"): name, val = line.split(":") gen, retorno = val.split(",\n") c5valor_gen = gen.split(',') elif line.startswith("fit"): name, val = line.split(":") fit, retorno = val.split(",\n") c5valor_fit = fit.split(',') elif line.startswith("Elapsed time"): name, val = line.split(":") tiempo, retorno = val.split("\n") valoresTiempo.append(float(tiempo)) elif line.startswith("---"): break f.close() for i in range(len(c1valor_fit)): aux = [] aux.append(float(c1valor_fit[i])) aux.append(float(c2valor_fit[i])) aux.append(float(c3valor_fit[i])) aux.append(float(c4valor_fit[i])) aux.append(float(c5valor_fit[i])) valorMedioFitness.append(np.mean(aux)) with open(guardar, 'a') as filehandle: filehandle.writelines("fitnessmedio:" ) filehandle.writelines("%s," % element for element in valorMedioFitness) filehandle.writelines("\ntiempomedio:") filehandle.writelines("%s" % np.mean(valoresTiempo)) filehandle.writelines("\nvarianzatiempo:") filehandle.writelines("%s" % np.std(valoresTiempo)) Código 6. Script_Isla_NoScoop_A.sh for i in 1 2 3 4 5 do python Ensayo_Isla_NoScoop.py 20 100 100 Resultados_Isla_NoScoop_A 3 5 15 0.5 0.2 done Apéndice. Códigos 70 Código 7. Script_Isla_NoScoop_B.sh for i in 1 2 3 4 5 do python Ensayo_Isla_NoScoop.py 40 200 100 Resultados_Isla_NoScoop_B 3 10 15 0.5 0.2 done Código 8. Script_Isla_NoScoop_C.sh for i in 1 2 3 4 5 do python Ensayo_Isla_NoScoop.py 60 300 100 Resultados_Isla_NoScoop_C 3 15 15 0.5 0.2 done Código 9. Script_Isla_NoScoop_D.sh for i in 1 2 3 4 5 do python Ensayo_Isla_NoScoop.py 80 400 100 Resultados_Isla_NoScoop_D 3 20 15 0.5 0.2 done Código 10. Script_Isla_NoScoop_E.sh for i in 1 2 3 4 5 do python Ensayo_Isla_NoScoop.py 100 500 100 Resultados_Isla_NoScoop_E 3 25 15 0.5 0.2 done Código 11. Script_Isla_Scoop_A_1rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_1rpi_2worker Ensayo_Isla_Scoop.py 20 100 100 Resultados_Isla_Scoop_A_1RPI_2Wor 3 5 15 0.5 0.2 python -m scoop --hostfile hostfile_1rpi_4worker Ensayo_Isla_Scoop.py 20 100 100 Resultados_Isla_Scoop_A_1RPI_4Wor 3 5 15 0.5 0.2 done Código 12. Script_Isla_Scoop_A_2rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_2rpi_2worker Ensayo_Isla_Scoop.py 20 100 100 Resultados_Isla_Scoop_A_2RPI_2Wor 3 5 15 0.5 0.2 python -m scoop --hostfile hostfile_2rpi_4worker Ensayo_Isla_Scoop.py 20 100 100 71 71 Diseño de servidor para sistemas distribuidos sobre dispositivos Raspberry Pi Resultados_Isla_Scoop_A_2RPI_4Wor 3 5 15 0.5 0.2 done Código 13. Script_Isla_Scoop_A_3rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_3rpi_2worker Ensayo_Isla_Scoop.py 20 100 100 Resultados_Isla_Scoop_A_3RPI_2Wor 3 5 15 0.5 0.2 python -m scoop --hostfile hostfile_3rpi_4worker Ensayo_Isla_Scoop.py 20 100 100 Resultados_Isla_Scoop_A_3RPI_4Wor 3 5 15 0.5 0.2 done Código 14. Script_Isla_Scoop_B_1rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_1rpi_2worker Ensayo_Isla_Scoop.py 40 200 100 Resultados_Isla_Scoop_B_1RPI_2Wor 3 10 15 0.5 0.2 python -m scoop --hostfile hostfile_1rpi_4worker Ensayo_Isla_Scoop.py 40 200 100 Resultados_Isla_Scoop_B_1RPI_4Wor 3 10 15 0.5 0.2 done Código 15. Script_Isla_Scoop_B_2rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_2rpi_2worker Ensayo_Isla_Scoop.py 40 200 100 Resultados_Isla_Scoop_B_2RPI_2Wor 3 10 15 0.5 0.2 python -m scoop --hostfile hostfile_2rpi_4worker Ensayo_Isla_Scoop.py 40 200 100 Resultados_Isla_Scoop_B_2RPI_4Wor 3 10 15 0.5 0.2 done Código 16. Script_Isla_Scoop_B_3rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_3rpi_2worker Ensayo_Isla_Scoop.py 40 200 100 Resultados_Isla_Scoop_B_3RPI_2Wor 3 10 15 0.5 0.2 python -m scoop --hostfile hostfile_3rpi_4worker Ensayo_Isla_Scoop.py 40 200 100 Resultados_Isla_Scoop_B_3RPI_4Wor 3 10 15 0.5 0.2 done Código 17. Script_Isla_Scoop_C_1rpi.sh for i in 1 2 3 4 5 do python -m scoop --hostfile hostfile_1rpi_2worker Ensayo_Isla_Scoop.py 60 300 100 Resultados_Isla_Scoop_C_1RPI_2Wor 3 15 15 0.5 0.2 python -m scoop --hostfile hostfile_1rpi_4worker Ensayo_Isla_Scoop.py 60 300 100 Apéndice. Códigos 78 Código 43. hostfile_1rpi_2worker 192.168.1.49 2 Código 44. hostfile_1rpi_4worker 192.168.1.49 4 Código 45. hostfile_2rpi_2worker 192.168.1.49 2 192.168.1.51 2 Código 46. hostfile_2rpi_4worker 192.168.1.49 4 192.168.1.51 4 Código 47. hostfile_3rpi_2worker: 192.168.1.49 4 192.168.1.51 4 192.168.1.50 4 Código 48. hostfile_3rpi_4worker: 192.168.1.49 4 192.168.1.51 4 192.168.1.50 4