Development of Advanced WTA (Weapon Target Assignment) Algorithms for Parallel Processing.

摘要

The objective of weapon-target assignment (WTA) in a ballistic missile defense (BMD) system is to determine how defensive weapons should be assigned to boosters and reentry vehicles in order to maximize the survival of assets belonging to the U.S. and allied countries. The implied optimization problem requires consideration of a large number of potential weapon target assignments in order to select the most effective combination of assignments. The resulting WTA optimization problems are among the most complex encountered in mathematical programming. Indeed, simple versions of the WTA problem have been shown to be NP-complete, implying that the computations required achieve optimal solutions grow exponentially with the numbers of weapons and targets considered in the solution. The computational complexity of the WTA problem has motivated the development of heuristic algorithms that are not altogether satisfactory for use in Strategic Defense Systems (SDS). Some special cases of the WTA problem are not NP-complete and can be solved using standard optimization algorithms such as linear programming and maximum marginal return algorithms; these algorithms enjoy low computational requirements and therefore have been adopted as heuristics for solving more general WTA problems. However, experimental studies have demonstrated that these heuristic algorithms lead to significantly suboptimal solutions for certain scenarios. (kr)