A Parallel Simulated Annealing Algorithm for Weapon-Target Assignment Problem
Küçük Resim Yok
Tarih
2017
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Science & Information Sai Organization Ltd
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Weapon-target assignment (WTA) is a combinatorial optimization problem and is known to be NP-complete. The WTA aims to best assignment of weapons to targets to minimize the total expected value of the surviving targets. Exact methods can solve only small-size problems in a reasonable time. Although many heuristic methods have been studied for the WTA in the literature, a few parallel methods have been proposed. This paper presents parallel simulated algorithm (PSA) to solve the WTA. The PSA runs on GPU using CUDA platform. Multi-start technique is used in PSA to improve quality of solutions. 12 problem instances (up to 200 weapons and 200 targets) generated randomly are used to test the effectiveness of the PSA. Computational experiments show that the PSA outperforms SA on average and runs up to 250x faster than a single-core CPU.
Açıklama
Anahtar Kelimeler
Weapon-Target Assignment, Multi-start Simulated Annealing, Combinatorial optimization, Parallel algorithms, GPU
Kaynak
International Journal of Advanced Computer Science and Applications
WoS Q Değeri
N/A
Scopus Q Değeri
Cilt
8
Sayı
4
