Loading…

Optimal Design of Reliable Computer Networks: A Comparison of Metaheuristics

In many computer communications network design problems, such as those faced by hospitals, universities, research centers, and water distribution systems, the topology is fixed because of geographical and physical constraints or the existence of an existing system. When the topology is known, a reas...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2003-12, Vol.9 (6), p.471-487
Main Authors: Altiparmak, Fulya, Dengiz, Berna, Smith, Alice E.
Format: Article
Language:English
Subjects:
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In many computer communications network design problems, such as those faced by hospitals, universities, research centers, and water distribution systems, the topology is fixed because of geographical and physical constraints or the existence of an existing system. When the topology is known, a reasonable approach to design is to select components among discrete alternatives for links and nodes to maximize reliability subject to cost. This problem is NP-hard with the added complication of a very computationally intensive objective function. This paper compares the performance of three classic metaheuristic procedures for solving large and realistic versions of the problem: hillclimbing, simulated annealing and genetic algorithms. Three alterations that use local search to seed the search or improve solutions during each iteration are also compared. It is shown that employing local search during evolution of the genetic algorithm, a memetic algorithm, yields the best network designs and does so at a reasonable computational cost. Hillclimbing performs well as a quick search for good designs, but cannot identify the most superior designs even when computational effort is equal to the metaheuristics. [PUBLICATION ABSTRACT]
ISSN:1381-1231
1572-9397
DOI:10.1023/B:HEUR.0000012447.32370.fd