In this paper, an optimization procedure is derived to find the best controller for the trajectory-tracking of an autonomous underwater vehicle (AUV) subject to uncertainties (e.g., current disturbances, un-modeled dynamics and parameter variations). The proposed algorithm is based on the dynamic model of the system and a recently proposed controller called Hierarchical Robust Nonlinear Controller (HRNC). The first objective is to find the best values for the controller gains to achieve trajectory tracking of the leader AUV. Starting from a random configuration, the leader AUV and the five followers make and keep a given formation all along the trajectory. A multi-objective optimization, based on genetic algorithms, is used here. A star formation with 6 AUVs is used as a case study to test the proposed algorithm. Simulation results show that the optimized controller gains led to successful formation keeping along the selected path with relatively minimum controller output toques.