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 98
- Downloads 0
Comparative Analysis of K-Means and Fuzzy C-Means Algorithms
In the arena of software, data mining technology has been considered as useful means for identifying patterns and trends of large volume of data. This approach is basically used to extract the unknown pattern from the la...
Collaborative Spectrum Sensing under Suburban Environments
Collaborative spectrum sensing for detection of white spaces helps in realizing reliable and efficient spectrum sensing algorithms, which results in efficient usage of primary spectrum in secondary fashion. Collaboration...
Optimization of Channel Coding for Transmitted Image Using Quincunx Wavelets Transforms Compression
Many images you see on the Internet today have undergone compression for various reasons. Image compression can benefit users by having pictures load faster and webpages use up less space on a Web host. Image compression...
Java Based Computer Algorithms for the Solution of a Business Mathematics Model
A novel approach is proposed as a framework for working out uncertainties associated with decisions between the choices of leasing and procurement of capital assets in a manufacturing industry. The mathematical concept o...
A Bus Arbitration Scheme with an Efficient Utilization and Distribution
Computer designers utilize the recent huge advances in Very Large Scale Integration (VLSI) to place several processors on the same chip die to get Chip Multiprocessor (CMP). The shared bus is the most common media used t...