A Comparison of Heuristics Applied to the Sensor Deployment Problem

PDF

Authors
  1. Pond, G.T.
  2. Wang, Y.
  3. Brimberg, J.
  4. Simms, B.
Corporate Authors
Defence R&D Canada - Centre for Operational Research and Analysis, Ottawa ON (CAN);Royal Military Coll of Canada, Kingston Ont (CAN) Center for Smart Materials and Structures
Abstract
The sensor deployment problem shares commonality with two well-known problems in optimisation: the art gallery (or museum) problem, and the set covering problem. Both of these are known to be NP-hard in computational complexity, suggesting that deterministic methods of optimising sensor locations will almost certainly yield a sub-optimal solution. In cases such as this, population-based metaheuristics are commonly used. This report compares the performance of two population-based metaheuristics (a genetic algorithm and a differential evolution algorithm) and one single-solution metaheuristic (a Vertex Swap Algorithm) when applied to two different models of the sensor deployment problem. The results suggest that the Vertex Swap Algorithm provides the best solution and competitive computational speed.

Il y a un résumé en français ici.

Report Number
DRDC-CORA-TM-2012-191 — Technical Memorandum
Date of publication
01 Aug 2012
Number of Pages
46
DSTKIM No
CA036730
CANDIS No
536427
Format(s):
Electronic Document(PDF)

Permanent link

Document 1 of 1

Date modified: