Detailansicht

Ant approaches for the QAP

Stephanie Richter

Art der Arbeit

Diplomarbeit

Universität

Universität Wien

Fakultät

Fakultät für Wirtschaftswissenschaften

Betreuer*in

Richard Hartl

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.13822

URN

urn:nbn:at:at-ubw:1-29491.32214.245663-5

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Diese Diplomarbeit beschäftigt sich mit dem wissenschaftlichen Forschungsgebiet der Ameisenoptimierung und deren Algorithmen und wendet diese auf das Quadratische Zuordnungsproblem an. Das Hauptziel des Quadratischen Zuordnungsproblems besteht darin eine geeignete Zuordnung von einer gewissen Anzahl an Funktionen zu der gleichen Anzahl an möglichen Plätzen zu finden, um die Gesamtkosten zu minimieren. Dieser theoretische Ansatz kann auf direktem Weg auf Probleme der Wirklichkeit übertragen werden. Eines der besten Beispiele hierfür ist die Herausforderung, welcher ein Unternehmen sich stellen muss wenn es eine neue Produktionsstätte eröffnet. Die Produktionskosten können solang auf einem minimalen Level gehalten werden wie die verwendeten Maschinen intelligent auf ihren Standorten angeordnet werden, sodass die Gesamtsumme der Produkte zwischen Materialflüsse und Distanzen einen ökonomisch angemessenen Wert ergibt. Im theoretischen Teil dieser Arbeit werden einige der wichtigsten Ameisenalgorithmen wie MMAS und HAS-QAP diskutiert und es wird gezeigt wie die zusätzliche Implementierung von effektiven Local Search Methoden die Lösungsqualität verbessern kann. Der praktische Teil dieser Arbeit versucht einen grundlegenden MMAS Algorithmus um zusätzliche Local Search Methoden, welche auf den Ideen von Iterated Ants und Adaptive Large Neighborhood Search basieren, zu erweitern und so zu verbessern. Hierfür wurden fünf verschiedene Algorithmen in C++ implementiert: MMAS Basis, MMAS Random Removal, MMAS Product Removal Highest, MMAS Product Removal Lowest and MMAS 3 Iterated. Zuletzt werden die generierten Ergebnisse diskutiert und die Lösungsqualitäten der einzelnen Algorithmen untereinander verglichen.

Abstract

(Englisch)

This diploma thesis deals with the scientific research area of Ant Colony Optimization algorithms and applies them to the Quadratic Assignment Problem. The central aim of the Quadratic Assignment Problems is to find an optimal allocation of a certain number of facilities to the equal number of possible locations in order to minimize the overall costs. This theoretical formulation can be passed on real life problems in a straightforward way. One of the best examples is the challenge each company has to deal with when opening a new production site. The production cost can be kept to a minimum as long as the used machines are cleverly arranged to their locations so that the overall sum of the products between material flows and distances comes to an economical appropriate value. In the theoretical part of this thesis some of the most important ant algorithms like MMAS and HAS-QAP are discussed and it is shown how the additional implementation of an effective local search method can improve the solution quality. The practical part of this thesis tries to enhance a basic MMAS algorithm by implementing additional local search methods based on the ideas of Iterated Ants and Adaptive Large Neighborhood Search. Therefore five different algorithms have been implemented in C++: MMAS Basis, MMAS Random Removal, MMAS Product Removal Highest, MMAS Product Removal Lowest and MMAS 3 Iterated. At the end the generated results are discussed and the solution qualities of the individual algorithms are compared among themselves.

Autor*innen

Stephanie Richter

Haupttitel (Englisch)

Ant approaches for the QAP

Paralleltitel (Deutsch)

Ameisenansätze für das Quadratische Zuordnungsproblem

Publikationsjahr

2011

Umfangsangabe

VIII, 62 S. : Ill., graph. Darst.

Sprache

Englisch

Beurteiler*in

Richard Hartl

Klassifikationen

85 Betriebswirtschaft > 85.00 Betriebswirtschaft: Allgemeines ,

85 Betriebswirtschaft > 85.03 Methoden und Techniken der Betriebswirtschaft

AC Nummer

AC08486410

Utheses ID

12419

Studienkennzahl

UA | 157 | | |

Detailansicht

Abstracts

Schlagwörter