# A Novel Genetic Algorithm for the Synthetical Sensor-Weapon-Target Assignment Problem
## 3 Description of the Proposed Method
### Population Initialization  
A population initialization method is an important part in the framework of GA. A common way to initialize the population for this problem is random initialization, which may generate initial solutions with an inferior fitness and redundancy. In addition, S-WTA has much prior knowledge, such as the benefits of detection or damage, which should be fully considered to improve the quality of the initial population to speed up algorithm to reach global optimum. In this paper, some important prior knowledge, which was originally designed for the WTA problem [13], is adaptively improved as the rules of initialization of the S-WTA problem. It is defined as in Rule 1 and Rule 2. Rule 1 is used for the sensor-target assignment. Rule 2 is used for the weapon-target assignment. **Rule 1:** If \(q_{ik}\cdot\mathit{v}_{k}\) is the highest value among all the sensor-target pair, the assignment scheme that the \(i\)th sensor is assigned to the \(k\)th target is the most appropriate scheme. **Rule 2:** If \((p_{ik}+\sigma)\cdot\mathit{v}_{k}\) is the highest value among all the weapon-target pair, the assignment scheme that the \(i\)th weapon is assigned to the \(k\)th target is the most appropriate scheme. The flow chart of the proposed initialization method is shown in Figure 6.  
Figure 6: The flow chart of the proposed initialization method. As shown in Figure 6, the population is initialized by two procedures. First, the sensor is assigned to the target according to the Rule 1. Then, on the basis of the results of sensor assignment, the weapon is assigned according to the Rule 2. To facilitate further implementation of the algorithm, the pseudocode of the proposed method is given in Algorithm 1. ```
0: The number of sensors is \(M\). The number of weapons is \(W\). The number of targets is \(N\). The matrix of the probability of detecting and tracking the targets by the sensors is \(Q=(q_{ik})_{M\times N}\). The matrix of the probability of destroying the targets by the weapons is \(P=(p_{jk})_{W\times N}\). The maximum sensor cost of each target is \(\{{n^{\prime}}_{1},\cdots,{n^{\prime}}_{k},\cdots,{n^{\prime}}_{N}\}\). The maximum weapon cost of each target is \(\{{m^{\prime}}_{1},\cdots,{m^{\prime}}_{k},\cdots,{m^{\prime}}_{N}\}\). The threat value of each target is \(\{v_{1},\cdots,v_{k},\cdots,v_{N}\}\). 0: The initialized population \(\{C_{1},\cdots,C_{pop}\}\). 1:for\(i=1\) to \(pop\)do
2:\(C_{i}=\{c_{1},\cdots,c_{M\cdot}c_{M+1},\cdots,c_{M+W}\}=0\)
3:for\(j=1\) to \(M\)do
4: Randomly select an unassigned sensor \(s_{j}\). 5:for each target \(t\)do
6:\(V_{t}=q_{sj}\cdot v_{t}\)
7:endfor
8: Sort the targets in descending order by \(V_{t}\) as \(\{t_{1},\cdots,t_{k},\cdots,t_{N}\}\). 9: Initial the sensor cost for \(\{t_{1},\cdots,t_{k},\cdots,t_{N}\}\) as \(\{n_{1},\cdots,n_{k},\cdots,n_{N}\}=0\). 10:for\(k=1\) to \(N\)do
11:if\(n_{k}<n^{\prime}_{k}\)then
12:\(c_{s_{j}}=t_{k}\)
13:\(n_{k}\)=\(n_{k}+1\)
14:\(v_{k}=v_{k}\cdot(1-q_{sj_{k}})\)
15:break
16:endif
17:endfor
18:endfor
19: Restore the updated threat value \(\{v_{1},\cdots,v_{k},\cdots,v_{N}\}\) to the original value. 20:for\(j=1\) to \(W\)do
21: Randomly select an unassigned weapon \(w_{j}\). 22:for each target \(t\)do
23:\(V_{t}=(p_{w_{j}t}+\sigma_{t})\cdot v_{t}\)
24:endfor
25: Sort the targets in descending order by \(V_{t}\) as \(\{t_{1},\cdots,t_{k},\cdots,t_{N}\}\). 26: Initial the weapon cost for \(\{t_{1},\cdots,t_{k},\cdots,t_{N}\}\) as \(\{m_{1},\cdots,m_{i},\cdots,m_{k}\}=0\). 27:for\(k=1\) to \(N\)do
28:if\(m_{k}<m^{\prime}_{k}\) and \(n_{t_{k}}>0\)then
29:\(c_{M+w_{j}}=t_{k}\)
30:\(m_{k}\)=\(m_{k}+1\)
31:\(v^{\prime}_{k}=v^{\prime}_{k}\cdot(1-(p_{w_{j}k}+\sigma_{t_{k}}))\)
32:break
33:endif
34:endfor
35:endfor
36:endfor
```  
**Algorithm 1** Initialization  
In Algorithm 1, the procedure of sensor-target assignment is from Step 3 to Step 18. In this procedure, Step 6 is to calculate the values of the sensor-target pairs. Based on Rule 1, Step 8 determines the optimal sensor-target pair.