A parallel tabu search alglorithm for the quadratic assignment problemReportar como inadecuado




A parallel tabu search alglorithm for the quadratic assignment problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

2008 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis

Abstract [en] : A parallel version of the tabu search algorithm is implemented and used to optimize the solutions for a quadratic assignment problem (QAP). The instances are taken from the qaplib website (http://www.opt.math.tu-graz.ac.at/qaplib/) and we mainly concentrate on optimizing the instances announced by Sergio Carvalho derived from the ``Microarray Placement Problem'' (http://gi.cebitec.uni-bielefeld.de/comet/chiplayout/qap) where one wants to find an arrangement of the probes (small DNA fragments) on specific locations of a microarray chip. We briefly explain combinatorics including graph theory and also the theory behind combinatorial optimization, heuristics and metaheuristcs. A description of some network optimization problems are also introduced before we apply our parallel tabu search algorithm to the quadratic assignment problem. Different approaches like Boltzmann selection procedure and random restarts are used to optimize the solutions. Through our experiments, we show that our parallel version of tabu Search do indeed manage to further optimize and even find better solutions found so far in the litterature. We try out a communication protocol based on sequentially generating graphs, where each node in the graph corresponds to a CPU or tabu search thread. One of the main goals is to find out if communication helps to further optimize the best known solution found so far for each instace.

Place, publisher, year, edition, pages: 2008.

Keyword [en] : Physics Chemistry Maths, Parallel Tabu Search, Optimization, QAPLIB, heuristics, metaheuristics

Keyword [sv] : Fysik, Kemi, Matematik

Identifiers: URN: urn:nbn:se:ltu:diva-43798ISRN: LTU-EX--08/019--SELocal ID: 1a0d96e0-082a-4424-a973-d35a43f97b4aOAI: oai:DiVA.org:ltu-43798DiVA: diva2:1017040

Subject / course: Student thesis, at least 30 credits

Educational program: Computer Science and Engineering, master's level

Examiners : Söderkvist, Inge

Note: Validerat; 20101217 (root)Available from: 2016-10-04 Created: 2016-10-04Bibliographically approved



Autor: Gabrielsson, Samuel

Fuente: http://ltu.diva-portal.org/







Documentos relacionados