Análisis y optimización de algoritmos genéticos para el filtrado de imágenes mediante hardware evolutivo

Barajas Fernández, Rodrigo (2017). Análisis y optimización de algoritmos genéticos para el filtrado de imágenes mediante hardware evolutivo. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. Industriales (UPM).

Descripción

Título: Análisis y optimización de algoritmos genéticos para el filtrado de imágenes mediante hardware evolutivo
Autor/es:
  • Barajas Fernández, Rodrigo
Director/es:
  • Torre Arnanz, Eduardo de la
  • Mora de Sambricio, Javier
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Ingeniería en Tecnologías Industriales
Fecha: Febrero 2017
Materias:
Palabras Clave Informales: Hardware evolutivo, tasa de mutación, array sistólico, evolución, fitness, Processing Element.
Escuela: E.T.S.I. Industriales (UPM)
Departamento: Automática, Ingeniería Eléctrica y Electrónica e Informática Industrial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (2MB) | Vista Previa

Resumen

Con la realización de este proyecto se busca estudiar el algoritmo genético que gobierna un hardware evolutivo para el filtrado de imágenes. El objetivo es analizar los diferentes parámetros que componen el algoritmo para evaluar su efecto y optimizarlos para cada tamaño del hardware. La tecnología evolutiva se basa en plasmar la evolución por selección natural de los seres vivos en la construcción de sistemas. El funcionamiento básico consta de la generación de modificaciones aleatorias en un sistema para generar un nuevo sistema “hijo”, y en función de si este sistema “hijo” realiza mejor o peor la función que el “padre”, este se sustituye o no por el nuevo. El Array Sistólico (o en inglés, Systolic Array) va a ser la arquitectura de hardware evolutivo a emplear. Durante el proyecto se va a modificar el algoritmo que maneja el mecanismo de la evolución, no el hardware implementado. El sistema se encarga de filtrar imágenes, por ello las entradas del mismo son los pixeles de la imagen que se va a filtrar. Las entradas las forman un pixel principal y los pixeles de alrededor al mismo (un total de 9 entradas), para dar más posibilidades al filtrado de la imagen. Como resultado se obtiene el pixel principal filtrado. Los pixeles de la imagen se van enviando en serie hasta completar la totalidad de la imagen. El Array sistólico está formado por una malla de elementos de procesamiento o processing elements (PE) que realizan pequeñas operaciones entre sus entradas locales para dar lugar a una salida, funciones como suma, resta, máximo absoluto o media. La esquematización del sistema se observa en la imagen, para un array sistólico de 3x3. Cada PE está conectado con el PE superior y el que se encuentra a su izquierda, de manera que hace la operación con los valores que recibe de estos. En el caso de los PE de los extremos, estos pueden recibir cualquiera de los pixeles de entrada. La evolución del Array sistólico se basa en generar modificaciones aleatorias de partes del sistema. Cada evolución, es decir, cada nueva generación, modifica aleatoriamente la funcionalidad de unos PE escogidos también aleatoriamente. A estos PE se les asignará una de las funciones previamente programadas aleatoriamente de manera que se modifica el sistema. Además, en el caso de los PE en los extremos, los pixeles de entrada son escogidos aleatoriamente, de manera que realizará su función con una entrada aleatoria, dando gran cantidad de posibilidades al conjunto. Esta fase de evolución es un mecanismo de entrenamiento del sistema. Este entrenamiento se realiza con una imagen predefinida, de la cual se disponen dos versiones, una con ruido y otra sin ruido. La forma de evaluar si una modificación aleatoria ha sido o no ventajosa para el sistema se realiza a partir de una función llamada función fitness. Esta función define la calidad de filtrado del sistema. Para ello se introduce la imagen predefinida con ruido en el sistema y luego se compara la imagen perfecta sin ruido con la imagen de salida del sistema. La función fitness, en este caso, se calcula como el sumatorio de los valores absolutos de la diferencia entre cada pixel de la imagen de referencia y la salida del sistema (cuanto menor valor tiene el fitness, mejor es el filtrado del array). Gracias a esta función el sistema es capaz de evaluar si una evolución ha generado una modificación ventajosa, y en caso afirmativo, se sustituirá la configuración antigua por la nueva configuración. Repitiendo este proceso se puede alcanzar un sistema con un muy buen resultado. En este proyecto se ha trabajado con arrays de tamaños variables desde 8x8 hasta 24x24 elementos de procesamiento. La metodología seguida se basa en evaluar la influencia de los diferentes factores realizando 1000 pruebas con cada modificación y se van escribiendo los diferentes valores de fitness del modelo cada 1024 evoluciones. Estos valores luego se editan con un programa que se ha creado específicamente para este proyecto que genera un archivo Excel con los diferentes valores que ha ido tomando cada prueba. Todos los datos que se muestran en el proyecto son medias y medianas de conjuntos de pruebas. Debido a la naturaleza aleatoria de todo el sistema, se observa que las distribuciones de los resultados de cada prueba tienen grandes varianzas, por lo que en muchos casos no se puede afirmar que, estadísticamente, una modificación es mejor que otra, ahora bien, sí se observan tendencias y patrones. La tasa de mutación: Uno de los parámetros que se estudia es la tasa de mutación. Ésta se define como la cantidad de PEs del array que se van a modificar en una evolución. En esta fase del proyecto se estudia el resultado tras el mismo número de evoluciones de los diferentes tamaños con tasas de mutación diferentes, para calcular cuál es la mejor tasa para cada caso. Tras 131.072 evoluciones se observa que para los tamaños de 12x12 y 16x16 la mejor tasa de mutación es la de valor 3, y para los otros casos, es decir, para arrays más pequeños, el valor 2. Se observa que todas las tasas tienen curvas del mismo tipo, a continuación se muestra un ejemplo de la curva media del fitness de la evolución de un array de 24x24 y sus diferentes tasas de mutación, tras 262.144 evoluciones. Con una fase de mejora muy rápida seguida de una diminución de la velocidad de mejora. Se ha probado tasas de mutación variables en el tiempo, primero con tasas de evolución variables en números de evoluciones del orden de 100.000 o 250.000 generaciones (como la mayor parte de los experimentos del proyecto) siempre con peores comportamientos. Se ha probado también una tasa de mutación aleatoria entre 1 y 8, demostrando no haber ventajas frente a tasas de tamaño fijo. Para entender la evolución del sistema se han hecho pruebas con 8 veces más tiempo de evolución, sobrepasando el millón de generaciones (en un array de 16x16). El resultado es que la evolución se acaba bloqueando. Se probó una tasa de mutación variable, pasando de 2 a 1 y en otro caso de 2 a 5, con números de evoluciones del mismo orden, produciéndose el cambio de tasa tras el medio millón de evoluciones. Se observa que el sistema acaba bloqueándose. En la siguiente tabla se muestran valores medios, lo problemático del bloqueo es que en ocasiones se bloquea en valores muy malos, dando como resultado un filtrado demasiado malo. Evoluciones en paralelo: Tribus Una modificación que se implementó antes de este proyecto fue la paralelización de evoluciones. Esta idea se basa en los resultados del apartado anterior donde se ven pruebas que acaban dando resultados muy buenos y otras que, con el mismo sistema, terminan con malos resultados. Consiste en crear varias configuraciones independientes y evolucionarlas en paralelo, en vez de evolucionar únicamente una configuración. A cada configuración se la llama tribu. Este es otro parámetro fundamental del algoritmo evolutivo. Se utilizarán las tasas de mutación de los resultados del apartado anterior a pesar de haberse realizado sin paralelización. Además, se implementó un sistema de guerras de tribus, que se basa en que cada cierto tiempo, la peor tribu se sustituye por una copia de la mejor tribu en ese instante. En este apartado se han realizado pruebas con diferentes tamaños y diferentes números de tribus. Para poder comparar estos resultados se realiza el mismo número de evoluciones totales en este algoritmo que en el caso de la tasa de mutación sin tribus. Esto significa que en el caso de tener 8 tribus y realizar un total de 262.144 evoluciones, cada tribu realizará entonces individualmente 262.144/8 = 32.768 evoluciones. Los resultados muestran que para el array de 8x8, 16x16 y 24x24 el número de tribus que da mejor resultado es el de 8, aunque números de tribus cercanos dan resultados muy similares. Además, se observa una mejora de resultado importante disminuyendo el valor de fitness alcanzado en el caso del 16x16 y 24x24 en 9000 y 6000 respectivamente. A partir de estos resultados se concluye que las 8 tribus son las óptimas para los tamaños del hardware del proyecto. Además, la distribución de los resultados de las pruebas tiene menor varianza mostrando un sistema más robusto y fiable. Sin embargo, los resultados muestran que se consumen recursos en modificar tribus con fitness muy elevados (malos). Para evitar esta desviación se crearon las guerras, pero en pruebas con pocas evoluciones, se están realizando operaciones similares en copias de la misma tribu (las guerras copian la tribu principal), y en pruebas muy largas, se acaban copiando la mejor tribu en las otras posiciones. Por ello, aunque el sistema de guerras es útil, se considera la posibilidad de crear unas tribus variables en el tiempo, en vez de este sistema. Las tribus variables se han implementado de dos maneras. Una primera que elimina una tribu si esta es un 25% peor que la mejor, que resulta muy agresiva y tras pocas evoluciones solo se mantiene la primera tribu. La segunda consiste en eliminar la peor tribu cada ciertas evoluciones (3072), para consumir los recursos que se emplearían en evolucionar esta tribu en las otras tribus con mejores resultados. Las pruebas realizadas con este último algoritmo, en un array de 16x16, generan un fitness medio final de 37.098,6. Este es un mejor resultado que el mostrado anteriormente, de 39484,6 por lo tanto se concluye que este sistema es interesante (a pesar de no poder asegurar estadísticamente el resultado). En este proyecto, el mejor resultado se ha obtenido con este algoritmo. Nuevos mecanismos de evolución: Cruce de configuraciones. En esta fase se han buscado nuevas formas de evolución. Se plantea entonces un sistema de cruce de configuraciones, de manera que se genere un nuevo sistema a partir de dos anteriores. La mezcla total de dos sistemas no muestra valores satisfactorios mientras que un cruce parcial, definido este como el introducir fragmentos de la malla de PE de una configuración en otra, si da algunos resultados interesantes. Este sistema necesita la evolución con tasa de mutación, simplemente se implementa como sistema complementario. Esta modificación se ha ensayado sin tribus. El resultado muestra que las pruebas con cruces dan mejor resultado que el mismo sistema sin cruces. Los intentos para cruzar dos sistemas se consideran como evoluciones corrientes de tasa de mutación realizando el mismo número total de evoluciones. Se consigue en un array de 16x16 con un cruce de un fragmento de 7x7 de una tribu independiente en paralelo (esta tribu evoluciona sin influencia de la tribu objeto del estudio, pudiendo tener un fitness mejor o peor en cada caso), un resultado de 53.488,8 que mejora en 3000 el fitness medio de la misma prueba sin cruces. Conclusiones sobre la fase de evolución: De estas pruebas se realiza una hipótesis del funcionamiento de la evolución. Esta la forman dos fases, una fase principal donde se realiza un esqueleto de lo que va a ser el sistema de filtrado final, siendo la fase donde se produce la mayor parte de la mejora de fitness. A partir de este momento, se genera una línea evolutiva que tenderá a una asíntota que definirá el fitness final tras un número muy elevado de evoluciones. La fase principal termina de media tras las 15.000-25.000 evoluciones, en función del tamaño, sin embargo, depende de la aleatoriedad de cada prueba. Tras la fase principal, como la variación de fitness durante la fase secundaria es relativamente pequeña, las líneas evolutivas con mejor fitness en este momento tienen mucha mayor probabilidad de finalizar con un mejor resultado que las otras pruebas. En concreto, se puede aproximar que, si una configuración se presenta un 10% mejor que otra al finalizar la fase principal, en prácticamente todos los casos, esta finalizará con un mejor comportamiento. Al realizar pruebas en paralelo, se escoge la que mejor línea evolutiva presenta (la que da el mejor resultado), obteniendo buenos resultados. Se ha comprobado que a pesar de realizar muchas menos evoluciones individualmente en cada prueba, mientras se realicen evoluciones suficientes como para permitir sobrepasar con seguridad la fase principal, el resultado va a ser mejor. Esto es debido a que la mayor parte de la mejora de fitness se realiza en estas evoluciones. La razón de que sea difícil que una prueba que empieza peor que otra acabe dando mejor resultado explica el buen resultado de las tribus variables. Con este algoritmo se concentran los recursos en las tribus que se muestran más favorables, dándoles más evoluciones que en el caso de tribus fijas y se consigue un mejor resultado final. En cuanto al cruce de tribus, los resultados muestran que es ventajoso invertir ciertos recursos en el cruce de configuraciones, antes que invertir todas en evolución por mutación, permitiendo nuevas posibilidades en algoritmos futuros. En definitiva, con el proyecto se han optimizado, evaluado y propuesto varios algoritmos evolutivos consiguiendo el resultado de que el algoritmo de tribus variables con la tasa de mutación óptima para el tamaño correspondiente, es el que tiene mejor comportamiento. Además se ha incidido en el funcionamiento interno de la evolución de los arrays sistólicos para intentar comprender los resultados que se han ido obteniendo.

Más información

ID de Registro: 45666
Identificador DC: http://oa.upm.es/45666/
Identificador OAI: oai:oa.upm.es:45666
Depositado por: Biblioteca ETSI Industriales
Depositado el: 28 Abr 2017 06:45
Ultima Modificación: 28 Abr 2017 06:45
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM