Abstract A virus coevolutionary partheno-genetic algorithm (VEPGA), which combined a partheno-genetic algorithm (PGA) with virus evolutionary theory, is proposed to place sensors optimally on a large space structure for the purpose of modal identification. The VEPGA is composed of a host population of candidate solutions and a virus population of substrings of host individuals. The traditional crossover and mutation operators in genetic algorithm are repealed and their functions are implemented by particular partheno-genetic operators which are suitable to combinatorial optimization problems. Three different optimal sensor placement performance index, one aim on the maximization of linear independence, one aim on the maximization of modal energy and the last is a combination of the front two indices, have been investigated. The algorithm is applied to two examples: sensor placement for a portal frame and a concrete arc dam. Results show that the proposed VEPGA outperforms the sequential reduction procedure (SRP) and PGA. The combined performance index makes an excellent compromise between the linear independence aimed index and the modal energy aimed index.