FRAMEWORK PARA EL DESARROLLO DE ALGORITMOS GENÉTICOS EN GPU

Páginas: 26 (6372 palabras) Publicado: 30 de mayo de 2014
F A CU L T A D

DE

I NG E N I E R Í A – U NI VE SI D A D

D E LA

R E P Ú BLI C A

F RAMEWORK PARA EL DESARROLLO DE
A LGORITMOS G ENÉTICOS EN GPU
P ROYECTO DE G RADO 2012

P A B L O G A R C Í A – F R A N C I S C O P O L T I – M O N T S ER R A T L Ó P E Z

TUTORES
M A R T Í N P E D EM O N T E



P A BL O E Z Z A T T I

2

R E SU M E N
Para la resolución deproblemas de optimización del tipo NP-difícil, no es posible utilizar métodos
exactos debido al excesivo tiempo de cómputo que implican. Para este tipo de problemas, las
metaheurísticas han demostrado ser una buena herramienta, aunque en problemas de gran
dimensionalidad, pueden incrementar el tiempo de cómputo, al punto de volver también
impracticable esta opción. Por esto, y por lasposibilidades que brindan las nuevas arquitecturas de
hardware, una buena alternativa es la aplicación de estrategias de computación de alto desempeño
(HPC).
En los últimos años, las tarjetas gráficas (co-procesador gráfico, GPU) han experimentado una
evolución vertiginosa. Este hecho ha motivado que muchos científicos busquen la utilización de las
GPUs, para atacar problemas depropósito general (GPGPU). Sumado a esto, la arquitectura Fermi y
la plataforma CUDA han evolucionado ofreciendo extensiones en C y C++, facilitando la
programación sobre las GPUs.
En este proyecto se realiza el diseño, la implementación y la documentación de un framework para
la implementación de algoritmos genéticos sobre arquitecturas híbridas que incluyen GPUs. En
particular, se logróun prototipo avanzado de un framework para que pueda ser utilizado por el resto
de la comunidad académica/científica. Este abarca diversos tipos de representación y sus
correspondientes operadores evolutivos.
Los resultados obtenidos sobre casos de prueba específicos para cada tipo de representación
denotan speedups de hasta 6.70x para representación binaria, 11.68x pararepresentación entera y
35.10x para representación real. Los resultados obtenidos en representación de permutación no
fueron buenos en cuanto al tiempo de ejecución, a pesar de haber realizado diversas
implementaciones para tratar de mejorar la eficiencia de los operadores evolutivos y de la función
fitness.
Palabras clave: Algoritmos Genéticos, GPU, GPGPU, CUDA, Framework.

3

4

C ONT ENI D O
Resumen ............................................................................................................................................. 3
Contenido ............................................................................................................................................ 5
1 Introducción................................................................................................................................... 7
2 Algoritmos Genéticos y Algoritmos Evolutivos ................................................................. 9
2.1 Técnicas de Computación Evolutiva ............................................................................................. 9
2.2 Algoritmos Evolutivos................................................................................................................. 10
2.3 Algoritmos Genéticos ................................................................................................................. 11
2.3.1 Tipos Básicos de Representación ........................................................................................ 13
2.3.2 Mecanismos de Selección................................................................................................... 14
2.3.3 Tipos de operadores de cruzamiento .................................................................................. 15
2.3.4 Tipos de operadores de mutación ....................................................................................... 21
2.3.5 Mecanismos de reemplazo...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Metodologías Para El Desarrollo De Algoritmos
  • Algoritmo genetico para la generacion de horarios
  • Pasos A Seguir Para Desarrollar Un Algoritmo
  • Algoritmos geneticos
  • Algoritmos Geneticos
  • Algoritmos geneticos
  • Algoritmo genetico
  • Algoritmo genético

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS