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

Abstract

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).

The use of genetic algorithms to solve problems of combinatorial optimization is a technique that is being increasingly used because the search space is generally too big to be solved by conventional means. In many instances, genetic algorithms applied sequentially encounter the difficulty that an excessively high evaluation time (if the population is of a certain size) is required, which may be unsuitable for solving this kind of problems. One way to extend the applicability of evolutionary computing to more complex problems is to include parallelism, thanks to the performance improvements that it implies. This work is divided in two parts. The first one is dedicated to a study on the theoretical bases of these algorithms, as well as their uses in parallel computing and distributed network computing. In the second part, several Raspberry Pi devices have been connected by Wi-Fi in a local area network (LAN). These devices will be configured to work together in order to solve a classic optimization problem, known as the 'N queens problem'. Using this structure, a series of tests will be designed (consisting of different scenarios that make use of these genetic algorithms) with the aim of parallelizing the algorithm and being able to make comparisons between the obtained results. One of the most remarkable conclusions of this work could be that there is a turning point from which it is convenient to use parallel genetic algorithms with a population model based on islands (In the case of using devices with computational limitations, such as a Raspberry Pi).