This article proposes a new physics-assisted genetic algorithm (PAGA) for decoupling capacitor (decap) optimization in power distribution networks (PDNs), which is, by far, the most powerful approach to efficiently minimizing the number of decaps within an enormous search space. In the proposed PAGA method, the priority of the decap ports is first determined based on their physical loop inductances. Then, an initial solution is quickly obtained by placing decaps sequentially on the port with the highest priority. Subsequently, a GA with prior physical knowledge is developed to find better decap solutions progressively. A port removal scheme that eliminates the low-priority ports and a modified mutation operation that better guides the mutation direction is proposed to accelerate the convergence of the GA. The initial solution and the proposed auxiliary schemes can significantly narrow the search space and incorporate physical knowledge into the GA, thus greatly accelerating the convergence process. Several representative state-of-the-art algorithms and commercial tools are thoroughly compared with the proposed PAGA in different application scenarios. The proposed PAGA shows remarkably better performance in efficiently finding high-quality decap solutions and exhibits strong robustness to handle real-world and large-scale problems, which brings decap optimization algorithms to a new benchmark.