A parallel tabu search alglorithm for the quadratic assignment problemReport as inadecuate

A parallel tabu search alglorithm for the quadratic assignment problem - Download this document for free, or read online. Document in PDF available to download.

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

Author: Gabrielsson, Samuel

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

Related documents