In this paper, the applicability of heuristic methods for an automated and reactive optimization of network infrastructures in highly-dynamic communication networks is studied. With an increasing amount of (mobile) participants and at the same time significantly growing quality requirements in communication networks over the past years, optimization of communication infrastructures will become an inevitable challenge in providing a reliable and high-quality communication service. Mostly, changes in highly-dynamic networks, which may be planned or unplanned, happen swiftly, such that it is not possible to apply manual optimization. Thus, an automated and reactive optimization becomes necessary to address this problem. Two major issues arise from the optimization of highly-dynamic communication networks. First, the complexity of problems, which is either implied by the complex optimization problem or the number of different possibly concurrent goals subject to optimization. Second, the highly-dynamic optimization search space, where network topologies may change rapidly introducing severe challenges for the optimization process. Here, different evolutionary and greedy optimization heuristics for the optimal selection of monitors in communication networks are studied and compared. Monitor selection is a well-known, important, and complex (NP-hard) optimization problem, serving as a current and actual use case for the general concept of highly-dynamic communication network optimization. As the results show, two of three methods reliably provide solutions of sufficiently high quality in reasonable time, enabling the applicability of heuristic methods of optimization in highly-dynamic communication networks. Results of the experiments are obtained using state-of-the-art statistical methods for evaluation of (evolutionary) search heuristics on a set of 39 real-world and synthetic benchmark problem instances.