# Continuous Space Wireless Communication Tower Placement by Hybrid Simulated Annealing
## 5 Experimental Analysis
### Exploration and Exploitation Capacities  
The exploration capacity of a search algorithm is the capacity to discover new promising search regions, and the exploitation capacity of a search algorithm is the capacity to exploit the discovered promising regions. If the exploration capacity of a search algorithm is not powerful, then some promising search regions may be missed by the search algorithm, and therefore, it cannot find the region where the optimal solution is situated; if the exploitation capacity of a search algorithm is limited, then the search algorithm cannot find the optimal solution even if the search region where the optimal solution is situated is discovered by the search algorithm. To evaluate the exploration and exploitation capacities of the hybrid SA, we generate a number of test problems whose promising search regions and optimal solutions are known (the generation of such test problems is discussed later in this section) and use the hybrid SA to solve the test problems. Thus, we know if all the promising search regions are explored and if the solutions are the optimal ones for those test problems. If the hybrid SA does not discover any of the promising search regions, then the exploration capacity of the hybrid SA is questionable; if the hybrid SA explores all the promising search regions of a problem but cannot find the optimal solution or a near-optimal solution, then the exploitation capacity of the hybrid SA is limited. To generate a test problem with known promising search regions and the optimal solution, firstly, we randomly generate \(m\) wireless communication tower locations in a geographical area, making sure that the distance between any pair of wireless communication tower locations is greater than \(2\times d_{max}\). In this way, we can guarantee that there will be no user that can be covered by more than one wireless communication tower. Secondly, for each of the wireless communication towers, we randomly generate \(k\) user locations surrounding it so that all users can be covered by the wireless communication tower. Thirdly, we remove those wireless communication tower locations and obtain a test problem with \(m\times k\) users and \(m\) wireless communication towers. The test problem is to find the locations of \(m\) wireless communication towers in the geographical area. Figure 6 illustrates this test problem generation process where \(m=3\) and \(k=5\). In the first step, we create three wireless communication tower locations, as shown in Figure 5(a). Then, in the second step, we randomly generate five users surrounding each of the three wireless communication towers, as illustrated in Figure 5(b). Finally, in the third step, we remove the three wireless communication towers and obtain a test problem, as shown in Figure 5(c). The number of wireless communication towers in a test problem gives the number of promising search areas. In a test problem generated in this way, the users are clustered around the randomly generated wireless communication tower locations. Thus, if an algorithm can reach at least one user from each of the user clusters, the algorithm's exploration capacity is excellent, as it explores all the promising search areas of the problem. Let us say that the number of wireless communication towers is \(m\) and the number of users is \(k\). Then, if the algorithm can find \(m\times(k-1)+1\) or more users, then it explores all the promising search areas of the test problem. To evaluate the exploitation capacity of an algorithm, we look at the total number of users that are covered in a solution generated by the algorithm in a promising area. It can be seen from the test problem shown in Figure 5(c) that the users are clustered in three regions, which are three promising regions to which the hybrid SA should reach; otherwise, the hybrid SA will not find the optimal or near-optimal solution for the test problem.