Sistema inmune artificial con población reducida para optimización numérica

Abstract

En este trabajo de tesis se presenta un nuevo algoritmo, se trata de un micro‐sistema inmune artificial (denominado micro‐SIA), basado en la teoría de la selección clonal, para resolver problemas de optimización numérica. Para este estudio se empleó el algoritmo CLONALG en su versión estándar, que es un sistema inmune artificial ampliamente utilizado para resolver problemas de optimización y de reconocimiento de patrones. Durante la fase de clonación, CLONALG incrementa drásticamente el tamaño de su población, por lo que esta característica es atractiva para proponer una versión con una población de individuos reducida. La hipótesis que se estableció en este trabajo fue que al reducir el número de individuos en la población, también se reduce el número de evaluaciones a la función objetivo, con lo que fue posible incrementar la velocidad de convergencia y decrementar el uso de la memoria de datos. El micro‐SIA propuesto usa una población de 5 individuos (anticuerpos) de los cuales se obtienen sólo 15 clones. En el proceso de maduración de estos clones, dos simples y rápidos operadores de mutación fueron diseñados y utilizados dentro de una convergencia nominal que trabaja en conjunto con un proceso de reinicialización para preservar la diversidad. Se realizaron dos versiones del micro‐SIA para optimización numérica, la primera de éstas no considera el manejo de restricciones, sin embargo la mayoría de los problemas de optimización en el mundo real tienen restricciones, por lo que una segunda versión del micro‐SIA, sí permite lidiar con éstas. También se presentan dos aproximaciones del micro‐SIA embebidas en hardware y que se ejecutan intrínsecamente para resolver el problema de la maximización de unos en una cadena finita (MaxOne Problem), la primera se implementó en un microcontrolador comercial de 8 bits y la segunda en un dispositivo de lógica reconfigurable (FPGA) estimando cadenas de 16 bits. La experimentación con el micro‐SIA finalizó con una aplicación de reconocimiento de caracteres. // This thesis presents a new algorithm, it is a micro‐artificial immune system (micro‐ SIA) based on the clonal selection theory to solve numerical optimization. For this study it was considered the algorithm named CLONALG, it is a widely used artificial immune system. During the process of cloning, CLONALG greatly increases the size of its population, so this feature is attractive to propose a version with a reduced population. The established hypothesis is that by reducing the number of individuals in a population will decrease the number of evaluations to the objective function, increasing the speed of convergence and reducing the use of data memory. The proposed micro‐SIA uses a population of 5 individuals (antibodies) which are obtained only 15 clones. In the maturation stage of the clones, two simple and fast mutation operators are used in a nominal convergence that works together with a reinitialization process to preserve the diversity. Two versions of the micro‐SIA to solve global numerical optimization problems were realized. The first version does not consider constraints handling. However, the majority of optimization problems in the real world have constraints, so a second version of the micro‐SIA, it does allow dealing with constraints. This thesis also presented two approaches of micro‐SIA implemented in hardware. These architectures allow the intrinsic execution of the algorithm to solve the MaxOne problem in a finite string. The first approach is implemented in a commercial 8‐bit microcontroller. The second architecture was implemented on a reconfigurable logic device (FPGA). Finally, experimentation with the micro‐SIA concluded with the design and implementation of a character recognition application.