The high speed and low energy cost are two conflicting objectives in the motion optimization of bio-inspired underwater robots, but playing a very important role. To this end, this paper proposes an optimization strategy for swimming speed and power cost using an improved NSGAII for a flexible robotic fish. A dynamic model involving flexible deformation is established for speed prediction with the hydrodynamic parameters identified. A back propagation (BP) neural network is applied to perform compensation of power cost prediction with the dynamic model’s prediction as input. In particular, an NSGA-II-AMS method is developed to improve the efficiency of solving the two-objective optimization problem based on NSGA-II. Finally, extensive simulations and experimental results demonstrate the effectiveness of the proposed optimization strategy, which offers promising prospects for the flexible robotic fish performing aquatic tasks with different performance constraints.