Low Earth Orbit (LEO) navigation-augmented constellations experience critical performance degradation under partial satellite failures, leading to the issues such as coverage holes, positioning inaccuracy, and excessive energy consumption during reconfiguration. To mitigate these challenges, we propose an improved non-dominated sorting genetic algorithm-ii based on associative unlocking strategy (AU-NSGA-II) to address multi-objective trade-offs under continuous small-thrust constraints. First, a hybrid Walker constellation model is formulated, integrating three key performance metrics: coverage reachability maximization, geometric dilution of precision (GDOP) minimization, and energy consumption optimization via continuous thrust trajectory modeling. Second, an associative unlocking chromosome encoding strategy is developed to selectively activate genes linked to damaged orbits, reducing decision variables by 32% compared to conventional full encoding. Third, damage-level adaptive mutation operators dynamically adjust probabilities based on orbital failure rates, prioritizing severely impaired regions. Simulations on a hybrid Walker constellation demonstrate that AU-NSGA-II achieves a uniform Pareto front distribution, improving coverage from 68.4% to 83.9% and reducing navigation errors by 43%. The optimized configurations balance coverage, accuracy, and energy efficiency, validating the framework’s adaptability to asymmetric failures.