Diseño e implementación de un algoritmo genético paralelo para la solución de problemas de optimización combinatoria

Memoria:
Diseño e implementación de un algoritmo genético paralelo para la solución de problemas de optimización combinatoria

dc.contributor.advisor	Herrera-López, Carlos	es
dc.contributor.advisor	Parada-Daza, Víctor	es
dc.contributor.advisor	Durán-Faúndez, Cristián Rodrigo	es
dc.contributor.author	Fonseca-Avendaño, José Nicolás	es
dc.date.accessioned	2017-04-05T12:21:41Z
dc.date.available	2017-04-05T12:21:41Z
dc.date.issued	2015
dc.description	Memoria (Ingeniero Civil en Automatización)	es
dc.description.abstract	El presente trabajo de título tiene por objetivo diseñar un algoritmo genético paralelo para la resolución de problemas de optimización combinatoria. Para cumplir con el objetivo general es necesario contar con un problema de decisión complejo (NP-Hard), en este trabajo se selecciona el problema de localización de nodos presente en las redes inalámbricas. Una vez definido el problema a resolver se desarrollan los principales componentes del algoritmo genético como: la codificación utilizada, la función de fitness, los operadores genéticos, etc. Finalmente se realiza una comparación entre el algoritmo propuesto y su versión secuencial. Para el desarrollo de este trabajo título se realiza una exhaustiva búsqueda bibliográfica, que permite tener una visión actualizada sobre las características y problemas presentes en las redes inalámbricas, los distintos tipos de algoritmos genéticos, los frameworks que permiten la implementación de metaheurísticas evolutivas y por último una descripción de la computación de alta performance. El problema de localización de nodos se resolvió por medio de tres algoritmos genéticos, el primero de ellos es un algoritmo genético secuencial, el segundo es un algoritmo paralelo Maestro/Esclavo y el tercero es un algoritmo basado en un modelo de islas. Para los tres algoritmos desarrollados se implementaron la misma función objetivo y operadores genéticos. Como los algoritmos genéticos son de naturaleza estocástica, para la comparación entre ellos es necesario realizar un elevado número de ejecuciones independientes sobre el problema planteado. Una vez obtenidos los resultados de las respectivas ejecuciones se realiza un análisis estadístico que permite verificar si los resultados obtenidos (fitness) provienen de poblaciones distintas o iguales. Luego se realiza una comparación del tiempo de procesamiento entre los distintos algoritmos utilizando el Speedup y la eficiencia. Los algoritmos modelos de islas son los que obtienen los mejores resultados en función del tiempo de procesamiento. Respecto a los valores de fitness promedio obtenidos los algoritmos secuencial y los basados en modelos de islas son los que obtienen los mejores resultados.	es
dc.description.call-number	M(DC) 629.8 F733 2015	es
dc.format	application/pdf
dc.identifier.uri	https://repositorio.ubiobio.cl/handle/123456789/1481
dc.language	spa	es
dc.publisher	Universidad del Bío-Bío. Departamento de Ingeniería Eléctrica y Electrónica	es
dc.rights	info:eu-repo/semantics/acceso abierto
dc.subject	Algoritmos genéticos-diseño	es
dc.subject	Optimización combinatoria	es
dc.subject	Wireless sensor networks	es
dc.subject	Computación paralela	es
dc.subject	Análisis estadístico	es
dc.title	Diseño e implementación de un algoritmo genético paralelo para la solución de problemas de optimización combinatoria	es
dc.type	tesina	es
dspace.entity.type	memoria
ubb.Carrera	Ingeniería Civil en Automatización
ubb.Departamento	Departamento de Ingeniería Eléctrica y Electrónica
ubb.Facultad	Facultad de Ingeniería
ubb.Sede	Concepción