Reducción del ancho de banda de matrices dispersos utilizando metaheurísticas
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Benemérita Universidad Autónoma de Puebla
Abstract
Introducción
El problema de minimizar el ancho de banda de matrices dispersas (Bandwidth minimización problema (BMP) se originó en 1950 cuando los ingenieros estudiaron los marcos de acero haciendo uso de las computadoras. El BMP se encuentran en un gran número de aplicaciones entre las que podemos mencionar.
Solución de sistemas de ecuaciones lineales grandes.
Ecuaciones diferenciales.
Diseño de circuitos.
Hipertextos.
Sistemas de transmisión de alta potencia.
En este trabajo de tesis nosotros trabajamos con matrices dispersas, este término se le atribuye al economista Harry Markowitz quien al analizar modelos de actividad industrial en la Rad corporación durante 1950 observo que al trabajar con matrices la mayoría de sus elementos eran ceros.
William Orchand Hayes fue el primero en implementar un código para matrices dispersas. La investigación y los trabajos realizados este tipo de matrices son ahora de mucha importancia, ya que son estándares, que se utilizan en códigos de programación lineal.
El objetivo de este trabajo de tesis es reducir el ancho de banda de matrices dispersas utilizando metaheurísticas.
Los objetivos particulares son:
1.- Implementar el algoritmo de Cuthill.Mckee.
2.- Implementar en el algoritmo de recocido simulado.
3.- Implementar el algoritmo de algoritmos genéticos.
4.- Implemento de algoritmo de colonia implementados.
5.- Comparar los algoritmos implementados.
Así este trabajo de tesis ésta compuesto por los siguientes capítulos.
1.- Conceptos Básicos
2.- Algoritmo de Cuthill-Mckee
3.- Metaheurísticas
3.1.- Recocido de Simulado.
3.2.- Algoritmos genéticos
3.3.- Colonia de hormigas
4.- Implementación y pruebas
5.-Conclusiones.
6.- Bibliografía.