To tackle the problem that traditional clonal selection algorithm may suffer from premature convergence phenomenon and is lack of crossover operator problems, this paper proposes a new efficient clonal annealing optimization algorithm. The proposed algorithm combines simulated annealing algorithm with clonal selection mechanism of immune system, and maintains the balance of global and local search. The algorithm can effectively improve search efficiency, so as to speed up the convergence rate. Meanwhile, a quality factor model is used to analyze the dynamic performance of the algorithm, and an analysis of its convergence is performed using Markov chain theory. Finally, the proposed algorithm is applied to the association rule data mining, achieving satisfactory results.