We address the problem of determining the optimal number and placement of multistatic sonar sensors to achieve maximal coverage while minimizing the number of required sensors. The use of a computationally expensive environmentally-dependent acoustic model for sonar performance prediction precludes the direct application of population-based techniques. Instead, we present computationally-frugal methods based on particle swarm optimization (PSO). Comparison of the algorithms using a surrogate model for sonar performance prediction based on Cassini ovals against a reference set generated through brute force evaluation of all configurations is presented.