ScatterSearch y Busqueda Aleatoria aplicado al Problema de la mochila y del viajante

Introducción ............................................................................................................. 1
Problemas de Optimización ..................................................................................... 2
Problema de la mochila (KP). ..................................................................................................... 2
Problema del viajante(TSP)....................................................................................................... 3

Algoritmos................................................................................................................ 4
Búsqueda Aleatoria .................................................................................................................... 4
Adaptación alproblema de la Mochila .................................................................................................................. 4
Adaptación al problema del Viajante ..................................................................................................................... 5

Búsqueda Dispersa.................................................................................................................... 5
Adaptación al problema de la Mochila. ................................................................................................................. 7
Adaptación al problema del Viajante. .................................................................................................................... 8

Experimentación...................................................................................................... 9
Algoritmo Aleatorio ..................................................................................................................... 9
Problema de la Mochila ......................................................................................................................................... 9
Problema del viajante.......................................................................................................................................... 13

Scatter Search.......................................................................................................................... 20
Problema de la Mochila....................................................................................................................................... 20
Problema del viajante .......................................................................................................................................... 24

Scatter Search VS VNS ........................................................................................................... 31
Problema de la Mochila....................................................................................................................................... 31
Problema del viajante .......................................................................................................................................... 33

Conclusiones ......................................................................................................... 351

Introducción.

En el mundo de la informática y el desarrollo software, además de en nuestra vida cotidiana, existe una gran
cantidad de problemas que requieren de la aplicación de técnicas de optimización para hallar los mejores valores de
diversos parámetros. Generalmente esta optimización no se puede resolver mediante problemas de análisis, por lo
que debe enfocarse mediante el uso detécnicas de optimización heurísticas.
En este trabajo se estudiará la aplicación de dos algoritmos diferentes (búsqueda aleatoria y búsqueda dispersa),
aplicado a dos problemas de optimización, como son el problema de la mochila (KP) y el del viajante (TSP). Una
vez implementado ambos algoritmos y sus adaptaciones a los dos problemas, analizaremos su comportamiento, el
tiempo de ejecución y...