The adaptive Fourier decomposition (AFD) uses an adaptive basis instead of a fixed basis in the rational analytic function and thus achieves a fast energy convergence rate. At each decomposition level, an important step is to determine a new basis element from a dictionary to maximize the extracted energy. The existing basis searching method, however, is only the exhaustive searching method that is rather inefficient. This paper proposes four methods to accelerate the AFD algorithm based on four typical optimization techniques including the unscented Kalman filter (UKF) method, the Nelder-Mead (NM) algorithm, the genetic algorithm (GA), and the particle swarm optimization (PSO) algorithm. In the simulation of decomposing four representative signals and real ECG signals, compared with the existing exhaustive search method, the proposed schemes can achieve much higher computation speed with a fast energy convergence, that is, in particular, to make the AFD possible for real-time applications.