A Parallel Simulated Annealing Algorithm for Weapon-Target Assignment Problem
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 4
Abstract
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.
Authors and Affiliations
Emrullah SONUC, Baha SEN, Safak BAYIR
Keywords
Related Articles
- EP ID EP258300
- DOI 10.14569/IJACSA.2017.080412
- Views 81
- Downloads 0
Overview of Technical Elements of Liver Segmentation
Liver diseases are life-threatening, it’s important to detect it tumor in early stages. So, for tumor detection Segmentation of the liver is a first and significant stride. Segmentation of the liver is a yet difficult un...
EMCC: Enhancement of Motion Chain Code for Arabic Sign Language Recognition
In this paper, an algorithm for Arabic sign language recognition is proposed. The proposed algorithm facilitates the communication between deaf and non-deaf people. A possible way to achieve this goal is to enable comput...
NMVSA Greedy Solution for Vertex Cover Problem
Minimum vertex cover (MVC) is a well-known NP-Complete optimization problem. The importance of MVC in theory and practical comes from the wide range of its applications. This paper describes a polynomial time greedy algo...
A New Hybrid Network Sniffer Model Based on Pcap Language and Sockets (Pcapsocks)
Nowadays, the protection and the security of data transited within computer networks represent a real challenge for developers of computer applications and network administrators. The Intrusion Detection System and Intru...
Connection Time Estimation between Nodes in VDTN
Vehicular delay tolerant network (VDTN) is a widely used communication standard for the scenarios where no end to end path is available between nodes. Data is sent from one node to another node using routing protocols of...