Developing Efficient Metaheuristics for Communication Network Problems by using Problem-specific Knowledge

Rothlauf, Franz ; Heinzl, Armin

abwl_09_04.pdf - Published

Download (274kB)

URN: urn:nbn:de:bsz:180-madoc-9840
Document Type: Working paper
Year of publication: 2004
The title of a journal, publication series: None
Publication language: English
Institution: Business School > Sonstige - Fakultät für Betriebswirtschaftslehre
MADOC publication series: Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
Subject: 004 Computer science, internet
Subject headings (SWD): Heuristik , Algorithmus , Computerunterstützte Kommunikation
Abstract: Metaheuristics, such as evolutionary algorithms or simulated annealing, are widely applicable heuristic optimization strategies that have shown encouraging results for a large number of difficult optimization problems. To show high performance, metaheuristics need to be adapted to the properties of the problem at hand. This paper illustrates how efficient metaheuristics can be developed for communication network problems by utilizing problem-specific knowledge for the design of a high-quality problem representation. The minimum communication spanning tree (MCST) problem finds a communication spanning tree that connects all nodes and satisfies their communication requirements for a minimum total cost. An investigation into the properties of the problem reveals that optimum solutions are similar to the minimum spanning tree (MST). Consequently, a problem-specific representation, the link biased (LB) encoding, is developed, which represents trees as a list of floats. The LB encoding makes use of the knowledge that optimum solutions are similar to the MST, and encodes trees that are similar to the MST with a higher probability. Experimental results for different types of metaheuristics show that metaheuristics using the LB-encoding efficiently solve existing MCST problem instances from the literature, as well as randomly generated MCST problems of different sizes and types.
Additional information:

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.

Metadata export


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item