Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Weighting-based Variable Neighborhood Search for Optimal Camera Placement

Abstract : The optimal camera placement problem (OCP) aims to accomplish surveillance tasks with the minimum number of cameras, which is one of the topics in the GECCO 2020 Competition and can be modeled as the unicost set covering problem (USCP). This paper presents a weighting-based variable neighborhood search (WVNS) algorithm for solving OCR. First, it simplifies the problem instances with four reduction rules based on dominance and independence. Then, WVNS converts the simplified OCP into a series of decision unicost set covering subproblems and tackles them with a fast local search procedure featured by a swap-based neighborhood structure. WVNS employs an efficient incremental evaluation technique and further boosts the neighborhood evaluation by exploiting the dominance and independence features among neighborhood moves. Computational experiments on the 69 benchmark instances introduced in the GECCO 2020 Competition on OCP and USCP show that WVNS is extremely competitive comparing to the state-of-the-art methods. It outperforms or matches several best performing competitors on all instances in both the OCP and USCP tracks of the competition, and its advantage on 15 large-scale instances are over 10%. In addition, WVNS improves the previous best known results for 12 classical benchmark instances in the literature.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636412
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:08
Dernière modification le : vendredi 5 août 2022 - 11:22:18

Identifiants

  • HAL Id : hal-03636412, version 1

Citation

Zhouxing Su, Qingyun Zhang, Zhipeng Lu, Chu-Min Li, Weibo Lin, et al.. Weighting-based Variable Neighborhood Search for Optimal Camera Placement. THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, Feb 2021, Vancouver, Canada. pp.12400-12408. ⟨hal-03636412⟩

Partager

Métriques

Consultations de la notice

44