Optimal sensor placement is a challenging task in the design of an effective structural health monitoring system. In this paper, a novel optimal sensor placement algorithm, called adaptive monkey algorithm (AMA), to cope with the sensor placement problem for target location under constraints of the computing efficiency and convergence stability is proposed. The dual-structure coding method, instead of the traditional coding method, is adopted to code the solution. The adaptive operator is designed and implemented in the AMA, which provides an automatic technique for adjusting the climb process and watch–jump process of the monkey algorithm according to the observed performance while the search is ongoing. Two new somersault processes, i.e., reflection somersault process and mutation somersault process, are incorporated in the AMA to strengthen its global search ability. Numerical experiments involving two high-rise structures have been carried out to evaluate the performance of the proposed AMA algorithm. The results demonstrated that the innovations in the AMA make it outperform the other algorithms in most cases in terms of less iterations and generating more stable optimal solutions. This algorithm can also be easily applied to other discrete optimization problems.