Métodos de criba para problemas NP resueltos mediante el uso de procesadores híbridos

Río Álvarez, Alejandro Carlos Del (2022). Métodos de criba para problemas NP resueltos mediante el uso de procesadores híbridos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. de Sistemas Informáticos (UPM), Madrid.

Description

Title: Métodos de criba para problemas NP resueltos mediante el uso de procesadores híbridos
Author/s:
  • Río Álvarez, Alejandro Carlos Del
Contributor/s:
  • Sánchez Couso, José Ramón
Item Type: Final Project
Degree: Grado en Ingeniería del Software
Date: July 2022
Subjects:
Freetext Keywords: Procesadores híbridos; Criba; Optimización combinatoria; Knapsack problem
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB)

Abstract

El objetivo de este trabajo es mejorar el impacto en memoria que tiene el uso de las redes de procesadores bioinspirados, creando para ello una red de procesadores híbridos que apliquen diversos métodos de cribado entre cada generación. La red de procesadores híbridos así creada se pretende que tengan mejor eficiencia en espacio que las redes de procesadores bioinspirados y mejor eficiencia en tiempo que otros métodos como puede ser el backtracking. Más concretamente este trabajo estará centrado en el desarrollo de métodos de cribado para la resolución del problema de la mochila, un problema del tipo NP-completo. Podríamos pensar en cribar las mochilas por el valor de estas o por su peso, pero como dijo Charles Darwin en el origen de las especies “No es la más fuerte de las especies la que sobrevive y tampoco la más inteligente. Sobrevive aquella que mejor se adapte al cambio”, esto mismo se puede aplicar a la problemática que nos concierne pues, no necesariamente será la mochila que cuente con un mejor valor intermedio la que nos conduzca a la solución. Por ello, se hace necesario desarrollar nuestra propia función de calidad del contenido de una mochila, lo que simbolizara su capacidad para “adaptarse al cambio”. En este trabajo se presenta el problema de la mochila y se estudian diversos métodos de cribado para redes de procesadores híbridos, además, se exponen una serie de conocimientos necesarios para el entendimiento de estos métodos. Así mismo, se realizará una simulación mediante un programa en java para comparar los resultados obtenidos por algunos de estos métodos de cribado con los resultados que se obtendrían al usar una red de procesadores bioinspirados convencional en vez de una red de procesadores híbridos.Por último, se presentarán las conclusiones obtenidas con base en los resultados de la simulación. Abstract: The objective of this work is to improve the impact on memory of the use of bioinspired processor networks, creating hybrid processor networks that apply different screening methods between each generation. The aim is thus to create a network of hybrid processors that have better space efficiency than bio-inspired processor networks and better time efficiency than other methods such as backtracking. More specifically, this work will focus on the development of screening methods for solving the knapsack problem, an NP-complete problem. We could think of ordering backpacks by their value or by their weight, but, as Charles Darwin said in the Origin of Species “It is not the strongest of the species that survives and neither is it the most intelligent. The one that best adapts to change survives” [1], the same can be applied to the problem that concerns us, since it will not necessarily be the backpack that has a better intermediate value the one that would lead us to the solution. For this reason, it is necessary to develop our own quality function for the content of a backpack, which will symbolize its ability to “adapt to change”. In this paper the knapsack problem is presented and various screening methods for hybrid processor networks are studied, in addition, a series of knowledge necessary for the understanding of these methods is exposed. Furthermore, a simulation will be carried out using a Java program to compare the results obtained by some of these screening methods with the results that would be obtained by using a conventional bioinspired processor network instead of a hybrid processor network. Finally, The conclusions obtained based on the results of the simulation will be presented.

More information

Item ID: 71174
DC Identifier: https://oa.upm.es/71174/
OAI Identifier: oai:oa.upm.es:71174
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 14 Jul 2022 16:05
Last Modified: 14 Jul 2022 16:05
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM